The use of concurrent regions for the detection of global predicates in distributed systems.

摘要

The main contribution of this dissertation is the development of theory and techniques in the area of monitoring and debugging of asynchronous distributed systems. This dissertation introduces a new method that we call Concurrent Regions. A concurrent region in a distributed system consists of a set of local intervals, one per process. Within a region, an event or state from process pi is potentially concurrent with all events and states from other processes in the same region. The concurrent regions method maintains only Lamport's logical clock at the application processes. Consequently, algorithms which use our method have a constant network and application overhead---per external event---that is not dependent on the number of processes in the distributed system. This is an improvement over existing algorithms in the field of unstable global predicates, which usually maintain a timestamping mechanism that characterizes causality (such as vector clocks) at the application processes. The overhead of such mechanisms at the application processes and at the network is dependent on the number of processes in the system. For systems with large number of processes, the network overhead can become an issue.;The CR method minimizes the application process overhead and the network overhead to the greatest possible extent, while at the same time providing a general framework to develop algorithms for unstable global predicates. Concurrent regions also relieve the need to specifically construct consistent global states as the concurrent regions already provide this. In addition, some classes of global predicates may benefit from the structure of a concurrent region.;We present the concurrent region method, describe its basis, show how it works, and present an algorithm to implement it. We use the concurrent region method to develop algorithms to detect three different classes of unstable global predicates. They are General Global Predicates, Relational Global Predicates, and Conjunctive Global Predicates. The algorithms detect for the possibility that the global predicate may have occurred in the distributed computation. Each of the algorithms is described, proven correct, and analyzed for complexity.