The Impact of Time on Distributed Computing

时间对分布式计算的影响

基本信息

批准号：
9010730
负责人：
Jennifer Welch
金额：
$ 6万
依托单位：
University of North Carolina at Chapel Hill
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
1990
资助国家：
美国
起止时间：
1990-06-15 至 1992-11-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=9010730&HistoricalAwards=false
关键词：
Impact Time 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.

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