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

46th Annual ACM Symposium on Theory of Computing (STOC)

作者： Alistarh, Dan Censor-Hillel, Keren Shavit, Nir MSR Cambridge Cambridge England Technion Haifa Israel MIT Cambridge MA 02139 USA Tel Aviv Univ Tel Aviv Israel MIT CSAIL Cambridge MA 02139 USA

ISBN: (纸本)9781450327107

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.

关键词： Distributed computing shared memory wait-free algorithms lock-free algorithms progress properties schedulers

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Are Lock-free Concurrent algorithms Practically wait-free? 14

Brief Announcement: Are Lock-Free Concurrent Algorithms Prac...

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Alistarh, Dan Censor-Hillel, Keren Shavit, Nir Microsoft Res Redmond WA 98052 USA Technion Haifa Israel MIT Cambridge MA 02139 USA Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9781450329446

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers would prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is in general a complex undertaking, and the resulting algorithms are not always efficient, so most non-blocking commercial code is only lock-free, and the design of efficient wait-free algorithms has been left to the academic community. In [2], we suggest a solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a broad subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.

关键词： Distributed computing shared memory wait-free algorithms lock-free algorithms progress properties schedulers

来源：评论

学校读者我要写书评

暂无评论

Are Lock-free Concurrent algorithms Practically wait-free?

引用

JOURNAL OF THE ACM 2016年第4期63卷 31-31页

作者： Alistarh, Dan Censor-Hillel, Keren Shavit, Nir ETH Inst Theoret Informat CAB J 21-5Univ Str 6 CH-8092 Zurich Switzerland Technion Dept Comp Sci IL-32000 Haifa Israel MIT 32 Vassar St32-G622 Cambridge MA 02139 USA Tel Aviv Univ Comp Sci & Artificial Intelligence Lab Stata Ctr 32 Vassar St32-G622 Cambridge MA 02139 USA

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. Although obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most nonblocking commercial code is only lock-free. This article suggests a simple solution to this problem. We show that for a large class of lock-free algorithms, under scheduling conditions that approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can continue to design simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes to the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1 but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst-case adversary, in a stochastic model capturing their expected asymptotic behavior.

关键词： Distributed computing shared memory wait-free algorithms lock-free algorithms progress properties schedulers

来源：评论

学校读者我要写书评

暂无评论

wait-free implementations in message-passing systems

引用

THEORETICAL COMPUTER SCIENCE 1999年第1期220卷 211-245页

作者： Chaudhuri, S Herlihy, M Tuttle, MR Compaq Cambridge Res Lab Cambridge MA 02139 USA Brown Univ Dept Comp Sci Providence RI 02912 USA Iowa State Univ Dept Comp Sci Ames IA 50011 USA

We study the round complexity of problems in a synchronous, message-passing system with crash failures. We show that if processors start in order-equivalent states, then a logarithmic number of rounds is both necessary and sufficient for them to reach order-inequivalent states. These upper and lower bounds are significant because they establish a complexity threshold below which no nontrivial problem can be solved, but at which certain nontrivial problems do have solutions. This logarithmic lower bound implies a matching lower bound for a variety of decision tasks and concurrent object implementations. In particular, we examine two nontrivial problems for which this lower bound is tight: the strong renaming task, and a wait-free increment register implementation. For each problem, we present a nontrivial algorithm that halts in O(log c) rounds, where c is the number of participating processors. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： distributed algorithms data structures wait-free algorithms message-passing model increment register strong renaming

来源：评论

学校读者我要写书评

暂无评论

Generalized irreducibility of consensus and the equivalence of t-resilient and wait-free implementations of consensus

引用

SIAM JOURNAL ON COMPUTING 2004年第2期34卷 333-357页

作者： Chandra, T Hadzilacos, V Jayanti, P Toueg, S IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Univ Toronto Dept Comp Sci Toronto ON MSS 3H5 Canada Dartmouth Coll Dept Comp Sci Hanover NH 03755 USA

We study the consensus problem, which requires multiple processes with different input values to agree on one of these values, in the context of asynchronous shared memory systems. Prior research focussed either on t-resilient solutions of this problem (which must be correct even if up to t processes crash) or on wait-free solutions (which must be correct despite the crash of any number of processes). In this paper, we show that these two forms of solvability are closely related. Specifically, for all n > t >= 2 and all sets S of shared object types (that include simple read/write registers), there is a t-resilient solution to n-process consensus using objects of types in S if and only if there is a wait-free solution to (t+1)-process consensus using objects of types in S. Our proof of this equivalence uses another result derived in this paper, which is of independent interest. Roughly speaking, this result states that a wait-free solution to (n-1)-process consensus is never necessary in designing a wait-free solution to n-process consensus, regardless of the types of objects available. More precisely, for all n >= 2 and all sets S of shared object types (that include simple read/write registers), if there is a wait-free solution to n-process consensus that uses a wait-free solution to (n-1)-process consensus and objects of types in S, then there is a wait-free solution to n-process consensus that uses only objects of types in S.

关键词： asynchronous distributed computation consensus wait-free algorithms fault tolerant algorithms impossibility results

来源：评论

学校读者我要写书评

暂无评论

wait-free Queues With Multiple Enqueuers and Dequeuers 11

Wait-Free Queues With Multiple Enqueuers and Dequeuers

引用

16th ACM Symposium on Principles and Practice of Parallel Programming

作者： Kogan, Alex Petrank, Erez Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9781450301190

