Distributed agreement in dynamic peer-to-peer networks

DOI10.1016/J.JCSS.2014.10.005MaRDI QIDQ2353391zbMATH OpenOpenAlexFDO

Authors John Augustine, Gopal Pandurangan, Peter Robinson, Eli Upfal

Publication date 13 July 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.0809

zbMATH Keywords

agreementchurndistributed computationdynamic networksfault-toleranceP2P networksrandomization

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

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}. 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 {em stable almost-everywhere agreement} with high probability even under high adversarial churn in a polylogarithmic number of rounds: 1. An $O(lo{g}^{2}n)$-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., $epsilonn$, for some small constant $epsilon>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). Our algorithm requires only polylogarithmic in $n$ bits to be processed and sent (per round) by each node. 2. An $O(logmlo{g}^{3}n)$-round randomized algorithm that achieves almost-everywhere agreement with high probability under up to $epsilonsqrtn$ churn per round (for some small $epsilon>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). This algorithm requires up to polynomial in $n$ bits (and up to $O(logm)$ bits) to be processed and sent (per round) by each node.

Recommendations

• Towards robust and efficient computation in dynamic peer-to-peer networks
• Fast Byzantine agreement in dynamic networks
• Fast Byzantine leader election in dynamic networks
• Failure recovery for structured p2p networks: protocol design and performance under churn
• Towards worst-case churn resistant peer-to-peer systems

Cites work

• A Distributed and Oblivious Heap
• A distributed polylogarithmic time algorithm for self-stabilizing skip graphs
• Algorithms – ESA 2005
• Asymptotically efficient approaches to fault-tolerance in peer-to-peer networks
• Automata, Languages and Programming
• Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary
• Coordinated consensus in dynamic networks
• Deterministic computations in time-varying graphs: broadcasting under unstructured mobility
• DEX: self-healing expanders
• Distributed computation in dynamic networks
• Fast asynchronous Byzantine agreement and leader election with full information
• Fast Byzantine agreement in dynamic networks
• Fast consensus in networks of bounded degree.
• Fast Distributed Algorithms for Computing Separable Functions
• Fast distributed computation in dynamic networks via random walks
• Faster information dissemination in dynamic networks via network coding
• Fault Tolerance in Networks of Bounded Degree
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• How to spread adversarial nodes?
• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 1161555 (Why is no real title available?)
• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• scientific article; zbMATH DE number 2079362 (Why is no real title available?)
• scientific article; zbMATH DE number 1931813 (Why is no real title available?)
• scientific article; zbMATH DE number 2119648 (Why is no real title available?)
• Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
• Network information flow
• Parsimonious flooding in dynamic graphs
• Partial information spreading with application to distributed maximum coverage
• Robust random number generation for peer-to-peer systems
• Scalable leader election
• Self-stabilization
• Size-estimation framework with applications to transitive closure and reachability
• The effect of faults on network expansion
• The expansion and mixing time of skip graphs with applications
• The hyperring: a low-congestion deterministic data structure for distributed environments
• The slide mechanism with applications in dynamic networks (extended abstract)
• Tolerating a linear number of faults in networks of bounded degree
• Towards a scalable and robust DHT
• Towards worst-case churn resistant peer-to-peer systems
• Xheal, localized self-healing using expanders

Cited in

(11)

• Dogfish: decentralized optimistic game-theoretic file sharing
• Bankrupting Sybil despite churn
• scientific article; zbMATH DE number 2080904 (Why is no real title available?)
• Fault-tolerant consensus with an abstract MAC layer
• Fast Byzantine agreement in dynamic networks
• Highly dynamic distributed computing with Byzantine failures
• Agreement over random networks
• Towards robust and efficient computation in dynamic peer-to-peer networks
• Monitoring churn in wireless networks
• Managed agreement: generalizing two fundamental distributed agreement problems
• The price of validity in dynamic networks

Describes a project that uses

Uses Software

• Xheal

This page was built for publication: Distributed agreement in dynamic peer-to-peer networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353391)