Finite-Time Convergent Gossiping
文献类型：期刊论文
| 作者 | Shi, Guodong1; Li, Bo2 ; Johansson, Mikael3; Johansson, Karl Henrik3
|
| 刊名 | IEEE-ACM TRANSACTIONS ON NETWORKING
 |
| 出版日期 | 2016-10-01 |
| 卷号 | 24期号:5页码:2814-2826 |
| 关键词 | Gossip algorithms finite-time convergence computational complexity quantum algorithms |
| ISSN号 | 1063-6692 |
| DOI | 10.1109/TNET.2015.2484345 |
| 英文摘要 | Gossip algorithms are widely used in modern distributed systems, with applications ranging from sensor networks and peer-to-peer networks to mobile vehicle networks and social networks. A tremendous research effort has been devoted to analyzing and improving the asymptotic rate of convergence for gossip algorithms. In this work we study finite-time convergence of deterministic gossiping. We show that there exists a symmetric gossip algorithm that converges in finite time if and only if the number of network nodes is a power of two, while there always exists an asymmetric gossip algorithm with finite-time convergence, independent of the number of nodes. For n = 2(m) nodes, we prove that a fastest convergence can be reached in nm = n log(2) n node updates via symmetric gossiping. On the other hand, under asymmetric gossip among n = 2(m) + rnodes with 0 <= r <= 2(m), it takes at least mn + 2r node updates for achieving finite-time convergence. It is also shown that the existence of finite-time convergent gossiping often imposes strong structural requirements on the underlying interaction graph. Finally, we apply our results to gossip algorithms in quantum networks, where the goal is to control the state of a quantum system via pairwise interactions. We show that finite-time convergence is never possible for such systems. |
| 资助项目 | Knut and Alice Wallenberg Foundation ; Swedish Research Council ; KTH SRA TNG ; NKBRPC[2011CB302400] ; NSFC of China[11301518] ; National Center for Mathematics and Interdisciplinary Sciences, CAS |
| WOS研究方向 | Computer Science ; Engineering ; Telecommunications |
| 语种 | 英语 |
| WOS记录号 | WOS:000386238600018 |
| 出版者 | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/23914]  |
| 专题 | 系统科学研究所 |
| 通讯作者 | Shi, Guodong |
| 作者单位 | 1.Australian Natl Univ, Res Sch Engn, Coll Engn & Comp Sci, GPO Box 4, Canberra, ACT 2601, Australia 2.Chinese Acad Sci, Key Lab Math Mechanizat, Acad Math & Syst Sci, Beijing 100190, Peoples R China 3.KTH Royal Inst Technol, ACCESS Linnaeus Ctr, S-10044 Stockholm, Sweden |
| 推荐引用方式 GB/T 7714 | Shi, Guodong,Li, Bo,Johansson, Mikael,et al. Finite-Time Convergent Gossiping[J]. IEEE-ACM TRANSACTIONS ON NETWORKING,2016,24(5):2814-2826. |
| APA | Shi, Guodong,Li, Bo,Johansson, Mikael,&Johansson, Karl Henrik.(2016).Finite-Time Convergent Gossiping.IEEE-ACM TRANSACTIONS ON NETWORKING,24(5),2814-2826. |
| MLA | Shi, Guodong,et al."Finite-Time Convergent Gossiping".IEEE-ACM TRANSACTIONS ON NETWORKING 24.5(2016):2814-2826. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。