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), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 3: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 4: M. P. Herlihy , J. M. Wing, Axioms for concurrent objects, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.13-26, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41627]
• 5: Prasad Jayanti, Adaptive and efficient abortable mutual exclusion, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.295-304, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872079]
• 6: Leslie Lamport. On interprocess communication. Part II: Algorithms. Distributed Computing, 1(2):86--101, 1986.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Design, Theory

Keywords:
abortable types, memory contention, non-triviality, obstruction-freedom, shared memory, universal constructions