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

CSI International Symposium on Real-Time and Embedded Systems and Technologies

作者： Nia, Mehran Alidoost Faghih, Fathiyeh Univ Tehran Sch Elect & Comp Engn DRTS Res Lab Tehran Iran

ISBN: (纸本)9781538614754

The heterogeneity in cyber-physical systems (CPS) and the diverse situations that they may face with, along with the environmental hazards raise the need to self-stabilization. The uncertain nature of CPS necessitates a probabilistic view for analyzing the system stabilization-time that is a highly critical metric in distributed/time-sensitive applications. Calculating the worst-case expected stabilization-time and possible improvements help to have safer designs of CPS applications. In this paper, a mutual exclusion algorithm based on PIF (Propagation of Information with Feedback) self-stabilizing algorithm is selected in synchronous environment as a case study. Using probabilistic analysis, we present a set of guidelines for utilizing this algorithm in time-sensitive applications. We have also utilized an approximation method for improving the scalability of our probabilistic analysis and did a set of experiments to show how this analysis could be used in the design of topologies with the goal of having an optimal worst-case expected stabilization-time. Our results show that using this approach, we can significantly improve the worst-case expected stabilization-time.

关键词： cyber-physical systems probabilistic formal analysis self-stabilizing algorithms propagation of information with feedback real-time systems

来源：评论

学校读者我要写书评

暂无评论

Phoenix: A Substrate for Resilient Distributed Graph Analytics 19

Phoenix: A Substrate for Resilient Distributed Graph Analyti...

引用

24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)

作者： Dathathri, Roshan Gill, Gurbinder Loc Hoang Pingali, Keshav Univ Texas Austin Austin TX 78712 USA

ISBN: (纸本)9781450362405

This paper presents Phoenix, a communication and synchronization substrate that implements a novel protocol for recovering from fail-stop faults when executing graph analytics applications on distributed-memory machines. The standard recovery technique in this space is checkpointing, which rolls back the state of the entire computation to a state that existed before the fault occurred. The insight behind Phoenix is that this is not necessary since it is sufficient to continue the computation from a state that will ultimately produce the correct result. We show that for graph analytics applications, the necessary state adjustment can be specified easily by the programmer using a thin API supported by Phoenix. Phoenix has no observable overhead during fault-free execution, and it is resilient to any number of faults while guaranteeing that the correct answer will be produced at the end of the computation. This is in contrast to other systems in this space which may either have overheads even during fault-free execution or produce only approximate answers when faults occur during execution. We incorporated Phoenix into D-Galois, the state-of-the-art distributed graph analytics system, and evaluated it on two production clusters. Our evaluation shows that in the absence of faults, Phoenix is similar to 24x faster than GraphX, which provides fault tolerance using the Spark system. Phoenix also outperforms the traditional checkpoint-restart technique implemented in D-Galois: in fault-free execution, Phoenix has no observable overhead, while the checkpointing technique has 31% overhead. Furthermore, Phoenix mostly outperforms checkpointing when faults occur, particularly in the common case when only a small number of hosts fail simultaneously.

关键词： fault tolerance distributed-memory graph analytics big data self-stabilizing algorithms

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing Services for Emulating Distributed Shared Memory on Message Passing Platforms

Self-Stabilizing Services for Emulating Distributed Shared M...

引用

作者： ROBERT GUSTAFSSON CHALMERS UNIVERSITY OF TECHNOLOGY

学位级别：硕士

We use self-stabilization techniques to construct a distributed service for shared memory emulation on message passing platforms. We are the first to implement and practically evaluate the self-stabilizing algorithm for atomic shared memory emulation developed by Dolev, Petig and Schiller, which in turn is the first al- gorithm of its kind to address privacy, malicious behaviour and self-stabilization. Furthermore, we have used techniques from the self-stabilizing Reconfiguration paper by Dolev et al. to create a mechanism for performing a virtually synchronous global reset of the entire system to deal with transient faults. With a firm analytical basis, these algorithms provide the tools needed to deal with arbitrary starting configurations and recover to legal behaviour within a bounded time. To show the applicability and correctness in practice, we have created an evaluation environment using PlanetLab. The evaluation shows that our imple- mentation of the self-stabilizing version of the Coded Shared Atomic Memory al- gorithm (CAS) scales very well both in terms of the number of servers and in terms of the number of concurrent clients. It is shown to have only a constant overhead compared to the traditional CAS algorithm. Furthermore, the evaluation shows that it scales well with respect to data object size too-the system shows almost no slowdown for data objects up to 512 KiB, and is only slightly slower for data objects up to 1 MiB. Last but not least, the evaluation reveals that the global reset mechanism, which is the worst case scenario for handling transient faults, is as fast as a few client operations. For systems with up to 20 servers, the global reset is done within a few seconds. The same techniques used in this project can also be used to create a multitude of other self-stabilizing services and algorithms, such as self-stabilizing Paxos and self-stabilizing Virtual Synchrony to name a few.

