Pôle Modèles Distributed Computing

Contact: Matthias Függer

We are working on topics from distributed systems, studying their properties and fundamental limitations both from a theoretical and application-oriented perspective.

An incomplete list of current research questions we address in this group is

• Distributed biological systems. Analyzing and designing the dynamics of natural and synthetic biological systems.
• Automated synthesis of distributed systems. Given a specification and a communication model, generate a distributed algorithm that complies with the specification in the given model.
• Distributed games. Multiple agents collaborating or competing against an environment to maximize their payoff.
• Distributed AI. AI to synthesize distributed systems.
• Runtime verification. Monitoring a system during execution to detect anomalies.

People

Faculty

Thibaut Balabonski

Maître de conférences

Université Paris-Saclay

URL

Dietmar Berwanger

CNRS

URL

Benedikt Bollig

CNRS

URL

Patricia Bouyer-Decitre

Directrice de recherche

CNRS

URL

Thomas Chatain

Maître de conférences

ENS Paris-Saclay

URL

Sylvain Conchon

Professeur

Université Paris-Saclay

URL

Alain Finkel

Professeur

ENS Paris-Saclay

URL

Laurent Fribourg

CNRS

URL

Matthias Fuegger

Chercheur

CNRS

URL

Stéphane Le Roux

Maître de conférences

ENS Paris-Saclay

URL

Thomas Nowak

ENS Paris-Saclay

URL

Stefan Schwoon

Maître de conférences

ENS Paris-Saclay

URL

Mihaela Sighireanu

ENS Paris-Saclay

URL

Lina Ye

Maître de conférences

CentraleSupélec

URL

Fatiha Zaidi

Professeur

Université Paris-Saclay

URL

Emeriti

Philippe Dague

Professeur

Université Paris-Saclay

URL

Paul Gastin

Professeur

ENS Paris-Saclay

URL

Serge Haddad

Professeur

ENS Paris-Saclay

URL

Postdocs

PhD students

Publications

The group's publications can be accessed via https://hal.science/LMF-CDS. Recent publications are listed below.

2024

• Thomas Nowak, Ulrich Schmid, Kyrill Winkler: Topological Characterization of Consensus in Distributed Systems, Journal of the ACM (JACM), 2024.
• Lélia Blin, Gabriel Le Bouder, Franck Petit: Optimal Memory Requirement for Self-Stabilizing Token Circulation, Structural Information and Communication Complexity (SIROCCO 2024), 2024.

2023

• Alain Finkel, Etienne Lozes: Synchronizability of Communicating Finite State Machines is not Decidable, Logical Methods in Computer Science, 2023.
• Sylvain Conchon, Alexandrina Korneva: The Cubicle Fuzzy Loop: A Fuzzing-Based Extension for the Cubicle Model Checker, SEFM 2023 - Software Engineering and Formal Methods, 2023.
• Hagit Attiya, Armando Castañeda, Thomas Nowak: Topological Characterization of Task Solvability in General Models of Computation, 37th International Symposium on Distributed Computing (DISC 2023), 2023.
• Dietmar Berwanger, Laurent Doyen, Thomas Soullard: Synthesising Full-Information Protocols, 2023.
• Nick Würdemann, Thomas Chatain, Stefan Haar: Taking Complete Finite Prefixes To High Level\, Symbolically (Full Version), Petri Nets 2023 - 44TH International Conference on Applications and Theory of Petri Nets and Concurrency, 2023.

2022

