31 March 2022 — NUS Computing Assistant Professor Umang Mathur and his collaborators have won the Best Paper Award at the ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) 2022.
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 conference was held in early March this year.
Dr Mathur, along with Assistant Professor Andreas Pavlogiannis and PhD student Hünkar Can Tunç, both from Aarhus University, and Professor Mahesh Viswanathan from the University of Illinois at Urbana-Champaign, presented their paper on A Tree Clock Data Structure For Causal Orderings In Concurrent Executions at the conference.
In the paper, the team presented a new and efficient data structure for tracking causality in concurrent systems.
In a system comprising of multiple concurrent processes such as shared-memory or message passing multi-threaded programs, or even distributed systems, one often needs to track causal relationships between events. Causality is often encoded as a partial ordering on events and is succinctly captured using timestamps.
The traditional method to implement timestamps is to use flat array-like data structures called vector clocks, which provide APIs to update and to compute new timestamps. The vector clock data structure, although very ubiquitous, can be very slow, and hence, a source of severe performance bottleneck in applications where timestamps need to be frequently computed and updated.
“In our work, we propose a new data structure, tree clocks, as an alternative to the traditional vector clock data structure. The insight behind this data structure is that, by tracking only a small amount of additional information about how the timestamp was obtained, one can optimise the performance of timestamp operations,” explained Dr Mathur. “Tree clocks store such additional information in a hierarchical tree-like manner (hence their name) and are, in fact, optimal for the case of the happens-before partial order used in the context of the application of our interest: dynamic data race detection.”
Dr Mathur added that their work made ‘foundational contributions’ to the fundamental use of timestamps, and has the potential to have immediate impact in many application areas such as the analysis of concurrent software and in distributed computing.
“The proposed work is not just empirically promising but is also backed by theoretical guarantees, which, I believe, is a challenging and rare combination,” said Dr Mathur.
