Information theory for distributed and asynchronous network communication

点击翻译按钮获取中文摘要

We are currently in the midst of a distributed revolution. Distributed ways of communicating, processing and computing are dislodging more traditional centralized architectures. Canonical examples of distributed communication systems are telecommunication networks, including wireless networks.However, this technological revolution has not always been followed by all the theoretical advances that could have been expected. This is the case for instance for information theory. Although it should play a central role in the theory of distributed communication systems, information theory has not obtained results in multi-user network theory as much significant as in the single-user case.I propose to re-consider multi-user information theory by using network models whose dynamics are based on partial orders. The main feature of these models is to provide a dynamics where events can occur in parallel. A recent implementation of fault diagnosis algorithms for the monitoring of telecommunication networks (on Alcatel platforms around Paris, by DistribCom research team from IRISA, Rennes, France) has shown the efficiency of these models, in a practical context. Concurrency models have been originally designed for their communication features. There is thus a natural place for interactions between concurrency theory and information theory. Information theory is based upon probability theory; these interactions must therefore be based upon probabilistic extensions of concurrency models. Such probabilistic extensions have been the topic of a research area only covered very recently. I have participated to this new research area through my PhD thesis and subsequent publications. Therefore my expertise in probabilistic concurrent systems makes me a natural candidate to explore the bridge between concurrency theory and information theory.From the mathematical point of view, this new framework constitutes a non-trivial extension of dynamical systems and stochastic processes theory. The main feature of concurrency models is that there is no global clock at the scale of the system. Instead, the time is partially ordered . Indeed, the system being distributed by nature, only local clocks can be defined at different nodes. Their synchronisation yields a time which is not totally ordered, but which is only partially ordered instead. The main issue, from the mathematical point of view, is the absence of a natural shift operator, which is the basis of classical dynamical systems theory. The objective of the project is thus to develop theoretical foundations for distributed and asynchronous communication, based on concurrency models. This amounts to define the notions of concurrent sources and channels, together with the associated notions of entropy (for sources) and capacity (for channels), then to derive entropy and coding theorems, and finally to design and implement coding and/or compression network algorithms.The work is to be done in collaboration with Pr Winskel's research team at Computer Laboratory (University of Cambridge) and with Pr Benveniste's research team DistribCom at IRISA/INRIA in Rennes, France. Pr Winskel has obtained an EPSRC grant Domain theory for concurrency-new categorical foundations , which includes a probabilistic treatment of concurrency models. My own research intends to be a complement of Pr Winskel's team research, by bringing analytical elements that match their study from the categorical and computer scientist viewpoints. On the other hand, Pr Benveniste's research team at IRISA has an experience in the application of concurrency models to telecommunication networks. I have been working at DistribCom during my PhD. Pr Winskel was a member of my PhD committee, and I have visited him at Cambridge in 2004. I can be an active interface between both teams. The industrial partner (Alcatel) of DistribCom represents a source of implementation opportunities.