Space-efficient FCFS group mutual exclusion

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 Θ(N²) 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.)     

Automated analysis of mutual exclusion algorithms using CCS

A number of mutual exclusion algorithms are studied by representing them as agents in the Calculus of Communicating Systems and using an automated tool embodying some of the theory of the Calculus to analyse the representations. It is determined whether or not each of the algorithms preserves mutual exclusion and is live.     

A fast,scalable mutual exclusion algorithm

Summary This paper is concerned with synchornization under read/write atomicity in shared memory multi-processors. We present a new algorithm forN-process mutual exclusion that requires only read and write operations and that hasO(logN) time complexity, where time is measured by counting remote memory references. The time complexity of this algorithm is better than that of all prior solutions to the mutual exclusion problem that are based upon atomic read and write instructions; in fact, the time complexity of most prior solutions is unbounded. Performance studies are presented that show that our mutual exclusion algorithm exhibits scalable performance under heavy contention. In fact, its performance rivals that of the fastest queue-based spin locks based on strong primitives such as compare-and-swap and fetch-and-add. We also present a modified version of our algorithm that generates onlyO(1) memory references in the absence of contention. Jae-Heon Yang received the B.S. and M. S. degrees in Computer Engineering from Seoul National University in 1985 and 1987, respectively, and the Ph.D. degree in Computer Science from the University of Maryland at College Park in 1994. Since June 1994, he has been an Assistant Professor of Computer Science at Mills College in Oakland, California. From 1987 to 1989, he was a junior researcher at the Korea Telecommunication Authority Research Center. His research interests include distributed computing and operating systems. James H. Anderson received the M. S. degree in Computer Science from Michigan State University in 1982, the M.S. degree in Computer Science from Purdue University in 1983, and the Ph.D. degree in Computer Sciences from the University of Texas at Austin in 1990. Since August 1993, he has been an Assistant Professor of Computer Science at the University of North Carolina at Chapel Hill. Prior to joining the University of North Carolina, he was an Assistant Professor of Computer Science for three years at the University of Maryland at College Park Professor Anderson's main research interests are within the area of coneurrent and distributed computing. His current interests include wait-free algorithms, scalabde synchronization mechanisms for shared-memory systems, and object-sharing strategies for hard real-time applications.Preliminary version was presented at the Twelfth Annual ACM Symposium on Principles of Distributed Computing Ithaca, New York, August 1993 [15]. Work supported, in part, by NSF Contracts CCR-9109497 and CCR-9216421 and by the Center for Excellence in Space Data and Information Sciences (CESDIS)     

A mutual exclusion algorithm with optimally bounded bypasses

Peterson's algorithm [G.L. Peterson, Myths about the mutual exclusion problem, Inform. Process. Lett. 12 (3) (1981) 115-116] for mutual exclusion has been widely studied for its elegance and simplicity. In Peterson's algorithm, each process has to cross n−1 stages to access the shared resource irrespective of the contention for the shared resource at that time, and allows unbounded bypasses. In [K. Block, T.-K. Woo, A more efficient generalization of Peterson's mutual exclusion algorithm, Inform. Process. Lett. 35 (1990) 219-222], Block and Woo proposed a modified algorithm that transforms the number stages to be crossed from fixed n−1 to t, where 1?t?n, and bounds the number of possible bypasses by n(n−1)/2. This paper proposes a simple modification that reduces the bound on the number of possible bypasses to optimal n−1.     

Adaptive mutual exclusion with local spinning

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].     

Long-distance mutual exclusion for planning

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, londex₁, is derived from individual domain transition graphs (DTGs), and the second level, londex_m, 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 londex_m can significantly improve over londex₁ 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.     

Asynchronous group mutual exclusion

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     

Superstabilizing mutual exclusion

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     

Fair mutual exclusion on a graph of processes

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.     

分布式系统中进程的同步与互斥算法讨论

详细阐述了分布式系统中进程的同步与互斥问题。对几种算法进行了讨论,分析了其特点,还提出了令牌环算法的一个改进算法。该算法解决了在真网络中可能出现的部分问题,并经过了实验验证。     

Adaptive and efficient mutual exclusion

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     

Shared-memory mutual exclusion: major research trends since 1986

In 1986, Michel Raynal published a comprehensive survey of algorithms for mutual exclusion [72]. In this paper, we survey major research trends since 1986 in work on shared-memory mutual exclusion.Received: June 2001, Accepted: January 2003, Work supported by NSF grants CCR 9732916, CCR 9972211, CCR 9988327, ITR 0082866, and CCR 0208289.     

(h,k)-Arbiters for h-out-of-k mutual exclusion problem

