The Research On Advanced Gossip Algorithms Based On Superposition Coding

The nature of distributed computing is a combination of computing andcommunication, thus the key work of research on distributed computing is designinghigh-efficiency and low-complexity algorithms. Gossip algorithm, with a nature ofsimplicity, robustness and scalability, is well adapted to the distributed networkenvironment, and has been widely used in distributed information dissemination, averageconsensus and load balancing. However, current research on Gossip algorithms mainlyfocuses on the computing part but ignores its communication part, especially in wirelesscommunication environment.In comparison with cable channels, the wireless channels have several features, likethe scalability of network topology, time invariance and noise of channels, and thebroadcast nature of wireless transmissions. On one hand, these features make theenvironment of wireless channels worse than cable channels, thus causing wirelesscommunication easily affected by noise, channel fading and co-channel interference. Onthe other hand, they provide convenience for information transmission because thebroadcast nature can greatly improve the efficiency of information spreading.Traditional Gossip algorithms have superior performance in cable distributednetworks, but when applied to wireless environment, some potential problems will leadperformance degradation. If properly making use of the broadcast and superpositionnature of wireless channels, we can design advanced Gossip algorithms with betterperformance.Based on the above considerations, we made in-depth investigations on thebackground of traditional Gossip algorithms and found the flaws and shortages. Later on,we did in-depth research on broadcast nature of wireless channel exemplified with thedistributed averaging problem. We proposed an advanced broadcast Gossip algorithmbased on superposition coding. Theoretical analysis and experimental results show that ouralgorithm greatly accelerates the convergence rate. In application scenarios wherealgorithm efficiency and communication overhead is very important, the proposedalgorithm significantly outperforms the traditional ones.