On Principles of Distributed Computing for Message-Passing, Shared-Memory, and Hybrid Systems

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

The long term objective of this research is to study fundamental problems in distributed computing, the area of computer science addressing the problems that arise when a set of communicating processes cooperate to carry out jointly a computational task. As in our previous work, our research will focus on the two central concerns of distributed computing: synchronization, which ensures that processes do not impede each other as they access shared resources, and fault-tolerance, which ensures that the system continues to work correctly even if some of its components fail. The proposed research will encompass message-passing systems, where processes communicate by exchanging messages, shared-memory systems, where processes communicate by accessing shared objects, and also hybrid systems where processes can both exchange messages and share memory. This research is primarily theoretical but it is motivated by practical problems and considerations. Some anticipated results are expected to have direct applications. As part of this research, we plan to investigate new liveness and fairness requirements for shared objects. Intuitively, liveness guarantees that (some or all) processes that access a shared object get a response from the object within a bounded time, and fairness ensures that the number of operations that each process is able to complete on a shared object is proportional to its relative speed. In particular, we will explore a new parametrized liveness property which ensures that, for every object operation type T, at least k processes accessing an object by applying operations of type T are guaranteed to make progress. The goal is to derive algorithms for implementing objects that satisfy this property and are also fair. We also plan to explore the use of highly synchronized external clocks (e.g., GPS clocks) to solve problems efficiently in systems that are otherwise partially asynchronous. Our starting point is an efficient algorithm that uses such clocks to maintain highly-consistent object replicas (such as data stores) in geographically distributed message-passing systems that are prone to failures. We will investigate how the clock-based techniques that we used in this algorithm can be applied to solve other problems efficiently. We also want to understand the limitation of such clock-equipped systems by deriving performance lower bounds. Motivated by technological advances, we also aim to solve problems and obtain performance lower bounds for hybrid systems where processes can both exchange messages and share memory. To do so we plan to extend our recent work where we solved some fundamental problems, including consensus, in such systems. These solutions are optimal in the sense that they tolerate the maximum number of process crashes possible. Our goal is to increase the fault-tolerance of our solutions by tolerating additional types of process failures, and also by tolerating failures of the shared objects they access.