Title: Tight Bounds for Distributed Streaming

Speaker: Qin Zhang, MADALGO, Aarhus Univ.

Time/Date:  Friday, Aug 11, 11-12
Location: Room 4483

Abstract:

In this talk we will discuss the distributed streaming model. In this
model, we have k sites, each receiving a stream of elements over time.
There is a designated coordinator who would like to track, that is,
maintain continuously at all times, some function f of all the
elements received from the k sites. There is a two-way communication
channel between each site and the coordinator, and the goal is to
track f with minimum communication. This model is motivated by
applications in distributed databases, network monitoring and sensor
networks.

In this talk we will first introduce the model and briefly review the
existing results in this model, and then focus on proving lower bounds
for two basic problems: F0 (number of distinct elements) and F2 (size
of self join). The lower bounds are proved using a new
technique/framework called "composition" in the multiparty
number-in-hand communication complexity.