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.