• Amrita Suresh: Formal Verification of Communicating Automata,Vérification formelle des automates communicants, 2022.
• Béatrice Bérard, Benedikt Bollig, Patricia Bouyer, Matthias Függer, Nathalie Sznajder: Synthesis in presence of dynamic links, Information and Computation, 2022.
• Neha Rino, Thomas Chatain: Timed Alignments with Mixed Moves, 2022.
• Thomas Chatain, Neha Rino: Timed Alignments, 2022 4th International Conference on Process Mining (ICPM), 2022.
• Giann Karlo Aguirre-Samboní, Stefan Haar, Loïc Paulevé, Stefan Schwoon, Nick Würdemann: Avoid One's Doom: Finding Cliff-Edge Configurations in Petri Nets, GandALF 2022 - Games, Automata, Logics, and Formal Verification, 2022.
• Lulu He, Philippe Dague, Lina Ye: Using Delay Blocks to Make Non-Diagnosable Discrete Event Systems Diagnosable, DX 2022 - 33rd International Workshop on Principle of Diagnosis, 2022.
• Bharat Adsul, Paul Gastin, Saptarshi Sarkar, Pascal Weil: Propositional Dynamic Logic and Asynchronous Cascade Decompositions for Regular Trace Languages, 33rd International Conference on Concurrency Theory (CONCUR 2022), 2022.
• Giann Karlo Aguirre-Samboní, Cédric Gaucherel, Stefan Haar, Franck Pommereau: Reset Petri Net Unfolding Semantics for Ecosystem Hypergraphs, PNSE 2023 - International Workshop on Petri Nets and Software Engineering, 2022.
• Bharat Adsul, Paul Gastin, Saptarshi Sarkar, Pascal Weil: Asynchronous wreath product and cascade decompositions for concurrent behaviours, Logical Methods in Computer Science, 2022.
• Thomas Chatain, Maurice Comlan, David Delfieu, Loïg Jezequel, Olivier Henri Roux: Pomset bisimulation and unfolding for reset Petri nets, Information and Computation, 2022.
• Igor Khmelnitsky: Verification of Infinite-State Systems and Machine Learning,Vérification de systèmes infinis et apprentissage automatique, 2022.
• Alain Finkel, Serge Haddad, Igor Khmelnitsky: Coverability\, Termination\, and Finiteness in Recursive Petri Nets, Fundamenta Informaticae, 2022.
• Matthias Függer, Attila Kinali, Christoph Lenzen, Ben Wiederhake: Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022.

2021

• Thibaut Balabonski, Pierre Courtieu, Robin Pelle, Lionel Rieg, Sébastien Tixeuil, Xavier Urbain: Computer Aided Formal Design of Swarm Robotics Algorithms, Stabilization, Safety, and Security of Distributed Systems. SSS 2021, 2021.
• Mathilde Boltenhagen, Thomas Chatain, Josep Carmona: An A*-Algorithm for Computing Discounted Anti-Alignments in Process Mining, 3rd International Conference on Process Mining, 2021.
• Matthias Függer, Thomas Nowak, Manfred Schwarz: Tight Bounds for Asymptotic and Approximate Consensus, Journal of the ACM (JACM), 2021.
• Mathilde Boltenhagen: Partitionnement d’instances de processus basé sur les techniques de conformité de modèles,Process Instance Clustering Based on Conformance Checking Artefacts, 2021.
• Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, Quentin Soubeyran: Distributed computation with continual population growth, Distributed Computing, 2021.
• Anirban Majumdar: Vérification et synthèse de systèmes concurrents paramétrés,Verification and synthesis of parameterized concurrent systems, 2021.
• Mathilde Boltenhagen, Thomas Chatain, Josep Carmona: A Discounted Cost Function for Fast Alignments of Business Processes, BPM 2021 - 19th International Conference on Business Process Management, 2021.
• Benedikt Bollig, Cinzia Di Giusto, Alain Finkel, Laetitia Laversa, Etienne Lozes, Amrita Suresh: A Unifying Framework for Deciding Synchronizability, CONCUR 2021 - 32nd International Conference on Concurrency Theory, 2021.
• Juraj Kolcak: Dépliages et interprétation abstraite pour réseaux de régulation biologiques paramétrés,Unfoldings and Abstract Interpretation for Parametric Biological Regulatory Networks, 2021.
• Serge Haddad, Didier Lime, Olivier H Roux: A Turn-Based Approach for Qualitative Time Concurrent Games, PETRI NETS 2021 - 42nd International Conference on Applications and Theory of Petri Nets and Concurrency, 2021.
• Thomas Chatain, Mathilde Boltenhagen, Josep Carmona: Anti-Alignments -- Measuring The Precision of Process Models and Event Logs, Information Systems, 2021.
• Wolfgang Dür, Matthias Függer, Andreas Steininger: Generation of a fault-tolerant clock through redundant crystal oscillators, Microelectronics Reliability, 2021.
• Nathalie Bertrand, Patricia Bouyer, Anirban Majumdar: Reconfiguration and Message Losses in Parameterized Broadcast Networks, Logical Methods in Computer Science, 2021.
• Sylvain Conchon, Giorgio Delzanno, Angelo Ferrando: Declarative Parameterized Verification of Distributed Protocols via the Cubicle Model Checker, Fundamenta Informaticae, 2021.
• Benedikt Bollig, Marie Fortin, Paul Gastin: Communicating finite-state machines\, first-order logic\, and star-free propositional dynamic logic, Journal of Computer and System Sciences, 2021.
• Thibaut Balabonski, Pierre Courtieu, Robin Pelle, Lionel Rieg, Sébastien Tixeuil, Xavier Urbain: Computer Aided Formal Design of Swarm Robotics Algorithms, 2021.
• Mathilde Boltenhagen, Thomas Chatain, Josep Carmona: Optimized SAT encoding of conformance checking artefacts, Computing, 2021.
• Alain Finkel, Serge Haddad, Igor Khmelnitsky: Commodification of accelerations for the Karp and Miller Construction., Discrete Event Dynamic Systems, 2021.
• Sylvain Conchon, Alexandrina Korneva, Çagdas Bozman, Mohamed Iguernlala, Alain Mebsout: Formally Documenting Tenderbake, Open Access Series in Informatics, 2021.
• Thibaut Balabonski, Pierre Courtieu, Robin Pelle, Lionel Rieg, Sébastien Tixeuil, Xavier Urbain: Comment s'assurer de garder le contact (et nos distances), ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, 2021.

