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

A family of optimal termination detection algorithms

DISTRIBUTED COMPUTING 2007年第2期20卷 141-162页

作者： Mittal, Neeraj Venkatesan, S. Peri, Sathya Univ Texas Dept Comp Sci Richardson TX 75083 USA

An important problem in distributed systems is to detect termination of a distributed computation. A computation is said to have terminated when all processes have become passive and all channels have become empty. In this paper, we present a suite of algorithms for detecting termination of a non-diffusing computation for an arbitrary communication topology under a variety of conditions. All our termination detection algorithms have optimal message complexity. Furthermore, they have optimal detection latency when message processing time is ignored.

关键词： monitoring distributed system termination detection arbitrary communication topology optimal algorithm diffusing and non-diffusing computations simultaneous and delayed initiations single-hop and multi-hop application messages

来源：评论

学校读者我要写书评

暂无评论

On termination detection in an asynchronous distributed system 17

On termination detection in an asynchronous distributed syst...

引用

17th International Conference on Parallel and Distributed Computing Systems

作者： Peri, S Mittal, N Univ Texas Dept Comp Sci Richardson TX 75083 USA

ISBN: (纸本)1880843528

An important problem in distributed systems is to detect termination of a distributed computation. A distributed computation is said to have terminated when all processes have become passive and all channels have become empty. We focus on two attributes of a termination detection algorithm. First, whether the distributed computation starts from a single process or from multiple processes: diffusing computation versus non-diffusing computation. Second, whether the detection algorithm should be initiated along with the computation or can be initiated anytime after the computation has started: simultaneous initiation versus delayed initiation. We show that any termination detection algorithm for a diffusing computation can be transformed into a termination detection algorithm for a non-diffusing computation. We also demonstrate that any termination detection algorithm for simultaneous initiation can be transformed into a termination detection algorithm for delayed initiation. We prove the correctness of our transformations, and show that our transformations have minimal impact on the complexity of the given termination detection algorithm.

关键词： termination detection algorithm transformation diffusing and non-diffusing computations simultaneous and delayed initiations

来源：评论

学校读者我要写书评

暂无评论

Improving the efficacy of a termination detection algorithm

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2008年第1期24卷 159-174页

作者： Peri, Sathya Mittal, Neeraj Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA

An important problem in distributed systems is to detect termination of a distributed computation. A distributed computation is said to have terminated when all processes have become passive and all channels have become empty. We focus on two attributes of a termination detection algorithm. First, whether the distributed computation starts from a single process or from multiple processes: diffusing computation versus non-diffusing computation. Second, whether the detection algorithm should be initiated along with the computation or can be initiated any time after the computation has started: simultaneous initiation versus delayed initiation. We show that any termination detection algorithm for a diffusing computation can be transformed into a termination detection algorithm for a non-diffusing computation. We also demonstrate that any termination detection algorithm for simultaneous initiation can be transformed into a termination detection algorithm for delayed initiation. We prove the correctness of our transformations, and show that our transformations have only a small impact on the performance of the given termination detection algorithm.

关键词： distributed system termination detection algorithm transformation diffusing and non-diffusing computations simultaneous and delayed initiations worst-case and average-case message complexities fault-tolerance

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：