Pith. sign in

REVIEW 3 major objections 4 minor 67 references

Using Weaker Consistency Models with Monitoring and Recovery for Improving Performance of Key-Value Stores

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A detect-rollback scheme lets eventual consistency match sequential-consistency correctness while running faster.

desk verdict The detect-rollback system is real and the throughput gains look genuine, but for graph coloring the monitored predicate only enforces mutual exclusion, so stale reads can corrupt output without ever tripping the detector. read the letter →

arxiv 1909.01980 v1 pith:UGPRA3NJ submitted 2019-09-04 cs.DC

Duong Nguyen , Aleksey Charapko , Sandeep S Kulkarni , Murat Demirbas This is my paper · ORCID
classification cs.DC
keywords eventualconsistencysequentialpredicatedetectionrollbackrecoverykey-valuestoresmutualexclusiondistributedmonitoringhybridvectorclocks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that a program written for a sequentially consistent key-value store does not have to be rewritten when the store only offers eventual consistency. The designer keeps running the original algorithm, monitors a correctness predicate $P$ that the sequential-consistency assumption was supposed to guarantee, and rolls back to an earlier state whenever $P$ fails. The paper demonstrates this detect-rollback loop on graph-processing workloads over the Voldemort key-value store, where $P$ is the mutual-exclusion property that no two clients update neighboring nodes at the same time. In cloud deployments the approach raised client throughput by 50–80% relative to sequential consistency, with monitoring overhead usually below 4%, and after accounting for rollback it still produced final progress gains of 10–47% on the tested workloads. The point is that a designer can keep the easy programming model of strong consistency while paying for the weaker store's higher performance only when an actual violation occurs.

What carries the argument

The load-bearing mechanism is the detect-rollback loop built from three pieces: (1) local predicate detectors attached to each key-value server that intercept PUT requests and emit candidates—timestamped intervals in which the local part of $\neg P$ holds—using hybrid vector clocks to track causality; (2) monitor processes that run the linear and semilinear predicate detection algorithms, checking whether a consistent global state satisfying $\neg P$ exists and returning it as evidence of a violation; (3) a client-side rollback algorithm that partitions each task into a read phase and a write phase, so a client receiving a violation notice during its read phase simply aborts and re-reads instead of writing. The key timing property making this safe is that detection latency is much smaller than a task's read-phase duration, so the client responsible for the violation has not yet written anything when the violation is reported. This machinery converts a correctness violation into a cheap local retry rather than a full distributed rollback.

What would settle it

Run the Social Media Analysis workload while artificially increasing monitor delay or network latency so that detection latency exceeds a client's read-phase duration; if the store then ever fails a post-hoc check for mutual exclusion on neighboring nodes, the rollback guarantee is broken. A cheaper quantitative check is to measure whether the throughput advantage over sequential consistency disappears when violation frequency is high enough that clients are stuck in repeated rollbacks despite backoff and adaptive mechanisms.

Watch

Extended reading notes

Core claim

The central claim is that optimistic execution—running a sequential-consistency-correct algorithm against an eventually consistent store, watching for violations of an application-defined predicate $P$, and rolling back when $P$ breaks—preserves correctness while delivering the throughput advantage of weak consistency. The paper implements predicate detection for linear and semilinear predicates using hybrid vector clocks, integrated into the Voldemort key-value store, with local detectors on servers that emit timestamped candidate states to monitors. For graph applications the monitored predicate is mutual exclusion on neighboring nodes; when a violation is caught while the offending client is still in its read phase, the client aborts and restarts its task, and no wrong write ever reaches the store. In experiments, aggregate client throughput increased by 50–80% on Amazon AWS compared with sequential consistency (57% and 78% for two sequential configurations of the Social Media Analysis workload), monitoring overhead was typically below 4% and at most 8%, and more than 99.9% of induced violations were detected within 50 ms in a regional network and within 3 s globally. After including rollback cost, terminating applications finished 10–20% faster (Social Media Analysis, using adaptive switching to sequential consistency near the end) and non-terminating applications progressed 45–47% faster (Weather Monitoring), so the paper concludes that eventual consistency with rollback still beats sequential consistency overall.

Load-bearing premise

The whole safety argument rests on every violation being detected before any involved client has started writing its results, so that aborting read-phase work is enough to undo the damage; if detection ever arrives after a client has already written, the rollback no longer restores correctness.

Editorial extensions

