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

Signature-Free asynchronous Binary Byzantine Consensus with t < n/3, O(n²) messages, and O(1) Expected Time

JOURNAL OF THE ACM 2015年第4期62卷 1–21页

作者： Mostefaoui, Achour Moumen, Hamouma Raynal, Michel Univ Nantes LINA F-44322 Nantes France Univ Bejaia LMA Bejaia 06000 Algeria Inst Univ France F-35042 Rennes France Univ Rennes IRISA F-35042 Rennes France

This article is on broadcast and agreement in asynchronous message-passing systems made up of n processes, and where up to t processes may have a Byzantine Behavior. Its first contribution is a powerful, yet simple, all-to-all broadcast communication abstraction suited to binary values. This abstraction, which copes with up to t < n/3 Byzantine processes, allows each process to broadcast a binary value, and obtain a set of values such that ( 1) no value broadcast only by Byzantine processes can belong to the set of a correct process, and ( 2) if the set obtained by a correct process contains a single value v, then the set obtained by any correct process contains v. The second contribution of this article is a new round-based asynchronous consensus algorithm that copes with up to t < n/3 Byzantine processes. This algorithm is based on the previous binary broadcast abstraction and a weak common coin. In addition to being signature-free and optimal with respect to the value of t, this consensus algorithm has several noteworthy properties: the expected number of rounds to decide is constant;each round is composed of a constant number of communication steps and involves O(n(2)) messages;each message is composed of a round number plus a constant number of bits. Moreover, the algorithm tolerates message reordering by the adversary (i.e., the Byzantine processes).

关键词： Algorithms Reliability Theory asynchronous message-passing system broadcast abstraction Byzantine process common coin consensus distributed algorithm optimal resilience randomized algorithm signature-free algorithm simplicity

来源：评论

学校读者我要写书评

暂无评论

The weakest failure detector to implement a register in asynchronous systems with hybrid communication

引用

THEORETICAL COMPUTER SCIENCE 2013年 512卷 130-142页

作者： Imbs, Damien Raynal, Michel Inst Univ France Lyon France Univ Rennes 1 IRISA F-35014 Rennes France

This paper introduces an asynchronous crash-prone hybrid system model. The system is hybrid in the way the processes can communicate. On the on side, a process can send messages to any other process. On another side, the processes are partitioned into clusters and each cluster has its own read/write shared memory. In addition to the model, a main contribution of the paper concerns the implementation of an atomic register in this system model. More precisely, a new failure detector (denoted M Sigma) is introduced and it is shown that, when considering the information on failures needed to implement a register, this failure detector is the weakest. To that end, the paper presents an M Sigma-based algorithm that builds a register in the considered hybrid system model and shows that it is possible to extract M Sigma from any failure detector-based algorithm that implements a register in this model. The paper also (a) shows that M Sigma is strictly weaker than Sigma (which is the weakest failure detector to implement a register in a classical message-passing system) and (b) presents a necessary and sufficient condition to implement M Sigma in a hybrid asynchronous communication system. (C) 2012 Elsevier B.V. All rights reserved.

关键词： asynchronous message-passing system Atomic register Distributed algorithm Failure detector Fault-tolerance Hybrid communication Necessity proof Process crash Shared memory system Weakest failure detector

来源：评论

学校读者我要写书评

暂无评论

Money Transfer Made Simple: a Specification, a Generic Algorithm, and its Proof

引用

BULLETIN OF THE EUROPEAN ASSOCIATION FOR THEORETICAL COMPUTER SCIENCE 2020年第132期2020卷 22-43页

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

It has recently been shown that, contrarily to a common belief, money transfer in the presence of faulty (Byzantine) processes does not require strong agreement such as consensus. This article goes one step further: namely, it first proposes a non-sequential specification of the money-transfer object, and then presents a generic algorithm based on a simple FIFO order between each pair of processes that implements it. The genericity dimension lies in the underlying reliable broadcast abstraction which must be suited to the appropriate failure model. Interestingly, whatever the failure model, the money transfer algorithm only requires adding a single sequence number to its messages as control information. Moreover, as a side effect of the proposed algorithm, it follows that money transfer is a weaker problem than the construction of a safe/regular/atomic read/write register in the asynchronous message-passing crash-prone model.

