TY - GEN
T1 - Towards robust and efficient computation in dynamic Peer-to-Peer networks
AU - Augustine, John
AU - Pandurangan, Gopal
AU - Robinson, Peter
AU - Upfal, Eli
PY - 2012
Y1 - 2012
N2 - 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 almost-everywhere agreement with high probability under up to linear churn per round (i.e., en, 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). 2. An O(log m log3 n)-round randomized algorithm that achieves almost-everywhere agreement with high probability under up to ε√n churn per round (for some small ε > 0), where m is the size of the input value domain, that works even under an adaptive adversary (that also knows the past random choices made by the algorithm). Our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings (i.e., high churn rates per step). Furthermore, they are localized (i.e., do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in dynamic P2P networks.
AB - 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 almost-everywhere agreement with high probability under up to linear churn per round (i.e., en, 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). 2. An O(log m log3 n)-round randomized algorithm that achieves almost-everywhere agreement with high probability under up to ε√n churn per round (for some small ε > 0), where m is the size of the input value domain, that works even under an adaptive adversary (that also knows the past random choices made by the algorithm). Our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings (i.e., high churn rates per step). Furthermore, they are localized (i.e., do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in dynamic P2P networks.
KW - Distributed algorithm
KW - Dynamic network
KW - Expander graph
KW - Peer-to-Peer network
KW - Randomized algorithm
KW - Stable agreement
UR - http://www.scopus.com/inward/record.url?scp=84860120033&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860120033&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973099.47
DO - 10.1137/1.9781611973099.47
M3 - Conference contribution
AN - SCOPUS:84860120033
SN - 9781611972108
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 551
EP - 569
BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
PB - Association for Computing Machinery
T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
Y2 - 17 January 2012 through 19 January 2012
ER -