Level: M1 – M2
Contact: Dietmar Berwanger (dwb@lmf.cnrs.fr) and Patricia Bouyer (bouyer@lmf.cnrs.fr)
Location: Laboratoire Méthodes Formelles, ENS Paris-Saclay
Keywords: Distributed synthesis, signalling, automata theory, imperfect information
Description
In distributed systems, control actions are often executed by a single component, but the information needed to make these decisions is dispersed across the system. This internship focuses on the synthesis of signalling strategies, where the objective is not to coordinate multiple control agents but to ensure that information is effectively transmitted within the system.
We consider settings where a single output process is responsible for acting based on inputs observed by one or more sender processes. Due to bandwidth limitations in the communication channels, it is not possible to transmit the entire input verbatim. Instead, the senders must encode the relevant information into signals that the receiver can decode to make correct decisions.
The project will investigate which system architectures admit effective synthesis of such strategies using finite-state implementations. The intern will gain exposure to foundational methods from automata theory and infinite games with imperfect information.
→ Download the full internship description (PDF)
References
[1] Shaull Almagor, Denis Kuperberg, and Orna Kupferman. Regular sensing. FSTTCS 2014.
[2] Dietmar Berwanger and Laurent Doyen. Observation and distinction. Theory of Computing Systems, 2023.
[3] Patricia Bouyer. Games on graphs with a public signal monitoring. FoSSaCS 2018.
[4] P. Madhusudan and P. S. Thiagarajan. Distributed controller synthesis for local specifications. ICALP 2001.