. Here, we already known that this holds. Therefore, by the same argument as in the first case, we conclude that there is a path between op and op in CG

=. Op and . Op-k, op 1 defined as in the first case By the same reasoning as in the first case, each of these operations is a vertex and (op i , op i?1 ), (op i , op i ?1 ) are edges of CG(op, op ) , for each i, i : 2 ? i ? k, 2 ? i ? k, Since DS(op 1 ) ? DS(op 1 ) = ?, we conclude that op and op are connected by a path in CG(op, op )

]. Y. Afek, D. Dauber, and D. Touitou, Wait-free made fast, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing , STOC '95, pp.538-547, 1995.
DOI : 10.1145/225058.225271

Y. Afek, M. Merritt, G. Taubenfeld, and D. Touitou, Disentangling multi-object operations (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing , PODC '97, pp.111-120, 1997.
DOI : 10.1145/259380.259431
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.1771

J. H. Anderson and M. Moir, Universal constructions for multi-object operations, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing , PODC '95, pp.184-193, 1995.
DOI : 10.1145/224964.224985
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.80.4860

J. H. Anderson and M. Moir, Universal constructions for large objects, IEEE Transactions on Parallel and Distributed Systems, vol.10, issue.12, pp.1317-1332, 1999.
DOI : 10.1109/71.819952
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.161.5007

H. Attiya and E. Dagan, Universal operations, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing , PODC '96, pp.223-232, 1996.
DOI : 10.1145/248052.248097

H. Attiya and E. Hillel, Built-In Coloring for Highly-Concurrent Doubly-Linked Lists, Distributed Computing, 20th International Symposium, DISC 2006 Proceedings, pp.31-45, 2006.
DOI : 10.1007/11864219_3

H. Attiya and E. Hillel, Highly-concurrent multi-word synchronization, Proceedings of the 9th international conference on Distributed computing and networking, ICDCN'08, pp.112-123, 2008.
DOI : 10.1007/978-3-540-77444-0_9
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.167.2736

H. Attiya and E. Hillel, Single-version stms can be multi-version permissive, Proceedings of the 12th international conference on Distributed computing and networking, pp.83-94, 2011.

H. Attiya, E. Hillel, and A. Milani, Inherent limitations on disjoint-access parallel implementations of transactional memory, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, SPAA '09, pp.69-78, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00992693

G. Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures , SPAA '93, pp.261-270, 1993.
DOI : 10.1145/165231.165265

V. Bushkov, R. Guerraoui, and M. Kapalka, On the liveness of transactional memory, Proceedings of the 31st ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '12

P. Chuong, F. Ellen, and V. Ramachandran, A universal construction for wait-free transaction friendly data structures, Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures, SPAA '10, pp.335-344, 2010.
DOI : 10.1145/1810479.1810538

T. Crain, D. Imbs, and M. , Towards a universal construction for transaction-based multiprocess programs, ICDCN, pp.61-75, 2012.
DOI : 10.1016/j.tcs.2012.09.011
URL : https://hal.archives-ouvertes.fr/inria-00576755

D. Dice and N. Shavit, What Really Makes Transactions Faster?, Proc. of the 1st TRANSACT 2006 workshop, 2006.

P. Fatourou and N. D. Kallimanis, The RedBlue Adaptive Universal Constructions, Proceedings of the 23rd international conference on Distributed computing, DISC'09, pp.127-141, 2009.
DOI : 10.1007/978-3-642-04355-0_15

P. Fatourou and N. D. Kallimanis, A highly-efficient wait-free universal construction, Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures, SPAA '11, pp.325-334, 2011.
DOI : 10.1145/1989493.1989549

K. Fraser, Practical lock freedom, 2003.

R. Guerraoui and M. Kapalka, On obstruction-free transactions, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, SPAA '08, pp.304-313, 2008.
DOI : 10.1145/1378533.1378587

M. Herlihy, A methodology for implementing highly concurrent data structures, Proceedings of the second ACM SIGPLAN symposium on Principles & Practice of Parallel Programming, PPOPP '90, pp.197-206, 1990.

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

M. Herlihy, V. Luchangco, P. Martin, and M. Moir, Nonblocking memory management support for dynamic-sized data structures, ACM Transactions on Computer Systems, vol.23, issue.2, pp.146-196, 2005.
DOI : 10.1145/1062247.1062249

M. Herlihy and J. E. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on computer architecture, ISCA '93, pp.289-300, 1993.
DOI : 10.1109/isca.1993.698569
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.208.4448

M. Herlihy and J. M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems, vol.12, issue.3, pp.463-492, 1990.
DOI : 10.1145/78969.78972

A. Israeli and L. Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing , PODC '94, pp.151-160, 1994.
DOI : 10.1145/197917.198079

V. J. Marathe, W. N. Scherer, I. , and M. L. Scott, Adaptive software transactional memory Earlier but expanded version available as TR 868, Proceedings of the 19th International Symposium on Distributed Computing, 2005.
DOI : 10.1007/11561927_26
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.126.9568

D. Pelerman, R. Fan, and I. Keidar, On maintaining multiple versions in stm, Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '10, pp.16-25, 2010.

N. Shavit and D. Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, PODC '95, pp.204-213, 1995.

F. Tabba, M. Moir, J. R. Goodman, A. Hay, and C. Wang, NZTM, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, SPAA '09, 2009.
DOI : 10.1145/1583991.1584048

J. Turek, D. Shasha, and S. Prakash, Locking without blocking, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems , PODS '92, pp.212-222, 1992.
DOI : 10.1145/137097.137873

J. Wamhoff, T. Riegel, C. Fetzer, and P. Felber, Robustm: A robust software transactional system, Stabilization, Safety, and Security in Distributed Systems, Proceedings, 2010.

. Append, the list L by appending a node containing num as the next element of that pointed to by end, and updating end to point to the newly appended node. Search(L, num) searches L for the first occurrence of num, starting from the element pointed to by start. Search returns true if num is in L and false otherwise. Throughout this code, if T is a type with some field f , then ptr to T t declares that t is a pointer to an object of type T and t ? f denotes the f field of that object. CreateDI(T ) creates a new data item of type T and returns a pointer to it, ReadDI() and WriteDI() are used when accessing a data item or a field of a data item