Computational Complexity for Extracting Global Information from Locally Distributed Information

从局部分布信息中提取全局信息的计算复杂性

• 批准号: 01460150
• 负责人: TOKURA Nobuki
• 金额: $ 1.6万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (B)
• 财政年份: 1989
• 资助国家: 日本
• 起止时间: 1989 至 1990
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-01460150/
• 关键词: Distributed algorithm; Parallel algorithm; LAN; Bus network; Computational complexity; Fault tolerance; Routing; アルゴリズム・シミュレ-タ

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.

并行和分布式计算是当今计算机科学的一个重要主题。在更高的层次上，并行分布式计算被认为是从局部分布的信息中提取全局信息的计算。这项研究的目的是澄清这种计算的计算复杂性。主要结果如下：1.在分布式算法方面，（1）针对分布式计算中最基本的问题之一--终止检测问题，提出了一种消息时间最优的算法;（2）分析了弦环中弦数与消息复杂度之间的折衷关系.提出了一种高速局域网的网络模型，并在此模型上提出了相应的算法.在并行算法方面，我们提出了（1）带总线的处理器阵列上的并行算法和（2）计算几何问题的并行随机存取机（PRAM）算法.提出了使分布式算法具有容错性的方法。我们展示了网络中的高效和容错路由方案。

项目成果

齊藤 明紀: "完全生成木維持アルゴリズムとその複雑度" 電子情報通信学会論文誌(DI).

Akinori Saito：“完整的生成树维护算法及其复杂性”电子、信息和通信工程师协会 (DI) 汇刊。

Koichi Wada: "A new measure of faultーtolerance for interconnection network" Proc. of 1990 BILKENT International,Conf. on New Trends in Comm. Control and Signal Processing. 111-118 (1990)

Koichi Wada：“互连网络容错的新措施”，1990 年 BILKENT 国际会议，《控制和信号处理新趋势》(1990)。

和田 幸一: "kー辺連結グラフに対する耐故障性路線割当" 電子情報通信学会技術研究報告(コンピュテ-ション研究会).

Koichi Wada：“k 边连通图的容错路线分配”IEICE 技术研究报告（计算研究组）。

Wei Chen: "An optimal parallel algorithm for computing intersection of two convex polygons (in Japanese)" Trans. IEICE, J73-D-i. 11. 905-907 (1990)

陈伟：“一种计算两个凸多边形交集的最优并行算法（日语）” Trans.

Koichi Wada: "Distributed algorithms for connectivity problem of networks with faulty elements (in Japanese)" Trans. IEICE, J74-D-I. 2. 137-145 (1991)

Koichi Wada：“具有故障元件的网络连接问题的分布式算法（日语）”Trans。