Partially Synchronous Shared-Memory Systems and the Study of Real-Time Algorithms

9301454 Neiger分布式系统的模型分为两大类：使用消息传递的系统和使用共享内存的系统。早期对消息传递系统的研究集中在两种系统模型上：完全异步（其中没有关于系统的定时信息）和完全同步（其中有完美的定时信息）。最近的研究还考虑了部分同步系统（其中不完美的定时信息是可用的），这些中间系统更准确地捕捉许多真实的系统的属性。 相反，对共享内存系统的研究几乎只限于完全异步系统（完全同步系统是不现实的）。 虽然这种限制允许开发非常通用的算法，但它排除了对许多真实的系统正确的更有效的算法的考虑。在许多情况下，部分同步模型对于共享内存系统更现实，就像它对于消息传递系统一样。 这样一个模型承认一个更广泛的类的算法，这些算法可以分析其实时性能。 本计画的目标是提供一个全面的研究部分同步共享记忆体系统，并开发和分析这些系统的广泛的算法。 该项目正在为部分同步共享内存系统开发正式模型，考虑到定时行为和故障;探索这些系统中算法设计和分析的几种范例，包括实时分析;研究分布式计算中的各种具体问题。（如共识和原子快照）以及在这些系统中解决它们的算法的开发;处理器知识的应用;以及具有不同类型错误行为的模型之间的翻译的使用。 ***

9301454 Neiger Models of distributed systems fall into two main classes: systems using message passing and those using shared memory. Early research on message-passing systems focused on two system models: completely asynchronous (in which there is not timing information available about the system) and completely synchronous (in which perfect timing information is available). More recent research has also considered partially synchronous systems (in which imperfect timing information is available), and these intermediate systems more accurately capture the properties of many real systems. In contrast, research on shared-memory systems has been restricted almost exclusively to completely asynchronous systems (completely synchronous systems are not realistic). While such a restriction permits the development of very general algorithms, it excludes consideration of more efficient algorithms that would be correct for many real systems. In many cases, a partially synchronous model is more realistic for shared-memory systems, just as it is for message-passing systems. Such a model admits a much wider class of algorithms, and these algorithms can be analyzed with respect to their realtime performance. The objective of this project is to provide a comprehensive study of partially synchronous shared-memory systems and to develop and analyze a wide range of algorithms for these systems. The project is developing formal models for partially synchronous shared-memory systems, taking into account timing behavior and failures; an exploration of several paradigms for algorithm design and analysis in these system, including real-time analyses; the study of a variety of specific problems in distributed computing (such as consensus and atomic snapshot) and the development of algorithms to solve them in these systems; the application of processor knowledge; and the use of translations between models with different types of faulty behavior. ***