A new competitive algorithm for group testing
Amotz Bar-Noy, Frank K. Hwang, et al.
IEEE INFOCOM 1992
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, Frank K. Hwang, et al.
IEEE INFOCOM 1992
Amotz Bar-Noy, Shlomo Kipnis
Discrete Applied Mathematics
Amotz Bar-Noy, Shlomo Kipnis
Networks
Amotz Bar-Noy, Reuven Bar-Yehuda, et al.
STOC 2000