A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Initial Conditions Solving the Leader Election Problem by Randomized Algorithms Condições Iniciais Resolvendo o Problema da Eleição do Líder por Algoritmos Randomizados

Naoshi SAKAMOTO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Quando um algoritmo aleatório elege um líder em redes anônimas, a informação inicial (que é chamada em geral condição inicial neste artigo) de algum tipo é sempre necessária. Neste artigo, estudamos propriedades comuns de condições iniciais que permitem que um algoritmo aleatório eleja um líder. Nos artigos anteriores, o autor introduziu a noção de transformação entre condições iniciais utilizando algoritmos distribuídos. Ao utilizar esta noção de transformação, investigamos a propriedade das condições iniciais para a eleição do líder. Definimos que uma condição inicial C is p(N)-completo se existir algum algoritmo aleatório que eleja um líder com probabilidade p(N) em qualquer tamanho N rede satisfatória C. Mostramos que podemos dividir p(N)-completude em quatro tipos, como segue. 1. p(N)=1: Para quaisquer condições iniciais 1 completas, existe um algoritmo distribuído determinístico que pode calcular o tamanho da rede para qualquer informação inicial que satisfaça a condição inicial. 2. informações p(N) >0: Para qualquer p(N)-conclua as condições iniciais com inf p(N) >0, existe um algoritmo distribuído determinístico que pode calcular um limite superior para o tamanho da rede para qualquer informação inicial que satisfaça a condição inicial. 3. informações p(N) converge para 0: O conjunto de p(N)-condições iniciais completas variam dependendo da taxa de diminuição de p(N) 4. p(N) diminui exponencialmente: Qualquer condição inicial é considerada como p(N)-completo.

Publicação
IEICE TRANSACTIONS on Information Vol.E85-D No.1 pp.203-213
Data de publicação
2002/01/01
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Algoritmos

autores

Palavra-chave