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

distributed Link Removal Using Local Estimation of Network Topology

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2019年第3期6卷 280-292页

作者： Gusrialdi, Azwirman Qu, Zhihua Hirche, Sandra Univ Cent Florida Dept Elect & Comp Engn Orlando FL 32816 USA Tech Univ Munich Dept Elect Engn & Informat Technol Inst Informat Oriented Control D-80290 Munich Bavaria Germany

This paper considers the problem of network structure manipulation in the absence of information on the global network topology. In particular, the problem of removing some of links is investigated in order to slow or stop the spread of disease in a network while preserving its connectivity. Existing methods solve this combinatorial problem in a centralized manner and they require the global information of network structure. In this paper, we propose a distributed design algorithm to compute a suboptimal solution to this problem efficiently by mimicking gradient based method, namely by iteratively removing one or multiple links at a time from the network. Specifically, using matrix perturbation analysis we formulate an optimization problem involving the eigenvector associated with the largest eigenvalue of the adjacency matrix and whose solution is equal to a suboptimal solution to the original problem. This strategy also enables us to overcome the combinatorial issue of the problem. distributed algorithms to estimate the eigenvector and to verify network's connectivity are then proposed which facilitate us to solve the new optimization problem. In addition, topological insights into the proposed algorithm and optimality of its solution are also discussed. Finally, the proposed distributed design method is demonstrated and evaluated via several numerical examples.

关键词： Eigenvalues and eigenfunctions Network topology Symmetric matrices Diseases distributed algorithms Perturbation methods Optimization Link removal largest eigenvalue minimization distributed algorithm matrix perturbation

来源：评论

学校读者我要写书评

暂无评论

distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions

引用

AUTOMATICA 2019年 105卷 206-215页

作者： Qu, Guannan Brown, Dave Li, Na Harvard Univ Cambridge MA 02138 USA MIT Lincoln Lab Lexington MA 02420 USA

We consider a multi-agent task assignment problem where a group of agents need to select tasks from their admissible task sets. The utility of an assignment profile is measured by the sum of individual task utilities, which is a submodular function of the set of agents that are assigned to it. The objective is to find an assignment profile that maximizes the global utility. This problem is NP-hard in general. In this paper we propose an algorithm that provides an assignment profile with utility at least 1/(1 + kappa) of the optimal utility, where kappa is an element of [0, 1] is a parameter for the curvature of the submodular utility functions. In the worst case, when kappa = 1, our algorithm achieves utility at least 1/2 of the optimal. Moreover, when the communication links between agents are consistent with the admissible task sets, the algorithm can be implemented distributedly and asynchronously, which means that there is no centralized coordinator and each agent selects its task using only local information and local communication based on its own time-clock. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Optimization Submodular functions Task assignment Multi-agent systems distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Subgradient-Push Is of the Optimal Convergence Rate

Subgradient-Push Is of the Optimal Convergence Rate

引用

IEEE Conference on Decision and Control

作者： Yixuan Lin Ji Liu Department of Applied Mathematics and Statistics Stony Brook University

ISBN: (数字)9781665467612

ISBN: (纸本)9781665467629

The push-sum based subgradient is an important method for distributed convex optimization over unbalanced directed graphs, which is known to converge at a rate of $O\left( {\ln t/\sqrt t } \right)$. This paper shows that the subgradient-push algorithm actually converges at a rate of $O\left( {1/\sqrt t } \right)$, which is the same as that of the single-agent subgradient and thus optimal. The proposed tool for analyzing push-sum based algorithms is of independent interest.

关键词： Directed graphs Convex functions Delays Proposals distributed algorithms Convergence

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing 2-minimal dominating set algorithm based on loop composition in networks of girth at least 7

A self-stabilizing 2-minimal dominating set algorithm based ...

引用

International Symposium on Parallel and distributed Processing (IPDPS)

作者： Syohei Maruyama Yuichi Sudo Sayaka Kamei Hirotsugu Kakugawa Fujitsu Ltd. Japan Hosei University Japan Hiroshima University Japan Ryukoku University Japan

