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

Randomized k-set agreement in crash-prone and Byzantine asynchronous systems

THEORETICAL COMPUTER SCIENCE 2018年 709卷 80-97页

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

k-Set agreement is a central problem of fault-tolerant distributed computing. Considering a set of n processes, where up to t may commit failures, let us assume that each process proposes a value. The problem consists in defining an algorithm such that each non-faulty process decides a value, at most k different values are decided, and the decided values satisfy some context-depending validity condition. algorithms solving k-set agreement in synchronous message-passing systems have been proposed for different failure models (mainly process crashes, and process Byzantine failures). Differently, k-set agreement cannot be solved in failure-prone asynchronous message-passing systems when t > k. To circumvent this impossibility an asynchronous system must be enriched with additional computational power. Assuming t > k, this paper presents two distributed algorithms that solve k-set agreement in asynchronous message-passing systems where up to t processes may commit crash failures (first algorithm) or more severe Byzantine failures (second algorithm). To circumvent k-set agreement impossibility, this article considers that the underlying system is enriched with the computability power provided by randomization. Interestingly, the algorithm that copes with Byzantine failures is signature-free, and ensures that no value proposed only by Byzantine processes can be decided by a non-faulty process. Both algorithms share basic design principles. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Asynchronous system Broadcast abstraction Byzantine process Coin Crash failure Distributed algorithm k-Set agreement Message-passing system Randomized algorithm signature-free algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Minimal Synchrony for Byzantine Consensus 15

Minimal Synchrony for Byzantine Consensus

引用

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

作者： Bouzid, Zohir Mostfaoui, Achour Raynal, Michel Univ Rennes IRISA Rennes France Univ Nantes LINA F-44322 Nantes France Inst Univ France Paris France

ISBN: (纸本)9781450336178

Solving the consensus problem requires in one way or another that the underlying system satisfies some synchrony assumption. Considering an asynchronous message-passing system of n processes where (a) up to t < n/3 may commit Byzantine failures, and (b) each pair of processes is connected by two uni-directional channels (with possibly different timing properties), this paper investigates the synchrony assumption required to solve consensus, and presents a signature-free consensus algorithm whose synchrony requirement is the existence of a process that is an eventual < t + 1 > bisource. Such a process p is a correct process that eventually has (a) timely input channels from t correct processes and (b) timely output channels to t correct processes ( these input and output channels can connect p to different subsets of processes). As this synchrony condition was shown to be necessary and sufficient in the stronger asynchronous system model (a) enriched with message authentication, and (b) where the channels are bidirectional and have the same timing properties in both directions, it follows that it is also necessary and sufficient in the weaker system model considered in the paper. In addition to the fact that it closes a long-lasting problem related to Byzantine agreement, a noteworthy feature of the proposed algorithm lies in its design simplicity, which is a first-class property.

关键词： Adopt-commit Asynchronous message-passing Byzantine process Consensus Distributed algorithm Eventual timely channel Feasibility condition Lower bound Optimal resilience Reliable broadcast signature-free algorithm Synchrony assumption

来源：评论

学校读者我要写书评

暂无评论

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卷 31-31页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

signature-free Asynchronous Byzantine Consensus with t < n/3 and O(n²) Messages 14

Signature-Free Asynchronous Byzantine Consensus with <i>t</i...

引用

ACM Symposium on Principles of Distributed Computing (PODC)

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

ISBN: (纸本)9781450329446

This paper presents a new round-based asynchronous consensus algorithm that copes with up to t < n/3 Byzantine processes, where n is the total number of processes. In addition of not using signature, not assuming a computationally-limited adversary, while being optimal with respect to the value of t, this algorithm has several noteworthy properties: the expected number of rounds to decide is four, each round is composed of two or three communication steps and involves O(n(2)) messages, and a message is composed of a round number plus a single bit. To attain this goal, the consensus algorithm relies on a common coin as defined by Rabin, and a new extremely simple and powerful broadcast abstraction suited to binary values. The main target when designing this algorithm was to obtain a cheap and simple algorithm. This was motivated by the fact that, among the first-class properties, simplicity -albeit sometimes under-estimated or even ignored- is a major one.

关键词： Abstraction Asynchronous message-passing system Broadcast abstraction Byzantine process Common coin Consensus Distributed algorithm Optimal resilience Randomized algorithm signature-free algorithm Simplicity

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：