• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Randomized gossip algorithms
【24h】

Randomized gossip algorithms

机译：随机八卦算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. The topology of such networks changes continuously as new nodes join and old nodes leave the network. Algorithms for such networks need to be robust against changes in topology. Additionally, nodes in sensor networks operate under limited computational, communication, and energy resources. These constraints have motivated the design of "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for an arbitrary network graph, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Designing the fastest gossip algorithm corresponds to minimizing this eigenvalue, which is a semidefinite program (SDP). In general, SDPs cannot be solved in a distributed fashion; however, exploiting problem structure, we propose a distributed subgradient method that solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities derived from the gossip algorithm. We use this connection to study the performance and scaling of gossip algorithms on two popular networks: Wireless Sensor Networks, which are modeled as Geometric Random Graphs, and the Internet graph under the so-called Preferential Connectivity (PC) model.
机译：受传感器，对等网络和自组织网络应用程序的启发，我们研究了分布式算法（也称为八卦算法），用于在节点的任意连接的网络中交换信息和进行计算。随着新节点的加入和旧节点的离开，此类网络的拓扑结构不断变化。用于此类网络的算法必须对拓扑变化具有鲁棒性。另外，传感器网络中的节点在有限的计算，通信和能源资源下运行。这些约束激发了“闲话”算法的设计：这些算法分散了计算负担，并且其中的节点与随机选择的邻居进行通信。我们分析了八卦约束下任意网络图的平均问题，发现八卦算法的平均时间取决于表征该算法的双随机矩阵的第二大特征值。设计最快的八卦算法对应于最小化该特征值，这是一个半定程序（SDP）。通常，无法以分布式方式解决SDP。但是，我们利用问题结构，提出了一种解决网络优化问题的分布式次梯度方法。平均时间与第二大特征值的关系自然将其与随机游走的混合时间以及从八卦算法中得出的转移概率联系起来。我们使用这种连接来研究八种流行网络上八卦算法的性能和可扩展性：无线传感器网络（建模为几何随机图）和Internet图（称为“优先连接性”（PC）模型）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号