DocumentCode :
2257210
Title :
Distributed computation under bit constraints
Author :
Ayaso, Ola ; Shah, Devavrat ; Dahleh, Munther A.
Author_Institution :
Lab. for Inf. & Decision Syst., Massachusetts Inst. of Technol., Cambridge, MA, USA
fYear :
2008
fDate :
9-11 Dec. 2008
Firstpage :
4837
Lastpage :
4842
Abstract :
A network of nodes communicate via noisy channels. Each node has some real-valued initial measurement or message. The goal of each of the nodes is to acquire an estimate of a given function of all the initial measurements in the network. We survey our recent results that relate limitations imposed by the communication constraints to the nodes¿ performance in computing the desired function. In particular, we determine a lower bound on computation time that must be satisfied by any algorithm used by the nodes to communicate and compute, so that the mean square error in the nodes¿ estimates is within a given interval around zero. We apply the lower bound to a specific scenario where we find the bound to be asymptotically tight. Specifically, we consider a scenario where nodes are required to learn a linear combination of the initial values in the network while communicating over erasure channels. Our results suggest that in this scenario, the computation time depends reciprocally on ¿conductance.¿ Conductance is a property of the network which captures the information-flow bottle-neck that arises due to topology and channel capacities.
Keywords :
mean square error methods; telecommunication network topology; bit constraint; communication constraint; distributed computation; mean square error; network conductance; Channel capacity; Computer networks; Control systems; Decoding; Distributed computing; Laboratories; Mean square error methods; Network topology; USA Councils; Uncertainty;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Decision and Control, 2008. CDC 2008. 47th IEEE Conference on
Conference_Location :
Cancun
ISSN :
0191-2216
Print_ISBN :
978-1-4244-3123-6
Electronic_ISBN :
0191-2216
Type :
conf
DOI :
10.1109/CDC.2008.4739490
Filename :
4739490
Link To Document :
بازگشت