Computer Science

Iterative approximate consensus in the presence of Byzantine link failures

Document Type

Conference Paper

Abstract

This paper explores the problem of reaching approximate consensus in synchronous point-to-point networks, where each directed link of the underlying communication graph represents a communication channel between a pair of nodes. We adopt the transient Byzantine link failure model [15, 16], where an omniscient adversary controls a subset of the directed communication links, but the nodes are assumed to be fault-free. Recent work has addressed the problem of reaching approximate consensus in incomplete graphs with Byzantine nodes using a restricted class of iterative algorithms that maintain only a small amount of memory across iterations [12, 21, 23, 24]. This paper addresses approximate consensus in the presence of Byzantine links. We extend our past work [21, 23] that provided exact characterization of graphs in which the iterative approximate consensus problem in the presence of Byzantine node failures is solvable. In particular, we prove a tight necessary and sufficient condition on the underlying communication graph for the existence of iterative approximate consensus algorithms under transient Byzantine link model [15, 16]. © 2014 Springer International Publishing.

Publication Title

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

Publication Date

2014

Volume

8593 LNCS

First Page

84

Last Page

98

ISSN

0302-9743

ISBN

9783319095806

DOI

10.1007/978-3-319-09581-3_7

APA Citation

Tseng, L., & Vaidya, N. (2014). Iterative approximate consensus in the presence of Byzantine link failures. In Networked Systems: Second International Conference, NETYS 2014, Marrakech, Morocco, May 15-17, 2014. Revised Selected Papers (pp. 84-98). Springer International Publishing.

Link to Full Text

Share

COinS