{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:56:02Z","timestamp":1787385362124,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    We consider a system of t synchronous processes that communicate only by sending messages to one another, and together the processes must perform n independent units of work. Processes may fail by crashing; we want to guarantee that in every execution of the protocol in which at least one process survives, all n units of work will be performed. We consider three parameters: the number of messages sent, the total number of units of work performed (including multiplicities), and time. We present three protocols for solving the problem. All three are work optimal, doing O(n+t) work. The first has moderate costs in the remaining two parameters, sends $O(t\\sqrt{t})$ messages, and takes O(n+t) time. This protocol can be easily modified to run in any completely asynchronous system equipped with a failure detection mechanism. The second sends only O(t log t) messages, but its running time is large (O(t\n                    <jats:sup>2<\/jats:sup>\n                    (n+t) 2\n                    <jats:sup>n+t<\/jats:sup>\n                    )). The third is essentially time optimal in the (usual) case in which there are no failures, and its time complexity degrades gracefully as the number of failures increases.\n                  <\/jats:p>","DOI":"10.1137\/s0097539793255527","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1457-1491","source":"Crossref","is-referenced-by-count":52,"title":["Performing Work Efficiently in the Presence of Faults"],"prefix":"10.1137","volume":"27","author":[{"given":"Cynthia","family":"Dwork","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph Y.","family":"Halpern","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Orli","family":"Waarts","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794319126"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200869"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187073"},{"key":"R4","unstructured":"G. Bracha, Department of Computer Science, Cornell University, Ithaca, New York, July 1984, manuscript."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"M. F. Bridgland and R. J. Watro,\n                      Fault\u2010tolerant decision making in totally asynchronous distributed systems\n                      , in PODC 6th, 1987, pp. 52\u201363.","DOI":"10.1145\/41840.41845"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0003"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226647"},{"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 PODC 13th, 1994, pp. 161\u2013172.","DOI":"10.1145\/197917.198082"},{"key":"R9","unstructured":"C. Dwork, J. Y. Halpern, and H. R. Strong,\n                      Fault Tolerant Load Management System and Method\n                      , U.S. Patent 5,513,354, 1996."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96565"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Z. Galil, A. Mayer, and M. Yung,\n                      Resolving message complexity of Byzantine agreement and beyond\n                      , in FOCS 36th, 1995, pp. 724\u2013733.","DOI":"10.1109\/SFCS.1995.492674"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"D. Gelernter and D. Kaminsky,\n                      Supercomputing out of recycled garbage: Preliminary experience with Piranha\n                      , in Proc. ACM International Conference on Supercomputing, 1992, pp. 417\u2013427.","DOI":"10.1145\/143369.143444"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02277667"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Z. Kedem, K. Palem, A. Raghunathan, and P. G. Spirakis,\n                      Combining tentative and definite executions for very fast dependable parallel computing\n                      , in STOC 23rd, 1991, pp. 381\u2013389.","DOI":"10.1145\/103418.103459"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Z. M. Kedem, K. V. Palem, and P. G. Spirakis,\n                      Efficient robust parallel computations\n                      , in STOC 22nd, 1990, pp. 138\u2013148.","DOI":"10.1145\/100216.100231"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0221063"},{"key":"R17","first-page":"95","volume":"25","author":"Shoch J. F.","year":"1982","journal-title":"Comm. Assoc. Comput. Mach."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793255527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:23Z","timestamp":1787336063000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793255527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":17,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793255527"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793255527","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}