Complexity of distributively verifying that the diameter is small
There is an $O(k)$ rounds algorithm for distinguishing between graphs of diameter at most $k$ and those with a diameter larger than $2k$.

This works in two stages:

First, each vertex broadcasts the smallest ID it has learned about for $k/2$ rounds.
For a vertex $v$, let $L_v$ be the smallest ID that $v$ has observed by the end of this stage.

Next, the algorithm makes $k+1$, such that in each iteration every vertex broadcasts the largest $L_v$ and smallest $L_u$ it has learned about. If the graph is indeed of diameter $k$, then we would have these equal in all vertices.

Assume that the graph has a diameter larger than $2k$, then any vertex $v$ has a path of length at least $k+1$ starting from it. This means that there exists a vertex $u$ such that $d(u,v)=k+1&gt; 2(k/2)$ which implies $L_u\neq L_v$. Thus, both $u,v$ would learn that not all vertices agreed on the node with the minimal identifier.