Computing along the routes via gossiping

Mehmet E. Yildiz, Anna Scaglione, Tuncer C. Aysal

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

3 Scopus citations


In this paper, we focus on a class of information propagation problems where a group of nodes (destinations) wants to gather a function of data that are stored by another disjoint group of nodes (sources). We assume that the function can be decomposed as a sum of functions of local variables. We study an algorithm which computes the function along the routes from sources to destinations iteratively, via gossiping among near neighbors. More specifically, in our protocol each node updates its own local value as a linear combination of its neighbors' values, repeatedly. Given the underlying network connectivity and the source-destination sets, we provide necessary and sufficient conditions for the feasibility of non-negative update weights. We further introduce topology based necessary conditions for the feasibility and discuss about known infeasible scenarios. By introducing the notion of source clusters, we also show that the complexity of the design problem is not directly related to the number of source nodes but the number of source clusters in the network.

Original languageEnglish (US)
Title of host publication2009 IEEE Information Theory Workshop, ITW 2009
Number of pages5
StatePublished - Dec 7 2009
Externally publishedYes
Event2009 IEEE Information Theory Workshop, ITW 2009 - Taormina, Sicily, Italy
Duration: Oct 11 2009Oct 16 2009

Publication series

Name2009 IEEE Information Theory Workshop, ITW 2009


Other2009 IEEE Information Theory Workshop, ITW 2009
CityTaormina, Sicily


  • Distributed computing
  • Gossiping protocols
  • Information flow
  • Network coding

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Information Systems
  • Electrical and Electronic Engineering


Dive into the research topics of 'Computing along the routes via gossiping'. Together they form a unique fingerprint.

Cite this