pith. sign in

arxiv: 1907.06250 · v1 · pith:IIU2I6K3new · submitted 2019-07-14 · 💻 cs.DB · cs.DC

Delivery, consistency, and determinism: rethinking guarantees in distributed stream processing

Artem Trofimov , Igor E. Kuralenok , Nikita Marshalkin , Boris Novikov This is my paper

Pith reviewed 2026-05-24 21:32 UTC · model grok-4.3

classification 💻 cs.DB cs.DC
keywords distributed stream processingexactly-oncedeterminismconsistencydelivery guaranteesperformance overhead
0
0 comments X

The pith

Delivery, consistency, and determinism are tightly connected in distributed stream processing, enabling exactly-once guarantees via lightweight determinism with minimal overhead.

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

The paper introduces a formal framework for defining guarantees in stream processing systems more precisely. It demonstrates that delivery, consistency, and determinism are interconnected properties. Using this connection, the authors show that lightweight determinism can deliver exactly-once processing without the usual performance costs. Experiments indicate this approach outperforms existing industrial solutions.

Core claim

We introduce a formal framework that allows us to define streaming guarantees more regularly. We demonstrate that the properties of delivery, consistency, and determinism are tightly connected within distributed stream processing. We also show that having lightweight determinism, it is possible to provide exactly-once with almost no performance overhead. Experiments show that the proposed approach can significantly outperform alternative industrial solutions.

What carries the argument

The formal framework that redefines streaming guarantees by linking delivery, consistency, and determinism properties.

Load-bearing premise

The formal framework accurately models all relevant properties of real distributed stream processing systems.

What would settle it

A deployment where the proposed lightweight determinism approach incurs significant performance overhead or fails to maintain exactly-once guarantees under failures would disprove the claim.

Figures

Figures reproduced from arXiv: 1907.06250 by Artem Trofimov, Boris Novikov, Igor E. Kuralenok, Nikita Marshalkin.

