Interprocess Communication and Synchronization in Parallel and Distributed Systems

在并行和分布式系统中，进程间的通信和同步是至关重要的。它们共同影响并发程序的效率、设计和理解。这项研究旨在检查共享变量和消息传递系统中的进程间通信和同步机制。在共享变量系统的情况下，考虑了高速缓存一致性和非原子共享存储器的适当性问题。开发了用于处理非原子存储器的证明技术和编程方法。在消息传递系统的情况下，研究了计算的局部性问题。开发了衡量局部性的复杂性度量和针对常见同步问题的高效算法。研究了故障和动态网络对算法的影响以及各种性能指标的严格下界。最后，研究考察了同时支持共享内存和消息传递的混合编程范例。作为研究的一部分，设计了共享内存在底层消息传递体系结构上的高效模拟。

Communication and synchronization among processes is of fundamental importance in parallel and distributed systems. Together, they have an impact on the efficiency, the design, and the understanding of concurrent programs. This research aims at examining shared variable and message passing systems with respect to mechanisms for interprocess communication and synchronization. In the case of shared variable systems, the question of cache coherence and the appropriateness of non-atomic shared memory is considered. Proof techniques and programming methodologies are developed for dealing with non-atomic memories. In the case of message passing systems, the question of locality of computations is investigated. Complexity measures that measure locality and efficient algorithms for commonly occurring synchronization problems are developed. The impact of failures and dynamic networks on algorithms and tight lower bounds on various performance measures are explored. Finally, the research examines mixed programming paradigms that support both shared memory and message passing. As a part of this research, efficient simulations of shared memory on an underlying message passing architecture are designed.