
In this work we study the cost of local and global proofs on distributed
verification. In this setting the nodes of a distributed system are provided
with a nondeterministic proof for the correctness of the state of the system,
and the nodes need to verify this proof by looking at only their local
neighborhood in the system.
Previous works have studied the model where each node is given its own,
possibly unique, part of the proof as input. The cost of a proof is the maximum
size of an individual label. We compare this model to a model where each node
has access to the same global proof, and the cost is the size of this global
proof.
It is easy to see that a global proof can always include all of the local
proofs, and every local proof can be a copy of the global proof. We show that
there exists properties that exhibit these relative proof sizes, and also
properties that are somewhere in between. In addition, we introduce a new lower
bound technique and use it to prove a tight lower bound on the complexity of
reversing distributed decision and establish a link between communication
complexity and distributed proof complexity.

Distributed proofs are mechanisms enabling the nodes of a network to
collectivity and efficiently check the correctness of Boolean predicates on the
structure of the network, or on datastructures distributed over the nodes
(e.g., spanning trees or routing tables). We consider mechanisms consisting of
two components: a \emph{prover} assigning a \emph{certificate} to each node,
and a distributed algorithm called \emph{verifier} that is in charge of
verifying the distributed proof formed by the collection of all certificates.
In this paper, we show that many network predicates have distributed proofs
offering a high level of redundancy, explicitly or implicitly. We use this
remarkable property of distributed proofs for establishing perfect tradeoffs
between the \emph{size of the certificate} stored at every node, and the
\emph{number of rounds} of the verification protocol. If we allow every node to
communicate to distance at most $t$, one might expect that the certificate
sizes can be reduced by a multiplicative factor of at least~$t$. In trees,
cycles and grids, we show that such tradeoffs can be established for \emph{all}
network predicates, i.e., it is always possible to linearly decrease the
certificate size. In arbitrary graphs, we show that any part of the
certificates common to all nodes can be evenly redistributed among these nodes,
achieving even a better tradeoff: this common part of the certificate can be
reduced by the size of a smallest ball of radius $t$ in the network.
In addition to these general results, we establish several upper and lower
bounds on the certificate sizes used for distributed proofs for spanning trees,
minimumweight spanning trees, diameter, additive and multiplicative spanners,
and more, improving and generalizing previous results from the literature.

We survey the recent distributed computing literature on checking whether a
given distributed system configuration satisfies a given boolean predicate,
i.e., whether the configuration is legal or illegal w.r.t. that predicate. We
consider classical distributed computing environments, including mostly
synchronous faultfree network computing (LOCAL and CONGEST models), but also
asynchronous crashprone sharedmemory computing (WAITFREE model), and mobile
computing (FSYNC model).

Prooflabeling schemes are known mechanisms providing nodes of networks with
certificates that can be verified locally by distributed algorithms. Given a
boolean predicate on network states, such schemes enable to check whether the
predicate is satisfied by the actual state of the network, by having nodes
interacting with their neighbors only. Prooflabeling schemes are typically
designed for enforcing faulttolerance, by making sure that if the current
state of the network is illegal with respect to some given predicate, then at
least one node will detect it. Such a node can raise an alarm, or launch a
recovery procedure enabling the system to return to a legal state. In this
paper, we introduce errorsensitive prooflabeling schemes. These are
prooflabeling schemes which guarantee that the number of nodes detecting
illegal states is linearly proportional to the editdistance between the
current state and the set of legal states. By using errorsensitive
prooflabeling schemes, states which are far from satisfying the predicate will
be detected by many nodes, enabling fast return to legality. We provide a
structural characterization of the set of boolean predicates on network states
for which there exist errorsensitive prooflabeling schemes. This
characterization allows us to show that classical predicates such as, e.g.,
acyclicity, and leader admit errorsensitive prooflabeling schemes, while
others like regular subgraphs don't. We also focus on compact errorsensitive
prooflabeling schemes. In particular, we show that the known prooflabeling
schemes for spanning tree and minimum spanning tree, using certificates on
$O(\log n)$ bits, and on $O\left(\log^2n\right)$ bits, respectively, are
errorsensitive, as long as the trees are locally represented by adjacency
lists, and not just by parent pointers.

In the context of distributed synchronous computing, processors perform in
rounds, and the timecomplexity of a distributed algorithm is classically
defined as the number of rounds before all computing nodes have output. Hence,
this complexity measure captures the running time of the slowest node(s). In
this paper, we are interested in the running time of the ordinary nodes, to be
compared with the running time of the slowest nodes. The nodeaveraged
timecomplexity of a distributed algorithm on a given instance is defined as
the average, taken over every node of the instance, of the number of rounds
before that node output. We compare the nodeaveraged timecomplexity with the
classical one in the standard LOCAL model for distributed network computing. We
show that there can be an exponential gap between the nodeaveraged
timecomplexity and the classical timecomplexity, as witnessed by, e.g.,
leader election. Our first main result is a positive one, stating that, in
fact, the two timecomplexities behave the same for a large class of problems
on very sparse graphs. In particular, we show that, for LCL problems on cycles,
the nodeaveraged time complexity is of the same order of magnitude as the
slowest node timecomplexity.
In addition, in the LOCAL model, the timecomplexity is computed as a worst
case over all possible identity assignments to the nodes of the network. In
this paper, we also investigate the IDaveraged timecomplexity, when the
number of rounds is averaged over all possible identity assignments. Our second
main result is that the IDaveraged timecomplexity is essentially the same as
the expected timecomplexity of randomized algorithms (where the expectation is
taken over all possible random bits used by the nodes, and the number of rounds
is measured for the worstcase identity assignment).
Finally, we study the nodeaveraged IDaveraged timecomplexity.

We extend the notion of distributed decision in the framework of distributed
network computing, inspired by recent results on socalled distributed graph
automata. We show that, by using distributed decision mechanisms based on the
interaction between a prover and a disprover, the size of the certificates
distributed to the nodes for certifying a given network property can be
drastically reduced. For instance, we prove that minimum spanning tree can be
certified with $O(\log n)$bit certificates in $n$node graphs, with just one
interaction between the prover and the disprover, while it is known that
certifying MST requires $\Omega(\log^2 n)$bit certificates if only the prover
can act. The improvement can even be exponential for some simple graph
properties. For instance, it is known that certifying the existence of a
nontrivial automorphism requires $\Omega(n^2)$ bits if only the prover can act.
We show that there is a protocol with two interactions between the prover and
the disprover enabling to certify nontrivial automorphism with $O(\log n)$bit
certificates. These results are achieved by defining and analysing a local
hierarchy of decision which generalizes the classical notions of
prooflabelling schemes and locally checkable proofs.

A standard model in network synchronised distributed computing is the LOCAL
model. In this model, the processors work in rounds and, in the classic
setting, they know the number of vertices of the network, $n$. Using $n$, they
can compute the number of rounds after which they must all stop and output. It
has been shown recently that for many problems, one can basically remove the
assumption about the knowledge of $n$, without increasing the asymptotic
running time. In this case, it is assumed that different vertices can choose
their final output at different rounds, but continue to transmit messages. In
both models, the measure of the running time is the number of rounds before the
last node outputs. In this brief announcement, the vertices do not have the
knowledge of $n$, and we consider an alternative measure: the average, over the
nodes, of the number of rounds before they output. We prove that the complexity
of a problem can be exponentially smaller with the new measure, but that
Linial's lower bound for colouring still holds.

This work studies distributed algorithms for locally optimal loadbalancing:
We are given a graph of maximum degree $\Delta$, and each node has up to $L$
units of load. The task is to distribute the load more evenly so that the loads
of adjacent nodes differ by at most $1$.
If the graph is a path ($\Delta = 2$), it is easy to solve the fractional
version of the problem in $O(L)$ communication rounds, independently of the
number of nodes. We show that this is tight, and we show that it is possible to
solve also the discrete version of the problem in $O(L)$ rounds in paths.
For the general case ($\Delta > 2$), we show that fractional load balancing
can be solved in $\operatorname{poly}(L,\Delta)$ rounds and discrete load
balancing in $f(L,\Delta)$ rounds for some function $f$, independently of the
number of nodes.

Finding a maximum independent set (MIS) of a given fam ily of axisparallel
rectangles is a basic problem in computational geom etry and combinatorics.
This problem has attracted significant atten tion since the sixties, when
Wegner conjectured that the corresponding duality gap, i.e., the maximum
possible ratio between the maximum independent set and the minimum hitting set
(MHS), is bounded by a universal constant. An interesting special case, that
may prove use ful to tackling the general problem, is the
diagonalintersecting case, in which the given family of rectangles is
intersected by a diagonal. Indeed, Chepoi and Felsner recently gave a factor 6
approximation algorithm for MHS in this setting, and showed that the duality
gap is between 3/2 and 6. In this paper we improve upon these results. First we
show that MIS in diagonalintersecting families is NPcomplete, providing one
smallest subclass for which MIS is provably hard. Then, we derive an
$O(n^2)$time algorithm for the maximum weight independent set when, in
addition the rectangles intersect below the diagonal. This improves and extends
a classic result of Lubiw, and amounts to obtain a 2approximation algo rithm
for the maximum weight independent set of rectangles intersecting a diagonal.
Finally, we prove that for diagonalintersecting families the duality gap is
between 2 and 4. The upper bound, which implies an approximation algorithm of
the same factor, follows from a simple com binatorial argument, while the
lower bound represents the best known lower bound on the duality gap, even in
the general case.