Online Algorithms for Information Aggregation from Distributed and Correlated Sources

Chi Kin Chau, Majid Khonji, Muhammad Aftab

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


There is a fundamental tradeoff between the communication cost and the latency in information aggregation. Aggregating multiple communication messages over time can alleviate overhead and improve energy efficiency on one hand, but inevitably incurs information delay on the other hand. In the presence of uncertain future inputs, this tradeoff should be balanced in an online manner, which is studied by the classical dynamic TCP ACK problem for a single information source. In this paper, we extend dynamic TCP ACK problem to a general setting of collecting aggregate information from distributed and correlated information sources. In this model, distributed sources observe correlated events, whereas only a small number of reports are required from the sources. The sources make online decisions about their reporting operations in a distributed manner without prior knowledge of the local observations at others. Our problem captures a wide range of applications, such as in-situ sensing, anycast acknowledgement, and distributed caching. We present simple threshold-based competitive distributed online algorithms under different settings of intercommunication. Our algorithms match the theoretical lower bounds in order of magnitude. We observe that our algorithms can produce satisfactory performance in simulations and practical test bed.

Original languageBritish English
Article number7457233
Pages (from-to)3714-3725
Number of pages12
JournalIEEE/ACM Transactions on Networking
Issue number6
StatePublished - Dec 2016


  • communication cost
  • competitive analysis
  • distributed optimization problem
  • latency
  • Online algorithms


Dive into the research topics of 'Online Algorithms for Information Aggregation from Distributed and Correlated Sources'. Together they form a unique fingerprint.

Cite this