Information theory for distributed and asynchronous network communication

分布式异步网络通信的信息论

• 批准号: EP/D066670/1
• 负责人: Samy Abbes
• 金额: $ 25.73万
• 依托单位: University of Cambridge
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2006
• 资助国家: 英国
• 起止时间: 2006 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FD066670%2F1
• 关键词: Information; theory; distributed; asynchronous; network

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.

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