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

== Distributed algorithms ==

=== Symmetry breaking  ===
{{Theorem|Theorem (Angluin 1980)|
:There is no deterministic algorithm for leader election in a synchronous anonymous ring.
}}

=== Consensus ===
; Termination<nowiki>:</nowiki>
:All non-faulty processes eventually decide some value.
;Agreement<nowiki>:</nowiki>
:All non-faulty processes decide the same value.
;Validity<nowiki>:</nowiki>
:For each possible decision value, there is an execution in which that value is chosen.

{{Theorem|Theorem (Fischer-Lynch-Paterson)|
:There is no deterministic algorithm for solving the consensus problem in an asynchronous message-passing system with <math>n</math> processors, one of which may fail by crashing.
}}



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


{{Theorem|Ben-Or's protocol for asynchronous Byzantine agreement|
'''Input''': an initial value <math>\texttt{prefer}\in\{0,1\}</math>.
----

For <math>r=1,2,3,\ldots</math>, do:

;Phase 1<nowiki>:</nowiki>
: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;
:if <math>>\frac{n}{2}</math> of the messages have the same value <math>\texttt{prefer}</math>, then 
::<math>\texttt{vote}=\texttt{prefer}</math>; 
:else 
::<math>\texttt{vote}=?</math>;
;Phase 2<nowiki>:</nowiki>
: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;
:if <math>>t</math> of the received messages have the same value <math>\texttt{vote}\neq ?</math>, then
::'''decide''' <math>\texttt{vote}</math>;
:if there is a message with the <math>\texttt{vote}\neq ?</math>, then
::<math>\texttt{prefer}=\texttt{vote}</math>;
:else
::flip a fair coin to decide the value of <math>\texttt{prefer}</math>;
}}

== Data Streams ==

=== Fingerprinting ===

=== The count-min sketch ===