Distributed Computation over Random Geometric Graphs: Some Asymptotic Results

Add to your list(s) Download to your calendar using vCal

• D. Manjunath, Department of Electrical Engineering of IIT, Bombay
• Thursday 04 December 2008, 14:00-15:00
• MR5, CMS, Wilberforce Road, Cambridge, CB3 0WB.

If you have a question about this talk, please contact Neil Walton.

The problem setting is motivated by applications in wireless sensor networks. $n$ nodes are assumed distributed uniformly in the unit square. Node $i$ has data $x_i.$ The objective is to obtain $f(x_1,\ldots, x_n).$ The nodes communicate over a wireless communication channel and form a multihop radio network. Spatial reuse is determined by the protocol model.

An overview of the results for noisefree, organized networks and a summary of our results on networks with noisy links is first provided. Two variations to the basic model are considered. First, a method to compute a probably approximately correct (PAC) histogram of observations with a refresh rate of $\Theta(1)$ time units per histogram sample is described. This is then extended to a network with noisy links with the same refresh rate. This refresh rate for PAC that of $\Theta(1/\log n)$ for exact computation in noisy networks. The improvement is achieve by operating in the super-critical thermodynamic regime where the transmission range is smaller, leading to an increased spatial reuse. Computation is over a giant components rather than over a connected network.

Second, we motivate and develop the notion of structure-free networks and analyse them. In these networks, nodes do not have an identity or a sense of time. Thus traditional `organized’ protocols cannot be used here and we resort to an Aloha MAC with local computation. We describe the performance of this network to compute the MAX and the histogram. Here, links are assumed noisefree.

This talk is part of the Optimization and Incentives Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Economics and Computer Science Talks
• Hanchen DaDaDash
• Interested Talks
• MR5, CMS, Wilberforce Road, Cambridge, CB3 0WB
• Optimization and Incentives Seminar
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.