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

26th International Symposium on Stabilization, Safety, and Security of Distributed Systems

作者： Yamada, Tota Ki, Yonghwan Nagoya Inst Technol Nagoya Aichi Japan

ISBN: (纸本)9783031744976;9783031744983

A Minus Dominating (MD) Function of a graph G = (V, E) (vertical bar V vertical bar = n) is a function that assigns a value from {-1, 0, 1} to each node i. V such that the sum of the values of node i and all its neighboring nodes is positive (i.e., equal to or greater than 1). An MD function is minimal if decreasing the value of any node by 1 causes a violation of the conditions of the MD function. As an extension of the MD function, we introduce the k-Minimal Minus Dominating (MMD) Function (k >= 0), which is a minimal MD function such that no other MD function can be obtained by increasing the values for some nodes by k in total and decreasing the values for some nodes by at least k + 1 in total. Note that any minimal MD function can be referred to as a 0-MMD function. In this paper, we propose a silent self-stabilizing algorithm to solve the 1-Minimal Minus Domination Problem on an arbitrary graph, using a composition technique that repeatedly applies several self-stabilizing algorithms in order, known as loop composition. It converges within O(n(Delta(2) + D)) rounds, where D is the diameter and Delta is the maximum degree of a graph, and each node requires O(Delta(4) log n) bits of memory.

关键词： Distributed System self-stabilizing algorithm Loop Composition Minus Domination

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing algorithm for two disjoint minimal dominating sets

引用

INFORMATION PROCESSING LETTERS 2019年 147卷 38-43页

作者： Srimani, Pradip K. Wang, James Z. Clemson Univ Sch Comp Clemson SC 29634 USA

