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

distributed algorithms for random graphs

THEORETICAL COMPUTER SCIENCE 2015年 605卷 95-105页

作者： Krzywdzinski, K. Rybarczyk, K. Adam Mickiewicz Univ Poznan Poland

In this article we study statistical properties of a commonly used network model - an Erdos-Renyi random graph G(n, p). We are interested in the performance of distributed algorithms on large networks, which might be represented by G(n, p). We concentrate on classical problems from the field of distributed algorithms such as: finding a maximal independent set, a vertex colouring, an approximation of a minimum dominating set, a maximal matching, an edge colouring and an approximation of a maximum matching. We propose new algorithms, which with probability close to one as n -> infinity construct anticipated structures in G(n, p) in a low number of rounds. Moreover, in some cases, we modify known algorithms to obtain better efficiency on G(n, p). (C) 2015 Elsevier B.V. All rights reserved.

关键词： distributed algorithms Random graphs Colouring Independent set Dominating set Matching

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Learning and Cognitive Medium Access with Logarithmic Regret

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2011年第4期29卷 731-745页

作者： Anandkumar, Animashree Michael, Nithin Tang, Kevin Swami, Ananthram Univ Calif Irvine Ctr Pervas Commun & Comp Dept Elect Engn & Comp Sci Irvine CA 92697 USA Cornell Univ Sch Elect & Comp Engn Ithaca NY 14853 USA USA Res Lab Adelphi MD 20783 USA

The problem of distributed learning and channel access is considered in a cognitive network with multiple secondary users. The availability statistics of the channels are initially unknown to the secondary users and are estimated using sensing decisions. There is no explicit information exchange or prior agreement among the secondary users and sensing and access decisions are undertaken by them in a completely distributed manner. We propose policies for distributed learning and access which achieve order-optimal cognitive system throughput (number of successful secondary transmissions) under self play, i.e., when implemented at all the secondary users. Equivalently, our policies minimize the sum regret in distributed learning and access, which is the loss in secondary throughput due to learning and distributed access. For the scenario when the number of secondary users is known to the policy, we prove that the total regret is logarithmic in the number of transmission slots. This policy achieves order-optimal regret based on a logarithmic lower bound for regret under any uniformly-good learning and access policy. We then consider the case when the number of secondary users is fixed but unknown, and is estimated at each user through feedback. We propose a policy whose sum regret grows only slightly faster than logarithmic in the number of transmission slots.

关键词： Cognitive medium access control multi-armed bandits distributed algorithms logarithmic regret

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms FOR THE COMPUTATION OF NONCOOPERATIVE EQUILIBRIA

引用

AUTOMATICA 1987年第4期23卷 523-533页

作者： LI, S BASAR, T UNIV ILLINOIS COORDINATED SCI LAB DECIS & CONTROL LAB 1101 W SPRINGFIELD AVE URBANA IL 61801 USA

In this paper, a general class of nonquadratic convex Nash games is studied, from the points of view of existence, stability and iterative computation of noncooperative equilibria. Conditions for contraction of general nonlinear operators are obtained, which are then used in the stability study of such games. These lead to existence and uniqueness conditions for stable Nash equilibrium solutions, under both global and local analysis. Also, convergence of an algorithm which employs inaccurate search techniques is verified. It is shown in the context of a fish war example that the algorithm given is in some aspects superior to various algorithms found in the literature, and is furthermore more meaningful for real world implementation.

关键词： distributed algorithms Game theory inaccurate search techniques noncooperative equilibria numerical methods

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Composite Optimization: Unified Framework and Convergence Analysis

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2021年 69卷 3555-3570页

作者： Xu, Jinming Tian, Ye Sun, Ying Scutari, Gesualdo Zhejiang Univ Coll Control Sci & Engn Hangzhou 310027 Peoples R China Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Penn State Univ Sch Elect Engn & Comp Sci State Coll PA 16802 USA

We study distributed composite optimization over networks: agents minimize a sum of smooth (strongly) convex functions-the agents' sum-utility-plus a nonsmooth (extended-valued) convex one. We propose a general unified algorithmic framework for such a class of problems and provide a convergence analysis leveraging the theory of operator splitting. Distinguishing features of our scheme are: (i) When each of the agent's functions is strongly convex, the algorithm converges at a linear rate, whose dependence on the agents' functions and network topology is decoupled;(ii) When the objective function is convex (but not strongly convex), similar decoupling as in (i) is established for the coefficient of the proved sublinear rate. This also reveals the role of function heterogeneity on the convergence rate. (iii) The algorithm can adjust the ratio between the number of communications and computations to achieve a rate (in terms of computations) independent on the network connectivity;and (iv) A by-product of our analysis is a tuning recommendation for several existing (non-accelerated) distributed algorithms yielding provably faster (worst-case) convergence rate for the class of problems under consideration.

