Thumbnail
Access Restriction
Open

Author Rabani, Yuval ♦ Tardos, Eva
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Infinite Stream ♦ Distributed Algorithm ♦ Asz Local Lemma ♦ Followup Paper Leighton ♦ Centralized Algorithm ♦ Algorithmic Version ♦ Seminal Paper Leighton ♦ Single Packet ♦ Packet Switching ♦ Local Lemma ♦ Distributed Randomized Algorithm ♦ Proof Relies ♦ Packet Scheduling Problem ♦ High Dilation ♦ High Probability ♦ Arbitrary Network
Description In a seminal paper Leighton, Maggs, and Rao consider the packet scheduling problem when a single packet has to traverse each path. They show that there exists a schedule where each packet reaches its destination in O(C + D) steps, where C is the congestion and D is the dilation. The proof relies on the Lov'asz Local Lemma, and hence is not algorithmic. In a followup paper Leighton and Maggs use an algorithmic version of the Local Lemma due to Beck to give centralized algorithms for the problem. Leighton, Maggs, and Rao also give a distributed randomized algorithm where all packets reach their destinations with high probability in O(C +D log n) steps. In this paper we develop techniques to guarantee the high probability of delivering packets without resorting to the Lov'asz Local Lemma. We improve the distributed algorithm for problems with relatively high dilation to O(C) + (log n) O(log n) D + poly(log n). We extend the techniques to handle the case of infinite streams of ...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1996-01-01
Publisher Institution In Proceedings of the 28th Annual ACM Symposium on Theory of Computing