pith. sign in

arxiv: 2305.01425 · v5 · submitted 2023-05-02 · 💻 cs.FL

Adding Reconfiguration to Zielonka's Asynchronous Automata

Mathieu Lehaut (University of Gothenburg) , Nir Piterman (University of Gothenburg) This is my paper

Pith reviewed 2026-05-24 09:07 UTC · model grok-4.3

classification 💻 cs.FL
keywords asynchronous automatareconfigurationZielonka automataexpressive powerdistributed systemscommunication disseminationfixed automata
0
0 comments X

The pith

Reconfigurable asynchronous automata accept exactly the same languages as fixed ones, but any fixed equivalent must broadcast every communication to all processes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that adding the ability for processes to dynamically change communication partners in Zielonka-style asynchronous automata does not increase the class of languages they can recognize. Translations are given in both directions between the reconfigurable and fixed models. The direction from reconfigurable to fixed requires that every communication event is sent to every process so that the fixed automaton can simulate the changing neighborhoods. A concrete language is exhibited for which this global dissemination is unavoidable: in any fixed automaton accepting the language, each process must either receive information about every communication or play no role in acceptance.

Core claim

Reconfigurable asynchronous automata are not more expressive than fixed asynchronous automata. Translations exist from reconfigurable to fixed and back, but the reconfigurable-to-fixed translation requires disseminating communication and knowledge to all processes in the system. This dissemination is unavoidable, shown by a language accepted by a reconfigurable automaton such that in every equivalent fixed automaton every process must either be aware of all communication or be irrelevant.

What carries the argument

The pair of translations between reconfigurable and fixed asynchronous automata, where the reconfigurable-to-fixed translation uses global dissemination of all communication events to every process.

If this is right

  • Any language accepted by a reconfigurable automaton is also accepted by some fixed automaton.
  • Any fixed automaton simulating a reconfigurable one must make every communication event visible to every process.
  • There exist languages for which no fixed automaton can accept them unless every process tracks the entire communication history.
  • Processes that remain unaware of some communications can be made irrelevant without changing the accepted language.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Designers of distributed protocols may prefer reconfiguration for locality during execution even though the final expressive power remains the same.
  • The cost of simulation suggests that verification algorithms for reconfigurable systems could exploit the fixed-model translation only when global knowledge is acceptable.
  • The result separates the benefit of dynamic neighborhoods from any gain in computational power, pointing to efficiency or robustness questions left open.

Load-bearing premise

The acceptance condition and communication semantics of the reconfigurable model can be faithfully simulated by a fixed automaton whose processes receive global dissemination of all communication events.

What would settle it

A language accepted by some reconfigurable automaton but not by any fixed automaton in which every process either receives all communication events or is irrelevant.

Figures

Figures reproduced from arXiv: 2305.01425 by Mathieu Lehaut (University of Gothenburg), Nir Piterman (University of Gothenburg).

Figure 1
Figure 1. Figure 1: An asynchronous automaton B over three processes. 2.1.2. Asynchronous Automata. An asynchronous automaton (in short: AA) [Zie87] over distributed alphabet (Σ, dom) and processes P is a tuple B = ((Sp)p∈P,(s 0 p )p∈P,(δa)a∈Σ, Acc) such that: • Sp is the finite set of states for process p, and s 0 p ∈ Sp is its initial state, • δa : Q p∈dom(a) Sp → Q p∈dom(a) Sp is a partial transition function for letter a … view at source ↗
Figure 2
Figure 2. Figure 2: An RAA A over three processes. The listening function is given to the right of each state. 3.1. Fixed AA to Reconfigurable AA. Let (Σ, dom) be a distributed alphabet, and let B be an AA over it. One can construct an RAA A∥P with Σ as set of channels that recognizes the same language as B. The intuition is as follows. The listening function of each process is the same for all states: each process always lis… view at source ↗
Figure 3
Figure 3. Figure 3: On the left, the RAA from Example 2. On the right, its translation to an AA. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of how the order on the channels in D is maintained. We consider the case where D = {1, . . . , n} and pi is in charge of channel i. The order between the channels is the natural order on {1, . . . , n}. The black token indicates the current state for each process. Transitions that are on the same channel are connected with a dashed line. The system is set up for next communication on channel … view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of how the set D and the switching channel sc change whenever there is a communication on sc. We consider the case where there are three processes and four channels. Each column corresponds to the status after one more communication on sc. Each channel is in turn the switching channel starting with 4. The channels in D at a certain time/column are marked with a black box. We cycle through the … view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of the switching RAA for n = 2. channel (3, i.e. the previous switching channel), while q keeps its old assigned channel. After enough changes of the switching channel, the state cycles back to the initial state for both. Let A be the parallel composition of (Ap). A state for one process keeps track of 3 channels and one set of channels, so its size is in O(n 3 .2 n ). Therefore, the size of t… view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of the second construction for [PITH_FULL_IMAGE:figures/full_fig_p018_7.png] view at source ↗
read the original abstract