关键词： distributed systems distributed shared memory emulation self-stabilizing algorithms

来源：评论

学校读者我要写书评

暂无评论

Evaluation of Fault Tolerant Link Monitoring algorithms for Wireless Sensor Networks 26

Evaluation of Fault Tolerant Link Monitoring Algorithms for ...

引用

26th IEEE Signal Processing and Communications Applications Conference (SIU)

作者： Yigit, Yasin Dagdeviren, Orhan Ege Univ Uluslararasi Bilgisayar Enstitusu Izmir Turkey

ISBN: (纸本)9781538615010

Wireless sensor networks are ad-hoc networks that operate with limited capacity and energy. In wireless sensor networks, it may be desirable to monitor the traffic on the network by checking the links for the security of the system. For such a scenario, the vertex cover problem, which is the well-known problem in the graph theory, can be used. The problem is covering of links on the graph by selecting the minimum number of nodes. Thus, all connections on the network can be controlled using as few devices as possible. self-stabilizing algorithms are algorithms that stabilize the system without external intervention from a random initial state. At this point, the system guarantees a stabilization after a limited time against possible faults. In this study evaluation of vertex cover algorithms for fault tolerant link monitoring in wireless sensor network is made and it is shown that Kiniwa's algorithm performs better than the other algorithms.

关键词： Wireless Sensor Network Link Monitoring Vertex Cover self-stabilizing algorithms Distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A O(m) self-stabilizing Algorithm for Maximal Triangle Partition of General Graphs

引用

PARALLEL PROCESSING LETTERS 2017年第2期27卷 1750004-1750004页

作者： Neggazi, Brahim Turau, Volker Haddad, Mohammed Kheddouci, Hamamache Univ Claude Bernard Lyon 1 43 Bd 11 Novembre 1918 F-69622 Villeurbanne France Hamburg Univ Technol Inst Telemat Schwarzenberg Campus 3 D-21073 Hamburg Germany

The triangle partition problem is a generalization of the well-known graph matching problem consisting of finding the maximum number of independent edges in a given graph, i.e., edges with no common node. Triangle partition instead aims to find the maximum number of disjoint triangles. The triangle partition problem is known to be NP-complete. Thus, in this paper, the focus is on the local maximization variant, called maximal triangle partition (MTP). Thus, paper presents a new self-stabilizing algorithm for MTP that converges in O(m) moves under the unfair distributed daemon.

关键词： self-stabilizing algorithms riangle partition triangle packing tripartite matching fault-tolerance

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing Metric Graphs 18th

引用

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

作者： Gmyr, Robert Lefevre, Jonas Scheideler, Christian Univ Paderborn Dept Comp Sci Paderborn Germany Univ Paris Diderot Paris 7 IRIF Paris France

ISBN: (纸本)9783319492599;9783319492582

We present a self-stabilizing algorithm for overlay networks that, for an arbitrary metric given by a distance oracle, constructs the graph representing that metric. The graph representing a metric is the unique minimal undirected graph such that for any pair of nodes the length of a shortest path between the nodes corresponds to the distance between the nodes according to the metric. The algorithm works under both an asynchronous and a synchronous d ae mon. In the synchronous case, the algorithm stablizes in time O(n) and it is almost silent in that after stabilization a node sends and receives a constant number of messages per round.

关键词： Overlay network self-stabilizing algorithms Metric graph

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing local k-placement of replicas with local minimum variance

引用

THEORETICAL COMPUTER SCIENCE 2015年 591卷 15-27页

作者： Koehler, S. Turau, V. Tel Aviv Univ Dept Elect Engn IL-6997801 Tel Aviv Israel Hamburg Univ Technol Inst Telemat D-21073 Hamburg Germany

Large scale distributed systems require replication of resources to amplify availability and to provide fault tolerance. The placement of replicated resources significantly impacts performance. This paper considers local k-placements: Each node of a network has to place k replicas of a resource among its direct neighbors. The load of a node in a given local k-placement is the number of replicas it stores. The local k-placement problem is to achieve a preferably homogeneous distribution of the loads. We present a novel self-stabilizing, distributed, asynchronous, scalable algorithm for the k-placement problem such that the standard deviation of the distribution of the loads assumes a local minimum. (C) 2015 Elsevier B.V. All rights reserved.