The queue data structure is fundamental and ubiquitous. Lock-free versions of the queue are well known. However, an important open question is whether practical wait-free queues exist. Until now, only versions with limited concurrency were proposed. In this paper we provide a design for a practical wait-free queue. Our construction is based on the highly efficient lock-free queue of Michael and Scott. To achieve wait-freedom, we employ a priority-based helping scheme in which faster threads help the slower peers to complete their pending operations. We have implemented our scheme on multicore machines and present performance measurements comparing our implementation with that of Michael and Scott in several system configurations.

关键词： concurrent queues wait-free algorithms algorithms Performance

来源：评论

学校读者我要写书评

暂无评论

Solvability of consensus: Composition breaks down for nondeterministic types

引用

SIAM JOURNAL ON COMPUTING 1998年第3期28卷 782-797页

作者： Jayanti, P Dartmouth Coll Sudikoff Lab Comp Sci 6211 Hanover NH 03755 USA

Consensus, which requires processes with different input values to eventually agree on one of these values, is a fundamental problem in fault-tolerant computing. We study this problem in the context of asynchronous shared-memory systems. Prior research on consensus focused on its solvability using shared objects of specific types. In this paper, we investigate the following general question: Let T and T' be any two types. Consider the consensus problem among N processes. Suppose that this problem is unsolvable if processes may use only objects of any one type (T or T') for communication. Does it follow that the problem is unsolvable even if processes may use objects of both types? Recent results imply that the answer is positive if T and T' are both deterministic types. We prove that the answer is negative even if one of T and T' is nondeterministic.

关键词： asynchronous distributed computation consensus wait-free algorithms nondeterministic object type

来源：评论

学校读者我要写书评

暂无评论

Simple and efficient bounded concurrent timestamping and the traceable use abstraction

引用

JOURNAL OF THE ACM 1999年第5期46卷 633-666页

作者： Dwork, C Waarts, O IBM Corp Almaden Res Ctr Dept K53 San Jose CA 95120 USA

In a timestamping system, processors repeatedly choose timestamps so that the order of the timestamps obtained reflects the real-time order in which they were requested. Concurrent timestamping systems permit requests by multiple processors to be issued concurrently;in bounded timestamping systems the sizes of the timestamps and the size and number of shared variables are bounded. An algorithm is wait-free if there exists an a priori bound on the number of steps a processor must take in order to make progress, independent of the action or inaction of other processors. Letting n denote the number of processors, we construct a simple wait-free bounded concurrent timestamping system requiring O(n) steps (accesses to shared memory) for a processor to read the current timestamps and determine the order among them, and O(n) steps to generate a timestamp, independent of the actions of other processors. In addition, we introduce and implement the traceable use abstraction, a new primitive providing "inventory control" over values introduced by processors in the course of an algorithm execution. This abstraction has proved to be of great value in converting unbounded algorithms to bounded ones [Attiya and Rachman 1998;Dwork et al. 1992;1993].

关键词： distributed computing distributed timestamps fault-tolerant computing shared memory timestamping systems traceable-use wait-free algorithms

来源：评论

学校读者我要写书评

暂无评论

The topological structure of asynchronous computability

引用

JOURNAL OF THE ACM 1999年第6期46卷 858-923页

作者： Herlihy, M Shavit, N Brown Univ Dept Comp Sci Providence RI 02912 USA Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel

We give necessary and sufficient combinatorial conditions characterizing the class of decision tasks that can be solved in a wail-free manner by asynchronous processes that communicate by reading and writing a shared memory. We introduce a new formalism for tasks, based on notions from classical algebraic and combinatorial topology, in which a task's possible input and output values are each associated with high-dimensional geometric structures called simplicial complexes. We characterize computability in terms of the topological properties of these complexes. This characterization has a surprising geometric interpretation: a task is solvable if and only if the complex representing the task's allowable inputs can be mapped to the complex representing the task's allowable outputs by a function Satisfying certain simple regularity properties. Our formalism thus replaces the "operational" notion of a wait-free decision task, expressed in terms of interleaved computations unfolding in time, by a static "combinatorial" description expressed in terms of relations among topological spaces. This allows us to exploit powerful theorems from the classic literature on algebraic and combinatorial topology. The approach yields the first impossibility results for several long-standing open problems in distributed computing, such as the "renaming" problem of Attiya et al., and the "k-set agreement" problem of Chaudhuri.

关键词： algebraic topology asynchronous distributed computation decision tasks distributed computing homology simplicial complex wait-free algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient and robust sharing of memory in message-passing systems

引用

JOURNAL OF algorithms 2000年第1期34卷 109-127页

作者： Attiya, H Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

A simulation of a wait-free, atomic, single-writer multireader register in an asynchronous message passing system is presented. The simulation can withstand the failure of up to half of the processors and requires O(n) messages (for each read or write operation), assuming there are n + 1 processors in the system. It improves on the previous simulation, which requires O(n(2)) messages (for each read or write operation). The message complexity of the new simulation is within a constant factor of the optimum. The new simulation improves the complexity of algorithms for the following problems in the message-passing model in the presence of processor failures: multiwriter multireader registers, concurrent time-stamp systems, e-exclusion, atomic snapshots, randomized consensus, implementation of data structures, as well as improved fault-tolerant algorithms for any solvable decision task. (C) 2000 Academic Press.

关键词： fault-tolerance shared memory message passing wait-free algorithms processor failures atomic registers simulation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：