  We introduce a communication model called universal SMP, in which Alice and
Bob receive a function $f$ belonging to a family $\mathcal{F}$, and inputs $x$
and $y$. Alice and Bob use shared randomness to send a message to a third party
who cannot see $f, x, y$, or the shared randomness, and must decide $f(x,y)$.
Our main application of universal SMP is to relate communication complexity to
graph labeling, where the goal is to give a short label to each vertex in a
graph, so that adjacency or other functions of two vertices $x$ and $y$ can be
determined from the labels $\ell(x),\ell(y)$. We give a universal SMP protocol
using $O(k^2)$ bits of communication for deciding whether two vertices have
distance at most $k$ on distributive lattices (generalizing the $k$-Hamming
Distance problem in communication complexity), and explain how this implies an
$O(k^2\log n)$ labeling scheme for determining $\mathrm{dist}(x,y) \leq k$ on
distributive lattices with size $n$; in contrast, we show that a universal SMP
protocol for determining $\mathrm{dist}(x,y) \leq 2$ in modular lattices (a
superset of distributive lattices) has super-constant $\Omega(n^{1/4})$
communication cost. On the other hand, we demonstrate that many graph families
known to have efficient adjacency labeling schemes, such as trees,
low-arboricity graphs, and planar graphs, admit constant-cost communication
protocols for adjacency. Trees also have an $O(k)$ protocol for deciding
$\mathrm{dist}(x,y) \leq k$ and planar graphs have an $O(1)$ protocol for
$\mathrm{dist}(x,y) \leq 2$, which implies a new $O(\log n)$ labeling scheme
for the same problem on planar graphs.
