More is more: The benefits of denser sensor deployment
Matthew P. Johnson, Deniz Sariöz, et al.
INFOCOM 2009
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.
Matthew P. Johnson, Deniz Sariöz, et al.
INFOCOM 2009
Alok Aggarwal, Amotz Bar-Noy, et al.
FOCS 1992
Amotz Bar-Noy, Danny Dolev
Distributed Computing
Gilad Asharov, Moni Naor, et al.
STOC 2016