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

20th International Symposium on Parallel and distributed Computing (ISPDC)

作者： Bayramzadeh, Zahra Kshemkalyani, Ajay D. Molla, Anisur Rahaman Sharma, Gokarna Kent State Univ Kent OH 44242 USA Univ Illinois Chicago IL 60607 USA Indian Stat Inst Kolkata 700108 India

ISBN: (纸本)9781665432818

Flooding is a fundamental concept in distributed computing. In flooding, typically, a node forwards a message to its neighbors for the first time when it receives a message. Later if the node receives the same message again, it simply ignores the message and does not forward it. The nodes store a "message record" to ensure that the same message is not forwarded again. Hussak and Trehan introduced amnesiac flooding where nodes do not require to keep the message record. They established a surprising result that the amnesic flooding of a single (k = 1) message starting from some source node always terminates in bipartite graphs in e rounds and in non-bipartite graphs in [e + 1;e + D + 1] rounds, where e is the eccentricity of the source node and D is the diameter of the graph. Recently, Hussak and Trehan introduced dynamic amnesiac flooding initiated in possibly multiple rounds with possibly multiple (k > 1) messages from possibly multiple source nodes. They showed that the partial-send case where a node only sends a message to neighbours from which it did not receive any message in the previous round and the ranked full-send case where a node sends some highest ranked message to all neighbors from which it did not receive that message in the previous round, both terminate. However, they showed that the unranked full-send case, where a node sends some random message (not necessarily the highest ranked message) to all the neighbors from which it did not receive that message in the previous round, does not terminate. In this paper, we show that the unranked full-send case also terminates, provided that diameter D is known to graph nodes. We further show that the termination time is D . (2k - 1) rounds in bipartite graphs and (2D + 1) . (2k 1) rounds in non-bipartite

关键词： distributed algorithms Classic Flooding Amnesiac Flooding Termination Time Complexity Memory

来源：评论

学校读者我要写书评

暂无评论

A scenario-based approach to multi-agent optimization with distributed information 21st

A scenario-based approach to multi-agent optimization with d...

引用

21st IFAC World Congress on Automatic Control - Meeting Societal Challenges

作者： Falsone, Alessandro Margellos, Kostas Prandini, Maria Garatti, Simone Politecn Milan Dipartimento Elett Informaz & Bioingn Piazza Leonardo Da Vinci 32 I-20133 Milan Italy Univ Oxford Dept Engn Sci Pk Rd Oxford OX1 3PJ England

In this paper, we consider optimization problems involving multiple agents. Each agent introduces its own constraints on the optimization vector, and the constraints of all agents depend on a common source of uncertainty. We suppose that uncertainty is known locally to each agent through a private set of data (multi-agent scenarios), and that each agent enforces its scenario-based constraints to the solution of the multi-agent optimization problem. Our goal is to assess the feasibility properties of the corresponding multi-agent scenario solution. In particular, we are able to provide a priori certificates that the solution is feasible for a new occurrence of the global uncertainty with a probability that depends on the size of the datasets and the desired confidence level. The recently introduced wait-and-judge approach to scenario optimization and the notion of support rank are used for this purpose. Notably, decision-coupled and constraint-coupled uncertain optimization programs for multi-agent systems fit our framework and, hence, any distributed optimization scheme to solve the associated multi-agent scenario problem can be accompanied with our a priori probabilistic feasibility certificates. Copyright (C) 2020 The Authors.

关键词： Uncertain systems multi-agent systems data-driven optimization distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed Signal Detection under Communication Constraints 33

Distributed Signal Detection under Communication Constraints

引用

33rd Conference on Learning Theory (COLT)

作者： Acharya, Jayadev Canonne, Clement L. Tyagi, Himanshu Cornell Univ Ithaca NY 14853 USA IBM Res Almaden CA USA IISc Bangalore Bangalore Karnataka India

Independent draws from a d-dimensional spherical Gaussian distribution are distributed across users, each holding one sample. A central server seeks to distinguish between the two hypotheses: the distribution has zero mean, or the mean has l(2)-norm at least epsilon, a pre-specified threshold. However, the users can each transmit at most l bits to the server. This is a distributed variant of the classic problem of detecting signal in white noise. We study this distributed testing problem with and without the availability of a common randomness shared by the users. We design schemes with and without such shared randomness. We then obtain lower bounds for protocols with public randomness, which are tight when l = O(1). We finally conclude with several conjectures and open problems.

关键词： Hypothesis testing signal detection distributed algorithms high-dimensional distributions Gaussian location model mean testing communication constraints

来源：评论

学校读者我要写书评

暂无评论

Fast generalized Nash equilibrium seeking under partial-decision information

引用

AUTOMATICA 2022年 136卷 110080-110080页

作者： Bianchi, Mattia Belgioioso, Giuseppe Grammatico, Sergio Delft Univ Technol Delft Ctr Syst & Control Delft Netherlands Swiss Fed Inst Technol Automat Control Lab Zurich Switzerland

