Distributed corruption detection in networks

DOI10.4086/TOC.2020.V016A001MaRDI QIDQ5140835zbMATH OpenOpenAlexFDO

Authors Noga Alon, Elchanan Mossel, Robin Pemantle

Publication date 17 December 2020

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

distributed computingPMC modelexpander graphsgraph separatorsnetwork testing

Mathematics Subject Classification ID

Applications of graph theory (05C90) Data encryption (aspects in computer science) (68P25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Fault detection; testing in circuits and networks (94C12) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Abstract: We consider the problem of distributed corruption detection in networks. In this model, each vertex of a directed graph is either truthful or corrupt. Each vertex reports the type (truthful or corrupt) of each of its outneighbors. If it is truthful, it reports the truth, whereas if it is corrupt, it reports adversarially. This model, first considered by Preparata, Metze, and Chien in 1967, motivated by the desire to identify the faulty components of a digital system by having the other components checking them, became known as the PMC model. The main known results for this model characterize networks in which emph{all} corrupt (that is, faulty) vertices can be identified, when there is a known upper bound on their number. We are interested in networks in which the identity of a emph{large fraction} of the vertices can be identified. It is known that in the PMC model, in order to identify all corrupt vertices when their number is $t$, all indegrees have to be at least $t$. In contrast, we show that in $d$ regular-graphs with strong expansion properties, a $1-O(1/d)$ fraction of the corrupt vertices, and a $1-O(1/d)$ fraction of the truthful vertices can be identified, whenever there is a majority of truthful vertices. We also observe that if the graph is very far from being a good expander, namely, if the deletion of a small set of vertices splits the graph into small components, then no corruption detection is possible even if most of the vertices are truthful. Finally, we discuss the algorithmic aspects and the computational hardness of the problem.

Recommendations

• Noisy corruption detection
• Edge Fault Tolerance on Sparse Networks
• Detecting a Network Failure
• Almost Sure Fault Tolerance in Random Graphs
• Almost-everywhere secure computation with edge corruptions

Cites work

• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• A diagnosing algorithm for networks
• A survey of fault localization techniques in computer networks
• Almost-Everywhere Secure Computation
• Characterization of Connection Assignment of Diagnosable Systems
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Expander graphs and their applications
• Explicit Concentrators from Generalized N-Gons
• Explicit construction of linear sized tolerant networks
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Fault Tolerance in Networks of Bounded Degree
• Graph expansion and the unique games conjecture
• Introduction to algorithms.
• Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
• Optimization of Reduced Dependencies for Synchronous Sequential Machines
• Ramanujan graphs
• The Byzantine Generals Problem

Cited in

(4)

• Network Structure Identification From Corrupt Data Streams
• scientific article; zbMATH DE number 7559088 (Why is no real title available?)
• Distributed Detection in the Presence of Byzantine Attacks
• Locating corruptions in a replicated file in a distributed environment

This page was built for publication: Distributed corruption detection in networks

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