Consider a distributed system of n processors arranged on a ring. All processors are labeled with distinct identity-numbers, but are otherwise identical. In this paper, we make use of combinatorial enumeration methods in permutations and derive the one and the same exact asymptotic value, lJ2nH,,+O(n), of the expected number of messages in both probabilistic and deterministicbidirectional variants of Chang-Roberts distributed election algorithm. This confirms the result of Bodlaender and van Leeuwen (1986) that distributed Ieader finding is indeed strictly more efficient on bidirectional rings of processors than on unidirectional ones.
Publié le : 1989-07-05
Classification:
Distributed algorithms,
Average message complexity,
Combinatorial enumeration,
Election,
Uni- and bidirectional rings,
Distributed systems,
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
@article{hal-00464399,
author = {Lavault, Christian},
title = {Average number of messages for distributed leader-finding in rings of processors},
journal = {HAL},
volume = {1989},
number = {0},
year = {1989},
language = {en},
url = {http://dml.mathdoc.fr/item/hal-00464399}
}
Lavault, Christian. Average number of messages for distributed leader-finding in rings of processors. HAL, Tome 1989 (1989) no. 0, . http://gdmltest.u-ga.fr/item/hal-00464399/