Congratulations to assistant professor Andreas Pavlogiannis and PhD student Hünkar Can Tunc for winning the distinguished paper award at ASPLOS 2022. The paper ‘A tree clock data structure for causal orderings in concurrent executions’ is written in collaboration with Umang Mathur from National University of Singapore and Mahesh Viswanathan from University of Illinois at Urbana-Champaign.

Read the full paper at https://dl.acm.org/doi/10.1145/3503222.3507734.

ASPLOS is the premier forum for interdisciplinary systems research, intersecting computer architecture, hardware and emerging technologies, programming languages and compilers, operating systems, and networking. The 27th edition of the ASPLOS conference will be in Lausanne, Switzerland from Feb 28-March 4, 2022.

ABSTRACT

Dynamic techniques are a scalable and effective way to analyze concurrent programs. Instead of analyzing all behaviors of a program, these techniques detect errors by focusing on a single program execution. Often a crucial step in these techniques is to define a causal ordering between events in the execution, which is then computed using vector clocks, a simple data structure that stores logical times of threads. The two basic operations of vector clocks, namely join and copy, require Θ(k) time, where k is the number of threads. Thus, they are a computational bottleneck when k is large.

In this work, we introduce tree clocks, a new data structure that replaces vector clocks for computing causal orderings in program executions. Joining and copying tree clocks takes time that is roughly proportional to the number of entries being modified, and hence the two operations do not suffer the a-priori Θ(k) cost per application. We show that when used to compute the classic happens-before (HB) partial order, tree clocks are optimal, in the sense that no other data structure can lead to smaller asymptotic running time. Moreover, we demonstrate that tree clocks can be used to compute other partial orders, such as schedulable-happens-before (SHB) and the standard Mazurkiewicz (MAZ) partial order, and thus are a versatile data structure. Our experiments show that just by replacing vector clocks with tree clocks, the computation becomes from 2.02 × faster (MAZ) to 2.66 × (SHB) and 2.97 × (HB) on average per benchmark. These results illustrate that tree clocks have the potential to become a standard data structure with wide applications in concurrent analyses.