{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T16:53:13Z","timestamp":1694623993320},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[1992,5,1]],"date-time":"1992-05-01T00:00:00Z","timestamp":704678400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[1992,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>\n            Most proof methods for reasoning about concurrent programs are based upon the\n            <jats:italic>interleaving semantics<\/jats:italic>\n            of concurrent computation: a concurrent program is executed in a stepwise fashion, with only one enabled action being executed at each step. Interleaving semantics, in effect, requires that a concurrent program be executed as a nondeterministic sequential program. This is clearly an abstraction of the way in which concurrent programs are actually executed. To ensure that this is a reasonable abstraction, interleaving semantics should only be used to reason about programs with \u201csimple\u201d actions; we call such programs \u201catomic\u201d. In this paper, we formally characterise the class of atomic programs. We adopt the criterion that a program is\n            <jats:italic>atomic<\/jats:italic>\n            if it can be implemented in a wait-free, serialisable manner by a primitive program. A program is\n            <jats:italic>primitive<\/jats:italic>\n            if each of its actions has at most one occurrence of a shared bit, and each shared bit is read by at most one process and written by at most one process. It follows from our results that the traditionally accepted atomicity criterion, which allows each action to have at most one occurrence of a shared variable, can be relaxed, allowing programs to have more powerful actions. For example, according to our criterion, an action can read any finite number of shared variables, provided it writes no shared variable.\n          <\/jats:p>","DOI":"10.1007\/bf01212305","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T13:00:49Z","timestamp":1109336449000},"page":"273-298","source":"Crossref","is-referenced-by-count":17,"title":["A criterion for atomicity"],"prefix":"10.1145","volume":"4","author":[{"given":"James H.","family":"Anderson","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Maryland at College Park, 20742-3255, Maryland, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohamed G.","family":"Gouda","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences, The University of Texas at Austin, Texas, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","doi-asserted-by":"crossref","unstructured":"Afek Y. Attiya H. Dolev D. Gafni E. Merritt M. and Shavit N.: Atomic Snapshots of Shared Memory. Proc. Ninth Annual Symp. on Principles of Distributed Computing pp. 1\u201314 1990.","DOI":"10.21236\/ADA222765"},{"key":"e_1_2_1_2_2_2","volume-title":"Technical Report TR.89.26","author":"Anderson J.","year":"1989"},{"key":"e_1_2_1_2_3_2","doi-asserted-by":"crossref","unstructured":"Anderson J.: Composite Registers Proc. Ninth Annual Symp. on Principles of Distributed Computing pp. 15\u201330 1990.","DOI":"10.1145\/93385.93396"},{"key":"e_1_2_1_2_4_2","volume-title":"Ph.D. Dissertation","author":"Anderson J.","year":"1990"},{"key":"e_1_2_1_2_5_2","volume-title":"Technical Report TR.90.23","author":"Anderson J.","year":"1990"},{"key":"e_1_2_1_2_6_2","doi-asserted-by":"crossref","unstructured":"Anderson J. and Gro\u0161elj B.: Pseudo Read-Modify-Write Operations: Bounded Wait-Free Implementations. Proceedings of the Fifth International Workshop on Distributed Algorithms Lecture Notes in Computer Science 579 Springer-Verlag 1992.","DOI":"10.1007\/BFb0022437"},{"key":"e_1_2_1_2_7_2","doi-asserted-by":"crossref","unstructured":"Aspens J. and Herlihy M.: Wait-Free Data Structures in the Asynchronous PRAM Model. Proc. Second Annual ACM Symp. on Parallel Architectures and Algorithms July 1990.","DOI":"10.1145\/97444.97701"},{"key":"e_1_2_1_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.9729"},{"key":"e_1_2_1_2_9_2","doi-asserted-by":"crossref","unstructured":"Burns J. and Peterson G.: Constructing Multi-Reader Atomic Values from Non-Atomic Values. Proceedings of the Sixth Annual Symposium on Principles of Distributed Computing pp. 222\u2013231 (1987).","DOI":"10.1145\/41840.41859"},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"crossref","unstructured":"Burns J. and Peterson G.: Pure Buffers for Concurrent Reading While Writing. Technical Report GIT-ICS-87\/17 School of Information and Computer Science Georgia Institute of Technology April 1987.","DOI":"10.1109\/SFCS.1987.15"},{"key":"e_1_2_1_2_11_2","doi-asserted-by":"crossref","unstructured":"Chor B. Israeli A. and Li M.: On Processor Coordination Using Asynchronous Hardware. Proc. Sixth Annual Symp. on Principles of Distributed Computing pp. 86\u201397 1987.","DOI":"10.1145\/41840.41848"},{"key":"e_1_2_1_2_12_2","volume-title":"A Discipline of Programming","author":"Dijkstra E.","year":"1976"},{"key":"e_1_2_1_2_13_2","doi-asserted-by":"crossref","unstructured":"Gouda M.: Serializable Programs Parallelizable Assertions: A Basis for Interleaving. In: Beauty is Our Business W.H.J. Feijen A.J.M. van Gasteren D. Gries and J. Misra (eds) pp. 135\u2013140 Springer-Verlag 1990.","DOI":"10.1007\/978-1-4612-4476-9_16"},{"key":"e_1_2_1_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_2_16_2","doi-asserted-by":"crossref","unstructured":"Kirousis L. Kranakis E. and Vitanyi P.: Atomic Multireader Register. Proc. Second Int. Workshop on Distributed Computing Lecture Notes in Computer Science 312 pp. 278\u2013296 Springer Verlag 1987.","DOI":"10.1007\/BFb0019809"},{"key":"e_1_2_1_2_17_2","volume-title":"Operating Systems Techniques","author":"Hoare C.A.R.","year":"1972"},{"key":"e_1_2_1_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/48022.48024"},{"key":"e_1_2_1_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786227"},{"key":"e_1_2_1_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78970"},{"key":"e_1_2_1_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2993.357247"},{"key":"e_1_2_1_2_22_2","doi-asserted-by":"crossref","unstructured":"Li M. Tromp J. and Vitanyi P.: How to Construct Wait-Free Variables. Proceedings of International Colloquium on Automata Languages and Programming Lecture Notes in Computer Science 372 pp. 488\u2013505 Springer-Verlag 1989.","DOI":"10.1007\/BFb0035779"},{"key":"e_1_2_1_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(84)90003-0"},{"key":"e_1_2_1_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/5001.5007"},{"key":"e_1_2_1_2_25_2","doi-asserted-by":"crossref","unstructured":"Newman-Wolfe R.: A Protocol for Wait-Free Atomic Multi-Reader Shared Variables. Proceedings of the Sixth Annual Symposium on Principles of Distributed Computing pp. 232\u2013248 (1987).","DOI":"10.1145\/41840.41860"},{"key":"e_1_2_1_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268134"},{"key":"e_1_2_1_2_27_2","doi-asserted-by":"crossref","unstructured":"Peterson G. and Burns J.: Concurrent Reading While Writing II: The Multi-Writer Case. Proceedings of the 28th Annual Symposium on Foundations of Computer Science 1987.","DOI":"10.1109\/SFCS.1987.15"},{"key":"e_1_2_1_2_28_2","doi-asserted-by":"crossref","unstructured":"Singh A. Anderson J. and Gouda M.: The Elusive Atomic Register Revisited. Proc. Sixth Annual Symp. on Principles of Distributed Computing pp. 206\u2013221 1987.","DOI":"10.1145\/41840.41858"},{"key":"e_1_2_1_2_29_2","doi-asserted-by":"crossref","unstructured":"Tromp J.: Proc. of the Third International Workshop on Distributed Algorithms Lecture Notes in Computer Science 392 pp 292\u2013302 Springer-Verlag 1989.","DOI":"10.1007\/3-540-51687-5_51"},{"key":"e_1_2_1_2_30_2","doi-asserted-by":"crossref","unstructured":"Vitanyi P. and Awerbuch B.: Atomic Shared Register Access by Asynchronous Hardware. Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science 1986 pp. 233\u2013243.","DOI":"10.1109\/SFCS.1986.11"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01212305.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01212305\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/BF01212305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T15:22:31Z","timestamp":1641482551000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/BF01212305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,5]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,5]]}},"alternative-id":["10.1007\/BF01212305"],"URL":"https:\/\/doi.org\/10.1007\/bf01212305","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,5]]}}}