Distributed CONGEST Algorithms against Mobile Adversaries

DOI10.1145/3583668.3594578MaRDI QIDQ6202259zbMATH OpenOpenAlexWikidataFDO

Authors Orr Fischer, M. Parter

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

CONGESTfault toleranceinteractive coding

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed computation in the presence of mobile adversaries which can dynamically appear throughout the network. Over the years, this setting has been studied mostly under the assumption that the communication graph is fully-connected. Resilient CONGEST algorithms for general graphs, on the other hand, are currently known only for the classical static setting, i.e., where the set of corrupted edges (or nodes) is fixed throughout the entire computation. We fill this gap by providing round-efficient simulations that translate given CONGEST algorithms into equivalent algorithms that are resilient against $f$-mobile edge adversaries. Our main results are: -Perfect-Security with Mobile Eavesdroppers: A translation of any $r$-round $f$-static-secure algorithm into an equivalent $Theta(f)$-mobile-secure algorithm with $Theta(r)$ rounds. We also show that the $f$-static-secure algorithms of [Hitron, Parter and Yogev, DISC 2022 & ITCS 2023] can be modified into $f$-mobile-secure algorithms with the same number of rounds. -Resilience with Mobile Byzantine Adversaries: An $f$-mobile-byzantine simulation which is based on a decomposition of the graph into low-diameter edge-disjoint spanning trees. This provides us with near-optimal CONGEST compilers for expander graphs. It also leads to near-optimal compilers in the congested-clique model against $Theta(n)$-mobile adversaries. For general $(2f+1)$ edge-connected graphs with $f$-mobile adversary, we almost match the bounds known for the $f$-static setting, when provided a trusted pre-processing phase. Our results are based on a collection of tools from interactive coding [Gelles, Found. Trends Theor. Comput. Sci. 2017], linear sketches and low-congestion graph decomposition. The introduced toolkit might have further applications for resilient computation.

Cites work

• A coding theorem for distributed computation
• A trade-off between information and communication in broadcast protocols
• An efficient algorithm for byzantine agreement without authentication
• An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
• Asynchronous byzantine agreement protocols
• Asynchronous consensus and broadcast protocols
• Broadcast in radio networks tolerating Byzantine adversarial behavior
• Broadcasting with locally bounded byzantine faults
• Cloture Votes:n/4-resilient Distributed Consensus int + 1 rounds
• Coding for interactive communication: a survey
• Constant-Space Localized Byzantine Consensus
• Distributed algorithms made secure: a graph theoretic approach
• Distributed Broadcast Revisited: Towards Universal Optimality
• Distributed Computing: A Locality-Sensitive Approach
• Eavesdropping games
• Edge-Disjoint Spanning Trees of Finite Graphs
• Efficient and Explicit Coding for Interactive Communication
• Exact Byzantine Consensus on Undirected Graphs under Local Broadcast Model
• Fast Distributed Agreement
• From partial consistency to global broadcast
• Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds
• How to withstand mobile virus attacks (extended abstract)
• How to withstand mobile virus attacks, revisited
• scientific article; zbMATH DE number 3819094 (Why is no real title available?)
• scientific article; zbMATH DE number 1256711 (Why is no real title available?)
• scientific article; zbMATH DE number 1406798 (Why is no real title available?)
• Information dissemination in distributed systems with faulty units
• Low congestion cycle covers and their applications
• Making Asynchronous Distributed Computations Robust to Channel Noise
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Modular construction of a Byzantine agreement protocol with optimal message bit complexity
• On Byzantine broadcast in loosely connected networks
• On Expected Constant-Round Protocols for Byzantine Agreement
• On Proactive Perfectly Secure Message Transmission
• On the round complexity of randomized Byzantine agreement
• Optimal communication in networks with randomly distributed byzantine faults
• Perfectly reliable and secure message transmission tolerating mobile adversary
• Perfectly-Secure MPC with Linear Communication Complexity
• Polynomial Codes Over Certain Finite Fields
• Proactive Secret Sharing with a Dishonest Majority
• Random sampling in cut, flow, and network design problems
• Reaching Agreement in the Presence of Faults
• Reliable communication in networks with Byzantine link failures
• Secure Distributed Computing Made (Nearly) Optimal
• Small cuts and connectivity certificates: a fault tolerant approach
• The adversarial noise threshold for distributed protocols
• The Byzantine Generals Problem
• The Byzantine generals strike again
• Tight bound on mobile Byzantine agreement
• Time is not a healer (preliminary version)

This page was built for publication: Distributed CONGEST Algorithms against Mobile Adversaries

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