We propose a new self stabilizing algorithm to compute two mutually disjoint minimal dominating sets in an arbitrary graph G with no isolates (this is always possible due to famous Ore's theorem in [1] that says "In a graph having no isolated nodes, the complement of any minimal dominating set is a dominating set"). We use an unfair central daemon and unique ids of the nodes. The time complexity of our algorithm is O(n(3)), an improvement by a factor of n from that of [2], that uses same assumptions to design an O(n(4)) algorithm, where n is the number of nodes in G. The algorithm uses the concept of running two copies of an algorithm in an interleaving manner such that the state spaces of the two copies are always kept mutually disjoint. We expect our approach will prove useful in designing algorithms for other mutually disjoint predicates in a network graph. (C) 2019 Elsevier B.V. All rights reserved.

关键词： self-stabilizing algorithm Minimal dominating set Mutually disjoint minimal dominating sets Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing algorithm for minimum-depth search of graphs

引用

INFORMATION SCIENCES 1999年第1-4期118卷 241-249页

作者： Chaudhuri, P Kuwait Univ Dept Elect & Comp Engn Safat Kuwait

This paper presents a self-stabilizing algorithm for the minimum-depth search (MDS) of a connected undirected graph on an asynchronous distributed or network model of computation. The algorithm produces a minimum-depth spanning tree (MDST) of the given graph in a distributed manner so that each node of the graph knows its depth and parent. The algorithm is resilient to transient faults and does not require initialization. It has been proved that the algorithm is correct and requires O(n(2)) time, where n is the number of nodes of the graph. (C) 1999 Elsevier Science Inc. All rights reserved.

关键词： self-stabilizing algorithm transient faults undirected graph minimum-depth search algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing algorithm for minimal (α,β)-dominating set

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS- COMPUTER SYSTEMS THEORY 2022年第2期7卷 81-94页

作者： Saadi, Leila Benreguia, Badreddine Arar, Chafik Moumen, Hamouma Univ Batna 2 Comp Sci Dept Batna Algeria

This paper deals with the problem of finding dominating set using self-stabilization paradigm in distributed systems. Usually, members of a dominating set are selected to be as cluster heads in Wireless Sensor Networks (WSN) to ensure a permanent service availability. Since failures occur frequently inside WSN due to limited battery energy, self-stabilizing algorithm allows recomputing the dominating set, and hence the network returns to its ordinary running. Existing works have introduced many variants of self-stabilizing algorithms that compute minimal dominating set S where each node out of S has neighbours in S more than it has out S. In this paper, we introduce a generalized self-stabilizing algorithm called minimal (alpha , beta)-dominating set. An alpha-dominating set is a subset of nodes S such that for any node v out of S, the rate of neighbours of v inside S must be greater than alpha, where 0 < alpha <= 1 . In the same way, an (alpha , beta)-dominating set is a subset of nodes S such that: S is alpha-dominating set and for each node v in S, the rate of neighbours of v inside S is greater than beta, where 0 <= beta <= 1 . Mathematical proofs and simulation tests show the correctness and the efficiency of the proposed algorithm. Through our proposed variant ( alpha , beta ) -domination, we prove rigorously the conjecture of Carrier et al. [self-stabilizing (f,g)-alliances with safe convergence, J. Parallel Distrib. Comput. 81-82 (2015), pp. 11-23. doi:10.1016/***.2015.02.001] who have proposed a self-stabilizing algorithm for a domination variant called ( f , g ) -alliance set only when f >= g . We prove the correctness of the case f

关键词： self-stabilizing algorithm dominating set alpha-domination distributed system expression distance-2 model

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing algorithm for the center-finding problem assuming read/write separate atomicity

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2004年第10-11期48卷 1667-1676页

作者： Huang, TC Lin, JC Mou, N Yuan Ze Univ Dept Comp Engn & Sci Taoyuan 32026 Taiwan

The problem of locating centers of graphs has a variety of applications in the areas of transportation and communication in distributed systems. In this paper, we design and prove the correctness of a self-stabilizing algorithm which finds the center(s) for a distributed system with a tree topology. The computational model employed in this paper was introduced by Dolev et al., which assumes the read/write separate atomicity. (C) 2004 Elsevier Ltd. All rights reserved.

关键词： self-stabilizing algorithm model of computation read/write separate atomicity interleaving model center

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing algorithm for Finding a Minimal Distance-2 Dominating Set in Distributed Systems

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2008年第6期24卷 1709-1718页

作者： Lin, Ji-Cherng Huang, Tetz C. Wang, Cheng-Pin Chen, Chih-Yuan Yuan Ze Univ Dept Comp Sci & Engn Chungli 320 Taiwan Nanya Inst Technol Dept Comp Sci & Informat Engn Chungli 320 Taiwan

The study of various dominating set problems is an important area within graph theory. In applications, a dominating set in a system can be considered as an ideal place for allocating resources. And, a minimal dominating set allows allocating a smaller number of resources. Distance-versions of the concept of minimal dominating sets are more applicable to modeling real-world problems, such as placing a smaller number of objects within acceptable distances of a given population. However, due to the main restriction that any processor in a distributed system can only access the data of its direct neighbors, a self-stabilizing algorithm for finding a minimal distance-k (with k >= 2) dominating set is hard to get, and its correctness is hard to verify. In this paper, a self-stabilizing algorithm for finding a minimal distance-2 dominating set is proposed. The algorithm can be applied to any distributed system that operates under the central demon model. The correctness of the algorithm is verified.

关键词： minimal distance-2 dominating set self-stabilizing algorithm Dijkstra's central demon model distributed system legitimate configuration

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2005年第1期71卷 70-85页

作者： Huang, TC Yuan Ze Univ Dept Comp Engn & Sci Taoyuan 32026 Taiwan

Shortest path finding has a variety of applications in the areas of transportation and communication in distributed systems. In this paper, we design and prove the correctness of a self-stabilizing algorithm that solves the single-source shortest path problem for a distributed system. Unlike all previous works on this topic, the model of computation employed by the system in this paper assumes the separate read/write atomicity introduced by Dolev et al. instead of the commonly used composite read/write atomicity introduced by Dijkstra. (C) 2005 Elsevier Inc. All rights reserved.

关键词： self-stabilizing algorithm shortest path model of computation separate read/write atomicity composite read/write atomicity

来源：评论

学校读者我要写书评

暂无评论

An improved self-stabilizing algorithm for biconnectivity and bridge-connectivity

引用

INFORMATION PROCESSING LETTERS 2007年第1期102卷 27-34页

作者： Tsin, Yung H. Univ Windsor Sch Comp Sci Windsor ON N9B 3P4 Canada

The functionality of a self-stabilizing algorithm for determining cut-vertices and biconnected components of distributed computer networks, are discussed. A self-stabilizing algorithm is a distributed algorithm that determines all the bridges and determines all bridge-connected components. It is a modification of the self-stabilizing depth-first search algorithm of Collin and Dolev and it is a adaptation of Tarjan's sequential algorithm for biconnectivity to the self-stabilizing model. The time complexity and memory requirement of the algorithm is similar to that of the depth-first spanning tree algorithm. The algorithm require O(m log n) bits per processor and it efficiently determines bridge-connected components in comparison of Chaudhari's composite algorithm for bridge-connected components. It determines biconnected components of distributed computer networks using spanning subtrees.

关键词： self-stabilizing algorithm fault tolerance distributed computing distributed algorithm cut-vertex biconnected component bridge bridge-connected component

来源：评论

学校读者我要写书评

暂无评论

An O(n²) self-stabilizing algorithm for computing bridge-connected components

引用

COMPUTING 1999年第1期62卷 55-67页

作者： Chaudhuri, P Kuwait Univ Dept Elect & Comp Engn Safat Kuwait

This paper presents a self-stabilizing algorithm that finds the bridge-connected components of a connected undirected graph on an asynchronous distributed or network model of computation. An edge of a graph is a bridge if its removal disconnects the graph. The bridge-connected components problem consists of finding the maximal connected subgraphs (components) of the given graph such that none of the components contains a bridge. The output of the algorithm is available in a distributed manner in the sense that, upon termination of the algorithm, each node of the graph knows its component number: the component number is a representative node number which uniquely identifies a bridge-connected component. It has been proved that the algorithm is correct and requires O(n(2)) time if the depth-first search spanning tree of the graph is known, or else it requites O(n(2) + n . d . Delta) time, where n is the number of nodes, d is the graph diameter, and a is an upper bound on the degree of a node.

关键词： distributed system self-stabilizing algorithm graphs bridge-connected components time complexity

来源：评论

学校读者我要写书评

暂无评论

An energy-efficient QoS routing for wireless sensor networks using self-stabilizing algorithm

引用

AD HOC NETWORKS 2016年第Part2期37卷 240-255页

作者： Chen, Da-Ren Natl Taichung Univ Sci & Technol Dept Informat Management Taichung 404 Taiwan

Transmission delays caused by wireless multi-hop communications usually hamper the time-sensitive applications on wireless sensor networks (WSNs). In this paper, transmission delay of data packets is quantified as the number of hops from a sensor to base station (BS), and a tolerable delay (TD) of each packet denotes the initial value of aging tag (AT) to present their QoS metric. On the basis of predictability of TDMA schedule, we propose a self-stabilizing hop-constrained energy-efficient (SHE) protocol for constructing minimum energy networks for hard real-time routing. The protocol first constructs ad hoc multi-hop paths within a cluster while controlling the number of nodes in the cluster so as to meet the TO of data packets from member nodes to their CH. An adaptive routing protocol is then proposed to convey aggregate data packets from CHs to BSs in different routes depending on their current AT values, thus meeting their QoS requirements while prolonging the network lifetime. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Wireless sensor networks self-stabilizing algorithm TDMA Real-time routing protocol

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：