{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:37:08Z","timestamp":1750307828736,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["9.98E+27"],"award-info":[{"award-number":["9.98E+27"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004415","name":"North Atlantic Treaty Organization","doi-asserted-by":"publisher","award":["209588"],"award-info":[{"award-number":["209588"]}],"id":[{"id":"10.13039\/100004415","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            The problem of performing\n            <jats:italic>n<\/jats:italic>\n            tasks on\n            <jats:italic>p<\/jats:italic>\n            asynchronous or undependable processors is a basic problem in distributed computing. This article considers an abstraction of this problem called\n            <jats:italic>Write-All: using p processors write 1's into all locations of an array of size n<\/jats:italic>\n            . In this problem writing 1 abstracts the notion of performing a simple task. Despite substantial research, there is a dearth of efficient deterministic asynchronous algorithms for\n            <jats:italic>Write-All\/<\/jats:italic>\n            . Efficiency of algorithms is measured in terms of\n            <jats:italic>work<\/jats:italic>\n            that accounts for all local steps performed by the processors in solving the problem. Thus, an optimal algorithm would have work \u0398(\n            <jats:italic>n<\/jats:italic>\n            ), however it is known that optimality cannot be achieved when\n            <jats:italic>p<\/jats:italic>\n            = \u03a9(\n            <jats:italic>n<\/jats:italic>\n            ). The quest then is to obtain work-optimal solutions for this problem using a nontrivial, compared to\n            <jats:italic>n<\/jats:italic>\n            , number of processors\n            <jats:italic>p<\/jats:italic>\n            . The algorithm presented in this article has work complexity of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>p<\/jats:italic>\n            <jats:sup>2 + \u03f5<\/jats:sup>\n            ), and it achieves work optimality for\n            <jats:italic>p<\/jats:italic>\n            =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\/(2 + \u03b5)<\/jats:sup>\n            ) for any \u03b5 &gt; 0, while the previous best result achieved optimality for\n            <jats:italic>p<\/jats:italic>\n            \u22644\u221a\n            <jats:italic>n<\/jats:italic>\n            \/log\n            <jats:italic>n<\/jats:italic>\n            . Additionally, the new result uses\n            <jats:italic>only<\/jats:italic>\n            the atomic read\/write memory, without resorting to using the test-and-set primitive that was necessary in the previous solution.\n          <\/jats:p>","DOI":"10.1145\/1367064.1367073","type":"journal-article","created":{"date-parts":[[2008,7,2]],"date-time":"2008-07-02T12:09:19Z","timestamp":1215000559000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Writing-all deterministically and optimally using a nontrivial number of asynchronous processors"],"prefix":"10.1145","volume":"4","author":[{"given":"Dariusz R.","family":"Kowalski","sequence":"first","affiliation":[{"name":"University of Liverpool, Liverpool, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander A.","family":"Shvartsman","sequence":"additional","affiliation":[{"name":"University of Connecticut, Storrs, CT"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,7,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365676"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794319126"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366860"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90162-7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0003"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378685"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060698"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/97444.97673"},{"volume-title":"Proceedings of the International Conference on Distributed Computer Systems. 467--474","author":"Dasgupta P.","key":"e_1_2_1_9_1","unstructured":"Dasgupta , P. , Kedem , Z. M. , and Rabin , M. O . 1995. Parallel processing on networks of workstations: A fault-tolerant, high performance approach . In Proceedings of the International Conference on Distributed Computer Systems. 467--474 . Dasgupta, P., Kedem, Z. M., and Rabin, M. O. 1995. Parallel processing on networks of workstations: A fault-tolerant, high performance approach. In Proceedings of the International Conference on Distributed Computer Systems. 467--474."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198082"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255527"},{"volume-title":"Proceedings of the IEEE Symposium Symposium on the Foundations of Computer Science. IEEE Computer Society","author":"Galil Z.","key":"e_1_2_1_12_1","unstructured":"Galil , Z. , Mayer , A. J. , and Yung , M . 1995. Resolving message complexity of byzantine agreement and beyond . In Proceedings of the IEEE Symposium Symposium on the Foundations of Computer Science. IEEE Computer Society , Press, Los Alamitos, CA, 724--733. Galil, Z., Mayer, A. J., and Yung, M. 1995. Resolving message complexity of byzantine agreement and beyond. In Proceedings of the IEEE Symposium Symposium on the Foundations of Computer Science. IEEE Computer Society, Press, Los Alamitos, CA, 724--733."},{"key":"e_1_2_1_13_1","volume-title":"Distributed Systems: Cooperation in the Presence of Adversity","author":"Georgiou C.","year":"2007","unstructured":"Georgiou , C. , and Shvartsman , A. A . 2007 . Do-All Computing in Distributed Systems: Cooperation in the Presence of Adversity . Springer-Verlag , New York . Georgiou, C., and Shvartsman, A. A. 2007. Do-All Computing in Distributed Systems: Cooperation in the Presence of Adversity. Springer-Verlag, New York."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/72935.72953"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008930"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Kanellakis P. C. and Shvartsman A. A. 1997. Fault-Tolerant Parallel Computation. Kluwer Academic Publishers Norwell MA.   Kanellakis P. C. and Shvartsman A. A. 1997. Fault-Tolerant Parallel Computation. Kluwer Academic Publishers Norwell MA.","DOI":"10.1007\/978-1-4757-5210-6"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129742"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103459"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100231"},{"volume-title":"The Art of Computer Programming","author":"Knuth D. E.","key":"e_1_2_1_20_1","unstructured":"Knuth , D. E. 1998. The Art of Computer Programming , Volume III ( third edition): Sorting and Searching. Addison-Wesley , Reading, MA. Knuth, D. E. 1998. The Art of Computer Programming, Volume III (third edition): Sorting and Searching. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2005.34"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872075"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221063"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1017"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89580"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060105"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791219670"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90156-C"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367073","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1367064.1367073","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:54Z","timestamp":1750255074000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1367064.1367073"],"URL":"https:\/\/doi.org\/10.1145\/1367064.1367073","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,6]]},"assertion":[{"value":"2006-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}