关键词： asynchronous message-passing system Byzantine process Distributed computing Efficiency Fault tolerance FIFO message order Modularity Money transfer Process crash Reliable broadcast Simplicity

来源：评论

学校读者我要写书评

暂无评论

A message-passing and Adaptive Implementation of the Randomized Test-and-Set Object 14

A Message-Passing and Adaptive Implementation of the Randomi...

引用

IEEE 14th International Symposium on Network Computing and Applications NCA

作者： Anceaume, Emmanuelle Castella, Francois Mostefaoui, Achour Sericola, Bruno CNRS IRISA F-75700 Paris France Univ Rennes 1 IRMAR F-35014 Rennes France Univ Nantes LINA F-44035 Nantes France INRIA Rennes Atlantique Rennes France

ISBN: (纸本)9781509018499

This paper presents a solution to the well-known Test-and-Set operation in asynchronous systems prone to process crashes. Test-and-Set is a synchronization operation that, when invoked by a set of processes, returns "yes" to a unique process and returns "no" to all the others. Recently many advances in implementing Test and Set objects have been achieved, however all of them uniquely target the shared memory model. In this paper we propose an implementation of a Test-and-Set object for message passing distributed systems. This implementation can be invoked by any number p of processes. It has an expected step complexity in O(p) and an expected message complexity in O(np), where n is the total number of processes in the system. The proposed Test and Set object is built atop a new basic building block that allows to select a winning group among two groups of processes.

关键词： Test&Set synchronization asynchronous message-passing system crash failures randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Relations Linking Failure Detectors Associated with k-Set Agreement in message-passing systems

Relations Linking Failure Detectors Associated with <i>k</i>...

引用

13th International Symposium on Stabilization, Safety, and Security of Distributed systems (SSS)

作者： Mostefaoui, Achour Raynal, Michel Stainer, Julien Univ Rennes 1 IRISA F-35014 Rennes France

ISBN: (纸本)9783642245497;9783642245503

The k-set agreement problem is a coordination problem where each process is assumed to propose a value and each process that does not crash has to decide a value such that each decided value is a proposed value and at most k different values are decided. While it can always be solved in synchronous systems, k-set agreement has no solution in asynchronous send/receive message-passing systems where up to t >= k processes may crash. A failure detector is a distributed oracle that provides processes with additional information related to failed processes and can consequently be used to enrich the computability power of asynchronous send/receive message-passing systems. Several failure detectors have been proposed to circumvent the impossibility of k-set agreement in pure asynchronous send/receive message-passing systems. Considering three of them (namely, the generalized quorum failure detector Sigma(k), the generalized loneliness failure detector L-k and the generalized eventual leader failure detector Omega(k)) the paper investigates their computability power and the relations that link them. It has three mains contributions: (a) it shows that the failure detector Omega(k) and the eventual version of L-k have the same computational power;(b) it shows that L-k is realistic if and only if k >= n/2;and (c) it gives an exact characterization of the difference between L-k (that is too strong for k-set agreement) and Sigma(k) (that is too weak for k-set agreement).

关键词： asynchronous message-passing system Distributed computability Equivalence Eventual leader Failure detector Fault-tolerance Impossibility Quorum Realistic failure detector Reduction k-Set agreement Theory

来源：评论

学校读者我要写书评

暂无评论

Two-Bit messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone systems 16

Two-Bit Messages are Sufficient to Implement Atomic Read/Wri...

引用

35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

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

ISBN: (纸本)9781450339643

Atomic registers are certainly the most basic objects of computing science. Their 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 presents an algorithm which implements a single-writer multi-reader atomic register with four message types only, and where no message needs to carry control information in addition to its type. Hence, two bits are sufficient to capture all the control information carried by all the implementation messages. Moreover, the messages of two types need to carry a data value while the messages of the two other types carry no value at all. As far as we know, this algorithm is the first with such a sufficiency property on the size of control information carried by messages. It is also particularly efficient from a time complexity point of view,

关键词： asynchronous message-passing system Atomic read-write register message type Process crash failure Sequence number Upper bound

来源：评论

学校读者我要写书评

暂无评论

Reliable Shared Memory Abstraction on Top of asynchronous Byzantine message-passing systems

引用