We study an extension of Zielonka's (fixed) asynchronous automata called reconfigurable asynchronous automata where processes can dynamically change who they communicate with. We show that reconfigurable asynchronous automata are not more expressive than fixed asynchronous automata by giving translations from one to the other. However, going from reconfigurable to fixed comes at the cost of disseminating communication (and knowledge) to all processes in the system. We then show that this is unavoidable by describing a language accepted by a reconfigurable automaton such that in every equivalent fixed automaton, every process must either be aware of all communication or be irrelevant.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces reconfigurable asynchronous automata as an extension of Zielonka's fixed asynchronous automata, allowing processes to dynamically change communication partners. It claims to show that reconfigurable automata are not more expressive than fixed ones via explicit translations between the models. The translation from reconfigurable to fixed automata incurs the cost of global dissemination of all communication events (and knowledge) to every process. This cost is shown to be unavoidable by exhibiting a language accepted by a reconfigurable automaton such that any equivalent fixed automaton requires every process to either be aware of all communications or be irrelevant.

Significance. If the translations and unavoidability argument are correct, the result clarifies the expressive power of reconfiguration in asynchronous automata and identifies a concrete cost in terms of dissemination. The explicit constructions and the language witnessing unavoidability are strengths, as they provide a direct equivalence proof and a falsifiable example. This could inform models of dynamic distributed systems in automata theory and concurrency.

minor comments (3)
  1. The abstract states the existence of translations and the language but provides no proof sketches or key definitions; the main body should include a high-level outline of the translation construction (e.g., how local states and transitions are preserved under asynchrony) for readability.
  2. Notation for 'dissemination' and 'irrelevance' should be introduced with a small running example early in the paper to make the unavoidability claim easier to follow.
  3. Ensure all references to Zielonka's original model include precise citations and clarify any differences in acceptance conditions between the fixed and reconfigurable variants.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the paper, recognition of its strengths in providing explicit translations and a witnessing language, and recommendation for minor revision. We are pleased that the core results on equivalence with dissemination cost and unavoidability are viewed as clarifying the role of reconfiguration.

Circularity Check

0 steps flagged

No significant circularity; direct constructions establish equivalence

full rationale

The paper establishes equivalence via explicit translations from reconfigurable to fixed asynchronous automata (with global dissemination) and a concrete witnessing language showing dissemination is forced. These are self-contained proof constructions that do not reduce to fitted parameters, self-citations, or definitional renaming. The central claim is the existence of the translations and the lower-bound language, both presented as direct arguments without load-bearing reliance on prior author results or internal fits. This matches the default case of a non-circular theoretical equivalence proof.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions of asynchronous automata and language acceptance from prior literature; introduces no free parameters, no new axioms beyond standard automata theory, and no invented entities.

axioms (1)
  • standard math Standard definitions and acceptance conditions of Zielonka's asynchronous automata as background
    The entire development builds directly on the fixed asynchronous automata model from the literature.

