检索结果-内蒙古大学图书馆

Recoverable mutual exclusion with abortability

COMPUTING 2022年第10期104卷 2225-2252页

作者： Jayanti, Prasad Joshi, Anup Dartmouth Coll Hanover NH 03755 USA

Recent advances in non-volatile main memory (NVM) technology have spurred research on algorithms that are resilient to intermittent failures that cause processes to crash and subsequently restart. In this paper we present a Recoverable Mutual Exclusion (RME) algorithm that supports abortability. Our algorithm guarantees FCFS and a strong liveness property: processes do not starve even in runs consisting of infinitely many crashes, provided that a process crashes at most a finite number of times in each of its attempts. On DSM and Relaxed-CC multiprocessors, a process incurs O (min(k, log n)) RMRs in a passage and O(f + min (k, log n)) RMRs in an attempt, where n is the number of processes that the algorithm is designed for, k is the point contention of the passage or the attempt, and f is the number of times that p crashes during the attempt. On a Strict CC multiprocessor, the passage and attempt complexities are O(n) and 0(f + n), respectively. Our algorithm uses only the read, write, and CAS operations, which are commonly supported by multiprocessors. Attiya, Hendler, and Woelfel proved that, with any mutual exclusion algorithm, a process incurs at least 52 (log n) RMRs in a passage, if the algorithm uses only the read, write, and CAS operations (in: Proc. of the Fortieth ACM Symposium on Theory of Computing, New York, NY, USA, 2008). This lower bound implies that the worst-case RMR complexity of our algorithm is optimal for the DSM and Relaxed CC multiprocessors. This paper is an expanded version of our conference paper as reported by Jayanti and Joshi (in: Atig and Schwarzmann (eds) Networked Systems. Springer International Publishing, Cham, 2019), which presented the first Recoverable Mutual Exclusion (RME) algorithm that supports abortability. This algorithm from our conference paper (in: Atig and Schwarzmann (eds) Networked Systems. Springer International Publishing, Cham, 2019) admits starvation when there are infinitely many aborts in a run. In this paper,

关键词： concurrent algorithm Synchronization Mutual exclusion Recoverable algorithm Fault tolerance Non-volatile main memory Shared memory Multi-core algorithms

来源：评论

学校读者我要写书评

暂无评论

A Behavioural Theory of Recursive algorithms

引用

FUNDAMENTA INFORMATICAE 2020年第1期177卷 1-37页

作者： Borger, Egon Schewe, Klaus-Dieter Univ Pisa Dipartimento Informat Pisa Italy Zhejiang Univ UIUC Inst Haining Peoples R China

"What is an algorithm?" is a fundamental question of computer science. Gurevich's behavioural theory of sequential algorithms (aka the sequential ASM thesis) gives a partial answer by defining (non-deterministic) sequential algorithms axiomatically, without referring to a particular machine model or programming language, and showing that they are captured by (nondeterministic) sequential Abstract State Machines (nd-seq ASMs). However, recursive algorithms such as mergesort are not covered by this theory, as has been pointed out by Moschovakis, who had independently developed a different framework to mathematically characterize the concept of (in particular recursive) algorithm. In this article we propose an axiomatic definition of the notion of sequential recursive algorithm which extends Gurevich's axioms for sequential algorithms by a Recursion Postulate and allows us to prove that sequential recursive algorithms are captured by recursive Abstract State Machines, an extension of nd-seq ASMs by a CALL rule. Applying this recursive ASM thesis yields a characterization of sequential recursive algorithms as finitely composed concurrent algorithms all of whose concurrent runs are partial-order runs.

关键词： recursive algorithm behavioural theory abstract state machine concurrent algorithm partial-order run

来源：评论

学校读者我要写书评

暂无评论

Towards an Ideal Queue Lock 20

Towards an Ideal Queue Lock

引用

21st International Conference on Distributed Computing and Networking (ICDCN)

作者： Jayanti, Prasad Jayanti, Siddhartha Jayanti, Sucharita Dartmouth Coll Hanover NH 03755 USA MIT Cambridge MA 02139 USA

ISBN: (纸本)9781450377515