Figure 2
Figure 2. Figure 2: The scheme of Theorem 1 Theorem 1. If D contains non-commutative transformation and has the following dependencies for some aτ ∈ Γ: (i) x ∈ ClD(aτ ), y ∈ ClD(aτ ) (ii) ((x, y), s) ∈ D through a non-commutative operation (iii) bτ1 , bτ2 ∈ ClD(s), τ1 < τ2 then non-deterministic system supports exactly-once if and only if: G = ClD(bτ1 ) ∩ C −1 D (bτ2 ) ∀(u, v) ∈ D, u ∈ ClD(s) : v ⊂ G ⇒ u ⊂ G (1) Proof Sketch.… view at source ↗
Figure 3
Figure 3. Figure 3: Strong productions mechanism Such behavior is also called effective determinism [23] because computations become deterministic until the persistent storage is cleared. Strong productions method guarantees that even if many possible results of a non-commutative operation may be obtained due to races, only one of them is computed and saved. The price for such exactly-once enforcement is an overhead on extern… view at source ↗
Figure 4
Figure 4. Figure 4: Micro-batching and transactional approach [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The overview of an architecture for drifting state implementation [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: State snapshotting protocol in Apache Flink [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: State snapshotting protocol in a deterministic system [PITH_FULL_IMAGE:figures/full_fig_p009_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The inverted index pipeline We choose the problem of an inverted index maintenance because it satisfies the following properties: • Operation that generates change records is non￾commutative • The computational workflow contains network shuffle that can violate the ordering constraints • Consistency guarantees are strongly required because the inconsistent index does not make sense for many applications • … view at source ↗
Figure 9
Figure 9. Figure 9: The latencies of FlameStream during three artificially reproduced [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: FlameStream and Flink latencies with 50ms between checkpoints [PITH_FULL_IMAGE:figures/full_fig_p011_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: FlameStream and Flink latencies with 500ms between checkpoints [PITH_FULL_IMAGE:figures/full_fig_p011_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: FlameStream and Flink latencies with 1000ms between checkpoints [PITH_FULL_IMAGE:figures/full_fig_p011_12.png] view at source ↗
read the original abstract

Consistency requirements for state-of-the-art stream processing systems are defined in terms of delivery guarantees. Exactly-once is the strongest one and the most desirable for end-user. However, there are several issues regarding this concept. Commonly used techniques that enforce exactly-once produce significant performance overhead. Besides, the notion of exactly-once is not formally defined and does not capture all properties that provide stream processing systems supporting this guarantee. In this paper, we introduce a formal framework that allows us to define streaming guarantees more regularly. We demonstrate that the properties of delivery, consistency, and determinism are tightly connected within distributed stream processing. We also show that having lightweight determinism, it is possible to provide exactly-once with almost no performance overhead. Experiments show that the proposed approach can significantly outperform alternative industrial solutions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces a formal framework for defining guarantees in distributed stream processing systems. It demonstrates that delivery, consistency, and determinism are tightly interconnected, and shows that lightweight determinism enables exactly-once semantics with negligible performance overhead. Experiments indicate that the proposed approach significantly outperforms alternative industrial solutions.

Significance. If the framework and results hold, the work offers a more rigorous basis for reasoning about streaming guarantees and a practical path to strong consistency at low cost. The formal linkage of the three properties and the empirical demonstration of low-overhead exactly-once processing are the primary contributions; the explicit generalization caveats noted in the manuscript strengthen the assessment.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'define streaming guarantees more regularly' is likely intended as 'more rigorously'; this should be corrected for precision.
  2. [Experiments] The experimental section would benefit from explicit discussion of how the tested workloads relate to the assumptions of the formal framework (e.g., failure models and network conditions).
  3. [Formal Framework] Notation for the formal definitions could be clarified with a small glossary or running example to aid readers unfamiliar with the specific stream-processing model.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work, the recognition of the formal framework linking delivery, consistency, and determinism, and the recommendation for minor revision. The report accurately captures the core contributions regarding lightweight determinism for exactly-once semantics with low overhead.

Circularity Check

0 steps flagged

No significant circularity; new framework is self-contained

full rationale

The paper introduces a novel formal framework to redefine streaming guarantees, explicitly linking delivery, consistency, and determinism without reducing any core claim to a fitted parameter, self-citation chain, or definitional tautology. The abstract and skeptic analysis confirm the framework is presented as newly introduced, with experimental overhead numbers obtained under stated assumptions rather than by construction. No load-bearing step matches any enumerated circularity pattern; the derivation chain remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on abstract; no free parameters, axioms, or invented entities are specified or invoked.

pith-pipeline@v0.9.0 · 5671 in / 1056 out tokens · 23891 ms · 2026-05-24T21:32:12.327456+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Mapreduce: Simplified data processing on large clusters,

    J. Dean and S. Ghemawat, “Mapreduce: Simplified data processing on large clusters,” Commun. ACM, vol. 51, no. 1, pp. 107–113, Jan. 2008. [Online]. Available: http://doi.acm.org/10.1145/1327452.1327492

    work page doi:10.1145/1327452.1327492 2008

  2. [2]

    [Online]

    (2017, Oct.) Apache hadoop. [Online]. Available: http://hadoop.apache. org/

    work page 2017

  3. [3]

    Apache spark: A unified engine for big data processing,

    M. Zaharia, R. S. Xin, P. Wendell, T. Das, M. Armbrust, A. Dave, X. Meng, J. Rosen, S. Venkataraman, M. J. Franklin, A. Ghodsi, J. Gonzalez, S. Shenker, and I. Stoica, “Apache spark: A unified engine for big data processing,” Commun. ACM , vol. 59, no. 11, pp. 56–65, Oct. 2016

    work page 2016

  4. [4]

    Apache hadoop goes realtime at facebook,

    D. Borthakur, J. Gray, J. S. Sarma, K. Muthukkaruppan, N. Spiegelberg, H. Kuang, K. Ranganathan, D. Molkov, A. Menon, S. Rash et al. , “Apache hadoop goes realtime at facebook,” in Proc. of the 2011 ACM SIGMOD Intnl. Conf. on Management of data . ACM, 2011, pp. 1071– 1080

    work page 2011

  5. [5]

    A survey of large-scale analytical query processing in mapreduce,

    C. Doulkeridis and K. Norvaag, “A survey of large-scale analytical query processing in mapreduce,” The VLDB Journal , vol. 23, no. 3, pp. 355– 380, Jun. 2014

    work page 2014

  6. [6]

    Apache flink: Stream and batch processing in a single engine,

    P. Carbone, A. Katsifodimos, S. Ewen, V . Markl, S. Haridi, and K. Tzoumas, “Apache flink: Stream and batch processing in a single engine,” Bulletin of the IEEE Computer Society Technical Committee on Data Engineering , vol. 36, no. 4, 2015

    work page 2015

  7. [7]

    Samza: Stateful scalable stream process- ing at linkedin,

    S. A. Noghabi, K. Paramasivam, Y . Pan, N. Ramesh, J. Bringhurst, I. Gupta, and R. H. Campbell, “Samza: Stateful scalable stream process- ing at linkedin,” Proc. VLDB Endow. , vol. 10, no. 12, pp. 1634–1645, Aug. 2017

    work page 2017

  8. [8]

    [Online]

    (2017, Oct.) Apache storm. [Online]. Available: http://storm.apache.org/

    work page 2017

  9. [9]

    Discretized streams: An efficient and fault-tolerant model for stream processing on large clusters,

    M. Zaharia, T. Das, H. Li, S. Shenker, and I. Stoica, “Discretized streams: An efficient and fault-tolerant model for stream processing on large clusters,” in Proc. of the 4th USENIX Conf. on Hot Topics in Cloud Ccomputing , ser. HotCloud’12. Berkeley, CA, USA: USENIX Association, 2012, pp. 10–10

    work page 2012

  10. [10]

    Millwheel: Fault- tolerant stream processing at internet scale,

    T. Akidau, A. Balikov, K. Bekiro ˘glu, S. Chernyak, J. Haberman, R. Lax, S. McVeety, D. Mills, P. Nordstrom, and S. Whittle, “Millwheel: Fault- tolerant stream processing at internet scale,” Proc. VLDB, vol. 6, no. 11, pp. 1033–1044, Aug. 2013

    work page 2013

  11. [11]

    [Online]

    (2018, Mar.) Trident. [Online]. Available: http://storm.apache.org/ releases/current/Trident-tutorial.html

    work page 2018

  12. [12]

    Benchmarking streaming computation engines: Storm, flink and spark streaming,

    S. Chintapalli, D. Dagit, B. Evans, R. Farivar, T. Graves, M. Holder- baugh, Z. Liu, K. Nusbaum, K. Patil, B. J. Peng, and P. Poulosky, “Benchmarking streaming computation engines: Storm, flink and spark streaming,” in 2016 IEEE Intnl. Parallel and Distributed Processing Symposium Workshops (IPDPSW), May 2016, pp. 1789–1792

    work page 2016

  13. [13]

    Benchmarking modern dis- tributed streaming platforms,

    S. Qian, G. Wu, J. Huang, and T. Das, “Benchmarking modern dis- tributed streaming platforms,” in 2016 IEEE International Conference on Industrial Technology (ICIT) , March 2016, pp. 592–598

    work page 2016

  14. [14]

    Exactly once is not exactly the same,

    “Exactly once is not exactly the same,” https://streaml.io/blog/ exactly-once, 2017, accessed: 2018-10-08

    work page 2017

  15. [15]

    Exactly-once or not, atomic broadcast is still impossible in kafka - or anywhere,

    “Exactly-once or not, atomic broadcast is still impossible in kafka - or anywhere,” https://www.the-paper-trail.org/post/ 2017-07-28-exactly-not-atomic-broadcast-still-impossible-kafka/, 2017, accessed: 2018-10-08

    work page 2017

  16. [16]

    Maximizing determinism in stream processing under latency constraints,

    N. Zacheilas, V . Kalogeraki, Y . Nikolakopoulos, V . Gulisano, M. Papatri- antafilou, and P. Tsigas, “Maximizing determinism in stream processing under latency constraints,” in Proc. of the 11th ACM Intnl. Conf. on Distributed and Event-based Systems , ser. DEBS ’17. New York, NY , USA: ACM, 2017, pp. 112–123

    work page 2017

  17. [17]

    The 8 requirements of real-time stream processing,

    M. Stonebraker, U. C ¸ etintemel, and S. Zdonik, “The 8 requirements of real-time stream processing,” SIGMOD Rec., vol. 34, no. 4, pp. 42–47, Dec. 2005

    work page 2005

  18. [18]

    De- terministic model for distributed speculative stream processing,

    I. E. Kuralenok, A. Trofimov, N. Marshalkin, and B. Novikov, “De- terministic model for distributed speculative stream processing,” in Ad- vances in Databases and Information Systems, A. Bencz´ur, B. Thalheim, and T. Horv ´ath, Eds. Cham: Springer International Publishing, 2018, pp. 233–246

    work page 2018

  19. [19]

    Weikum and G

    G. Weikum and G. V ossen, Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery . Morgan Kaufmann, 2002

    work page 2002

  20. [20]

    Distributed snapshots: Determining global states of distributed systems,

    K. M. Chandy and L. Lamport, “Distributed snapshots: Determining global states of distributed systems,” ACM Trans. Comput. Syst. , vol. 3, no. 1, pp. 63–75, Feb. 1985. [Online]. Available: http: //doi.acm.org/10.1145/214451.214456

    work page doi:10.1145/214451.214456 1985

  21. [21]

    Lightweight Asynchronous Snapshots for Distributed Dataflows,

    P. Carbone, G. F ´ora, S. Ewen, S. Haridi, and K. Tzoumas, “Lightweight Asynchronous Snapshots for Distributed Dataflows,” ArXiv e-prints, Jun. 2015

    work page 2015

  22. [22]

    State management in apache flink&reg;: Consistent stateful distributed stream processing,

    P. Carbone, S. Ewen, G. F ´ora, S. Haridi, S. Richter, and K. Tzoumas, “State management in apache flink&reg;: Consistent stateful distributed stream processing,” Proc. VLDB, vol. 10, no. 12, pp. 1718–1729, Aug. 2017

    work page 2017

  23. [23]

    Akidau, S

    T. Akidau, S. Chernyak, and R. Lax, Streaming Systems: The What, Where, When, and how of Large-scale Data Processing . ” O’Reilly Media, Inc.”, 2018

    work page 2018

  24. [24]

    Flamestream: Model and runtime for distributed stream processing,

    I. E. Kuralenok, A. Trofimov, N. Marshalkin, and B. Novikov, “Flamestream: Model and runtime for distributed stream processing,” in Proceedings of the 5th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond , ser. BeyondMR’18. New York, NY , USA: ACM, 2018, pp. 8:1–8:2. [Online]. Available: http://doi.acm.org/10.1145/3206333.3209273

    work page doi:10.1145/3206333.3209273 2018

  25. [25]

    An optimistic approach to handle out-of-order events within analytical stream processing,

    I. Kuralenok, N. Marshalkin, A. Trofimov, and B. Novikov, “An optimistic approach to handle out-of-order events within analytical stream processing,” in Third Conference on Software Engineering and Information Management (SEIM-2018) (full papers) , ser. CEUR Workshop Proceedings, Y . Litvinov, M. Akhin, B. Novikov, and V . Itsykson, Eds., no. 2135, Aachen,...

    work page 2018

  26. [26]

    Failure detectors for large-scale distributed systems,

    N. Hayashibara, A. Cherif, and T. Katayama, “Failure detectors for large-scale distributed systems,” in 21st IEEE Symposium on Reliable Distributed Systems, 2002. Proceedings. IEEE, 2002, pp. 404–409

    work page 2002

  27. [27]

    [Online]

    (2018, Mar.) Rocksdb. [Online]. Available: http://rocksdb.org/

    work page 2018

  28. [28]

    Benchmarking streaming computation engines: Storm, flink and spark streaming,

    S. Chintapalli, D. Dagit, B. Evans, R. Farivar, T. Graves, M. Holder- baugh, Z. Liu, K. Nusbaum, K. Patil, B. J. Peng, and P. Poulosky, “Benchmarking streaming computation engines: Storm, flink and spark streaming,” in 2016 IEEE Intnl. Parallel and Distributed Processing Symp. Workshops (IPDPSW), May 2016, pp. 1789–1792

    work page 2016

  29. [29]

    Aurora: A new model and architecture for data stream management,

    D. J. Abadi, D. Carney, U. C ¸ etintemel, M. Cherniack, C. Convey, S. Lee, M. Stonebraker, N. Tatbul, and S. Zdonik, “Aurora: A new model and architecture for data stream management,” The VLDB Journal , vol. 12, no. 2, pp. 120–139, Aug. 2003

    work page 2003

  30. [30]

    The design of the borealis stream processing engine,

    D. J. Abadi, Y . Ahmad, M. Balazinska, U. C ¸ etintemel, M. Cherniack, J. Hwang, W. Lindner, A. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y . Xing, and S. B. Zdonik, “The design of the borealis stream processing engine,” in CIDR 2005, Second Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4-7, 2005, Online Proceedings . ...

    work page 2005

  31. [31]

    Twitter heron: Stream processing at scale,

    S. Kulkarni, N. Bhagat, M. Fu, V . Kedigehalli, C. Kellogg, S. Mittal, J. M. Patel, K. Ramasamy, and S. Taneja, “Twitter heron: Stream processing at scale,” in Proc. of the 2015 ACM SIGMOD Intnl. Conf. on Management of Data, ser. SIGMOD ’15. New York, NY , USA: ACM, 2015, pp. 239–250

    work page 2015

  32. [32]

    Interfaces for stream processing systems,

    R. Alur, K. Mamouras, C. Stanford, and V . Tannen, “Interfaces for stream processing systems,” in Principles of Modeling. Springer, 2018, pp. 38–60

    work page 2018

  33. [33]

    A formalization of complex event stream processing,

    S. Hall ´e and S. Varvaressos, “A formalization of complex event stream processing,” in 2014 IEEE 18th International Enterprise Distributed Object Computing Conference . IEEE, 2014, pp. 2–11

    work page 2014

  34. [34]

    Lars: A logic-based framework for analytic reasoning over streams,

    H. Beck, M. Dao-Tran, and T. Eiter, “Lars: A logic-based framework for analytic reasoning over streams,” Artificial Intelligence, vol. 261, pp. 16–70, 2018

    work page 2018