The Essence of Coin Lemmas
Roberto Segala · Electronic Notes in Theoretical Computer Science · 1999
Coin lemmas are a tool 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.