2020

• Mathieu Lehaut: Synthesis for parameterized systems,Synthèse pour les systèmes paramétrés, 2020.
• Stefan Haar, Serge Haddad, Stefan Schwoon, Lina Ye: Active Prediction for Discrete Event Systems, FSTTCS 2020 - 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020.
• Wenbo Zhou, Philippe Dague, Lei Liu, Lina Ye, Fatiha Zaïdi: A Coloured Petri Nets Based Attack Tolerance Framework, 27th Asia-Pacific Software Engineering Conference (APSEC 2020), 2020.
• Nathalie Bertrand, Serge Haddad, Engel Lefaucheux: Diagnosis and Degradation Control for Probabilistic Systems, Discrete Event Dynamic Systems, 2020.
• Safouan Taha, Burkhart Wolff, Lina Ye: Philosophers may Dine - Definitively!, Integrated Formal Methods, 2020.
• Mathilde Boltenhagen, Thomas Chatain, Josep Carmona: Model-based trace variant analysis of event logs, Information Systems, 2020.
• Johannes Bund, Matthias Függer, Christoph Lenzen, Moti Medina: Synchronizer-free Digital Link Controller, IEEE Transactions on Circuits and Systems I: Regular Papers, 2020.
• Béatrice Bérard, Benedikt Bollig, Patricia Bouyer, Matthias Függer, Nathalie Sznajder: Synthesis in Presence of Dynamic Links, GandALF'20 - 11th International Symposium on Games, Automata, Logics, and Formal Verification, 2020.
• Sani Mohammadreza Fani, Mathilde Boltenhagen, Aalst Wil van Der: Prototype Selection using Clustering and Conformance Metrics for Process Discovery, BPI’20 - 16th International Workshop on Business Process Intelligence, 2020.
• Serge Haddad, Igor Khmelnitsky: Dynamic Recursive Petri Nets, PETRI NETS 2020 - 41st International Conference on Application and Theory of Petri Nets and Concurrency, 2020.
• Johannes Bund, Matthias Függer, Christoph Lenzen, Moti Medina, Will Rosenbaum: PALS: Plesiochronous and Locally Synchronous Systems, ASYNC 2020 - 26th IEEE International Symposium on Asynchronous Circuits and Systems, 2020.
• Alain Finkel, Serge Haddad, Igor Khmelnitsky: Minimal Coverability Tree Construction Made Complete and Efficient, FoSSaCS 2020 - 23rd International Conference on Foundations of Software Science and Computation Structures, 2020.
• Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, Quentin Soubeyran: Distributed Computation with Continual Population Growth, DISC 2020 - 34th International Symposium on DIStributed Computing, 2020.
• Matthias Függer, Thomas Nowak, Kyrill Winkler: On the Radius of Nonsplit Graphs and Information Dissemination in Dynamic Networks, Discrete Applied Mathematics, 2020.
• Thomas Chatain, Stefan Haar, Juraj Kolčák, Loïc Paulevé, Aalok Thakkar: Concurrency in Boolean networks, Natural Computing, 2020.

