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.
In recent years, several algorithms have been proposed to implement distributed share memory systems that can tolerate processor failures. This paper presents a more abstract algorithm to provide a recoverable DSM and...
详细信息
In recent years, several algorithms have been proposed to implement distributed share memory systems that can tolerate processor failures. This paper presents a more abstract algorithm to provide a recoverable DSM and analyzes the role of data-race-free programs in recovery to point out where the real benefits of weakly consistent DSM might come from. For this, two specific algorithms that have been proposed for recoverable distributed shared memory are explored.
A new model is proposed for measuring the expected cost of a network operation. The model exhibits monotonicity which means that the cost for site s to communicate with site t must be no greater than the cost for site...
详细信息
ISBN:
(纸本)9780897918008
A new model is proposed for measuring the expected cost of a network operation. The model exhibits monotonicity which means that the cost for site s to communicate with site t must be no greater than the cost for site s to communicate with both site t and some other set of sites. Moreover, by assigning a meaningful cost to all transactions, including unsuccessful one, the cost model allow to minimize the overall network cost independent of data availability. This in contrast to a cost model that minimizes the overall network cost by minimizing data availability.
A task is a distributed coordination problem in which each process starts with a private input value taken from a finite set, communicates with the other processes by applying operations to shared objects, and eventua...
详细信息
ISBN:
(纸本)9780897918008
A task is a distributed coordination problem in which each process starts with a private input value taken from a finite set, communicates with the other processes by applying operations to shared objects, and eventually halts with a private output value, also taken from a finite set. It is said that tasks are decidable in a given model if there exists an effective procedure for deciding whether any task has a protocol in that model. This paper uses techniques adapted from classical algebraic topology to prove undecidability results for a variety of models, and explicit constructions to prove decidability in the complimentary cases. These results are summarized and presented.
The problem of tolerating crash/or link failures has been extensively studied. These studies focused on a single link, and how to mask failures of that link. In contrast, this paper studies lossy links in the context ...
详细信息
ISBN:
(纸本)9780897918008
The problem of tolerating crash/or link failures has been extensively studied. These studies focused on a single link, and how to mask failures of that link. In contrast, this paper studies lossy links in the context of an entire system: it is shown that the effect of lossy links depends on the proportion of faulty processes in the system. The results assume permanent process crashes, and more importantly, the effect of adding link failures on the solvability of problems in general is studied. This approach stresses the importance of the notion of correct-restricted problems.
I present the first randomized wait-free implementation of consensus from multiple writer multiple reader register in which each process takes polylog (O(log2n)) expected steps. To achieve this result, I assume a non-...
详细信息
ISBN:
(纸本)9780897918008
I present the first randomized wait-free implementation of consensus from multiple writer multiple reader register in which each process takes polylog (O(log2n)) expected steps. To achieve this result, I assume a non-standard type of adversary (from [Abr88]). I argue that this type of adversary (which is more powerful than the oblivious adversary, but weaker than the strong adversary) is powerful enough to model practical systems.
This paper presents a specification for membership services designed to operate in an asynchronous environment that is subject to both crash and omission failures. In case of a loss of connectivity in the system (part...
详细信息
This paper presents a specification for membership services designed to operate in an asynchronous environment that is subject to both crash and omission failures. In case of a loss of connectivity in the system (partition), the specification supports partitionable operation, in which components that (temporarily) disconnected from each other operate autonomously. Furthermore, the framework suggested is achievable in an asynchronous environment, yet offers useful semantics of split-up and merging that provide the application developer with sufficient information to recover a consistent state. By taking into account hidden changes, the framework supports consistent mending of partitions and allows for a full recovery.
This paper shows that any counting network, made up of balancers whose fan-in and fan-out vary arbitrarily, is, indeed, strong enough to simultaneously support both Fetch&Increment and Fetch&Decrement operatio...
详细信息
This paper shows that any counting network, made up of balancers whose fan-in and fan-out vary arbitrarily, is, indeed, strong enough to simultaneously support both Fetch&Increment and Fetch&Decrement operations, once each of its balancers is substituted by an elimination balancer. Its proof is purely combinatorial, carried out within the elegant combinatorial framework put forth for the study of balancing networks. Through equivalence theorems, impossibility results, lower bounds, verification algorithms and methodologies to prove correctness carry over to counting networks with enriched operation set.
The I/O automaton model for distributed systems was introduced in [LV89], and has subsequently been generalized and extended [LT95]. This paper focuses on the decision problems for various refinement and simulation re...
详细信息
The I/O automaton model for distributed systems was introduced in [LV89], and has subsequently been generalized and extended [LT95]. This paper focuses on the decision problems for various refinement and simulation relations between I/O automata [LT89, LV95]. The result pertains to the complexity aspects of decision problems that arise in the context of I/O automata based verification. The results are summarized and presented.
Collective consistency is a weak form of agreement in which processes try to reach a common view of group membership under a rather relaxed definition of 'common'. This paper provides a knowledge-based specifi...
详细信息
ISBN:
(纸本)9780897918008
Collective consistency is a weak form of agreement in which processes try to reach a common view of group membership under a rather relaxed definition of 'common'. This paper provides a knowledge-based specification for a simple protocol for the collective consistency. The implementation of this specification is sound if it provides a function that returns a Boolean in the place of the knowledge operator and its argument such that, when the function returns true, the argument is actually true in the set of possible executions provided by the system in which each participant uses this implementation. Extremely fast, nontrivial, sound implementations are presented.
暂无评论