gossip and geographic routing

Having opening night for a play at the same time as a conference paper deadline is somewhat killer, but everything seems to have turned out well:

Geographic Gossip : Efficient Aggregation for Sensor Networks
A.G. Dimakis, A.D. Sarwate, and M.J. Wainwright

Gossip algorithms for aggregation have recently received significant attention for sensor network applications because of their simplicity and robustness in noisy and uncertain environments. However, gossip algorithms can waste significant energy by essentially passing around redundant information multiple times. Specifically, for realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is caused by slow mixing times of random walks on those graphs. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing a simple resampling method, we can demonstrate substantial gains over previously proposed gossip protocols. In particular, for random geometric graphs, our algorithm computes the true average to accuracy $1/n^a$ using $O(n^{1.5}\sqrt{\log n})$ radio transmissions, which reduces the energy consumption by a $\sqrt{\frac{n}{\log n}}$ factor over standard gossip algorithms.

Advertisement

post 501 : a recommendation

Cantata 140 : “Wachet auf, ruft uns die Stimme” is really one of most amazing pieces ever written. When Ed Cohen declared this in the composition seminar, I assumed he was just waxing poetic about the Baroque era. But just listen to the first movement, when Bach drops out the continuo on “sie rufen uns mit hellem Munde” to let the chorus climb and soar, suspended, before regrounding them with “wo seid ihr klugen Jungfrauen? Wohl auf, der Bräut’gam kommt.” Fantastisch.