Jeremy Hurwitz
Jeremy Hurwitz is presently a software engineer at Google. Before coming to Google, he received an M.Eng. from MIT and an M.S. from CalTech. His main interests are in the theoretical aspects of Computer Science, including algorithms and complexity theory.
Research Areas
Authored Publications
Sort By
On the k-atomicity-verification problem
Wojciech Golab
The 33rd International Conference on Distributed Computing Systems, IEEE (2013)
Preview abstract
Modern Internet-scale storage systems often provide weak consistency in exchange for better perfor- mance and resilience. An important weak consistency prop- erty is k-atomicity, which bounds the staleness of values returned by read operations. The k-atomicity-verification problem (or k-AV for short) is the problem of deciding whether a given history of operations is k-atomic. The 1-AV problem is equivalent to verifying atomicity/linearizability, a well-known and solved problem. However, for k ? 2, no polynomial-time k-AV algorithm is known.
This paper makes the following contributions towards solving the k-AV problem. First, we present a simple 2- AV algorithm called LBT, which is likely to be efficient (quasilinear) for histories that arise in practice, although it is less efficient (quadratic) in the worst case. Second, we present a more involved 2-AV algorithm called FZF, which runs efficiently (quasilinear) even in the worst case. To our knowledge, these are the first algorithms that solve the 2-AV problem fully. Third, we show that the weighted k-AV problem, a natural extension of the k-AV problem, is NP-complete.
View details
