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

39th Symposium on Principles of distributed Computing

作者： Michail, Othon Skretas, George Spirakis, Paul G. Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Patras Comp Engn & Informat Dept Patras Greece

ISBN: (纸本)9781450375825

In this paper, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require a global reconfiguration from a given initial network G(s). to a target network G(f). from a family of networks having some good properties, like small diameter. To formally capture costs associated with creating and maintaining connections, we define three reasonable edge-complexity measures: the total edge activations, the maximum activated edges per round, and the maximum activated degree of a node. We give (poly)log(n) time algorithms for the general task of transforming any G(s) into a G(f) of diameter (poly)log(n), while minimizing the edge-complexity. There is a natural trade-off between time and edge complexity. Our main lower bound shows that Omega(n) total edge activations and O(n/log n) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of Theta( log n) rounds. On the positive side, we give three distributed algorithms for our general task. The first runs in O( log n) time, with at most 2n active edges per round, a total of O(n log n) edge activations, a maximum degree n - 1, and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations. It gives a target network of diameter O( log n) and uses O (n) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog(n) then we can achieve a running time of o (log(2) n). This novel model of distributed computation and reconfiguration in actively dynamic networks and the proposed measures of the edge complexity of distributed algorithms, may open new avenues for research in the algorithmic theory of dynamic networks.

关键词： distributed algorithms dynamic networks reconfiguration transformation polylogarithmic time edge complexity

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: Efficient load-balancing through distributed token dropping 34

Brief announcement: Efficient load-balancing through distrib...

引用

34th International Symposium on distributed Computing, DISC 2020

作者： Brandt, Sebastian Keller, Barbara Rybicki, Joel Suomela, Jukka Uitto, Jara ETH Zürich Switzerland Aalto University Finland IST Austria Klosterneuburg Austria

ISBN: (纸本)9783959771689

We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for the stable orientation problem, which is a special case of the more general locally optimal semi-matching problem. The prior work by Czygrinow et al. (DISC 2012) finds a locally optimal semi-matching in O(∆5) rounds in graphs of maximum degree ∆, which directly implies an algorithm with the same runtime for stable orientations. We improve the runtime to O(∆4) for stable orientations and prove a lower bound of Ω(∆) rounds. © Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto;licensed under Creative Commons License CC-BY 34th International Symposium on distributed Computing (DISC 2020).

关键词： distributed algorithms Graph problems Semi-matching

来源：评论

学校读者我要写书评

暂无评论

Auto-active Verification of distributed Systems and Specification Refinements with Why3-do

引用

Science of Computer Programming 2025年

作者： Cláudio Belo Lourenço Jorge Sousa Pinto Huawei Central Software Institute Edinburgh United Kingdom HASLab/INESC TEC & Universidade do Minho Portugal

In this paper, we introduce a novel approach for rigorously verifying safety properties of state machine specifications. Our method leverages an auto-active verifier and centers around the use of action functions annotated with contracts. These contracts facilitate inductive invariant checking, ensuring correctness during system execution. Our approach is further supported by the Why3-do library, which extends the Why3 tool's capabilities to verify concurrent and distributed algorithms using state machines. Two distinctive features of Why3-do are: (i) it supports specification refinement through refinement mappings, enabling hierarchical reasoning about distributed algorithms; and (ii) it can be easily extended to make verifying specific classes of systems more convenient. In particular, the library contains models allowing for message-passing algorithms to be described with programmed handlers , assuming different network semantics. A gallery of examples, all verified with Why3 using SMT solvers as proof tools, is also described in the paper. It contains several auto-actively verified concurrent and distributed algorithms, including the Paxos consensus algorithm.

关键词： Deductive Verification Auto-active Verification State Machine Specifications Specification Refinement Refinement Mappings distributed algorithms Concurrent algorithms Paxos Consensus

来源：评论

学校读者我要写书评

暂无评论

distributed Generalized Nash Equilibrium Seeking of N-Coalition Games with Inequality Constraints

Distributed Generalized Nash Equilibrium Seeking of N-Coalit...

引用

IEEE Conference on Decision and Control

作者： Chao Sun Guoqiang Hu School of Electrical and Electronic Engineering Nanyang Technological University Singapore

ISBN: (纸本)9781665436601

In this paper, we study the generalized Nash equilibrium (GNE) seeking problem for an N-coalition game with inequality constraints. First, using full decision information, a finite-time average consensus-based approach is proposed. It is demonstrated that the algorithm converges to a GNE (specifically, a variational equilibrium) of the game. Then, using the finite-time consensus tracking technique, we propose a distributed algorithm that only requires neighboring action information for each agent. The solution by using partial decision information covers the distributed GNE seeking solutions of generalized non-cooperative games as a special case.

