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

Quantized incremental algorithms for distributed optimization

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2005年第4期23卷 798-808页

作者： Rabbat, MG Nowak, RD Univ Wisconsin Dept Elect & Comp Engn Madison WI 53706 USA

Wireless sensor networks are capable of collecting an enormous amount of data. Often, the ultimate objective is to estimate a parameter or function from these data, and such estimators are typically the solution of an optimization problem (e.g., maximum likelihood, minimum mean-squared error, or maximum a posteriori). This paper investigates a general class of distributed optimization algorithms for "in-network" data processing, aimed at reducing the amount of energy and bandwidth used for communication. Our intuition tells us that processing the data in-network should, in general, require less energy than transmitting all of the data to a fusion center. In this paper, we address the questions: When, in fact, does in-network processing use less energy, and how much energy is saved.? The proposed distributed algorithms are based on incremental optimization methods. A parameter estimate,is circulated through the network, and along the way each node makes a small gradient descent-like adjustment to the estimate based only on its local data. Applying results from the theory of incremental subgradient optimization, we find that the distributed algorithms converge to an approximate solution for a broad class of problems. We extend these results to the case where the optimization variable is quantized before being transmitted to the next node and find that quantization does not affect the rate of convergence. Bounds on the number of incremental steps required for a certain level of accuracy provide insight into the tradeoff between estimation performance and communication overhead. Our main conclusion is that as the number of sensors in the network grows, in-network processing will always use less energy than a centralized algorithm, while maintaining a desired level of accuracy.

关键词： distributed algorithms energy-accuracy tradeoff gradient methods wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

distributed CONTINUOUS-TIME algorithms FOR NONSMOOTH EXTENDED MONOTROPIC OPTIMIZATION PROBLEMS

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2018年第6期56卷 3973-3993页

作者： Zeng, Xianlin Yi, Peng Hong, Yiguang Xie, Lihua Beijing Inst Technol Sch Automat Key Lab Intelligent Control & Decis Complex Syst Beijing 100081 Peoples R China Washington Univ Dept Elect & Syst Engn St Louis MO 63130 USA Univ Chinese Acad Sci Chinese Acad Sci Key Lab Syst & Control Beijing 100190 Peoples R China Nanyang Technol Univ Sch Elect & Elect Engn 50 Nanyang Ave Singapore 639798 Singapore

This paper studies distributed algorithms for the nonsmooth extended monotropic optimization problem, which is a general convex optimization problem with a certain separable structure. The considered nonsmooth objective function is the sum of local objective functions assigned to agents in a multiagent network, with local set constraints and affine equality constraints. Each agent only knows its local objective function, local set constraint, and the information exchanged between neighbors. To solve the constrained convex optimization problem, we propose two novel distributed continuous-time subgradient-based algorithms, with projected output feedback and derivative feedback, respectively. Moreover, we prove the convergence of proposed algorithms to the optimal solutions under some mild conditions and analyze convergence rates, with the help of the techniques of variational inequalities, decomposition methods, and differential inclusions. Finally, we give an example to illustrate the efficacy of the proposed algorithms.

关键词： extended monotropic optimization distributed algorithms nonsmooth convex functions decomposition methods differential inclusions

来源：评论

学校读者我要写书评

暂无评论

Consensus-Based Cooperative algorithms for Training Over distributed Data Sets Using Stochastic Gradients

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2022年第10期33卷 5579-5589页

作者： Li, Zhongguo Liu, Bo Ding, Zhengtao Univ Manchester Dept Elect & Elect Engn Manchester M13 9PL Lancs England

In this article, distributed algorithms are proposed for training a group of neural networks with private data sets. Stochastic gradients are utilized in order to eliminate the requirement for true gradients. To obtain a universal model of the distributed neural networks trained using local data sets only, consensus tools are introduced to derive the model toward the optimum. Most of the existing works employ diminishing learning rates, which are often slow and impracticable for online learning, while constant learning rates are studied in some recent works, but the principle for choosing the rates is not well established. In this article, constant learning rates are adopted to empower the proposed algorithms with tracking ability. Under mild conditions, the convergence of the proposed algorithms is established by exploring the error dynamics of the connected agents, which provides an upper bound for selecting the constant learning rates. Performances of the proposed algorithms are analyzed with and without gradient noises, in the sense of mean square error (MSE). It is proved that the MSE converges with bounded errors determined by the gradient noises, and the MSE converges to zero if the gradient noises are absent. Simulation results are provided to validate the effectiveness of the proposed algorithms.

关键词： Training Neural networks Convergence distributed databases Machine learning algorithms Optimization distributed algorithms Consensus convergence analysis distributed training multiagent systems neural networks optimization

来源：评论

学校读者我要写书评

暂无评论

Specification and verification of various distributed leader election algorithms for unidirectional ring networks

引用

