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

local computations in graphs:: The case of cellular edge local computations

FUNDAMENTA INFORMATICAE 2006年第1期74卷 85-114页

作者： Chalopin, Jeremie Metivier, Yves Zielonka, Wiestaw Univ Bordeaux 1 LaBRI ENSEIRB F-33405 Talence France Univ Paris 07 LIAFA F-75251 Paris 05 France

We examine the power and limitations of the weakest vertex relabelling system which allows to change a label of a vertex in function of its own label and of the label of one of its neighhours. We characterize the grap... 详细信息

关键词： distributed computing local computations election naming submersion

来源：评论

学校读者我要写书评

暂无评论

Scheduling for gathering multitype data with local computations

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第2期294卷 453-459页

作者： Berlinska, Joanna Przybylski, Bartlomiej Adam Mickiewicz Univ Fac Math & Comp Sci Uniwersytetu Poznanskiego 4 PL-61614 Poznan Poland

In this paper, we analyze scheduling gathering multitype data in a star network. Certain numbers of datasets of different types have to be collected on a single computer, either by downloading them from remote nodes, or by producing them locally. The time required to download a dataset depends on its type and initial location, and the time needed to produce a dataset depends only on its type. The scheduling problem is to decide which datasets should be downloaded from which nodes, and how many datasets of each type should be generated locally, in order to minimize the total time necessary for gathering all data. We show that this problem is NP-hard, indicate special cases solvable in polynomial time, and propose a fully polynomial time approximation scheme for a special case which is still NP-hard. For the general case, we present an integer linear programming formulation, a dynamic programming algorithm and a polynomial 2-approximation algorithm. The performance of these algorithms is tested in computational experiments. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Scheduling Data gathering networks local computations Makespan

来源：评论

学校读者我要写书评

暂无评论

Electing a Leader in Dynamic Networks using Mobile Agents and local computations 8

Electing a Leader in Dynamic Networks using Mobile Agents an...

引用

8th International Conference on Ambient Systems, Networks and Technologies (ANT) / 7th International Conference on Sustainable Energy Information Technology (SEIT)

作者： Ktari, Mouna Mosbah, Mohamed Kacem, Ahmed Hadj Univ Sfax ReDCAD Lab FSEGS Sfax 3018 Tunisia Univ Bordeaux CNRS Bordeaux INP LaBRI F-33405 Talence France

In dynamic distributed systems, the topology of networks changes over time which makes difficult the design and much harder the proof of distributed algorithms. These unavoidable changes of the topology make the election and the maintenance of the elected leader a complex task. The maintaining problem is not considered in a static context. To encode distributed algorithms, we adopt the local computation model. Distributed algorithms are formally presented by transitions systems. Based on both, the mobile agent paradigm and the local computation model, we present in this paper a distributed algorithm that elects a leader in a tree. A set of topological events that may affect the structure of the tree: we focus on the appearance and the disappearance of places as well as the communication channels. Our goal is to maintain always a tree with a single leader or a forest of trees where each one has his own leader. 1877-0509 (C) 2017 The Authors. Published by Elsevier B.V.

关键词： Distributed Algorithms local computations Election Mobile Agents Dynamic Networks

来源：评论

学校读者我要写书评

暂无评论

Formal Proofs of Termination Detection for local computations by Refinement-Based Compositions 5th

引用

5th International Conference on Abstract State Machines, Alloy, B, TLA, VDM, and Z

作者： Boussabbeh, Maha Tounsi, Mohamed Mosbah, Mohamed Kacem, Ahmed Hadj Univ Bordeaux LaBRI Lab Talence France Univ Sfax ReDCAD Lab Sfax Tunisia

ISBN: (纸本)9783319336008;9783319335995

In this paper, we propose a formal framework enhancing the termination detection property of distributed algorithms and reusing their specifications as well as their proofs. By relying on refinement and composition, we show that an algorithm specified with local termination detection, can be reused in order to compute the same algorithm with global termination detection. The main idea relies upon the development of distributed algorithms following a top/down approach and the integration of additional computation steps developed in a pre-defined module. This module is specified in a generic and scalable way in order to be composed with particular developments. Once the composition link is proven, the global termination emerges automatically.

关键词： Distributed algorithms local computations Termination detection SSP algorithm Composition Event-B method

来源：评论

学校读者我要写书评

暂无评论

Enhancing Proofs of local computations Through Formal Event-B Modularization 23

Enhancing Proofs of Local Computations Through Formal Event-...

引用

23rd IEEE International Conference on Enabling Technologies, Infrastructure for Collaborative Enterprises (WETICE)

作者： Boussabbeh, Maha Tounsi, Mohamed Kacem, Ahmed Hadj Mosbah, Mohamed ReDCAD Lab Sfax Tunisia Univ Sfax Sfax Tunisia Univ Bordeaux LaBRI Lab Bordeaux France

ISBN: (纸本)9781479942497