The MCS lock was the first mutual exclusion lock to support an arbitrary number of processes with unknown identities such that each process can acquire and release the lock in a constant number of RMRs on both Cache-Coherent and Distributed Shared Memory multiprocessors. The MCS algorithm, however, has a shortcoming: its Exit section is not bounded. The algorithm also requires hardware support for more than one special instruction, namely, Fetch&Store and Compare&Swap. Many MCS-style algorithms were subsequently designed to overcome these shortcomings, but to the best of our knowledge they either lack some desirable property of the MCS lock or introduce a new shortcoming. In this paper we present a new MCS-style algorithm that has all of the desirable properties and no ostensible shortcoming. We also provide a rigorous, invariant-based proof of correctness. To realize a bounded Exit section, all prior MCS-style algorithms use either the "node-switching" or the "node-toggling" strategy. Our work unifies these two strategies: we present a single algorithm which, when appropriately instantiated, yields both a node-switching and a node-toggling algorithm. Moreover, the two algorithms so derived are the simplest in their respective classes among all known MCS-style algorithms.

关键词： mutual exclusion concurrent algorithm queue lock distributed computing RMR

来源：评论

学校读者我要写书评

暂无评论

From Bezout's Identity to Space-Optimal Election in Anonymous Memory Systems 20

From Bezout's Identity to Space-Optimal Election in Anonymou...

引用

39th Symposium on Principles of Distributed Computing

作者： Godard, Emmanuel Imbs, Damien Raynal, Michel Taubenfeld, Gadi Aix Marseille Univ LIS Marseille France CNRS Marseille France Univ Toulon & Var Marseille France Univ Rennes CNRS INRIA Rennes France Hong Kong Polytech Univ Hong Kong Peoples R China Interdisciplinary Ctr Herzliyya Israel

ISBN: (纸本)9781450375825

An anonymous shared memory REG can be seen as an array of atomic registers such that there is no a priori agreement among the processes on the names of the registers. As an example a very same physical register can be known as REG[x] by a process p and as REG[y] (where y not equal x) by another process q. Moreover, the register known as REG[a] by a process p and the register known as REG[b] by a process q can be the same physical register. It is assumed that each process has a unique identifier that can only be compared for equality. This article is on solving the d-election problem, in which it is required to elect at least one and at most d leaders, in such an anonymous shared memory system. We notice that the 1-election problem is the familiar leader election problem. Let n be the number of processes and m the size of the anonymous memory (number of atomic registers). The article shows that the condition gcd(m, n) <= d is necessary and sufficient for solving the d-election problem, where communication is through read/write or read+modify+write registers. The algorithm used to prove the sufficient condition relies on Bezout's Identity - a Diophantine equation relating numbers according to their Greatest Common Divisor. Furthermore, in the process of proving the sufficient condition, it is shown that 1-leader election can be solved using only a single read/write register (which refutes a 1989 conjecture stating that three non-anonymous registers are necessary), and that the exact d-election problem, where exactly d leaders must be elected, can be solved if and only if gcd(m, n) divides d.

关键词： Anonymous register Asynchrony Atomic register Bezout Identity Bounded register concurrent algorithm Equality-based comparison Leader election Process identity RW register Symmetric algorithm Symmetry breaking

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Hazard Pointer Protection of Structures with Immutable Links 20

Brief Announcement: Hazard Pointer Protection of Structures ...

引用

39th Symposium on Principles of Distributed Computing

作者： Michael, Maged M. Facebook New York NY 10003 USA

ISBN: (纸本)9781450375825

The hazard pointer method [4] for safe reclamation is capable of protecting individual dynamic objects, including individual nodes of linked structures. However, on its own, it does not protect the descendants of protected nodes for unconditional traversal. We present a new algorithm that extends the hazard pointer algorithm to support unconditional traversal though immutable links of acyclic structures. It has an important added advantage of allowing the reclamation of nodes at any depth with their ancestors in the same pass over hazard pointers. Achieving these advantages does not incur any extra computing cost in protection operations, which are the common case. A counter is added to each object for holding the number of inbound immutable links. Such counters are updated when setting and clearing immutable links, which can happen at most once per link in the lifetime of an object. The algorithm is implemented and used in the Facebook Folly open-source C++ library [1].

关键词： hazard pointer safe reclamation concurrent algorithm

来源：评论

学校读者我要写书评

暂无评论

Anonymous Read/Write Memory: Leader Election and De-anonymization 26th

