Distributed corruption detection in networks

DOI10.4086/TOC.2020.V016A001zbMATH Open1454.05115arXiv1505.05637OpenAlexW3016900072MaRDI QIDQ5140835FDOQ5140835

Authors: Noga Alon, Elchanan Mossel, Robin Pemantle 

Publication date: 17 December 2020

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Locating corruptions in a replicated file in a distributed environment
• Network Structure Identification From Corrupt Data Streams
• Distributed Detection in the Presence of Byzantine Attacks

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)