14 Search Results for "Charron-Bost, Bernadette"


Document
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
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
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
Verification of Randomized Consensus Algorithms Under Round-Rigid Adversaries

Authors: Nathalie Bertrand, Igor Konnov, Marijana Lazić, and Josef Widder

Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)


Abstract
Randomized fault-tolerant distributed algorithms pose a number of challenges for automated verification: (i) parameterization in the number of processes and faults, (ii) randomized choices and probabilistic properties, and (iii) an unbounded number of asynchronous rounds. This combination makes verification hard. Challenge (i) was recently addressed in the framework of threshold automata. We extend threshold automata to model randomized consensus algorithms that perform an unbounded number of asynchronous rounds. For non-probabilistic properties, we show that it is necessary and sufficient to verify these properties under round-rigid schedules, that is, schedules where processes enter round r only after all processes finished round r-1. For almost-sure termination, we analyze these algorithms under round-rigid adversaries, that is, fair adversaries that only generate round-rigid schedules. This allows us to do compositional and inductive reasoning that reduces verification of the asynchronous multi-round algorithms to model checking of a one-round threshold automaton. We apply this framework and automatically verify the following classic algorithms: Ben-Or’s and Bracha’s seminal consensus algorithms for crashes and Byzantine faults, 2-set agreement for crash faults, and RS-Bosco for the Byzantine case.

Cite as

Nathalie Bertrand, Igor Konnov, Marijana Lazić, and Josef Widder. Verification of Randomized Consensus Algorithms Under Round-Rigid Adversaries. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bertrand_et_al:LIPIcs.CONCUR.2019.33,
  author =	{Bertrand, Nathalie and Konnov, Igor and Lazi\'{c}, Marijana and Widder, Josef},
  title =	{{Verification of Randomized Consensus Algorithms Under Round-Rigid Adversaries}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Fokkink, Wan and van Glabbeek, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.33},
  URN =		{urn:nbn:de:0030-drops-109358},
  doi =		{10.4230/LIPIcs.CONCUR.2019.33},
  annote =	{Keywords: threshold automata, counter systems, parameterized verification, randomized distributed algorithms, Byzantine faults}
}
Document
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
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
The Need for Language Support for Fault-Tolerant Distributed Systems

Authors: Cezara Dragoi, Thomas A. Henzinger, and Damien Zufferey

Published in: LIPIcs, Volume 32, 1st Summit on Advances in Programming Languages (SNAPL 2015)


Abstract
Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. Nonetheless there is surprisingly little language and verification support to build distributed systems based on fault-tolerant algorithms. In this paper, we present some of the challenges that a designer has to overcome to implement a fault-tolerant distributed system. Then we review different models that have been proposed to reason about distributed algorithms and sketch how such a model can form the basis for a domain-specific programming language. Adopting a high-level programming model can simplify the programmer's life and make the code amenable to automated verification, while still compiling to efficiently executable code. We conclude by summarizing the current status of an ongoing language design and implementation project that is based on this idea.

Cite as

Cezara Dragoi, Thomas A. Henzinger, and Damien Zufferey. The Need for Language Support for Fault-Tolerant Distributed Systems. In 1st Summit on Advances in Programming Languages (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 32, pp. 90-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{dragoi_et_al:LIPIcs.SNAPL.2015.90,
  author =	{Dragoi, Cezara and Henzinger, Thomas A. and Zufferey, Damien},
  title =	{{The Need for Language Support for Fault-Tolerant Distributed Systems}},
  booktitle =	{1st Summit on Advances in Programming Languages (SNAPL 2015)},
  pages =	{90--102},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-80-4},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{32},
  editor =	{Ball, Thomas and Bodík, Rastislav and Krishnamurthi, Shriram and Lerner, Benjamin S. and Morriset, Greg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2015.90},
  URN =		{urn:nbn:de:0030-drops-50192},
  doi =		{10.4230/LIPIcs.SNAPL.2015.90},
  annote =	{Keywords: Programming language, Fault-tolerant distributed algorithms, Automated verification}
}
Document
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
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
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
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
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}
}
Document
Methods and Metrics for Reliability Assessment

Authors: Lirida Alves de Barros-Naviner, Jean-François Naviner, Denis Teixeira Franco, and Mai Correia de Vasconcelos

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


Abstract
This paper deals with digital VLSI design aspects related to reliability. The focus is on the problem of reliability evaluation in combinational logic circuits.We present some methods for this evaluation that can be easily integrated in a tradidional design flow. Also we describe suitable metrics for performance estimation of concurrent error detection schemes.

Cite as

Lirida Alves de Barros-Naviner, Jean-François Naviner, Denis Teixeira Franco, and Mai Correia de Vasconcelos. Methods and Metrics for Reliability Assessment. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{alvesdebarrosnaviner_et_al:DagSemProc.08371.5,
  author =	{Alves de Barros-Naviner, Lirida and Naviner, Jean-Fran\c{c}ois and Teixeira Franco, Denis and Correia de Vasconcelos, Mai},
  title =	{{Methods and Metrics for Reliability Assessment}},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--15},
  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.5},
  URN =		{urn:nbn:de:0030-drops-19252},
  doi =		{10.4230/DagSemProc.08371.5},
  annote =	{Keywords: Reliability, fault tolerance, combinational logic}
}
Document
Multiple Event Upsets Aware FPGAs Using Protected Schemes

Authors: Costas Argyrides and Dhiraj K. Pradhan

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


Abstract
Multiple upsets would be available in SRAM-based FPGAs which utilizes SRAM in different parts to implement circuit configuration and to implement circuit data. Moreover, configuration bits of SRAM-based FPGAs are more sensible to upsets compared to circuit data due to significant number of SRAM bits. In this paper, a new protected Configurable Logic Block (CLB) and FPGA architecture are proposed which utilize multiple error correction (DEC) and multiple error detection. This is achieved by the incorporation of recently proposed coding technique Matrix codes [1] inside the FPGA. The power and area analysis of the proposed techniques show that these methods are more efficient than the traditional schemes such as duplication with comparison and TMR circuit design in the FPGAs.

Cite as

Costas Argyrides and Dhiraj K. Pradhan. Multiple Event Upsets Aware FPGAs Using Protected Schemes. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{argyrides_et_al:DagSemProc.08371.6,
  author =	{Argyrides, Costas and Pradhan, Dhiraj K.},
  title =	{{Multiple Event Upsets Aware FPGAs Using Protected Schemes}},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--15},
  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.6},
  URN =		{urn:nbn:de:0030-drops-19261},
  doi =		{10.4230/DagSemProc.08371.6},
  annote =	{Keywords: FPGA, SEUs, ECC, Reliability, MTTF}
}
  • 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 Classification
  • 3 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Dynamic graph algorithms
  • 1 Computing methodologies → Distributed artificial intelligence
  • 1 Networks → Mobile networks
  • 1 Networks → Network dynamics
  • Show More...

  • Refine by Keyword
  • 4 fault tolerance
  • 3 Fault-tolerant distributed algorithms
  • 2 Clock synchronization
  • 2 Reliability
  • 2 Self-stabilization
  • Show More...

  • Refine by Type
  • 14 document

  • Refine by Publication Year
  • 6 2009
  • 2 2023
  • 1 2013
  • 1 2015
  • 1 2016
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail