Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks. / Augustine, John; Pandurangan, Gopal; Robinson, Peter; Roche, Scott; Upfal, Eli.

Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on. IEEE, 2015. p. 1-20.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

E-pub ahead of print

Standard

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks. / Augustine, John; Pandurangan, Gopal; Robinson, Peter; Roche, Scott; Upfal, Eli.

Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on. IEEE, 2015. p. 1-20.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Augustine, J, Pandurangan, G, Robinson, P, Roche, S & Upfal, E 2015, Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks. in Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on. IEEE, pp. 1-20. https://doi.org/10.1109/FOCS.2015.29

APA

Augustine, J., Pandurangan, G., Robinson, P., Roche, S., & Upfal, E. (2015). Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on (pp. 1-20). IEEE. https://doi.org/10.1109/FOCS.2015.29

Vancouver

Augustine J, Pandurangan G, Robinson P, Roche S, Upfal E. Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on. IEEE. 2015. p. 1-20 https://doi.org/10.1109/FOCS.2015.29

Author

Augustine, John ; Pandurangan, Gopal ; Robinson, Peter ; Roche, Scott ; Upfal, Eli. / Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks. Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on. IEEE, 2015. pp. 1-20

BibTeX

@inproceedings{13791e6983904276b2848af4b3152cf1,
title = "Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks",
abstract = "Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy churn (i.e., Nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an 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. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a constant degree graph with high expansion even under continuous high adversarial churn. Our protocol can tolerate a churn rate of up to O(n/polylog(n)) per round (where n is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only O(polylog(n)) overhead for topology maintenance: only polylogarithmic(in n) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.",
author = "John Augustine and Gopal Pandurangan and Peter Robinson and Scott Roche and Eli Upfal",
year = "2015",
month = dec,
day = "17",
doi = "10.1109/FOCS.2015.29",
language = "English",
pages = "1--20",
booktitle = "Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on",
publisher = "IEEE",

}

RIS

TY - GEN

T1 - Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

AU - Augustine, John

AU - Pandurangan, Gopal

AU - Robinson, Peter

AU - Roche, Scott

AU - Upfal, Eli

PY - 2015/12/17

Y1 - 2015/12/17

N2 - Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy churn (i.e., Nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an 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. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a constant degree graph with high expansion even under continuous high adversarial churn. Our protocol can tolerate a churn rate of up to O(n/polylog(n)) per round (where n is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only O(polylog(n)) overhead for topology maintenance: only polylogarithmic(in n) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.

AB - Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy churn (i.e., Nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an 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. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a constant degree graph with high expansion even under continuous high adversarial churn. Our protocol can tolerate a churn rate of up to O(n/polylog(n)) per round (where n is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only O(polylog(n)) overhead for topology maintenance: only polylogarithmic(in n) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.

U2 - 10.1109/FOCS.2015.29

DO - 10.1109/FOCS.2015.29

M3 - Conference contribution

SP - 1

EP - 20

BT - Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on

PB - IEEE

ER -