Packet distribution on a ring
David Peleg, Allen Van Gelder · Journal of Parallel and Distributed Computing · 1989
Abstract The balanced packet distribution problem on a ring of n processors requires that randomly arriving packets be stored at nodes as evenly as possible by passing packets (and other messages) around the ring. We give a protocol to achieve balanced distribution with an average message complexity of √n per packet and to show that the protocol is optimal, up to lower order terms, for unidirectional rings.