We address the generalized Nash equilibrium seeking problem in a partial-decision information scenario, where each agent can only exchange information with some neighbors, although its cost function possibly depends on the strategies of all agents. The few existing methods build on projected pseudo-gradient dynamics, and require either double-layer iterations or conservative conditions on the step sizes. To overcome both these flaws and improve efficiency, we design the first fully distributed single-layer algorithms based on proximal best-response. Our schemes are fixed-step and allow for inexact updates, which is crucial for reducing the computational complexity. Under standard assumptions on the game primitives, we establish convergence to a variational equilibrium (with linear rate for games without coupling constraints) by recasting our algorithms as proximal point methods, opportunely preconditioned to distribute the computation among the agents. Since our analysis hinges on a restricted monotonicity property, we also provide new general results that significantly extend the domain of applicability of proximal-point methods. Besides, our operator theoretic approach favors the implementation of provably correct acceleration schemes that can further improve the convergence speed. Finally, the potential of our algorithms is demonstrated numerically, revealing much faster convergence with respect to projected pseudo-gradient methods and validating our theoretical findings. (C) 2021 The Author(s). Published by Elsevier Ltd.

关键词： Nash equilibrium seeking Proximal-point method distributed algorithms Multi-agent systems

来源：评论

学校读者我要写书评

暂无评论

Efficient Traffic Management For Resolving Traffic Congestion On Motorways

Efficient Traffic Management For Resolving Traffic Congestio...

引用

Smart Computing and Application (ICSCA), International Conference on

作者： Muhammad Arslan Rana Abu Bakar Abdul Ahad Department of Computer Science University of Sahiwal Sahiwal Pakistan Department of Computer Engineering Faculty of Engineering Chulalongkorn University Bangkok Thailand

Traffic jams on the motorways due to accidents or other emergencies have proven difficult to resolve. The time it takes for the cars to line up and move out of the jam on their own accord is usually rather long. This article presents a system named ETMRTCM, which effectively centralized traffic coordination as a solution for overcoming transitory bottlenecks on multi-lane motorways. At initially, warning alerts regarding the traffic congestion happened depending on Vehicle to Vehicle communications. Then, automobiles start negotiating with their neighbors to figure out the best structure (platoon leader, distance gap, speed, and the number of vehicles) for formulating platoons. As a result, cars can move through the congestion more efficiently. After that, the platoon leaders give orders to the troops to switch lanes if there is an open space in the road adjacent to the one in which they are. The trial findings show that our method may shorten the wait time for the last few cars passing through the congested region by up to 22%. The suggested process also efficiently shortens wait times for vehicles entering the crowded zone while keeping things even for those leaving it.

关键词： Roads Vehicular ad hoc networks Switches Automobiles distributed algorithms Traffic congestion Accidents

来源：评论

学校读者我要写书评

暂无评论

BLOCK AXIAL CHECKERBOARDING: A distributed ALGORITHM FOR HELICAL X-RAY CT RECONSTRUCTION 17

BLOCK AXIAL CHECKERBOARDING: A DISTRIBUTED ALGORITHM FOR HEL...

引用

IEEE 17th International Symposium on Biomedical Imaging (ISBI)

作者： Murthy, Naveen Fessler, Jeffrey A. Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

ISBN: (纸本)9781538693308

Model-Based Iterative Reconstruction (MBIR) methods for X-ray CT provide improved image quality compared to conventional techniques like filtered backprojection (FBP), but their computational burden is undesirably high. distributed algorithms have the potential to significantly reduce reconstruction time, but the communication overhead of existing methods has been a considerable bottleneck. This paper proposes a distributed algorithm called Block-Axial Checkerboarding (BAC) that utilizes the special structure found in helical CT geometry to reduce inter-node communication. Preliminary results using a simulated 3D helical CT scan suggest that the proposed algorithm has the potential to reduce reconstruction time in multi-node systems, depending on the balance between compute speed and communication bandwidth.

关键词： distributed algorithms Helical X-ray CT

来源：评论

学校读者我要写书评

暂无评论

A Discrete-time distributed Algorithm for Minimum l1 -Norm Solution of an Under-determined Linear Equation Set 21st

A Discrete-time Distributed Algorithm for Minimum l1 -Norm S...

引用

21st IFAC World Congress on Automatic Control - Meeting Societal Challenges

作者： Wang, Xuan Mou, Shaoshuai Anderson, Brian D. O. Purdue Univ Sch Aeronaut & Astronaut W Lafayette IN 47906 USA Hangzhou Dianzi Univ Hangzhou Peoples R China Australian Natl Univ Canberra ACT Australia

This paper proposes a discrete-time, distributed algorithm for multi-agent networks to achieve the minimum l(1)-norm solution to a group of linear equations known to possess a family of solutions. We assume each agent in the network knows only one equation and can communicate with only its neighbors. The algorithm is developed based on a combination of the projection-consensus idea and the sub-gradient descent method. Given the underlying network graph to be directed and strongly connected, we prove that the algorithm enables all agents to achieve a common minimum l(1) -norm solution. The major difficulty to be dealt with is the non-smooth nature of the norm and the lack of strict convexity of the associated relevant performance index. Copyright (C) 2020 The Authors.

关键词： distributed algorithms Minimum l(1)-Norm Solutions

