Resolving Conflicts and Electing Leaders

Abstract

We review distributed algorithms for transmitting data ($n$ real numbers) under a broadcast communication model, as well as for maximum finding and for sorting. Our interest is in the basics of recursive formulas and corresponding asymptotics as $n\to \infty$. The emphasis is on concrete examples rather than general theory.

26 pages, 5 figures

References in corpus (1)

• On the asymptotic behavior of some Algorithms

Cited by in corpus (3)

• Variance of Longest Run Duration in a Random Bitstring
• Recursive PGFs for BSTs and DSTs
• Errata and Addenda to Mathematical Constants