The Impact of Time on Distributed Computing

该项目的目标是开发现实的，部分 分布式系统的同步模型，并确定 他们之间的关系。 多种部分同步模型 将通过研究真实的分布式协议来收集， 尽可能抽象地制定他们的时间要求。 应用领域包括分布式文件系统和通信 网络. 模型之间的关系将由 定义模型之间的模拟，并寻找问题， 区分它们。 时间约束将被添加到分布式 问题（以前研究没有他们）和由此产生的上部和 将分析时间复杂度的下限。 第一个问题 要分析的是实现原子寄存器的问题。 识别部分同步模型的重要性在于， 它们比两个极端的时间模型更真实 （同步和异步）经常使用。 了解 模型之间的关系很重要，因为它们表明 什么样的时间行为是必要的和充分的， 特别的财产持有。 系统构建者可以集中精力 提供适当的时间行为。 模型模拟可以 当结果从一个模型转移到另一个模型时， 另 研究真实的协议和特定问题可以导致 在特定问题域中有用的结果。

The objectives of this project are to develop realistic, partially synchronous models of distributed systems and to determine the relationships between them. A variety of partially synchronous models will be collected by studying real distributed protocols and formulating their timing requirements as abstractly as possible. Application areas include distributed file systems and communication networks. Relationships between the models will be determined by defining simulations between models and looking for problems that differentiate them. Timing constraints will be added to distributed problems (previously studied without them) and the resulting upper and lower bounds on time complexity will be analyzed. The first problem to be so analyzed is that of implementing atomic registers. The significance of identifying partially synchronous models is that they are more realistic than the two extreme timing models (synchronous and asynchronous) often used. Understanding the relationships between models is important because they indicate precisely what time behavior is necessary and sufficient for particular properties to hold. Systems builders can then concentrate on providing the appropriate time behavior. Model simulations can save work and unify results when results carry over from one model to another. Studying real protocols and specific problems can lead to results that are useful in the specific problem domains.