权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Study of Co-operative Problem Solving Methods in Distributed Network Environment

分布式网络环境下协同问题解决方法研究

基本信息

批准号：
01580030
负责人：
HAGIHARA Kenichi
金额：
$ 1.22万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1989
资助国家：
日本
起止时间：
1989 至 1990
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-01580030/
关键词：
Distributed Algorithm Message Complexity Minimum Weight Spanning Tree Louder Election Problem Fail-Stop Global Sense of Direction Complete Network 分散協調問題解決リ-ダ選出問題重み最小生成木再構成問題リ-ダ-選出問題

项目摘要

(1) It is considered the Updating Minimum Spanning Tree Problem (UMP), that is, the problem to update the Minimum-weight Spanning Tree (MST) in response to topology change of network. The distributed algorithm is proposed which reconstructs the MST after several links are deleted and added. Its message complexity and its ideal-time complexity are 0 (m+n・log (t+f)) and 0 (n+n・log (t+f)) respectively, where n is the number of processors in the network, t (resp. f) is the number of added links (resp. the number of deleted links of the old MST), and m=t+n if f=0, m=e (i. e. the number of links in the network after topology change) otherwise. And the distributed algorithms is also proposed which deals with deletion and addition of processors as well as links.(2) The leader election problem (LEP) in asynchronous complete networks with undetectable fail-stop failures is considered. Especially, it is discussed whether presence of a global sense of direction affects the message complexity of LEP in faulty networks. For a complete network of n processors where k processors start the algorithm spontaneously and at most f (<n/2) processors are faulty, the message complexity of LEP is rheta (n+k.f) if the complete network has a global sense of direction. It is already known that LEP requires OMEGA (n. log k + k・f) message exchanges, if the complete network has no global sense of direction. Therefore, this result implies that the message complexity of LEP can be greatly reduced by using a global sense of direction in faulty networks as well as in reliable networks.

(1)最小生成树更新问题（UMP），即根据网络拓扑结构的变化更新最小权生成树的问题。提出了分布式算法，在删除和添加多个链接后重建MST。它的消息复杂度和理想时间复杂度分别为0（m+n·log（t+f））和0（n+n·log（t+f）），其中n是网络中处理器的个数，t（分别为n和t）是网络中处理器的个数。f）是添加的链路的数量（分别为旧MST的删除链接的数量），并且如果f=0，m=e（即，e.拓扑改变后网络中的链路数量）。提出了处理器和链路的删除和添加的分布式算法。(2)研究了异步完全网络中具有不可测失效-停止失效的领导者选举问题。特别是，它是讨论是否存在一个全局的方向感影响的消息复杂性的LEP在故障网络。对于一个n个处理器的完全网络，其中k个处理器自发地启动算法，并且至多有f（<n/2）个处理器发生故障，如果完全网络具有全局方向感，则LEP的消息复杂度为rheta（n+k.f）。众所周知，LEP需要OMEGA（n。log k + k·f）消息交换，如果整个网络没有全局方向感。因此，这一结果意味着LEP的消息复杂度可以大大降低，通过使用一个全局的方向感在故障网络以及在可靠的网络。