TY - GEN

T1 - Multi-terminal function multicasting in undirected graphs

AU - Kannan, Sreeram

AU - Viswanath, Pramod

PY - 2013/12/19

Y1 - 2013/12/19

N2 - In the function computation problem, certain nodes of an undirected graph have access to independent data, while certain other nodes of the graph require certain functions of the data; this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which the function computation is possible on a capacitated graph. We consider a general model of function computation, which we term as multi-session function multicasting. In this general model, there are K independent sessions sharing the communication infrastructure; in each session, a set of D destinations all want the same function of a group of S sources. This traffic model generalizes various well known traffic models like the classical model of function computation(K = 1, D = 1), multiple-unicasting (S = 1, D = 1) and multicasting (K = 1, S = 1). For this general model, we propose a simple achievable strategy in which the function is computed for each session using Steiner trees at a specific destination and then distributed to the other destinations also using Steiner trees. Thus, in our proposed strategy, Steiner trees play the dual role of computation trees and also that of multicasting trees. Our main result is that this achievable strategy is near optimal for multi-session function multicasting of a wide class of functions in undirected graphs. The key technical contribution involves relating algorithmic work on Steiner cuts in undirected graphs to the function computation problem.

AB - In the function computation problem, certain nodes of an undirected graph have access to independent data, while certain other nodes of the graph require certain functions of the data; this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which the function computation is possible on a capacitated graph. We consider a general model of function computation, which we term as multi-session function multicasting. In this general model, there are K independent sessions sharing the communication infrastructure; in each session, a set of D destinations all want the same function of a group of S sources. This traffic model generalizes various well known traffic models like the classical model of function computation(K = 1, D = 1), multiple-unicasting (S = 1, D = 1) and multicasting (K = 1, S = 1). For this general model, we propose a simple achievable strategy in which the function is computed for each session using Steiner trees at a specific destination and then distributed to the other destinations also using Steiner trees. Thus, in our proposed strategy, Steiner trees play the dual role of computation trees and also that of multicasting trees. Our main result is that this achievable strategy is near optimal for multi-session function multicasting of a wide class of functions in undirected graphs. The key technical contribution involves relating algorithmic work on Steiner cuts in undirected graphs to the function computation problem.

UR - http://www.scopus.com/inward/record.url?scp=84890405317&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84890405317&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2013.6620643

DO - 10.1109/ISIT.2013.6620643

M3 - Conference contribution

AN - SCOPUS:84890405317

SN - 9781479904464

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2334

EP - 2338

BT - 2013 IEEE International Symposium on Information Theory, ISIT 2013

T2 - 2013 IEEE International Symposium on Information Theory, ISIT 2013

Y2 - 7 July 2013 through 12 July 2013

ER -