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

Evolving distributed algorithms With Genetic Programming

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2012年第2期16卷 242-265页

作者： Weise, Thomas Tang, Ke Univ Sci & Technol China Sch Comp Sci & Technol Nat Inspired Computat & Applicat Lab Hefei 230027 Anhui Peoples R China

In this paper, we evaluate the applicability of genetic programming (GP) for the evolution of distributed algorithms. We carry out a large-scale experimental study in which we tackle three well-known problems from distributed computing with six different program representations. For this purpose, we first define a simulation environment in which phenomena such as asynchronous computation at changing speed and messages taking over each other, i.e., out-of-order message delivery, occur with high probability. Second, we define extensions and adaptations of established GP approaches (such as tree-based and linear GP) in order to make them suitable for representing distributed algorithms. Third, we introduce novel rule-based GP methods designed especially with the characteristic difficulties of evolving algorithms (such as epistasis) in mind. Based on our extensive experimental study of these approaches, we conclude that GP is indeed a viable method for evolving non-trivial, deterministic, non-approximative distributed algorithms. Furthermore, one of the two rule-based approaches is shown to exhibit superior performance in most of the tasks and thus can be considered as an interesting idea also for other problem domains.

关键词： Critical section distributed algorithms election fraglets GCD genetic programming LGP mutual exclusion rule-based genetic programming SGP

来源：评论

学校读者我要写书评

暂无评论

Scalable, distributed algorithms for Solving Linear Equations via Double-Layered Networks

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第3期65卷 1132-1143页

作者： Wang, Xuan Mou, Shaoshuai Anderson, Brian D. O. Purdue Univ Sch Aeronaut & Astronaut W Lafayette IN 47906 USA Hangzhou Dianzi Univ Hangzhou 310018 Peoples R China Data 61 CSIRO Canberra ACT 2601 Australia Australian Natl Univ Sch Informat Sci & Engn Canberra ACT 2600 Australia

This paper proposes scalable, distributed algorithms for solving linear equations by integrating two mechanisms, termed consensus and conservation, in double-layered multiagent networks. The multiagent network considered in this paper is composed of clusters and each cluster consists of an aggregator and a subnetwork of agents. By achieving consensus and conservation through agent-agent communications in the same cluster and aggregator-ggregator communications among different clusters, respectively, distributed algorithms are devised for agents to cooperatively achieve a solution to the overall linear equation. These algorithms outperform existing algorithms, including but not limited to the following aspects-first, each agent does not have to know as much as a complete row or column of the overall equation;second, each agent only needs to control as few as two scalar states when the number of clusters and the number of agents are sufficiently large;third, the dimensions of agents' states in the proposed algorithms do not have to be the same (while in contrast, algorithms based on the idea of standard consensus inherently require all agents' states to be of the same dimension). Both analytical proof and simulation results are provided to validate exponential convergence of the proposed distributed algorithms in solving linear equations.

关键词： Mathematical model distributed algorithms Clustering algorithms Nickel Standards Optimization Information exchange distributed algorithms double-layered framework linear equations multiagent networks

来源：评论

学校读者我要写书评

暂无评论

Nonsmooth Continuous-Time distributed algorithms for Seeking Generalized Nash Equilibria of Noncooperative Games via Digraphs

引用

IEEE TRANSACTIONS ON CYBERNETICS 2022年第7期52卷 6196-6206页

作者： Lu, Kaihong Zhu, Qixin Jiangsu Univ Sch Elect & Informat Engn Zhenjiang 212013 Jiangsu Peoples R China Suzhou Univ Sci & Technol Sch Mech Engn Suzhou 215009 Peoples R China

In this article, the problem of distributed generalized Nash equilibrium (GNE) seeking in noncooperative games is investigated via multiagent networks, where each player aims to minimize his or her own cost function with a nonsmooth term. Each player's cost function and feasible action set in the noncooperative game are both determined by actions of others who may not be neighbors, as well as his/her own action. Particularly, feasible action sets are constrained by private convex inequalities and shared linear equations. Each player can only have access to his or her own cost function, private constraint, and a local block of shared constraints, and can only communicate with his or her neighbours via a digraph. To address this problem, a novel continuous-time distributed primal-dual algorithm involving Clarke's generalized gradient is proposed based on consensus algorithms and the primal-dual algorithm. Under mild assumptions on cost functions and graph, we prove that players' actions asymptotically converge to a GNE. Finally, a simulation is presented to demonstrate the effectiveness of our theoretical results.

关键词： Games Cost function distributed algorithms Mathematical model Consensus algorithm Topology Nash equilibrium distributed algorithm multiagent networks Nash equilibrium (NE) noncooperative game

来源：评论

学校读者我要写书评

暂无评论

How to compute times of random walks based distributed algorithms

引用

FUNDAMENTA INFORMATICAE 2007年第4期80卷 363-378页

作者： Bui, Alain Sohier, Devan Univ Reims Dept Math & Informat SysCom CReSTIC F-51687 Reims France

Random walk based distributed algorithms make use of a token that circulates in the system according to a random walk scheme to achieve their goal. To study their efficiency and compare it to one of the deterministic solutions, one is led to compute certain quantities, namely the hitting times and the cover time. Until now, only bounds on these quantities were known. First, this paper presents two generalizations of the notions of hitting and cover times to weighted graphs. Indeed, the properties of random walks on symmetrically weighted graphs provide interesting results on random walk based distributed algorithms, such as local load balancing. Both of these generalizations are proposed to precisely represent the behaviour of these algorithms, and to take into account what the weights represent. Then, we propose an algorithm to compute the n(2) hitting times on a weighted graph of n vertices, which we improve to obtain a O(n(3)) complexity. This complexity is the lowest up to now. This algorithm computes both of the generalizations that we propose for the hitting times on a weighted graph. Finally, we provide the first algorithm to compute the cover time (in both senses) of a graph. We improve it to achieve a complexity of O(n(3)2(n)). The algorithms that we present are all robust to a topological change in a limited number of edges. This property allows us to use them on dynamic graphs.

关键词： RANDOM walks (Mathematics) distributed algorithms GRAPHIC methods COMPUTATIONAL complexity MATHEMATICAL analysis NUMERICAL analysis

来源：评论

学校读者我要写书评

暂无评论

IMSuite: A benchmark suite for simulating distributed algorithms

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2015年 75卷 1-19页

作者： Gupta, Suyash Nandivada, V. Krishna Indian Inst Technol Dept Comp Sci & Engn PACE Lab Madras 600036 Tamil Nadu India

Considering the diverse nature of real-world distributed applications that makes it hard to identify a representative subset of distributed benchmarks, we focus on their underlying distributed algorithms. We present and characterize a new kernel benchmark suite (named IMSuite) that simulates some of the classical distributed algorithms in task parallel languages. We present multiple variations of our kernels, broadly categorized under two heads: (a) varying synchronization primitives (with and without fine grain synchronization primitives);and (b) varying forms of parallelization (data parallel and recursive task parallel). Our characterization covers interesting aspects of distributed applications such as distribution of remote communication requests, number of synchronization, task creation, task termination and atomic operations. We study the behavior (execution time) of our kernels by varying the problem size, the number of compute threads, and the input configurations. We also present an involved set of input generators and output validators. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Benchmarks. distributed algorithms Performance evaluation Task parallelism Data parallelism Recursive task parallelism

来源：评论

学校读者我要写书评

暂无评论

Structure of initial conditions for distributed algorithms

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2000年第12期E83D卷 2029-2038页

作者： Sakamoto, N Tokyo Inst Technol Grad Sch Informat Sci & Engn Dept Math & Comp Sci Tokyo 1528552 Japan

We call a network an anonymous network, if each vertex of the network is given no ID's. For distributed algorithms fur anonymous networks, solvable problems depend strongly on the given initial conditions. In the past, initial conditions have been investigated, for example, by computation given the number of vertices as the initial condition, and in terms of what initial condition is needed to elect a leader. In this paper, we study the relations among initial conditions. To achieve this task, we define the relation between initial conditions A and B (denoted by A greater than or equal to B) as the relation that some distributed algorithm can compute B on any network satisfying A. Then we show the following property of this relation among initial conditions. The relation is a partial order with respect to equivalence classes. Moreover, over initial conditions, it induces a lattice which has maxima and minima, and contains an infinite number of elements. On the other hand, we give new initial conditions k-LEADER and k-COLOR. k-LEADER denotes the initial condition that gives special condition only to k vertices. k-COLOR denotes the initial condition that divides the vertices into k groups. Then we, investigate the property of the relation among these initial conditions.

关键词： distributed algorithms anonymous networks leader election problem

来源：评论

学校读者我要写书评

暂无评论

Revisiting Finite-Time distributed algorithms via Successive Nulling of Eigenvalues

引用

IEEE SIGNAL PROCESSING LETTERS 2015年第1期22卷 54-57页

作者： Safavi, Sam Khan, Usman A. Tufts Univ Dept Elect & Comp Engn Medford MA 02155 USA

In this letter, we characterize the finite-time behavior on arbitrary undirected graphs. In particular, we derive distributed iterations that are a function of a linear operator on the underlying graph and show that any arbitrary initial condition can be forced to lie on a particular subspace in a finite time. This subspace can be chosen to have the same dimension as the algebraic multiplicity of any (arbitrarily chosen) eigenvalue of the underlying linear operator and is spanned by the eigenvectors corresponding to the chosen eigenvalue. In other words, finite-time behavior is completely characterized by the algebraic multiplicity of the eigenvalues and the corresponding eigenvectors of the underlying linear operator. We show that finite-time average-consensus can be cast naturally in this setup for which we further develop the necessary and sufficient conditions.

关键词： Average-consensus distributed algorithms Eigenvalue multiplicity finite-time convergence subspaces

来源：评论

学校读者我要写书评

暂无评论

Finite-Bit Quantization for distributed algorithms With Linear Convergence

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第11期68卷 7254-7280页

作者： Michelusi, Nicolo Scutari, Gesualdo Lee, Chang-Shen Arizona State Univ Sch Elect Comp & Energy Engn Tempe AZ 85287 USA Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Bloomberg New York NY 10022 USA

This paper studies distributed algorithms for (strongly convex) composite optimization problems over mesh networks, subject to quantized communications. Instead of focusing on a specific algorithmic design, a black-box model is proposed, casting linearly convergent distributed algorithms in the form of fixed-point iterates. The algorithmic model is equipped with a novel random or deterministic Biased Compression (BC) rule on the quantizer design, and a new Adaptive encoding Non-uniform Quantizer (ANQ) coupled with a communication-efficient encoding scheme, which implements the BC-rule using a finite number of bits (below machine precision). This fills a gap existing in most state-of-the-art quantization schemes, such as those based on the popular compression rule, which rely on communication of some scalar signals with negligible quantization error (in practice quantized at the machine precision). A unified communication complexity analysis is developed for the black-box model, determining the average number of bits required to reach a solution of the optimization problem within a target accuracy. It is shown that the proposed BC-rule preserves linear convergence of the unquantized algorithms, and a trade-off between convergence rate and communication cost under ANQ-based quantization is characterized. Numerical results validate our theoretical findings and show that distributed algorithms equipped with the proposed ANQ have more favorable communication cost than algorithms using state-of-the-art quantization rules.

关键词： Quantization (signal) distributed algorithms Convergence Optimization Stars Mesh networks Costs distributed algorithms linear convergence quantization optimization methods

来源：评论

学校读者我要写书评

暂无评论

Logical classification of distributed algorithms (Bakery algorithms as an example)

引用

THEORETICAL COMPUTER SCIENCE 2011年第25期412卷 2724-2745页

作者： Abraham, Uri Ben Gurion Univ Negev Dept Math & Comp Sci IL-84105 Beer Sheva Israel

We argue that logical descriptions of distributed algorithms can reveal key features of their high-level properties, and can serve to classify and explicate fundamental similarities even among superficially very dissimilar algorithms. As an illustration, we discuss two distinct mutual-exclusion algorithms: the Bakery algorithm of Lamport is for shared memory, and the Ricart and Agrawala version is for message passing. It is universally agreed that they are both instances of "the Bakery algorithm" family, but is there a formal expression of this affinity? Here we present logical properties expressed naturally in Tarskian event structures that allow us to capture the similarities precisely. We use the notions of low-level and high-level events to organize the comparison. We find a set of properties expressed in quantification language which are satisfied by every Tarskian system execution that models a run by either one of the protocols, and we suggest these properties as a formal explication for the similarity of the two algorithms. An abstract proof shows that these common properties imply the mutual exclusion, and the informal arguments explain the sense in which they capture the essence of the two Bakery algorithms. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Tarski structures Classification of algorithms Event structures Mutual exclusion distributed algorithms Models of concurrency Many-sorted logics

来源：评论

学校读者我要写书评

暂无评论

Solving a system of linear equations: From centralized to distributed algorithms

引用

ANNUAL REVIEWS IN CONTROL 2019年 47卷 306-322页

作者： Wang, Peng Mou, Shaoshuai Lian, Jianming Ren, Wei Pacific Northwest Natl Lab Richland WA 99354 USA Purdue Univ Sch Aeronaut & Astronaut W Lafayette IN 47906 USA Univ Calif Riverside Dept Elect & Comp Engn Riverside CA 92521 USA

For a wide range of control engineering applications, the problem of solving a system of linear equations is often encountered and has been well studied. Traditionally, this problem has been mainly solved in a centralized manner. However, for applications related to large-scale complex networked systems, centralized algorithms are often subjected to some practical issues due to limited computational power and communication bandwidth. As a promising and viable alternative, distributed algorithms can effectively address the issues associated with centralized algorithms by solving the problem efficiently in a multi-agent setting that accords with the distributed nature of networked systems. distributed algorithms decompose the entire problem into many sub-problems that are solved by individual agents in a cooperative manner. In this survey paper, we provide a detailed overview of the state of the art relevant to distributed algorithms for solving a system of linear equations. We will first review basic distributed algorithms including both discrete-time and continuous-time algorithms. Then we will discuss the extended algorithms to achieve communication efficiency. Furthermore, we will also introduce distributed algorithms to obtain the minimum-norm solution for a system of linear equations with multiple solutions, as well as the least-squares solution when there is no solution. Finally, the relationship of distributed algorithms for solving a system of linear equations to the existing distributed optimization algorithms is discussed. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： System of linear equations distributed algorithms Computational efficiency Minimum-norm solution Least-squares solution

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：