Strong Dynamic Consensus in Byzantine Faulty Systems with Churn Conference Paper

abstract

• 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.

name of conference

• 2013 International Conference on Parallel and Distributed Systems

authors

• Klappenecker, Andreas
• Lee, Hyunyoung

published proceedings

• 2013 19TH IEEE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS (ICPADS 2013)

author list (cited authors)

• Klappenecker, A., & Lee, H.

citation count

• 0

complete list of authors

• Klappenecker, Andreas||Lee, Hyunyoung

publication date

• December 2013

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS  Journal

keywords

• Dynamic Distributed Systems
• Markov Process
• Strong Consensus
• Strong Dynamic Consensus

Digital Object Identifier (DOI)

• 10.1109/ICPADS.2013.53

International Standard Book Number (ISBN) 13

• 9781479920815

start page

• 323

end page

• 330

URL

• http://dx.doi.org/10.1109/icpads.2013.53