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

From EtoneWiki
Jump to: navigation, 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 processors, one of which may fail by crashing.


Rabin's common coin protocol for synchronous Byzantine agreement

Input: an initial value .


Repeat:

send to all other processors;
wait till votes of all other processors received;
let be the majority value among all votes (including own vote);
let be the number of occurrence of among all votes;
If then
;
else
;


Ben-Or's protocol for asynchronous Byzantine agreement

Input: an initial value .


For , do:

Phase 1:
send to all other processors;
wait till messages of type received;
if of the messages have the same value , then
;
else
;
Phase 2:
send to all other processors;
wait till messages of type received;
if of the received messages have the same value , then
decide ;
if there is a message with the , then
;
else
flip a fair coin to decide the value of ;

Data Streams

Fingerprinting

The count-min sketch