关键词： Conferences Games Nash equilibrium distributed algorithms Convergence

来源：评论

学校读者我要写书评

暂无评论

distributed alternated-inertia generalized Nash equilibrium seeking algorithm: The partial-decision-information case

Distributed alternated-inertia generalized Nash equilibrium ...

引用

International Conference on Information Science and Technology (ICIST)

作者： Zhangcheng Feng Wenying Xu Jinde Cao Shaofu Yang School of Mathematics Southeast University Nanjing China School of Computer Science and Engineering Southeast University Nanjing China

This paper investigates the distributed computation issue of generalized Nash equilibrium (GNE) in games with globally shared constraints under partial-decision information, where players only get information from their neighbors rather than all the other players. First, we propose two kinds of fully distributed projected-gradient algorithms with inertia/alternated inertia respectively, to seek the GNE. Then, by using the operator splitting technique, the convergence of the proposed algorithms can be guaranteed under the assumptions of Lipschitz continuity and strong monotonicity of the pseudo-gradient mappings. Finally, several numerical examples are provided to verify the developed algorithms.

关键词： Couplings Information science Computational modeling Games Nash equilibrium distributed algorithms Convergence

来源：评论

学校读者我要写书评

暂无评论

Generating Massive Scale-free Networks: Novel Parallel algorithms using the Preferential Attachment Model

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2020年第2期7卷 1–35页

作者： Alam, Maksudul Khan, Maleq Perumalla, Kalyan S. Marathe, Madhav Oak Ridge Natl Lab 1 Bethel Valley Rd Oak Ridge TN 37831 USA Texas A&M Univ Kingsville 700 Univ Blvd Kingsville TX 78363 USA Univ Virginia Network Syst Sci & Adv Comp Div Biocomplex Inst & Initiat Res Pk Blvd Charlottesville VA 22904 USA Univ Virginia Dept Comp Sci Res Pk Blvd Charlottesville VA 22904 USA

Recently, there has been substantial interest in the study of various random networks as mathematical models of complex systems. As real-life complex systems grow larger, the ability to generate progressively large random networks becomes all the more important. This motivates the need for efficient parallel algorithms for generating such networks. Naive parallelization of sequential algorithms for generating random networks is inefficient due to inherent dependencies among the edges and the possibility of creating duplicate (parallel) edges. In this article, we present message passing interface-based distributed memory parallel algorithms for generating random scale-free networks using the preferential-attachment model. Our algorithms are experimentally verified to scale very well to a large number of processing elements (PEs), providing near-linear speedups. The algorithms have been exercised with regard to scale and speed to generate scale-free networks with one trillion edges in 6 minutes using 1,000 PEs.

关键词： Network science random networks preferential attachment distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed optimal scheduling of integrated energy system based on ADMM algorithm

Distributed optimal scheduling of integrated energy system b...

引用

Sustainable Power and Energy Conference (iSPEC)

作者： Yi Wu Liangzhong Yao Siyang Liao Beilin Mao Institute of Electrical and Automation Wuhan University Wuhan China

ISBN: (纸本)9781665414401

With the change of energy consumption structure, the integrated energy system coupled with multiple energy flows such as electricity, natural gas and heat is developing rapidly. At present, the decision-making center of the integrated energy park is the park dispatching control center. The dispatching process involves in the collection of distributed resource data, the joint centralized scheduling of multiple data, and the allocation and distribution of dispatching tasks. However, with the expansion of the scale of the integrated energy system, the centralized control center needs to collect and process a large amount of data, this depends on the strong computing power of the park control center and the reliable communication ability with distributed resources. For the future large-scale comprehensive energy park, centralized computing has many deficiencies. In this paper, the distributed computing method is used to decompose the joint scheduling problem into electric-gas subproblems, and the strong coupling relationship between electricity, natural gas and heat is considered; In the longitudinal consideration of source and reservoir interaction, a day ahead scheduling model considering economic cost and fluctuation cost of tie line is established. Finally, an example is given to analyze the feasibility of the distributed optimization model.

关键词： Costs Processor scheduling Computational modeling distributed databases Optimal scheduling Dispatching distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A distributed Algorithm for Overlapped Community Detection in Large-Scale Networks

A Distributed Algorithm for Overlapped Community Detection i...

