  We study the effect of limiting the number of different messages a node can
transmit simultaneously on the verification complexity of proof-labeling
schemes (PLS). In a PLS, each node is given a label, and the goal is to verify,
by exchanging messages over each link in each direction, that a certain global
predicate is satisfied by the system configuration. We consider a single
parameter r that bounds the number of distinct messages that can be sent
concurrently by any node: in the case r=1, each node may only send the same
message to all its neighbors (the broadcast model), in the case r is at least
Delta, where Delta is the largest node degree in the system, each neighbor may
be sent a distinct message (the unicast model), and in general, for r between 1
and Delta, each of the r messages is destined to a subset of the neighbors.
  We show that message compression linear in r is possible for verifying
fundamental problems such as the agreement between edge endpoints on the edge
state. Some problems, including verification of maximal matching, exhibit a
large gap in complexity between r=1 and r>1. For some other important
predicates, the verification complexity is insensitive to r, e.g., the question
whether a subset of edges constitutes a spanning-tree. We also consider the
congested clique model. We show that the crossing technique for proving lower
bounds on the verification complexity can be applied in the case of congested
clique only if r=1. Together with a new upper bound, this allows us to
determine the verification complexity of MST in the broadcast clique. Finally,
we establish a general connection between the deterministic and randomized
verification complexity for any given number r.
