Information theory for distributed and asynchronous network communication

我们目前正处于一场分布式革命之中。分布式的通信、处理和计算方式正在取代传统的集中式架构。分布式通信系统的典型例子是电信网络，包括无线网络。然而，这场技术革命并不总是伴随着所有可以预期的理论进步。这就是信息论的例子。尽管信息理论在分布式通信系统理论中应该发挥核心作用，但它在多用户网络理论中并没有像在单用户情况下那样取得重要的成果。我建议通过使用基于偏序的动态网络模型来重新考虑多用户信息理论。这些模型的主要特性是提供事件可以并行发生的动态。最近，来自法国Rennes IRISA的DistribCom研究小组在巴黎附近的Alcatel平台上实施了电信网络故障诊断算法，在实际环境中显示了这些模型的效率。并发模型最初是为其通信特性而设计的。因此，并发理论和信息理论之间有一个自然的相互作用的地方。信息论以概率论为基础；因此，这些交互必须基于并发模型的概率扩展。这种概率扩展一直是最近才涉及的一个研究领域的主题。我通过我的博士论文和随后的出版物参与了这个新的研究领域。因此，我在概率并发系统方面的专业知识使我成为探索并发理论和信息论之间桥梁的自然人选。从数学的角度来看，这个新框架构成了动力系统和随机过程理论的非平凡扩展。并发模型的主要特点是在系统的规模上没有全局时钟。相反，时间是部分有序的。实际上，系统本质上是分布式的，只能在不同的节点上定义本地时钟。它们的同步产生的时间不是完全有序的，而是部分有序的。从数学的角度来看，主要问题是缺乏自然移位算子，这是经典动力系统理论的基础。因此，该项目的目标是开发基于并发模型的分布式和异步通信的理论基础。这相当于定义并发源和通道的概念，以及相关的熵（用于源）和容量（用于通道）的概念，然后推导熵和编码定理，最后设计和实现编码和/或压缩网络算法。这项工作将与剑桥大学计算机实验室的Winskel博士的研究小组以及法国Rennes的IRISA/INRIA的Benveniste博士的研究小组DistribCom合作完成。Winskel博士获得了EPSRC授予的并发领域理论——新分类基础，其中包括并发模型的概率处理。我自己的研究打算通过从分类和计算机科学家的角度引入与他们的研究相匹配的分析元素，成为Winskel博士团队研究的补充。另一方面，Benveniste博士在IRISA的研究团队在将并发模型应用于电信网络方面有着丰富的经验。我博士期间一直在DistribCom工作。温斯克尔教授是我的博士委员会成员之一，2004年我曾在剑桥拜访过他。我可以成为两个团队之间的活跃接口。DistribCom的工业合作伙伴（阿尔卡特）代表了实现机会的来源。

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.