Combinatorial Algorithms for Parallel and Distributed Computing

拟议的研究计划将调查在计算机系统的并行和分布式计算的通信问题。为了在静态和动态图形中实现快速有效的通信，将设计和分析组合算法。在静态网络中，将考虑不同的并行和分布式原语，如广播，多播，八卦。在动态图最快，最短和最重要的广播问题将进行研究。 通过对每个处理器可用的信息量、中继器和接收器的数量、消息的长度、传输或处理延迟、故障链路的数量、消息的数量等设置约束来考虑各种信息传播模型。这些原语，特别是广播和多播，在并行处理、数据迁移、高速缓存一致性和通信网络中的数据共享。广播时间是衡量网络整体性能的主要指标之一。这些原语不仅在大规模复杂网络、并行机中，而且在工作站网络中也很重要。 在最近建立的研究领域，称为时间图或时间网络，不同的基本通信问题被认为是基于图的动态性质。在网络中具有最小跳数的通信被称为最短广播（或简称为shortestcast）。消息到达时间最早的通信称为最早广播（简称forestcast），持续时间最短的通信称为最快广播（简称fastestcast）。所有这些和一些更基本的图论参数在不同的假设下的时间图将进行研究。

The proposed research program will investigate communication problems in computer systems for parallel and distributed computing. To achieve fast and efficient communication in static and dynamic graphs combinatorial algorithms will be designed and analyzed. In static networks different parallel and distributed primitives such as broadcasting, multicasting, gossiping will be considered. In dynamic graphs fastest, shortest and foremost broadcast problems will be investigated. Various information dissemination models are considered by placing constraints on the amount of information available for each processor, number of senders and receivers, length of the message, transmission or processing delay, the number of faulty links, the number of messages, etc. These primitives, especially broadcasting and multicasting, play an important role in parallel processes, in data migration, in cache coherence and in data sharing in communication networks. Broadcast time is one of the main measures of overall network performance. These primitives are also important not only in massively complex networks, parallel machines but also in networks of workstations. In a recently established research area, called temporal graphs or temporal networks, different basic communication problems are considered based on the dynamic nature of the graph. Communication with minimum number of hops in the network is called shortest broadcast (or shortly shortestcast). Communication with earliest arrival time of the message is called foremost broadcast (shortly foremostcast), and communication with smallest duration is called fastest broadcast (shortly fastestcast). All these and some even more fundamental graph theoretic parameters in temporal graphs under different assumptions will be investigated.