Computer Science

An improved approximate consensus algorithm in the presence of mobile faults

Document Type

Conference Paper

Abstract

This paper explores the problem of reaching approximate consensus in synchronous point-to-point networks, where each pair of nodes is able to communicate with each other directly and reliably. We consider the mobile Byzantine fault model proposed by Garay ’94 – in the model, an omniscient adversary can corrupt up to f nodes in each round, and at the beginning of each round, faults may “move” in the system (i.e., different sets of nodes may become faulty in different rounds). Recent work by Bonomi et al. ’16 proposed a simple iterative approximate consensus algorithm which requires at least 4f+1 nodes. This paper proposes a novel technique of using “confession” (a mechanism to allow other nodes to ignore past behavior) and a variant of reliable broadcast to improve the fault-tolerance level. In particular, we present an approximate consensus algorithm that requires only ⌈7f/2⌈ + 1 nodes, an ⌈f/2⌉ improvement over the state-of-the-art algorithms. Moreover, we also show that the proposed algorithm is optimal within a family of round-based algorithms.

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Publication Date

2017

Volume

10616 LNCS

First Page

109

Last Page

125

ISSN

0302-9743

ISBN

9783319690834

DOI

10.1007/978-3-319-69084-1_8

Keywords

approximate consensus, Byzantine mobile faults, iterative algorithms

APA Citation

Tseng, L. (2017, October). An improved approximate consensus algorithm in the presence of mobile faults. In International Symposium on Stabilization, Safety, and Security of Distributed Systems (pp. 109-125). Cham: Springer International Publishing.

Link to Full Text

Share

COinS