Student: Deniz Ustebay, PhD Candidate
Supervisor: Supervisor: Michael Rabbat
Abstract: Greedy gossip with eavesdropping (GGE) is a novel randomized gossip algorithm that exploits the broadcast nature of wireless communications to converge rapidly without requiring that nodes know their geographic locations. When a node decides to gossip, rather than choosing one of its neighbors randomly, it greedily chooses to gossip with the neighbor whose values are most different from its own. We assume that all transmissions are wireless broadcasts so that nodes can keep track of their neighbors' values by eavesdropping on their communications. We show that the convergence of GGE is guaranteed for connected network topologies. We also study the rates of convergence and illustrate, through theoretical bounds and numerical simulations, that GGE consistently outperforms randomized gossip and performs comparably to geographic gossip on moderate-sized random geometric graph topologies.
[Full Description] [Paper (pdf format)]
|