Deciding and Verifying Network Properties Locally with Few Output Bits

Given a boolean predicate on labeled networks (e.g., the network is acyclic, or the network is properly colored, etc.),, deciding in a distributed manner whether a given labeled network satisfies that predicate typically consists, in the standard setting, of inspecting by every node its close neighborhood, and of outputting a boolean verdict, such that the network satisfies the predicate if and only if all nodes output true. In this paper, we investigate a more general notion of distributed decision in which every node is allowed to output a constant number b > 1 of bits, which are gathered by a central authority emitting a global boolean verdict based on these outputs, such that the network satisfies the predicate if and only if this global verdict equals true. We analyze the power and limitations of this extended notion of distributed decision.