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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Naoshi SAKAMOTO, "Initial Conditions Solving the Leader Election Problem by Randomized Algorithms" in IEICE TRANSACTIONS on Information,
vol. E85-D, no. 1, pp. 203-213, January 2002, doi: .
Abstract: When a randomized algorithm elects a leader on anonymous networks, initial information (which is called in general initial condition in this paper) of some sort is always needed. In this paper, we study common properties of initial conditions that enable a randomized algorithm to elect a leader. In the previous papers, the author introduced the notion of transformation between initial conditions using distributed algorithms. By using this notion of transformation, we investigate the property of initial conditions for the leader election. We define that an initial condition C is p(N)-complete if there exists some randomized algorithm that elects a leader with probability p(N) on any size N network satisfying C. We show that we can divide p(N)-completeness into four types as follows. 1. p(N)=1: For any 1-complete initial conditions, there exists a deterministic distributed algorithm that can compute the size of the network for any initial information satisfying the initial condition. 2. inf p(N) >0: For any p(N)-complete initial conditions with inf p(N) >0, there exists a deterministic distributed algorithm that can compute an upper-bound for the size of the network for any initial information satisfying the initial condition. 3. inf p(N) converges to 0: The set of p(N)-complete initial conditions varies depending on the decrease rate of p(N). 4. p(N) decreases exponentially: Any initial condition is regarded as p(N)-complete.
URL: https://global.ieice.org/en_transactions/information/10.1587/e85-d_1_203/_p
Copiar
@ARTICLE{e85-d_1_203,
author={Naoshi SAKAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Initial Conditions Solving the Leader Election Problem by Randomized Algorithms},
year={2002},
volume={E85-D},
number={1},
pages={203-213},
abstract={When a randomized algorithm elects a leader on anonymous networks, initial information (which is called in general initial condition in this paper) of some sort is always needed. In this paper, we study common properties of initial conditions that enable a randomized algorithm to elect a leader. In the previous papers, the author introduced the notion of transformation between initial conditions using distributed algorithms. By using this notion of transformation, we investigate the property of initial conditions for the leader election. We define that an initial condition C is p(N)-complete if there exists some randomized algorithm that elects a leader with probability p(N) on any size N network satisfying C. We show that we can divide p(N)-completeness into four types as follows. 1. p(N)=1: For any 1-complete initial conditions, there exists a deterministic distributed algorithm that can compute the size of the network for any initial information satisfying the initial condition. 2. inf p(N) >0: For any p(N)-complete initial conditions with inf p(N) >0, there exists a deterministic distributed algorithm that can compute an upper-bound for the size of the network for any initial information satisfying the initial condition. 3. inf p(N) converges to 0: The set of p(N)-complete initial conditions varies depending on the decrease rate of p(N). 4. p(N) decreases exponentially: Any initial condition is regarded as p(N)-complete.},
keywords={},
doi={},
ISSN={},
month={January},}
Copiar
TY - JOUR
TI - Initial Conditions Solving the Leader Election Problem by Randomized Algorithms
T2 - IEICE TRANSACTIONS on Information
SP - 203
EP - 213
AU - Naoshi SAKAMOTO
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E85-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2002
AB - When a randomized algorithm elects a leader on anonymous networks, initial information (which is called in general initial condition in this paper) of some sort is always needed. In this paper, we study common properties of initial conditions that enable a randomized algorithm to elect a leader. In the previous papers, the author introduced the notion of transformation between initial conditions using distributed algorithms. By using this notion of transformation, we investigate the property of initial conditions for the leader election. We define that an initial condition C is p(N)-complete if there exists some randomized algorithm that elects a leader with probability p(N) on any size N network satisfying C. We show that we can divide p(N)-completeness into four types as follows. 1. p(N)=1: For any 1-complete initial conditions, there exists a deterministic distributed algorithm that can compute the size of the network for any initial information satisfying the initial condition. 2. inf p(N) >0: For any p(N)-complete initial conditions with inf p(N) >0, there exists a deterministic distributed algorithm that can compute an upper-bound for the size of the network for any initial information satisfying the initial condition. 3. inf p(N) converges to 0: The set of p(N)-complete initial conditions varies depending on the decrease rate of p(N). 4. p(N) decreases exponentially: Any initial condition is regarded as p(N)-complete.
ER -