2014/01/26 by Lewis Tseng, Tseng, Lewis, Nitin H. Vaidya +1
Computer Science · #Cooperative Communication and Network Coding #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1401.6615
openalex publication_date 2014/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper explores the problem of reaching approximate consensus in\nsynchronous point-to-point networks, where each directed link of the underlying\ncommunication graph represents a communication channel between a pair of nodes.\nWe adopt the transient Byzantine link failure model [15, 16], where an\nomniscient adversary controls a subset of the directed communication links, but\nthe nodes are assumed to be fault-free.\n Recent work has addressed the problem of reaching approximate consen- sus in\nincomplete graphs with Byzantine nodes using a restricted class of iterative\nalgorithms that maintain only a small amount of memory across iterations [22,\n21, 23, 12]. However, to the best of our knowledge, we are the first to\nconsider approximate consensus in the presence of Byzan- tine links. We extend\nour past work that provided exact characterization of graphs in which the\niterative approximate consensus problem in the presence of Byzantine node\nfailures is solvable [22, 21]. In particular, we prove a tight necessary and\nsufficient condition on the underlying com- munication graph for the existence\nof iterative approximate consensus algorithms under transient Byzantine link\nmodel. The condition answers (part of) the open problem stated in [16].\n