Research on Gossip Algorithms with Binary Exponential Backoff

Weiqing CHENG; Lei ZHANG

doi:10.11999/JEIT200094

Volume 43 Issue 12

Dec. 2021

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2021 > 43(12): 3486-3495

Weiqing CHENG, Lei ZHANG. Research on Gossip Algorithms with Binary Exponential Backoff[J]. Journal of Electronics & Information Technology, 2021, 43(12): 3486-3495. doi: 10.11999/JEIT200094

Citation:

Weiqing CHENG, Lei ZHANG. Research on Gossip Algorithms with Binary Exponential Backoff[J]. Journal of Electronics & Information Technology, 2021, 43(12): 3486-3495. doi: 10.11999/JEIT200094

Weiqing CHENG, Lei ZHANG. Research on Gossip Algorithms with Binary Exponential Backoff[J]. Journal of Electronics & Information Technology, 2021, 43(12): 3486-3495. doi: 10.11999/JEIT200094

Citation:

Weiqing CHENG, Lei ZHANG. Research on Gossip Algorithms with Binary Exponential Backoff[J]. Journal of Electronics & Information Technology, 2021, 43(12): 3486-3495. doi: 10.11999/JEIT200094

PDF( 1414 KB)

Research on Gossip Algorithms with Binary Exponential Backoff

doi: 10.11999/JEIT200094

Weiqing CHENG^{1, 2
,
,},
Lei ZHANG¹

1.
School of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
2.
Key Laboratory of Computer Network and Information Integration (Ministry of Education), Southeast University, Nanjing 211189, China

Received Date: 2020-02-11
Rev Recd Date: 2021-03-23

Available Online: 2021-06-03

Publish Date: 2021-12-21

Abstract

Abstract

In order to reduce the communication cost of classic Gossip algorithm for information dissemination, an improved Gossip algorithm BEBG (Gossip with Binary Exponential Backoff) is proposed, which combines the binary exponential backoff algorithm with Gossip algorithm. Its information dissemination strategy is that the more times that a node has received the same information, the lower probability it continues to spread the information. Theoretical analysis and simulation results show that the BEBG can effectively reduce the redundancy of information propagation, and compared with the classic Gossip algorithm, the network load is reduced by about 61% when there are 10⁴ nodes in the network. In order to solve the problem of edge nodes in the BEBG, two improved BEBG algorithms PBEBG that introduces Pull operations and NBEBG that introduces pushing information to a Neighbor node are further proposed. Experimental results show that the two algorithms can eliminate the edge nodes, and when there are 10⁴ nodes in the network, they reduce the network load by about 34% and 37% respectively compared with the corresponding improved classic Gossip algorithms which introduce the same pull and push respectively.
- Distributed systems,
- Information dissemination,
- Gossip algorithm

FullText(HTML)

References(23)

References

