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

From TCS Wiki
Revision as of 07:21, 22 June 2010 by imported>WikiSysop (→‎Min-cut sketch)
Jump to navigation Jump to search

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 asynchronous 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 all of these 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 all of these messages have the same value [math]\displaystyle{ \texttt{vote}\neq ? }[/math], then
decide [math]\displaystyle{ \texttt{vote} }[/math];
else if at least [math]\displaystyle{ n-2t }[/math] of these messages have the same value [math]\displaystyle{ \texttt{vote}\neq ? }[/math], then
[math]\displaystyle{ \texttt{prefer}=\texttt{vote} }[/math];
else
flip a fair coin to decide the value of [math]\displaystyle{ \texttt{prefer} }[/math];


Data Streams

Fingerprinting

Min-count sketch