The Essence of Coin Lemmas

Appears: Proceedings of the first Workshop on Probabilistic Methods in Verification (PROBMIV), Indianapolis, USA, June 1998.

Also: A revised version appears in Volume 22 of ENTCS.

Abstract: Coin lemmas are one of the tools for the analysis of randomized distributed algorithms. Their principal role is to reduce the analysis of a randomized system to the analysis of an ordinary nondeterministic system. This paper describes the main ideas behind the formulation and use of coin lemmas and gives examples of coin lemmas of increasing complexity and generality.

Download:
Download the paper.