Avancées en théorie de l'information et codage-codage et stockage distribués de sources dans les réseaux

Nous vous rappelons que, afin de garantir l'accès de tous les inscrits aux salles de réunion, l'inscription aux réunions est gratuite mais obligatoire.

Inscriptions closes à cette réunion.

Inscriptions

7 personnes membres du GdR ISIS, et 15 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 0 personnes.

Annonce

Journée du GdR ISIS sur le thème «Avancées en théorie de l’information et codage – codage et stockage distribués de sources dans les réseaux »
 

Le jeudi 28 Novembre 2013 à Télécom ParisTech (Paris 13e), Amphithéâtre Émeraude

Cette journée thématique organisée par le GdR ISIS est consacrée aux dernières avancées dans le
domaine du codage distribué de sources et du stockage distribué de l’information.

La conférence sera également diffusée sur Ximinds: http://www.ximinds.com

Organisateurs :
Abdellatif Zaidi (abdellatif.zaidi@univ-mlv.fr)
Mérouane Debbah (merouane.debbah@supelec.fr)
 

Les membres du GdR sont priés de s’inscrire sur le site http://gdr-isis.fr/. Toute autre personne
intéressée par cette journée est invitée à contacter les organisateurs.

 

Programme
9h30-9h40 Accueil
9h40-10h20 Gerhard Kramer (Technische Universität München (TUM), Germany)
Broadcast with Receiver Side Information.
10h20-11h Prakash Ishwar (Boston University, USA)
Interactive Source Coding and Computation : Benefits, Ultimate Limits, and Challenges.
11h00-11h10 Pause
11h10-11h50 Michael Gastpar (EPFL, Switzerland)
Algebraic Structure in Distributed Source Coding.
11h50-12h30 Michèle Wigger (Télécom ParisTech, France)
New Results on the Kaspi/Heegard-Berger Problem.
12h30-14h00 Déjeuner
14h00-14h40 Jean-Claude Belfiore (Télécom ParisTech, France)
Ideal Lattices and the computation of a nonlinear function on a wireless channel.
14h40-15h20 Aslan Tchamkerten (Télécom ParisTech, France)
Cooperation in Distributed computation
15h20-16h00 Stefan Valentin (Alcatel-Lucent, Germany)
Anticipatory Buffering for Wireless Media Streaming.
16h00-16h10 Pause
16h10-16h50 Laurent Massoulié (Inria, Saclay, France)
Content placement in distributed systems for efficient load balancing
16h50-17h30 Jean-Louis Guenego (Chaire Alcatel-Lucent, Supélec, France)
Open Cloud Protocol applied to CDN.
17h30-18h10 Nicolas Le Scouarnec (Technicolor, Rennes, France)
Coordinated Regenerating Codes.

 

Résumés des interventions

Jean-Claude Belfiore (Télécom ParisTech, France)
Title : Ideal Lattices and the computation of a nonlinear function on a wireless channel.
Abstract : Suppose that a wireless network is used as a distributed computer. Each node of
the network has to reliably compute a function of its inputs and forward the result. The case
where the function is linear has already been addressed in the celebrated contribution of Nazer &
Gastpar who introduced the so-called "Compute-and-Forward". By using lattice codes constructed
via construction A, they proved that the "Computation Rate" is achievable. Lattices were mainly
used because of their linearity. In this work, we are interested in the computation of nonlinear
functions in a finite ring. Lattice codes can also be used only if we can define an inner multiplication
in the lattice. We show that a family of lattices called ideal lattices enjoy this property and we also
propose a framework where we connect ideal lattices to construction.

Michael Gastpar (EPFL, Switzerland)
Title : Algebraic Structure in Distributed Source Coding.
Abstract : The information-theoretic understanding of distributed compression has been shaped by
the clever "binning" idea of Slepian and Wolf (1974), and the best currently known general results
are all based on combining this idea with standard vector quantization. Recent work, however, has
shown that this strategy by itself is not sufficient to attain optimal performance in all cases. In
most of the new example scenarios, the best known performance is found by modifying the random
coding argument underlying the vector quantization to include algebraic structure. The talk surveys
and discusses some of these examples, along with novel variations.

Jean-Louis Guenego (Chaire Alcatel-Lucent, Supéléc)
Title : Open Cloud Protocol applied to CDN
Abstract : Open Cloud Protocol (OCP) is an open software protocol framework for defining a
secure and reliable cloud storage system, fully distributed, in hostile environment, where storage
resource usage can be measured for trading purpose and finally a system that aims to reduce
network traffic for a given level of user experience (CDN). In this talk, we will describe in details
the combination of the different technical components such as distributed hashtable, multi-ring
topologies addressing, immutable objects, connection objects, billable objects, caching on the road,
object location system. We will end up the talk with a live demo of the Cloud storage application.
OCP received the Qualcom prize award in 2012 and the OSEO prize in 2013.