SCIENCE OF COMPUTER PROGRAMMING 1997年第1-2期29卷 171-197页

作者： Garavel, H Mounier, L VERIMAG F-38610 GIERESFRANCE

This paper deals with the formal specification and verification of distributed leader election algorithms for a set of machines connected by a unidirectional ring network. Starting from an algorithm proposed by Le Lann in 1977, and its variant proposed by Chang and Roberts in 1979, we study the robustness of these algorithms in the presence of unreliable communication medium and unreliable machines. We propose various improvements of these algorithms in order to obtain a fully fault-tolerant protocol. These algorithms are formally described using the ISO specification language LOTOS and verified (for a fixed number of machines) using the CADP (CAESAR/ALDEBARAN) toolbox. Using model-checking and bisimulation techniques, the verification of these non-trivial algorithms can be carried out automatically, in a few seconds. (C) 1997 Elsevier Science B.V.

关键词： distributed algorithms formal methods leader election LOTOS token ring validation verification

来源：评论

学校读者我要写书评

暂无评论

distributed Generalized Nash Equilibria Computation of Monotone Games via Double-Layer Preconditioned Proximal-Point algorithms

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2019年第1期6卷 299-311页

作者： Yi, Peng Pavel, Lacra Washington Univ Dept Elect & Syst Engn St Louis MO 63130 USA Univ Toronto Dept Elect & Comp Engn Toronto ON M5S Canada

In this paper, we investigate distributed generalized Nash equilibrium (GNE) computation of monotone games with affine coupling constraints. Each player can only utilize its local objective function, local feasible set, and a local block of the coupling constraint, and can only communicate with its neighbors. We assume the game has monotone pseudo-subdifferential without Lipschitz continuity restrictions. We design novel center-free distributed GNE seeking algorithms for equality and inequality affine coupling constraints, respectively. A proximal alternating direction method of multipliers is proposed for the equality case, while for the inequality case, a parallel splitting type algorithm is proposed. In both algorithms, the GNE seeking task is decomposed into a sequential Nash equilibrium (NE) computation of regularized subgames and distributed update of multipliers and auxiliary variables, based on local data and local communication. Our two double-layer GNE algorithms need not specify the inner loop NE seeking algorithm, and moreover, only require that the strongly monotone subgames are inexactly solved. We prove their convergence by showing that the two algorithms can be seen as specific instances of preconditioned proximal point algorithms for finding zeros of monotone operators. Applications and numerical simulations are given for illustration.

关键词： distributed algorithms game theory networks

来源：评论

学校读者我要写书评

暂无评论

Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks

引用

WIRELESS NETWORKS 2006年第2期12卷 179-188页

作者： Bahramgiri, M Hajiaghayi, M Mirrokni, VS MIT Dept Math Cambridge MA 02139 USA MIT Dept Math CSAIL Cambridge MA 02139 USA

The topology of a multi-hop wireless network can be controlled by varying the transmission power at each node. The life-time of such networks depends on battery power at each node. This paper presents a distributed fault-tolerant topology control algorithm for minimum energy consumption in multi-hop wireless networks. This algorithm is an extension of cone-based topology control algorithm [19, 12]. The main advantage of this algorithm is that each node decides on its power based on local information about the relative angle of its neighbors and as a result of these local decisions, a fault-tolerant connected network is formed on the nodes. It is done by preserving the connectivity of a network upon failing of, at most, k nodes (k is a constant) and simultaneously minimize the transmission power at each node to some extent. In addition, simulations are studied to support the effectiveness of this algorithm. Finally, it is shown how to extend this algorithm to 3-dimensions.

关键词： topology control power optimization distributed algorithms multi-hop wireless networks

来源：评论

学校读者我要写书评

暂无评论

Faster Leader Election and Its Applications for Mobile Agents with Parameter Advice 21st

Faster Leader Election and Its Applications for Mobile Agent...

引用

21st International Conference on distributed Computing and Intelligent Technology

作者： Kshemkalyani, Ajay D. Kumar, Manish Molla, Anisur Rahaman Sharma, Gokarna Univ Illinois Chicago IL USA Indian Inst Technol Madras Chennai Tamil Nadu India Indian Stat Inst Kolkata India Kent State Univ Kent OH USA

ISBN: (纸本)9783031814037;9783031814044

Leader election is a critical and extensively studied problem in distributed computing. This paper introduces the study of leader election using mobile agents. Consider n agents initially placed arbitrarily on the nodes of an arbitrary, n-node, m-edge graph G. These agents move autonomously across the nodes of G and elect one agent as the leader such that the leader is aware of its status as the leader, and the other agents know they are not the leader. The goal is to minimize both time and memory usage. We study the leader election problem in a synchronous setting where each agent performs operations simultaneously with the others, allowing us to measure time complexity in terms of rounds. We assume that the agents have prior knowledge of the number of nodes n and the maximum degree of the graph Delta. We first elect a leader deterministically in O(n log(2) n + D Delta log n) rounds with each agent using O(log n) bits of memory, where D is the diameter of the graph. Leveraging this leader election result, we then present a deterministic algorithm for constructing a minimum spanning tree of G in O(m+ n log n) rounds, with each agent using O(Delta log n) bits of memory. Finally, using the same leader election result, we improve time and memory bounds for other key distributed graph problems, including gathering, maximal independent set, and minimal dominating set. For all the aforementioned problems, our algorithms remain memory-optimal.