We propose a silent self-stabilizing asynchronous distributed algorithm to find a 2-minimal dominating set (2-MDS) in networks of girth at least 7. Given a graph $G=(V, E)$ , a 2-MDS of $G$ is a minimal dominating set $D\subseteq V$ such that $D\backslash \{p_{i},p_{j}\}\cup\{p_{z}\}$ is not a dominating set for any nodes $p_{i},p_{j}\in L (p_{i}\neq p_{j})$ and $p_{z}\ /{\!\!\!\in} D$ . The girth is the length of the shortest cycles in the graph. We assume that the processes have unique identifiers. The proposed algorithm constructs a 2-MDS in the networks of girth at least 7 under the weakly fair distributed daemon. The time complexity is $O(nH)$ rounds, and the space complexity is $O(\log n)$ bits per process, where $n$ is the number of processes and $H$ is the diameter of the network.

关键词： distributed processing Network topology Complexity theory Topology Time complexity distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed Optimization Under Adversarial Nodes

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2019年第3期64卷 1063-1076页

作者： Sundaram, Shreyas Gharesifard, Bahman Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47906 USA Queens Univ Dept Math & Stat Kingston ON K7L 3N6 Canada

We investigate the vulnerabilities of consensus-based distributed optimization protocols to nodes that deviate from the prescribed update rule (e.g., due to failures or adversarial attacks). We first characterize certain fundamental limitations on the performance of any distributed optimization algorithm in the presence of adversaries. We then propose a secure distributed optimization algorithm that guarantees that the nonadversarial nodes converge to the convex hull of the minimizers of their local functions under the certain conditions on the graph topology, regardless of the actions of a certain number of the adversarial nodes. In particular, we provide sufficient conditions on the graph topology to tolerate a bounded number of adversaries in the neighborhood of every nonadversarial node, and necessary and sufficient conditions to tolerate a globally bounded number of adversaries. For situations, where there are up to F adversaries in the neighborhood of every node, we use the concept of maximal F-local sets of graphs to provide lower bounds on the distance-to-optimality of achievable solutions under any algorithm. We show that finding the size of such sets is NP-hard.

关键词： distributed algorithms fault tolerance graph theory machine learning multi-agent systems network security optimization

来源：评论

学校读者我要写书评

暂无评论

Relaxed hybrid consensus ADMM for distributed convex optimisation with coupling constraints

引用

IET CONTROL THEORY AND APPLICATIONS 2019年第17期13卷 2828-2837页

作者： Olama, Alireza Bastianello, Nicola Mendes, Paulo R. C. Camponogara, Eduardo Univ Fed Santa Catarina Dept Automat & Syst Engn Florianopolis SC Brazil Univ Padua Dept Informat Engn Via Gradenigo 6-B I-35131 Padua Italy

In this study, the solution of a convex distributed optimisation problem with a global coupling inequality constraint is considered. By using the Lagrange duality framework, the problem is transformed into a distributed consensus optimisation problem and then based on the recently proposed Hybrid Alternating Direction Method of Multipliers (H-ADMM), which merges distributed and centralised optimisation concepts problems, a novel distributed algorithm is developed. In particular, the authors offer a reformulation of the original H-ADMM in an operator theoretical framework, which exploits the known relationship between ADMM and Douglas-Rachford splitting. In addition, the authors' formulation allows us to generalise the H-ADMM by including a relaxation constant, not present in the original design of the algorithm. Moreover, an adaptive penalty parameter selection scheme that consistently improves the practical convergence properties of the algorithm is proposed. Finally, the convergence results of the proposed algorithm are discussed and moreover, in order to present the effectiveness and the major capabilities of the proposed algorithm in off-line and on-line scenarios, distributed quadratic programming and distributed model predictive control problems are considered in the simulation section.

关键词： gradient methods distributed algorithms convex programming distributed control iterative methods predictive control quadratic programming convergence of numerical methods convergence relaxed hybrid consensus ADMM distributed convex optimisation coupling constraints convex distributed optimisation problem global coupling inequality constraint Lagrange duality framework distributed consensus optimisation problem centralised optimisation concepts problems original H-ADMM operator theoretical framework Douglas-Rachford splitting adaptive penalty parameter selection scheme distributed quadratic programming distributed model predictive control problems distributed algorithm hybrid alternating direction method hybrid alternating direction method of multipliers

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Safety Certificate for Multi-agent Systems

Probabilistic Safety Certificate for Multi-agent Systems

引用

IEEE Conference on Decision and Control

作者： Haoming Jing Yorie Nakahira Department of Electrical and Computer Engineering Carnegie Mellon Universty

ISBN: (数字)9781665467612

ISBN: (纸本)9781665467629

