Exact average message complexity values for distributed election on bidirectional rings of processors
Lavault, Christian
HAL, hal-00464403 / Harvested from HAL
Text on HAL
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 : 1990-07-05
Classification:  Bidirectional ring,  Complexity,  Message transmission,  Multiprocessor,  Ringed network,  Distributed system,  Computer system,  Combinatorial method,  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],  [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] 
@article{hal-00464403,
     author = {Lavault, Christian},
     title = {Exact average message complexity values for distributed election on bidirectional rings of processors},
     journal = {HAL},
     volume = {1990},
     number = {0},
     year = {1990},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00464403}
}

Lavault, Christian. Exact average message complexity values for distributed election on bidirectional rings of processors. HAL, Tome 1990 (1990) no. 0, . http://gdmltest.u-ga.fr/item/hal-00464403/