Work-competitive scheduling for cooperative computing with dynamic groups

ABSTRACT

The problem of cooperatively performing a set of t tasks in a decentralized setting where the computing medium is subject to failures is one of the fundamental problems in distributed computing. The setting with partitionable networks is especially challenging, as algorithmic solutions must accommodate the possibility that groups of processors become disconnected (and, perhaps, reconnected) during the computation. The efficiency of task-performing algorithms is often assessed in terms of their work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, an adversary that is able to partition the network into g components can cause any task-performing algorithm to have work Ω(t•g) even if each group of processors performs no more than the optimal number of Θ(t) tasks.Given such pessimistic lower bounds, and in order to understand better the practical implications of performing work in partitionable settings, we study distributed work-scheduling andpursue a competitiveanalysis. Specifically, we study asimple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. We compare the performance of the algorithm against that of an "off-line" algorithm with full knowledge of the future changes in the communication medium. We describe a notion of computation width, which associates a natural number with a history of changes in the communication medium, and show both upper and lower bounds on competitiveness in terms of this quantity. Specifically, we show that a simple randomized algorithm obtains the competitive ratio (1+cw/e), where cw is computation width; we then show that this ratio is tight.

REFERENCES

• 1: M. Ajtai, J. Aspnes, C. Dwork, and O. Waarts. A theory of competitive analysis for distributed algorithms. In Proceedings of the 35th Symposium on Foundations of Computer Science (FOCS 1994), pages 401--411, 1994.
• 2: Baruch Awerbuch , Shay Kutten , David Peleg, Competitive distributed job scheduling (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.571-580, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129768]
• 3: Ö. Babaoglu , R. Davoli , A. Montresor , R. Segala, System Support for Partition-Aware Network Applications, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.184, May 26-29, 1998
• 4: Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.39-50, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129717]
• 5: S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11(1):2--14, 1994.
• 6: Bogdan S. Chlebus , Roberto De Prisco , Alex A. Shvartsman, Performing tasks on synchronous restartable message-passing processors, Distributed Computing, v.14 n.1, p.49-64, January 2001 [doi>10.1007/PL00008926]
• 7: Roberto De Prisco , Alain Mayer , Moti Yung, Time-optimal message-efficient work performance in the presence of faults, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.161-172, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198082]
• 8: R.P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 51:161--166, 1950.
• 9: S. Dolev, R. Segala, and A.A. Shvartsman. Dynamic load balancing with group communication. In Proceedings of the 6th International Colloquium on Structural Information and Communication Complexity (SIROCCO 1999), pages 111--125, 1999.
• 10: Cynthia Dwork , Joseph Y. Halpern , Orli Waarts, Performing work efficiently in the presence of faults, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.91-102, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135439]
• 11: Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
• 12: Stavros Georgiades , Marios Mavronicolas , Paul G. Spirakis, Optimal, Distributed Decision-Making: The Case of No Communication, Proceedings of the 12th International Symposium on Fundamentals of Computation Theory, p.293-303, August 30-September 03, 1999
• 13: Chryssis Georgiou , Alexander Russell , Alex A. Shvartsman, Optimally work-competitive scheduling for cooperative computing with merging groups, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571848]
• 14: Chryssis Georgiou , Alex A. Shvartsman, Cooperative computing with fragmentable and mergeable groups, Journal of Discrete Algorithms, v.1 n.2, p.211-235, April 2003 [doi>10.1016/S1570-8667(03)00026-1]
• 15: Paris Christos Kanellakis , Alex A. Shvartsman, Fault-Tolerant Parallel Computation, Kluwer Academic Publishers, Norwell, MA, 1997
• 16: Grzegorz Greg Malewicz , Alexander Russell , Alexander A. Shvartsman, Distributed Cooperation During the Absence of Communication, Proceedings of the 14th International Conference on Distributed Computing, p.119-133, October 04-06, 2000
• 17: Christos H. Papadimitriou , Mihalis Yannakakis, On the value of information in distributed decision-making (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.61-64, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112606]
• 18: David Powell, Group communication, Communications of the ACM, v.39 n.4, p.50-53, April 1996 [doi>10.1145/227210.227225]
• 19: Michael Saks , Nir Shavit , Heather Woll, Optimal time randomized consensus—making resilient algorithms fast in practice, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.351-362, January 28-30, 1991, San Francisco, California, United States
• 20: 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]
• 21: Jeremy B. Sussman , Keith Marzullo, The Bancomat Problem: An Example of Resource Allocation in a Partitionable Asynchronous System, Proceedings of the 12th International Symposium on Distributed Computing, p.363-377, September 24-26, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation; Parallelism and concurrency

General Terms:
Algorithms, Theory

Keywords:
competitive analysis, distributed computation, independent tasks, on-line algorithms, partitionable networks, randomized algorithms, work complexity