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

Atomic Read/Write Memory in Signature-Free Byzantine asynchronous message-passing systems

THEORY OF COMPUTING systemS 2017年第4期60卷 677-694页

作者： Mostefaoui, Achour Petrolia, Matoula Raynal, Michel Jard, Claude Univ Nantes LINA F-44322 Nantes France Inst Univ Francex Nantes France Univ Rennes IRISA F-35042 Rennes France

This article presents a signature-free distributed algorithm which builds an atomic read/write shared memory on top of a fully connected peer-to-peer n-process asynchronous message-passing system in which up to t < n/3 processes may commit Byzantine failures. From a conceptual point of view, this algorithm is designed to be as close as possible to the algorithm proposed by Attiya, Bar-Noy and Dolev. J. ACM 42(1), 121-132 (1995), which builds an atomic register in an n-process asynchronous message-passing system where up to t < n/2 processes may crash. The proposed algorithm is particularly simple. It does not use cryptography to cope with Byzantine processes, and is optimal from a t-resilience point of view (t < n/3). A read operation requires O(n) messages, and a write operation requires O(n (2)) messages.

关键词： asynchronous message-passing system Atomic read/write register Byzantine process Linearizability Reliable broadcast abstraction

来源：评论

学校读者我要写书评

暂无评论

Implementing Snapshot Objects on Top of Crash-Prone asynchronous message-passing systems

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED systemS 2018年第9期29卷 2033-2045页

作者： Delporte-Gallet, Carole Fauconnier, Hugues Rajsbaum, Sergio Raynal, Michel Univ Paris Diderot IRIF GANG F-75013 Paris France Univ Nacl Autonoma Mexico Inst Matemat Mexico City 04510 DF Mexico Univ Rennes IRISA F-35000 Rennes France Hong Kong Polytech Univ Hong Kong Hong Kong Peoples R China

In asynchronous crash-prone read/write shared-memory systems there is the notion of a snapshot object, which simulates the behavior of an array of single-writer/multi-reader (SWMR) shared registers that can be read atomically. Processes in the system can access the object invoking (any number of times) two operations, denoted write() and snapshot(). A process invokes write() to update the value of its register in the array. When it invokes snapshot(), the process obtains the values of all registers, as if it read them simultaneously. It is known that a snapshot object can be implemented on top of SWMR registers, tolerating any number of process failures. Snapshot objects provide a level of abstraction higher than individual SWMR registers, and they simplify the design of applications. Building a snapshot object on an asynchronous crash-prone message-passing system has similar benefits. The object can be implemented by using the known simulations of a SWMR shared memory on top of an asynchronous message-passing system (if less than half the processes can crash), and then build a snapshot object on top of the simulated SWMR memory. This paper presents an algorithm that implements a snapshot object directly on top of the message-passing system, without building an intermediate layer of a SWMR shared memory. To the authors knowledge, the proposed algorithm is the first providing such a direct construction. The algorithm is more efficient than the indirect solution, yet relatively simple.

关键词： asynchronous message-passing system atomic read/write register linearizability process crash failure snapshot object

来源：评论

学校读者我要写书评

暂无评论

Time-efficient read/write register in crash-prone asynchronous message-passing systems

引用

COMPUTING 2019年第1期101卷 3-17页

作者： Mostefaoui, Achour Raynal, Michel Roy, Matthieu Univ Nantes LINA Nantes France Univ Rennes 1 IRISA Rennes France Hong Kong Polytech Univ Dept Comp Hung Hom Hong Kong Peoples R China Univ Toulouse CNRS LAAS Toulouse France

The atomic register is one of the most basic and useful object of computing science, and its simple read-write semantics is appealing when programming distributed systems. Hence, its implementation on top of crash-prone asynchronous message-passing systems has received a lot of attention. It was shown that having a strict minority of processes that may crash is a necessary and sufficient requirement to build an atomic register on top of a crash-prone asynchronous message-passing system. This paper visits the notion of a fast implementation of an atomic register, and presents a new time-efficient asynchronous algorithm that reduces latency in many cases: a write operation always costs a round-trip delay, while a read operation costs a round-trip delay in favorable circumstances (intuitively, when it is not concurrent with a write). When designing this algorithm, the design spirit was to be as close as possible to the original algorithm proposed by Attiya, Bar-Noy, and Dolev.

关键词： asynchronous message-passing system Atomic read write register Concurrency Fast operation Process crash failure Synchronous behavior Time-efficient operation

来源：评论

学校读者我要写书评

暂无评论

A simple proof of the necessity of the failure detector Σ to implement an atomic register in asynchronous message-passing systems

引用

INFORMATION PROCESSING LETTERS 2010年第4期110卷 153-157页

作者： Bonnet, Francois Raynal, Michel Univ Rennes 1 IRISA F-35042 Rennes France

This paper presents a simple proof that shows that the quorum failure detector class (denoted Sigma) is the weakest failure detector class required to implement all atomic read/write register in all asynchronous message-passing system prone to all arbitrary number of process crashes. This proof is based on a new reduction algorithm ill which all the variables are bounded. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Concurrency Distributed algorithms Fault-tolerance Theory of computation asynchronous message-passing system Atomic register Weakest failure detector