来源：评论

学校读者我要写书评

暂无评论

distributed MST: A Smoothed Analysis 20

Distributed MST: A Smoothed Analysis

引用

21st International Conference on distributed Computing and Networking (ICDCN)

作者： Chatterjee, Soumyottam Pandurangan, Gopal Nguyen Dinh Pham Univ Houston Dept Comp Sci Houston TX 77204 USA

ISBN: (纸本)9781450377515

We study smoothed analysis of distributed graph algorithms, focusing on the fundamental minimum spanning tree (MST) problem. With the goal of studying the time complexity of distributed MST as a function of the "perturbation" of the input graph, we posit a smoothing model that is parameterized by a smoothing parameter 0 <= epsilon(n) <= 1 which controls the amount of random edges that can be added to an input graph G per round. Informally, epsilon(n) is the probability (typically a small function of n, e.g., n(-1/4)) that a random edge can be added to a node per round. The added random edges, once they are added, can be used (only) for communication. We show upper and lower bounds on the time complexity of distributed MST in the above smoothing model. We present a distributed algorithm that, with high probability,(1) computes an MST and runs in (O) over tilde (min{1/root epsilon(n)2(O(root log n)), D + root n}) rounds(2) where epsilon is the smoothing parameter, D is the network diameter and n is the network size. To complement our upper bound, we also show a lower bound of (Omega) over tilde (min{1/root epsilon(n), D + root n}). We note that the upper and lower bounds essentially match except for a multiplicative 2(O(root log n)) polylog(n) factor. Our work can be considered as a first step in understanding the smoothed complexity of distributed graph algorithms.

关键词： distributed algorithms smoothed analysis random model minimum spanning tree lower bound

来源：评论

学校读者我要写书评

暂无评论

Non-oscillating quantized average consensus over dynamic directed topologies

引用

AUTOMATICA 2022年 146卷

作者： Rikos, Apostolos I. Hadjicostis, Christoforos N. Johansson, Karl H. KTH Royal Inst Technol Div Decis & Control Syst S-10044 Stockholm Sweden Digital Futures SE-10044 Stockholm Sweden Univ Cyprus Dept Elect & Comp Engn Nicosia Cyprus

In this paper we study the distributed average consensus problem in multi-agent systems with dynamically-changing directed communication links that are subject to quantized information flow. We present and analyze a distributed averaging algorithm which operates exclusively with quantized values (i.e., the information stored, processed and exchanged between neighboring agents is subject to deterministic uniform quantization) and relies on event-driven updates (e.g., to reduce energy con-sumption, communication bandwidth, network congestion, and/or processor usage). We characterize the properties of the proposed distributed algorithm over dynamic directed communication topologies subject to some connectivity conditions and we show that its execution allows each agent to reach, in finite time, a fixed state that is equal (within one quantization level) to the average of the initial states. The main idea of the proposed algorithm is that each agent (i) models its initial state as two quantized fractions which have numerators equal to the agent's initial state and denominators equal to one, and (ii) transmits one fraction randomly while it keeps the other stored. Then, every time an agent receives one or more fractions, it averages their numerators with the numerator of the fraction it stored, and then transmits them to randomly selected out-neighbors. Finally, we provide examples to illustrate the operation, performance, and potential advantages of the proposed algorithm. We compare against various quantized average consensus algorithms and show that our algorithm's convergence speed is among the fastest in the current literature.(c) 2022 Published by Elsevier Ltd.

关键词： Quantized average consensus distributed algorithms Quantization Digraphs Multi -agent systems Event-triggered

来源：评论

学校读者我要写书评

暂无评论

A distributed Depth First Search based Algorithm for Edge Connectivity Estimation 16

A Distributed Depth First Search based Algorithm for Edge Co...

引用

16th International Conference on Network and Service Management (CNSM) / 2nd International Workshop on Analytics for Service and Application Management (AnServApp) / 1st International Workshop on the Future Evolution of Internet Protocols (IPFuture)

作者： Ugurlu, Onur Akram, Vahid Khalilpour Eliiyi, Deniz Tursel Izmir Bakircay Univ Dept Fundamental Sci Izmir Turkey Ege Univ Int Comp Inst Izmir Turkey Izmir Bakircay Univ Dept Ind Engn Izmir Turkey

ISBN: (纸本)9783903176317

The edge connectivity of a network is the minimum number of edges whose removal disconnect the network. The edge connectivity determines the minimum number of edge-disjoint paths between all nodes. Hence finding the edge connectivity can reveal useful information about reliability, alternative paths and bottlenecks. In this paper, we propose a cost-effective distributed algorithm that finds a lower bound for the edge connectivity of a network via finding at most c depth-first-search trees, where c is the edge connectivity. The proposed algorithm is asynchronous and does not need any synchronization between the nodes. In the proposed algorithm, the root node starts a distributed depth-first-search algorithm, and the nodes select next node in the tree based on their available edges to maximize the total number of established trees. The simulation results show that the proposed algorithm finds the edge connectivity with an average of 48% accuracy ratio.

关键词： distributed algorithms Edge Connectivity Depth First Search Spanning Tree

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：