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

39th Annual ACM Symposium on Applied Computing (SAC)

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

ISBN: (纸本)9798400702433

Causal ordering is widely used in distributed systems to maintain validity and correctness of data across concurrent updates. Previous work has shown that it is impossible to solve the causal ordering problem under the strong safety condition in cryptography-free Byzantine-prone systems. It has also been shown that it is impossible to solve deterministic causal ordering for unicasts/multicasts in asynchronous systems even under a weaker notion of safety called weak safety. However, inherently asynchronous (round-free) protocols solve causal ordering for unicasts/multicasts in synchronous systems under the weak safety condition. In this paper, we first examine the causal ordering problem under the notion of synchronous rounds. We examine whether causal ordering is solvable by simulating rounds in synchronous systems under fault-free, crash-failure and Byzantine failure models. We then provide a round-based synchronous algorithm for causal ordering of unicasts/multicasts/broadcasts under the strong safety condition. Finally, we provide an overall analysis of solvability of causal ordering in synchronous systems for a variety of system model settings.

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

来源：评论

学校读者我要写书评

暂无评论

message lower bounds via efficient network synchronization

引用

THEORETICAL COMPUTER SCIENCE 2020年 810卷 82-95页

作者： Pandurangan, Gopal Peleg, David Scquizzato, Michele Univ Houston Dept Comp Sci Houston TX 77204 USA Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel Univ Padua Dept Math I-35121 Padua Italy

We present a uniform approach to derive message-time tradeoffs and message lower bounds for synchronous distributed computations using results from communication complexity theory. Since the models used in the classical theory of communication complexity are inherently asynchronous, lower bounds do not directly apply in a synchronous setting. To address this issue, we show a general result called synchronous Simulation Theorem (SST) which allows to obtain message lower bounds for synchronous distributed computations by leveraging lower bounds on communication complexity. The SST is a by-product of a new efficient synchronizer for complete networks, called sigma, which has simulation overheads that are only logarithmic in the number of synchronous rounds with respect to both time and message complexity, even in networks with limited bandwidth. Synchronizer sigma is particularly efficient in simulating synchronous algorithms which employ silence, a situation that occurs when in some round no processor sends any message. In particular, a curious property of this synchronizer, which sets it apart from its predecessors, is that it is time-compressing, and hence in some cases it may result in a simulation that is faster than the original execution. While the SST gives near-optimal message lower bounds up to large values of the number of allowed synchronous rounds r (usually polynomial in the size of the input), it fails to provide meaningful bounds when the synchronous algorithm to be simulated may comprise a very large number of rounds. To complement the bounds provided by the SST, we then derive message lower bounds for the synchronous message-passing model that are unconditional, that is, independent of r, by establishing novel lower bounds for multi-party synchronous communication complexity. We apply our approach to show (almost) tight message-time tradeoffs and message lower bounds for several fundamental problems in the synchronous message-passing model of distribu

关键词： Distributed algorithms synchronous message-passing Communication complexity Lower bounds Synchronizers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：