Amotz Bar-Noy, Rajeev Motwani, et al.
Information Processing Letters
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.
Amotz Bar-Noy, Rajeev Motwani, et al.
Information Processing Letters
Amos Fiat, Moni Naor
STOC 1991
Amotz Bar-Noy, Randeep Bhatia, et al.
Mathematics of Operations Research
Amotz Bar-Noy, Theodore Brown, et al.
MASS 2008