If this is right

  • Designers of graph-processing algorithms can keep their sequential-consistency-correct code and gain 10–47% final progress on the tested workloads, or 50–80% on raw throughput, simply by adding a monitor and a rollback rule.
  • Monitoring overhead is low enough for production use: typically under 4% and at most 8% in the paper's experiments, so the approach is practical as a runtime safety net rather than just a debugging tool.
  • Violation detection is fast enough to support the rollback strategy: more than 99.9% of induced violations were found within 50 ms regionally and within 3 s globally, well under the 22–45 s task durations observed in the same experiments.
  • Terminating applications may livelock near completion; switching to sequential consistency (adaptive consistency) restores progress and yields a final 10–20% gain, while non-terminating applications keep a 45–47% gain using random backoff.
  • Because Voldemort clients control their read and write quorum settings, moving from eventual to sequential consistency at run time requires no changes to the servers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same pattern should extend beyond graph applications to any workload where correctness can be expressed as a monitorable predicate and tasks have a read-compute-write shape; the paper's own identified open direction is integrating the monitor with a general snapshot-rollback service such as Retroscope.
  • A testable threshold prediction follows from the weakest assumption: if detection latency is made to exceed the read-phase duration (for example by slowing the monitors or inflating network delay), the abort-and-restart recovery will no longer prevent incorrect writes from being committed, so the approach must switch to sequential consistency or full snapshot rollback.
  • The throughput benefit is geography-dependent: the paper reports the gap over sequential consistency growing with one-way latency between replicas (from about 47% to 60% in one configuration), suggesting the scheme is most attractive for wide-area deployments where the cost of strong consistency is highest.
  • For a practitioner, the economic question the paper leaves open is the cost of dedicated monitor machines: the paper co-locates monitors with servers and notes that separate hosts are more efficient, but does not quantify that hardware cost.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes a detect-rollback framework that lets a designer run an algorithm written for sequential consistency on an eventually consistent key-value store. The designer identifies a correctness predicate P; a monitoring module detects violations of P caused by weaker consistency; on detection, the system rolls back to a state where P holds and resumes. The authors implement monitors for linear and semilinear predicates on the Voldemort key-value store, and evaluate graph-based applications (Social Media Analysis / graph coloring, Weather Monitoring, and a synthetic Conjunctive workload) on AWS EC2 and a local lab network. They report that eventual consistency with monitoring improves aggregate throughput by 50–80% over sequential consistency, that monitor overhead is typically below 4%, that detection latency is small (over 99.9% of violations detected within 50 ms in regional tests), and that even after accounting for rollback the applications progress 10–20% (terminating) or 45–47% (non-terminating) faster than with sequential consistency. The paper claims this approach preserves the correctness/safety properties of the original sequentially consistent algorithm.

Significance. If the central claim were correct, the work would be a valuable practical option: applications that are correct only under sequential consistency could run on weaker, higher-performance consistency models without rewriting the application, provided the designer can supply a monitorable correctness predicate. The paper's strengths are its direct measurements rather than fitted parameters, the availability of source code and experimental data, and the explicit treatment of livelock mechanisms (backoff, task reordering, adaptive consistency). The reported throughput benefits, low monitor overhead, and prompt detection latencies are credible as experimental findings. However, the correctness claim is not established: for the flagship graph-coloring application, the monitored predicate P is only mutual exclusion on neighboring nodes, and under eventual consistency P can hold while a client performs a stale read that invalidates the output. The experiments measure throughput and progress but never validate the final coloring. Because the correctness claim is the paper's central contribution, the significance of the work is substantially undermined as presented.