Anonymous Read/Write Memory: Leader Election and De-anonymiz...

引用

26th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Godard, Emmanuel Imbs, Damien Raynal, Michel Taubenfeld, Gadi Univ Aix Marseille LIS Marseille France Univ Rennes IRISA Rennes France Polytech Univ Dept Comp Kowloon Hong Kong Peoples R China Interdisciplinary Ctr IL-46150 Herzliyya Israel

ISBN: (纸本)9783030249212;9783030249229

Anonymity has mostly been studied in the context where processes have no identity. A new notion of anonymity was recently introduced at PODC 2017, namely, this notion considers that the processes have distinct identities but disagree on the names of the read/write registers that define the shared memory. As an example, a register named A by a process p and a shared register named B by another process q may correspond to the very same register X, while the same name C may correspond to different registers for p and q. Recently, a memory-anonymous deadlock-free mutual exclusion algorithm has been proposed by some of the authors. This article addresses two different problems, namely election and memory de-anonymization. Election consists of electing a single process as a leader that is known by every process. Considering the shared memory as an array of atomic read/write registers SM[1..m], memory de-anonymization consists in providing each process pi with a mapping function map(i)() such that, for any two processes pi and p(j) and any integer x is an element of[1..m], map(i)(x) and map(j)(x) allow them to address the same register. Let n be the number of processes and alpha a positive integer. The article presents election and de-anonymization algorithms for m = alpha n+ ss registers, where ss is equal to 1, n- 1, or belongs to a set denoted M(n) (which characterizes the values for which mutual exclusion can be solved despite anonymity). The de-anonymization algorithms are based on the use of election algorithms. The article also shows that the size of the permanent control information that, due to de-anonymization, a register must save forever, can be reduced to a single bit.

关键词： Anonymous registers Asynchronous system Atomic read/write registers concurrent algorithm Leader election Local memory Mapping Memory de-anonymization Mutual exclusion Synchronization

来源：评论

学校读者我要写书评

暂无评论

Mutex-Based De-anonymization of an Anonymous Read/Write Memory 7th

Mutex-Based De-anonymization of an Anonymous Read/Write Memo...

引用

7th International Conference on Networked Systems (NETYS)

作者： Godard, Emmanuel Imbs, Damien Raynal, Michel Taubenfeld, Gadi Univ Aix Marseille LIS Marseille France Univ Rennes IRISA Rennes France Polytechn Univ Hung Hom Dept Comp Hong Kong Peoples R China Interdisciplinary Ctr IL-46150 Herzliyya Israel

ISBN: (纸本)9783030312770;9783030312763

Anonymous shared memory is a memory in which processes use different names for the same shared read/write register. As an example, a shared register named A by a process p and a shared register named B by another process q can correspond to the very same register X, and similarly for the names B at p and A at q which can correspond to the same register Y not equal X. Hence, there is a permanent disagreement on the register names among the processes. This new notion of anonymity was recently introduced by G. Taubenfeld (PODC 2017), who presented several memory-anonymous algorithms and impossibility results. This paper introduces a new problem, that consists in "deanonymizing" an anonymous shared memory. To this end, it presents an algorithm that, starting with a shared memory made up of m anonymous read/write atomic registers (i.e., there is no a priori agreement on their names), allows each process to compute a local addressing mapping, such that all the processes agree on the names of each register. The proposed construction is based on an underlying deadlock-free mutex algorithm for n >= 2 processes (recently proposed in a paper co-authored by some of the authors of this paper), and consequently inherits its necessary and sufficient condition on the size m of the anonymous memory, namely m must belong to the set M(n) = {m : such that l : (sic) 1 < l <= n : gcd(l, m) = 1} \ {1}. This algorithm, which is also symmetric in the sense process identities can only be compared by equality, requires the participation of all the processes;hence it can be part of the system initialization. Last but not least, the proposed algorithm has a noteworthy first-class property, namely, its simplicity.

关键词： Anonymity Anonymous shared memory Asynchronous system Atomic read/write register concurrent algorithm Deadlock-freedom Local memory Mapping function Mutual exclusion Simplicity Synchronization

来源：评论

学校读者我要写书评

暂无评论

Recoverable Mutual Exclusion with Abortability 7th

Recoverable Mutual Exclusion with Abortability

引用

7th International Conference on Networked Systems (NETYS)

