I'm working on a homework in which a graph of n nodes is arranged as a one-dimensional ring and every node has 3 out-going edges.
I need some help in proving that any decentralized algorithm would need at least Ω(√n) steps to forward the message from a node A to B if the nodes A and B are √n distance apart on the ring.