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

10th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS 2008)

作者： Manne, Fredrik Mjelde, Morten Pilard, Laurence Tixeuil, Sebastien Univ Bergen N-5020 Bergen Norway Univ Franche Comte Besancon France Univ Paris 06 LIP6 & INRIA Grand Larg Paris France

ISBN: (纸本)9783540893349

The matching problem asks for a large set of disjoint edges in a graph. It is a problem that has received considerable attention in both the sequential and self-stabilizing literature. Previous work has resulted in self-stabilizing algorithms for computing a maximal (1/2-approximation) matching in a general graph, as well is computing a 2/3-approximation on more specific graph types. In the following we present the first self-stabilizing algorithm for finding a 2/3-approximation to the maximum matching problem in a general graph. We show that our new algorithm stabilizes in at most exponential time under a distributed adversarial daemon, and O(n(2)) rounds under a distributed fair daemon, where n is the number of nodes in the graph.

关键词： self-stabilizing algorithm 2/3-Approximation Maximum matching

来源：评论

学校读者我要写书评

暂无评论

A token based self-stabilizing mutual exclusion algorithm

A token based self-stabilizing mutual exclusion algorithm

引用

International Conference on Parallel and Distributed Processing Techniques and Applications

作者： Chaudhuri, P Edward, T Univ W Indies Dept Comp Sci Math & Phys Bridgetown Barbados

ISBN: (纸本)1892512459

This paper presents a self-stabilizing algorithm for mutual exclusion in asynchronous networks. The algorithm is token based and a binary tree network topology is used 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) moves, where n is the number of nodes in the system.

关键词： distributed system self-stabilizing algorithm mutual exclusion complexity

来源：评论

学校读者我要写书评

暂无评论

Short correctness proofs for two self-stabilizing algorithms under the distributed daemon model

引用

DISCRETE APPLIED MATHEMATICS 2009年第1期157卷 140-148页

作者： Lin, Ji-Cherng Chiu, Ming-Yi Yuan Ze Univ Dept Comp Sci & Engn Chungli 320 Tao Yuan Taiwan

The distributed daemon model introduced by Burns in 1987 is a natural generalization of the central daemon model introduced by Dijkstra in 1974. In this paper, we show that a well-known shortest path algorithm is self-stabilizing under the distributed daemon model. Although this result has been proven only recently, the correctness proof provided here is from a different point of view and is much more concise. We also show that Bruell et al.'s center-finding algorithm is actually self-stabilizing under the distributed daemon model. Finally, we compute the worst-case stabilization times of the two algorithms under the distributed daemon model. (c) 2008 Elsevier B.V. All rights reserved.

关键词： self-stabilizing algorithm Shortest path Center Distributed daemon model

来源：评论

学校读者我要写书评

暂无评论

A theorem of Ore and self-stabilizing algorithms for disjoint minimal dominating sets

引用

THEORETICAL COMPUTER SCIENCE 2015年 593卷 132-138页

作者： Hedetniemi, Stephen T. Jacobs, David P. Kennedy, K. E. Clemson Univ Sch Comp Clemson SC 29634 USA Southern Wesleyan Univ Dept Comp Sci Central SC 29630 USA

A theorem of Ore [20] states that if D is a minimal dominating set in a graph G = (V, E) having no isolated nodes, then V - D is a dominating set. It follows that such graphs must have two disjoint minimal dominating sets R and B. We describe a self-stabilizing algorithm for finding such a pair of sets. It also follows from Ore's theorem that in a graph with no isolates, one can find disjoint sets R and B where R is maximal independent and B is minimal dominating. We describe a self-stabilizing algorithm for finding such a pair. Both algorithms are described using the Distance-2 model, but can be converted to the usual Distance-1 model [7], yielding running times of O (n(2)m). (C) 2015 Elsevier B.V. All rights reserved.

关键词： Graph self-stabilizing algorithm Minimal dominating set Maximal independent set

来源：评论

学校读者我要写书评

暂无评论

Improved self-stabilizing algorithms for L(2, 1)-Labeling Tree Networks

引用

MATHEMATICS IN COMPUTER SCIENCE 2011年第1期5卷 27-39页

作者： Chaudhuri, Pranay Thompson, Hussein Jaypee Univ Informat Technol Dept Comp Sci & Engn Waknaghat 173215 Solan India Univ West Indies Dept Comp Sci Math & Phys Bridgetown Barbados

The L(2, 1)-labeling problem for a graph G is a variation of the standard graph coloring problem. Here, we seek to assign a label (color) to each node of G such that nodes a distance of two apart are assigned unique labels and adjacent nodes receive labels which are at least two apart. In a previous paper-presented at the 23rd IASTED International Multi-Conference: Parallel and Distributed Computing and Networks, Innsbruck, Austria-we presented, to the best of our knowledge, the first self-stabilizing algorithm which {Delta + 2}-L(2, 1)-labels rooted trees. That algorithm was shown to require an exponential number of moves to stabilize on a global solution (which is not uncommon in self-stabilizing systems). In this paper, we present two self-stabilizing algorithms which {Delta + 2}-L(2, 1)-label a given rooted tree T in only O(nh) moves (where h is the height and n is the number of nodes in the tree T) under a central scheduler. We also show how the algorithms may be adapted to unrooted trees, dynamic topology changes, and consider the correctness of the protocols under the distributed scheduler model.

