TY - JOUR
T1 - Computing along routes via gossiping
AU - Yildiz, Mehmet Ercan
AU - Scaglione, Anna
N1 - Funding Information:
Manuscript received June 29, 2009; accepted February 05, 2010. Date of publication March 11, 2010; date of current version May 14, 2010. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Ta-Sung Lee. This work was supported by the National Science Foundation by Grant NSF-ITR-CCR-042827. The material in this paper was presented in part at Asilomar 2008 [1], ITW, October 2009 [2], and CAMSAP, December 2009 [3].
PY - 2010/6
Y1 - 2010/6
N2 - In this paper, we study a class of distributed computing problems where a group of nodes (destinations) is interested in a function of data which are stored by another group of nodes (sources). We assume that the function of interest is separable, i.e., it can be decomposed as a sum of functions of local variables, a case that subsumes several interesting types of queries. One approach to solve this problem is to route raw information from the sources to the interested destinations by either unicasting or multicasting. The second approach is to compute the function of interest along some routes while propagating the information from the sources to the destinations. Considering the second scenario, the goal of this paper is to examine how information should be forwarded to the intended recipients, computing along the routes by gossiping with selected neighbors. Unlike efficient unicasting/multicasting problems, nodes are interested in a specific function of the data, rather than the raw data themselves. Moreover, unlike standard gossiping problems, in our case, the information needs to flow in a specific direction. Given the underlying network connectivity and the source-destination sets, we provide necessary and sufficient conditions on the update weights (referred to as codes) so that the destination nodes converge to the desired function of the source values. We show that the evolution of the source states does not affect the feasibility of the problem, and we provide a detailed analysis on the spectral properties of the feasible codes. We also study the problem feasibility under some specific topologies and provide guidelines to determine infeasibility. We also formulate different strategies to design codes, and compare the performance of our solution with existing alternatives.
AB - In this paper, we study a class of distributed computing problems where a group of nodes (destinations) is interested in a function of data which are stored by another group of nodes (sources). We assume that the function of interest is separable, i.e., it can be decomposed as a sum of functions of local variables, a case that subsumes several interesting types of queries. One approach to solve this problem is to route raw information from the sources to the interested destinations by either unicasting or multicasting. The second approach is to compute the function of interest along some routes while propagating the information from the sources to the destinations. Considering the second scenario, the goal of this paper is to examine how information should be forwarded to the intended recipients, computing along the routes by gossiping with selected neighbors. Unlike efficient unicasting/multicasting problems, nodes are interested in a specific function of the data, rather than the raw data themselves. Moreover, unlike standard gossiping problems, in our case, the information needs to flow in a specific direction. Given the underlying network connectivity and the source-destination sets, we provide necessary and sufficient conditions on the update weights (referred to as codes) so that the destination nodes converge to the desired function of the source values. We show that the evolution of the source states does not affect the feasibility of the problem, and we provide a detailed analysis on the spectral properties of the feasible codes. We also study the problem feasibility under some specific topologies and provide guidelines to determine infeasibility. We also formulate different strategies to design codes, and compare the performance of our solution with existing alternatives.
KW - Data aggregation
KW - Distributed computing
KW - Duplicate-sensitive data aggregation
KW - Gossiping protocols
UR - http://www.scopus.com/inward/record.url?scp=77952561008&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77952561008&partnerID=8YFLogxK
U2 - 10.1109/TSP.2010.2045421
DO - 10.1109/TSP.2010.2045421
M3 - Article
AN - SCOPUS:77952561008
SN - 1053-587X
VL - 58
SP - 3313
EP - 3327
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
IS - 6
M1 - 5428817
ER -