BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Distributed Computation over Random Geometric Graphs: Some Asympto
 tic Results - D. Manjunath\, Department of Electrical Engineering of IIT\,
  Bombay
DTSTART:20081204T140000Z
DTEND:20081204T150000Z
UID:TALK14902@talks.cam.ac.uk
CONTACT:Neil Walton
DESCRIPTION:The problem setting is motivated by applications in wireless s
 ensor networks. $n$ nodes are assumed distributed uniformly in the unit sq
 uare. 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 f
 orm a multihop radio network. Spatial reuse is determined by the protocol 
 model.\n\nAn overview of the results for noisefree\, organized networks an
 d 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 com
 pute a\nprobably approximately correct (PAC) histogram of observations wit
 h a refresh rate of $\\Theta(1)$ time units per histogram sample is descri
 bed. This is then extended to a network with noisy links with the same ref
 resh rate. This refresh rate for PAC that of $\\Theta(1/\\log n)$ for exac
 t computation in noisy networks. The improvement is achieve by operating i
 n\nthe super-critical thermodynamic regime where the transmission range is
  smaller\, leading to an increased spatial reuse. Computation is over a gi
 ant components rather than over a connected network.\n\nSecond\, we motiva
 te 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 tr
 aditional `organized' protocols  cannot be used here and we resort to an A
 loha MAC with local computation.  We  describe the performance of this net
 work to compute the MAX and the  histogram. Here\,\nlinks are assumed nois
 efree.
LOCATION:MR5\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR