Multi-session function computation and multicasting in undirected graphs

Sreeram Kannan, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

In the function computation problem, certain nodes of an undirected graph have access to independent data, while some 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 function computation is possible on a capacitated graph; the capacities on the edges of the graph impose constraints on the communication rate. We consider a simple class of computation strategies based on Steiner-tree packing (so-called em computation trees), which does not involve block coding and has minimal delay. With a single terminal requiring function computation, computation trees are known to be optimal when the underlying graph is itself a directed tree, but have arbitrarily poor performance in general directed graphs. Our main result is that computation trees are em near optimal for a wide class of function computation requirements even at em multiple terminals in em undirected graphs. The key technical contribution involves connecting approximation algorithms for Steiner cuts in undirected graphs to the function computation problem. Furthermore, we show that existing algorithms for Steiner tree packings allow us to compute approximately optimal packings of computation trees in polynomial time. We also show a close connection between the function computation problem and a communication problem involving multiple multicasts.

Original languageEnglish (US)
Article number6481624
Pages (from-to)702-713
Number of pages12
JournalIEEE Journal on Selected Areas in Communications
Volume31
Issue number4
DOIs
StatePublished - Apr 4 2013

Keywords

  • Function computation
  • Steiner packing
  • capacity
  • computation trees
  • multicasting
  • multiple unicast
  • network coding
  • sensor networks

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

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

  • Cite this