arXiv:1605.00928v4 Announce Type: replace Abstract: Distributed Stream Processing Engines (DSPEs) target applications related to continuous computation, online machine learning and real-time query processing. DSPEs operate on high volume of data by applying lightweight operations on real-time and continuous streams. Such systems require clusters of hundreds of machines for their deployment. Streaming applications come with various requirements, i.e., low-latency, high throughput, scalability and high availability. In this survey, we study the fault tolerance problem for DSPEs. We discuss fault tolerance techniques that are used in stream processing engines that were state of the art at the time of writing (2016), namely S4, Storm, Flink, Spark Streaming, Samza and MillWheel. Further, we give insight on fault tolerance approaches that we categorize as active replication, passive replication and upstream backup. Finally, we discuss implications of the fault tolerance techniques for different streaming application requirements. This revised version corrects errors in the original 2016 manuscript, summarizes later developments in Flink and Spark, discusses durable logs and archival storage for replay, and points to more recent surveys.