Synthesising Asynchronous Automata from Fair Specifications
Béatrice Bérard, Benjamin Monmege, B Srivathsan, Arnab Sur · 2025
Read Synthesising Asynchronous Automata from Fair Specifications by Béatrice Bérard, Benjamin Monmege, B Srivathsan, Arnab Sur (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-14623.txt.
Introduction
Béatrice Bérard, Benjamin Monmege, Srivathsan, and Arnab Sur revisit how to build asynchronous automata from fair specifications. Their 2025 paper deals with distributed finite state processes that synchronize on shared actions.
A classic result by Zielonka shows how to synthesize such an automaton from a global specification and a split of the alphabet among processes. That translation is complex and lacks a complete tool. The authors restrict attention to fair specifications, in which every process acts in each loop, so none is starved. For this class they give a new construction. Each process ends with a number of local states that grows only linearly.
Catalog record
| CREATOR | Béatrice Bérard, Benjamin Monmege, B Srivathsan, Arnab Sur |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 112 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-14623
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Synthesising Asynchronous Automata from Fair Specifications Béatrice Bérard, Benjamin Monmege, B Srivathsan, Arnab Sur Abstract Asynchronous automata are a model of distributed finite state processes synchronising on shared actions. A celebrated result by Zielonka shows how a deterministic asynchronous automaton (AA) can be synthesised, starting from two inputs: a global specification given as a deterministic finite-state automaton (DFA) and a distribution of the alphabet into local alphabets for each process. The DFA to AA translation is particularly complex and has been revisited several times, with no complete prototype tool provided for the full construction. In this work, we revisit this construction on a restricted class of “fair” specifications: a DFA describes a fair specification if in every loop, all processes participate in at least one action — so, no process is starved. For fair specifications, we present a new construction to synthesise an AA. Our construction results in an AA where every process has a number of local states that is linear in the number of states of the DFA, and where the only exponential explosion is related to a fairness parameter: the length of the longest word that can be read in the DFA in which not every process participates. We have implemented a prototype tool showing how it can be applied to some examples, in particular a concrete one: the dining philosophers problem. Finally, we show how this construction can be combined with an existing construction for hierarchical process architectures, in order to relax the fairness assumption. 1 Introduction Asynchronous automata (AA) are a foundational model for distributed systems, where independent processes synchronise on shared actions. These models enable the design and analysis of systems with decentralised control, making them critical in theoretical computer science and applications like parallel computing and distributed algorithms. Figure 1 gives an example (from [ 17 ] ) of an AA. 0 1 2 a a c c p_{1} 0 1 2 b b c c p_{2} 0,0 0,1 0,2 1,0 1,1 1,2 2,0 2,1 2,2 b b b b b b a a a a a a c c Figure 1: Left: An AA. Right: its semantics seen as a DFA It contains two processes p_{1} , p_{2} which control letters \{a,c\} and \{b,c\} respectively: so a is local to p_{1} , b is local to p_{2} , and c is shared by p_{1} and p_{2} . The key point is the synchronisation mechanism on shared actions. Here, the AA is defined in a way that the two red-dashed c transitions can synchronise, as well as the two blue c transitions. However, the red-dashed c in one cannot be done together with the blue c of the other. The behaviour of the AA is described as a deterministic finite-state automaton (DFA) on the right. The language of this AA is (([ab]+[aabb]).c)^{*} where [ab] stands for either ab or ba , and [aabb] denotes the set of words obtained by shuffling two a ’s and two b ’s. From an AA, it is straightforward to construct a language-equivalent DFA, as shown in the example. The reverse process — that is, given a DFA (global specification), construct a language-equivalent AA (distributed implementation) — is highly non-trivial. A cornerstone result is Zielonka’s theorem, which provides a method for synthesising a (deterministic) AA from a given DFA, and an alphabet distribution among processes [ 20 ] . However, Zielonka’s construction is known to be extremely complex and has been the subject of numerous refinements and optimisations (e.g. [ 7 , 16 , 11 ] ), leading to an optimal Zielonka-type construction [ 10 ] . In all these constructions, each process keeps track of what it believes to be the latest “information” available to every other process. When there is a shared action, the processes share their local information, reconcile them and update their local states. This underlying idea is implemented using a gossip automaton in [ 16 , 17 ] , and so-called zones in [ 11 , 10 ] . This idea yields a number of local states that is exponential in the number of processes (whereas the construction can be kept polynomial in the number of states of the DFA). Several solutions have been considered in order to avoid the resolution of this gossip problem . For instance, compositional methods have been used in order to construct non-deterministic AA [ 5 , 18 , 4 ] , still requiring a number of states exponential in the number of processes. Another solution, leading to a quadratic number of states, is to restrict the topology of communications to be acyclic, and with any letter synchronising at most two processes [ 13 ] . This special case has recently been extended to remove the restriction on the number of processes synchronising on each letter, and to allow for a reconfiguration of the topology along the executions [ 12 ] . Another recent work [ 1 ] has proposed a logic-based route for Zielonka’s theorem by going through a local, past-oriented fragment of propositional dynamic logic. The AA is obtained by a cascade product of localised AA, which essentially operate on a single process. Our goal in this work is to find a “meaningful” restriction on the DFA specifications which can result in a conceptually simpler and more efficient AA synthesis, that can be implemented in a prototype tool. Indeed, there are very few attempts of implementations of the synthesis algorithm based on Zielonka’s theorem, partly due to its intricacy. The work of [ 19 ] proposes a notion of safe asynchronous automata and states that the problem of synthesizing a safe AA whose language is contained in a DFA specification is undecidable. They go on to study syntactic conditions on DFAs which make them equivalent to safe AA and then propose a method to find sub-automata inside the DFA specification that satisfy these conditions. From such sub-automata, safe AA are synthesized using a modified Zielonka’s procedure, which is implemented and experimented. Another implementation has been proposed in [ 2 ] for a fragment of asynchronous automata that are called realistic , that is both deadend-free and locally accepting. Both studies define restrictions on the DFA specification which are orthogonal to those we consider. In this article, we revisit AA synthesis with a focus on fair specifications. As an example, consider the dining philosophers problem, introduced in [ 9 ] . The problem is modeled for n philosophers (the processes), sitting around a table with a single chopstick lying between two consecutive philosophers. A philosopher’s actions (picking up/putting down the left/right chopstick) are shared actions, involving the philosopher and its two neighbors. The description of the authorised sequence of actions, as well as the objective for all philosophers to eat (i.e. have both chopsticks at some point in the future, before releasing them), can be given as a DFA where each state stores the current status of each philosopher. One of the objectives is to design a distributed algorithm to avoid deadlock situations (where nothing else can be done), and the starvation of any of the philosophers. In our setting, we want to design an AA where every philosopher eats infinitely often, which is traditionally called fairness