The existing analyses of distributed Shared Memory (DSM) consistency conditions is extended by investigating achievable levels of fault tolerance. It is shown that in many cases there is a tradeoff - increasing the re...
详细信息
ISBN:
(纸本)9780897919524
The existing analyses of distributed Shared Memory (DSM) consistency conditions is extended by investigating achievable levels of fault tolerance. It is shown that in many cases there is a tradeoff - increasing the resilience of one operation necessitates a decrease in the resilience of the other. This result implies that, in practice, it may be possible to increase the resilience of critical or oft-used operations at the expense of other operations.
Lower and upper bounds on convergence complexity, under varying degrees of locality, for optimistic, rate-based flow control algorithms are established. It is shown that randomness can be exploited to yield an even si...
详细信息
Lower and upper bounds on convergence complexity, under varying degrees of locality, for optimistic, rate-based flow control algorithms are established. It is shown that randomness can be exploited to yield an even simpler oblivious algorithm at the price of a small increase in convergence complexity. The results for partially oblivious algorithms imply that knowledge of session rates cannot merely suffice to reduce convergence complexity.
The use of the simpler variants of broadcast protocols for managing replicated databases where the unit of activity is a transaction consisting of multiple operations that need to be executed atomically as a unit is e...
详细信息
The use of the simpler variants of broadcast protocols for managing replicated databases where the unit of activity is a transaction consisting of multiple operations that need to be executed atomically as a unit is explored. The advantage of using causal broadcast for replicated databases is examined. A suite of simple replica control protocols which have been designed to exploit the properties of broadcast communication is developed.
An anonymous network is given by a set of processors without unique identifiers. The result characterizes effectively the functions computable on an arbitrary class of unidirectional anonymous networks, under differen...
详细信息
ISBN:
(纸本)9780897919524
An anonymous network is given by a set of processors without unique identifiers. The result characterizes effectively the functions computable on an arbitrary class of unidirectional anonymous networks, under different activation models. It is shown that wireless bidirectional networks can compute all symmetric functions, but this is not true as soon as the bidirectional requirement is dropped;this is the first class for which such an impossibility result has been obtained, and it shows that the unidirectional case differs from the bidirectional one in an essential way.
We study the scenario where a transient fault hit f of the n nodes of a distributed system by corrupting their state. We consider the basic problem of persistent bit, where the system is required to maintain a value i...
详细信息
ISBN:
(纸本)9780897919524
We study the scenario where a transient fault hit f of the n nodes of a distributed system by corrupting their state. We consider the basic problem of persistent bit, where the system is required to maintain a value in the face of transient failures by means of replication. We give an algorithm to recover the value quickly: the value of the bit is recovered at all nodes in O(f) time units for any unknown value of f > n/2. Moreover, complete state quiescence occurs in O(diam) time units, where diam denotes the diameter of the network. This means that the value persists indefinitely so long as any f
This paper introduces two new novel tools for the study of distributedcomputing and shows their utility by using them to exhibit a simple derivation of the Herlihy and Shavit characterization of wait-free shared-memo...
详细信息
This paper introduces two new novel tools for the study of distributedcomputing and shows their utility by using them to exhibit a simple derivation of the Herlihy and Shavit characterization of wait-free shared-memory computation. The first tool is the notion of the iterated version of a given model. We show that the topological structure that corresponds to an iterated model has a nice recursive structure, and that the iterated version of the atomic snapshot memory solves any task solvable by the non-iterated model. The second tool is an iterated explicit simple convergence algorithm. In the Ph.D. Thesis of the first author these tool were used to characterize models more complex than read-write shared-memory.
A new location management strategy that employs dynamic hashing and quorums is presented. Location information of a mobile host is replicated at a subset of location servers. New location can be added to the system as...
详细信息
ISBN:
(纸本)9780897919524
A new location management strategy that employs dynamic hashing and quorums is presented. Location information of a mobile host is replicated at a subset of location servers. New location can be added to the system as the number of mobile hosts and/or location update and query rates increase. The proposed scheme requires at most two rounds of message multicasting for location update and query operations. This compares favorably with hierarchical schemes that require O(lg N) rounds of unicast messages, where N is the total number of location servers.
We consider the problem of asynchronous consensus with a weak dynamic adversary scheduler. We provide the first algorithm to obtain O¯(n) total work in the weak adversary model using only single-writer registers....
详细信息
ISBN:
(纸本)9780897919524
We consider the problem of asynchronous consensus with a weak dynamic adversary scheduler. We provide the first algorithm to obtain O¯(n) total work in the weak adversary model using only single-writer registers. For the multi-writer setting we give an O(log n) work-per-processor algorithm, improving upon the previous O(log2n) bound. The adversary model considered is the content oblivious adversary model, which assumes that the adversary does not know the content of a register until it is read by some processor [13].
Services replicated using a quorum system allow operations to be performed at only a subset (quorum) of the servers, and ensure consistency among operations by requiring that any two quorums intersect. In this paper w...
详细信息
ISBN:
(纸本)9780897919524
Services replicated using a quorum system allow operations to be performed at only a subset (quorum) of the servers, and ensure consistency among operations by requiring that any two quorums intersect. In this paper we explore the consequences of requiring this intersection property to hold only with very high probability. We show that doing so can offer dramatic improvements in the performance and availability of the service, both for services tolerant of benign server failures and services tolerant of arbitrary (Byzantine) ones. We also prove a lower bound on the performance that can be achieved with this technique.
A distributed counter allows each processor in an asynchronous message passing network to access the counter value and increment it. We study the problem of implementing a distributed counter such that no processor is...
详细信息
A distributed counter allows each processor in an asynchronous message passing network to access the counter value and increment it. We study the problem of implementing a distributed counter such that no processor is a communication bottleneck. We prove a lower bound of Ω(log n/log log n) on the number of messages that some processor must exchange in a sequence of n counting operations spread over n processors. We propose a counter that achieves this bound when each processor increments the counter exactly once. Hence the lower bound is tight. Because most algorithms and data structures count in some way the lower bound holds for many distributed computations. We feel that the proposed concept of a communication bottleneck is a relevant measure of efficiency for a distributed algorithm and data structure because it indicates the achievable degree of distribution.
暂无评论