关键词： Convergence Signal processing algorithms distributed algorithms Tuning Network topology Electronic mail Sun distributed optimization linear convergence

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for QoS load balancing

引用

distributed COMPUTING 2011年第5-6期23卷 321-330页

作者： Ackermann, Heiner Fischer, Simon Hoefer, Martin Schoengens, Marcel Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany Fraunhofer Inst Ind Math ITWM Kaiserslautern Germany ETH Inst Theoret Comp Sci Zurich Switzerland

We consider a dynamic load balancing scenario in which users allocate resources in a non-cooperative and selfish fashion. The perceived performance of a resource for a user decreases with the number of users that allocate the resource. In our dynamic, concurrent model, users may reallocate resources in a round-based fashion. As opposed to various settings analyzed in the literature, we assume that users have quality of service demands. A user has zero utility when falling short of a certain minimum performance threshold and having positive utility otherwise. Whereas various load-balancing protocols have been proposed for the setting without quality of service requirements, we consider protocols that satisfy an additional locality constraint: The behavior of a user depends merely on the state of the resource it currently allocates. This property is particularly useful in scenarios where the state of other resources is not readily accessible. For instance, if resources represent channels in a mobile network, then accessing channel information may require time-intensive measurements. We consider several variants of the model, where the quality of service demands may depend on the user, the resource, or both. For all cases we present protocols for which the dynamics converge to a state in which all users are satisfied. More importantly, the time to reach such a state scales nicely. It is only logarithmic in the number of users, which makes our protocols applicable in large-scale systems.

关键词： QUALITY of service COMPUTER network protocols INFORMATION services THEORY of constraints (Management) distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for barrier coverage using relocatable sensors

引用

distributed COMPUTING 2016年第5期29卷 361-376页

作者： Eftekhari, Mohsen Kranakis, Evangelos Krizanc, Danny Morales-Ponce, Oscar Narayanan, Lata Opatrny, Jaroslav Shende, Sunil Concordia Univ Dept Comp Sci & Software Engn Montreal PQ Canada Carleton Univ Sch Comp Sci Ottawa ON Canada Wesleyan Univ Dept Math & Comp Sci Middletown CT 06459 USA Chalmers Univ Technol Dept Comp Sci Gothenburg Sweden Rutgers State Univ Dept Comp Sci Camden NJ USA

We study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier and can move along the barrier. The goal is to find final positions for sensors so that the entire barrier is covered. In recent years, the problem has been studied extensively in the centralized setting. In this paper, we study a barrier coverage problem in the distributed and discrete setting. We assume that we have n identical sensors located at grid positions on the barrier, and that each sensor repeatedly executes a Look-Compute-Move cycle: based on what it sees in its vicinity, it makes a decision on where to move, and moves to its next position. We make two strong but realistic restrictions on the capabilities of sensors: they have a constant visibility range and can move only a constant distance in every cycle. In this model, we give the first two distributed algorithms that achieve barrier coverage for a line segment barrier when there are enough nodes in the network to cover the entire barrier. Our algorithms are synchronous, and local in the sense that sensors make their decisions independently based only on what they see within their constant visibility range. One of our algorithms is oblivious whereas the other uses two bits of memory at each sensor to store the type of move made in the previous step. We show that our oblivious algorithm terminates within steps with the barrier fully covered, while the constant-memory algorithm is shown to take steps to terminate in the worst case. Since any algorithm in which a sensor can only move a constant distance in one step requires steps on some inputs, our second algorithm is asymptotically optimal.

关键词： Barrier coverage Wireless relocatable sensors Autonomous mobile robots Optimal algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for multicast path setup in data networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 1996年第2期4卷 181-191页

作者： Bauer, F Varma, A Dept. of Comput. Eng. California Univ. Santa Cruz CA USA

