Efficient dynamic aggregation

We consider the problem of dynamic aggregation of inputs over a large graph. A dynamic aggregation algorithm must continuously compute the result of a given aggregation function over a dynamically changing set of inputs. To be efficient, such an algorithm should refrain from sending messages when the inputs do not change, and should perform local communication whenever possible. We show an instance-based lower bound on the efficiency of such algorithms, and provide two algorithms matching this bound. The first, MultI-LEAG, re-samples the inputs at intervals that are proportional to the graph size, and is extremely message efficient. The second, DynI-LEAG, more closely monitors the aggregate value by sam-pling it more frequently, at the cost of slightly higher message complexity.