2019

• Jérôme Leroux, M. Praveen, Philippe Schnoebelen, Grégoire Sutre: On Functions Weakly Computable by Pushdown Petri Nets and Related Systems, Logical Methods in Computer Science, 2019.
• Wil M.P. van Der Aalst, Josep Carmona, Thomas Chatain, Boudewijn F. van Dongen: A Tour in Process Mining: From Practice to Algorithmic Challenges, LNCS Transactions on Petri Nets and Other Models of Concurrency, 2019.
• Alain Finkel, Ekanshdeep Gupta: The Well Structured Problem for Presburger Counter Machines, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2019.
• Nathalie Bertrand, Serge Haddad, Engel Lefaucheux: A Tale of Two Diagnoses in Probabilistic Systems, Information and Computation, 2019.
• Lina Ye, Philippe Dague, Lulu He: Manifestability Verification of Discrete Event Systems, DX 2019 - 30th International Workshop on Principles of Diagnosis, 2019.
• Sylvain Conchon, Alexandrina Korneva, Fatiha Zaïdi: Verifying Smart Contracts with Cubicle, FM 2019 International Workshops, 2019.
• Hugues Mandon, Cui Su, Stefan Haar, Jun Pang, Loïc Paulevé: Sequential Reprogramming of Boolean Networks Made Practical, CMSB 2019 - 17th International Conference on Computational Methods in Systems Biology, 2019.
• Daniele Zonetti, Adnane Saoud, Antoine Girard, Laurent Fribourg: Decentralized monotonicity-based voltage control of DC microgrids with ZIP loads, NecSys 2019 - 8th IFAC Workshop on Distributed Estimation and Control in Networked Systems, 2019.
• Mathilde Boltenhagen, Thomas Chatain, Josep Carmona: Encoding Conformance Checking Artefacts in SAT, BPI 2019 - 15th International Workshop on Business Process Intelligence, 2019.
• Nathalie Bertrand, Patricia Bouyer, Anirban Majumdar: Reconfiguration and message losses in parameterized broadcast networks, CONCUR 2019 - 30th International Conference on Concurrency Theory, 2019.
• Daniel Ohlinger, Jürgen Maier, Matthias Függer, Ulrich Schmid: The Involution Tool for Accurate Digital Timingand Power Analysis, PATMOS 2019 - 29th International Symposium on Power and Timing Modeling, Optimization and Simulation, 2019.
• Daniele Zonetti, Adnane Saoud, Antoine Girard, Laurent Fribourg: A symbolic approach to voltage stability and power sharing in time-varying DC microgrids, ECC 2019 - European control conference, 2019.
• Alain Finkel, Serge Haddad, Igor Khmelnitsky: Coverability and Termination in Recursive Petri Nets,Couverture et Terminaison dans les réseaux de Petri Récursifs, Petri Nets 2019 / ACSD 2019 - 40th International Conference on Application and Theory of Petri Nets and Concurrency, 2019.
• Mathilde Boltenhagen, Thomas Chatain, Josep Carmona: Generalized Alignment-Based Trace Clustering of Process Behavior, Petri Nets 2019 / ACSD 2019 - 40th International Conference on Application and Theory of Petri Nets and Concurrency, 2019.
• Benedikt Bollig, Patricia Bouyer, Fabian Reiter: Identifiers in Registers, 22nd International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'19), 2019.

