{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:58Z","timestamp":1787337538337,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>The problem of cooperatively performing a set of t tasks in a decentralized computing environment 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 work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, the scenario where the processors are partitioned into g disconnected components causes any task-performing algorithm to have work $\\Omega(t\\cdot g)$ even if each group of processors performs no more than the optimal number of $\\Theta(t)$ tasks. Given that such pessimistic lower bounds apply to any scheduling algorithm, we pursue a competitive analysis. Specifically, this paper studies a simple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. The performance of this algorithm is compared against that of an omniscient off-line algorithm with full knowledge of the future changes in the communication medium. The paper describes a notion of computation width, which associates a natural number with a history of changes in the communication medium, and shows both upper and lower bounds on work-competitiveness in terms of this quantity. Specifically, it is shown that the simple randomized algorithm obtains the competitive ratio $(1+\\mathbf{cw}\/e)$, where $\\mathbf{cw}$ is the computation width and e is the base of the natural logarithm ($e=2.7182\\ldots$); this competitive ratio is then shown to be tight.<\/jats:p>","DOI":"10.1137\/s0097539704440442","type":"journal-article","created":{"date-parts":[[2005,8,9]],"date-time":"2005-08-09T16:06:38Z","timestamp":1123603598000},"page":"848-862","source":"Crossref","is-referenced-by-count":15,"title":["Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups"],"prefix":"10.1137","volume":"34","author":[{"given":"Chryssis","family":"Georgiou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Russell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander A.","family":"Shvartsman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Aspnes, C. Dwork, and O. Waarts,\n                      A theory of competitive analysis for distributed algorithms\n                      , in Proceedings of the 35th Symposium on Foundations of Computer Science (FOCS 1994), IEEE, Los Alamitos, CA, 1994, pp. 401\u2013411.","DOI":"10.1109\/SFCS.1994.365676"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794319126"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, S. Kutten, and D. Peleg,\n                      Competitive distributed job scheduling\n                      , in Proceedings of the 24th ACM Symposium on Theory of Computing (STOC 1992), ACM, New York, 1992, pp. 571\u2013580.","DOI":"10.1145\/129712.129768"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"O. Babaoglu, R. Davoli, A. Montresor, and R. Segala,\n                      System support for partition\u2010aware network applications\n                      , in Proceedings of the 18th IEEE International Conference on Distributed Computing Systems (ICDCS 1998), IEEE, Los Alamitos, CA, 1998, pp. 184\u2013191.","DOI":"10.1109\/ICDCS.1998.679501"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1073"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294260"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008926"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R. De Prisco, A. Mayer, and M. Yung,\n                      Time\u2010optimal message\u2010efficient work performance in the presence of faults\n                      , in Proceedings of the 13th ACM Symposium on Principles of Distributed Computing (PODC 1994), ACM, New York, 1994, pp. 161\u2013172.","DOI":"10.1145\/197917.198082"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"key":"R10","unstructured":"S. Dolev, R. Segala, and A. A. Shvartsman,\n                      Dynamic load balancing with group communication\n                      , in Proceedings of the 6th International Colloquium on Structural Information and Communication Complexity (SIROCCO 1999), Carleton Scientific, Waterloo, ON, Canada, 1999, pp. 111\u2013125."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255527"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Stavros Georgiades, Marios Mavronicolas, Paul Spirakis, Optimal, distributed decision\u2010making: the case of no communication, Lecture Notes in Comput. Sci., Vol. 1684, Springer, Berlin, 1999, 293\u2013303MR1850240","DOI":"10.1007\/3-540-48321-7_24"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Ch. Georgiou, A. Russell, and A. A. Shvartsman,\n                      Optimally work\u2010competitive scheduling for cooperative computing with merging groups (brief announc.)\n                      , in Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC 2002), ACM, New York, 2002, p. 132.","DOI":"10.1145\/571825.571848"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Chryssis Georgiou, Alexander Russell, Alex Shvartsman, Work\u2010competitive scheduling for cooperative computing with dynamic groups, ACM, New York, 2003, 251\u2013258MR2121040","DOI":"10.1145\/780542.780581"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00026-1"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008930"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-5210-6"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Z. M. Kedem, K. V. Palem, and P. Spirakis,\n                      Efficient robust parallel computations\n                      , in Proceedings of the 22nd ACM Symposium on Theory of Computing (STOC 1990), ACM, New York, 1990, pp. 138\u2013148.","DOI":"10.1145\/100216.100231"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"G. Malewicz, A. Russell, and A. A. Shvartsman,\n                      Distributed cooperation during the absence of communication\n                      , in Proceedings of the 14th International Symposium on Distributed Computing (DISC 2000), Lecture Notes in Comput. Sci. 1914, Springer\u2010Verlag, Berlin, 2000, pp. 119\u2013133.","DOI":"10.1007\/3-540-40026-5_8"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1017"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and M. Yannakakis,\n                      On the value of information in distributed decision\u2010making\n                      , in Proceedings of the 10th ACM Symposium on Principles of Distributed Computing (PODC 1991), ACM, New York, 1991, pp. 61\u201364.","DOI":"10.1145\/112600.112606"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"D. Powell, ed.\n                      Special Issue on Group Communication Services\n                      , Comm. ACM, 39 (1996).","DOI":"10.1145\/227210.227225"},{"key":"R24","unstructured":"Michael Saks, Nir Shavit, Heather Woll, Optimal time randomized consensus\u2014making resilient algorithms fast in practice, ACM, New York, 1991, 351\u2013362MR1095852"},{"key":"R25","unstructured":"N. Shavit,\n                      Concurrent Timestamping\n                      , Ph.D. thesis, The Hebrew University, 1989."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00398-X"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539704440442","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:16:14Z","timestamp":1787336174000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539704440442"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539704440442"],"URL":"https:\/\/doi.org\/10.1137\/s0097539704440442","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}