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

重点研究了基于共享对象的分布式系统的设计方法，并考虑了具有高可用性和容错性的自稳定共享对象。本文的主要研究成果如下：形式化地描述了自稳定对象，给出了搜索树、堆等自稳定对象的顺序实现；提出了自稳定搜索树的分布式实现；提出了广播等高效容错的群组通信机制。群组通信在共享对象的分布式实现中起着重要的作用，提出了一种新的分析异步分布式系统效率的方法。该方法基于将系统的异步行为简化为同步行为。

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.