作者： Jayanti, Prasad Joshi, Anup Dartmouth Coll Hanover NH 03755 USA

ISBN: (纸本)9783030312770;9783030312763

In light of recent advances in non-volatile main memory technology, there has been a flurry of research in designing algorithms that are resilient to process crashes. As a result of main memory non-volatility, a process is allowed to crash any time during the execution, without affecting the state of the data stored in the main memory. With the assumption that a process eventually restarts after a crash, prior works have focused on designing mutual exclusion algorithms that use the non-volatile main memory to recover from such crashes. Such mutual exclusion algorithms that provide multiple processes with a mutually exclusive access to a shared resource in the presence of process crashes are called Recoverable Mutual Exclusion (RME) algorithms. We present the first RME algorithm where a process has the ability to abort executing the algorithm, if it decides to give up its request for a shared resource before being granted access to that resource. With n being the maximum number of processes for which the algorithm is designed, in the absence of a crash our algorithm guarantees a worst-case remote memory references (RMR) complexity of O(log n) per passage on the Distributed Shared Memory (DSM) machines, and a complexity of O(log n) or O(n) on Cache Coherent (CC) machines, depending on how caches are managed.

关键词： concurrent algorithm Synchronization Mutual exclusion Recoverable algorithm Fault tolerance Non-volatile main memory Shared memory Multi-core algorithms

来源：评论

学校读者我要写书评

暂无评论

A Recoverable Mutex algorithm with Sub-logarithmic RMR on Both CC and DSM 19

A Recoverable Mutex Algorithm with Sub-logarithmic RMR on Bo...

引用

38th ACM Symposium on Principles of Distributed Computing (PODC)

作者： Jayanti, Prasad Jayanti, Siddhartha Joshi, Anup Dartmouth Coll Hanover NH 03755 USA MIT Cambridge MA 02139 USA

ISBN: (纸本)9781450362177

In light of recent advances in non-volatilemain memory technology, Golab and Ramaraju reformulated the traditional mutex problem into the novel Recoverable Mutual Exclusion (RME) problem. In the best known solution for RME, due to Golab and Hendler from PODC 2017, a process incurs at most O(log n/log log n) remote memory references (RMRs) per passage on a system with n processes, where a passage is an interval from when a process enters the Try section to when it subsequently returns to Remainder. Their algorithm, however, guarantees this bound only for cache-coherent (CC) multiprocessors, leaving open the question of whether a similar bound is possible for distributed shared memory (DSM) multiprocessors. We answer this question affirmatively by designing an algorithm for a system with n processes, such that, it satisfies the same complexity bound as Golab and Hendler's for both CC and DSM multiprocessors. Our algorithm has some additional advantages over Golab and Hendler's: (i) its Exit section is wait-free, (ii) it uses only the Fetch-and-Store instruction, and (iii) on a CC machine our algorithm needs each process to have a cache of only O(1) words, while their algorithm needs a cache of size that is a function of n.

关键词： concurrent algorithm synchronization mutual exclusion recoverable algorithm fault tolerance non-volatile main memory shared memory multi-core algorithms

来源：评论

学校读者我要写书评

暂无评论

BSP abstract state machines capture bulk synchronous parallel computations

引用

SCIENCE OF COMPUTER PROGRAMMING 2019年 184卷 102319-000页

作者： Ferrarotti, Flavio Gonzalez, Senen Schewe, Klaus-Dieter Software Competence Ctr Hagenberg Hagenberg Austria P&T Connected Hagenberg Austria Zhejiang Univ UIUC Inst Haining Peoples R China

The bulk synchronous parallel (BSP) bridging model is a model for concurrent computations with alternating computation and communication phases between programs running on different processors. In a computation phase the programs proceed independently and asynchronously until a barrier is reached. In a communication phase initiated by all programs having reached the barrier only messages between the programs are exchanged until normal processing can be continued. In this article we present a behavioural theory for BSP computations comprising an axiomatisation of the BSP model, the definition of a restricted class of concurrent abstract state machines, which we call BSP abstract state machines, and the proof that BSP abstract state machines capture BSP computations as defined by the axiomatisation. We illustrate the use of BSP abstract state machines on map-reduce. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Bulk synchronous parallel bridging model Abstract state machine concurrent algorithm Behavioural theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：