Towards robust and efficient computation in dynamic peer-to-peer networks
John E. Augustine, Gopal Pandurangan, Peter D. Robinson, Eli Upfal · 2012
Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node churn (i.e., nodes join and leave the network continuously over time). Our goal is to design fast algorithms (running in a small number of rounds) that guarantee, despite high node churn rate, that almost all nodes reach a stable agreement. Our main contributions are randomized distributed algorithms that guarantee stable almost-everywhere agreement with high probability even under high adversarial churn in a polylogarithmic number of rounds. In particular, we present the following results: 1. An O(log 2 n)-round (n is the stable network size) randomized algorithm that achieves almosteverywhere agreement with high probability under up to linear churn per round (i.e., εn, for some small constant ε> 0), assuming that the churn is controlled by an oblivious adversary (that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm).