Distributed Corruption Detection in Networks

DOI10.4086/TOC.2020.V016A001zbMath1454.05115arXiv1505.05637OpenAlexW3016900072MaRDI QIDQ5140835

Elchanan Mossel, Noga Alon, Robin Pemantle

Publication date: 17 December 2020

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

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) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10) Data encryption (aspects in computer science) (68P25) Fault detection; testing in circuits and networks (94C12) Distributed systems (68M14)

Related Items (1)

Unnamed Item

Cites Work

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

This page was built for publication: Distributed Corruption Detection in Networks