Randeep Bhatia, Nicole Immorlica, et al.
Theory of Computing Systems
Many algorithms in distributed systems assume that the size of a single message depends on the number of processors. In this paper, we assume in contrast that messages consist of a single bit. Our main goal is to explore how the one-bit translation of unbounded message algorithms can be sped up by pipelining. We consider two 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. The routing problem is a very basic subroutine in many distributed algorithms; the three coloring problem demonstrates that pipelining is not always useful. © 1990 Springer-Verlag.
Randeep Bhatia, Nicole Immorlica, et al.
Theory of Computing Systems
Amotz Bar-Noy, Joseph Seffi Naor, et al.
Wireless Networks
Amotz Bar-Noy, Sudipto Guha, et al.
ACM Transactions on Algorithms
Moni Naor, Larry Stockmeyer
STOC 1993