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

Guest Editorial: Special Issue on Security and Privacy of distributed algorithms and Network Systems

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第9期65卷 3725-3727页

作者： Chen, Zhiyong Pasqualetti, Fabio He, Jianping Cheng, Peng Trentelman, Harry L. Bullo, Francesco Univ Newcastle Sch Elect Engn & Comp Callaghan NSW 2308 Australia Univ Calif Riverside Dept Mech Engn Riverside CA 92521 USA Shanghai Jiao Tong Univ Dept Automat Shanghai 200240 Peoples R China Zhejiang Univ Coll Control Sci & Engn Hangzhou 310027 Peoples R China Univ Groningen Johann Bernoulli Inst Math & Comp Sci NL-9712 CP Groningen Netherlands Univ Calif Santa Barbara Dept Mech Engn Santa Barbara CA 93106 USA

The articles in this special issue focus on security and privacy of distributed algorithms and network systems. The integration of computation, communication, and control technologies has led to the widespread emergence of large scale engineering systems. These network systems are deployed in numerous fields, including electric and smart grids, transportation and smart cities, health-care and manufacturing, and so forth. Due to the rapid growth in number of geographically deployed units, such as sensors, computers and controllers, traditional centralized control and optimization algorithms may not be efficient, robust, or even applicable at all. Instead, distributed control and optimization algorithms offer a promising and desirable approach to operate and guarantee the well functioning of network systems. The aim of this special issue is to provide a window into the recent developments of the fundamentals and applications of security and privacy of distributed algorithms in network systems.

关键词： Special issues and sections Security Privacy distributed algorithms Optimization Information and communication technology Control systems

来源：评论

学校读者我要写书评

暂无评论

Quantitative program logic and expected time bounds in probabilistic distributed algorithms

引用

THEORETICAL COMPUTER SCIENCE 2002年第1期282卷 191-219页

作者： McIver, AK Univ Oxford Comp Lab Programming Res Grp Oxford OX1 3QD England

In this paper we show how quantitative program logic (Morgan et al., ACM Trans. Programming Languages Systems 18 (1996) 325) provides a formal framework in which to promote standard techniques of program analysis to a context where probability and nondeterminism interact, a situation common to probabilistic distributed algorithms. We show that overall expected time can be formulated directly in the logic and that it can be derived from local properties of components. We illustrate the methods with an analysis of expected running time of the probabilistic dining philosophers (Lehmann and Ravin, Proc 8th Annu. ACM. Symp. on principles of Programming Languages, ACM, New York, 1981, p. 133). (C) 2002 Published by Elsevier Science B.V.

关键词： distributed algorithms analysis programme Computer Programming Languages Probability Formal logic Runtime Bound

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for filling MIS vertices of an arbitrary graph by myopic luminous robots

引用

THEORETICAL COMPUTER SCIENCE 2023年 978卷

作者： Pramanick, Subhajit Samala, Sai Vamshi Pattanayak, Debasish Mandal, Partha Sarathi Indian Inst Technol Guwahati Dept Math Gauhati 781039 Assam India LUISS Univ Rome Italy

We present the problem of finding a maximal independent set (MIS) (named as MIS Filling problem) of an arbitrary connected graph having n vertices with luminous myopic mobile robots. The robots enter the graph one after another from a particular vertex called the Door and move along the edges of the graph without collision to occupy vertices such that the set of occupied vertices form a maximal independent *** this paper, we explore two versions of the MIS filling problem, where two separate algorithms are proposed. First version of the problem considers a Single Door where our IND algorithm forms an MIS of size m in O (m(2)) epochs under an asynchronous scheduler, where an epoch is the smallest time interval in which each participating robot gets activated at least once and performs a Look-Compute-Move cycle. The robots have three hops of visibility range, Delta + 8 number of colors, and O (log Delta) bits of persistent storage, where A is the maximum degree of the graph. The second version of the problem has Multiple Doors for which we present our MULTIND algorithm that forms an MIS in O (m(2)) epochs under a semi-synchronous scheduler using robots with five hops of visibility range, Delta + k + 7 number of colors, and O (log(Delta + k)) bits of persistent storage, where k is the number of Doors. We also achieve a lower bound of Omega(n) for MIS filling problem with Single Door, where n is the number of vertices of the graph.(c) 2023 Elsevier B.V. All rights reserved.

关键词： distributed algorithms Multi-agent systems Mobile robots Luminous robots Filling problem Maximal independent set (MIS)

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for End-to-End Packet Scheduling in Wireless Ad Hoc Networks

引用

