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

点击翻译按钮获取中文摘要

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