21st International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Imbs, Damien Rajsbaum, Sergio Raynal, Michel Stainer, Julien Univ Nacl Autonoma Mexico Inst Math Mexico City 04510 DF Mexico Inst Univ France F-75005 Paris France IRISA F-35042 Rennes France

ISBN: (纸本)9783319096209;9783319096193

This paper is on the construction and the 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. Differently from usual atomic registers which record a single value, each of these atomic registers records the whole history of values written to it. A distributed algorithm building such a shared memory abstraction it 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 algorithms built on top of this shared memory abstraction, which cope with up to t Byzantine processes. The simplicity of these algorithms constitutes a strong motivation for such a shared memory abstraction in the presence of Byzantine processes. For a lot of problems, algorithms are more difficult to design and prove correct in a message-passing system than in a shared memory system. Using a protocol stacking methodology, the aim of the proposed abstraction is to allow an easier design (and proof) of distributed algorithms, when the underlying system is an asynchronous message-passing system prone to Byzantine failures.

关键词： APppproximate 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

来源：评论

学校读者我要写书评

暂无评论

The weakest failure detector to implement a register in asynchronous systems with hybrid communication

The weakest failure detector to implement a register in asyn...

引用

13th International Symposium on Stabilization, Safety, and Security of Distributed systems (SSS)

作者： Imbs, Damien Raynal, Michel Inst Univ France Lyon France Univ Rennes 1 IRISA F-35014 Rennes France

ISBN: (纸本)9783642245497

来源：评论

学校读者我要写书评

暂无评论

Signature-Free Broadcast-Based Intrusion Tolerance: Never Decide a Byzantine Value

Signature-Free Broadcast-Based Intrusion Tolerance: Never De...

引用

14th International Conference on Principles of Distributed systems

作者： Mostefaoui, Achour Raynal, Michel Univ Rennes 1 IRISA F-35042 Rennes France

ISBN: (纸本)9783642176524

Providing application processes with strong agreement guarantees despite failures is a fundamental problem of fault-tolerant distributed computing. Correct processes have not to be "polluted" by the erroneous behavior of faulty processes. This paper considers the consensus agreement problem in a setting where some processes can behave arbitrarily (Byzantine behavior). In such a context it is possible that Byzantine processes collude to direct the correct processes to decide on a "bad" value (a value proposed only by faulty processes). The paper has several contributions. It presents a family of consensus algorithms in which no bad value is ever decided by correct processes. These processes always decide a value they have proposed (and this is always the case when they all propose the same value) or a default value perpendicular to. These algorithms are called intrusion-free consensus algorithms. To that end, each consensus algorithm is based on an appropriate underlying broadcast algorithm. One of these abstractions, called validated broadcast is new and allows the design of a resilience-optimal consensus algorithm (i.e., it copes with up to t < n/3 faulty processes where m is the total number of processes). All proposed consensus algorithms assume the underlying system is enriched with additional computational power provided by a binary Byzantine consensus algorithm. The paper presents also a resilience-optimal randomized binary consensus algorithm based on the validated broadcast abstraction. An important feature of all these algorithms lies in the fact that they are signature-free (and hence particularly efficient).

关键词： asynchronous message-passing system Broadcast abstraction Byzantine process Consensus problem Fault-tolerance Intrusion-tolerance Reliable broadcast Resilience Signature-free algorithm Time-free algorithm

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Causal message Ordering 14th

引用

14th International Conference on Parallel Computing Technologies (PaCT)

作者： Mostefaoui, Achour Weiss, Stephane Univ Nantes LS2N F-44322 Nantes France

ISBN: (纸本)9783319629322;9783319629315

Causal broadcast is a classical communication primitive that has been studied for more then three decades and several implementations have been proposed. The implementation of such a primitive has a non negligible cost either in terms of extra information messages have to carry or in time delays needed for the delivery of messages. It has been proved that messages need to carry a control information the size of which is linear with the size of the system. This problem has gained more interest due to new application domains such that collaborative applications are widely used and are becoming massive and social semantic web and linked-data the implementation of which needs causal ordering of messages. This paper proposes a probabilistic but efficient causal broadcast mechanism for large systems with changing membership that uses few integer timestamps.

关键词： asynchronous message-passing system Happened before relation Logical clock message causal ordering Vector clock

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：