Fault Tolerance and Information Security of Communications in Distributed Systems

分布式系统通信的容错与信息安全

基本信息

批准号：
09680325
负责人：
IGARASHI Yoshihide
金额：
$ 1.79万
依托单位：
Gunma University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1997
资助国家：
日本
起止时间：
1997 至 1998
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-09680325/
关键词：
broadcasting distributed systems fault tolerance independent spanning trees information security message distributing mutual exclusion secret sharing メッセージ分配

项目摘要

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.

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