This paper focuses on the multi-agent safe control problem for stochastic systems. We propose a probabilistic certificate for safety and performance specifications and use it to construct a distributed algorithm. The certificate integrates the reachability- and invariance-based (barrier-function-based) approaches via a new notion of forward invariance defined on the long-term probability. The proposed method has two features. First, it can guarantee a long-term probability of safety and performance satisfaction using myopic evaluation. Second, each agent can collaboratively ensure system-wide specifications even if each does not have sufficient information to evaluate the specifications. The effectiveness of the proposed method is tested using numerical experiments.

关键词： Stochastic systems Probabilistic logic Safety distributed algorithms Robots Multi-agent systems

来源：评论

学校读者我要写书评

暂无评论

A Minimal Memory Game-Based distributed Algorithm to Vertex Cover of Networks

A Minimal Memory Game-Based Distributed Algorithm to Vertex ...

引用

IEEE International Symposium on Circuits and Systems

作者： Jie Chen Xiang Li Adaptive Networks and Control Lab Fudan University Shanghai China Research Center of Smart Networks and Systems School of Information Science and Engineering Fudan University Shanghai China MOE Frontiers Center for Brain Science Institutes of Brain Science Fudan University Shanghai China

The vertex cover of networks is a classical combinatorial optimization problem. In this paper, we investigate the vertex cover problem solved by the memory-based best response update rule, which can not converge to a strict Nash equilibrium (SNE) with memory length m =3D 1. To overcome this shortcoming, a bounded rational behavioral (BRB) update rule is newly proposed in this paper. We prove that the BRB with m =3D 1 can guarantee that the whole vertices' state converges to a SNE. The simulation is carried out to verify that the performance of the proposed BRB update rule on representative networks. Moreover, we also find that a better SNE will be achieved by increasing the selection intensity.

关键词： Circuits and systems Numerical simulation Nash equilibrium distributed algorithms Optimization

来源：评论

学校读者我要写书评

暂无评论

An improved scheme of practical Byzantine fault tolerant algorithm

An improved scheme of practical Byzantine fault tolerant alg...

引用

The International Conference on Forthcoming Networks and Sustainability (FoNeS 2022)

作者： H. Sui J. Y. School of Cyberspace Security Hainan University Haikou People's Republic of China

Blockchain technology has become the hottest technology in the market because of its characteristics such as decentralization and data tamper resistance. With the development of blockchain, it is widely used in many fields. There are many types of blockchain, such as alliance chain, private chain and public chain. At present, the alliance chain has attracted extensive attention, but the commonly used PBFT algorithm still has many problems. In order to solve the high communication overhead and low efciency of PBFT consensus echanism, an improved PBFT consensus algorithm with a reputation mechanism are proposed in this paper. Diff erent permissions of nodes are made according to their diff erent reputation levels. Only the nodes with high reputation are qualifed to act as master nodes. Nodes with low reputation will be prohibited from participating in the consistency protocol and reduce the probability of becoming master nodes. In our scheme, the security, efciency and throughput of the consensus algorithm are improved, and the communication cost is reduced.

关键词： blockchains distributed algorithms fault tolerance multi-agent systems protocols software fault tolerance

来源：评论

学校读者我要写书评

暂无评论

Maintaining a distributed Spanning Forest in Highly Dynamic Networks

引用

COMPUTER JOURNAL 2019年第2期62卷 231-246页

作者： Barjon, Matthieu Casteigts, Arnaud Chaumette, Serge Johnen, Colette Neggaz, Yessin M. Univ Bordeaux CNRS LaBRI Bordeaux France

Highly dynamic networks are characterized by frequent changes in the availability of communication links. These networks are often partitioned into several components, which split and merge unpredictably. We present a distributed algorithm that maintains a forest of (as few as possible) spanning trees in such a network, with no restriction on the rate of change. Our algorithm is inspired by high-level graph transformations, which we adapt here in a (synchronous) message passing model for dynamic networks. The resulting algorithm has the following properties. First, every decision is purely localin each round, a node only considers its role and that of its neighbors in the tree, with no further information propagation (in particular, no wave mechanisms). Second, whatever the rate and scale of the changes, the algorithm guarantees that, by the end of every round, the network is covered by a forest of spanning trees in which (1) no cycle occur, (2) every node belongs to exactly one tree and (3) every tree contains exactly one root. We primarily focus on the correctness of this algorithm, which is established rigorously. While performance is not the main focus, we suggest new complexity metrics for such problems, and report on preliminary experimentation results validating our algorithm in a practical scenario.

关键词： distributed algorithms communication networks time-varying graphs highly dynamic networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：