The relations that can be computed with arbitrary knowledge on networks where all processors use the same algorithm and start from the same state are investigated. Three known activation models are considered, namely,...
详细信息
The relations that can be computed with arbitrary knowledge on networks where all processors use the same algorithm and start from the same state are investigated. Three known activation models are considered, namely, asynchronous, synchronous, and interleaved. The networks are directed graphs colored on their arcs, and each processor changes its state depending on its previous state and on the state of its in-neighbors.
We compare the impact of timing conditions on implementing sequentially consistent and linearizable counters using counting networks in distributed systems. For counting problems in application domains which do not re...
详细信息
We compare the impact of timing conditions on implementing sequentially consistent and linearizable counters using counting networks in distributed systems. For counting problems in application domains which do not require linearizability but will run correctly if only sequential consistency is provided, the potential payoffs of our investigation are threefold: First, we show that sequential consistency and linearizability cannot be distinguished by the timing conditions previously considered in the context of counting networks, and thus in contexts in which these constraints apply, it is possible to rely on the stronger semantics of linearizability, which simplifies proofs and enhances compositionality. Second, we identify local timing conditions that support sequential consistency but not linearizability, and thus suggest weaker, easily implementable timing conditions that are likely to be sufficient in many applications. third, we show that any kind of synchronization that is too weak to support even sequential consistency, may violate it significantly for some counting networks;hence, we identify timing conditions that are to be totally ruled out for specific applications that rely critically on either sequential consistency or linearizability.
It is shown that if there is no bound on the number of faulty processes, then in a precise sense, in a system with unreliable but fair communication, Uniform distributed Coordination (UDC) can be attained if and only ...
详细信息
It is shown that if there is no bound on the number of faulty processes, then in a precise sense, in a system with unreliable but fair communication, Uniform distributed Coordination (UDC) can be attained if and only if a system has perfect failure detectors. This result is generalized to the case where there is a bound t on the number of faulty processes. It is shown that a certain type of generalized failure detector is necessary and sufficient for achieving UDC in a context with at most t faulty processes. Reasoning about processes' knowledge as to which other processes are faulty plays a key role in the analysis.
We describe a fast, wait-free (2k-1)-renaming algorithm which takes O(k2) time. (Where k is the contention, the number of processes actually taking steps in a given run.) The algorithm makes extensive use of tools and...
详细信息
We describe a fast, wait-free (2k-1)-renaming algorithm which takes O(k2) time. (Where k is the contention, the number of processes actually taking steps in a given run.) The algorithm makes extensive use of tools and techniques developed by Attiya and Fouren [AF98]. Other extensions, including a fast (long-lived) atomic snapshot algorithm, are briefly discussed.
This paper studies the `usefulness' of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making on vertex a leader, giving the number of ver...
详细信息
This paper studies the `usefulness' of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making on vertex a leader, giving the number of vertex to each vertices, and so on, have been considered. In this paper, we study a relation between the initial condition by considering transformation algorithm from one initial condition to another. For such transformation algorithms, we consider in this paper, both deterministic and randomized distributed algorithms. For each deterministic and randomized transformation type, we show that the relation induces an infinite lattice structure among equivalence classes of initial conditions.
Locking is a standard technique in traditional distributedcomputing and database systems to ensure data integrity by prohibiting concurrent conflicting updates on shared data objects. Operational transformation is an...
详细信息
Locking is a standard technique in traditional distributedcomputing and database systems to ensure data integrity by prohibiting concurrent conflicting updates on shared data objects. Operational transformation is an innovative technique invented by groupware research for consistency maintenance in real-time group editors. In this paper, we will examine and explore the complementary roles of locking and operational transformation in consistency maintenance. A novel optional locking scheme is proposed and integrated with operation transformation to maintain both generic and context-specific consistency in a distributed, interactive, and collaborative environment. The integrated optional locking and operational transformation technique is fully distributed, highly responsive, non-blocking, and capable of avoiding locking overhead in the most common case of collaborative editing.
Various timing-based mutual exclusion algorithms have been proposed that guarantee mutual exclusion if certain timing assumptions hold. In this paper, we examine how these algorithms behave when the time for the basic...
详细信息
Various timing-based mutual exclusion algorithms have been proposed that guarantee mutual exclusion if certain timing assumptions hold. In this paper, we examine how these algorithms behave when the time for the basic operations is governed by random distributions. In particular, we are concerned with how often such algorithms succeed in allowing a processor to obtain a critical section and how this success rate depends on the random variables involved. We explore this question in the case where operation times are governed by exponential and gamma distributions, using both theoretical analysis and simulations.
Ordering and time are two different aspects of consistency of shared objects in a distributed system. One avoids conflicts between operations, the other addresses how quickly the effects of an operation are perceived ...
详细信息
Ordering and time are two different aspects of consistency of shared objects in a distributed system. One avoids conflicts between operations, the other addresses how quickly the effects of an operation are perceived by the rest of the system. Consistency models such as sequential consistency and causal consistency do not consider the particular time at which an operation is executed to establish a valid order among all the operations of a computation. Timed consistency models require that if a write operation is executed at time t, it must be visible to all nodes by time t+Δ. Timed consistency generalizes several existing consistency criteria and it is well suited for interactive and collaborative applications, where the action of one user must be seen by others in a timely fashion.
This paper addresses the problem of designing bounded range priority queues, that is, queues that support a fixed range of priorities. Bounded range priority queues are fundamental in the design of modern multiprocess...
详细信息
This paper addresses the problem of designing bounded range priority queues, that is, queues that support a fixed range of priorities. Bounded range priority queues are fundamental in the design of modern multiprocessor algorithms - from the application level to lowest levels of the operating system kernel. While most of the available priority queue literature is directed at existing small-scale machines, we chose to evaluate algorithms on a broader concurrency scale using a simulated 256 node shared memory multiprocessor architecture similar to the MIT Alewife. Our empirical evidence suggests that the priority queue algorithms currently available in the literature do not scale. Based on these findings, we present two simple new algorithms. LinearFunnels and FunnelTree, that provide true scalability throughout the concurrency range.
We present a combinatorial framework;for the study of a natural class of distributed optimization problems that involve decisionmaking by a collection of n distributed agents in the presence of incomplete information;...
详细信息
ISBN:
(纸本)3540664122
We present a combinatorial framework;for the study of a natural class of distributed optimization problems that involve decisionmaking by a collection of n distributed agents in the presence of incomplete information;such problems were originally considered in a load balancing setting by Papadimitriou and Yannakakis (proceedings of the 10th annualacmsymposium on principles of distributedcomputing, pp. 61-64, August 1991). For any given decision protocol and assuming no communication among the agents, our framework allows to obtain a combinatorial inclusion-exclusion expression for the probability that no "overflow" occurs, called the winning probability, in terms of the volume of some simple combinatorial polytope. Within our general framework, we offer a complete resolution to the special cases of oblivious algorithms, for which agents do not "look at" their inputs, and non-oblivious algorithms, for which they do, of the general optimization problem. In either case, we derive optimality conditions in the form of combinatorial polynomial equations. For oblivious algorithms, we explicitly solve these equations to show that the optimal algorithm is simple and uniform, in the sense that agents need not "know" n. Most interestingly, we shaw that optimal non-oblivious algorithms must be non-uniform: we demonstrate that the optimality conditions admit different solutions for particular, different "small" values of n;however, these solutions improve in terms of the winning probability over the optimal, oblivious algorithm. Our results demonstrate an interesting tradeoff between the amount of knowledge used by agents and uniformity for optimal, distributed decision-making with no communication.
暂无评论