Atomicity checking in linear time using vector clocks

Umang Mathur, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Multi-threaded programs are challenging to write. Developers often need to reason about a prohibitively large number of thread interleavings to reason about the behavior of software. A non-interference property like atomicity can reduce this interleaving space by ensuring that any execution is equivalent to an execution where all atomic blocks are executed serially. We consider the well studied notion of conflict serializability for dynamically checking atomicity. Existing algorithms detect violations of conflict serializability by detecting cycles in a graph of transactions observed in a given execution. The number of edges in such a graph can grow quadratically with the length of the trace making the analysis not scalable. In this paper, we present AeroDrome, a novel single pass linear time algorithm that uses vector clocks to detect violations of conflict serializability in an online setting. Experiments show that AeroDrome scales to traces with a large number of events with significant speedup.

Original languageEnglish (US)
Title of host publicationASPLOS 2020 - 25th International Conference on Architectural Support for Programming Languages and Operating Systems
PublisherAssociation for Computing Machinery
Pages183-199
Number of pages17
ISBN (Electronic)9781450371025
DOIs
StatePublished - Mar 9 2020
Event25th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2020 - Lausanne, Switzerland
Duration: Mar 16 2020Mar 20 2020

Publication series

NameInternational Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS

Conference

Conference25th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2020
CountrySwitzerland
CityLausanne
Period3/16/203/20/20

Keywords

  • Atomicity
  • Concurrency
  • Conflict Serializability
  • Dynamic Program Analysis
  • Vector Clocks

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Atomicity checking in linear time using vector clocks'. Together they form a unique fingerprint.

  • Cite this

    Mathur, U., & Viswanathan, M. (2020). Atomicity checking in linear time using vector clocks. In ASPLOS 2020 - 25th International Conference on Architectural Support for Programming Languages and Operating Systems (pp. 183-199). (International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS). Association for Computing Machinery. https://doi.org/10.1145/3373376.3378475