Fault Tolerance and Information Security of Communications in Distributed Systems

我们主要研究了分布式系统中可靠和安全的消息广播、消息分发和消息传输。作为相关课题，我们还研究了共享存储型异步分布式系统的互斥问题，信息安全的一些技术，以及有限自动机公钥密码体制。我们使用独立生成树或广义独立生成树作为通信信道。也就是说，我们首先将原始消息转换为一条消息，然后通过每个独立生成树或每个广义独立生成树上的路径将每条消息发送到其目的地。我们已经设计了各种协议，这种类型的通信，并分析其效率，可靠性和安全性。一般来说，很难构造与网络连通性一样多的独立生成树。已经证明，任何kappa连通网络都具有以网络的任何节点为根的kappa独立生成树。对于任意kappa> 3的kappa连通网络，这个定理仍然成立.我们已经展示了构造某些网络族的独立生成树的有效方法。互斥是一个管理一次只能支持一个用户的单个不可分割资源的问题。我们已经提出了一些有效的无锁互斥算法的异步多写/读共享内存模型。这些算法是对以前公知的算法的改进。在本研究项目过程中获得的一些成果已在国际会议上发表，其中一些已经作为期刊论文发表或被接受在期刊上发表。

We have mainly studied reliable and secure message broadcasting, message distribution, and message transmission in distributed systems. As related topics we have also studied the mutual exclusion problem on asynchronous distributed systems of the shared memory type, some techniques on information secu- rity, and a finite automata public key cryptosystem. We use independent spanning trees or generalized independent spanning trees as communication channels. That is, we first transform the original message to a piece of messages, and then each piece is sent to its destination through a path on each independent spanning tree or each generalized independent spanning tree. We have designed various protocols for this types of communications and analyzed their efficiency, reliability and security. In general, it is hard to construct as many independent spanning trees as the connectivity of the network. It has been conjectured that any kappa-connected network has kappa independent spanning trees rooted at any node of the network. For arbitrary kappa -connected networks with kappa > 3, this conjectured is still open. We have shown efficient ways of constructing independent spanning trees of some families of networks.Mutual exclusion is a problem of managing to a single indivisible resource that can only support one user at a time. We have proposed a number of efficient lockout-free mutual exclusion algorithms for the asynchronous multi-writer/reader shared memory model. These algorithms are improvements upon the previously well known algorithms. Some results obtained during the process of this research project have been presented at international conferences, and some of them have been already published as journal papers or accepted for publication in journals.