Geodesic
Equitable Probabilistic Elections in Ring Networks
Yugoslav journal of operations research, Tome 4 (1994) no. 1, p. 67 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

A probabilistic algorithm for leader election in ring networks is described and analyzed. The election is based on comparison of random priority numbers drawn independently by each station from a globally defined finite integer range, with ties resolved by additional election round, and with all stations having equal chances of being elected. The algorithm is shown to be partially correct and to terminate with probability 1. The main result of the paper is an explicit formula for the probability distribution of election time (i.e., the number of rounds). It i also shown that all moments of the distribution exist. A distinctive feature of the underlying ring model is the assumption that each receiving station can distinguish its own messages from those of others, but that the stations are otherwise indistinguishable and use no global information. This assumption is motivated by a reliability argument based on reconfigurable local area network of ring topology.
Keywords: Distributed algorithms , probabilistic algorithms , ring networks , election of ring leader, election time, permutation runs 
@article{YJOR_1994_4_1_a6,
     author = {Jernej Polajnar and Tomislav Unka\v{s}evi\'c},
     title = {Equitable {Probabilistic} {Elections} in {Ring} {Networks}},
     journal = {Yugoslav journal of operations research},
     pages = {67 },
     year = {1994},
     volume = {4},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_1994_4_1_a6/}
}
TY  - JOUR
AU  - Jernej Polajnar
AU  - Tomislav Unkašević
TI  - Equitable Probabilistic Elections in Ring Networks
JO  - Yugoslav journal of operations research
PY  - 1994
SP  - 67 
VL  - 4
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/YJOR_1994_4_1_a6/
LA  - en
ID  - YJOR_1994_4_1_a6
ER  - 
%0 Journal Article
%A Jernej Polajnar
%A Tomislav Unkašević
%T Equitable Probabilistic Elections in Ring Networks
%J Yugoslav journal of operations research
%D 1994
%P 67 
%V 4
%N 1
%U http://geodesic.mathdoc.fr/item/YJOR_1994_4_1_a6/
%G en
%F YJOR_1994_4_1_a6
Jernej Polajnar; Tomislav Unkašević. Equitable Probabilistic Elections in Ring Networks. Yugoslav journal of operations research, Tome 4 (1994) no. 1, p. 67 . http://geodesic.mathdoc.fr/item/YJOR_1994_4_1_a6/