{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:21Z","timestamp":1750306881700,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,8,27]],"date-time":"2012-08-27T00:00:00Z","timestamp":1346025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2012,8,27]]},"abstract":"<jats:p>What can and cannot be computed in a distributed system is a complex function of the system's communication model, timing model, and failure model. This tutorial surveys some important results about computability in the canonical distributed system model, where processes execute asynchronously, they communicate by reading and writing shared memory, and they fail by crashing. It explains the fundamental role that topology plays in the distributed computability theory.<\/jats:p>","DOI":"10.1145\/2421096.2421118","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"88-110","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Computability in distributed computing"],"prefix":"10.1145","volume":"43","author":[{"given":"Maurice","family":"Herlihy","sequence":"first","affiliation":[{"name":"Brown University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[{"name":"Instituto de Matem\u00e1ticas UNAM, Mexico City, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Raynal","sequence":"additional","affiliation":[{"name":"IRISA, Univ. Rennes 1, Rennes, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,8,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153741"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795279463"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797330689"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0090-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280833"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79158"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378591"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations and Advanced Topics (2d Edition)","author":"Attiya H.","year":"2004","unstructured":"Attiya H. and Welch J. , Distributed Computing: Fundamentals, Simulations and Advanced Topics (2d Edition) , Wiley-Interscience , 414 pages, 2004 . Attiya H. and Welch J., Distributed Computing: Fundamentals, Simulations and Advanced Topics (2d Edition), Wiley-Interscience, 414 pages, 2004."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/62546.62590"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167119"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/164051.164056"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259439"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008933"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0084-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2011.04.001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1043"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5931"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2075029.2075074"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305766"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1926829.1926861"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1940234.1940258"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_23"},{"key":"e_1_2_1_24_1","first-page":"47","volume-title":"9th Int'l Conference on Parallel Computing Technologies (PaCT'07)","author":"Guerraoui R.","year":"2007","unstructured":"Guerraoui R. and Raynal M. , From Unreliable Objects to Reliable Objects: the Case of atomic Registers and Consensus . 9th Int'l Conference on Parallel Computing Technologies (PaCT'07) , Springer , LNCS 4671, pp. 47 -- 61 , 2007 . Guerraoui R. and Raynal M., From Unreliable Objects to Reliable Objects: the Case of atomic Registers and Consensus. 9th Int'l Conference on Parallel Computing Technologies (PaCT'07), Springer, LNCS 4671, pp. 47--61, 2007."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258652"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00396-6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835724"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888781.1888795"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332483"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/277697.277722"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331529"},{"key":"e_1_2_1_33_1","volume-title":"The Art of Multiprocessor Programming","author":"Herlihy M.P.","year":"2008","unstructured":"Herlihy M.P. and Shavit N. , The Art of Multiprocessor Programming , Morgan Kaufman Pub. , San Francisco (CA), 508 pages, 2008 . Herlihy M.P. and Shavit N., The Art of Multiprocessor Programming, Morgan Kaufman Pub., San Francisco (CA), 508 pages, 2008."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_35_1","first-page":"66","volume":"6796","author":"Imbs D.","year":"2011","unstructured":"Imbs D. , Rajsbaum S. , Raynal M. , The Universe of Symmetry Breaking Tasks. Proc. 18th Int'l Colloquium on Structural Information and Communication Complexity (SIROCCO'11) , Springer LNCS 6796 , pp. 66 -- 77 , 2011 . Imbs D., Rajsbaum S., Raynal M., The Universe of Symmetry Breaking Tasks. Proc. 18th Int'l Colloquium on Structural Information and Communication Complexity (SIROCCO'11), Springer LNCS 6796, pp. 66--77, 2011.","journal-title":"Springer LNCS"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.08.005"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1741"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786227"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.033"},{"key":"e_1_2_1_41_1","series-title":"Advances in Computing Research","volume-title":"Memory Requirements for Agreement Among Unreliable Asynchronous Processes. Parallel and Distributed Computing","author":"Loui M.C.","year":"1987","unstructured":"Loui M.C. , and Abu-Amara H.H. , Memory Requirements for Agreement Among Unreliable Asynchronous Processes. Parallel and Distributed Computing : vol. 4 of Advances in Computing Research , JAI Press , 4: 163--183, 1987 . Loui M.C., and Abu-Amara H.H., Memory Requirements for Agreement Among Unreliable Asynchronous Processes. Parallel and Distributed Computing: vol. 4 of Advances in Computing Research, JAI Press, 4:163--183, 1987."},{"key":"e_1_2_1_42_1","volume-title":"San Francisco (CA), 872 pages","author":"Lynch N.A.","year":"1996","unstructured":"Lynch N.A. , Distributed Algorithms. Morgan Kaufmann Pub ., San Francisco (CA), 872 pages , 1996 . Lynch N.A., Distributed Algorithms. Morgan Kaufmann Pub., San Francisco (CA), 872 pages, 1996."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364006"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198176"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69733-6_48"},{"key":"e_1_2_1_46_1","volume-title":"Concurrent Programming: Algorithms, Principles, and Foundations","author":"Raynal M.","year":"2012","unstructured":"Raynal M. , Concurrent Programming: Algorithms, Principles, and Foundations . Springer , 450 pages, 2012 (ISBN: 978-3-642-32026-2). Raynal M., Concurrent Programming: Algorithms, Principles, and Foundations. Springer, 450 pages, 2012 (ISBN: 978-3-642-32026-2)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796307698"},{"key":"e_1_2_1_48_1","volume-title":"Synchronization Algorithms and Concurrent Programming","author":"Taubenfeld G.","year":"2006","unstructured":"Taubenfeld G. , Synchronization Algorithms and Concurrent Programming . Pearson Prentice-Hall , 423 pages, 2006 (ISBN 0-131-97259-6). Taubenfeld G., Synchronization Algorithms and Concurrent Programming. Pearson Prentice-Hall, 423 pages, 2006 (ISBN 0-131-97259-6)."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2421096.2421118","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2421096.2421118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:34Z","timestamp":1750234714000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2421096.2421118"}},"subtitle":["a Tutorial"],"short-title":[],"issued":{"date-parts":[[2012,8,27]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,8,27]]}},"alternative-id":["10.1145\/2421096.2421118"],"URL":"https:\/\/doi.org\/10.1145\/2421096.2421118","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2012,8,27]]},"assertion":[{"value":"2012-08-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}