Distributed agreement in dynamic peer-to-peer networks

• We introduce a rigorous framework for modeling churn in a dynamic distributed network.
• We provide a fast algorithm to reach agreement even with εn nodes churning per time step.
• We provide a fast algorithm that can tolerate O((n)) nodes churning per round against the harder adaptive adversary.
• We show that deterministic agreement algorithms can tolerate at most O(1)O(1) churn per time step.

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.