Replication
Theory and Practice
Article
In the stabilizing consensus problem each agent of a networked system has an input value and is repeatedly writing an output value; it is required that eventually all the output values stabilize to the same value...
Chapter and Conference Paper
We define the \(\mathrm {mod}\,k\) mod k ...
Reference Work Entry In depth
Chapter and Conference Paper
We investigate the approximate consensus problem in highly dynamic networks in which topology may change continually and unpredictably. We prove that in both synchronous and partially synchronous networks, app...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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). ...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Book
Article
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...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Reference Work Entry In depth
Book and Conference Proceedings
31st Conference on Current Trends in Theory and Practice of Computer Science Liptovský Ján, Slovakia, January 22-28, 2005. Proceedings
Chapter and Conference Paper
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...
Chapter
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...
Chapter and Conference Paper
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 ...
Chapter and Conference Paper
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...
Article
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...