Recently, it was suggested by multiple researchers that the smaller is the number of faults to hit a network, the faster should a network protocol recover. This goal proved hard, however, so such protocols have been s...
详细信息
Recently, it was suggested by multiple researchers that the smaller is the number of faults to hit a network, the faster should a network protocol recover. This goal proved hard, however, so such protocols have been suggested only for relatively easier (and less typical) cases, such as non-reactive tasks, or the case where a node can detect that it is faulty. We present solutions for the reactive problem that is often used as a benchmark for such protocols: the problem of token passing. We treat the realistic case, where no bound is known on the time a node can hold the token (a node holds the token as long as the node has not completed some external task). We study the scenario where up to k (for a given k) faults hit nodes in a reactive asynchronous distributed system by corrupting their state undetectably. The exact number of faults, the specific faulty nodes, and the time the faults hit are not known. We present several algorithms that stabilize into a legitimate configuration (in which exactly one node has a token) in time that depends only on k, and not on n (the number of nodes). We present our solutions in stages, by first presenting a basic protocol that stabilizes in O(k2) time and uses only a constant number of (logarithmic size) variables per node. For this first protocol it is required that k is smaller than √n-2, that is, the first protocol k-stabilizes, but does not self-stabilize. In terms of the number of individual nodes' steps the stabilization takes O(kn) steps, and it is shown that any 1-stabilizing algorithm (that is, when k = 1) must use at least n-3 steps. The other algorithms are built on the basic one: one stabilizes in O(k2) time and is self-stabilizing (so k can be larger than √n-2), another enhanced version stabilizes in O(k) time (and is time optimal) but the space it uses is larger by a multiplicative factor of k.
This conference proceedings contains 25 papers. The topics covered are: impossibility proofs;nondeterministic processes;communicating finite-state machines;bounded protocols for FIFO channels;sequence transmission pro...
详细信息
ISBN:
(纸本)0897913264
This conference proceedings contains 25 papers. The topics covered are: impossibility proofs;nondeterministic processes;communicating finite-state machines;bounded protocols for FIFO channels;sequence transmission problems;communication in the presence of faults;knowledge, probability, and adversaries;reliable message diffusion;expressivity and knowledge;ambiguity of choosing;concensus;mutual exclusion;fault-tolerant computing;parallel algorithms;distributed recovery;induction theorem;parallel programs;concurrency;Byzantine agreement;shared memory versus message passing;calling names;multishop radio networks;fault isolation;randomized concensus.
We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximation distributed algorithm for weighted maximum matching;whose running time...
详细信息
ISBN:
(纸本)9781595936165
We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximation distributed algorithm for weighted maximum matching;whose running time is O(log n) for any constant epsilon > 0, where n is the number of nodes in the graph. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give an algorithm that maintains a (1 + epsilon)-approximation in O(1/epsilon) time for each node insertion or deletion. For weighted dynamic graphs we give a constant-factor approximation algorithm that runs in constant time for each insertion or deletion.
This paper presents two distributed algorithms for the computation of sparse certificates for k-connectivity in asynchronous networks where a network is represented by a graph and processors have unique identities. A ...
详细信息
ISBN:
(纸本)9780897918008
This paper presents two distributed algorithms for the computation of sparse certificates for k-connectivity in asynchronous networks where a network is represented by a graph and processors have unique identities. A certificate of the k-connectivity of a graph G = (V,E) on n nodes and m edges is a spanning subgraph G′ = (V,E′). Finding a certificate with the minimum number of edges for any fixed k is NP-hard, thus, sparse certificates which contain 0(kn) edges are found.
The proceedings contain 28 papers. The topics discussed include: practical uses of synchronized clocks undistributed systems;randomized wait-free concurrent objects;efficient parallel algorithms on restartable fail-st...
ISBN:
(纸本)0897914392
The proceedings contain 28 papers. The topics discussed include: practical uses of synchronized clocks undistributed systems;randomized wait-free concurrent objects;efficient parallel algorithms on restartable fail-stop processors;resiliency of interactive distributed tasks;how to withstand mobile virus attacks;on the value of information in distributed decision-making;optimal space distributed move-to-front lists;compact deterministic distributed dictionaries;a theory of relaxed atomicity;real-time sequence transmission problem;and consensus in the presence of timing uncertainty: omission and byzantine failures.
An adding network is a distributed data structure that supports a concurrent, lock-free, low-contention implementation of a fetch&add counter. We give a lower bound showing that adding networks have inherently hig...
详细信息
An adding network is a distributed data structure that supports a concurrent, lock-free, low-contention implementation of a fetch&add counter. We give a lower bound showing that adding networks have inherently high latency. We prove that our lower bound is tight.
暂无评论