Distributed program creation depends on communication patterns
Distributed LTL Synthesis under Arbitrary Message Adversaries
Distributed, Parallel, and Cluster ComputingFormal Languages and Automata TheoryLogic in Computer Science
Summary
Creating programs that react correctly in a distributed system is tricky when messages between parts may be lost. This paper finds that deciding whether such a program can exist is impossible in many scenarios, even when some messages always get through. The researchers describe exactly which communication patterns allow deciding this and provide a method to build correct programs when it is possible. They also reveal a surprising connection between being able to reach agreement quickly and being able to synthesize these programs.
What this means in practice
- •For distributed system engineers: Understand exactly which message loss patterns allow creating guaranteed-correct distributed reactive programs.
- •For network protocol designers: Use the results to decide when coordination tasks can be implemented under varying unreliable communication scenarios.
A theory result. No direct application yet.
Authors
Benedikt Bollig, Patricia Bouyer-Decitre, Matthias Függer, Dhrubajyoti Ghosh, Thomas Nowak, Nathalie Sznajder
Abstract
Reactive synthesis is the problem of generating a program that produces outputs satisfying a logical specification for every input stream. We study distributed synthesis for two processes communicating in rounds over unreliable links, with at least one message delivered in every round. Despite this delivery guarantee, we show that synthesis from linear temporal logic specifications is undecidable, even when messages carry the processes' complete causal histories. More generally, we give a complete characterization of the communication restrictions that make synthesis decidable. Restrictions are described by a message adversary $A$, a set of allowed infinite graph histories: sequences of communication graphs, each specifying which messages are delivered in a round. Iterated chromatic subdivision associates these histories with points in the unit interval, yielding an image $π(A) \subseteq [0,1]$. For every $ω$-regular message adversary $A$, synthesis is decidable if and only if $π(A)$ is nowhere dense. In the decidable cases, our procedure takes a deterministic parity automaton for $A$ and a specification, decides realizability, and constructs a realizing distributed algorithm whenever one exists. Further, our topological arguments shed new light on the fundamental requirements of synthesis. They show that, for $ω$-regular message adversaries, synthesis is decidable if and only if consensus is repeatedly solvable in bounded time. This links two previously unrelated problems from formal verification and distributed computing through the processes' uncertainty about communication.