Aggregation in dynamic networks
Alejandro Cornejo, Seth Lewis Gilbert, Calvin C. Newport · 2012
The aggregation problem assumes that every process starts an execution with a unique token (an abstraction for data). The goal is to collect these tokens at a minimum number of processes by the end of the execution. This problem is particularly relevant to mobile networks where peer-to-peer communication is cheap (e.g., using 802.11 or Bluetooth), but uploading data to a central server can be costly (e.g., using 3G/4G). With this in mind, we study this problem in a dynamic network model, in which the communication graph can change arbitrarily from round to round.