Distributed agreement in dynamic peer-to-peer networks

Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we present first-known, fully-distributed algorithms for the fundamental distributed agreement problem in dynamic networks that experience heavy node churn (i.e., nodes join and leave the network continuously over time). Our algorithms guarantee stable almost-everywhere agreement with high probability even under high adversarial churn and run in time that is polylogarithmic in n (which is the stable network size). Our first algorithm can tolerate a churn of up to εn per time step, sends only polylogarithmic number of bits per node per time step, and works under an adversary that is oblivious to the algorithm's random choices. Our second algorithm, designed for the more challenging adaptive adversary, can tolerate a churn of up to ε√n. Being easy to implement, our algorithms could serve as building blocks for other non-trivial distributed computation in dynamic networks.