2018

• Adnane Saoud, Antoine Girard, Laurent Fribourg: Contract Based Design of Symbolic Controllers for Interconnected Multiperiodic Sampled-Data Systems, 57th IEEE Conference on Decision and Control (CDC 2018), 2018.
• Béatrice Bérard, Stefan Haar, Loïc Hélouët: Hyper Partial Order Logic, FSTTCS 2018 - Foundations of Software Technology and Theoretical Computer Science, 2018.
• Adrien Le Coënt, Julien Alexandre Dit Sandretto, Alexandre Chapoutot, Laurent Fribourg: An improved algorithm for the control synthesis of nonlinear sampled switched systems, Formal Methods in System Design, 2018.
• Benedikt Bollig, Manuela-Lidia Grindei, Peter Habermehl: Realizability of concurrent recursive programs, Formal Methods in System Design, 2018.
• Dietmar Berwanger, Anup Basil Mathew, Marie van den Bogaard: Hierarchical information and the synthesis of distributed strategies, Acta Informatica, 2018.
• Adrien Le Coënt, Laurent Fribourg, Nicolas Markey, Florian de Vuyst, Ludovic Chamoin: Compositional synthesis of state-dependent switching control, Theoretical Computer Science, 2018.
• Fabrice Kordon, Hubert Garavel, Lom Hillah, Emmanuel Paviot-Adet, Loïg Jezequel, Francis Hulin-Hubard, Elvio Amparore, Marco Beccuti, Bernard Berthomieu, Hugues Evrard, Peter Gjøl Jensen, Didier Le Botlan, Torsten Liebke, Jeroen Meijer, Jiří Srba, Yann Thierry-Mieg, Jaco van de Pol, Karsten Wolf: MCC’2017 - The Seventh Model Checking Contest, LNCS Transactions on Petri Nets and Other Models of Concurrency, 2018.
• Matthias Függer, Thomas Nowak: Fast Multidimensional Asymptotic and Approximate Consensus, International Symposium on DIStributed Computing (DISC) 2018, 2018.
• Benedikt Bollig, Mathieu Lehaut, Nathalie Sznajder: Round-Bounded Control of Parameterized Systems, 16th International Symposium on Automated Technology for Verification and Analysis (ATVA 2018), 2018.
• Da-Jung Cho, Yo-Sub Han, Hwee Kim, Kai Salomaa: Site-Directed Deletion, 22nd International Conference on Developments in Language Theory (DLT 2018), 2018.
• Da-Jung Cho, Yo-Sub Han, Kai Salomaa, Taylor J. Smith: Site-Directed Insertion: Decision Problems\, Maximality and Minimality, 20th International Conference on Descriptional Complexity of Formal Systems, 2018.
• Matthias Függer, Thomas Nowak, Manfred Schwarz: Tight Bounds for Asymptotic and Approximate Consensus, ACM Symposium on Principles of Distributed Computing (PODC'18), 2018.
• Adrien Le Coënt, Laurent Fribourg, Jonathan Vacher: Control Synthesis for Stochastic Switched Systems using the Tamed Euler Method., 6th IFAC Conference on Analysis and Design of Hybrid Systems ADHS 2018 ADHS'18,, 2018.
• Béatrice Bérard, Stefan Haar, Sylvain Schmitz, Stefan Schwoon: The Complexity of Diagnosability and Opacity Verification for Petri Nets, Fundamenta Informaticae, 2018.
• Serge Haddad, Benjamin Monmege: Interval Iteration Algorithm for MDPs and IMDPs, Theoretical Computer Science, 2018.
• Benoît Barbot, Béatrice Bérard, Yann Duplouy, Serge Haddad: Integrating Simulink Models into the Model Checker Cosmos, 39th International Conference on Applications and Theory of Petri Nets and Concurrency, 2018.
• Engel Lefaucheux, Alessandro Giua, Carla Seatzu: Basis Coverability Graph for Partially Observable Petri Nets with Application to Diagnosability Analysis, Petri Nets 2018 - International Conference on Applications and Theory of Petri Nets and Concurrency, 2018.
• Olivier Carton, Bruno Guillon, Fabian Reiter: Counter Machines and Distributed Automata, International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2018), 2018.
• Thomas Chatain, Stefan Haar, Loïc Paulevé: Boolean Networks: Beyond Generalized Asynchronicity, AUTOMATA 2018 - 24th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, 2018.
• Loïg Jezequel, Agnes Madalinski, Stefan Schwoon: Distributed computation of vector clocks in Petri nets unfolding for test selection, Workshop on Discrete Event Systems (WODES), 2018.
• Matthias Függer, Attila Kinali, Christoph Lenzen, Ben Wiederhake: Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance, 24th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), 2018.
• Sylvain Conchon, Giorgio Delzanno, Angelo Ferrando: Parameterized Verification of Topology-sensitive Distributed Protocols goes Declarative, International Conference on Networked Systems (NETYS), 2018.
• Loïg Jezequel, Thomas Chatain, Maurice Comlan, David Delfieu, Olivier Henri Roux: Pomsets and Unfolding of Reset Petri Nets, LATA 2018 - 12th International Conference on Language and Automata Theory and Applications, 2018.
• C. Aiswarya, Benedikt Bollig, Paul Gastin: An automata-theoretic approach to the verification of distributed algorithms, Information and Computation, 2018.
• Matthias Függer, Jürgen Maier, Robert Najvirt, Thomas Nowak, Ulrich Schmid: A Faithful Binary Circuit Model with Adversarial Noise, DATE 2018 - Design, Automation and Test in Europe Conference and Exhibition, 2018.
• Stephan Friedrichs, Matthias Függer, Christoph Lenzen: Metastability-Containing Circuits, IEEE Transactions on Computers, 2018.
• Benedikt Bollig, Marie Fortin, Paul Gastin: Communicating Finite-State Machines and Two-Variable Logic, Symposium on Theoretical Aspects of Computer Science (STACS 2018), 2018.
• Paul Gastin, Benjamin Monmege: A Unifying Survey on Weighted Logics and Weighted Automata, Soft Computing, 2018.
• Rolf Hennicker, Michel Bidoit: Compatibility Properties of Synchronously and Asynchronously Communicating Components, Logical Methods in Computer Science, 2018.
• Adnane Saoud, Antoine Girard, Laurent Fribourg: On the Composition of Discrete and Continuous-time Assume-Guarantee Contracts for Invariance, European Control Conference (ECC 2018), 2018.
• Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Pierre P. Carlier: When are stochastic transition systems tameable?, Journal of Logical and Algebraic Methods in Programming, 2018.
• Serge Haddad: Memoryless Determinacy of Finite Parity Games: Another Simple Proof, Information Processing Letters, 2018.

2012

• Philippe Darondeau, Stephane Demri, Roland Meyer, Christophe Morvan: Petri Net Reachability Graphs: Decidability Status of First Order Properties, Logical Methods in Computer Science, 2012.

2011

• Philippe Darondeau, Stephane Demri, Roland Meyer, Christophe Morvan: Petri Net Reachability Graphs: Decidability Status of FO Properties, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011.

Projects

running

• DREAMY (ANR) on Distributed Algorithms for Microbiological Systems.
• COSTXPRESS (ANR) on Quantitative models of expression costs of synthetic genetic circuits.

past

currently no past projects

Seminar

For seminars please see the seminar page.

Joining the group / open positions

We are looking for excellent Postdocs, PhDs, and interns. If you are interested in joining, please contact a member of the group that is closest to your research interests.

We are also looking for high potentials that want to join the group as a researcher. If you got interested please contact Matthias Függer.

Contact

Any other questions? Please write us.

Email: mfuegger@lmf.cnrs.fr