Due to the lack of knowledge of the global state and the non determinism in the execution of the processes, distributed algorithms are considered to be very complex to design and to prove. However, it becomes crucial to guarantee that these algorithms run as designed. Modularization mechanism in formal development provides a simple way to manage this complexity. In this paper, we rely on the modularization mechanism of the Event-B method and on local computations model to propose a reuse based approach for modelling classes of distributed algorithms. The proposed approach consists in developing a formal pattern defined as a set of proved logical entities called modules. These modules are developed separately and, when needed, can be incorporated and instantiated in a given system development. Such a mechanism can save efforts on modelling and proving the computation steps in distributed algorithms.

关键词： Distributed algorithms local computations Formal pattern Modularization Event-B method

来源：评论

学校读者我要写书评

暂无评论

A simple randomized k-local election algorithm for local computations

引用

4th International Workshop on Experimental and Efficient Algorithms

作者： Ossamy, R Univ Bordeaux 1 LaBRI F-33405 Talence France

ISBN: (纸本)3540259201

Most of distributed algorithms encoded by means of local computations [3] need to solve k-local election problems to ensure a faithful relabeling of disjoint subgraphs. Due to a result stated in [1], it is not possible to solve the k-local election problem for k >= 3 in anonymous networks. Based on distributed computations of rooted trees of minimal paths, we present in this paper a simple randomized algorithm which, with very high probability, solves the k-local election problem (k >= 2) in an anonymous graph.

关键词： local computations election in graphs distributed algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Checking global properties for local computations in graphs with applications to invariant testing

Checking global properties for local computations in graphs ...

引用

5th Mexican International Conference in Computer Science (ENC 2004)

作者： Mosbah, M Ossamy, R Univ Bordeaux 1 ENSEIRB LaBRI F-33405 Talence France

ISBN: (纸本)0769521606

Global predicates in distributed systems are predicates considering the state of more than one process. They are a useful concept for debugging parallel programs, e.g., for specifying assertions, breakpoints or termination. In this paper we propose an algorithm for detecting the validity of local and global state predicates in distributed algorithms encoded by means of local computations. This algorithm is based on ideas introduced by Cooper and Marzullo and on the approach of Garg and Waldecker. It uses the Lamport's happened-before ordering relationship to construct a partial sorted sequence of all the events that have changed the local state of any process during a computation. While the sequence is traversed, all the global states through which the system has passed are computed and the validity of the given properties is checked. Under the same assumptions, our algorithm is significantly more efficient than the algorithms by Cooper and Marzullo and by Garg and Waldecker.

关键词： global predicates detection consistent global states local computations distributed systems distributed programming languages distributed debugging

来源：评论

学校读者我要写书评

暂无评论

A Fault-Tolerant Handshake Algorithm for local computations 30

A Fault-Tolerant Handshake Algorithm for Local Computations

引用

30th IEEE International Conference on Advanced Information Networking and Applications (IEEE AINA)

作者： Fontaine, Allyx Mosbah, Mohamed Tounsi, Mohamed Zemmari, Akka Univ Bristol Dept Comp Sci Bristol BS8 1UB Avon England Univ Bordeaux LaBRI CNRS UMR 5800 F-33400 Talence France Univ Sfax ReDCAD Lab Sfax Tunisia

ISBN: (纸本)9781509024612

Distributed systems have been studied thoroughly. Many applications are based on huge systems and one of the main property an algorithm running on such systems should verified is fault-tolerance. This paper presents a new randomized algorithm to solve the handshake problem in a distributed system. This algorithm is designed for an asynchronous distributed network of anonymous processes under the message passing communication protocol. In addition to its fault-tolerance, this algorithm is more effective than the existing ones thanks to its asynchronous aspect. To highlight its performance, we provide an experimental evaluation by comparing it to the most representative algorithm solving the handshake problem. The experimentation is done using Visidia, a tool for simulating and visualizing distributed algorithms.

关键词： Distributed Algorithms Fault-Tolerance Handshake Algorithm local computations Visidia

来源：评论

学校读者我要写书评

暂无评论

Electing a Leader in Dynamic Networks using Mobile Agents and local computations

引用

Procedia Computer Science 2017年 109卷 351-358页

作者： Mouna Ktari Mohamed Mosbah Ahmed Hadj Kacem ReDCAD Laboratory University of Sfax FSEGS 3018 Sfax Tunisia LaBRI Bordeaux INP CNRS University of Bordeaux F-33405 Talence France

关键词： Distributed Algorithms local computations Election Mobile Agents Dynamic Networks

来源：评论

学校读者我要写书评

暂无评论

Proving Distributed Algorithms for Wireless Sensor Networks by Combining Refinement and local computations

Proving Distributed Algorithms for Wireless Sensor Networks ...

引用

IEEE International Conference on Enabling Technologies

作者： Emna Taktak Mohamed Mosbah Mohamed Tounsi Ahmed Hadj Kacem ReDCAD Laboratory University of Sfax Tunisia LaBRI CNRS France

Description of computations which can be easily specified with Event-B. We illustrate our approach by an example of distributed algorithm for WSN.

关键词： Wireless Sensor Network Distributed algorithm local computations Refinement Formal proofs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：