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 [math]\displaystyle{ n }[/math] processors, one of which may fail by crashing.

Rabin's common coin protocol for synchronous Byzantine agreement

Input: an initial value [math]\displaystyle{ \texttt{vote}\in\{0,1\} }[/math]. Repeat: send [math]\displaystyle{ \texttt{vote} }[/math] to all other processors; wait till votes of all other processors received; let [math]\displaystyle{ \texttt{maj} }[/math] be the majority value among all votes (including own vote); let [math]\displaystyle{ \texttt{tally} }[/math] be the number of occurrence of [math]\displaystyle{ \texttt{maj} }[/math] among all votes; If [math]\displaystyle{ \texttt{tally}\ge 2t+1 }[/math] then [math]\displaystyle{ \texttt{vote}=\texttt{maj} }[/math]; else [math]\displaystyle{ \texttt{vote}=\text{common-coin}() }[/math];

Ben-Or's protocol for asynchronous Byzantine agreement

Input: an initial value [math]\displaystyle{ \texttt{prefer}\in\{0,1\} }[/math]. For [math]\displaystyle{ r=1,2,3,\ldots }[/math], do: Phase 1: send [math]\displaystyle{ ( 1,r,\texttt{prefer}) }[/math] to all other processors; wait till [math]\displaystyle{ n-t }[/math] messages of type [math]\displaystyle{ (1,r,*) }[/math] received; if [math]\displaystyle{ \gt \frac{n}{2} }[/math] of the messages have the same value [math]\displaystyle{ \texttt{prefer} }[/math], then [math]\displaystyle{ \texttt{vote}=\texttt{prefer} }[/math]; else [math]\displaystyle{ \texttt{vote}=? }[/math]; Phase 2: send [math]\displaystyle{ ( 2,r,\texttt{vote}) }[/math] to all other processors; wait till [math]\displaystyle{ n-t }[/math] messages of type [math]\displaystyle{ (2,r,*) }[/math] received; if there is a message with the [math]\displaystyle{ \texttt{vote}\neq ? }[/math], then [math]\displaystyle{ \texttt{prefer}=\texttt{vote} }[/math]; if [math]\displaystyle{ \gt t }[/math] of these messages have the same value [math]\displaystyle{ \texttt{vote}\neq ? }[/math], then decide [math]\displaystyle{ \texttt{vote} }[/math]; else flip a fair coin to decide the value of [math]\displaystyle{ \texttt{prefer} }[/math];