Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks

John Augustine, Gopal Pandurangan, Peter Robinson and Eli Upfal

Abstract:
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 {\em churn} (i.e., nodes join and leave the network continuously over time). Our main contributions are randomized distributed algorithms that guarantee {\em stable almost-everywhere agreement} with high probability even under high adversarial churn in polylogarithmic number of rounds. In particular, we present the following results:
1. An -round (n is the stable network size) randomized algorithm that achieves almost-everywhere agreement with high probability under up to {\em linear} churn {\em per round} (i.e., , for some small constant ), assuming that the churn is controlled by an oblivious adversary (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 -round randomized algorithm that achieves almost-everywhere agreement with high probability under up to churn per round (for some small ), 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.

Guests: Gopal Pandurangan with John Augustine and Peter Robinson
Host: Chen Avin

Byzantine Agreement with Homonyms

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert and Hung Tran-The

Abstract:
So far, the distributed computing community has either assumed that the processes of a distributed system all have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. In a sense, these are two extremes of the same general model: namely, n processes can use l authenticated identifiers, where 1 ≤ l ≤ n. This paper studies Byzantine agreement in this general model assuming several processes can share the same identifier.
We study Byzantine agreement in a message-passing system with homonyms. We assume up to t < n of the processes can be Byzantine. We prove the following results: (i) synchronous agreement is possible if and only if l > 3t; (ii) partially synchronous agreement is possible if and only if 3t < l ≤ n < 2l−3t; (iii) asynchronous eventual agreement is possible if and only if l > 3t.

Guset: Rachid Guerraoui
Host: Zvi Lotker