Reaching approximate Byzantine consensus with multi-hop communication

DOI10.1016/J.IC.2016.12.003zbMATH Open1371.68029arXiv1411.5282OpenAlexW2559853601MaRDI QIDQ2013588FDOQ2013588

Authors: Lili Su, Nitin H. Vaidya 

Publication date: 8 August 2017

Published in: Information and Computation (Search for Journal in Brave)

Abstract: We address the problem of reaching consensus in the presence of Byzantine faults. In particular, we are interested in investigating the impact of messages relay on the network connectivity for a correct iterative approximate Byzantine consensus algorithm to exist. The network is modeled by a simple directed graph. We assume a node can send messages to another node that is up to $l$ hops away via forwarding by the intermediate nodes on the routes, where $linmathbbN$ is a natural number. We characterize the necessary and sufficient topological conditions on the network structure. The tight conditions we found are consistent with the tight conditions identified for $l=1$, where only local communication is allowed, and are strictly weaker for $l>1$. Let $l^{\ast }$ denote the length of a longest path in the given network. For $lge{l}^{\ast }$ and undirected graphs, our conditions hold if and only if $nge3f+1$ and the node-connectivity of the given graph is at least $2f+1$ , where $n$ is the total number of nodes and $f$ is the maximal number of Byzantine nodes; and for $lge{l}^{\ast }$ and directed graphs, our conditions is equivalent to the tight condition found for exact Byzantine consensus. Our sufficiency is shown by constructing a correct algorithm, wherein the trim function is constructed based on investigating a newly introduced minimal messages cover property. The trim function proposed also works over multi-graphs.

Full work available at URL: https://arxiv.org/abs/1411.5282

Recommendations

• Reaching approximate Byzantine consensus with multi-hop communication
• Iterative approximate Byzantine consensus in arbitrary directed graphs
• Iterative approximate Byzantine consensus under a generalized fault model
• An improved approximate consensus algorithm in the presence of mobile faults
• Approximate consensus in highly dynamic networks: the role of averaging algorithms

zbMATH Keywords

synchronous systemsapproximate agreementByzantine protocolsbounded-length communication paths

Mathematics Subject Classification ID

Network protocols (68M12)

Cites Work

• Introduction to algorithms
• Coordination of groups of mobile autonomous agents using nearest neighbor rules
• Title not available (Why is that?)
• Reaching a Consensus
• Title not available (Why is that?)
• Products of Indecomposable, Aperiodic, Stochastic Matrices
• Impossibility of distributed consensus with one faulty process
• Reaching Agreement in the Presence of Faults
• Reaching approximate agreement in the presence of faults
• Easy impossibility proofs for distributed consensus problems
• Iterative approximate Byzantine consensus in arbitrary directed graphs
• Fault-tolerant consensus in directed graphs
• Reaching approximate Byzantine consensus with multi-hop communication

Cited In (14)

• Defending non-Bayesian learning against adversarial attacks
• An improved approximate consensus algorithm in the presence of mobile faults
• Iterative approximate Byzantine consensus under a generalized fault model
• Robust asynchronous stochastic gradient-push: asymptotically optimal and network-independent performance for strongly convex functions
• Reaching approximate Byzantine consensus with multi-hop communication
• Recent results on fault-tolerant consensus in message-passing networks
• Resilient distributed state estimation with multi-hop communication
• Resilient leaderless and leader-follower consensus over random networks through \(\ell\)-hop communication
• Determining \(r\)- and \((r,s)\)-robustness of digraphs using mixed integer linear programming
• Secure consensus with distributed detection via two-hop communication
• Asynchronous approximate Byzantine consensus: a multi-hop relay method and tight graph conditions
• Resilient consensus for multi-agent systems subject to differential privacy requirements
• Resilient consensus in continuous-time networks with \(\ell\)-hop communication and time delay
• Iterative approximate Byzantine consensus in arbitrary directed graphs

This page was built for publication: Reaching approximate Byzantine consensus with multi-hop communication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2013588)