# Randomized Algorithms (Spring 2010)/Distributed algorithms, data streams

## Distributed algorithms

### Symmetry breaking

 Theorem (Angluin 1980) There is no deterministic algorithm for leader election in a synchronous anonymous ring.

### Consensus

Termination:
All non-faulty processes eventually decide some value.
Agreement:
All non-faulty processes decide the same value.
Validity:
For each possible decision value, there is an execution in which that value is chosen.
 Theorem (Fischer-Lynch-Paterson) There is no deterministic algorithm for solving the consensus problem in an asynchronous message-passing system with ${\displaystyle n}$ processors, one of which may fail by crashing.

 Rabin's common coin protocol for synchronous Byzantine agreement Input: an initial value ${\displaystyle {\texttt {vote}}\in \{0,1\}}$. Repeat: send ${\displaystyle {\texttt {vote}}}$ to all other processors; wait till votes of all other processors received; let ${\displaystyle {\texttt {maj}}}$ be the majority value among all votes (including own vote); let ${\displaystyle {\texttt {tally}}}$ be the number of occurrence of ${\displaystyle {\texttt {maj}}}$ among all votes; If ${\displaystyle {\texttt {tally}}\geq 2t+1}$ then ${\displaystyle {\texttt {vote}}={\texttt {maj}}}$; else ${\displaystyle {\texttt {vote}}={\text{common-coin}}()}$;

 Ben-Or's protocol for asynchronous Byzantine agreement Input: an initial value ${\displaystyle {\texttt {prefer}}\in \{0,1\}}$. For ${\displaystyle r=1,2,3,\ldots }$, do: Phase 1: send ${\displaystyle (1,r,{\texttt {prefer}})}$ to all other processors; wait till ${\displaystyle n-t}$ messages of type ${\displaystyle (1,r,*)}$ received; if ${\displaystyle >{\frac {n}{2}}}$ of the messages have the same value ${\displaystyle {\texttt {prefer}}}$, then ${\displaystyle {\texttt {vote}}={\texttt {prefer}}}$; else ${\displaystyle {\texttt {vote}}=?}$; Phase 2: send ${\displaystyle (2,r,{\texttt {vote}})}$ to all other processors; wait till ${\displaystyle n-t}$ messages of type ${\displaystyle (2,r,*)}$ received; if ${\displaystyle >t}$ of the received messages have the same value ${\displaystyle {\texttt {vote}}\neq ?}$, then decide ${\displaystyle {\texttt {vote}}}$; if there is a message with the ${\displaystyle {\texttt {vote}}\neq ?}$, then ${\displaystyle {\texttt {prefer}}={\texttt {vote}}}$; else flip a fair coin to decide the value of ${\displaystyle {\texttt {prefer}}}$;