Multi-terminal function multicasting in undirected graphs

Sreeram Kannan, Pramod Viswanath

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2013 IEEE International Symposium on Information Theory, ISIT 2013
Pages2334-2338
Number of pages5
DOIs
StatePublished - Dec 19 2013
Event2013 IEEE International Symposium on Information Theory, ISIT 2013 - Istanbul, Turkey
Duration: Jul 7 2013Jul 12 2013

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2013 IEEE International Symposium on Information Theory, ISIT 2013
CountryTurkey
CityIstanbul
Period7/7/137/12/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Multi-terminal function multicasting in undirected graphs'. Together they form a unique fingerprint.

  • Cite this

    Kannan, S., & Viswanath, P. (2013). Multi-terminal function multicasting in undirected graphs. In 2013 IEEE International Symposium on Information Theory, ISIT 2013 (pp. 2334-2338). [6620643] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2013.6620643