An adaptive algorithm for mutual exclusion is presented using only read and write operations. The algorithm has O(k) remote step complexity and O(log k) system response time. The space complexity of the algorithm is O...
详细信息
An adaptive algorithm for mutual exclusion is presented using only read and write operations. The algorithm has O(k) remote step complexity and O(log k) system response time. The space complexity of the algorithm is O(nN), where N is the range of processes' names.
This study considers asynchronous distributed systems equipped with limited scope accuracy failure detectors. It focuses on conditions on n, f, k and x that allow to solve the k-set agreement problem in those systems....
详细信息
ISBN:
(纸本)9781581131833
This study considers asynchronous distributed systems equipped with limited scope accuracy failure detectors. It focuses on conditions on n, f, k and x that allow to solve the k-set agreement problem in those systems. It is conjectured that, when f≥k, such conditions are necessary to solve the k-set agreement problem in asynchronous distributed systems equipped with failure detectors qq SX or qq SX.
In a previous study, Burns and Lynch proved that at least n multi-writer-multi-reader (MWMR) registers are necessary in any mutual exclusion algorithm that uses only MWMR registers. The present work extends the techni...
详细信息
In a previous study, Burns and Lynch proved that at least n multi-writer-multi-reader (MWMR) registers are necessary in any mutual exclusion algorithm that uses only MWMR registers. The present work extends the techniques of Burns and Lynch to prove that adaptive algorithms that use both n single-writer-multi-reader (SWMR) and MWMR registers, need in addition to the Ω(n) SWMR registers a non-constant, F(n) number of MWMR registers.
The problem we address is the distributed reconfiguration of a metamorphic robotic system composed of any number of two dimensional hexagonal modules from specific initial to specific goal configurations. We present a...
详细信息
ISBN:
(纸本)9781581131833
The problem we address is the distributed reconfiguration of a metamorphic robotic system composed of any number of two dimensional hexagonal modules from specific initial to specific goal configurations. We present a distributed algorithm for reconfiguring a straight chain of hexagonal modules at one location to any intersecting straight chain configuration at some other location in the plane. We prove our algorithm is correct, and show that it is either optimal or asymptotically optimal in the number of moves and asymptotically optimal in the time required for parallel reconfiguration. We then consider the distributed reconfiguration of straight chains of modules to a more general class of goal configurations.
distributed programs are hard to write. A distributed debugger equipped with the mechanism to re-execute the traced computation in a controlled fashion can greatly facilitate the detection and localization of bugs. Th...
详细信息
ISBN:
(纸本)9781581131833
distributed programs are hard to write. A distributed debugger equipped with the mechanism to re-execute the traced computation in a controlled fashion can greatly facilitate the detection and localization of bugs. This approach gives rise to a general problem, called predicate control problem, which takes a computation and a safety property specified on the computation, and outputs a controlled computation that maintains the property. We define a class of global predicates, called region predicates, that can be controlled efficiently in a distributed computation. We prove that the synchronization generated by our algorithm is optimal. Further, we introduce the notion of an admissible sequence of events and prove that it is equivalent to the notion of predicate control. We then give an efficient algorithm for the class of disjunctive predicates based on the notion of an admissible sequence.
It is well known that the consensus problem cannot be solved deterministically in an asynchronous environment, but that randomized solutions are possible. We propose a new model, called noisy scheduling, in which an a...
详细信息
ISBN:
(纸本)9781581131833
It is well known that the consensus problem cannot be solved deterministically in an asynchronous environment, but that randomized solutions are possible. We propose a new model, called noisy scheduling, in which an adversarial schedule is perturbed randomly, and show that in this model randomness in the environment can substitute for randomness in the algorithm. In particular, we show that a simplified, deterministic version of Chandra's wait-free shared-memory consensus algorithm solves consensus in time at most logarithmic in the number of active processes. The proof of termination is based on showing that race between independent delayed renewal processes produces a winner quickly. In addition, we show that the protocol finishes in constant time using quantum and priority-based scheduling on a uniprocessor, suggesting that it is robust against the choice of model over a wide range.
Support for efficient dynamic migration and replication of objects is essential for achieving adequate performance and scalability. Traditional solutions to the problem focused on competitiveness. This means that the ...
详细信息
ISBN:
(纸本)9781581131833
Support for efficient dynamic migration and replication of objects is essential for achieving adequate performance and scalability. Traditional solutions to the problem focused on competitiveness. This means that the algorithm's complexity matches the offline adversary's complexity within an acceptable ratio. We define and study the allocation problem under two new measures: stability and fault tolerance. Stability considers the performance of an object allocation algorithm when the object access patterns at the individual nodes of a distributed system stabilize. We present a new algorithm for uniform networks based on the idea of sliding windows. Besides being optimally competitive, the algorithm also exhibits good stability. For fault-tolerance, we consider the performance of allocation algorithms when at least t copies need to be maintained. We derive a lower bound on the competitiveness of such algorithms. Finally, we modify our earlier solution so that it is also optimally fault-tolerant.
A coterie is a family of subsets such that every pair of subsets in it has at least one element in common but neither is a subset of the other. We introduce an operator σ, which transforms a ND (non-dominated;see the...
详细信息
ISBN:
(纸本)9781581131833
A coterie is a family of subsets such that every pair of subsets in it has at least one element in common but neither is a subset of the other. We introduce an operator σ, which transforms a ND (non-dominated;see the Introduction for definition) coterie to another ND coterie. A 'regular' coterie is a natural generalization of a 'vote-assignable' coterie, which is used in some practical applications. We show that any regular ND coterie C can be transformed to any other regular ND coterie D by judiciously applying σ operations to C at most |C| + |D| - 2 times. As another application of the σ operation, we present an incrementally-polynomial-time algorithm for generating all regular ND coteries. We then introduce the concept of a 'g-regular' function, as a generalization of availability. We show how to construct an optimum coterie C with respect to a g-regular function in O(n3|C|) time.
We consider the task of distributedly assigning distinct labels to nodes of an unknown anonymous network. A priori, nodes do not have any identities (anonymous network) and do not know the topology or the size of the ...
详细信息
We consider the task of distributedly assigning distinct labels to nodes of an unknown anonymous network. A priori, nodes do not have any identities (anonymous network) and do not know the topology or the size of the network (unknown network). They execute identical algorithms, apart from a distinguished node, called the source, which starts the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms.
Long-lived and adaptive to point contention implementations of snapshot and immediate snapshot objects in the read/write shared-memory model are presented. In [2] we presented adaptive algorithms for mutual exclusion,...
详细信息
Long-lived and adaptive to point contention implementations of snapshot and immediate snapshot objects in the read/write shared-memory model are presented. In [2] we presented adaptive algorithms for mutual exclusion, collect and snapshot. However, the collect and snapshot algorithms were adaptive only when the number of local primitive operations that a process performs are ignored, i.e., not counted. The number of primitive local steps (operations that do not access the shared memory) in the collect and snapshot operations presented in [2] is O(Nk3) and O(Nk4) respectively where N is the total number of processes in the system and k is the encountered contention. Here we developed new techniques that enabled us to achieve fully adaptive implementations in which the step complexity (combined local and shared) of any operation is bounded by a function of the number of processes that are concurrent with the operation, in particular, O(k4) for the snapshot implementation.
暂无评论