Header menu link for other important links
Distributed agreement in dynamic peer-to-peer networks
Published in Academic Press Inc.
Volume: 81
Issue: 7
Pages: 1088 - 1109
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. © 2014 Elsevier Inc. All rights reserved.
About the journal
JournalJournal of Computer and System Sciences
PublisherAcademic Press Inc.
Open AccessYes
Concepts (10)
  •  related image
  •  related image
  •  related image
  •  related image
    Peer to peer networks
  •  related image
  •  related image
    Distributed computations
  •  related image
    Dynamic network
  •  related image
    P2p network
  •  related image
  •  related image
    Distributed computer systems