Trustworthy Information Processing

We propose to bring together two historically disjoint lines of research: the epistemic analysis of distributed systems on the one hand, which aims at understanding the evolution of the knowledge of the components of a distributed system; and reactive synthesis, which aims at constructing such systems automatically from a formal specification given as a formula of a temporal logic. 

Reactive synthesis has the potential to revolutionize the development of distributed systems. From a given logical specification, the synthesis algorithm automatically constructs an implementation that is correct-by-design. This allows the developer to focus on “what” the system should do instead of “how” it should be done. There has been a lot of success in the last years in synthesizing individual components of a distributed system. However, the complete synthesis of distributed protocols is, with currently available methods, far too expensive for practical applications. 

Recent advances in the study of knowledge in distributed systems, such as the Knowledge of Preconditions principle, offer a path to significantly improve the situation. Our vision is a new class of synthesis algorithms that gainfully use this potential by constructing the distributed protocol in terms of the evolving knowledge of the components rather than the low-level evolution of the states. 

We bring to the project complementing skills and expertise in the two respective fields. The proposed project will begin by carrying out a study on epistemic arguments for the correctness of existing distributed protocols. The goal is to develop a formalization of these arguments in the form of a diagrammatic proof that can be verified automatically. We will then develop systematic methods for the construction of such proofs, based on insights like the Knowledge of Preconditions principle. Finally, we will integrate our formalization of epistemic proofs into a synthesis algorithm that automatically constructs such a proof for a given specification, and then translates the proof into an actual implementation. 

Funding Body

Funding Body

GIF Research Grant Regular Program

The central role of information technology in all aspects of our private and professional lives has led to a fundamental change in the type of program properties we care about. Up to now, the focus has been on functional correctness; in the future, requirements that reflect our societal values, like privacy, fairness, The central role of information technology in all aspects of our private and professional lives has led to a fundamental change in the type of program properties we care about. Up to now, the focus has been on functional correctness; in the future, requirements that reflect our societal values, like privacy, fairness, and explainability will be far more important. These properties belong to the class of hyperproperties, which represent sets of sets of execution traces and can therefore specify the relationship between different computations of a reactive system. Previous work has focussed on individual hyperproperties like noninterference or restricted classes such as k-hypersafety; this project sets out to develop a unified theory for general hyperproperties. We will develop a formal specification language and effective algorithms for logical reasoning, verification, and program synthesis. The central idea is to use the type and alternation structure of the logical quantifiers, ranging from classic firstorder and second-order quantification to quantifiers over rich data domains and quantitative operators for statistical analysis, as the fundamental structure that partitions the broad concept of hyperproperties into specific property classes; each particular class is then supported by algorithms that provide a uniform solution for all the properties within the class. The project will bring the analysis of hyperproperties to the level of traditional notions of safety and reliability, and provide a rigorous foundation for the debate about standards for privacy, fairness, and explainability that future software-based systems will be measured against.