Fault Tolerance and Information Security of Communications in Distributed Systems

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

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.