关键词： Distributed system self-stabilizing algorithm L(2, 1)-labeling Graph coloring Complexity Tree

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing robots in highly dynamic environments

引用

THEORETICAL COMPUTER SCIENCE 2019年 772卷 88-110页

作者： Bournat, Marjorie Datta, Ajoy K. Dubois, Swan Sorbonne Univ CNRS INRIA LIP6 UMR 7606 4 Pl Jussieu F-75252 Paris 05 France Univ Nevada Las Vegas NV 89154 USA

This paper deals with the classical problem of exploring a ring by a cohort of synchronous robots. We focus on the perpetual version of this problem in which it is required that each node of the ring is visited by a robot infinitely often. The challenge in this paper is twofold. First, we assume that the robots evolve in a highly dynamic ring, i.e., edges may appear and disappear unpredictably without any recurrence, periodicity, or stability assumption. The only assumption we made (known as the temporal connectivity assumption) is that each node is infinitely often reachable from any other node. Second, we aim at providing a self-stabilizing algorithm to the robots, i.e., the algorithm must guarantee an eventual correct behavior regardless of the initial state and positions of the robots. In this harsh environment, our contribution is to fully characterize, for each size of the ring, the necessary and sufficient number of robots to solve deterministically the problem. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Highly dynamic graphs Evolving graphs Perpetual exploration Fully synchronous robots self-stabilizing algorithm

来源：评论

学校读者我要写书评

暂无评论

A New self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property

引用

COMPUTER JOURNAL 2016年第2期59卷 225-243页

作者： Blin, Lelia Potop-Butucaru, Maria Rovedakis, Stephane Tixeuil, Sebastien Univ Paris 06 Univ Evry Val Essonne Sorbonne Univ CNRSLIP6 UMR 7606 4 Pl Jussieu F-75005 Paris France Univ Paris 06 Sorbonne Univ CNRS LIP6 UMR 7606 4 Pl Jussieu F-75005 Paris France Conservatoire Natl Arts & Metiers CEDRIC Paris France Univ Paris 06 Sorbonne Univ Inst Univ France CNRSLIP6 UMR 7606 4 Pl Jussieu F-75005 Paris France

The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a unifiedmanner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol. We present a new self-stabilizing MST protocol that improves on previous known approaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Secondly, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most efficient to date.

关键词： self-stabilizing algorithm loop-free property minimum spanning tree construction

来源：评论

学校读者我要写书评

暂无评论

A note on self-stabilizing articulation point detection

引用

JOURNAL OF SYSTEMS ARCHITECTURE 1999年第14期45卷 1249-1252页

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

A self-stabilizing algorithm for detecting the articulation points of a connected undirected graph on an asynchronous distributed model of computation is proposed in this note. For a given graph if the deletion of a node splits the graph into two or more components then that node is called an articulation point. The algorithm is resilient to transient faults and does not require initialization. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： distributed system self-stabilizing algorithm undirected graph articulation point

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing tree ranking

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2005年第5期82卷 529-539页

作者： Chaudhuri, P Thompson, H Univ W Indies Dept Comp Sci Math & Phys Bridgetown Barbados

Given a graph G and some property p(g), a p-ranking (ordering) of the nodes of G can be defined as a one-to-one function from V to {1, 2, 3, ..., n} such that property p(G) holds for each node i is an element of V. In this paper we present an O(n(2)) self-stabilizing algorithm which, when given a rooted tree T, will provide p-rankings consistent with the following standard graph traversal properties: (i) pre-order traversal;(ii) postorder traversal;(iii) reverse-postorder traversal;(iv) breadth-first traversal;(v) breadth-depth traversal.

关键词： distributed system self-stabilizing algorithm tree traversal rank complexity

来源：评论

学校读者我要写书评

暂无评论

Space-efficient self-stabilizing counting population protocols on mobile sensor networks

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期552卷 99-108页

作者： Izumi, Tomoko Kinpara, Keigo Izumi, Taisuke Wada, Koichi Ritsumeikan Univ Coll Informat Sci & Engn Kusatsu Shiga 5258577 Japan Nagoya Inst Technol Grad Sch Engn Nagoya Aichi 4668555 Japan Hosei Univ Fac Sci & Engn Dept Appl Informat Tokyo 1848584 Japan

In this study, we consider a self-stabilizing counting problem for a passively-mobile sensor network with a base station originally proposed by Beauquier et al. [13], where the base station must count the number of sensors in the network. self-stabilizing counting means that the base station eventually counts the exact number of sensors in the system from the configuration where each sensor has an arbitrary initial state. In this paper, we focus on the space complexity of the self-stabilizing counting problem in terms of the number of sensor states. We propose two self-stabilizing counting protocols. Given a known upper bound P on the number of sensors, the first protocol performs counting using 2P sensor states and its convergence time is O (logn) in fair executions, where n is the actual number of sensors. The second protocol uses only 3. [P/2] sensor states but assumes the global fairness, which is an assumption stronger than the standard fairness. The best known protocol requires 4P states while the corresponding lower bound is P, so our result reduces the gap of the feasibility between P and 4P. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Counting problem Symmetric population protocol self-stabilizing algorithm Mobile sensor networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：