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

4th IEEE International Conference on Parallel, Distributed and Grid Computing (IEEE PDGC)

作者： Mishra, Richa Saini, Poonam PEC Univ Technol Dept Comp Sci & Engn Chandigarh India

ISBN: (纸本)9781509036691

Termination Detection (TD) is a fundamental problem of distributed systems. It is the process to determine whether the computations over a network has completed or not. However, certain environment specific features and limitations viz, mobility of nodes, change in network topology, failure and disconnection of nodes etc., pose a challenge to TD in dynamic environment. The two mechanisms-weight throwing and diffusing computation technique have been widely used to solve the problem of TD. In the paper, we have proposed a decentralized hybrid technique using weight throwing and diffusing computation approach to solve the problem of TD in Mobile Ad hoc Network (MANETs). The proposed algorithm allows any node in the network to detect termination and makes sure that disconnection of nodes does not pose challenge in the way of detection of termination. An extension to the proposed model has also been introduced which deals with TD in scalable environment.

关键词： Credit Distribution diffusing computation Termination Detection Weight Throwing

来源：评论

学校读者我要写书评

暂无评论

TERMINATION DETECTION OF diffusing computationS IN COMMUNICATING SEQUENTIAL PROCESSES

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1982年第1期4卷 37-43页

作者： MISRA, J CHANDY, KM Department of Computer Sciences College of Natural Sciences The University of Texas at Austin Austin TX

In this paper it is shown how the Dijkstra-Scholten scheme for termination detection in a diffusing computation can be adapted to detect termination or deadlock in a network of communicating sequential processes as de... 详细信息

关键词： diffusing computation distributed systems networks of processes termination detection

来源：评论

学校读者我要写书评

暂无评论

DISTRIBUTED computation ON GRAPHS - SHORTEST-PATH ALGORITHMS

引用

COMMUNICATIONS OF THE ACM 1982年第11期25卷 833-837页

作者： CHANDY, KM MISRA, J Univ. of Texas Austin

We use the paradigm of diffusing computation, introduced by Dijkstra and Scholten, to solve a class of graph problems. We present a detailed solution to the problem of computing shortest paths from a single vertex to ... 详细信息

关键词： depth first search diffusing computation distributed computation negative cycle shortest path

来源：评论

学校读者我要写书评

暂无评论

A distributed graph algorithm for the detection of local cycles and knots

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1998年第8期9卷 748-757页

作者： Boukerche, A Tropper, C Univ N Texas Dept Comp Sci Denton TX 76203 USA McGill Univ Sch Comp Sci Montreal PQ Canada

In this paper, a distributed cycle/knot detection algorithm for general graphs is presented. The algorithm distinguishes between cycles and knots and is the first algorithm to our knowledge which does so. It is especially relevant to an application such as parallel simulation in which 1) cycles and knots can arise frequently, 2) the size of the graph is very large, and 3) it is necessary to know if a given node is in a cycle or a knot. It requires less communication than previous algorithms-2m vs. (at least) (4m) for the Chandy and Misra algorithm, where m is the number of links in the graph. It requires O (nlog (n)) bits of memory, where n is the number of nodes. The algorithm differs from the classical diffusing computation methods through its use of incomplete search messages to speed up the computation. We introduce a marking scheme in order to identify strongly connected subcomponents of the graph which cannot reach the initiator of the algorithm. This allows us to distinguish between the case in which the initiator is in a cycle (only) or is in a knot.

关键词： Cycle diffusing computation Distributed Deadlock Detection Knot Distributed Simulation

来源：评论

学校读者我要写书评

暂无评论

ALGORITHMS FOR DISTRIBUTED TERMINATION DETECTION

引用

DISTRIBUTED COMPUTING 1987年第3期2卷 161-175页

作者： MATTERN, F 1. Department of Computer Science SFB124 University of Kaiserslautern P. O. Box 3049 D-6750 Kaiserslautern Federal Republic of Germany

The termination problem for distributed computations is analyzed in the general context of asynchronous communication. In the underlying computational model it is assumed that messages take an arbitrary but finite time and do not necessarily obey the FIFO rule. Time diagrams are used as a graphic means of representing the overall communication scheme, giving a clear insight into the difficulties involved (e.g., lack of global state or time, inconsistent time cuts) and suggesting possible solutions.

关键词： Distributed termination Termination detection Asynchronous communication systems Distributed programming Decentralized control Atomic model of computation Global snapshots Communication deadlock detection Global quiescence diffusing computation

来源：评论

学校读者我要写书评

暂无评论

DISTRIBUTED RESET

引用

IEEE TRANSACTIONS ON COMPUTERS 1994年第9期43卷 1026-1038页

作者： ARORA, A GOUDA, M UNIV TEXAS DEPT COMP SCI AUSTIN TX 78712 USA

We design a reset subsystem that can be embedded in an arbitrary distributed system in order to allow the system processes to reset the system when necessary. Our design is layered, and comprises three main components: a leader election, a spanning tree construction, and a diffusing computation. Each of these components is self-stabilizing in the following sense. If the coordination between the up processes in the system is ever lost (due to failures or repairs of processes and channels) then each component eventually reaches a state where coordination is regained. This capability makes our reset subsystem very robust: it can tolerate fail-stop failures and repairs of processes and channels even when a reset is in progress.

关键词： RELIABILITY FAULT-TOLERANCE SELF-STABILIZATION ALGORITHMS LEADER ELECTION SPANNING TREE diffusing computation

来源：评论

学校读者我要写书评

暂无评论

Accurate and Efficient Counting in Dynamic Networks 33

Accurate and Efficient Counting in Dynamic Networks

引用

IEEE 33rd International Symposium on Reliable Distributed Systems

作者： Yang, Zhiwei Wu, Weigang Chen, Yishun Lin, Xiaola Sun Yat Sen Univ Dept Comp Sci Guangzhou 510006 Guangdong Peoples R China Zhongkai Univ Agr & Engn Coll Computat Sci Guangzhou 510006 Guangdong Peoples R China SYSU CMU Shunde Int Joint Res Inst Shunde Peoples R China

ISBN: (纸本)9781479955848

Dynamic network is the abstraction of networks with frequent topology changes arising from node mobility or other reasons. With the model of dynamic network, fundamental distributed computing problems can be formally studied with rigorous correctness. In this work, we study the counting problem, which plays a significant role in many applications, such as all-to-all information dissemination. Existing counting algorithms for dynamic networks are mostly estimation based and randomized, and cannot achieve accurate results deterministically. To address this problem, we adopt the diffusing computation approach in this paper. Although this approach has been widely used to solve different distributed computing problems, due to dynamic topology changes, existing diffusing computation algorithms cannot work under dynamic network models. To address such challenge, we firstly define a new dynamicity model, named (Q, S)-distance, which is used to describe dynamic changes of information propagation time. Based on (Q, S)-distance, we design two different counting algorithms. The first algorithm focuses on extending typical diffusing computation approach by handling topology changes. Different from existing algorithms, which have two phases, our algorithms contain three phases and the new phase is used to determine and notify the termination of tree growing, which the major challenge is caused by topology dynamicity. The second algorithm further extends the first one by incorporating a cluster-based hierarchy to reduce communication cost. The correctness of both the algorithms is formally proved and their performances in time cost and communication cost are analyzed.

关键词： counting dynamic network diffusing computation distributed algorithm cluster

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：