major comments (3)
  1. [Sections 1, 5, and 7] The monitored predicate P for the graph applications is mutual exclusion on neighboring nodes: no two clients may simultaneously hold locks for adjacent nodes (Section 1 and Section 5). Under eventual consistency, this P does not imply correctness of graph coloring. A concrete scenario: client C2 colors node u, writes the new color, and releases the locks on the edge (u,v); client C1 then acquires those locks and performs a GET of u's color, but the replica it reads has not yet applied C2's color PUT. P holds because C1 and C2 are not concurrent lock holders, yet C1 may choose the same color as u's old color, producing an invalid edge. Crucially, the local predicate detectors intercept only PUT requests (Section 5, 'intercepting the PUT requests'), so stale reads are invisible to the monitor and can never trigger a rollback. The evaluation in Section 7 measures throughput and progress only; it never validates the final coloring against a known-correct result. Therefore the Conclusion's claim that the approach 'preserv[es] correctness/safety properties' is unsupported for the flagship application. This is not a minor gap: it invalidates the central correctness claim of the paper.
  2. [Section 6.1 and Algorithm 3] The rollback algorithm is safe only if every violation of P is detected before any involved client enters the write phase. The paper states this assumption explicitly ('if the detection of violation is quick then detection would occur before client C2 enters the write phase') and the rollback algorithm (Algorithm 3) aborts a task only if a violation notice is received during the read phase. If detection latency exceeds the read phase, C2's write has already been committed to the key-value store, Algorithm 3 lets C2 continue, and the incorrect value remains visible to subsequent tasks, which may build on it. The paper provides no argument that detection latency is always below the read-phase duration; the measured latencies in Section 7.6 (average 18 ms, worst 55 ms) are not compared with the read-phase times of the corresponding tasks. Since the Conclusion repeats this assumption as a premise of the developed rollback algorithm, it is a load-bearing limitation that needs to be proven or removed.
  3. [Section 5] The paper asserts that 'Since our algorithms are adapted from [12–14, 22], the correctness of our algorithms follow from those existing algorithms.' This is not a proof. The adaptation is nontrivial: candidates originate from servers rather than clients, carry HVC intervals, must handle multiple versions of the same key, and treat uncertain interval overlaps as concurrent to avoid missing violations. It is not immediate that the completeness and soundness properties of the original linear/semilinear predicate detection algorithms survive this translation. If the monitor can miss a P violation, the detect-rollback loop is unsound even before considering the stale-read issue. The paper should either provide a correctness argument for the adapted algorithms or clearly scope the claims to the implemented system.
minor comments (4)
  1. [Section 4] There is a typo in 'In [11], it authors have shown' — it should read 'the authors have shown'.
  2. [Section 7.4 and Table 4] The detection latency distribution in Table 4 has a long tail: six violations took between 10 and 17 seconds to detect. Given the quick-detection assumption in Section 6.1, the paper should report the task read-phase duration in those experiments so readers can assess whether the assumption was actually satisfied.
  3. [Table 3] Several 'server overhead' entries are slightly negative (e.g., -0.2% and -0.5%). The paper should state that these are within run-to-run variance, or provide confidence intervals for the reported throughput averages, since the claimed benefits are computed from three runs.
  4. [Section 7.5] In Figure 13, the curves labeled 'R1W1+reorder' and 'R1W1+rollback' do not terminate for Social Media Analysis; this is important context and should be mentioned explicitly in the caption or text, not only in the body.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all headline numbers are direct measurements and the monitor correctness is inherited from external prior work.

full rationale

The paper's central claims are empirical: the 50%-80% throughput increases, the <4% monitoring overhead, the detection-latency distributions, and the 10%-47% end-to-end progress improvements are all measured values from Voldemort deployments on AWS and a local lab network. No model parameter is fitted to a subset of the data and then renamed as a prediction; the benefit numbers are direct comparisons of measured throughput/progress between consistency configurations. The correctness of the predicate-detection module is explicitly imported from external, non-overlapping prior work: the paper states, "Since our algorithms are adapted from [12-14, 22], the correctness of our algorithms follow from those existing algorithms," referring to Garg and Chase's conjunctive/linear/semilinear predicate detection work, not to the present authors' own prior results. Self-citations are present but not load-bearing: Retroscope [11] is offered as one possible general rollback mechanism and is not used for the main measured results, and [33] is cited in the discussion of false positives rather than as the source of the framework's correctness. The rollback algorithm's safety depends on the explicitly stated assumption in Section 6.1 that "if the detection of violation is quick then detection would occur before client C2 enters the write phase"; this is a candid limitation and a correctness-risk item rather than a circular reduction. Similarly, the concern that the monitored mutual-exclusion predicate P may not be a sufficient correctness predicate for graph coloring under eventual consistency is a soundness gap in the claimed correctness preservation, but it is not a case where the paper derives Y from an X that is defined in terms of Y, nor a fitted-input-called-prediction, nor a self-citation chain. No equation or construction in the paper reduces its conclusions to its own inputs, so the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on the assumption that sequentially consistent algorithms can be run speculatively on an eventually consistent store with a monitorable predicate and quick rollback. The paper states these assumptions explicitly, and none are derived from first principles.

