STUDIES ON IMPLEMENTATION AND APPLICATION OF SELF-STABILIZING SHARED OBJECTS IN DISTRIBUTED SYSTEMS

分布式系统中自稳定共享对象的实现与应用研究

• 批准号: 12680349
• 负责人: MASUZAWA Toshimitsu
• 金额: $ 2.24万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12680349/
• 关键词: DISTRIBUTED SYSTEM; DISTRIBUTED ALGORITHM; SHARED OBJECT; FAULT TOLERANCE; SELF-STABILIZATION; GROUP COMMUNICATION; SEARCH TREE; EFFICIENCY ANALYSIS; ヒープ; データ構造

We focused on the design method of distributed systems based on shared objects and considered self-stabilizing shared objects that provide high availability arid fault-tolerance. The self-stabilization guarantees that the shared objects can automatically recover from faults.The main results obtained in this research is as follows:We formalized self-stabilizing; objects and presented sequential implementations of the self-stabilizing objects such as search trees and heaps.We proposed a distributed implementation of the self-stabilizing search trees.We proposed efficient and fault-tolerant group communication such as broadcast. The group communication plays an important role in distributed implementations of shared, objects.We proposed a hew method for analyzing efficiency of asynchronous distributed systems. The method is based on the reduction of asynchronous behavior to the synchronous behavior of the systems.

重点讨论了基于共享对象的分布式系统的设计方法，并考虑了具有高可用性和容错性的自稳定共享对象。自稳定保证了共享对象能够自动地从故障中恢复，本文的主要研究成果如下：形式化了自稳定对象，给出了自稳定对象的顺序实现，如搜索树和堆;提出了自稳定搜索树的分布式实现;提出了高效的容错组通信，如广播。组通信在共享对象的分布式实现中起着重要的作用，本文提出了一种分析异步分布式系统效率的新方法。该方法是基于减少异步行为的同步行为的系统。

项目成果

Ted Herman: "Available stabilizing heaps"Information Processing Letters. 77, 2-4. 115-121 (2001)

Ted Herman：“可用的稳定堆”信息处理快报。

Satoshige Ukena: "A self-stabilizing spanning tree protocol that tolerates non-quiescant permanent faults"Transactions of IEICE. Vol. J85-D-1. No. 11. 1007-1014 (2002)

Satoshige Ukena：“一种能够容忍非静止永久故障的自稳定生成树协议”IEICE 的交易。

Daisuke Kondou: "A self-stabilizing Protocol for pipelined PIF in tree networks"The 22nd International Conference on Distributed Computing Systems. (採録決定).

Daisuke Kondou：“树网络中管道 PIF 的自稳定协议”第 22 届分布式计算系统国际会议（已接受）。

浮穴 学慈: "非停止永久故障に耐性を有する自己安定生成木構成プロトコル"電子情報通信学会論文誌(DI). J85-D-I, 11. (2002)

Gakuji Ukie：“具有抵抗不间断永久故障的自稳定生成树构造协议”，电子、信息和通信工程师学会汇刊 (DI)，11。 (2002)。

大下 福仁: "異種並列計算環境におけるブロードキャストスケジューリング"電子情報通信学会論文誌(DI). J86-D-I, 2. 88-98 (2003)

Fukuhito Oshita：“异构并行计算环境中的广播调度”，电子、信息和通信工程师学会汇刊 (DI)，2. 88-98 (2003)。