Continuous Communication Complexity

Alice and Bob are seeing a continuously changing set of numbers. At time t, set Alice has is A_t and set Bob has is B_t. A_t and B_t each change by addition or removal of an element during each time step. They communicate with Carole independently (one way or two way). Carole must report |A_t union B_t|, at all times t. The goal is to minimize the total number of bits sent between (Alice,Bob) and (Carole). Is there a good theory one can develop?

Notes: One should allow Carole to approximate |A_t \union B_t|. This seems related to Slepian-Wolf where A and B independently communicate their individual streams to C and the goal is to make use of mutual information in their streams. Things get tricky when we allow A, B or C use models to predict how A_t, B_t vary over time t.

Refs: There has been a few papers recently in the database community that give upper bounds on the number of bits communicated for different problems. It is called distributed, continuous streaming. There is a survey and a tutorial by Graham Cormode and Minos Garofalakis. What we need is a good theory and a semblance of lower bounds.