Probabilistic leader election on rings of known size (Q4037443)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 177572
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Probabilistic leader election on rings of known size |
scientific article; zbMATH DE number 177572 |
Statements
18 May 1993
0 references
average case complexity of leader election
0 references
asynchronous processor rings
0 references
probabilistic algorithm
0 references
0.8678889870643616
0 references
0.8491755723953247
0 references
0.83156818151474
0 references
0.8265520930290222
0 references
Probabilistic leader election on rings of known size (English)
0 references
[For the entire collection see Zbl 0756.00009.] We are interested in the average case complexity of leader election (and related problems) on asynchronous processor rings, whose size, \(n\), is known to all constituent processors. We show that the lower bound technique introduced by \textit{P. Duris} and \textit{Z. Galil} [Two lower bounds in asynchronous distributed computation (preliminary version). In Proc. 28nd Annual Symp. on Foundations of Comput. Sci., 326-330 (1987)] can be modified to provide a direct proof of an \(\Omega(n\log n)\) lower bound for the expected message complexity of Las Vegas leader election on anonymous (identifier free) rings, that is substantially simpler than the original. This simplicity not only serves to highlight the important structure of technique but also facilitates its extension to both arbitrary ring size and to Monte Carlo algorithms (randomized algorithms that err with probability at most \(\varepsilon\)). Specifically, we prove that the expected message complexity of any probabilistic algorithm that selects a leader with probability at least \(1-\varepsilon\) on an anonymous ring of known size \(n\), is \(\Omega(n\min(\log n,\log\log(1\varepsilon)))\). A number of common function evaluation problems (including AND, OR, PARITY, and SUM) on rings of known size, are shown to inherit this complexity bound; furthermore these bounds are tight to within a constant factor.
0 references