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

Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation Problems

ALGORITHMS 2025年第1期18卷 26-26页

作者： Kshemkalyani, Ajay D. Misra, Anshuman Univ Illinois Dept Comp Sci Chicago IL 60607 USA Purdue Univ Ft Wayne Dept Comp Sci Ft Wayne IN 46805 USA

This paper considers the solvability of several fundamental problems in asynchronous message-passing distributed systems in the presence of Byzantine processes using distributed algorithms. These problems are the following: mutual exclusion, global snapshot recording, termination detection, deadlock detection, predicate detection, causal ordering, spanning tree construction, minimum spanning tree construction, all-all shortest paths computation, and maximal independent set computation. In a distributed algorithm, each process has access only to its local variables and incident edge parameters. We show the impossibility of solving these fundamental problems by proving that they require a solution to the causality determination problem which has been shown to be unsolvable in asynchronous message-passing distributed systems.

关键词： Byzantine fault-tolerance "happened before" relation causality state observation synchronization graph computation distributed system asynchronous message-passing

来源：评论

学校读者我要写书评

暂无评论

Byzantine Fault-Tolerant Causal Ordering 23

Byzantine Fault-Tolerant Causal Ordering

引用

24th International Conference on Distributed Computing and Networking (ICDCN)

作者： Misra, Anshuman Kshemkalyani, Ajay D. Univ Illinois Chicago IL 60607 USA

ISBN: (纸本)9781450397964

Byzantine fault-tolerant causal ordering of messages in asynchronous systems is useful to many applications. Although the problem has been studied for broadcast communication, it has not been examined for unicasts or multicasts in asynchronous systems. In this paper, we use execution histories to prove that it is impossible to solve causal ordering for both unicasts and multicasts in an asynchronous system with one or more Byzantine processes. In view of these impossibility results, we propose the Channel Sync Algorithms to provide causal order of unicasts and multicasts under the Byzantine failure model in synchronous systems, which have a known upper bound on message latency. The Channel Sync Algorithms operate under the synchronous system model, but are inherently asynchronous and offer a high degree of concurrency as lock-step communication is not assumed.

关键词： byzantine fault-tolerance causal order unicast communication causal multicast asynchronous message-passing

来源：评论

学校读者我要写书评

暂无评论

Causal Ordering in the Presence of Byzantine Processes 28

Causal Ordering in the Presence of Byzantine Processes

引用

IEEE 28th International Conference on Parallel and Distributed Systems (IEEE ICPADS)

作者： Misra, Anshuman Kshemkalyani, Ajay D. Univ Illinois Chicago IL 60607 USA

ISBN: (纸本)9781665473156

Causal ordering of messages in distributed systems is important for capturing application-level semantics. To the best of our knowledge, Byzantine fault-tolerant causal ordering has not been attempted for point-to-point communication in an asynchronous setting. In this paper, we first prove that it is impossible to causally order messages under point-to-point communication in an asynchronous system with one or more Byzantine processes. In the face of this impossibility, we then present an algorithm that can causally order messages under point-to-point communication in the face of Byzantine failures, assuming the network provides a known upper bound on the message latency. We also prove that it is impossible to causally order multicasts in an asynchronous setting with one or more Byzantine processes. We then give an extension of our algorithm for unicasts to provide Byzantine fault-tolerant causal ordering of multicasts under the assumption of a known upper bound on the message latency.

关键词： Byzantine fault-tolerance Causal Order Causality asynchronous message-passing Unicast Multicast

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：