[1]	DEMERS A, GREENE D, HOUSER C, et al. Epidemic algorithms for replicated database maintenance[J]. ACM SIGOPS Operating Systems Review, 1988, 22(1): 8–32. doi: 10.1145/43921.43922
[2]	GUPTA I, VAN RENESSE R, and BIRMAN K P. Scalable fault-tolerant aggregation in large process groups[C]. 2001 International Conference on Dependable Systems and Networks, Gothenburg, Sweden, 2001: 433–442. doi: 10.1109/DSN.2001.941427.
[3]	JELASITY M and BABAOGLU O. T-Man: Gossip-based overlay topology management[C]. The 3rd International Workshop on Engineering Self-Organising Applications, Utrecht, The Netherlands, 2005: 1–15. doi: 10.1007/11734697_1.
[4]	PROVENSI L L, SINGH A, ELIASSEN F, et al. Maelstream: Self-organizing media streaming for many-to-many interaction[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(6): 1342–1356. doi: 10.1109/TPDS.2018.2791599
[5]	LIU Mengdi, XU Guangquan, ZHANG Jun, et al. Roundtable gossip algorithm: A novel sparse trust mining method for large-scale recommendation systems[C]. The 18th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2018, Guangzhou, China, 2018: 495–510. doi: 10.1007/978-3-030-05063-4_37.
[6]	LAVINIA A, DOBRE C, POP F, et al. A failure detection system for large scale distributed systems[J]. International Journal of Distributed Systems and Technologies, 2011, 2(3): 64–87. doi: 10.1109/CISIS.2010.29
[7]	VAN RENESSE R, BIRMAN K P, and VOGELS W. Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining[J]. ACM Transactions on Computer Systems, 2003, 21(2): 164–206. doi: 10.1145/762483.762485
[8]	PIETRO R D and MICHIARDI P. Gossip-based aggregate computation: Computing faster with non address-oblivious schemes[C]. The 27th ACM Symposium on Principles of Distributed Computing, Toronto, Canada, 2008: 442. doi: 10.1145/1400751.1400837.
[9]	WANG Gang, WANG Zhiyue, and WU Jie. A local average broadcast gossip algorithm for fast global consensus over graphs[J]. Journal of Parallel and Distributed Computing, 2017, 109: 301–309. doi: 10.1016/j.jpdc.2017.05.008
[10]	张仕将, 柴晶, 陈泽华, 等. 基于Gossip协议的拜占庭共识算法[J]. 计算机科学, 2018, 45(2): 20–24. doi: 10.11896/j.issn.1002-137X.2018.02.004 ZHANG Shijiang, CHAI Jing, CHEN Zehua, et al. Byzantine consensus algorithm based on gossip protocol[J]. Computer Science, 2018, 45(2): 20–24. doi: 10.11896/j.issn.1002-137X.2018.02.004
[11]	WANG Huiwei, LIAO Xiaofeng, WANG Zidong, et al. Distributed parameter estimation in unreliable sensor networks via broadcast gossip algorithms[J]. Neural Networks, 2016, 73: 1–9. doi: 10.1016/j.neunet.2015.09.008
[12]	AZIMI R and SAJEDI H. Peer sampling gossip-based distributed clustering algorithm for unstructured P2P networks[J]. Neural Computing and Applications, 2018, 29(2): 593–612. doi: 10.1007/s00521-017-3119-0
[13]	AZIMI R and SAJEDI H. A decentralized gossip based approach for data clustering in peer-to-peer networks[J]. Journal of Parallel and Distributed Computing, 2018, 119: 64–80. doi: 10.1016/j.jpdc.2018.03.009
[14]	FEMMINELLA M, FRANCESCANGELI R, REALI G, et al. Gossip-based signaling dissemination extension for next steps in signaling[C]. 2012 IEEE Network Operations and Management Symposium, Maui, United States, 2012: 1022–1028. doi: 10.1109/NOMS.2012.6212024.
[15]	崔闻. 基于Gossip的无线传感器网络定位算法研究[D]. [硕士论文], 哈尔滨工业大学, 2014. CUI Wen. Research on gossip-based localization algorithms in wireless sensor networks[D]. [Master dissertation], Harbin Institute of Technology, 2014.
[16]	LIU Yan, NIU Di, and KHABBAZIAN M. Cooper: Expedite batch data dissemination in computer clusters with coded gossips[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(8): 2204–2217. doi: 10.1109/TPDS.2017.2654242
[17]	KERMARREC A M and VAN STEEN M. Gossiping in distributed systems[J]. ACM SIGOPS Operating Systems Review, 2007, 41(5): 2–7. doi: 10.1145/1317379.1317381
[18]	ESPOSITO C, CASTIGLIONE A, PALMIERI F, et al. Improving the gossiping effectiveness with distributed strategic learning[J]. Future Generation Computer Systems, 2017, 71: 221–233. doi: 10.1016/j.future.2016.11.006
[19]	HOEFLER T, BARAK A, SHILOH A, et al. Corrected gossip algorithms for fast reliable broadcast on unreliable systems[C]. 2017 IEEE International Parallel and Distributed Processing Symposium, Orlando, United States, 2017: 357–366. doi: 10.1109/IPDPS.2017.36.
[20]	LI Bo, WU Junfeng, QI Hongsheng, et al. Boolean gossip networks[J]. IEEE/ACM Transactions on Networking, 2018, 26(1): 118–130. doi: 10.1109/TNET.2017.2763964
[21]	FERTIN G, PETERS J G, RAABE L, et al. Odd gossiping[J]. Discrete Applied Mathematics, 2017, 216: 550–561. doi: 10.1016/j.dam.2016.01.034
[22]	田振兴, 代杰. 基于改进Gossip协议的数据同步设计[J]. 指挥信息系统与技术, 2017, 8(5): 99–103. doi: 10.15908/j.cnki.cist.2017.05.017 TIAN Zhenxing and DAI Jie. Data synchronization design based on improved gossip protocol[J]. Command Information System and Technology, 2017, 8(5): 99–103. doi: 10.15908/j.cnki.cist.2017.05.017
[23]	HAEUPLER B, PANDURANGAN G, PELEG D, et al. Discovery through gossip[C]. The 24th ACM Symposium on Parallelism in Algorithms and Architectures, Pittsburgh, United States, 2012: 140–149. doi: 10.1145/2312005.2312031.