Jump to Content
Jeremy Hurwitz

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.
Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, desc
  • Year
  • Year, desc
    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
    No Results Found