PODS 2021: Keynote Talk
Synchronization Schemas
Speaker: Rajeev Alur (University of Pennsylvania)
Abstract
We present a type-theoretic framework for data stream processing for real-time decision making, where the desired computation involves a mix of sequential computation, such as smoothing and detection of peaks and surges, and naturally parallel computation, such as relational operations, key-based partitioning, and map-reduce. To unify sequential (ordered) and relational (unordered) data models, we define synchronization schemas as types and series-parallel streams (SPS) as objects of these types. A synchronization schema imposes a hierarchical structure over relational types that succinctly captures ordering and synchronization requirements among different kinds of data items. Series-parallel streams naturally model objects such as relations, sequences, sequences of relations, sets of streams indexed by key values, time-based and event-based windows, and more complex structures obtained by nesting of these. We introduce series-parallel stream transformers (SPST) as a domain-specific language for modular specification of deterministic transformations over such streams. SPSTs provably specify only monotonic transformations allowing streamability, have a modular structure that can be exploited for correct parallel implementation, and are composable allowing specification of complex queries as a pipeline of transformations. We conclude by discussing research directions for both theory and practice of distributed stream processing.
Joint work with Phillip Hilliard, Zack Ives, Konstantinos Kallas, Kostas Mamouras, Filip Niksic, Caleb Stanford, Val Tannen, and Anton Xue.
Bio
Rajeev Alur is Zisman Family Professor of Computer and Information Science at University of Pennsylvania. He obtained his bachelor's degree from IIT Kanpur and PhD from Stanford University. His research is focused on formal methods for system design. He is a Fellow of the AAAS, a Fellow of the ACM, a Fellow of the IEEE, an Alfred P. Sloan Faculty Fellow, and a Simons Investigator. His research has won many awards including the inaugural Alonzo Church award for outstanding contributions to logic and computation. He is the author of the textbook Principles of Cyber-Physical Systems (MIT Press, 2015).
