The renaming problem in shared memory systems: An introduction

Chandra, 1996, Unreliable failure detectors for reliable distributed systems, Journal of the ACM, 43, 225, 10.1145/226643.226647 Raynal, 2010, Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems, Morgan & Claypool Publishers Attiya, 2004 Lynch, 1996 Raynal, 2010 Fischer, 1985, Impossibility of distributed consensus with one faulty process, Journal of the ACM, 32, 374, 10.1145/3149.214121 Loui, 1987, Memory requirements for agreement among unreliable asynchronous processes, vol. 4 Biran, 1990, A combinatorial characterization of the distributed 1-solvable tasks, Journal of Algorithms, 11, 420, 10.1016/0196-6774(90)90020-F Attiya, 1990, Renaming in an asynchronous environment, Journal of the ACM, 37, 524, 10.1145/79147.79158 Gafni, 2006, Subconsensus tasks: renaming is weaker than set agreement, vol. 4167, 329 Afek, 2006, Group renaming, vol. 5401, 58 Afek, 1999, Fast, wait-free (2k−1)-renaming, 105 Attiya, 2000, Polynomial and adaptive long-lived (2p−1)-renaming, vol. 1914, 149 Attiya, 2001, Adaptive and efficient algorithms for lattice agreement and renaming, SIAM Journal of Computing, 31, 642, 10.1137/S0097539700366000 Borowsky, 1993, Immediate atomic snapshots and fast renaming, 41 Gafni, 2010, Recursion in distributed computing, vol. 6366, 362 Imbs, 2010, On adaptive renaming under eventually limited contention, vol. 6366, 377 Moir, 1998, Fast, long-lived renaming improved and simplified, Science of Computer Programming, 30, 287, 10.1016/S0167-6423(97)00016-6 Moir, 1995, Wait-free algorithms for fast, long-lived renaming, Science of Computer Programming, 25, 1, 10.1016/0167-6423(95)00009-H Attiya, 2002, The combinatorial structure of wait-free solvable tasks, SIAM Journal on Computing, 31, 1286, 10.1137/S0097539797330689 Castañeda, 2008, New combinatorial topology upper and lower bounds for renaming, 295 Castañeda, 2010, New combinatorial topology upper and lower bounds for renaming: the lower bound, Distributed Computing, 22, 287, 10.1007/s00446-010-0108-2 Herlihy, 2000, Algebraic spans, Mathematical Structures in Computer Science, 10, 549, 10.1017/S0960129500003170 Herlihy, 1999, The topological structure of asynchronous computability, Journal of the ACM, 46, 858, 10.1145/331524.331529 Gafni, 2006, Renaming with k-set consensus: an optimal algorithm in n+k−1 slots, vol.4305, 36 Gafni, 2009, From adaptive renaming to set agreement, Theoretical Computer Science, 410, 1328, 10.1016/j.tcs.2008.05.016 Mostéfaoui, 2006, Exploring gafni’s reduction land: from Ωk to wait-free adaptive (2p−⌈pk⌉)-renaming via k-set agreement, vol. 4167, 1 Mostéfaoui, 2007, From renaming to k-set agreement, vol. 4474, 62 Gafni, 2007, Test&set, adaptive renaming and set agreement: a guided visit to asynchronous computability, 93 A. Castañeda, A Study of the Solvability of Weak Symmetry Breaking and Renaming, Ph.D. Thesis, Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México (UNAM), December 2010. Rajsbaum, 2011, A theory-oriented introduction to wait-free synchronization based on the adaptive renaming problem Borowsky, 1993, Generalized FLP impossibility result for t-resilient asynchronous computations, 91 Saks, 2000, Wait-free k-set agreement is impossible: the topology of public knowledge, SIAM Journal on Computing, 29, 1449, 10.1137/S0097539796307698 Herlihy, 1991, Wait-free synchronization, ACM Transactions on Programming Languages and Systems, 13, 124, 10.1145/114005.102808 Raynal, 2008, Locks considered harmful: a look at non-traditional synchronization, vol. 5287, 369 Herlihy, 1990, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems, 12, 463, 10.1145/78969.78972 Lamport, 1986, On interprocess communication, Part 1: basic formalism, Part II: algorithms, Distributed Computing, 1, 77, 10.1007/BF01786227 Gafni, 2004, Group solvability, vol. 3274, 30 Afek, 1993, Atomic snapshots of shared memory, Journal of the ACM, 40, 873, 10.1145/153724.153741 Imbs, 2009, Help when needed, but no more: efficient read/write partial snapshot, vol. 5805, 142 Attiya, 1998, Atomic snapshots in O(nlogn) operations, SIAM Journal on Computing, 27, 319, 10.1137/S0097539795279463 Neiger, 1994, Set linearizability. Brief announcement, 396 Lamport, 1987, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems, 5, 1, 10.1145/7351.7352 Herlihy, 2008 A. Fouren, Exponential Examples of Two Renaming Algorithms. Technion Tech Report, 1999. Available at www.cs.technion.ac.il/~hagit/pubs/expo.ps.gz. Taubenfeld, 2009, On the computational power of shared objects, vol. 5923, 270 Herlihy, 2003, Obstruction-free synchronization: double-ended queues as an example, 522 Chaudhuri, 1993, More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, 105, 132, 10.1006/inco.1993.1043 Raynal, 2009, Failure detectors for asynchronous distributed systems: an introduction. Wiley encyclopedia of, Computer Science and Engineering, 2, 1181 Neiger, 1995, Failure detectors and the wait-free hierarchy, 100 Raynal, 2006, In search of the holy grail: looking for the weakest failure detector for wait-free set agreement, vol. 4305, 1 Afek, 2008, Failure detectors in loosely named systems, 67 Herlihy, 2006, New perspectives in distributed computing, vol. 1672, 170 Herlihy, 2001, An overview of synchronous message-passing and topology, Electronic Notes in Theoretical Computer Science, 39, 1, 10.1016/S1571-0661(05)01148-5 Rajsbaum, 2010, Iterated shared memory models, vol. 6034, 407