Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols

八卦 计算机科学 八卦协议 成对比较 算法 块(置换群论) 随机算法 理论计算机科学 数学 人工智能 几何学 心理学 社会心理学
作者
Nicolas Loizou,Peter Richtárik
出处
期刊:IEEE Transactions on Information Theory [Institute of Electrical and Electronics Engineers]
卷期号:67 (12): 8300-8324 被引量:16
标识
DOI:10.1109/tit.2021.3113285
摘要

In this work we present a new framework for the analysis and design of randomized gossip algorithms for solving the average consensus problem. We show how classical randomized iterative methods for solving linear systems can be interpreted as gossip algorithms when applied to special systems encoding the underlying network and explain in detail their decentralized nature. Our general framework recovers a comprehensive array of well-known gossip algorithms as special cases, including the pairwise randomized gossip algorithm and path averaging gossip, and allows for the development of provably faster variants. The flexibility of the new approach enables the design of a number of new specific gossip methods. For instance, we propose and analyze novel block and the first provably accelerated randomized gossip protocols, and dual randomized gossip algorithms. From a numerical analysis viewpoint, our work is the first that explores in depth the decentralized nature of randomized iterative methods for linear systems and proposes them as methods for solving the average consensus problem. We evaluate the performance of the proposed gossip protocols by performing extensive experimental testing on typical wireless network topologies.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
PDF的下载单位、IP信息已删除 (2025-6-4)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
尊敬雨双完成签到,获得积分20
刚刚
顾矜应助光亮元枫采纳,获得10
2秒前
2秒前
2秒前
尊敬雨双发布了新的文献求助10
3秒前
4秒前
正无穷完成签到,获得积分10
4秒前
浪吃完成签到,获得积分20
4秒前
一轮太阳和幻想完成签到,获得积分10
4秒前
4秒前
曾经的真发布了新的文献求助10
6秒前
封典完成签到,获得积分10
6秒前
6秒前
Iceberg完成签到 ,获得积分10
7秒前
7秒前
搜集达人应助啦熊采纳,获得10
7秒前
今后应助羔羊采纳,获得10
7秒前
高雯发布了新的文献求助10
8秒前
8秒前
洁净斑马完成签到,获得积分10
8秒前
9秒前
Jingshuiliushen完成签到,获得积分10
10秒前
10秒前
10秒前
11秒前
谨慎的铭完成签到 ,获得积分10
11秒前
11秒前
11秒前
研友_n0DWDn发布了新的文献求助10
12秒前
丘比特应助蕙心采纳,获得20
12秒前
就叫柠檬吧完成签到,获得积分10
13秒前
Lazyazy_完成签到 ,获得积分10
13秒前
13秒前
13秒前
13秒前
研友_Z345g8发布了新的文献求助10
14秒前
合规部完成签到,获得积分10
14秒前
光亮元枫发布了新的文献求助10
14秒前
Faith发布了新的文献求助10
15秒前
16秒前
高分求助中
A new approach to the extrapolation of accelerated life test data 1000
ACSM’s Guidelines for Exercise Testing and Prescription, 12th edition 500
Picture Books with Same-sex Parented Families: Unintentional Censorship 500
Nucleophilic substitution in azasydnone-modified dinitroanisoles 500
不知道标题是什么 500
A Preliminary Study on Correlation Between Independent Components of Facial Thermal Images and Subjective Assessment of Chronic Stress 500
Phylogenetic study of the order Polydesmida (Myriapoda: Diplopoda) 360
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 遗传学 基因 物理化学 催化作用 冶金 细胞生物学 免疫学
热门帖子
关注 科研通微信公众号,转发送积分 3970949
求助须知:如何正确求助?哪些是违规求助? 3515634
关于积分的说明 11179061
捐赠科研通 3250769
什么是DOI,文献DOI怎么找? 1795474
邀请新用户注册赠送积分活动 875831
科研通“疑难数据库(出版商)”最低求助积分说明 805188