Randomized Algorithms (Spring 2010)/Distributed algorithms, data streams: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop m (Protected "Randomized Algorithms (Spring 2010)/Distributed algorithms, data streams" ([edit=sysop] (indefinite) [move=sysop] (indefinite))) |
||
(5 intermediate revisions by the same user not shown) | |||
Line 20: | Line 20: | ||
{{Theorem|Rabin's common coin protocol for | {{Theorem|Rabin's common coin protocol for synchronous Byzantine agreement| | ||
'''Input''': an initial value <math>\texttt{vote}\in\{0,1\}</math>. | '''Input''': an initial value <math>\texttt{vote}\in\{0,1\}</math>. | ||
---- | ---- | ||
Line 44: | Line 44: | ||
:send <math>( 1,r,\texttt{prefer})</math> to all other processors; | :send <math>( 1,r,\texttt{prefer})</math> to all other processors; | ||
:wait till <math>n-t</math> messages of type <math>(1,r,*)</math> received; | :wait till <math>n-t</math> messages of type <math>(1,r,*)</math> received; | ||
:if | :if <math>>\frac{n}{2}</math> of the messages have the same value <math>\texttt{prefer}</math>, then | ||
::<math>\texttt{vote}=\texttt{prefer}</math>; | ::<math>\texttt{vote}=\texttt{prefer}</math>; | ||
:else | :else | ||
Line 51: | Line 51: | ||
:send <math>( 2,r,\texttt{vote})</math> to all other processors; | :send <math>( 2,r,\texttt{vote})</math> to all other processors; | ||
:wait till <math>n-t</math> messages of type <math>(2,r,*)</math> received; | :wait till <math>n-t</math> messages of type <math>(2,r,*)</math> received; | ||
:if | :if <math>>t</math> of the received messages have the same value <math>\texttt{vote}\neq ?</math>, then | ||
::'''decide''' <math>\texttt{vote}</math>; | ::'''decide''' <math>\texttt{vote}</math>; | ||
: | :if there is a message with the <math>\texttt{vote}\neq ?</math>, then | ||
::<math>\texttt{prefer}=\texttt{vote}</math>; | ::<math>\texttt{prefer}=\texttt{vote}</math>; | ||
:else | :else | ||
::flip a fair coin to decide the value of <math>\texttt{prefer}</math>; | ::flip a fair coin to decide the value of <math>\texttt{prefer}</math>; | ||
}} | }} | ||
== Data Streams == | == Data Streams == | ||
Line 64: | Line 63: | ||
=== Fingerprinting === | === Fingerprinting === | ||
=== | === The count-min sketch === |
Latest revision as of 09:13, 12 January 2011
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 [math]\displaystyle{ \gt t }[/math] of the received messages have the same value [math]\displaystyle{ \texttt{vote}\neq ? }[/math], then
- decide [math]\displaystyle{ \texttt{vote} }[/math];
- if there is a message with the [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];