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
      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
      0 references
      0 references
      0 references
      0 references

      Identifiers