关键词： distributed algorithms mobile agents local communication leader election MST MIS gathering minimal dominating set time and memory complexity graph parameters

来源：评论

学校读者我要写书评

暂无评论

distributed trigger counting algorithms for arbitrary network topology

引用

WIRELESS COMMUNICATIONS & MOBILE COMPUTING 2016年第16期16卷 2463-2476页

作者： Chang, Che-Cheng Tsai, Jichiang Natl Chung Hsing Univ Dept Elect Engn Taichung 40227 Taiwan Natl Chung Hsing Univ Grad Inst Commun Engn Taichung Taiwan

The distributed trigger counting (DTC) problem is a fundamental block for many distributed applications. Particularly, such a problem is to raise an alert while the number of triggers received by the whole system reaches a pre-defined amount. There have been a few algorithms proposed to solve the DTC problem in the literature. However, these existing algorithms are all under the assumption that each process knows what kind of network topology the whole system forms as well as playing distinct kind of role in the system. The foregoing assumption is not practical for wireless sensor networks because the network topology of a wireless sensor network cannot be obtained in advance, and the roles of all processes are basically identical during the computation. In this paper, we propose a novel distributed algorithm to solve the DTC problem, free of any aforementioned global assumption. Moreover, in order to reduce the message complexity of our algorithm, we further propose a more message-efficient version, only with one extra requirement that all processes have learned ahead the number of processes in the system. Copyright (C) 2016 John Wiley & Sons, Ltd.

关键词： distributed trigger counting wireless sensor networks distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Mobile Agents on Chordal Graphs: Maximum Independent Set and Beyond 21st

Mobile Agents on Chordal Graphs: Maximum Independent Set and...

引用

21st International Conference on distributed Computing and Intelligent Technology

作者： Kaur, Tanvir Paul, Kaustav Mondal, Kaushik Indian Inst Thelmol Ropar Rupnagar Punjab India

ISBN: (纸本)9783031814037;9783031814044

We consider the problem of finding a maximum independent set (MaxIS) of chordal graphs using mobile agents. Suppose n agents are initially placed arbitrarily on the nodes of an n-node chordal graph G = (V, E). Agents need to find a maximum independent set M of G such that each node of M is occupied by at least one agent. Also, each of the n agents must know whether its occupied node is a part of M or not. Starting from both rooted and arbitrary initial configuration, we provide distributed algorithms for n mobile agents having O(log n) memory each to compute the MaxIS of G in O(mnlog Delta) time, where m denotes the number of edges in G and Delta is the maximum degree of the graph. Agents do not need prior knowledge of any parameters if the initial configuration is rooted. For arbitrary initial configuration, agents need to know few global parameters beforehand. We further show that using a similar approach it is possible to find the maximum clique in chordal graphs and color any chordal graph with the minimum number of colors. We also provide a dynamic programming-based approach to solve the MaxIS finding problem in trees in O(n) time.

关键词： Mobile agents Maximum Independent Set distributed algorithms Deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

A Survey of distributed Data Aggregation algorithms

引用

IEEE COMMUNICATIONS SURVEYS AND TUTORIALS 2015年第1期17卷 381-404页

作者： Jesus, Paulo Baquero, Carlos Almeida, Paulo Sergio Univ Minho HASLab INESC TEC P-4710057 Braga Portugal

distributed data aggregation is an important task, allowing the decentralized determination of meaningful global properties, which can then be used to direct the execution of other applications. The resulting values are derived by the distributed computation of functions like COUNT, SUM, and AVERAGE. Some application examples deal with the determination of the network size, total storage capacity, average load, majorities and many others. In the last decade, many different approaches have been proposed, with different trade-offs in terms of accuracy, reliability, message and time complexity. Due to the considerable amount and variety of aggregation algorithms, it can be difficult and time consuming to determine which techniques will be more appropriate to use in specific settings, justifying the existence of a survey to aid in this task. This work reviews the state of the art on distributed data aggregation algorithms, providing three main contributions. First, it formally defines the concept of aggregation, characterizing the different types of aggregation functions. Second, it succinctly describes the main aggregation techniques, organizing them in a taxonomy. Finally, it provides some guidelines toward the selection and use of the most relevant techniques, summarizing their principal characteristics.

关键词： distributed algorithms data aggregation performance trade-offs fault-tolerance

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：