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. ***