assumptions (5)
  • domain assumption The application algorithm is correct when executed under sequential consistency.
    The entire approach is premised on running such an algorithm and compensating for weaker consistency only through monitor and rollback; stated in the Introduction and Section 7.7.
  • domain assumption Monitoring mutual exclusion on neighboring nodes is sufficient for correctness of the graph applications.
    The paper assumes that if clients never update neighboring nodes concurrently, the distributed coloring and weather algorithms produce correct results; implicit in Sections 1 and 7.7.
  • ad hoc to paper All violations of P are detected before any involved client enters the write phase.
    Explicitly assumed in Section 6.1 and the Conclusion for the rollback algorithm; if detection is slow, the simple abort-and-restart recovery does not guarantee correctness.
  • domain assumption The application has exclusive access to its data.
    Stated in Section 7.7 as a condition for rollback to be suitable; if other applications read the data, rolling back is impossible.
  • standard math Correctness of the linear and semilinear predicate detection algorithms from Chase and Garg.
    The monitors are adapted from [13,14], and the paper states correctness follows from those algorithms without reproducing the proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Using Weaker Consistency Models with Monitoring and Recovery for Improving Performance of Key-Value Stores." pith.science (2026). https://pith.science/paper/UGPRA3NJ

@misc{pith2026190901980,
  author       = {Pith},
  title        = {Pith review of: Using Weaker Consistency Models with Monitoring and Recovery for Improving Performance of Key-Value Stores},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UGPRA3NJ}},
  note         = {Machine review of arXiv:1909.01980}
}
abstract

Consistency properties provided by most key-value stores can be classified into sequential consistency and eventual consistency. The former is easier to program with but suffers from lower performance whereas the latter suffers from potential anomalies while providing higher performance. We focus on the problem of what a designer should do if he/she has an algorithm that works correctly with sequential consistency but is faced with an underlying key-value store that provides a weaker consistency. We propose a detect-rollback based approach: The designer identifies a correctness predicate, say $P$, and continues to run the protocol, as our system monitors $P$. If $P$ is violated (because of weaker consistency), the system rolls back and resumes the computation at a state where $P$ holds. We evaluate this approach with graph-based applications running on the Voldemort key-value store. Our experiments with deployment on Amazon AWS EC2 instances shows that using eventual consistency with monitoring can provide a $50\%$ -- $80\%$ increase in throughput when compared with sequential consistency. We also observe that the overhead of the monitoring itself was low (typically less than $4\%$) and the latency of detecting violations was small. In particular, in a scenario designed to intentionally cause a large number of violations, more than $99.9\%$ of violations were detected in less than 50 milliseconds in regional networks, and in less than 3 seconds in global networks. We find that for some applications, frequent rollback can cause the program using eventual consistency to effectively \textit{stall}. We propose alternate mechanisms for dealing with re-occurring rollbacks. Overall, for applications considered in this paper, we find that even with rollback, eventual consistency provides better performance than using sequential consistency.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

67 extracted references · 59 canonical work pages

  1. [1]

    In: Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles

    DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., Vogels, W.: Dynamo: Amazon’s highly available key-value store. In: Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles. SOSP ’07, pp. 205–220. ACM, New York, NY, USA (2007). doi:10.1145/1294261.1294281

    arXiv 2007

  2. [2]

    In: Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing

    Brewer, E.A.: Towards robust distributed systems (abstract). In: Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing. PODC ’00, p. 7. ACM, New York, NY, USA (2000). doi:10.1145/343477.343502

    arXiv 2000

  3. [3]

    SIGACT News 33(2), 51–59 (2002)

    Gilbert, S., Lynch, N.: Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News 33(2), 51–59 (2002). doi:10.1145/564585.564601

    arXiv 2002

  4. [4]

    In: Proceedings of the ACM Symposium on Cloud Computing

    Du, J., Iorgulescu, C., Roy, A., Zwaenepoel, W.: Gentlerain: Cheap and scalable causal consistency with physical clocks. In: Proceedings of the ACM Symposium on Cloud Computing. SOCC ’14, pp. 4–1413. ACM, New York, NY, USA (2014). doi:10.1145/2670979.2670983

    arXiv 2014

  5. [5]

    In: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles

    Lloyd, W., Freedman, M.J., Kaminsky, M., Andersen, D.G.: Don’t settle for eventual: Scalable causal consistency for wide-area storage with cops. In: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. SOSP ’11, pp. 401–416. ACM, New York, NY, USA (2011). doi:10.1145/2043556.2043593

    arXiv 2011

  6. [6]

    In: 36th IEEE Symposium on Reliable Distributed Systems, SRDS 2017, Hongkong, China, September 26 - 29, 2017, pp

    Roohitavaf, M., Demirbas, M., Kulkarni, S.S.: Causalspartan: Causal consistency for distributed data stores using hybrid logical clocks. In: 36th IEEE Symposium on Reliable Distributed Systems, SRDS 2017, Hongkong, China, September 26 - 29, 2017, pp. 184–193 (2017)

    work page 2017

  7. [7]

    ACM SIGOPS Operating Systems Review 44(2), 35–40 (2010)

    Lakshman, A., Malik, P.: Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review 44(2), 35–40 (2010)

    work page 2010

  8. [8]

    http://www.project-voldemort.com/voldemort/quickstart.html

    Project Voldemort. http://www.project-voldemort.com/voldemort/quickstart.html. Accessed: 2019-07-14

    work page 2019

