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
Distributed Computing
Published in: Distributed Computing 4/2016

01-08-2016

Universal constructions that ensure disjoint-access parallelism and wait-freedom

Authors: Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, Corentin Travers

Published in: Distributed Computing | Issue 4/2016

Log in

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

search-config
loading …

Abstract

A universal construction is a general mechanism for obtaining a concurrent implementation of an object from its sequential code. We show that there is no universal construction that is both disjoint-access parallel (guaranteeing the processes operating on different parts of an implemented object do not interfere with one another) and wait-free (guaranteeing progress for each nonfaulty process when accessing an object). In contrast, we present a universal construction which results in disjoint-access parallel, wait-free implementations of any object provided there is a bound on the number of data items accessed by each operation supported by the object.
previous article Upper and lower bounds for deterministic broadcast in powerline communication networks
next article Modelling and verifying the AODV routing protocol

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 "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

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
Literature
1.
Afek, Y., Dauber, D., Touitou, D.: Wait-free made fast. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pp. 538–547. ACM (1995)
2.
Afek, Y., Merritt, M., Taubenfeld, G., Touitou, D.: Disentangling multi-object operations (extended abstract). In: Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 111–120. ACM (1997)
3.
Anderson, J.H., Moir, M.: Universal constructions for multi-object operations. In: Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 184–193. ACM (1995)
4.
Anderson, J.H., Moir, M.: Universal constructions for large objects. IEEE Trans. Parallel Distrib. Syst. 10(12), 1317–1332 (1999)CrossRef
5.
6.
Attiya, H., Fatourou, P.: Disjoint access parallelism in software transactional memory. Transactional Memory: Foundations. Algorithms, Tools and Applications, vol. 8913, pp. 72–97. Springer, Lecture Notes in Computing Sciences (2015)
7.
8.
9.
Attiya, H., Hillel, E., Milani, A.: Inherent limitations on disjoint-access parallel implementations of transactional memory. Theory Comput. Syst. 49(4), 698–719 (2011)MathSciNetCrossRefMATH
10.
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. ACM (1993)
11.
Berenson, H., Bernstein, P.A., Gray, J., Melton, J., O’Neil, E.J., O’Neil, P.E.: A critique of ANSI SQL isolation levels. In: Proceedings of the 16th ACM International Conference on Management of Data (SIGMOD), pp. 1–10. ACM Press (1995)
12.
Bushkov, V., Dziuma, D., Fatourou, P., Guerraoui, R.: The PCL theorem–transactions cannot be parallel, consistent and live. In: Proceedings of the 26th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM Press, July 2014
13.
Bushkov, V., Guerraoui, R., Kapałka, M.: On the liveness of transactional memory. In: Proceedings of the 31st ACM Symposium on Principles of Distributed Computing (PODC), pp. 9–18. ACM (2012)
14.
Chuong, P., Ellen, F., Ramachandran, V.: A universal construction for wait-free transaction friendly data structures. In: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 335–344. ACM (2010)
15.
Dice, D., Shavit, N.: What really makes transactions faster? In: 1st Workshop on Transactional Computing (2006)
16.
Fatourou, P., Kallimanis, N.D.: The redblue adaptive universal constructions. In: Proceedings of the 23rd International Symposium Distributed Computing (DISC), vol. 5805 of Lecture Notes in Computer Science, pp. 127–141. Springer (2009)
17.
18.
Felber, P., Fetzer, C., Riegel, T.: Dynamic performance tuning of word-based software transactional memory. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 237–246. ACM (2008)
19.
20.
21.
Guerraoui, R., Kapałka, M.: On obstruction-free transactions. In: Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 304–313. ACM (2008)
22.
Guerraoui, R., Kapałka, M.: On the correctness of transactional memory. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 175–184. ACM (2008)
23.
Guerraoui, R., Kapalka, M.: The semantics of progress in lock-based transactional memory. In: Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pp. 404–415. ACM (2009)
24.
Herlihy, M.: A methodology for implementing highly concurrent data structures. In: Proceedings of the 2nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 197–206. ACM (1990)
25.
Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13, 124–149 (1991)CrossRef
26.
Herlihy, M., Luchangco, V., Martin, P., Moir, M.: Nonblocking memory management support for dynamic-sized data structures. ACM Trans. Comput. Syst. 23, 146–196 (2005)CrossRef
27.
Herlihy, M., Moss, J.E.B.: Transactional memory: architectural support for lock-free data structures. In: Proceedings of the 20th Annual International Symposium on Computer Architecture (ISCA), pp. 289–300. ACM (1993)
28.
Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)CrossRef
29.
Israeli, A., Rappoport, L.: Disjoint-access-parallel implementations of strong shared memory primitives. In: Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 151–160. ACM (1994)
30.
Jayanti, P., Petrovic, S.: Efficiently implementing a large number of LL/SC objects. In: Proceedings of the 9th International Conference on Principles of Distributed Computing (OPODIS), vol. 3974 of Lecture Notes in Computer Science, pp. 45–56. Springer (2005)
31.
Kuznetsov, P., Ravi, S.: On partial wait-freedom in transactional memory. In: Proceedings of the 2015 International Conference on Distributed Computing and Networking, (ICDCN), pp. 10:1–10:9. ACM (2015)
32.
Lu, S., Bernstein, A., Lewis, P.: Correct execution of transactions at different isolation levels. IEEE Trans. Knowl. Data Eng. 16(9), 1070–1081 (2004)CrossRef
33.
Marathe, V.J., III, W.N.S., Scott, M.L.: Adaptive software transactional memory. In: Proceedings of the 19th International Conference on Distributed Computing (DISC), vol. 3724 of Lecture Notes in Computer Science, pp. 354–368. Springer (2005)
34.
35.
Peluso, S., Palmieri, R., Romano, P., Ravindran, B., Quaglia, F.: Disjoint-access parallelism: impossibility, possibility, and cost of transactional memory implementations. In: Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC), pp. 217–226. ACM (2015)
36.
Riegel, T., Fetzer, C., Felber, P.: Snapshot isolation for software transactional memory. In: First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT) (2006)
37.
Shavit, N., Touitou, D.: Software transactional memory. In: Proceedings of the 14th Annual ACM symposium on Principles of Distributed Computing (PODC), pp. 204–213. ACM (1995)
38.
Tabba, F., Moir, M., Goodman, J.R., Hay, A.W., Wang, C.: Nztm: nonblocking zero-indirection transactional memory. In: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 204–213. ACM (2009)
39.
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. ACM (1992)
40.
Weikum, G., Vossen, G.: Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann, Los Altos (2001)
Metadata
Title
Universal constructions that ensure disjoint-access parallelism and wait-freedom
Authors
Faith Ellen
Panagiota Fatourou
Eleftherios Kosmas
Alessia Milani
Corentin Travers
Publication date
01-08-2016
Publisher
Springer Berlin Heidelberg
Published in
Distributed Computing / Issue 4/2016
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-015-0261-8

Premium Partner

    Image Credits