引用

International Communication Systems and Networks and Workshops, COMSNETS

作者： Dibakar Saha Partha Sarathi Mandal Indian Institute of Technology Guwahati

ISBN: (数字)9781728191270

ISBN: (纸本)9781728191287

Overlapped community detection in social networks has become an important research area with the increasing popularity and complexity of the networks. Most of the existing solutions are either centralized or parallel algorithms, which are computationally intensive - require complete knowledge of the entire network. But it isn't easy to collect entire network data because the size of the actual network may be prohibitively large. It may result from either privacy concerns (users of a social network may be unwilling to reveal their social links) or technological impediments (implementation of an efficient web crawler). Performing in-network computation solves both problems utilizing the computational capability of the individual nodes of the network. Simultaneously, nodes communicate and share data with their neighbours via message passing, which may go a long way toward mitigating individual nodes' privacy concerns in the network. All the concerns mentioned above motivated us to design a decentralized or distributed technique to detect overlapped communities in a large-scale network. It is desirable because this technique does not offer a single point of failure, and the system as a whole can continue to function even when many of the nodes fail. To overcome the disadvantages of the existing solutions, in this paper, we address the overlapped community detection problem for large-scale networks. We present an efficient distributed algorithm, named DOCD, to identify the overlapped communities in the network. The efficiency of DOCD algorithm is verified with extensive simulation study on some networks such as, Dolphin, Zachary karate club, Football club, and Facebook ego networks. We show that DOCD algorithm is capable of keeping the asymptotically same results with the existing classical centralized algorithms [1]-[5] in terms of community modularity and the number of identified communities. The DOCD algorithm can also efficiently identify the overlapped nodes and ove

关键词： Privacy Social networking (online) Heuristic algorithms Complexity theory distributed algorithms Parallel algorithms Sports

来源：评论

学校读者我要写书评

暂无评论

Robust distributed Estimation of the Algebraic Connectivity for Networked Multi-robot Systems

Robust Distributed Estimation of the Algebraic Connectivity ...

引用

IEEE International Conference on Robotics and Automation (ICRA)

作者： Ioanna Malli Charalampos P. Bechlioulis Kostas J. Kyriakopoulos Control Systems Lab School of Mechanical Engineering National Technical University of Athens Greece

The connectivity of distributed networked multi-robot systems is a crucial operational specification, since the involved robots interact/communicate locally only with their immediate neighbors. Thus, in this work, we propose a distributed algorithm to estimate the algebraic connectivity of the underlying communication graph, which stands as a valid connectivity metric. Our method establishes robustness and fast convergence properties that can be adjusted independently via the appropriate selection of certain design parameters. Finally, we confirm the theoretical findings through simulated paradigms and verify the superiority of our method against a well-established solution of the related literature.

关键词： Measurement Automation Conferences Estimation Robustness Multi-robot systems distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A DETERMINISTIC ALMOST-TIGHT distributed ALGORITHM FOR APPROXIMATING SINGLE-SOURCE SHORTEST PATHS

引用

SIAM JOURNAL ON COMPUTING 2021年第3期50卷 STOC16-98-STOC16-137页

作者： Henzinger, Monika Krinninger, Sebastian Nanongkai, Danupon Univ Vienna Fac Comp Sci A-1090 Vienna Austria Univ Salzburg Dept Comp Sci A-5020 Salzburg Austria KTH Royal Inst Technol Dept Theoret Comp Sci S-10044 Stockholm Sweden

We present a deterministic (1 + o(1))-approximation (n(1/2+o(1)) + D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model);here n is the number of nodes in the network, D is its (hop) diameter, and edge weights are positive integers from 1 to poly(n). This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1 + o(1))-approximation (O) over tilde (root nD(1/4)+ D)-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565-573] by a factor of as large as n1/8, and (ii) the O(is an element of(-1) log is an element of(-1))- approximation factor of Lenzen and Patt-Shamir's (O) over tilde (n(1/2+is an element of)+ D)-time algorithm [in Proceedings of STOC, 2013, pp. 381-390] within the same running time. (Throughout, we use (O) over tilde (.) to hide polylogarithmic factors in n.) Our running time matches the known time lower bound of Omega (root n/log n + D) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433-456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40-57]. It also implies a (2+ o(1))-approximation (n(1/2+o(1))+D1+o(1))time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the ``hitting set argument"" commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (no(1), o(1))-hop set of size n1+o(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths,

关键词： distributed algorithms shortest paths approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：