Strong Dynamic Consensus in Byzantine Faulty Systems with Churn**This research was supported in part by NSF grant CCF 1018500. Conference Paper uri icon


  • Dynamic distributed systems allow processes to join and leave the system, so the number of processes participating in a computation varies over time. Examples of dynamic distributed systems include peer-to-peer networks, sensor networks, mobile ad-hoc networks, and many more. A fundamental problem in any distributed system is to find consensus among the processes on a common input value. For dynamic distributed systems, it is not entirely clear how the problem should be formulated, as processes can join and leave before consensus is reached. We formulate and solve a strong version of the consensus problem in dynamic distributed systems in the presence of Byzantine faulty processes. We show that one cannot improve upon our algorithm in terms of the bound on the number of processes. For stochastic dynamic distributed systems, we determine the probability that a set of processes can reach strong consensus. © 2013 IEEE.

author list (cited authors)

  • Klappenecker, A., & Lee, H.

citation count

  • 0

publication date

  • December 2013