Distributed agreement in dynamic peer-to-peer networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

4 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)1088-1109
Journal / PublicationJournal of Computer and System Sciences
Volume81
Issue number7
Online published12 Jan 2015
Publication statusPublished - Nov 2015
Externally publishedYes

Abstract

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.

Research Area(s)

  • Agreement, Churn, Distributed computation, Dynamic networks, Fault-tolerance, P2P networks, Randomization

Citation Format(s)

Distributed agreement in dynamic peer-to-peer networks. / Augustine, John; Pandurangan, Gopal; Robinson, Peter; Upfal, Eli.

In: Journal of Computer and System Sciences, Vol. 81, No. 7, 11.2015, p. 1088-1109.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review