Distributed CONGEST Algorithms against Mobile Adversaries

DOI10.1145/3583668.3594578arXiv2305.14300OpenAlexW4380874726WikidataQ130816785 ScholiaQ130816785MaRDI QIDQ6202259FDOQ6202259

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)

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.

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

zbMATH Keywords

fault toleranceCONGESTinteractive coding

Mathematics Subject Classification ID

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

Cites Work

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

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)