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

Agreement in synchronous networks with ubiquitous faults

THEORETICAL COMPUTER SCIENCE 2007年第2-3期384卷 232-249页

作者： Santoro, Nicola Widmayer, Peter Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada ETH Zentrum Inst Theoret Informat Zurich Switzerland

In this paper we are interested in synchronous distributed systems subject to transient and ubiquitous failures. This includes systems where failures will occur on any communication link, systems where every processor will experience at one time or another send or receive failure, etc., and, following a failure, normal functioning resuming after a finite time. Notice that these cases cannot be handled by the traditional component failure models. The model we use is the communication failure model, also called the transinission failure or a dynamic faults or mobile faults model. Using this model, we study the fundamental problem of agreement in synchronous networks of arbitrary topology with ubiquitous faults. We establish bounds on the number of dynamic faults that make any non-trivial form of agreement (even strong majority) impossible;in turn, these bounds express connectivity requirements that must be met to achieve any meaningful form of agreement. We also provide, constructively, bounds on the number of dynamic faults in spite of which any non-trivial form of agreement (even unanimity) is possible. These bounds are shown to be tight for a large class of networks, which includes hypercubes, toruses, rings, and complete graphs;incidentally, we close the existing gap between possibility and impossibility of non-trivial agreement in complete graphs in the presence of dynamic Byzantine faults. None of these results is derivable in the component failure models;in particular, all our possibility results hold in situations for which those models indicate impossibility. (C) 2007 Elsevier B.V. All rights reserved.

关键词： theory of distributed computation synchronous systems dynamic faults mobile faults transmission failure model arbitrary network topology agreement majority bivalency argument limits to computability

来源：评论

学校读者我要写书评

暂无评论

Keynote: Time is not a Healer: Before and After 24

Keynote: Time is not a Healer: Before and After

引用

Proceedings of the 43rd ACM Symposium on Principles of distributed Computing

作者： Nicola Santoro School of Computer Science Carleton University Ottawa Canada

ISBN: (纸本)9798400706684

distributed computing has been concerned with the topics of faults and failures from its very beginning (before PODC was born). The consensus problem was at the forefront of the research efforts, and an extensive body of literature on the subject was developed very quickly (e.g., [5, 6, 11, 20]). The beautiful proof of the impossibility of consensus under asynchrony [7] put to rest the unsuccessful attempts to prove otherwise, and gave an even stronger impetus to the focus on synchronous *** paper Time is not a Healer [16], which we shall denote by {T¬H}, was concerned with the problem of agreement in synchronous systems where failures have mostly a transient and ubiquitous nature; that is, faults can occur anywhere in the system and, following a failure, normal functioning can resume after a finite (although unpredictable) time. These type of dynamic failures, however, could not be handled by the traditional failure models developed for the consensus and related *** the significance and novelty of the scientific and technical contributions of {T¬H}, including the model, the proof technique, and the unexpected results. Incidentally, while known for its results on omissions, {T¬H} contains also tight bounds on corruptions, additions, and the Byzantine combination of all. While known for its impossibility results, it has tight possibility results, which hold in situations for which the traditional models indicate impossibility. Over the decades, triggered by these results, an extensive literature has been developed (e.g., [3, 4, 8, 9, 13, 15, 19, 21]).The relatively recent developments in communication technology and advent of new virtual systems (e.g., wireless mobile networks, social networks) have driven the research in distributed computing to investigate problems (including consensus) in dynamic networks (e.g., [2, 10, 12]); this has inevitably brought to light the immediate connection between such networks and the ones subject to dynamic omiss

关键词： theory of distributed computation synchronous systems dynamic faults agreement dynamic networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：