17 Search Results for "Charron-Bost, Bernadette"

Document
DOI: 10.4230/LIPIcs.SEA.2026.14
K-Hole Separation in PEO‑Based ILP Treewidth Formulation

Authors: Andrea D'Ascenzo

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
In this paper, we introduce a family of valid inequalities for the strongest currently known integer programming formulation of treewidth based on perfect elimination orderings. These inequalities arise from the structure of induced chordless cycles (holes) and strengthen the canonical linear relaxation by enforcing constraints that every feasible chordal completion must satisfy. To handle the exponentially many such inequalities, we develop a dedicated separation routine capable of detecting violated k-hole constraints within a cutting-plane framework. Our computational results show that incorporating these inequalities substantially improves the quality of the lower bounds across a broad range of graph classes, in some cases nearly closing the integrality gap.
Cite as

Andrea D'Ascenzo. K-Hole Separation in PEO‑Based ILP Treewidth Formulation. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dascenzo:LIPIcs.SEA.2026.14,
  author =	{D'Ascenzo, Andrea},
  title =	{{K-Hole Separation in PEO‑Based ILP Treewidth Formulation}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.14},
  URN =		{urn:nbn:de:0030-drops-260186},
  doi =		{10.4230/LIPIcs.SEA.2026.14},
  annote =	{Keywords: Treewidth, Integer Linear Programming, Polyhedral Combinatorics, Chordal Completion, Induced Cycles}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.32
Planar Stories of Graph Drawings: Algorithms and Experiments

Authors: Carla Binucci, Sabine Cornelsen, Walter Didimo, Seok-Hee Hong, Eleni Katsanou, Maurizio Patrignani, Antonios Symvonis, and Samuel Wolf

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We address the problem of computing a dynamic visualization of a geometric graph G as a sequence of frames. Each frame shows only a portion of the graph but their union covers G entirely. The two main requirements of our dynamic visualization are: (i) guaranteeing drawing stability, so to preserve the user’s mental map; (ii) keeping the visual complexity of each frame low. To satisfy the first requirement, we never change the position of the vertices. Regarding the second requirement, we avoid edge crossings in each frame. More precisely, in the first frame we visualize a suitable subset of non-crossing edges; in each subsequent frame, exactly one new edge enters the visualization and all the edges that cross with it are deleted. We call such a sequence of frames a planar story of G. Our goal is to find a planar story whose minimum number of edges contemporarily displayed is maximized (i.e., a planar story that maximizes the minimum frame size). Besides studying our model from a theoretical point of view, we also design and experimentally compare different algorithms, both exact techniques and heuristics. These algorithms provide an array of alternative trade-offs between efficiency and effectiveness, also depending on the structure of the input graph.
Cite as

Carla Binucci, Sabine Cornelsen, Walter Didimo, Seok-Hee Hong, Eleni Katsanou, Maurizio Patrignani, Antonios Symvonis, and Samuel Wolf. Planar Stories of Graph Drawings: Algorithms and Experiments. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{binucci_et_al:LIPIcs.GD.2025.32,
  author =	{Binucci, Carla and Cornelsen, Sabine and Didimo, Walter and Hong, Seok-Hee and Katsanou, Eleni and Patrignani, Maurizio and Symvonis, Antonios and Wolf, Samuel},
  title =	{{Planar Stories of Graph Drawings: Algorithms and Experiments}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.32},
  URN =		{urn:nbn:de:0030-drops-250182},
  doi =		{10.4230/LIPIcs.GD.2025.32},
  annote =	{Keywords: Graph Drawing, Dynamic Graphs, Graph Stories, Heuristics, ILP}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.26
Computational Complexity of Covering Regular Trees

Authors: Jan Bok, Jiří Fiala, Nikola Jedličková, and Jan Kratochvíl

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
A graph covering projection, also referred to as a locally bijective homomorphism, is a mapping between the vertices and edges of two graphs that preserves incidences and is a local bijection. This concept originates in topological graph theory but has also found applications in combinatorics and theoretical computer science. In this paper we consider undirected graphs in the most general setting - graphs may contain multiple edges, loops, and semi-edges. This is in line with recent trends in topological graph theory and mathematical physics. We advance the study of the computational complexity of the H-Cover problem, which asks whether an input graph allows a covering projection onto a parameter graph H. The quest for a complete characterization started in 1990’s. Several results for simple graphs or graphs without semi-edges have been known, the role of semi-edges in the complexity setting has started to be investigated only recently. One of the most general known NP-hardness results states that H-Cover is NP-complete for every simple connected regular graph of valency greater than two. We complement this result by considering regular graphs H arising from connected acyclic graphs by adding semi-edges. Namely, we prove that any graph obtained by adding semi-edges to the vertices of a tree making it a d-regular graph with d ≥ 3, defines an NP-complete graph covering problem. In line with the so called Strong Dichotomy Conjecture, we prove that the NP-hardness holds even for simple graphs on input.
Cite as

Jan Bok, Jiří Fiala, Nikola Jedličková, and Jan Kratochvíl. Computational Complexity of Covering Regular Trees. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.MFCS.2025.26,
  author =	{Bok, Jan and Fiala, Ji\v{r}{\'\i} and Jedli\v{c}kov\'{a}, Nikola and Kratochv{\'\i}l, Jan},
  title =	{{Computational Complexity of Covering Regular Trees}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.26},
  URN =		{urn:nbn:de:0030-drops-241338},
  doi =		{10.4230/LIPIcs.MFCS.2025.26},
  annote =	{Keywords: graph cover, covering projection, semi-edges, multigraphs, complexity, constrained homomorphisms, trees}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.34
Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure

Authors: Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Consensus is arguably the most studied problem in distributed computing as a whole, and particularly in the distributed message-passing setting. In this latter framework, research on consensus has considered various hypotheses regarding the failure types, the memory constraints, the algorithmic performances (e.g., early stopping and obliviousness), etc. Surprisingly, almost all of this work assumes that messages are passed in a complete network, i.e., each process has a direct link to every other process. A noticeable exception is the recent work of Castañeda et al. (Inf. Comput. 2023) who designed a generic oblivious algorithm for consensus running in radius(G,t) rounds in every graph G, when up to t nodes can crash by irrevocably stopping, where t is smaller than the node-connectivity κ of G. Here, radius(G,t) denotes a graph parameter called the radius of G whenever up to t nodes can crash. For t = 0, this parameter coincides with radius(G), the standard radius of a graph, and, for G = K_n, the running time radius(K_n,t) = t+1 of the algorithm exactly matches the known round-complexity of consensus in the clique K_n. Our main result is a proof that radius(G,t) rounds are necessary for oblivious algorithms solving consensus in G when up to t nodes can crash, thus validating a conjecture of Castañeda et al., and demonstrating that their consensus algorithm is optimal for any graph G. We also extend the result of Castañeda et al. to two different settings: First, to the case where the number t of failures is not necessarily smaller than the connectivity κ of the considered graph; Second, to the k-set agreement problem for which agreement is not restricted to be on a single value as in consensus, but on up to k different values.
Cite as

Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz. Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.STACS.2025.34,
  author =	{Fraigniaud, Pierre and Nguyen, Minh Hang and Paz, Ami},
  title =	{{Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{34:1--34:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.34},
  URN =		{urn:nbn:de:0030-drops-228606},
  doi =		{10.4230/LIPIcs.STACS.2025.34},
  annote =	{Keywords: Consensus, set-agreement, fault tolerance, crash failures}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.18
Stabilizing Consensus Is Impossible in Lossy Iterated Immediate Snapshot Models

Authors: Stephan Felber and Hugo Rincon Galeana

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
A substantial portion of distributed computing research is dedicated to terminating problems like consensus and similar agreement problems. However, non-terminating problems have been intensively studied in the context of self-stabilizing distributed algorithms, where processes may start from arbitrary initial states and can tolerate arbitrary transient faults. In between lie stabilizing problems, where the processes start from a well-defined initial state, but do not need to decide irrevocably and are allowed to change their decision finitely often until a stable decision is eventually reached. Stabilizing consensus has been studied within the context of synchronous message adversaries. In particular, Charron-Bost and Moran showed that a necessary condition for stabilizing consensus is the existence of at least one process that reaches all others infinitely often (a perpetual broadcaster). However, it was left open whether this is also a sufficient condition for solving stabilizing consensus. In this paper, we introduce the novel Delayed Lossy-Link (DLL) model, and the Lossy Iterated Immediate Snapshot Model (LIIS), for which we show stabilizing consensus to be impossible. The DLL model is introduced as a variant of the well-known Lossy-Link model, which admits silence periods of arbitrary but finite length. The LIIS model is a variant of the Iterated Immediate Snapshot (IIS), model which admits finite length periods of at most f omission faults per layer. In particular, we show that stabilizing consensus is impossible even when f = 1. Our results show that even in a model with very strong connectivity, namely, the Iterated Immediate Snapshot (IIS) model, a single omission fault per layer effectively disables stabilizing consensus. Furthermore, since the DLL model always has a perpetual broadcaster, the mere existence of a perpetual broadcaster, even in a crash-free setting, is not sufficient for solving stabilizing consensus, negatively answering the open question posed by Charron-Bost and Moran.
Cite as

Stephan Felber and Hugo Rincon Galeana. Stabilizing Consensus Is Impossible in Lossy Iterated Immediate Snapshot Models. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{felber_et_al:LIPIcs.OPODIS.2024.18,
  author =	{Felber, Stephan and Rincon Galeana, Hugo},
  title =	{{Stabilizing Consensus Is Impossible in Lossy Iterated Immediate Snapshot Models}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.18},
  URN =		{urn:nbn:de:0030-drops-225544},
  doi =		{10.4230/LIPIcs.OPODIS.2024.18},
  annote =	{Keywords: distributed systems, dynamic networks, dynamic graphs, message adversaries, stabilizing consensus, asynchronous message passing}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.12
Self-Stabilizing Clock Synchronization in Probabilistic Networks

Authors: Bernadette Charron-Bost and Louis Penet de Monterno

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
We consider the fundamental problem of clock synchronization in a synchronous multi-agent system. Each agent holds a clock with an arbitrary initial value, and clocks must eventually indicate the same value, modulo some integer P. A known solution for this problem in dynamic networks is the self-stabilization SAP (for self-adaptive period) algorithm, which uses finite memory and relies solely on the assumption of a finite dynamic diameter in the communication network. This paper extends the results on this algorithm to probabilistic communication networks: We introduce the concept of strong connectivity with high probability and we demonstrate that in any probabilistic communication network satisfying this hypothesis, the SAP algorithm synchronizes clocks with high probability. The proof of such a probabilistic hyperproperty is based on novel tools and relies on weak assumptions about the probabilistic communication network, making it applicable to a wide range of networks, including the classical push model. We provide an upper bound on time and space complexity. Building upon previous works by Feige et al. and Pittel, the paper provides solvability results and evaluates the stabilization time and space complexity of SAP in two specific cases of communication topologies.
Cite as

Bernadette Charron-Bost and Louis Penet de Monterno. Self-Stabilizing Clock Synchronization in Probabilistic Networks. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:LIPIcs.DISC.2023.12,
  author =	{Charron-Bost, Bernadette and Penet de Monterno, Louis},
  title =	{{Self-Stabilizing Clock Synchronization in Probabilistic Networks}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.12},
  URN =		{urn:nbn:de:0030-drops-191389},
  doi =		{10.4230/LIPIcs.DISC.2023.12},
  annote =	{Keywords: Self-stabilization, Clock synchronization, Probabilistic networks}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.28
Self-Stabilizing Clock Synchronization in Dynamic Networks

Authors: Bernadette Charron-Bost and Louis Penet de Monterno

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
We consider the fundamental problem of periodic clock synchronization in a synchronous multi-agent system. Each agent holds a clock with an arbitrary initial value, and clocks must eventually be congruent, modulo some positive integer P. Previous algorithms worked in static networks with drastic connectivity properties and assumed that global informations are available at each node. In this paper, we propose a finite-state algorithm for time-varying topologies that does not require any global knowledge on the network. The only assumption is the existence of some integer D such that any two nodes can communicate in each sequence of D consecutive rounds, which extends the notion of strong connectivity in static network to dynamic communication patterns. The smallest such D is called the dynamic diameter of the network. If an upper bound on the diameter is provided, then our algorithm achieves synchronization within 3D rounds, whatever the value of the upper bound. Otherwise, using an adaptive mechanism, synchronization is achieved with little performance overhead. Our algorithm is parameterized by a function g, which can be tuned to favor either time or space complexity. Then, we explore a further relaxation of the connectivity requirement: our algorithm still works if there exists a positive integer R such that the network is rooted over each sequence of R consecutive rounds, and if eventually the set of roots is stable. In particular, it works in any rooted static network.
Cite as

Bernadette Charron-Bost and Louis Penet de Monterno. Self-Stabilizing Clock Synchronization in Dynamic Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:LIPIcs.OPODIS.2022.28,
  author =	{Charron-Bost, Bernadette and Penet de Monterno, Louis},
  title =	{{Self-Stabilizing Clock Synchronization in Dynamic Networks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.28},
  URN =		{urn:nbn:de:0030-drops-176480},
  doi =		{10.4230/LIPIcs.OPODIS.2022.28},
  annote =	{Keywords: Self-stabilization, Clock synchronization, Dynamic networks}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.10
Computing Outside the Box: Average Consensus over Dynamic Networks

Authors: Bernadette Charron-Bost and Patrick Lambein-Monette

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
Networked systems of autonomous agents, and applications thereof, often rely on the control primitive of average consensus, where the agents are to compute the average of private initial values. To provide reliable services that are easy to deploy, average consensus should continue to operate when the network is subject to frequent and unpredictable change, and should mobilize few computational resources, so that deterministic, low powered, and anonymous agents can partake in the network. In this stringent adversarial context, we investigate the implementation of average consensus by distributed algorithms over networks with bidirectional, but potentially short-lived, communication links. Inspired by convex recurrence rules for multi-agent systems, and the Metropolis average consensus rule in particular, we design a deterministic distributed algorithm that achieves asymptotic average consensus, which we show to operate in polynomial time in a synchronous temporal model. The algorithm is easy to implement, has low space and computational complexity, and is fully distributed, requiring neither symmetry-breaking devices like unique identifiers, nor global control or knowledge of the network. In the fully decentralized model that we adopt, to our knowledge, no other distributed average consensus algorithm has a better temporal complexity. Our approach distinguishes itself from classical convex recurrence rules in that the agent’s values may sometimes leave their previous convex hull. As a consequence, our convergence bound requires a subtle analysis, despite the syntactic simplicity of our algorithm.
Cite as

Bernadette Charron-Bost and Patrick Lambein-Monette. Computing Outside the Box: Average Consensus over Dynamic Networks. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:LIPIcs.SAND.2022.10,
  author =	{Charron-Bost, Bernadette and Lambein-Monette, Patrick},
  title =	{{Computing Outside the Box: Average Consensus over Dynamic Networks}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.10},
  URN =		{urn:nbn:de:0030-drops-159521},
  doi =		{10.4230/LIPIcs.SAND.2022.10},
  annote =	{Keywords: average consensus, dynamic networks, distributed algorithms, iterated averaging, Metropolis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.20
The Firing Squad Problem Revisited

Authors: Bernadette Charron-Bost and Shlomo Moran

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
In the classical firing squad problem, an unknown number of nodes represented by identical finite state machines is arranged on a line and in each time unit each node may change its state according to its neighbors' states. Initially all nodes are passive, except one specific node located at an end of the line, which issues a fire command. This command needs to be propagated to all other nodes, so that eventually all nodes simultaneously enter some designated ``firing" state. A natural extension of the firing squad problem, introduced in this paper, allows each node to postpone its participation in the squad for an arbitrary time, possibly forever, and firing is allowed only after all nodes decided to participate. This variant is highly relevant in the context of decentralized distributed computing, where processes have to coordinate for initiating various tasks simultaneously. The main goal of this paper is to study the above variant of the firing squad problem under the assumptions that the nodes are infinite state machines, and that the inter-node communication links can be changed arbitrarily in each time unit, i.e., are defined by a dynamic graph. In this setting, we study the following fundamental question: what connectivity requirements enable a solution to the firing squad problem? Our main result is an exact characterization of the dynamic graphs for which the firing squad problem can be solved. When restricted to static directed graphs, this characterization implies that the problem can be solved if and only if the graph is strongly connected. We also discuss how information on the number of nodes or on the diameter of the network, and the use of randomization, can improve the solutions to the problem.
Cite as

Bernadette Charron-Bost and Shlomo Moran. The Firing Squad Problem Revisited. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:LIPIcs.STACS.2018.20,
  author =	{Charron-Bost, Bernadette and Moran, Shlomo},
  title =	{{The Firing Squad Problem Revisited}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.20},
  URN =		{urn:nbn:de:0030-drops-85195},
  doi =		{10.4230/LIPIcs.STACS.2018.20},
  annote =	{Keywords: Synchronization, Detection, Simultaneity, Dynamic Networks}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.137
Fast, Robust, Quantizable Approximate Consensus

Authors: Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We introduce a new class of distributed algorithms for the approximate consensus problem in dynamic rooted networks, which we call amortized averaging algorithms. They are deduced from ordinary averaging algorithms by adding a value-gathering phase before each value update. This results in a drastic drop in decision times, from being exponential in the number n of processes to being polynomial under the assumption that each process knows n. In particular, the amortized midpoint algorithm is the first algorithm that achieves a linear decision time in dynamic rooted networks with an optimal contraction rate of 1/2 at each update step. We then show robustness of the amortized midpoint algorithm under violation of network assumptions: it gracefully degrades if communication graphs from time to time are non rooted, or under a wrong estimate of the number of processes. Finally, we prove that the amortized midpoint algorithm behaves well if processes can store and send only quantized values, rendering it well-suited for the design of dynamic networked systems. As a corollary we obtain that the 2-set consensus problem is solvable in linear time in any dynamic rooted network model.
Cite as

Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Fast, Robust, Quantizable Approximate Consensus. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 137:1-137:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:LIPIcs.ICALP.2016.137,
  author =	{Charron-Bost, Bernadette and F\"{u}gger, Matthias and Nowak, Thomas},
  title =	{{Fast, Robust, Quantizable Approximate Consensus}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{137:1--137:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.137},
  URN =		{urn:nbn:de:0030-drops-62812},
  doi =		{10.4230/LIPIcs.ICALP.2016.137},
  annote =	{Keywords: approximate consensus, dynamic networks, averaging algorithms}
}
Document
DOI: 10.4230/DagRep.3.4.1
Formal Verification of Distributed Algorithms (Dagstuhl Seminar 13141)

Authors: Bernadette Charron-Bost, Stephan Merz, Andrey Rybalchenko, and Josef Widder

Published in: Dagstuhl Reports, Volume 3, Issue 4 (2013)

Abstract
The Dagstuhl Seminar 13141 "Formal Verification of Distributed Algorithms" brought together researchers from the areas of distributed algorithms, model checking, and semi-automated proofs with the goal to establish a common base for approaching the many open problems in verification of distributed algorithms. In order to tighten the gap between the involved communities, who have been quite separated in the past, the program contained tutorials on the basics of the concerned fields. In addition to technical talks, we also had several discussion sessions, whose goal was to identify the most pressing research challenges. This report describes the program and the outcomes of the seminar.
Cite as

Bernadette Charron-Bost, Stephan Merz, Andrey Rybalchenko, and Josef Widder. Formal Verification of Distributed Algorithms (Dagstuhl Seminar 13141). In Dagstuhl Reports, Volume 3, Issue 4, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{charronbost_et_al:DagRep.3.4.1,
  author =	{Charron-Bost, Bernadette and Merz, Stephan and Rybalchenko, Andrey and Widder, Josef},
  title =	{{Formal Verification of Distributed Algorithms (Dagstuhl Seminar 13141)}},
  pages =	{1--16},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{4},
  editor =	{Charron-Bost, Bernadette and Merz, Stephan and Rybalchenko, Andrey and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.4.1},
  URN =		{urn:nbn:de:0030-drops-40747},
  doi =		{10.4230/DagRep.3.4.1},
  annote =	{Keywords: Distributed algorithms; semi-automated proofs; model checking}
}
Document
DOI: 10.4230/DagSemProc.08371.1
08371 Abstracts Collection – Fault-Tolerant Distributed Algorithms on VLSI Chips

Authors: Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract
From September the $7^{\text{th}}$, 2008 to September the $10^{\text{th}}$, 2008 the Dagstuhl Seminar 08371 ``Fault-Tolerant Distributed Algorithms on VLSI Chips '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. The seminar was devoted to exploring whether the wealth of existing fault-tolerant distributed algorithms research can be utilized for meeting the challenges of future-generation VLSI chips. During the seminar, several participants from both the VLSI and distributed algorithms' discipline, presented their current research, and ongoing work and possibilities for collaboration were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid. 08371 Abstracts Collection – Fault-Tolerant Distributed Algorithms on VLSI Chips. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:DagSemProc.08371.1,
  author =	{Charron-Bost, Bernadette and Dolev, Shlomi and Ebergen, Jo and Schmid, Ulrich},
  title =	{{08371 Abstracts Collection – Fault-Tolerant Distributed Algorithms on VLSI Chips }},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.1},
  URN =		{urn:nbn:de:0030-drops-19283},
  doi =		{10.4230/DagSemProc.08371.1},
  annote =	{Keywords: Fault-tolerant distributed algorithms, fault tolerance, VLSI systems-on-chip, synchronous vs.\backslash asynchronous circuits, digital logic, specifications}
}
Document
DOI: 10.4230/DagSemProc.08371.2
08371 Summary – Fault-Tolerant Distributed Algorithms on VLSI Chips

Authors: Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract
Chips was devoted to exploring whether the wealth of existing fault-tolerant distributed algorithms research can be utilized for meeting the challenges of future-generation VLSI chips. Participants from both the distributed fault-tolerant algorithms community, interested in this emerging application domain, and from the VLSI systems-on-chip and digital design community, interested in well-founded system-level approaches to fault-tolerance, surveyed the current state-of-the-art and tried to identify possibilities to work together. The seminar clearly achieved its purpose: It became apparent that most existing research in Distributed Algorithms is too heavy-weight for being immediately applied in the “core” VLSI design context, where power, area etc. are scarce resources. At the same time, however, it was recognized that emerging trends like large multicore chips and increasingly critical applications create new and promising application domains for fault-tolerant distributed algorithms. We are convinced that the very fruitful cross-community interactions that took place during the Dagstuhl seminar will contribute to new research activities in those areas.
Cite as

Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid. 08371 Summary – Fault-Tolerant Distributed Algorithms on VLSI Chips. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:DagSemProc.08371.2,
  author =	{Charron-Bost, Bernadette and Dolev, Shlomi and Ebergen, Jo and Schmid, Ulrich},
  title =	{{08371 Summary – Fault-Tolerant Distributed Algorithms on VLSI Chips }},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.2},
  URN =		{urn:nbn:de:0030-drops-19270},
  doi =		{10.4230/DagSemProc.08371.2},
  annote =	{Keywords: Fault-tolerant distributed algorithms, fault tolerance, VLSI systemson- chip, synchronous vs. asynchronous circuits, digital logic, specifications}
}
Document
DOI: 10.4230/DagSemProc.08371.3
Error Containment in the Presence of Metastability

Authors: Andreas Steininger

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract
Error containment is an important concept in fault tolerant system design, and techniques like voting are applied to mask erroneous outputs, thus preventing their propagation. In this presentation we will use the example of DARTS, a fault-tolerant distributed clock generation scheme in hardware, to demonstrate that metastability is a substantial threat to error containment. We will illustrate how metastability can originate and propagate such that a single fault may upset the system. The main conclusion is that modeling efforts on all design levels are definitely required in order to mitigate and quantify the deteriorating effect of metastability on system dependability.
Cite as

Andreas Steininger. Error Containment in the Presence of Metastability. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{steininger:DagSemProc.08371.3,
  author =	{Steininger, Andreas},
  title =	{{Error Containment in the Presence of Metastability}},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.3},
  URN =		{urn:nbn:de:0030-drops-19235},
  doi =		{10.4230/DagSemProc.08371.3},
  annote =	{Keywords: Metastability, fault tolerance, clock generation}
}
Document
DOI: 10.4230/DagSemProc.08371.4
Implications of VLSI Fault Models and Distributed Systems Failure Models – A hardware designer's view

Authors: Gottfried Fuchs

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract
The fault and failure models as well as their semantics within the VLSI and the distributed systems/algorithms community are quite different. Pointing out the mismatch of those fault respectively failure models is the main part of this work. The impact of the implemented failure model in terms of hardware effort and system complexity will be shown on different VLSI implementations of distributed algorithms. However, still, there are a lot of open questions left mostly related to the coverage analysis of hardware implemented fault-tolerant algorithms.
Cite as

Gottfried Fuchs. Implications of VLSI Fault Models and Distributed Systems Failure Models – A hardware designer's view. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{fuchs:DagSemProc.08371.4,
  author =	{Fuchs, Gottfried},
  title =	{{Implications of VLSI Fault Models and Distributed Systems Failure Models – A hardware designer's view}},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.4},
  URN =		{urn:nbn:de:0030-drops-19245},
  doi =		{10.4230/DagSemProc.08371.4},
  annote =	{Keywords: VLSI, fault model, distributed system, failure model}
}
  • Refine by Type
  • 17 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 4 2025
  • 2 2023
  • 1 2022
  • 1 2018
  • Show More...

  • Refine by Author
  • 8 Charron-Bost, Bernadette
  • 2 Dolev, Shlomi
  • 2 Ebergen, Jo
  • 2 Penet de Monterno, Louis
  • 2 Schmid, Ulrich
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs
  • 1 DagRep
  • 6 DagSemProc

  • Refine by Classification
  • 5 Theory of computation → Distributed algorithms
  • 3 Mathematics of computing → Graph theory
  • 2 Theory of computation → Dynamic graph algorithms
  • 1 Computer systems organization → Fault-tolerant network topologies
  • 1 Computing methodologies → Distributed artificial intelligence
  • Show More...

  • Refine by Keyword
  • 5 fault tolerance
  • 3 dynamic networks
  • 2 Clock synchronization
  • 2 Fault-tolerant distributed algorithms
  • 2 Reliability
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact