24 Result(s)

Chapter and Conference Paper

Measure of parallelism of distributed computations

We define a measure of parallelism of a distributed computation which evaluates the interactions between the processes in this computation. This measure assesses the structure of the exchanges of messages, rat...

Bernadette Charron-Bost in STACS 89 (1989)

Chapter and Conference Paper

Combinatorics and geometry of consistent cuts : Application to concurrency theory

We define a concurrency measure of a distributed computation which is based on the number μ of its consistent cuts. We prove that counting consistent cuts takes into account the non-transitivity of the concurrenc...

Bernadette Charron-Bost in Distributed Algorithms (1989)

Chapter and Conference Paper

Concerning the size of clocks

By Fidge and Mattern's algorithm, it was already known that it is sufficient to use n-tuple as timestamps of events for a system distributed over n processes if causal independence is to be characterized. In this...

Bernadette Charron-Bost in Semantics of Systems of Concurrent Processes (1990)

Chapter and Conference Paper

Simulating reliable links with unreliable links in the presence of process crashes

Anindya Basu, Bernadette Charron-Bost, Sam Toueg in Distributed Algorithms (1996)

Article

Synchronous, asynchronous, and causally ordered communication

This article studies characteristic properties of synchronous and asynchronous message communications in distributed systems. Based on the causality relation between events in computations with asynchronous co...

Bernadette Charron-Bost, Friedemann Mattern, Gerard Tel in Distributed Computing (1996)

Chapter and Conference Paper

Revisiting Safety and Liveness in the Context of Failures

Safety and liveness are two fundamental concepts for proving the correctness of concurrent programs. In the context of failures, however, we observe that some properties that are commonly believed to be safety...

Bernadette Charron-Bost, Sam Toueg, Anindya Basu in CONCUR 2000 — Concurrency Theory (2000)

Chapter and Conference Paper

Agreement Problems in Fault-Tolerant Distributed Systems

Reaching agreement in a distributed system is a fundamental issue of both theoretical and practical importance. Consensus, Atomic Commitment, Atomic Broadcast, Group Membership which are different versions of ...

Bernadette Charron-Bost in SOFSEM 2001: Theory and Practice of Informatics (2001)

Chapter

Comparing the Atomic Commitment and Consensus Problems

Reaching agreement in a distributed system is a fundamental issue of both theoretical and practical importance. Consensus and non-blocking atomic commitment are two wellknown versions of this paradigm. The Consen...

Bernadette Charron-Bost in Future Directions in Distributed Computing (2003)

Chapter and Conference Paper

Validity Conditions in Agreement Problems and Time Complexity

We first introduce a new class of distributed agreement problems, ranging from Uniform Consensus to Non-Blocking Atomic Commitment, by varying the validity condition in the specification. We then provide an ea...

Bernadette Charron-Bost, Fabrice Le Fessant in SOFSEM 2004: Theory and Practice of Comput… (2004)

Reference Work Entry In depth

Consensus with Partial Synchrony

Bernadette Charron-Bost, André Schiper in Encyclopedia of Algorithms (2008)

Chapter and Conference Paper

A Reduction Theorem for the Verification of Round-Based Distributed Algorithms

We consider the verification of algorithms expressed in the Heard-Of Model, a round-based computational model for fault-tolerant distributed computing. Rounds in this model are communication-closed, and we sho...

Mouna Chaouch-Saad, Bernadette Charron-Bost, Stephan Merz in Reachability Problems (2009)

Chapter and Conference Paper

Link Reversal: How to Play Better to Work Less

Sensor networks, with their ad hoc deployments, node mobility, and wireless communication, pose serious challenges for develo** provably correct and efficient applications. A popular algorithm design techniq...

Bernadette Charron-Bost, Jennifer L. Welch… in Algorithmic Aspects of Wireless Sensor Net… (2009)

Article

The Heard-Of model: computing in distributed systems with benign faults

Problems in fault-tolerant distributed computing have been studied in a variety of models. These models are structured around two central ideas: (1) degree of synchrony and failure model are two independent param...

Bernadette Charron-Bost, André Schiper in Distributed Computing (2009)

Chapter and Conference Paper

Partial is Full

Link reversal is the basis of several well-known routing algorithms [1,2,3]. In these algorithms, logical directions are imposed on the communication links and a node that becomes a sink reverses some of its i...

Bernadette Charron-Bost, Matthias Függer… in Structural Information and Communication C… (2011)

Chapter and Conference Paper

Full Reversal Routing as a Linear Dynamical System

Link reversal is a versatile algorithm design paradigm, originally proposed by Gafni and Bertsekas in 1981 for routing, and subsequently applied to other problems including mutual exclusion and resource alloca...

Bernadette Charron-Bost, Matthias Függer… in Structural Information and Communication C… (2011)

Chapter and Conference Paper

Formal Verification of Consensus Algorithms Tolerating Malicious Faults

Consensus is the paradigmatic problem in fault-tolerant distributed computing: it requires network nodes that communicate by message passing to agree on common value even in the presence of (benign or maliciou...

Bernadette Charron-Bost, Henri Debrat… in Stabilization, Safety, and Security of Dis… (2011)

Chapter and Conference Paper

New transience bounds for long walks in weighted digraphs

Fix two nodes i and j in an edge-weighted diagraph and form the following sequence: Let a(n) be the maximum weight of walks from i to j of length n; if no such walk exists, a(n) = −∞. It is known that, if G is st...

Bernadette Charron-Bost, Matthias Függer… in The Seventh European Conference on Combina… (2013)

Chapter and Conference Paper

Transience Bounds for Distributed Algorithms

A large variety of distributed systems, like some classical synchronizers, routers, or schedulers, have been shown to have a periodic behavior after an initial transient phase (Malka and Rajsbaum, WDAG 1991). ...

Bernadette Charron-Bost, Matthias Függer… in Formal Modeling and Analysis of Timed Syst… (2013)