Establishing a multicast tree in a point-to-point network of switch nodes, such as a wide-area asynchronous transfer mode (ATM) network, can be modeled as the NP-complete Steiner problem in networks, In this paper, we introduce and evaluate two distributed algorithms for finding multicast trees in point-to-point data networks, These algorithms are based on the centralized Steiner heuristics, the shortest path heuristic (SPH) and the Kruskal-based shortest path heuristic (K-SPH), and have the advantage that only the multicast members and nodes in the neighborhood of the multicast tree need to participate in the execution of the algorithm, We compare our algorithms by simulation against a baseline algorithm, the pruned minimum spanning-tree heuristic that is the basis of many previously published algorithms for finding multicast trees. Our results show that the competitiveness (the ratio of the sum of the heuristic tree's edge weights to that of the best solution found) of both of our algorithms was, on the average, 25% better in comparison to that of the pruned spanning-tree approach, In addition, the competitiveness of our algorithms was, in almost all cases, within 10% of the best solution found by any of the Steiner heuristics considered, including both centralized and distributed algorithms, Limiting the execution of the algorithm to a subset of the nodes in the network results in an increase in convergence time over the pruned spanning-tree approach, but this overhead can be reduced by careful implementation.

关键词： multicasting Steiner problem in networks distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Solving a Least-Squares Solution of Linear Algebraic Equations

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2024年第2期11卷 599-609页

作者： Huang, Yi Meng, Ziyang Beijing Inst Technol Beijing 100081 Peoples R China Tsinghua Univ Dept Precis Instrument Beijing 100084 Peoples R China

This article proposes three distributed algorithms for solving linear algebraic equations to seek a least-squares (LS) solution via multiagent networks. We consider that each agent has only access to a small and incomplete block of linear equations rather than the complete row or column in the existing results. First, we focus on the case of a homogeneous partition of linear equations. A distributed algorithm is proposed via a single-layered grid network, in which each agent only needs to control three scalar states. Second, we consider the case of heterogeneous partitions of linear equations. Two distributed algorithms with a doubled-layered network are developed, which allow each agent's states to have different dimensions and can be applied to heterogeneous agents with different storage and computation capabilities. Rigorous proofs show that the proposed distributed algorithms collaboratively obtain an LS solution with exponential convergence and also own a solvability verification property, i.e., a criterion to verify whether the obtained solution is an exact solution. Finally, some simulation examples are provided to demonstrate the effectiveness of the proposed algorithms.

关键词： distributed algorithms least-squares (LS) solution linear equations multiagent networks

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for finding and maintaining a k-tree core in a dynamic network

引用

INFORMATION PROCESSING LETTERS 2003年第4期88卷 187-194页

作者： Srivastava, S Ghosh, RK Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 Uttar Pradesh India

A k-core C-k of a tree T is subtree with exactly k leaves for k less than or equal to n(l), where n(l) the number of leaves in T, and minimizes the sum of the distances of all nodes from C-k. In this paper first we propose a distributed algorithm for constructing a rooted spanning tree of a dynamic graph such that root of the tree is located near the center of the graph. Then we provide a distributed algorithm for finding k-core of that spanning tree. The spanning tree is constructed in two stages. In the first stage, a forest of trees is generated. In the next stage these trees are connected to form a single rooted tree. An interesting aspect of the first stage of proposed spanning algorithm is that it implicitly constructs the (convex) hull of those nodes which are not already included in the spanning forest. The process is repeated till all non root nodes of the graph have chosen a unique parent. We implemented the algorithms for finding spanning tree and its k-core. A core can be quite useful for routing messages in a dynamic network consisting of a set of mobile devices. (C) 2003 Elsevier B.V. All rights reserved.

关键词： k-core rooted core distributed algorithms routing ad hoc networks

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for depth-first search

引用

INFORMATION PROCESSING LETTERS 1996年第1期60卷 7-12页

作者： Makki, SAM Havas, G UNIV QUEENSLAND DEPT COMP SCIST LUCIAQLD 4072AUSTRALIA

We present distributed algorithms for constructing a depth-first search tree for a communication network which are more efficient than previous methods. Our algorithms require 2\V\ - 2 messages and units of time in the worst case, where \V\ is the number of sites in the network, and as little as \V\ messages and time units in the best case. The actual number of messages and time units depends on the network topology and possibly on the routing chosen. We can interpret this to mean that the number of messages and time units is \V\(1 + r) in the worst case, where 0 less than or equal to r < 1 and the value of r depends on the topology and the routing. In a best case for the simplest algorithm, for example when the underlying network has a ring topology, r = O and our basic algorithm requires \V\ messages and time units, regardless of routing. We extend the basic algorithm to achieve the same best case bound for other topologies. The worst case bound, which has r = 1 - 2/\V\, applies if the network topology is a tree. The improvement over the best of previous algorithms is achieved by dynamic backtracking, with a minor increase in message length.

关键词： distributed systems depth-first search distributed algorithms communication graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：