TaDA: A Logic for Time and Data Abstraction

Authors

  • Pedro da Rocha Pinto
  • Thomas Dinsdale-Young
  • Philippa Gardner

Abstract

To avoid data races, concurrent operations should either be at distinct times or on distinct data. Atomicity is the abstraction that an operation takes effect at a single, discrete instant in time, with linearisability being a well-known correctness condition which asserts that concurrent operations appear to behave atomically. Disjointness is the abstraction that operations act on distinct data resource, with concurrent separation logics enabling reasoning about threads that appear to operate independently on disjoint resources. Building on separation logic with concurrent abstract predicates (CAP), we introduce TaDA, a program logic which combines the benefits of abstract atomicity and abstract disjointness. We give several examples: an atomic lock module, a CAP example with a twist, which cannot be done using linearisability; an atomic MCAS module implemented using our lock module, a classic linearisability example which cannot be done using CAP; and a double-ended queue module implemented using MCAS.

Venue

Proceedings of the 28th European Conference on Object-Oriented Programming (ECOOP’14), pp. 207–231

Publication Date

Jul 2014

Identifiers

Source Materials