The RedBlue family of universal constructions
Abstract
A universal construction is a general mechanism for obtaining a concurrent implementation of any shared object from its sequential implementation. We present the family of RedBlue universal constructions which produce adaptive, linearizable, wait-free, concurrent implementations of shared objects. The proposed universal constructions improve upon previous universal constructions in terms of their step and/or space complexity. The first of these universal constructions, which serves as the keystone for the design of the other RedBlue algorithms, produces concurrent implementations with better step complexity than those produced by all previously presented universal constructions but it uses large LL/SC registers. The second universal construction significantly reduces the size of the required registers, whereas the last two are appropriate for the purpose of simulating large objects.
References
[1]
Afek, Y., Attiya, H., Fouren, A., Stupp, G., Touitou, D.: Long-lived renaming made adaptive. In Proceedings of the 18th ACM Symposium on Principles of Distributed Computing, pp. 91–103 (1990)
[2]
Afek, Y., Boxer, P., Touitou, D.: Bounds on the shared memory requirements for long-lived and adaptive objects. In Proceedings of the 19th ACM Symposium on Principles of Distributed Computing, pp. 81–89 (2000)
[3]
Afek, Y., Dauber, D., Touitou, D.: Wait-free made fast. In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp. 538–547 (1995)
[4]
Anderson JH and Moir M Universal constructions for large objects IEEE Trans. Parallel Distrib. Syst. 1999 10 12 1317-1332
[5]
Attiya H and Fouren AAdaptive and efficient wait-free algorithms for lattice agreement and renamingSIAM J. Comput.2001312642-6641861294
[6]
Attiya H and Fouren AAlgorithms adapting to point contentionJ. ACM200350444-4682146882
[7]
Attiya H and Welch J Distributed Computing: Fundamentals, Simulations and Advanced Topics 2004 New York Wiley
[8]
Barnes, G.: A method for implementing lock-free shared data structures. In: Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, pp. 261–270 (1993)
[9]
Chandra, T.D., Jayanti, P., Tan, K.: A polylog time wait-free construction for closed objects. In: Proceedings of the 17th ACM Symposium on Principles of Distributed Computing, pp. 287–296 (1998)
[10]
Chuong, P., Ellen, F., Ramachandran, V.: A universal construction for wait-free transaction friendly data structures. In: Proceedings of the 22nd Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 335–344 (2010)
[11]
Fatourou, P., Kallimanis, N.D.: The redblue adaptive universal constructions. Technical Report TR 2009-02, Department of Computer Science, University of Ioannina (2009, February)
[12]
Fatourou, P., Kallimanis, N.D.: The redblue adaptive universal constructions. In: Proceedings of the 23rd International Symposium Distributed Computing, volume 5805 of Lecture Notes in Computer Science, pp. 127–141. Springer (2009)
[13]
Fatourou, P., Kallimanis, N.D.: A highly-efficient wait-free universal construction. In Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 325–334. ACM (2011)
[14]
Fatourou P and Kallimanis NDHighly-efficient wait-free synchronizationTheory Comput. Syst.2014553475-5203250814
[15]
Herlihy M Wait-free synchronization ACM Trans. Progr. Lang. Syst. 1991 13 124-149
[16]
Herlihy M A methodology for implementing highly concurrent data objects ACM Trans. Progr. Lang. Syst. 1993 15 5 745-770
[17]
Herlihy M, Luchangco V, and Moir M Space and time adaptive non-blocking algorithms Electron. Notes Theor. Comput. Sci. 2003 78 260
[18]
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, pp. 289–300. ACM (1993)
[19]
Herlihy MP and Wing JM Linearizability: a correctness condition for concurrent objects ACM Trans. Progr. Lang. Syst. 1990 12 463-492
[20]
Jayanti, P.: A time complexity lower bound for randomized implementations of some shared objects. In: Proceedings of the 17th ACM Symposium on Principles of Distributed Computing, pp. 201–210 (1998)
[21]
Jayanti, P.: f-arrays: implementation and applications. In: Proceedings of the 21th ACM Symposium on Principles of Distributed Computing, pp. 270–279 (2002)
[22]
Jayanti, P., Petrovic, S.: Efficient wait-free implementation of multiword LL/SC variables. In: Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, pp. 59–68 (2005)
[23]
Shavit, N., Touitou, D.: Software transactional memory. In: Proceedings of the 14th annual ACM Symposium on Principles of Distributed Computing, pp. 204–213. ACM (1995)
Index Terms
- The RedBlue family of universal constructions
Index terms have been assigned to the content through auto-classification.
Recommendations
A paradox of eventual linearizability in shared memory
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computingThis paper compares, for the first time, the computational power of linearizable objects with that of eventually linearizable ones. We present the following paradox. We show that, unsurprisingly, no set of eventually linearizable objects can (1) ...
A wait-free universal construction for large objects
PPoPP '20: Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel ProgrammingConcurrency has been a subject of study for more than 50 years. Still, many developers struggle to adapt their sequential code to be accessed concurrently. This need has pushed for generic solutions and specific concurrent data structures.
Wait-free ...
Wait-free linearization with an assertional proof
Given a sequential implementation of an arbitrary data object, a wait-free, linearizable concurrent implementation is constructed with space complexity quadratic in the number of processes. If processes do not concurrently invoke, the amortized time ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© Springer-Verlag GmbH Germany, part of Springer Nature 2020.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 December 2020
Accepted: 26 January 2020
Received: 09 January 2016
Author Tags
Qualifiers
- Research-article
Funding Sources
- European Commission
- Research Committee of the University of Ioannina
- ARISTEIA Action of the Operational Program Education and Lifelong Learning
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Dec 2024