COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Optimization and Incentives Seminar > Distributed Computation over Random Geometric Graphs: Some Asymptotic Results

## Distributed Computation over Random Geometric Graphs: Some Asymptotic ResultsAdd 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
- DPMMS Lists
- DPMMS info aggregator
- DPMMS lists
- Economics and Computer Science Talks
- 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. |
## Other listsJunior Algebra/Logic/Number Theory seminar Open Innovation CRISPR Genome Editing Courses## Other talksBringing Personality Theory Back to Life: On Persons-in-Context, Idiographic Strategies, and Lazarus Populism and Central Bank Independence My ceramic practice, and Moon Jars for the 21st century Developing an optimisation algorithm to supervise active learning in drug discovery The Anne McLaren Lecture: CRISPR-Cas Gene Editing: Biology, Technology and Ethics Childhood adversity and chronic disease: risks, mechanisms and resilience. |