An overview is given of impossibility results in the area of distributedcomputing. The techniques used are described, and a historical perspective is given. Suggestions for future work are made.
ISBN:
(纸本)0897913264
An overview is given of impossibility results in the area of distributedcomputing. The techniques used are described, and a historical perspective is given. Suggestions for future work are made.
The notions of refinement for branching time based on stuttering simulation and bisimulation are developed. A local proof rule called well-founded simulation is introduced. It is shown that if one system refines anoth...
详细信息
The notions of refinement for branching time based on stuttering simulation and bisimulation are developed. A local proof rule called well-founded simulation is introduced. It is shown that if one system refines another, then a refinement map always exists. The added generality is obtained by using relations to relate implementation states with specification states and by requiring the use of well-founded relations.
Consider a distributed network in which up to a third of the nodes may be Byzantine, and in which the non-faulty nodes may be subject to transient, faults that alter their memory in air arbitrary fashion. Within the c...
详细信息
ISBN:
(纸本)9781595939890
Consider a distributed network in which up to a third of the nodes may be Byzantine, and in which the non-faulty nodes may be subject to transient, faults that alter their memory in air arbitrary fashion. Within the context of this model. we are interested in the digital clock synchronization problem;which consists of agreeing oil bounded integer counters, and increasing these counters regularly. It has been postulated in the past that, synchronization cannot be solved in a Byzantine tolerant and self-stabilizing first. solution to this problem tu had an expected manner. exponential convergence time. Later, a deterministic solution was, published with linear convergence time, which is optimal for deterministic solutions. In the current paper we achieve an expected constant convergence time. We thus obtain the optimal probabilistic solution, both in terms of convergence time and in terms of resilience to Byzantine adversaries.
This paper is a summary of an invited talk presented at the 12th acmsymposium on principles of distributedcomputing in August 1993. The talk gave a brief introduction to the Ubiquitious computing vision, described s...
详细信息
The set of conditions that allow to solve the interactive consistency problem, denoted CB_IC, in the presence of fc crashes and fe erroneous proposals are characterized. Those are the conditions including input vector...
详细信息
The set of conditions that allow to solve the interactive consistency problem, denoted CB_IC, in the presence of fc crashes and fe erroneous proposals are characterized. Those are the conditions including input vectors such that their Hamming is at least 2fe+fc+1. A CB_IC protocol for the shared memory systems is also introduced. This protocol establishes a connection relating consensus, interactive consistency and error-correcting codes.
Finding a maximal or maximum matching in a graph is a well-understood problem for which efficient sequential algorithms exist. Applications of matchings in distributed settings make it desirable to find self-stabilizi...
详细信息
Finding a maximal or maximum matching in a graph is a well-understood problem for which efficient sequential algorithms exist. Applications of matchings in distributed settings make it desirable to find self-stabilizing asynchronous distributed solutions to these problems. We first present a self-stabilizing algorithm for finding a maximal matching in a general anonymous network under read/write atomicity with linear round complexity. This is followed by a self-stabilizing algorithm, with quadratic time complexity, for finding a maximum matching in a biparite network under composite atomicity. These results represent significant progress in the area of distributed algorithms for matchings.
暂无评论