Show all 67 references
  1. [9]

    In: Proceedings of the 10th USENIX Conference on File and Storage Technologies, pp

    Sumbaly, R., Kreps, J., Gao, L., Feinberg, A., Soman, C., Shah, S.: Serving large-scale batch computed data with project voldemort. In: Proceedings of the 10th USENIX Conference on File and Storage Technologies, pp. 18–18 (2012). USENIX Association

    2012

  2. [10]

    In: Proceedings of the International Conference on Parallel Processing and Applied Mathematics-Revised Papers

    Brzezinski, J., Wawrzyniak, D.: Consistency requirements of peterson’s algorithm for mutual exclusion of N processes in a distributed shared memory system. In: Proceedings of the International Conference on Parallel Processing and Applied Mathematics-Revised Papers. PPAM ’01, ...

    2002

  3. [11]

    In: Distributed Computing Systems (ICDCS), 2017 IEEE 37th International Conference On, pp

    Charapko, A., Ailijiang, A., Demirbas, M., Kulkarni, S.: Retrospective lightweight distributed snapshots using loosely synchronized clocks. In: Distributed Computing Systems (ICDCS), 2017 IEEE 37th International Conference On, pp. 2061–2066 (2017). IEEE

    2017

  4. [12]

    Kluwer, Norwell, MA (1996)

    Garg, V.K.: Principles of Distributed Systems. Kluwer, Norwell, MA (1996)

    1996

  5. [13]

    In: Distributed Computing Systems, 1995., Proceedings of the 15th International Conference On, pp

    Garg, V.K., Chase, C.M.: Distributed algorithms for detecting conjunctive predicates. In: Distributed Computing Systems, 1995., Proceedings of the 15th International Conference On, pp. 423–430 (1995). IEEE

    1995

  6. [14]

    Distributed Computing 11(4), 191–201 (1998)

    Chase, C.M., Garg, V.K.: Detection of global predicates: Techniques and their limitations. Distributed Computing 11(4), 191–201 (1998)

    1998

  7. [15]

    doi:10.5281/zenodo.3338381

    Nguyen, D.: Supplementary dataset and source code for the paper ”Using Weaker Consistency Models with Monitoring and Recovery for Improving Performance of Key-Value Stores” (2019). doi:10.5281/zenodo.3338381. https://doi.org/10.5281/zenodo.3338381

    2019 doi

  8. [16]

    Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978). doi:10.1145/359545.359563

    1978

  9. [17]

    Distributed Computing 13(2), 85–98 (2000)

    Stoller, S.D.: Detecting global predicates in distributed systems with clocks. Distributed Computing 13(2), 85–98 (2000)

    2000

  10. [18]

    In: International Workshop on Distributed Algorithms, pp

    Marzullo, K., Neiger, G.: Detection of global state predicates. In: International Workshop on Distributed Algorithms, pp. 254–272 (1991). Springer

    1991

  11. [19]

    Fidge, C.J.: Timestamps in message-passing systems that preserve the partial ordering (1987)

    1987

  12. [20]

    Parallel and Distributed Algorithms 1(23), 215–226 (1989)

    Mattern, F.: Virtual time and global states of distributed systems. Parallel and Distributed Algorithms 1(23), 215–226 (1989)

    1989

  13. [21]

    In: Workshop on Large-Scale Distributed Systems and Middleware (LADIS) (2013)

    Demirbas, M., Kulkarni, S.: Beyond truetime: Using augmentedtime for improving google spanner. In: Workshop on Large-Scale Distributed Systems and Middleware (LADIS) (2013)

    2013

  14. [22]

    IEEE Transactions on Parallel and Distributed Systems 5(3), 299–307 (1994)

    Garg, V.K., Waldecker, B.: Detection of weak unstable predicates in distributed programs. IEEE Transactions on Parallel and Distributed Systems 5(3), 299–307 (1994)

    1994

  15. [24]

    In: Proc

    Bovy, C., Mertodimedjo, H., Hooghiemstra, G., Uijterwaal, H., Van Mieghem, P.: Analysis of end-to-end delay measurements in internet. In: Proc. of the Passive and Active Measurement Workshop-PAM, vol. 2002 (2002). sn

    2002

  16. [25]

    http://www

    NIST/SEMATECH e-Handbook of Statistical Methods. http://www. itl.nist.gov/div898/handbook/eda/section3/eda366b.htm. Accessed: 2019-07-14 (2013)

    2013

  17. [26]

    http://https://networkx.github.io/documentation/stable/

    Overview of NetworkX. http://https://networkx.github.io/documentation/stable/. Accessed: 2019-03-24

    2019

  18. [27]

    Springer, New York (2013)

    Raynal, M.: Distributed Algorithms for Message-passing Systems. Springer, New York (2013)

    2013

  19. [28]

    Procedia Computer Science 18, 1217–1225 (2013)

    Fjukstad, B., Bjørndalen, J.M., Anshus, O.: Embarrassingly distributed computing for symbiotic weather forecasts. Procedia Computer Science 18, 1217–1225 (2013)

    2013

  20. [29]

    In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, pp

    Prakash, R., Shivaratri, N.G., Singhal, M.: Distributed dynamic channel allocation for mobile computing. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 47–56 (1995). ACM

    1995

  21. [30]

    In: Proc

    N´ unez-Rodrıguez, Y., Xiao, H., Islam, K., Alsalih, W.: A distributed algorithm for computing voronoi diagram in the unit disk graph model. In: Proc. 20th Canadian Conference in Computational Geometry (CCCG’08), pp. 199–202 (2008)

    2008

  22. [31]

    In: High Performance Computer Architecture, 2007

    Ranger, C., Raghuraman, R., Penmetsa, A., Bradski, G., Kozyrakis, C.: Evaluating mapreduce for multi-core and multiprocessor systems. In: High Performance Computer Architecture, 2007. HPCA 2007. IEEE 13th International Symposium On, pp. 13–24 (2007). Ieee

    2007

  23. [32]

    In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp

    Blanas, S., Patel, J.M., Ercegovac, V., Rao, J., Shekita, E.J., Tian, Y.: A comparison of join algorithms for log processing in mapreduce. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 975–986 (2010). ACM

    2010

  24. [33]

    In: Runtime Verification, pp

    Yingchareonthawornchai, S., Nguyen, D., Valapil, V.T., Kulkarni, S.S., Demirbas, M.: Precision, recall, and sensitivity of monitoring partially synchronous distributed systems. In: Runtime Verification, pp. 20–30 (2016). Springer

    2016

  25. [34]

    ACM SIGOPS operating systems review 41(6), 205–220 (2007)

    DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., Vogels, W.: Dynamo: amazon’s highly available key-value store. ACM SIGOPS operating systems review 41(6), 205–220 (2007)

    2007

  26. [35]

    ACM Trans

    Chandy, K.M., Lamport, L.: Distributed snapshots: Determining global states of distributed systems. ACM Trans. Comput. Syst. 3(1), 63–75 (1985). doi:10.1145/214451.214456

    1985

  27. [36]

    In: International Conference on Foundations of Software Technology and Theoretical Computer Science, pp

    Garg, V.K., Waldecker, B.: Detection of unstable predicates in distributed programs. In: International Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 253–264 (1992). Springer

    1992

  28. [37]

    IEEE Transactions on Parallel and Distributed Systems 7(12), 1323–1333 (1996)

    Garg, V.K., Waldecker, B.: Detection of strong unstable predicates in distributed programs. IEEE Transactions on Parallel and Distributed Systems 7(12), 1323–1333 (1996)

    1996

  29. [38]

    In: Proceedings Hawaii International Conference on System Sciences HICSS95 (January 1995), IEEE Computer Society (1995)

    Garg, V.K., Chase, C.M., Mitchell, J.R., Kilgore, R.: Conjunctive predicate detection. In: Proceedings Hawaii International Conference on System Sciences HICSS95 (January 1995), IEEE Computer Society (1995). Citeseer

    1995

  30. [39]

    In: International Conference on Computer Aided Verification, pp

    Stoller, S.D., Unnikrishnan, L., Liu, Y.A.: Efficient detection of global properties in distributed systems using partial-order methods. In: International Conference on Computer Aided Verification, pp. 264–279 (2000). Springer

    2000

  31. [40]

    Distributed Computing 17(3), 251–277 (2005)

    Mittal, N., Garg, V.K.: Techniques and applications of computation slicing. Distributed Computing 17(3), 251–277 (2005)

    2005

  32. [41]

    Page 23 of 24 abstraction algorithm for online predicate detection

    Chauhan, H., Garg, V.K., Natarajan, A., Mittal, N.: A distributed Nguyen et al. Page 23 of 24 abstraction algorithm for online predicate detection. In: 2013 IEEE 32nd International Symposium on Reliable Distributed Systems, pp. 101–110 (2013). IEEE

    2013

  33. [42]

    In: Parallel and Distributed Systems (ICPADS), 2009 15th International Conference On, pp

    Wang, X., Mayo, J., Hembroff, G., Gao, C.: Detection of conjunctive stable predicates in dynamic systems. In: Parallel and Distributed Systems (ICPADS), 2009 15th International Conference On, pp. 828–835 (2009). IEEE

    2009

  34. [43]

    In: Parallel and Distributed Systems (ICPADS), 2010 IEEE 16th International Conference On, pp

    Wang, X., Mayo, J., Hembroff, G.C.: Detection of a weak conjunction of unstable predicates in dynamic systems. In: Parallel and Distributed Systems (ICPADS), 2010 IEEE 16th International Conference On, pp. 338–346 (2010). IEEE

    2010

  35. [44]

    In: Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma’ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers, pp

    Valapil, V.T., Kulkarni, S.S.: Biased clocks: A novel approach to improve the ability to perform predicate detection with O(1) clocks. In: Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma’ale HaHamisha, Israel, June 18-21, 2...

    2018

  36. [45]

    In: Runtime Verification - 17th International Conference, RV 2017, Seattle, WA, USA, September 13-16, 2017, Proceedings, pp

    Valapil, V.T., Yingchareonthawornchai, S., Kulkarni, S.S., Torng, E., Demirbas, M.: Monitoring partially synchronous distributed systems using SMT solvers. In: Runtime Verification - 17th International Conference, RV 2017, Seattle, WA, USA, September 13-16, 2017, Proceedings, p...

    2017

  37. [46]

    CoRR abs/1905.13064 (2019)

    Ramabaja, L.: The bloom clock. CoRR abs/1905.13064 (2019). 1905.13064

    2019 arXiv

  38. [47]

    https: //azure.microsoft.com/en-us/services/cosmos-db/?v=17.45b

    Azure Cosmos DB – Globally Distributed Database Service. https: //azure.microsoft.com/en-us/services/cosmos-db/?v=17.45b . Accessed: 2017-12-10

    2017

  39. [48]

    http://www

    Amazon DynamoDB – a Fast and Scalable NoSQL Database Service Designed for Internet Scale Applications. http://www. allthingsdistributed.com/2012/01/amazon-dynamodb.html. Accessed: 2017-12-10

    2012

  40. [49]

    : Spanner: Google’s globally distributed database

    Corbett, J.C., Dean, J., Epstein, M., Fikes, A., Frost, C., Furman, J.J., Ghemawat, S., Gubarev, A., Heiser, C., Hochschild, P., et al. : Spanner: Google’s globally distributed database. ACM Transactions on Computer Systems (TOCS) 31(3), 8 (2013)

    2013

  41. [51]

    : Tao: Facebook’s distributed data store for the social graph

    Bronson, N., Amsden, Z., Cabrera, G., Chakka, P., Dimov, P., Ding, H., Ferris, J., Giardullo, A., Kulkarni, S., Li, H.C., et al. : Tao: Facebook’s distributed data store for the social graph. In: USENIX Annual Technical Conference, pp. 49–60 (2013)

    2013

  42. [52]

    Proceedings of the VLDB Endowment 8(12), 1816–1827 (2015)

    Pelkonen, T., Franklin, S., Teller, J., Cavallaro, P., Huang, Q., Meza, J., Veeraraghavan, K.: Gorilla: A fast, scalable, in-memory time series database. Proceedings of the VLDB Endowment 8(12), 1816–1827 (2015)

    2015

  43. [53]

    In: 2018 IEEE 37th International Performance Computing and Communications Conference (IPCCC), pp

    Bisson, T., Chen, K., Choi, C., Balakrishnan, V., Kee, Y.: Crail-kv: A high-performance distributed key-value store leveraging native kv-ssds over nvme-of. In: 2018 IEEE 37th International Performance Computing and Communications Conference (IPCCC), pp. 1–8 (2018). doi:10.1109...

    2018

  44. [54]

    IEEE Data Eng

    Stuedi, P., Trivedi, A., Pfefferle, J., Stoica, R., Metzler, B., Ioannou, N., Koltsidas, I.: Crail: A high-performance I/O architecture for distributed data processing. IEEE Data Eng. Bull. 40(1), 38–49 (2017)

    2017

  45. [55]

    CoRR abs/1902.03305 (2019)

    Aldin, H.N.S., Deldari, H., Moattar, M.H., Ghods, M.R.: Consistency models in distributed systems: A survey on definitions, disciplines, challenges and applications. CoRR abs/1902.03305 (2019)

    2019 arXiv

  46. [56]

    CoRR abs/1905.11762 (2019)

    Kokocinski, M., Kobus, T., Wojciechowski, P.T.: On mixing eventual and strong consistency: Bayou revisited. CoRR abs/1905.11762 (2019)

    2019 arXiv

  47. [57]

    In: Proceedings of the 20th International Conference on Distributed Computing and Networking

    Sidhanta, S., Mukhopadhyay, S., Golab, W.: Consistify: Preserving correctness and sla under weak consistency. In: Proceedings of the 20th International Conference on Distributed Computing and Networking. ICDCN ’19, pp. 282–291. ACM, New York, NY, USA (2019). doi:10.1145/328859...

    2019

  48. [58]

    In: SoCC, pp

    Song, W., Gkountouvas, T., Birman, K., Chen, Q., Xiao, Z.: The freeze-frame file system. In: SoCC, pp. 307–320 (2016)

    2016

  49. [59]

    In: 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pp

    Devecsery, D., Chow, M., Dou, X., Flinn, J., Chen, P.M.: Eidetic systems. In: 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pp. 525–540 (2014)

    2014

  50. [60]

    In: Data Engineering (ICDE), 2016 IEEE 32nd International Conference On, pp

    Chirigati, F., Sim´ eon, J., Hirzel, M., Freire, J.: Virtual lightweight snapshots for consistent analytics in nosql stores. In: Data Engineering (ICDE), 2016 IEEE 32nd International Conference On, pp. 1310–1321 (2016). IEEE

    2016

  51. [61]

    Communications of the ACM 51(1), 107–113 (2008)

    Dean, J., Ghemawat, S.: Mapreduce: simplified data processing on large clusters. Communications of the ACM 51(1), 107–113 (2008)

    2008

  52. [62]

    : The dataflow model: a practical approach to balancing correctness, latency, and cost in massive-scale, unbounded, out-of-order data processing

    Akidau, T., Bradshaw, R., Chambers, C., Chernyak, S., Fern´ andez-Moctezuma, R.J., Lax, R., McVeety, S., Mills, D., Perry, F., Schmidt, E., et al. : The dataflow model: a practical approach to balancing correctness, latency, and cost in massive-scale, unbounded, out-of-order da...

    2015

  53. [63]

    In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp

    Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 135–146 (2010). ACM

    2010

  54. [64]

    Proceedings of the VLDB Endowment 5(8), 716–727 (2012)

    Low, Y., Bickson, D., Gonzalez, J., Guestrin, C., Kyrola, A., Hellerstein, J.M.: Distributed graphlab: a framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment 5(8), 716–727 (2012)

    2012

  55. [65]

    In: OSDI, vol

    Gonzalez, J.E., Xin, R.S., Dave, A., Crankshaw, D., Franklin, M.J., Stoica, I.: Graphx: Graph processing in a distributed dataflow framework. In: OSDI, vol. 14, pp. 599–613 (2014)

    2014

  56. [66]

    In: OSDI, vol

    Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., Guestrin, C.: Powergraph: distributed graph-parallel computation on natural graphs. In: OSDI, vol. 12, p. 2 (2012)

    2012

  57. [67]

    In: Proceedings of the 19th ACM Symposium on Operating Systems Principles 2003, SOSP 2003, Bolton Landing, NY, USA, October 19-22, 2003, pp

    Ghemawat, S., Gobioff, H., Leung, S.: The google file system. In: Proceedings of the 19th ACM Symposium on Operating Systems Principles 2003, SOSP 2003, Bolton Landing, NY, USA, October 19-22, 2003, pp. 29–43 (2003)

    2003

  58. [68]

    ACM Transactions on Computer Systems (TOCS) 26(2), 4 (2008)

    Chang, F., Dean, J., Ghemawat, S., Hsieh, W.C., Wallach, D.A., Burrows, M., Chandra, T., Fikes, A., Gruber, R.E.: Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS) 26(2), 4 (2008)

    2008

  59. [69]

    In: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, pp

    Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J., McCauley, M., Franklin, M.J., Shenker, S., Stoica, I.: Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In: Proceedings of the 9th USENIX Conference on Networked Systems Design ...

    2012

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.