One bit algorithms
Amotz Bar-Noy, Joseph Seffi Naor, Moni Naor · 1988
Many algorithms in distributed systems assume that the size of a single message depends on the number of processors.In this paper, we assume that messages consist of only one bit.Our main goal is to explore how the onebit translation of unbounded message algorithms can be sped up by pipelining.We consider three problems.The first is routing between two processors in an arbitrary network and in some special networks (ring, grid, hypercube).The second problem is coloring a synchronous ring with three colors, and the third is counting the number of processors in a synchronous network where each processor knows only its neighbors.The routing problem is a very basic subroutine in many distributed al-