Combinatorial Algorithms for Parallel and Distributed Computing

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

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.