Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Theory of Computing Systems
Published in: Theory of Computing Systems 4/2013

01-05-2013

Built-in Coloring for Highly-Concurrent Doubly-Linked Lists

Authors: Hagit Attiya, Eshcar Hillel

Published in: Theory of Computing Systems | Issue 4/2013

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper presents a novel approach for highly-concurrent nonblocking implementations of doubly-linked lists, based on dynamically maintaining a coloring of the nodes in the list. In these implementations, operations on non-adjacent nodes in the linked-list proceed without interfering with each other. Roughly speaking, the operations are implemented by acquiring nodes in the operation’s data set, in the order of their colors, and then making the changes atomically. The length of waiting chains is restricted, thereby increasing concurrency, because the colors are taken from a small set. Operations carefully update the colors of the nodes they modify, so neighboring nodes in the list have different colors. A helping mechanism ensures progress in small neighborhoods of processes that keep taking steps.
We use this approach in two new algorithms: CAS-Chromo uses an unary conditional primitive, cas, and allows insertions anywhere in the linked list and removals only at the ends, while DCAS-Chromo allows insertions and removals anywhere but uses a stronger primitive, dcas.
previous article Parameterized Complexity of Satisfying Almost All Linear Equations over
next article Collusion in Atomic Splittable Routing Games

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
This is similar to the way an operation is invalidated before releasing its nodes in [4].
 
Literature
1.
Afek, Y., Merritt, M., Taubenfeld, G., Touitou, D.: Disentangling multi-object operations. In: Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 111–120 (1997)
2.
Agesen, O., Detlefs, D.L., Flood, C.H., Garthwaite, A.T., Martin, P.A., Shavit, N., Steele, G.L.: DCAS-based concurrent deques. Theory Comput. Syst. 35(3), 349–386 (2002) MathSciNetMATHCrossRef
3.
Arora, N.S., Blumofe, R.D., Plaxton, C.G.: Thread scheduling for multiprogrammed multiprocessors. Theory Comput. Syst. 34(2), 115–144 (2001) MathSciNetMATH
4.
5.
6.
Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley-Interscience, New York (2004)
7.
Barnes, G.: A method for implementing lock-free shared-data structures. In: Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 261–270 (1993)
8.
Detlefs, D., Flood, C.H., Garthwaite, A., Martin, P., Shavit, N., Steele, G.L. Jr.: Even better DCAS-based concurrent deques. In: Proceedings of the 14th International Conference on Distributed Computing (DISC), pp. 59–73 (2000)
9.
Doherty, S., Detlefs, D.L., Groves, L., Flood, C.H., Luchangco, V., Martin, P.A., Moir, M., Shavit, N., Steele, G.L. Jr.: DCAS is not a silver bullet for nonblocking algorithm design. In: Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 216–224 (2004)
10.
Fich, F.E., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free step complexity: Lock-free DCAS as an example. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC), pp. 493–494 (2005)
11.
Greenwald, M.: Non-blocking synchronization and system design. PhD thesis, Stanford University, August 1999
12.
Greenwald, M.: Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS. In: Proceedings of the 21st Annual Symposium on Principles of Distributed Computing (PODC), pp. 260–269 (2002)
13.
Ha, P.H., Tsigas, P., Wattenhofer, M., Wattenhofer, R.: Efficient multi-word locking using randomization. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 249–257 (2005)
14.
Harris, T.L.: A pragmatic implementation of non-blocking linked-lists. In: Proceedings of the 15th International Conference on Distributed Computing (DISC), pp. 300–314 (2001)
15.
Harris, T.L., Fraser, K.: Language support for lightweight transactions. In: Proceedings of the 2003 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA), pp. 388–402 (2003)
16.
Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990) CrossRef
17.
Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS), pp. 522–529 (2003)
18.
IBM. IBM System/370 Extended Architecture, Principle of Operation. IBM Publication No. SA22-7085 (1983)
19.
20.
Michael, M.M.: High performance dynamic lock-free hash tables and list-based sets. In: Proceedings of the 14th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 73–82 (2002)
21.
Michael, M.M.: CAS-based lock-free algorithm for shared deques. In: Proceedings of the 9th Euro-Par Conference on Parallel Processing, pp. 651–660 (2003)
22.
23.
Schneider, J., Wattenhofer, R.: Bounds on contention management algorithms. In: Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pp. 441–451 (2009) CrossRef
24.
Shavit, N., Touitou, D.: Software transactional memory. Distrib. Comput. 10(2), 99–116 (1997) CrossRef
25.
Sundell, H.: Efficient and practical non-blocking data structures. PhD thesis, Chalmers University of Technology (2004)
26.
Sundell, H., Tsigas, P.: Lock-free deques and doubly linked lists. J. Parallel Distrib. Comput. 68(7), 1008–1020 (2008) MATHCrossRef
27.
Turek, J., Shasha, D., Prakash, S.: Locking without blocking: making lock based concurrent data structure algorithms nonblocking. In: Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 212–222 (1992)
Metadata
Title
Built-in Coloring for Highly-Concurrent Doubly-Linked Lists
Authors
Hagit Attiya
Eshcar Hillel
Publication date
01-05-2013
Publisher
Springer-Verlag
Published in
Theory of Computing Systems / Issue 4/2013
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-012-9420-5

Other articles of this Issue 4/2013

Theory of Computing Systems 4/2013 Go to the issue

OriginalPaper

Improved Lower Bounds on the Price of Stability of Undirected Network Design Games

OriginalPaper

Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds

OriginalPaper

On Rationality of Verbal Subsets in a Group

OriginalPaper

Parameterized Complexity of Satisfying Almost All Linear Equations over

OriginalPaper

Partition Into Triangles on Bounded Degree Graphs

OriginalPaper

Collusion in Atomic Splittable Routing Games

Premium Partner

    Image Credits