h-Out-of-k mutual exclusion is a generalization of the 1-mutual exclusion problem, where there are k units of shared resources and each process requests h (1hk) units at the same time. Though k-arbiter has been shown to be a quorum-based solution to this problem, quorums in k-arbiter are much larger than those in the 1-coterie for 1-mutual exclusion. Thus, the algorithm based on k-arbiter needs many messages. This paper introduces the new notion that each request uses different quorums depending on the number of units of its request. Based on the notion, this paper defines two (h,k)-arbiters for h-out-of-k mutual exclusion: a uniform (h,k)-arbiter and a (k+1)-cube (h,k)-arbiter. The quorums in each (h,k)-arbiter are not larger than the ones in the corresponding k-arbiter; consequently, it is more efficient to use (h,k)-arbiters than the k-arbiters. A uniform (h,k)-arbiter is a generalization of the majority coterie for 1-mutual exclusion. A (k+1)-cube (h,k)-arbiter is a generalization of square grid coterie for 1-mutual exclusion.     

Nonatomic mutual exclusion with local spinning

We present an N-process local-spin mutual exclusion algorithm, based on nonatomic reads and writes, in which each process performs Θ(log N) remote memory references to enter and exit its critical section. This algorithm is derived from Yang and Anderson's atomic tree-based local-spin algorithm in a way that preserves its time complexity. No atomic read/write algorithm with better asymptotic worst-case time complexity (under the remote-mem-ory-refer-ences measure) is currently known. This suggests that atomic memory is not fundamentally required if one is interested in worst-case time complexity.The same cannot be said if one is interested in fast-path algorithms (in which contention-free time complexity is required to be O(1)) or adaptive algorithms (in which time complexity is required to depend only on the number of contending processes). We show that such algorithms fundamentally require memory accesses to be atomic. In particular, we show that for any N-process nonatomic algorithm, there exists a single-process execution in which the lone competing process accesses Ω(log N/log log N) distinct variables to enter its critical section. Thus, fast and adaptive algorithms are impossible even if caching techniques are used to avoid accessing the processors-to-memory interconnection network.This paper was invited for inclusion in the special issue of this journal based on selected papers presented in PODC '02 (Distributed Computing 18(1)).It appears separately because of a publication delay. Yong-Jik Kimreceived a B.S. degree in Physics/Computer Science from Korea Advanced Institute of Science and Technology in 1998, and a Ph.D.degree in Computer Science from the University of Notrh Carolina at Chapel Hill in 2003. He currently works for the RDBMS group in Tmax Soft, and is otherwise occupied with his newborn daughter Darum, which means “difference” in Korean. James H. Anderson is a professor in the Department of Computer Science at the University of North Carolina at Chapel Hill. He received a B.S.degree in Computer Science from Michigan State University in 1982, an M.S. degree in Computer Science from Purdue University in 1983, and a Ph.D. degree in Computer Sciences from the University of Texas at Austin in 1990. Before joining UNC-Chapel Hill in 1993, he was with the Computer Science Department at the University of Maryland between 1990 and 1993. Dr.Anderson's main research interests are within the areas of real-time systems and concurrent and distributed computing.     

Queue based mutual exclusion with linearly bounded overtaking

The queue based mutual exclusion protocol establishes mutual exclusion for N>1 threads by means of not necessarily atomic variables. In order to enter the critical section, a competing thread needs to traverse as many levels as there are currently competing threads. Competing threads can be overtaken by other competing threads. It is proved here, however, that every competing thread is overtaken less than N times, and that the overtaking threads were competing when the first one of them exits.     

Building effective mutual exclusion services for grids

Taking into account the intrinsic heterogeneity of communication latency of grid environments, we propose in this article a composition approach that enables to build mutual exclusion services for grids. By using our approach, different intra and inter cluster token-based mutual exclusion algorithms can be combined easily. Performance evaluation tests were conducted on the French national grid testbed called Grid’5000, whose results show that our approach is effective and that the choice of the most suitable inter cluster algorithm depends on the behavior of the application.

Request-based token passing for self-stabilizing mutual exclusion

This paper presents a new method for request-based self-stabilizing token passing. A token is passed via a dynamic BFS (breadth-first search) tree rooted at a requesting process. When one of the tree edges reaches a process that has a token, the process is aware of the occurrence of a request. Then the token is passed towards the root. Even if multiple tokens stay at distinct roots, it can be shown that they will be merged into a single token. Furthermore, each request-rooted tree continues to grow until the request is serviced. As a result, the tree with a request that has long been neglected grows larger and larger, which makes it easier for the requesting process to get a token. Such advantages can be achieved by using bounded memory. We also evaluate the stabilization time and the efficiency of servicing k requests, called k-covering time, of our method.