来源：评论

学校读者我要写书评

暂无评论

Time-Efficient Read/Write Register in Crash-Prone asynchronous message-passing systems 4th

Time-Efficient Read/Write Register in Crash-Prone Asynchrono...

引用

4th International Conference on Networked systems (NETYS)

作者： Mostefaoui, Achour Raynal, Michel Univ Nantes LINA F-44322 Nantes France Inst Univ France Paris France Univ Rennes IRISA F-35042 Rennes France

ISBN: (纸本)9783319461403;9783319461397

The atomic register is certainly the most basic object of computing science. Its implementation on top of an n-process asynchronous message-passing system has received a lot of attention. It has been shown that t < n/2 (where t is the maximal number of processes that may crash) is a necessary and sufficient requirement to build an atomic register on top of a crash-prone asynchronous message-passing system. Considering such a context, this paper visits the notion of a fast implementation of an atomic register, and presents a new time-efficient asynchronous algorithm. Its time-efficiency is measured according to two different underlying synchrony assumptions. Whatever this assumption, a write operation always costs a round-trip delay, while a read operation costs always a round-trip delay in favorable circumstances (intuitively, when it is not concurrent with a write). When designing this algorithm, the design spirit was to be as close as possible to the one of the famous ABD algorithm (proposed by Attiya, Bar-Noy, and Dolev).

关键词： asynchronous message-passing system Atomic read/write register Concurrency Fast operation Process crash failure Synchronous behavior Time-efficient operation

来源：评论

学校读者我要写书评

暂无评论

Stabilizing Server-Based Storage in Byzantine asynchronous message-passing systems [Extended Abstract] 15

Stabilizing Server-Based Storage in Byzantine Asynchronous M...

引用

34th Annual ACM Symposium on Principles of Distributed Computing (PODC)

作者： Bonomi, Silvia Dolev, Shlomi Potop-Butucaru, Maria Raynal, Michel Univ Roma La Sapienza DIAG Rome Italy Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Univ P&M Curie LIP6 Paris France Univ Rennes IRISA Inst Univ France Rennes France

ISBN: (纸本)9781450336178

A stabilizing Byzantine single-writer single-reader (SWSR) regular register, which stabilizes after the first invoked write operation, is first presented. Then, new/old ordering inversions are eliminated by the use of a (bounded) sequence number for writes, obtaining a practically stabilizing SWSR atomic register. A practically stabilizing Byzantine single-writer multi-reader (SWMR) atomic register is then obtained by using several copies of SWSR atomic registers. Finally, bounded time-stamps, with a time-stamp per writer, together with SWMR atomic registers, are used to construct a practically stabilizing Byzantine multi-writer multi-reader (MWMR) atomic register. In a system of n servers implementing an atomic register, and in addition to transient failures, the constructions tolerate t < n/8 Byzantine servers if communication is asynchronous, and t < n/3 Byzantine servers if it is synchronous. The noteworthy feature of the proposed algorithms is that (to our knowledge) these are the first that build an atomic read/write storage on top of asynchronous servers prone to transient failures, and where up to t of them can be Byzantine.

关键词： asynchronous message-passing system Atomic read/write register Byzantine server Clients/servers architecture Distributed algorithm Fault-tolerance Read/write register Regular register Self-stabilization Transient failures

来源：评论

学校读者我要写书评

暂无评论

Implementing Snapshot Objects on Top of Crash-Prone asynchronous message-passing systems 16th

Implementing Snapshot Objects on Top of Crash-Prone Asynchro...

引用

16th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP)

作者： Delporte-Gallet, Carole Fauconnier, Hugues Rajsbaum, Sergio Raynal, Michel Univ Paris Diderot IRIF Paris France Univ Nacl Autonoma Mexico Inst Matemat Mexico City 04510 DF Mexico Univ Rennes IUF Rennes France Univ Rennes IRISA Rennes France

ISBN: (纸本)9783319495835;9783319495828

Distributed snapshots, as introduced by Chandy and Lamport in the context of asynchronous failure-free message-passing distributed systems, are consistent global states in which the observed distributed application might have passed through. It appears that two such distributed snapshots cannot necessarily be compared (in the sense of determining which one of them is the "first"). Differently, snapshots introduced in asynchronous crash-prone read/write distributed systems are totally ordered, which greatly simplify their use by upper layer applications. In order to benefit from shared memory snapshot objects, it is possible to simulate a read/write shared memory on top of an asynchronous crash-prone message-passing system, and build then snapshot objects on top of it. This algorithm stacking is costly in both time and messages. To circumvent this drawback, this paper presents algorithms building snapshot objects directly on top of asynchronous crash-prone message-passing system. "Directly" means here "without building an intermediate layer such as a read/write shared memory". To the authors knowledge, the proposed algorithms are the first providing such constructions. Interestingly enough, these algorithms are efficient and relatively simple.

关键词： asynchronous message-passing system Atomic read/write register Linearizability Process crash failure Snapshot object