ACM TRANSACTIONS ON algorithms 2016年第3期12卷 28-28页

作者： Kumar, V. S. Anil Marathe, Madhav V. Parthasarathy, Srinivasan Srinivasan, Aravind Virginia Tech Biocomplex Inst 1015 Life Sci Circle Blacksburg VA 24061 USA IBM TJ Watson Res Ctr Yorktown Hts NY USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA

Packet scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we study packet routing and scheduling under this model of interference. The main focus of our work is the development of fully distributed (decentralized) protocols. We present polylogarithmic/constant factor approximation algorithms for various families of disk graphs (which capture the geometric nature of wireless-signal propagation), as well as near-optimal approximation algorithms for general graphs. A basic distributed coloring procedure, originally due to Luby [1993] (Journal of Computer and System Sciences, 47:250-286, 1993), underlies many of our algorithms. The work of Finocchi et al. [2002] (Proc. ACM-SIAM Symposium on Discrete algorithms, 2002) showed that a natural modification of this algorithm leads to improved performance. A rigorous explanation of this was left as an open question, and we prove that the modified algorithm is indeed provably better in the worst case.

关键词： Packet scheduling wireless interference distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for computing a fixed point of multi-agent nonexpansive operators

引用

AUTOMATICA 2020年 122卷 109286-109286页

作者： Li, Xiuxian Xie, Lihua Nanyang Technol Univ Sch Elect & Elect Engn 50 Nanyang Ave Singapore 639798 Singapore

This paper investigates the problem of finding a fixed point for a global nonexpansive operator under time-varying communication graphs in real Hilbert spaces, where the global operator is separable and composed of an aggregate sum of local nonexpansive operators. Each local operator is only privately accessible to each agent, and all agents constitute a network. To seek a fixed point of the global operator, it is indispensable for agents to exchange local information and update their solution cooperatively. To solve the problem, two algorithms are developed, called distributed Krasnosel'ski- Mann (D-KM) and distributed block-coordinate Krasnosel'ski-Mann (D-BKM) iterations, for which D-BKM is a block-coordinate version of D-KM in the sense of randomly choosing and computing only one block-coordinate of local operators at each time for each agent. It is shown that the proposed two algorithms can both converge weakly to a fixed point of the global operator. Meanwhile, the designed algorithms are applied to recover the classical distributed gradient descent (DGD) algorithm, devise a new block-coordinate DGD algorithm, handle a distributed shortest distance problem in the Hilbert space for the first time, and solve linear algebraic equations in a novel distributed approach. Finally, the theoretical results are corroborated by a few numerical examples. (c) 2020 Elsevier Ltd. All rights reserved.

关键词： distributed algorithms Multi-agent networks Nonexpansive operators Fixed point distributed optimization

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Multicommodity Flow Problems via Approximate Steepest Descent Framework

引用

ACM TRANSACTIONS ON algorithms 2012年第1期9卷 3-3页

作者： Awerbuch, Baruch Khandekar, Rohit Rao, Satish Johns Hopkins Univ Baltimore MD 21218 USA Univ Calif Berkeley Berkeley CA 94720 USA

We consider solutions for distributed multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We show first distributed solutions that allow (1 + epsilon) approximation and whose convergence time is essentially linear in the maximal path length, and is independent of the number of commodities and the size of the graph. Our algorithms use a very natural approximate steepest descent framework, combined with a blocking flow technique to speed up the convergence in distributed and parallel environment. Previously known solutions that achieved comparable convergence time and approximation ratio required exponential computational and space overhead per agent.

关键词： algorithms Theory distributed algorithms multicommodity flow multiplicative update steepest descent

来源：评论

学校读者我要写书评

暂无评论

The South Zone: distributed algorithms for Alliances

The South Zone: Distributed Algorithms for Alliances

引用

13th International Symposium on Stabilization, Safety, and Security of distributed Systems (SSS)

作者： Dourado, M. C. Penso, L. D. Rautenbach, D. Szwarcfiter, J. L. Univ Fed Rio de Janeiro Inst Matemat NCE & COPPE Rio De Janeiro RJ Brazil Univ Ulm Inst Optimierung & Operat Res Fak Mathe & Wirtschaftswissenschaften Ulm Germany

ISBN: (纸本)9783642245497;9783642245503

We present novel results on and efficient deterministic as well as randomized synchronous message-passing distributed algorithms for generalized graph alliances, a new concept incorporating and expanding previous ones. An alliance is here a group of nodes of a connected network or a population fulfilling certain thresholds for their neighbourhood. More precisely, every node outside and inside the alliance must have a minimum number of neighbours inside the alliance. A threshold function defining this number may be specific to each node. We are interested in finding minimal alliances of generalized type: the threshold function might be any. We also investigate conditions in which it is possible to have anonymity, a praised property in population protocols.

