Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt et al., Atomic snapshots of shared memory, Journal of the ACM, vol.40, issue.4, pp.873-890, 1993.
DOI : 10.1145/153724.153741

Y. Afek, E. Gafni, J. Tromp, and P. Vitányi, Wait-free test-and-set, Proc. of 6th WDAG, pp.85-94, 1992.
DOI : 10.1007/3-540-56188-9_6

D. Alistarh and J. Aspnes, Sub-logarithmic Test-and-Set against a Weak Adversary, Proc. of 25th DISC, pp.97-109, 2011.
DOI : 10.1007/s004460200071

D. Alistarh, J. Aspnes, K. Censor-hillel, S. Gilbert, and M. Zadimoghaddam, Optimal-time adaptive strong renaming, with applications to counting, Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, PODC '11, pp.239-248, 2011.
DOI : 10.1145/1993806.1993850

D. Alistarh, J. Aspnes, S. Gilbert, and R. Guerraoui, The Complexity of Renaming, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp.718-727, 2011.
DOI : 10.1109/FOCS.2011.66

D. Alistarh, H. Attiya, S. Gilbert, A. Giurgiu, and R. Guerraoui, Fast Randomized Test-and-Set and Renaming, Proc. of 24th DISC, pp.94-108, 2010.
DOI : 10.1007/978-3-642-15763-9_9

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

J. H. Anderson, Composite registers, Distributed Computing, vol.5, issue.1, pp.141-154, 1993.
DOI : 10.1007/BF02242703

J. Aspnes, Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers, Proc. of 25th DISC, pp.363-373, 2011.
DOI : 10.1017/CBO9780511814075

J. Aspnes, Faster randomized consensus with an oblivious adversary, Proc. of 31st PODC, pp.1-8, 2012.

J. Aspnes, A modular approach to shared-memory consensus, with applications to the probabilistic-write model, Distributed Computing, vol.16, issue.3, pp.179-188, 2012.
DOI : 10.1007/s00446-011-0134-8

H. Attiya and K. Censor, Tight bounds for asynchronous randomized consensus, J. of the ACM, vol.55, issue.5, 2008.

H. Attiya and K. Censor, Lower Bounds for Randomized Consensus under a Weak Adversary, SIAM Journal on Computing, vol.39, issue.8, pp.3885-3904, 2010.
DOI : 10.1137/090751906

Y. Aumann, Efficient asynchronous consensus with the weak adversary scheduler, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing , PODC '97, pp.209-218, 1997.
DOI : 10.1145/259380.259441

H. Buhrman, A. Panconesi, R. Silvestri, and P. Vitányi, On the importance of having an identity or, is consensus really universal? Distr, Comp, vol.18, issue.3, pp.167-176, 2006.

W. Eberly, L. Higham, and J. Warpechowska-gruca, Long-lived, fast, waitfree renaming with optimal name space and high throughput, Proc. of 12th DISC, pp.149-160, 1998.
DOI : 10.1007/BFb0056480

F. Ellen, P. Fatourou, and E. Ruppert, Time lower bounds for implementations of multi-writer snapshots, Journal of the ACM, vol.54, issue.6, 2007.
DOI : 10.1145/1314690.1314694

F. Ellen, P. Fatourou, and E. Ruppert, The space complexity of unbounded timestamps, Distributed Computing, vol.43, issue.4, pp.103-115, 2008.
DOI : 10.1007/s00446-008-0060-6

F. Fich, M. Herlihy, and N. Shavit, On the space complexity of randomized synchronization, Journal of the ACM, vol.45, issue.5, pp.843-862, 1998.
DOI : 10.1145/290179.290183

F. Fich, V. Luchangco, M. Moir, and N. Shavit, Obstruction-Free Algorithms Can Be Practically Wait-Free, Proc. of 19th DISC, pp.78-92, 2005.
DOI : 10.1007/11561927_8

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

M. Fischer, N. Lynch, and M. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM, vol.32, issue.2, pp.374-382, 1985.
DOI : 10.1145/3149.214121

G. Giakkoupis and P. Woelfel, On the time and space complexity of randomized test-and-set, Proceedings of the 2012 ACM symposium on Principles of distributed computing, PODC '12, pp.19-28
DOI : 10.1145/2332432.2332436

URL : https://hal.archives-ouvertes.fr/hal-00722947

W. Golab, D. Hendler, and P. Woelfel, An $O(1)$ RMRs Leader Election Algorithm, SIAM Journal on Computing, vol.39, issue.7, pp.2726-2760, 2010.
DOI : 10.1137/070686445

M. Helmi, L. Higham, E. Pacheco, and P. Woelfel, The space complexity of longlived and one-shot timestamp implementations, Proc. of 30th PODC, pp.139-148, 2011.

M. Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems, vol.13, issue.1, pp.124-149, 1991.
DOI : 10.1145/114005.102808

P. Jayanti, K. Tan, and S. Toueg, Time and Space Lower Bounds for Nonblocking Implementations, SIAM Journal on Computing, vol.30, issue.2, pp.438-456, 2000.
DOI : 10.1137/S0097539797317299

C. Kruskal, L. Rudolph, and M. Snir, Efficient synchronization of multiprocessors with shared memory, ACM Transactions on Programming Languages and Systems, vol.10, issue.4, pp.579-601, 1988.
DOI : 10.1145/48022.48024

A. Panconesi, M. Papatriantafilou, P. Tsigas, and P. Vitányi, Randomized naming using wait-free shared variables, Distributed Computing, vol.11, issue.3, pp.113-124, 1998.
DOI : 10.1007/s004460050045

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

E. Styer and G. Peterson, Tight bounds for shared memory symmetric mutual exclusion problems, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing , PODC '89, pp.177-191, 1989.
DOI : 10.1145/72981.72993

J. Tromp and P. Vitányi, Randomized two-process wait-free test-and-set, Distributed Computing, vol.15, issue.3, pp.127-135, 2002.
DOI : 10.1007/s004460200071

A. Appendix, ?. .. {1, and ?. , V M ) of M values from some domain D. It supports two operations ; scan() takes no parameter and returns the value of V , and update(i,x ), writes x to the i-th component of V and returns nothing. Our implementation uses an array A[1 . . . M ] of shared registers and a register S. Each array entry A[i] stores a triple (w i , p i , b i ), where w i ? D represents the i-th entry in the vector V of the snapshot object, p i is a process ID or ? which identifies the last process that wrote to A[i], and b i ? {0, 1} is a bounded (modulo 2) sequence number. Initially, S = ? and each array entry A[i] has the value (w i , ?, 0) for some fixed w i ? D. Now suppose process p calls update(i, x), and this is p's j-th update of the i-th component of V

. Hence, ); in particular it writes the triple (w, q, b) to A[i] at some point t * ? (t 1 , t 2 ) Recall that each time q writes to A[i] it alternates the bit it writes to the third component. Hence, at no point in [t 1 , t * ] the second and third component of A[i] can have value q and b