来源：评论

学校读者我要写书评

暂无评论

Intrusion-Tolerant Broadcast and Agreement Abstractions in the Presence of Byzantine Processes

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED systemS 2016年第4期27卷 1085-1098页

作者： Mostefaoui, Achour Raynal, Michel Univ Nantes LINA F-44322 Nantes France Univ Rennes Inst Univ France F-35042 Rennes France Univ Rennes IRISA F-35042 Rennes France

A process commits a Byzantine failure when its behavior does not comply with the algorithm it is assumed to execute. Considering asynchronous message-passing systems, this paper presents distributed abstractions, and associated algorithms, that allow non-faulty processes to correctly cooperate, despite the uncertainty created by the net effect of asynchrony and Byzantine failures. These abstractions are broadcast abstractions (namely, no-duplicity broadcast, reliable broadcast, and validated broadcast), and agreement abstraction (namely, consensus). While no-duplicity broadcast and reliable broadcast are well-known one-to-all communication abstractions, validated broadcast is a new all-to-all communication abstraction designed to address agreement problems. After having introduced these abstractions, the paper presents an algorithm implementing validated broadcast on top of reliable broadcast. Then the paper presents two consensus algorithms, which are reductions of multivalued consensus to binary consensus. The first one is a generic algorithm, that can be instantiated with unreliable broadcast or no-duplicity broadcast, while the second is a consensus algorithm based on validated broadcast. Finally, a third algorithm is presented that solves the binary consensus problem. This algorithm is a randomized algorithm based on validated broadcast and a common coin. The presentation of all the abstractions and their algorithms is done incrementally.

关键词： Abstraction level agreement asynchronous message-passing system broadcast abstraction byzantine process common coin consensus distributed algorithm fault-tolerance intrusion-tolerance message validation reliable broadcast signature-free algorithm

来源：评论

学校读者我要写书评

暂无评论

Byzantine-tolerant causal broadcast

引用

THEORETICAL COMPUTER SCIENCE 2021年 885卷 55-68页

作者： Auvolat, Alex Frey, Davide Raynal, Michel Taiani, Francois Ecole Normale Super F-75230 Paris France Univ Rennes CNRS INRIA IRISA F-35000 Rennes France Polytech Univ Dept Comp Hong Kong Peoples R China

Causal broadcast is a communication abstraction built on top of point-to-point send/receive networks that ensures that any two messages whose broadcasts are causally related (as captured by Lamport's "happened before" relation) are delivered in their sending order. Several causal broadcast algorithms have been designed for failure-free and crash-prone asynchronous message-passing systems. This article first gives a formal definition of a causal broadcast abstraction in the presence of Byzantine processes, in the form of two equivalent characterizations, and then presents a simple causal broadcast algorithm that implements it. The main difficulty in the design and the proof of this algorithm comes from the very nature of Byzantine faults: Byzantine processes may have arbitrary behavior, and the algorithm must ensure that correct processes (i) maintain a coherent view of causality and (ii) are never prevented from communicating between themselves. To this end, the algorithm is built modularly, namely it works on top of any Byzantine-tolerant reliable broadcast algorithm. Due to this modularity, the proposed algorithm is easy to understand and inherits the computability assumptions (notably the maximal number of processes that may be Byzantine) and the message/time complexities of the underlying reliable broadcast on top of which it is built. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Algorithm asynchronous message-passing system Byzantine process Causal message delivery Fault-tolerance Modularity Reliable broadcast Simplicity

来源：评论

学校读者我要写书评

暂无评论

Read/write shared memory abstraction on top of asynchronous Byzantine message-passing systems

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2016年 93-94卷 1-9页

作者： Imbs, Damien Rajsbaum, Sergio Raynal, Michel Stainer, Julien Univ Bremen Dept Math D-28359 Bremen Germany Inst Univ France Paris France Univ Rennes IRISA F-35042 Rennes France Ecole Polytech Fed Lausanne Distributed Programming Lab CH-1015 Lausanne Switzerland Univ Nacl Autonoma Mexico Inst Matemat Mexico City DF Mexico

This paper is on the construction and use of a shared memory abstraction on top of an asynchronous message-passing system in which up to t processes may commit Byzantine failures. This abstraction consists of arrays of n single-writer/multi-reader atomic registers, where n is the number of processes. These registers enable Byzantine tolerance by recording the whole history of values written to each one of them. A distributed algorithm building such a shared memory abstraction is first presented. This algorithm assumes t < n/3, which is shown to be a necessary and sufficient condition for such a construction. Hence, the algorithm is resilient-optimal. Then the paper presents distributed objects built on top of this read/write shared memory abstraction, which cope with Byzantine processes. As illustrated by these objects, the proposed shared memory abstraction is motivated by the fact that, for a lot of problems, algorithms are simpler to design and prove correct in a shared memory system than in a message-passing system. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Approximate agreement asynchronous message-passing system Atomic read/write register Broadcast abstraction Byzantine process Distributed computing message-passing system Quorum Reliable broadcast Reliable shared memory Single-writer/multi-reader register t-Resilience

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：