{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:32Z","timestamp":1740109292673,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T00:00:00Z","timestamp":1635292800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T00:00:00Z","timestamp":1635292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2014-05296"],"award-info":[{"award-number":["RGPIN-2014-05296"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s00446-021-00405-7","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T13:03:44Z","timestamp":1635339824000},"page":"81-103","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On atomic registers and randomized consensus in M&M systems"],"prefix":"10.1007","volume":"35","author":[{"given":"Vassos","family":"Hadzilacos","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5242-4460","authenticated-orcid":false,"given":"Xing","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Sam","family":"Toueg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"405_CR1","unstructured":"Gen-Z draft specifications. https:\/\/genzconsortium.org\/bulk-download-of-completed-and-draft-gen-z-specifications-now-available\/"},{"key":"405_CR2","unstructured":"Gen-Z DRAM and persistent memory theory of operation. https:\/\/genzconsortium.org\/wp-content\/uploads\/2019\/03\/Gen-Z-DRAM-PM-Theory-of-Operation-WP.pdf"},{"key":"405_CR3","unstructured":"InfiniBand. https:\/\/en.wikipedia.org\/wiki\/InfiniBand"},{"key":"405_CR4","unstructured":"iWARP. https:\/\/en.wikipedia.org\/wiki\/IWARP"},{"key":"405_CR5","doi-asserted-by":"crossref","unstructured":"Lim, K., Chang, J., Mudge, T., Ranganathan, P., Reinhardt, S.K., Wenisch, T.F.: Disaggregated memory for expansion and sharing in blade servers. In: International Symposium on Computer Architecture, pp. 267\u2013278 (2009)","DOI":"10.1145\/1555815.1555789"},{"key":"405_CR6","unstructured":"RDMA over converged ethernet. https:\/\/en.wikipedia.org\/wiki\/RDMA_over_Converged_Ethernet"},{"key":"405_CR7","doi-asserted-by":"crossref","unstructured":"Aguilera, M.K., Ben-David, N., Calciu, I., Guerraoui, R., Petrank, E., Toueg, S.: Passing messages while sharing memory. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, pp. 51\u201360 (2018)","DOI":"10.1145\/3212734.3212741"},{"key":"405_CR8","unstructured":"Dragojevi\u0107, A., Narayanan, D., Castro, M., Hodson, O.: FaRM: Fast remote memory. In: Symposium on Networked Systems Design and Implementation, pp. 401\u2013414 (2014)"},{"key":"405_CR9","doi-asserted-by":"crossref","unstructured":"Kalia, A., Kaminsky, M., Andersen, D.G.: Using RDMA efficiently for key-value services. In: ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 295\u2013306 (2014)","DOI":"10.1145\/2740070.2626299"},{"key":"405_CR10","unstructured":"Kalia, A., Kaminsky, M., Andersen, D.G.: FaSST: Fast, scalable and simple distributed transactions with two-sided (RDMA) datagram RPCs. In: Symposium on Operating Systems Design and Implementation, pp. 185\u2013201 (2016)"},{"key":"405_CR11","doi-asserted-by":"crossref","unstructured":"Tsai, S.Y., Zhang, Y.: LITE kernel RDMA support for datacenter applications. In: ACM Symposium on Operating Systems Principles, pp. 306\u2013324 (2017)","DOI":"10.1145\/3132747.3132762"},{"issue":"1","key":"405_CR12","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/200836.200869","volume":"42","author":"H Attiya","year":"1995","unstructured":"Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. J. ACM 42(1), 124\u2013142 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"405_CR13","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0196-6774(90)90021-6","volume":"11","author":"J Aspnes","year":"1990","unstructured":"Aspnes, J., Herlihy, M.: Fast randomized consensus using shared memory. J. Algorithms 11(3), 441\u2013461 (1990)","journal-title":"J. Algorithms"},{"key":"405_CR14","unstructured":"Attiya, H., Enea, C.: Putting Strong Linearizability in Context: Preserving Hyperproperties in Programs That Use Concurrent Objects. In: 33rd International Symposium on Distributed Computing, DISC 2019, pp. 2:1\u20132:17 (2019)"},{"key":"405_CR15","doi-asserted-by":"crossref","unstructured":"Golab, W., Higham, L., Woelfel, P.: Linearizable implementations do not suffice for randomized distributed computation. In: Proceedings of the 2011 ACM Symposium on Theory of Computing, STOC 2011, pp. 373\u2013382 (2011)","DOI":"10.1145\/1993636.1993687"},{"key":"405_CR16","doi-asserted-by":"crossref","unstructured":"Hadzilacos, V., Hu, X., Toueg, S.: On register linearizability and termination. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC 2021, pp. 521\u2013531 (2021)","DOI":"10.1145\/3465084.3467925"},{"key":"405_CR17","doi-asserted-by":"crossref","unstructured":"Hadzilacos, V., Hu, X., Toueg, S.: Randomized consensus with regular registers. (June 11, 2020). arxiv:2006.06771. To appear in Information Processing Letters (March 2022)","DOI":"10.1016\/j.ipl.2021.106173"},{"issue":"2","key":"405_CR18","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF01786227","volume":"1","author":"L Lamport","year":"1986","unstructured":"Lamport, L.: On interprocess communication parts I-II. Distrib. Comput. 1(2), 77\u2013101 (1986)","journal-title":"Distrib. Comput."},{"key":"405_CR19","doi-asserted-by":"crossref","unstructured":"Poke, M., Hoefler, T.: Dare: High-performance state machine replication on RDMA networks. In: Proceedings of the 24th International Symposium on High-Performance Parallel and Distributed Computing, HPDC 2015, pp. 107\u2013118 (2015)","DOI":"10.1145\/2749246.2749267"},{"key":"405_CR20","unstructured":"Yang, J., Izraelevitz, J., Swanson, S.: Orion: A distributed file system for non-volatile main memory and RDMA-capable networks. In: 17th USENIX Conference on File and Storage Technologies, FAST 2019, pp. 221\u2013234 (2019)"},{"key":"405_CR21","doi-asserted-by":"crossref","unstructured":"Aguilera, M.K., Ben-David, N., Guerraoui, R., Marathe, V., Zablotchi, I.: The impact of RDMA on agreement. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, pp. 409\u2013418 (2019)","DOI":"10.1145\/3293611.3331601"},{"issue":"3","key":"405_CR22","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M Herlihy","year":"1990","unstructured":"Herlihy, M., Wing, J.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463\u2013492 (1990)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"5","key":"405_CR23","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1147\/rd.45.0497","volume":"4","author":"AJ Hoffman","year":"1960","unstructured":"Hoffman, A.J., Singleton, R.R.: On Moore graphs with diameters 2 and 3. IBM J. Res. Dev. 4(5), 497\u2013504 (1960)","journal-title":"IBM J. Res. Dev."},{"key":"405_CR24","unstructured":"Figure by Uzyel - Own work, CC BY-SA 3.0. https:\/\/commons.wikimedia.org\/w\/index.php?curid=10378641"},{"issue":"4","key":"405_CR25","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Amer. Math. Soc. 43(4), 439\u2013561 (2006)","journal-title":"Bull. Amer. Math. Soc."},{"issue":"2","key":"405_CR26","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985)","journal-title":"J. ACM"},{"issue":"163\u2013183","key":"405_CR27","first-page":"31","volume":"4","author":"MC Loui","year":"1987","unstructured":"Loui, M.C., Abu-Amara, H.H.: Memory requirements for agreement among unreliable asynchronous processes. Adv. Comput. Res. 4(163\u2013183), 31 (1987)","journal-title":"Adv. Comput. Res."},{"key":"405_CR28","unstructured":"Hadzilacos, V., Hu, X., Toueg, S.: Optimal register construction in m&m systems. In: 23rd International Conference on Principles of Distributed Systems, OPODIS 2019, pp. 28:1\u201328:16 (2019)"},{"key":"405_CR29","doi-asserted-by":"crossref","unstructured":"Hadzilacos, V., Hu, X., Toueg, S.: On atomic registers and randomized consensus in M&M systems (June 17, 2020). arxiv:1906.00298v2","DOI":"10.1007\/s00446-021-00405-7"},{"issue":"2","key":"405_CR30","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1109\/2.485843","volume":"29","author":"C Amza","year":"1996","unstructured":"Amza, C., Cox, A.L., Dwarkadas, S., Keleher, P., Lu, H., Rajamony, R., Yu, W., Zwaenepoel, W.: TreadMarks: Shared memory computing on networks of workstations. IEEE Comput. 29(2), 18\u201328 (1996)","journal-title":"IEEE Comput."},{"key":"405_CR31","doi-asserted-by":"crossref","unstructured":"Baumann, A., Barham, P., Dagand, P.E., Harris, T., Isaacs, R., Peter, S., Roscoe, T., Sch\u00fcpbach, A., Singhania, A.: The multikernel: A new OS architecture for scalable multicore systems. In: ACM Symposium on Operating Systems Principles, pp. 29\u201344 (2009)","DOI":"10.1145\/1629575.1629579"},{"key":"405_CR32","doi-asserted-by":"crossref","unstructured":"Bennett, J.K., Carter, J.B., Zwaenepoel, W.: Munin: Distributed shared memory based on type-specific memory coherence. In: ACM Symposium on Principles and Practice of Parallel Programming, pp. 168\u2013176 (1990)","DOI":"10.1145\/99164.99182"},{"key":"405_CR33","doi-asserted-by":"crossref","unstructured":"David, T., Guerraoui, R., Yabandeh, M.: Consensus inside. In: International Middleware Conference, pp. 145\u2013156 (2014)","DOI":"10.1145\/2663165.2663321"},{"key":"405_CR34","doi-asserted-by":"crossref","unstructured":"Kaxiras, S., Klaftenegger, D., Norgren, M., Ros, A., Sagonas, K.: Turning centralized coherence and distributed critical-section execution on their head: a new approach for scalable distributed shared memory. In: Proceedings of the 24th International Symposium on High-Performance Parallel and Distributed Computing, HPDC 2015, pp. 3\u201314 (2015)","DOI":"10.1145\/2749246.2749250"},{"key":"405_CR35","doi-asserted-by":"crossref","unstructured":"Kranz, D., Johnson, K., Agarwal, A., Kubiatowicz, J., Lim, B.H.: Integrating message-passing and shared-memory: Early experience. In: ACM Symposium on Principles and Practice of Parallel Programming, pp. 54\u201363 (1993)","DOI":"10.1145\/173284.155338"},{"key":"405_CR36","unstructured":"Nelson, J., Holt, B., Myers, B., Briggs, P., Ceze, L., Kahan, S., Oskin, M.: Latency-tolerant software distributed shared memory. In: USENIX Annual Technical Conference, pp. 291\u2013305 (2015)"},{"key":"405_CR37","doi-asserted-by":"crossref","unstructured":"Scales, D.J., Gharachorloo, K., Thekkath, C.A.: Shasta: A low overhead, software-only approach for supporting fine-grain shared memory. In: International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 174\u2013185 (1996)","DOI":"10.1145\/248208.237179"},{"key":"405_CR38","unstructured":"Attiya, H., Kumari, S., Schiller, N.: Optimal resilience in systems that mix shared memory and message passing. In: Q.\u00a0Bramas, R.\u00a0Oshman, P.\u00a0Romano (eds.) 24th International Conference on Principles of Distributed Systems, OPODIS 2020, pp. 16:1\u201316:16 (2020)"},{"key":"405_CR39","unstructured":"Attiya, H., Kumari, S., Schiller, N.: Optimal resilience in systems that mix shared memory and message passing. (December 20, 2020). arxiv:2012.10846"},{"key":"405_CR40","doi-asserted-by":"crossref","unstructured":"Afek, Y., Greenberg, D.S., Merritt, M., Taubenfeld, G.: Computing with faulty shared memory. In: Proceedings of the 1992 ACM Symposium on Principles of Distributed Computing, PODC 1992, pp. 47\u201358 (1992)","DOI":"10.1145\/135419.135431"},{"issue":"3","key":"405_CR41","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1145\/278298.278305","volume":"45","author":"P Jayanti","year":"1998","unstructured":"Jayanti, P., Chandra, T.D., Toueg, S.: Fault-tolerant wait-free shared objects. J. ACM 45(3), 451\u2013500 (1998)","journal-title":"J. ACM"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00405-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-021-00405-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00405-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,27]],"date-time":"2022-02-27T08:04:04Z","timestamp":1645949044000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-021-00405-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,27]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["405"],"URL":"https:\/\/doi.org\/10.1007\/s00446-021-00405-7","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2021,10,27]]},"assertion":[{"value":"17 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"No conflicts of interest to this work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}