Computational Complexity for Extracting Global Information from Locally Distributed Information

并行和分布式计算是当今计算机科学的主旋律。在更高层次上，并行和分布式计算被认为是从局部分布的信息中提取全局信息的计算。这项研究的目的是澄清这种计算的计算复杂性。下面总结了我们所取得的主要成果。在分布式算法方面，(1)针对分布式计算中最基本的问题之一--终端检测问题，提出了一种消息-时间最优算法；(2)分析了和弦环中的和弦数目与消息复杂度之间的权衡。提出了一种高速局域网的网络模型，并在该模型上提出了算法。在并行算法方面，提出了(1)基于处理器阵列的并行算法和(2)并行随机存取机(PRAM)算法。我们开发了使分布式算法具有容错性的方法。我们在一个网络中展示了高效和容错的路由方案。

Nowadays parallel and distributed computation is a dominant theme of computer science. On a higher level, parallel and distributed computation is regarded as computation to extracting global information from locally distributed information. The aim of this research is to clarify the computational complexity of this kind of computation. The followings summarize the main results we obtained.1. Concerning distributed algorithms,(1) We proposed a message-time optimal algorithm for a termination detection problem, one of the most fundamental problems in distributed computing, and(2) We analyzed the tradeoff between the number of chords and the message complexity in chordal rings.2. We presented a network model of high-speed LANs and proposed algorithms on the model.3. Concerning parallel algorithms, we proposed(1) Algorithms on processor arrays with buses, and(2) PRAM (Parallel Random Access Machine) algorithms for problems in computational geometry.4. We developed methods to make distributed algorithms fault-tolerant.5. We showed efficient and fault-tolerant routing schemes in a network.