Formalization of Timely Dataflow's Progress Tracking Protocol

Matthias Brun, Sára Decova, Andrea Lattuada 🌐 and Dmitriy Traytel 🌐

April 13, 2021

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

Large-scale stream processing systems often follow the dataflow paradigm, which enforces a program structure that exposes a high degree of parallelism. The Timely Dataflow distributed system supports expressive cyclic dataflows for which it offers low-latency data- and pipeline-parallel stream processing. To achieve high expressiveness and performance, Timely Dataflow uses an intricate distributed protocol for tracking the computation’s progress. We formalize this progress tracking protocol and verify its safety. Our formalization is described in detail in our forthcoming ITP'21 paper.

License

BSD License

Topics

Session Progress_Tracking

Depends on

Cite

× 
@article{Progress_Tracking-AFP,
  author  = {Matthias Brun and Sára Decova and Andrea Lattuada and Dmitriy Traytel},
  title   = {Formalization of Timely Dataflow's Progress Tracking Protocol},
  journal = {Archive of Formal Proofs},
  month   = {April},
  year    = {2021},
  note    = {\url{https://isa-afp.org/entries/Progress_Tracking.html},
             Formal proof development},
  ISSN    = {2150-914x},
}
Download

Download

× Download latest

Older releases: