Revised: April 18, 2019, March 9, 2020

Published: March 30, 2020

**Keywords:**distributed computing, expander graphs, PMC model, graph separators, network testing

**ACM Classification:**C.2.m, G.2.2

**AMS Classification:**05C90, 68R10, 94C12

**Abstract:**
[Plain Text Version]

We consider the problem of
distributed
corruption detection in networks. In this model
each node of a directed graph is either truthful or corrupt.
Each node 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 *all* corrupt (that is, faulty)
nodes can be identified,
when there is a known upper bound on their number.
We are interested in networks in which
a *large fraction* of the nodes can be classified.
It is known that in the PMC model,
in order to identify all corrupt
nodes when their number is $t$,
all in-degrees 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 nodes,
and a $1-O(1/d)$ fraction of the truthful nodes can be
identified, whenever there is a majority of truthful nodes.
We also observe that if the graph is very far from being a good expander,
namely, if the deletion of a small set of nodes splits the graph
into small components, then no corruption
detection is possible even if most of the nodes are truthful.
Finally we discuss the algorithmic aspects and the computational
hardness of the problem.