Distributed agreement in dynamic peer-to-peer networks

作者：

Highlights：

• We introduce a rigorous framework for modeling churn in a dynamic distributed network.

• We provide a fast algorithm to reach agreement even with εn nodes churning per time step.

• We provide a fast algorithm that can tolerate O((n)) nodes churning per round against the harder adaptive adversary.

• We show that deterministic agreement algorithms can tolerate at most O(1) churn per time step.

摘要

•We introduce a rigorous framework for modeling churn in a dynamic distributed network.•We provide a fast algorithm to reach agreement even with εn nodes churning per time step.•We provide a fast algorithm that can tolerate O((n)) nodes churning per round against the harder adaptive adversary.•We show that deterministic agreement algorithms can tolerate at most O(1) churn per time step.

论文关键词：Dynamic networks,Distributed computation,Fault-tolerance,P2P networks,Agreement,Churn,Randomization

论文评审过程：Received 3 March 2013, Revised 4 April 2014, Accepted 26 June 2014, Available online 12 January 2015, Version of Record 10 June 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.10.005