{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T11:51:08Z","timestamp":1649073068250},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,4,25]],"date-time":"2018-04-25T00:00:00Z","timestamp":1524614400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[2019,1]]},"DOI":"10.1007\/s00607-018-0618-5","type":"journal-article","created":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T22:44:02Z","timestamp":1524609842000},"page":"39-57","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Waiting in concurrent algorithms"],"prefix":"10.1007","volume":"101","author":[{"given":"Gadi","family":"Taubenfeld","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,25]]},"reference":[{"issue":"1","key":"618_CR1","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1109\/71.80120","volume":"1","author":"TE Anderson","year":"1990","unstructured":"Anderson TE (1990) The performance of spin lock alternatives for shared-memory multiprocessor. IEEE Trans Parallel Distrib Syst 1(1):6\u201316","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"3","key":"618_CR2","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1145\/79147.79158","volume":"37","author":"H Attiya","year":"1990","unstructured":"Attiya H, Bar-Noy A, Dolev D, Koller D, Peleg D, Reischuk R (1990) Renaming in an asynchronous environment. J Assoc Comput Mach 37(3):524\u2013548","journal-title":"J Assoc Comput Mach"},{"key":"618_CR3","unstructured":"Bar-Noy A, Dolev D (1989) Shared memory versus message-passing in an asynchronous distributed environment. In: Proceedings of the 8th ACM symposium on principles of distributed computing, pp 307\u2013318"},{"key":"618_CR4","doi-asserted-by":"crossref","unstructured":"Borowsky E, Gafni E (1993) Generalized FLP impossibility result for \n                    \n                      \n                    \n                    $$t$$\n                    \n                      \n                        t\n                      \n                    \n                  -resilient asynchronous computations. In: Proceedings of the 25th ACM symposium on theory of computing, pp 91\u2013100","DOI":"10.1145\/167088.167119"},{"key":"618_CR5","unstructured":"Burns JE, Peterson GL (1989) The ambiguity of choosing. In: Proceedings of the 8th ACM symposium on principles of distributed computing, pp 145\u2013158"},{"issue":"3","key":"618_CR6","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/j.cosrev.2011.04.001","volume":"5","author":"A Castaneda","year":"2011","unstructured":"Castaneda A, Rajsbaum S, Raynal M (2011) The renaming problem in shared memory systems: an introduction. Comput Sci Rev 5(3):229\u2013251","journal-title":"Comput Sci Rev"},{"issue":"9","key":"618_CR7","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1145\/365559.365617","volume":"8","author":"EW Dijkstra","year":"1965","unstructured":"Dijkstra EW (1965) Solution of a problem in concurrent programming control. Commun ACM 8(9):569","journal-title":"Commun ACM"},{"issue":"6","key":"618_CR8","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1145\/268999.269000","volume":"44","author":"C Dwork","year":"1997","unstructured":"Dwork C, Herlihy MP, Waarts O (1997) Contention in shared memory algorithms. J ACM 44(6):779\u2013805","journal-title":"J ACM"},{"issue":"2","key":"618_CR9","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer MJ, Lynch NA, Paterson MS (1985) Impossibility of distributed consensus with one faulty process. J ACM 32(2):374\u2013382","journal-title":"J ACM"},{"key":"618_CR10","unstructured":"Herlihy M (1991) Impossibility results for asynchronous pram. In: Proceedings of the 3rd annual ACM symposium on parallel algorithms and architectures, pp 327\u2013336"},{"key":"618_CR11","doi-asserted-by":"crossref","unstructured":"Herlihy M, Shavit N On the nature of progress. In: 15th International conference on principles of distributed systems (OPODIS 2011), LNCS 7109. Springer, pp 313\u2013328","DOI":"10.1007\/978-3-642-25873-2_22"},{"issue":"1","key":"618_CR12","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"MP Herlihy","year":"1991","unstructured":"Herlihy MP (1991) Wait-free synchronization. ACM Trans Progr Lang Syst 13(1):124\u2013149","journal-title":"ACM Trans Progr Lang Syst"},{"key":"618_CR13","doi-asserted-by":"crossref","unstructured":"Herlihy MP, Luchangco V, Moir M (2003) Obstruction-free synchronization: double-ended queues as an example. In: Proceedings of the 23rd international conference on distributed computing systems, p 522","DOI":"10.1109\/ICDCS.2003.1203503"},{"issue":"6","key":"618_CR14","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1145\/331524.331529","volume":"46","author":"MP Herlihy","year":"1999","unstructured":"Herlihy MP, Shavit N (1999) The topological structure of asynchronous computability. J ACM 46(6):858\u2013923","journal-title":"J ACM"},{"issue":"3","key":"618_CR15","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"MP Herlihy","year":"1990","unstructured":"Herlihy MP, Wing JM (1990) Linearizability: a correctness condition for concurrent objects. ACM Trans Progr Lang Syst 12(3):463\u2013492","journal-title":"ACM Trans Progr Lang Syst"},{"key":"618_CR16","doi-asserted-by":"crossref","unstructured":"Imbs D, Raynal M, Taubenfeld G (2010) On asymmetric progress conditions. In: Proceedings of the 29th ACM symposium on principles of distributed computing, pp 55\u201364","DOI":"10.1145\/1835698.1835709"},{"issue":"8","key":"618_CR17","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1145\/361082.361093","volume":"17","author":"L Lamport","year":"1974","unstructured":"Lamport L (1974) A new solution of Dijkstra\u2019s concurrent programming problem. Commun ACM 17(8):453\u2013455","journal-title":"Commun ACM"},{"key":"618_CR18","first-page":"163","volume":"4","author":"MC Loui","year":"1987","unstructured":"Loui MC, Abu-Amara H (1987) Memory requirements for agreement among unreliable asynchronous processes. Adv Comput Res 4:163\u2013183","journal-title":"Adv Comput Res"},{"issue":"3","key":"618_CR19","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0020-0190(87)90052-4","volume":"26","author":"S Moran","year":"1987","unstructured":"Moran S, Wolfstahl Y (1987) Extended impossibility results for asynchronous complete networks. Inf Process Lett 26(3):145\u2013151","journal-title":"Inf Process Lett"},{"key":"618_CR20","doi-asserted-by":"publisher","first-page":"1449","DOI":"10.1137\/S0097539796307698","volume":"29","author":"M Saks","year":"2000","unstructured":"Saks M, Zaharoglou F (2000) Wait-free \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -set agreement is impossible: the topology of public knowledge. SIAM J Comput 29:1449\u20131483","journal-title":"SIAM J Comput"},{"key":"618_CR21","doi-asserted-by":"crossref","unstructured":"Styer E, Peterson GL (1989) Tight bounds for shared memory symmetric mutual exclusion problems. In: Proceedings of the 8th ACM symposium on principles of distributed computing, pp 177\u2013191","DOI":"10.1145\/72981.72993"},{"key":"618_CR22","unstructured":"Taubenfeld G (2006) Synchronization algorithms and concurrent programming. Pearson\/Prentice-Hall, p 423. ISBN 0-131-97259-6"},{"key":"618_CR23","doi-asserted-by":"crossref","unstructured":"Taubenfeld G (Sept. 2010) The computational structure of progress conditions. In: 24th International symposium on distributed computing (DISC 2010). LNCS 6343 Springer 2010, pp. 221\u2013235","DOI":"10.1007\/978-3-642-15763-9_23"},{"key":"618_CR24","doi-asserted-by":"crossref","unstructured":"Taubenfeld G (2016) Fair synchronization. J Parallel Distrib Comput 97:1\u201310 (Also in: LNCS 8205, 2013, 179\u2013193, DISC 2013)","DOI":"10.1016\/j.jpdc.2016.06.007"},{"key":"618_CR25","unstructured":"Taubenfeld G (2016) Waiting in concurrent algorithms. In: 4th International conference on networked systems (NETYS, 2016) Marrakech, Morocco. LNCS 9944, 2016, 345\u2013360"},{"key":"618_CR26","doi-asserted-by":"crossref","unstructured":"Taubenfeld G (2017) A closer look at fault tolerance. Theory Comput Syst (To appear) (Also In: Proceedings of PODC 2012, 261\u2013270)","DOI":"10.1145\/2332432.2332484"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00607-018-0618-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-018-0618-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-018-0618-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T19:14:23Z","timestamp":1556133263000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00607-018-0618-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,25]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["618"],"URL":"https:\/\/doi.org\/10.1007\/s00607-018-0618-5","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,25]]},"assertion":[{"value":"11 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}