Network Coded Gossip with Correlated Data (and a little bit on distributed scheduling)
We design and analyze gossip algorithms for networks with correlated data. In these networks, either the data to be distributed, the data already available at the nodes, or both, are correlated. Although coding schemes for correlated data have been studied extensively, the focus has been on characterizing the rate region in static memory-free networks. In a gossip-based scheme, however, nodes communicate among each other by continuously exchanging packets according to some underlying communication model. The main figure of merit in this setting is the stopping time- the time required until nodes can successfully decode. While Gossip schemes are practical, distributed and scalable, they have only been studied for uncorrelated data. We wish to close this gap by providing techniques to analyze network coded gossip in (dynamic) networks with correlated data. We give a clean framework for oblivious network models that applies to a multitude of network and communication scenarios, specify a general setting for distributed correlated data, and give tight bounds on the stopping times of network coded protocols in this wide range of scenarios.
If time permits, we will shortly discuss novel distributed scheduling algorithms for multi-user MIMO systems. These algorithms do not require each user to send its channel state information (CSI) to a central unit, nor do they require communication between the users themselves, yet, their performance closely approximates that of a centrally-controlled system, which is able to schedule the strongest user in each time-slot. Possible applications include modern 4G networks such as 3GPP LTE or random access protocols. Our analysis is based on a novel application of the Point-Process approximation, enabling the computation of the capacity for non-homogeneous cases, such as non-identically distributed users, or handling various QoS considerations, which to date had been unresolved.
Based on joint works with B. Haeupler, C. Avin, M. Medard, S. Kampeas and O. Gurewitz.