BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Optimization and Incentives Seminar
SUMMARY:Distributed Computation over Random Geometric Grap
hs: Some Asymptotic Results - D. Manjunath\, Depar
tment of Electrical Engineering of IIT\, Bombay
DTSTART;TZID=Europe/London:20081204T140000
DTEND;TZID=Europe/London:20081204T150000
UID:TALK14902AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/14902
DESCRIPTION:The problem setting is motivated by applications i
n 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 wi
reless communication channel and form a multihop r
adio network. Spatial reuse is determined by the p
rotocol model.\n\nAn overview of the results for n
oisefree\, organized networks and a summary of our
results on networks with noisy links is first pro
vided. Two variations to the basic model are consi
dered. First\, a method to compute a\nprobably app
roximately correct (PAC) histogram of observations
with a refresh rate of $\\Theta(1)$ time units pe
r histogram sample is described. This is then exte
nded to a network with noisy links with the same r
efresh rate. This refresh rate for PAC that of $\\
Theta(1/\\log n)$ for exact computation in noisy n
etworks. The improvement is achieve by operating i
n\nthe super-critical thermodynamic regime where t
he transmission range is smaller\, leading to an i
ncreased spatial reuse. Computation is over a gian
t components rather than over a connected network.
\n\nSecond\, we motivate and develop the notion of
structure-free networks and analyse them. In thes
e networks\, nodes do not have an identity or a se
nse of time. Thus traditional `organized' protocol
s cannot be used here and we resort to an Aloha M
AC with local computation. We describe the perfo
rmance of this network to compute the MAX and the
histogram. Here\,\nlinks are assumed noisefree.
LOCATION:MR5\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
CONTACT:Neil Walton
END:VEVENT
END:VCALENDAR