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.