Amotz Bar-Noy, Shlomo Kipnis
Networks
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, Shlomo Kipnis
Networks
Miklos Ajtai, James Aspnes, et al.
SODA 1995
Amotz Bar-Noy, Sudipto Guha, et al.
SIAM Journal on Computing
Cynthia Dwork, Moni Naor, et al.
Journal of the ACM