Dynamic race prediction in linear time

Dileep Kini, Umang Mathur, Mahesh Viswanathan

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

Abstract

Writing reliable concurrent software remains a huge challenge for today's programmers. Programmers rarely reason about their code by explicitly considering different possible inter-leavings of its execution. We consider the problem of detecting data races from individual executions in a sound manner. The classical approach to solving this problem has been to use Lamport's happens-before (HB) relation. Until now HB remains the only approach that runs in linear time. Previous efforts in improving over HB such as causallyprecedes (CP) and maximal causal models fall short due to the fact that they are not implementable efficiently and hence have to compromise on their race detecting ability by limiting their techniques to bounded sized fragments of the execution. We present a new relation weak-causally-precedes (WCP) that is provably better than CP in terms of being able to detect more races, while still remaining sound. Moreover, it admits a linear time algorithm which works on the entire execution without having to fragment it.

Original languageEnglish (US)
Title of host publicationPLDI 2017 - Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
EditorsAlbert Cohen, Martin Vechev
PublisherAssociation for Computing Machinery
Pages157-170
Number of pages14
ISBN (Electronic)9781450349888
DOIs
StatePublished - Jun 14 2017
Event38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017 - Barcelona, Spain
Duration: Jun 18 2017Jun 23 2017

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
VolumePart F128414

Other

Other38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017
CountrySpain
CityBarcelona
Period6/18/176/23/17

Keywords

  • Concurrency
  • Online algorithm
  • Race prediction

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Dynamic race prediction in linear time'. Together they form a unique fingerprint.

Cite this