Computer science and engineering research finds real consistency of computer systems

By Peter Murphy

OSDI), one of the top symposiums associated with computer systems.

The symposium brings together professionals from academic and industrial backgrounds to discuss the design, implementation and implications of computer systems software. Lu’s research, featured in his paper “NCC: Natural Concurrency Control for Strictly Serializable Datastores by Avoiding the Timestamp-Inversion Pitfall,” deals with distributed computer systems, a fundamental enabler of computer applications today, and in the future.

“My research has three pillars,” Lu says. “The performance, correctness and practical impact of distributed systems. My work in correctness – the focus of this paper – is on the timestamp-inversion pitfall (PIT). This is an ongoing collaboration with Princeton University researchers, with the goal of identifying consistency violations within systems and automating that process.”

The consistency of distributed systems determines how easy it is to develop correct applications run on the systems. A stronger system consistency means that applications will have less bugs or other issues if two or more programs were to run on the systems at the same time. The computer system itself runs better, and can handle more applications and programs, if its consistency is stronger. Many researchers use timestamps to track system consistency, but according to Lu, this method is not without its flaws.

“Our work identifies a fundamental pitfall, the PIT, in leveraging timestamps to provide the strongest consistency model,” Lu says. “We examined some existing, well-known works that claim to provide the strongest consistency and use timestamps in their techniques. Several of the works we examined fell into PIT, meaning they do not provide as strong of a consistency as the claimed. Each of these three works still have many contributions, just with weaker consistency models than claimed.”

Computer application developers rely on consistency properties when building applications. Clarifying the real consistency level of systems is important because it will have a significant impact on how effectively different applications can run on a system. Identifying the actual consistency level of a system will improve the user experience and help develop better applications.

According to Lu, one of the main reasons the works he and his team identified fell into the PIT was because they used timestamp-based templates to measure consistency. This is a common practice, according to Lu, and one he has used himself, with some exceptions.

“One line of my work is to use timestamps to provide the strongest consistency while avoiding the PIT, i.e., striving to achieve the best possible performance and the strongest consistency at the same time.” Lu says. “Another line of work is to develop a formal method that automatically identifies consistency violations in existing works. We only examined a few well-known works for PIT and found some are incorrect. We are wondering how many more are out there.”

Lu is collaborating on this project with programming language and systems researchers at Princeton University.

Lu joined the UB School of Engineering and Applied Sciences in 2022. He earned his PhD in computer science from the University of Southern California in 2019. Lu’s research focuses on distributed systems and databases.