Abortable and query-abortable objects and their efficient implementation

ABSTRACT

We introduce abortable and query-abortable objects, intended for asynchronous shared-memory systems with low contention. These objects behave like ordinary objects when accessed sequentially, but may abort operations when accessed concurrently. An aborted operation may or may not take effect, i.e., cause a state transition, and it returns no indication of which possibility occurred. Since this uncertainty is problematic, a query-abortable object supports a QUERY operation that each process can use to determine its last non-QUERY operation on the object that caused a state transition, and the response associated with this state transition. Query-abortable objects can easily implement obstruction-free objects (introduced by Herlihy, Luchangco and Moir) and pausable objects (introduced by Attiya, Guerraoui and Kouznetsov).

We present universal constructions for abortable and query-abortable objects that use only abortable registers -- registers that are strictly weaker than safe registers. Our universal constructions are novel and efficient in the number of registers used. Specifically, they are based on a simple time stamping mechanism for detecting concurrent executions, and in systems with n processes, they use only 2n abortable registers. It is worth noting that our results imply that any obstruction-free object and any pausable object can be implemented using only 2n abortable registers.

Finally, we identify a potential problem with correctness properties based on step contention: with such properties, the composition of correct object implementations may result in an implementation that is not correct. In other words, implementations defined in terms of step contention are not always composable. To avoid this problem, we use interval contention to define the correct behaviour of abortable and query-abortable objects.

References

1. Hagit Attiya, Rachid Guerraoui, and Petr Kouznetsov. Computing with reads and writes in the absence of step contention. In DISC '05: 19th International Symposium on Distributed Computing, volume 3724 of Lecture Notes in Computer Science, pages 122--136. Springer, 2005.
2. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124--149, 1991.
3. Maurice Herlihy, Victor Luchangco, and Mark Moir. Obstruction-free synchronization: Double-ended queues as an example. In ICDCS '03: Proceedings of the 23rd International Conference on Distributed Computing Systems, page 522--529, Washington, DC, USA, 2003. IEEE Computer Society.
4. Maurice Herlihy and Jeannette Wing. Axioms for concurrent objects. In POPL '87: Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pages 13--26, New York, NY, USA, 1987. ACM Press.
5. Prasad Jayanti. Adaptive and efficient abortable mutual exclusion. In PODC '03: Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing, pages 295--304, New York, NY, USA, 2003. ACM Press.
6. Leslie Lamport. On interprocess communication. Part II: Algorithms. Distributed Computing, 1(2):86--101, 1986.

Index Terms

• Hardware

  • Integrated circuits

    • Semiconductor memory

      • Dynamic memory

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Concurrency control

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications

• Theory of computation

  • Design and analysis of algorithms