共查询到20条相似文献,搜索用时 15 毫秒
1.
Mutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. Attiya, Hendler, and Woelfel (40th STOC, 2008) established an Ω(log N) lower bound on the number of RMRs incurred by processes as they enter and exit the critical section, where N is the number of processes in the system. This matches the upper bound of Yang and Anderson (Distrib. Comput. 9(1):51–60,
1995). The upper and lower bounds apply for algorithms that only use read and write operations. The lower bound of Attiya et al.,
however, only holds for deterministic algorithms. The question of whether randomized mutual exclusion algorithms, using reads
and writes only, can achieve sub-logarithmic expected RMR complexity remained open. We answer this question in the affirmative
by presenting starvation-free randomized mutual exclusion algorithms for the cache coherent (CC) and the distributed shared
memory (DSM) model that have sub-logarithmic expected RMR complexity against the strong adversary. More specifically, each
process incurs an expected number of O(log N / log log N) RMRs per passage through the entry and exit sections, while in the worst case the number of RMRs is O(log N). 相似文献
2.
《Performance Evaluation》1986,6(2):93-102
This paper considers a multiple-access communication channel with an infinite number of users. We show that if a controlled slotted Aloha protocol is used, then messages with variable length will have a negative impact on the average message delay. In order to alleviate this problem, a mixed mode (Hybrid) access method is suggested under which the channel bandwidth is split into two sub-channels, managed under different policies. Messages whose length is less than or equal to a critical value are transmitted in one sub-channel under a slotted Aloha policy. The rest of the messages are sent through a separate portion of the channel bandwidth, using a reservation protocol. We show that under this hybrid access method the average delay of a message is greatly improved. 相似文献
3.
在复杂系统的设计流程中,每个设计阶段都要制定标准的设并方案以实现系统功能。渐进细化设计就是把设计流程中的设计方案和检验其能否实现一个特定功能分离开来。提出了渐进细化的概念,并将其应用于互斥访问系统中,同时用LOTOS规范进行描述。 相似文献
4.
We consider a random multiple access (RMA) procedure in a vector disjunctive channel. We show that exploiting properties of the channel allows one to reduce collision resolution time and thus increase the maximal stable throughput (MST) of RMA algorithms in this channel. We propose an algorithm, belonging to the class of splitting algorithms, which achieves the MST of 0.603. 相似文献
5.
Ted Herman 《Distributed Computing》2000,13(1):1-17
Summary. A superstabilizing protocol is a protocol that i is self-stabilizing, meaning that it can recover from an arbitrarily severe transient fault; and ii can recover from a local transient fault while satisfying a passage predicate during recovery. This paper investigates the possibility of superstabilizing protocols for mutual exclusion in a ring of
processors, where a local fault consists of any transient fault at a single processor; the passage predicate specifies that
there be at most one token in the ring, with the single exception of a spurious token colocated with the transient fault. The first result
of the paper is an impossibility theorem for a class of superstabilizing mutual exclusion protocols. Two unidirectional protocols
are then presented to show that conditions for impossibility can independently be relaxed so that superstabilization is possible
using either additional time or communication registers. A bidirectional protocol subsequently demonstrates that superstabilization
in O(1) time is possible. All three superstabilizing protocols are optimal with respect to the number of communication registers
used.
Received: August 1996 / Accepted: March 1999 相似文献
6.
Jan L. A. van de Snepscheut 《Distributed Computing》1987,2(2):113-115
We represent a set of communicating processes by a graph. The mutual exclusion problem is solved for an arbitrary connected graph. The solution is shown to be fair.Jan L.A. van de Snepscheut received a PhD from the Eindhoven University of Technology. He was a visiting assistant professor at the California Institute of Technology, and is presently a professor of computing science at Groningen University. 相似文献
7.
In the group mutual exclusion problem, each critical section has a type or a group associated with it. Processes requesting critical sections belonging to the same group (that is, of the same type) may execute their critical sections concurrently. However, processes requesting critical sections belonging to different groups (that is, of different types) must execute their critical sections in a mutually exclusive manner. 相似文献
8.
First-Come-First-Served (FCFS) mutual exclusion (ME) is the problem of ensuring that processes attempting to concurrently
access a shared resource do so one by one, in a fair order. In this paper, we close the complexity gap between FCFS ME and
ME in the asynchronous shared memory model where processes communicate using atomic reads and writes only, and do not fail.
Our main result is the first known FCFS ME algorithm that makes O(log N) remote memory references (RMRs) per passage and uses only atomic reads and writes. Our algorithm is also adaptive to point
contention. More precisely, the number of RMRs a process makes per passage in our algorithm is Θ(min(k, log N)), where k is the point contention. Our algorithm matches known RMR complexity lower bounds for the class of ME algorithms that use
reads and writes only, and beats the RMR complexity of prior algorithms in this class that have the FCFS property. 相似文献
9.
Asynchronous group mutual exclusion 总被引:1,自引:1,他引:0
Yuh-Jzer Joung 《Distributed Computing》2000,13(4):189-206
Abstract. Mutual exclusion and concurrency are two fundamental and essentially opposite features in distributed systems. However, in
some applications such as Computer Supported Cooperative Work (CSCW) we have found it necessary to impose mutual exclusion
on different groups of processes in accessing a resource, while allowing processes of the same group to share the resource.
To our knowledge, no such design issue has been previously raised in the literature. In this paper we address this issue by
presenting a new problem, called Congenial Talking Philosophers, to model group mutual exclusion. We also propose several criteria to evaluate solutions of the problem and to measure their
performance. Finally, we provide an efficient and highly concurrent distributed algorithm for the problem in a shared-memory
model where processes communicate by reading from and writing to shared variables. The distributed algorithm meets the proposed
criteria, and has performance similar to some naive but centralized solutions to the problem.
Received: November 1998 / Accepted: April 2000 相似文献
10.
A distributed control algorithm, called MEAL, is presented for achieving mutual exclusion in a distributed computing environment. It requires only (N + 2) messages per critical section entry, in the no failures case; N being the number of nodes in the distributed system. Few assertions are proved to verify the correct functioning of MEAL. Possible modification to make it resilient, in case of node failures, are also suggested. 相似文献
11.
The standard implementation of mutual exclusion by means of a semaphore allows starvation of processes. Between 1979 and 1986, three algorithms were proposed that preclude starvation. These algorithms use a special kind of semaphore. We model this so-called buffered semaphore rigorously and provide mechanized proofs of the algorithms. We prove that the algorithms are three implementations of one abstract algorithm in which every competing process is overtaken not more than once by any other process. We also consider a so-called polite semaphore, which is weaker than the buffered one and is strong enough for one of the three algorithms. Refinement techniques are used to compare the algorithms and the semaphores. 相似文献
12.
Srdjan Petrovic 《Information Processing Letters》2005,95(2):343-350
In the group mutual exclusion problem [Y. Joung, Asynchronous group mutual exclusion, Distrib. Comput. 13 (2000) 189], which generalizes mutual exclusion [E. Dijkstra, Solution of a problem in concurrent programming control, Comm. ACM 8 (9) (1965) 569], a process chooses a session when it requests entry into the Critical Section. A group mutual exclusion algorithm must ensure that the mutual exclusion property holds: if two processes are in the Critical Section at the same time, then they request the same session. In addition to mutual exclusion, lockout freedom, bounded exit, and concurrent entering are basic properties that are desirable in any group mutual exclusion algorithm.Hadzilacos in [Proc. 20th Annual Symp. on Principles of Distributed Computing, 2001, pp. 100-106] first introduced a fairness condition, called first-come-first-served (FCFS), for group mutual exclusion. The only known FCFS group mutual exclusion algorithm is due to Hadzilacos [Proc. 20th Annual Symp. on Principles of Distributed Computing, 2001, pp. 100-106], and requires Θ(N2) bounded shared registers, where N is the number of processes. We present a FCFS group mutual exclusion algorithm that uses only Θ(N) bounded shared registers. (The existence of such an algorithm was posed as an open problem by Hadzilacos.) 相似文献
13.
Summary. This paper presents adaptive algorithms for mutual exclusion using only read and write operations; the performance of the
algorithms depends only on the point contention, i.e., the number of processes that are concurrently active during the algorithm execution (and not on n, the total number of processes). Our algorithm has O(k) remote step complexity and O(logk) system response time, wherek is the point contention. The remote step complexity is the maximal number of steps performed by a process where a wait is counted as one step. The system response time is the time interval between subsequent entries to the critical section, where one time unit is the minimal interval in which
every active process performs at least one step. The space complexity of this algorithm is O(N logn), where N is the range of processes' names. We show how to make the space complexity of our algorithm depend solely on n, while preserving the other performance measures of the algorithm.
Received: March 2001 / Accepted: November 2001 相似文献
14.
Mutual exclusion (mutex) is a powerful mechanism for search space pruning in planning. However, a serious limitation of mutex is that it cannot specify constraints relating actions and facts across different time steps. In this paper, we propose a new class of mutual exclusions that significantly generalizes mutex and can be efficiently computed. The proposed long-distance mutual exclusion (londex) can capture constraints over actions and facts not only at the same time step but also across multiple steps. As a generalization, londex is much stronger than mutex, and provides a general and effective tool for developing efficient planners.We propose two levels of londex. The first level, londex1, is derived from individual domain transition graphs (DTGs), and the second level, londexm, is derived from multiple DTGs by taking into account the interactions among them. Londex constraints provide stronger pruning power but also require a large amount of memory. To address the memory problem, we further develop a virtual realization mechanism in which only a small proportion of londex constraints are dynamically generated as needed during the search. This scheme can save a huge amount of memory without sacrificing the pruning power of londex.For evaluation purposes, we incorporate londex into SATPlan04 and SATPlan06, two efficient SAT-based planners. Our experimental results show that londexm can significantly improve over londex1 since the former exploits causal dependencies among DTGs. Our experimental results for various planning domains also show significant advantages of using londex constraints for reducing planning time. 相似文献
15.
A new elegant and simple algorithm for mutual exclusion of N processes is proposed. It only requires shared variables in a memory model where shared variables need not be accessed atomically.
We prove mutual exclusion by reformulating the algorithm as a transition system (automaton), and applying simulation of automata.
The proof has been verified with the higher-order interactive theorem prover PVS. Under an additional atomicity assumption,
the algorithm is starvation free, and we conjecture that no competing process is passed by any other process more than once.
This conjecture was verified by model checking for systems with at most five processes. 相似文献
16.
17.
We present an adaptive algorithm for N-process mutual exclusion under read/write atomicity in which all busy waiting is by local spinning. In our algorithm, each process p performs O(k) remote memory references to enter and exit its critical section, where k is the maximum “point contention” experienced by p. The space complexity of our algorithm is Θ(N), which is clearly optimal. Our algorithm is the first mutual exclusion algorithm under read/write atomicity that is adaptive when time complexity is measured by counting remote memory references.A preliminary version of this paper was presented at the 14th International Symposium on Distributed Computing [6]. 相似文献
18.
19.
Yuh-Jzer Joung 《Parallel and Distributed Systems, IEEE Transactions on》2003,14(5):463-476
We propose a quorum system, which we referred to as the surficial quorum system, for group mutual exclusion. The surficial quorum system is geometrically evident and is easy to construct. It also has a nice structure based on which a truly distributed algorithm for group mutual exclusion can be obtained and processed loads can be minimized. When used with Maekawa's algorithm, the surficial quorum system allows up to /spl radic/2n/m(m-l) processes to access a resource simultaneously, where n is the total number of processes and m is the total number of groups. We also present two modifications of Maekawa's algorithm so that the number of processes that can access a resource at a time is not limited to the structure of the underlying quorum system, but to the number that the problem definition allows. 相似文献
20.
A fair distributed mutual exclusion algorithm 总被引:1,自引:0,他引:1
This paper presents a fair decentralized mutual exclusion algorithm for distributed systems in which processes communicate by asynchronous message passing. The algorithm requires between N-1 and 2(N-1) messages per critical section access, where N is the number of processes in the system. The exact message complexity can be expressed as a deterministic function of concurrency in the computation. The algorithm does not introduce any other overheads over Lamport's and Ricart-Agrawala's algorithms, which require 3(N-1) and 2(N-1) messages, respectively, per critical section access and are the only other decentralized algorithms that allow mutual exclusion access in the order of the timestamps of requests 相似文献