Synthesis of Distributed Synchronous Systems

The problem of distributed synthesis is to automatically generate a distributed algorithm, given a target communication network and a specification of the algorithm’s correct behavior. In this talk, I will first present the work that has been done since 1992 in order to solve the problem for static networks with an a priori fixed message size. I will show where the undecidability comes from, and when it is possible to obtain decidability results. Then I will present a recent work on synthesis of distributed systems with dynamic links. In fact, the classical approach has two shortcomings: Recent work in distributed computing is shifting towards dynamically changing communication networks rather than static ones, and an important class of distributed algorithms are so-called full-information protocols, where nodes piggy-pack previously received messages onto current messages. I will hence consider the synthesis problem for a system of two nodes communicating in rounds over a dynamic link whose message size is not bounded and show a necessary and sufficient condition for decidability of the problem.

Authors

• Nathalie Sznajder

Keywords

No keywords are indexed for this paper.