@inproceedings{cf3d825b0602481398864a0d4f799648,
title = "Atomicity checking in linear time using vector clocks",
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.",
keywords = "Atomicity, Concurrency, Conflict Serializability, Dynamic Program Analysis, Vector Clocks",
author = "Umang Mathur and Mahesh Viswanathan",
note = "Publisher Copyright: {\textcopyright} 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM.; 25th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2020 ; Conference date: 16-03-2020 Through 20-03-2020",
year = "2020",
month = mar,
day = "9",
doi = "10.1145/3373376.3378475",
language = "English (US)",
series = "International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS",
publisher = "Association for Computing Machinery",
pages = "183--199",
booktitle = "ASPLOS 2020 - 25th International Conference on Architectural Support for Programming Languages and Operating Systems",
address = "United States",
}