关键词： graph alliances distributed algorithms minimality population protocols

来源：评论

学校读者我要写书评

暂无评论

Fast deterministic distributed algorithms for sparse spanners

引用

13th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2006)

作者： Derbel, Bilel Gavoille, Cyril Univ Bordeaux Lab Boredelais Rech & Informat F-33405 Talence France

ISBN: (纸本)3540354743

This paper concerns the efficient construction of sparse and low stretch spanners for unweighted arbitrary graphs with n nodes. All previous deterministic distributed algorithms, for constant stretch spanners of o(n(2)) edges, have a running time Omega(n(epsilon)) for some constant epsilon > 0 depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of o(n(2)) edges in o(n(epsilon)) time for any constant epsilon > 0. More precisely, in Linial's free model a.k.a LOCAL model, we construct in n(O(1/root log n)) time, for every graph, a (3, 2)-spanner of O(n(3/2)) edges, i.e., a spanning subgraph in which the distance is at most 3 times the distance of the original graph plus 2. The result is extended to (alpha(k), beta(k))-spanners with O(n(1+1/k) log k) edges for every integer parameter k >= 1, where alpha(k)+beta(k) = O(k(log25)). If the minimum degree of the graph is Omega(root n), then, in the same time complexity, a (5, 4)-spanner with O (n) edges can be constructed. (C) 2008 Elsevier B.V. All rights reserved.

关键词： distributed algorithms graph spanners time complexity Linial's free model

来源：评论

学校读者我要写书评

暂无评论

Simplifying Hands-On Teaching of distributed algorithms with SPLAY

Simplifying Hands-On Teaching of Distributed Algorithms with...

引用

26th IEEE International Parallel and distributed Processing Symposium (IPDPS) / Workshop on High Performance Data Intensive Computing

作者： Riviere, Etienne Univ Neuchatel Inst Informat CH-2000 Neuchatel Switzerland

ISBN: (纸本)9780769546766

Teaching distributed algorithms using a learning-by-doing approach is usually associated with a slow and cumbersome learning process for students. In order to test and evaluate even simple protocols, students need to learn how to set up and operate a testbed, and to write scripts for deploying, running their program and finally retrieving some logs for parsing and observation of the results. Moreover, the amount of code required in languages such as C# or Java for implementing even a simple protocol is often one order of magnitude more than the length of the protocol pseudo-code description as discussed in class or in research papers. Nevertheless, teaching distributed algorithms and protocols using real deployed code on real conditions is highly desirable and can not always be replaced by the use of simulators. We present in this paper our experience of using SPLAY, a distributed systems evaluation framework that greatly simplifies the work of both instructors and students for hands-on learning of distributed systems. SPLAY simplifies the writing, deployment and observation of distributed algorithms and the management of test environments, narrowing the complexity gap between pseudo-code descriptions and executable implementations. In addition, SPLAY's features and the focus kept on the algorithms and their evaluation, allow students to evaluate their protocols in a variety of conditions, by controlling the experiments and their running conditions, or by allowing running them on multiple testbeds at no additional costs and with minimal administration complexity.

关键词： distributed systems distributed algorithms education deployment evaluation learning-by-doing

来源：评论

学校读者我要写书评

暂无评论

Certification of distributed algorithms Solving Problems with Optimal Substructure 1

引用

13th International Conference on Software Engineering and Formal Methods (SEFM)

作者： Voellinger, Kim Reisig, Wolfgang Humboldt Univ D-10099 Berlin Germany

ISBN: (数字)9783319229690

ISBN: (纸本)9783319229690;9783319229683

We report work-in-progress on applying the concept of a certifying algorithm to distributed algorithms. A certifying algorithm produces not only a result, but also a witness that verifies the result's correctness. Certifying variants of numerous (sequential) algorithms have been developed. However, distributed algorithms behave differently from sequential algorithms. Consequently, it is challenging to make them certifying. Our local approach is to make the distributed algorithm compute many local witnesses that together verify the result's correctness. We identified problems for which this approach is applicable. Particularly, we hypothesize that for problems with optimal substructure (i.e., an optimal solution can be constructed from optimal solutions of its sub-problems) it is often easy to apply the local approach. As an example, we give a certifying distributed algorithm for the shortest path problem.

关键词： distributed algorithms Certifying algorithms Optimal substructure Shortest path problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：