Competitive distributed job scheduling
Baruch Awerbuch, Shay Kutten, et al.
STOC 1992
This note deals with store-and-forward deadlock prevention in communication networks. The approach we adopt is that of establishing buffer classes in order to prevent cyclic wailing chains. This type of solutions usually tends to require many buffers. The main contribution of the current note is in showing that the number of required buffers can be reduced considerably by employing a hierarchical organization of the network. The note proposes a new hierarchical scheme for arbitrary networks, that features a tradeoff between the communication overhead and the buffer requirements of the routing. This tradeoff can be shown to be close to optimal. © 1994 IEEE
Baruch Awerbuch, Shay Kutten, et al.
STOC 1992
David Peleg, Eli Upfal
STOC 1988
Ray Bird, I.S. Gopal, et al.
IEEE Journal on Selected Areas in Communications
Baruch Awerbuch, Rohit Khandekar
STOC 2008