Competitive distributed job scheduling (extended abstract)

ABSTRACT

This paper examines the problem of balancing the job load in a network of processors, and introduces an online algorithm for scheduling a sequence of jobs in a competitive manner. The algorithm is shown to be polylog (n)-competitive according to a strict definition that forces the online algorithm to be competitive even when considering any bounded area of the network and bounded period of time. We also analyze the common greedy feedback-based approach, and provide matching lower and upper bounds (up to a polylogarithmic factor) for the tradeoff between the costs of searches and updates under this approach.

REFERENCES

• AAPS87: Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, and Michael Saks. Local management of a global resource in a communication network, in Proc. 28th IEEE Syrup. on Foundations of Computer Science, October 1987.
• ACG+90: Baruch Awerbuch , Israel Cidon , Inder Gopal , Marc Kaplan , Shay Kutten, Distributed control for PARIS, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.145-159, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93412]
• ACK90: Baruch Awerbuch, Israel Cidon, and Shay Kutten. Optimal maintenance of replicated information. In Proc. 31st IEEE Syrup. on Foundations of Computer Science, 1990.
• ADD82: Gregory R. Andrews , David P. Dobkin , Peter J. Downey, Distributed allocation with pools of servers, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.73-83, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806684]
• AHS91: James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks and multi-processor coordination, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.348-358, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103421]
• AP89: Baruch Awerbuch and David Peleg. Online tracking of mobile users. Technical Memo TM-410, MIT, Lab. for Computer Science, August 1989.
• AP90: Baruch Awerbuch and David Feleg. Sparse partitions. In Proc. 31st IEEE Symp. on Foundations of Computer Science, pages 503-513, 1990.
• AP91: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• CGK88: Isreal Cidon , Inder Gopal , Shay Kutten, New models and algorithms for future networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.79-89, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62560]
• FST91: Anja Feldmann , Jiří Sgall , Shang-Hua Teng, Dynamic scheduling on parallel machines, Proceedings of the 32nd annual symposium on Foundations of computer science, p.111-120, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185355]
• Gra66: R.L. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45:1563-1581, 1966.
• MRR80: John McQuillan, Ira Richer, and Eric Rosen. The new routing algorithm for the arpanet. IEEE Trans. on Commun., 28(5):711-719, May 1980.
• MV88: S.J. Mullender and P.M.B. Vit~nyi. Distributed match-making. Algorithmica, 3:367-391, 1988.
• Pel91: David Peleg, Distance-dependent distributed directories, Information and Computation, v.103 n.2, p.270-298, April 1993 [doi>10.1006/inco.1993.1020]
• PU89: David Peleg , Eli Upfal, The token distribution problem, SIAM Journal on Computing, v.18 n.2, p.229-243, April 1989 [doi>10.1137/0218015]
• Ran87: A.G. Ranade. How to emulate a shared memory. In Proc. 28th IEEE Syrup. on Foundations of Computer Science, pages 185-194, 1987.
• ST85: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• SWW91: David B. Shmoys , Joel Wein , David P. Williamson, Scheduling parallel machines on-line, Proceedings of the 32nd annual symposium on Foundations of computer science, p.131-140, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185361]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Theory