pith-pipeline@v0.9.0 · 5624 in / 1172 out tokens · 24955 ms · 2026-05-24T09:07:40.057233+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    A calculus for collective-adaptive systems and its behavioural theory

    Yehia Abd Alrahman, Rocco De Nicola, and Michele Loreti. A calculus for collective-adaptive systems and its behavioural theory. Inf. Comput. , 268, 2019. https://doi.org/10.1016/j.ic.2019.104457 doi:10.1016/j.ic.2019.104457

    work page doi:10.1016/j.ic.2019.104457 2019

  2. [2]

    Modelling and verification of reconfigurable multi-agent systems

    Yehia Abd Alrahman and Nir Piterman. Modelling and verification of reconfigurable multi-agent systems. Auton. Agents Multi Agent Syst. , 35(2):47, 2021. https://doi.org/10.1007/s10458-021-09521-x doi:10.1007/s10458-021-09521-x

    work page doi:10.1007/s10458-021-09521-x 2021

  3. [3]

    On the expressive power of polyadic synchronisation in pi-calculus

    Marco Carbone and Sergio Maffeis. On the expressive power of polyadic synchronisation in pi-calculus. Nord. J. Comput. , 10(2):70--98, 2003

    work page 2003

  4. [4]

    Luca Cardelli and Andrew D. Gordon. Mobile ambients. Theor. Comput. Sci. , 240(1):177--213, 2000. https://doi.org/10.1016/S0304-3975(99)00231-5 doi:10.1016/S0304-3975(99)00231-5

    work page doi:10.1016/s0304-3975(99)00231-5 2000

  5. [5]

    de Boer and Catuscia Palamidessi

    Frank S. de Boer and Catuscia Palamidessi. Embedding as a tool for language comparison. Inf. Comput. , 108(1):128--157, 1994. https://doi.org/10.1006/inco.1994.1004 doi:10.1006/inco.1994.1004

    work page doi:10.1006/inco.1994.1004 1994

  6. [6]

    Towards a unified approach to encodability and separation results for process calculi

    Daniele Gorla. Towards a unified approach to encodability and separation results for process calculi. Inf. Comput. , 208(9):1031--1053, 2010. https://doi.org/10.1016/j.ic.2010.05.002 doi:10.1016/j.ic.2010.05.002

    work page doi:10.1016/j.ic.2010.05.002 2010

  7. [7]

    Uhrmacher

    Mathias John, C \' e dric Lhoussaine, Joachim Niehren, and Adelinde M. Uhrmacher. The attributed pi calculus. In 6th International Conference on Computational Methods in Systems Biology , volume 5307 of Lecture Notes in Computer Science , pages 83--102. Springer, 2008. https://doi.org/10.1007/978-3-540-88562-7\_10 doi:10.1007/978-3-540-88562-7\_10

    work page doi:10.1007/978-3-540-88562-7 2008

  8. [8]

    Translating pi-calculus into LOTOS NT

    Radu Mateescu and Gwen Sala \" u n. Translating pi-calculus into LOTOS NT . In 8th International Conference on Integrated Formal Methods , volume 6396 of Lecture Notes in Computer Science , pages 229--244. Springer, 2010. https://doi.org/10.1007/978-3-642-16265-7\_17 doi:10.1007/978-3-642-16265-7\_17

    work page doi:10.1007/978-3-642-16265-7 2010

  9. [9]

    A calculus of mobile processes, I

    Robin Milner, Joachim Parrow, and David Walker. A calculus of mobile processes, I . Inf. Comput. , 100(1):1--40, 1992. https://doi.org/10.1016/0890-5401(92)90008-4 doi:10.1016/0890-5401(92)90008-4

    work page doi:10.1016/0890-5401(92)90008-4 1992

  10. [10]

    A calculus of mobile processes, II

    Robin Milner, Joachim Parrow, and David Walker. A calculus of mobile processes, II . Inf. Comput. , 100(1):41--77, 1992. https://doi.org/10.1016/0890-5401(92)90009-5 doi:10.1016/0890-5401(92)90009-5

    work page doi:10.1016/0890-5401(92)90009-5 1992

  11. [11]

    A formal approach to autonomic systems programming: The SCEL language

    Rocco De Nicola, Michele Loreti, Rosario Pugliese, and Francesco Tiezzi. A formal approach to autonomic systems programming: The SCEL language. ACM Trans. Auton. Adapt. Syst. , 9(2):7:1--7:29, 2014. https://doi.org/10.1145/2619998 doi:10.1145/2619998

    work page doi:10.1145/2619998 2014

  12. [12]

    Comparing the expressiveness of the \( \) -calculus and CCS

    Rob van Glabbeek. Comparing the expressiveness of the \( \) -calculus and CCS . In Ilya Sergey, editor, Programming Languages and Systems - 31st European Symposium on Programming, ESOP 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Munich, Germany, April 2-7, 2022, Proceedings , volume 13240 of Lecture...

    work page doi:10.1007/978-3-030-99336-8 2022

  13. [13]

    Notes on finite asynchronous automata

    Wieslaw Zielonka. Notes on finite asynchronous automata. RAIRO Theor. Informatics Appl. , 21(2):99--135, 1987. https://doi.org/10.1051/ita/1987210200991 doi:10.1051/ita/1987210200991

    work page doi:10.1051/ita/1987210200991 1987