Prakash Ishwar (University of Boston, USA)
Title : Interactive Source Coding and Computation : Benefits, Ultimate Limits, and Challenges.
Abstract : Problems of one-way communication and information reproduction have dominated
the research landscape of information theory and have yielded its greatest triumphs. In contrast,
problems of interactive communication and computation, where information can flow from sources
towards destinations and back, possibly over multiple rounds, have received far less attention and are
less well understood. This is primarily due to the complex interplay between source characteristics,
network topology, and the nature of the computations desired. This talk will sketch some recent
successes in tackling interactive coding problems highlighting the impact of the number of rounds
of interaction on performance.

Gerhard Kramer (TU Munich, Germany)
Title : Broadcast with Receiver Side Information.
Abstract : Two message strings are to be reliably communicated over a memoryless broadcast
channel to two receivers. Each receiver has as side information and is interested in one or both of
the strings. Coding rates are developed for several cases, including bit strings with vanishing error
probability, Gaussian strings with quadratic distortion functions, and other scenarios.

Nicolas Le Scouarnec (Technicolor, Rennes, France)
Title : Coordinated Regenerating Codes
Abstract : Erasure correcting codes are widely used to ensure data persistence in distributed
storage systems. However, in case of a failure, repairing a single lost device implies decoding the
whole file resulting in high network costs. Dimakis et al. showed that by applying network coding to
distributed storage system, the repair cost can be significantly reduced. This seminal work has since
been the basis for numerous works on specific coding schemes. In the first part of this talk, we will
give an overview of regenerating codes and present their extension to the case of multiple failures,
namely coordinated regenerating codes. We will also discuss the impact of the various parameters
of regenerating codes on the repair cost. In a second part of the talk, we will give an overview of
recent research in the area of exact (i.e., deterministic) regenerating codes and highlight some of
the most interesting constructions for use in practical systems.

Laurent Massoulié (Inria, Saclay, France)
Title : Content placement in distributed systems for efficient load balancing
Abstract : We consider the problem of content placement in large-scale distributed systems for
efficiently handling workloads of requests for content. We characterize the performance of optimal
load balancing for general random placement strategies. We use this to show how to improve upon
the popular “proportional placement" strategy.We also establish a form of insensitivity, namely : the
system inefficiency decays exponentially fast with the memory resource, irrespective of the precise
content replication and the workload. We contrast this with the performance of simpler “greedy"
load balancing methods well suited to dynamic scenarios with request arrivals and departures.

Aslan Tchamkerten (Télécom ParisTech, France)
Title : Cooperation in Distributed computation
Abstract : A function of two separate sources of information is to be computed at a receiver. How
many bits of information need to be conveyed to the receiver ? In this talk we will address this
question when the transmitters are allowed to cooperate, i.e., when the transmitters are allowed to
exchange some information before sending data to the receiver

Stefan Valentin (Alcatel-Lucent, Germany)
Title : Anticipatory Buffering for Wireless Media Streaming.
Abstract : Media streaming is heavily demanded by mobile users but the time-variant wireless
channel causes two major problems. Low channel states lead to an underrun of the handheld’s playout
buffer, thus, degrading streaming quality. High channel states, however, cause current streaming
clients to accumulate very long buffers. Such ‘over buffering’ wastes channel resources when the user
decides to jump inside a media stream or to change it. In this talk, we will introduce anticipatory
buffering as a solution to these problems. Assuming that we can predict the average wireless channel
state for some seconds ahead, we will systematically walk through ‘anticipative’ optimization
strategies for wireless video streaming. After formalizing the optimization problems, we will discuss
optimal real-time solutions, rate-memory tradeoffs, and the results of recent experimental studies.

Michèle Wigger (Télécom ParisTech, France)
Title : New Results on the Kaspi/Heegard-Berger Problem.
Abstract : We study the lossless Kaspi/Heegard-Berger problem where a single encoder compresses
two sources and conveys the resulting common description to two decoders. With this description
and some a priori side-information (which is not available at the encoder) each decoder attempts to
reconstruct its desired source. Our aim is to characterize the minimum rate of description that allows
the decoders to succeed with a probability arbitrarily close to 1. We characterize this minimum
rate of description for the class of conditionally less noisy side-information. This result generalizes
the previous results by Kaspi and Heegard-Berger for degraded side-information. Our result
requires a new converse proof and in particular a new entropy characterization lemma. We further
present results for the lossy Kaspi/Heegard-Berger problem and for the successive refinement problem
with side-information where we extend previous results by Steinberg-Merhav and Tian-Diggavi
to conditionally less noisy side-information.
In a second part of the talk, we consider a slight variation of the lossless Kaspi/Heegard-Berger
problem where the side-information is made available also to the encoder. We show that for different
classes of setups (e.g., physically degraded setups) knowing the side-information at the encoder does
not increase the minimum description rate. But we also provide first examples where knowing the
decoders’ side-information at the encoder strictly decreases the minimum description rate. The same
holds also when the encoder is informed only partially about the decoders’ side-information.
These results are based on joint work with Thomas Laich (ETH Zurich), Tobias Oechtering (KTH
Stockholm), and Roy Timo (University of Southern Australia).
 

Programme

Résumés des contributions