关键词： self-stabilizing algorithms Backup placement Replication

来源：评论

学校读者我要写书评

暂无评论

Resource Discovery and Cooperation in Decentralized Systems

Resource Discovery and Cooperation in Decentralized Systems

引用

作者： Seda Davtyan University of Connecticut

学位级别：博士

Massive distributed cooperative computing in networks involves marshaling large collection of network nodes possessing the necessary computational resources. The computing power of the resources is used in solving partitionable, computation intensive problems. This is referred to as Internet, or network, supercomputing. Traditional approaches to Internet supercomputing employ a master processor and many worker processors that execute a collection of tasks on behalf of the master. Despite the simplicity and advantages of centralized schemes, the master processor is a performance bottleneck and a single point of failure. Additionally, a phenomenon of increasing concern is that workers may return incorrect results. In this thesis, we present algorithms for the problem of network supercomputing that eliminate the master and instead use decentralized approach, where workers cooperate in performing tasks. The problem is studied under a variety of failure models, and all algorithms are designed to deal with undependable and crash-prone workers. Additionally, we present an algorithm that estimates the reliability of workers. In order for the willing nodes to act in a concerted way in decentralized systems they must first discover one another. This is the general setting of the Resource Discovery Problem (RDP), and it serves as a building block for any kind of decentralized collaborative computing. For the resource discovery problem this thesis explores solutions that can cope with intermittent failures, and, in particular we design self-stabilizing algorithms that solve the resource discovery problem in a deterministic synchronous setting.

关键词： Distributed algorithms Network Supercomputing Resource Discovery self-stabilizing algorithms Fault Tolerance

来源：评论

学校读者我要写书评

暂无评论

Stabilization and Lifetime Optimization in Distributed Sensor Networks

Stabilization and Lifetime Optimization in Distributed Senso...

引用

IEEE 27th International Conference on Advanced Information Networking and Applications Workshops (WAINA)

作者： Bahi, Jacques Haddad, Mohammed Hakem, Mourad Kheddouci, Hamamache Univ Franche Comte CNRS DISC Lab Inst FEMTO STUMR F-25030 Besancon France Univ Lyon 1 GAMA LIESP Lab Lyon France

ISBN: (纸本)9780769549521;9781467362399

One of the main design challenges in Wireless Sensor Networks (WSN) is to prolong the system lifetime, while achieving acceptable quality of service for applications. In WSN, each sensor node is battery powered and it is not convenient to recharge or replace the batteries in many cases, especially in remote and hostile environments. Due to the limited capabilities of sensor nodes, it is usually desirable that a WSN should be deployed with high density and thus redundancy can be exploited to increase the network's lifetime. In this paper, we introduce an efficient lifetime optimization and self-stabilizing algorithm to enhance the lifetime of wireless sensor networks especially when the reliabilities of sensor nodes are expected to decrease due to use and wear-out effects. Our algorithm seeks to build resiliency by maintaining a necessary set of working nodes and replacing failed ones when needed. We provide some theoretical and simulation results, that fully demonstrate the usefulness of the proposed algorithm.

关键词： self-stabilizing algorithms lifetime optimization distributed sensor networks reliability Weibull distribution

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing algorithm for optimally efficient sets in graphs

引用

INFORMATION PROCESSING LETTERS 2012年第16期112卷 621-623页

作者： Hedetniemi, Sandra M. Hedetniemi, Stephen T. Jiang, Hao Kennedy, K. E. McRae, Alice A. So Wesleyan Univ Dept Comp Sci Central SC 29630 USA Clemson Univ Sch Comp Clemson SC 29634 USA Appalachian State Univ Dept Comp Sci Boone NC 28608 USA

The efficiency of a set S subset of V in a graph G = (V, E), is defined as epsilon(S) = vertical bar{v is an element of V - S: vertical bar N(v) boolean AND S vertical bar = }vertical bar 1;in other words, the efficiency of a set S equals the number of vertices in V - S that are adjacent to exactly one vertex in S. A set S is called optimally efficient if for every vertex v is an element of V - S, epsilon(S boolean OR {v}) <= epsilon(S), and for every vertex u is an element of S, epsilon(S - {u}) < epsilon(S). We present a polynomial time self-stabilizing algorithm for finding an optimally efficient set in an arbitrary graph. This algorithm is designed using the distance-2 self-stabilizing model of computation. (C) 2012 Elsevier B.V. All rights reserved.

关键词： self-stabilizing algorithms Graph algorithms Optimally efficient set

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：