| In distributed computing, one of the most important problems is to detect some global state. The global state of distributed system is the union of the states of the processes. They do not share their own memory and they communicate with each other only through the exchange of messages. A process that wishes to construct a global state must infer the remote components of that state through message exchanges.;In this dissertation, two major problems are presented to resolve global state problems which detect particular states in distributed systems--quiescence (termination) detection and deadlock detection problems. We study existing algorithms from the perspective of total correctness and performance, and present new algorithms that are elegant and efficient.;First, new message-efficient solutions for quiescence detection problem for an extended model of generalized diffusing computations are presented. In the generalized model, processes are activated only upon the receipt of a message combination as dictated by their activation conditions, and this is in contrast to any message in the traditional model. Our solutions employ a rooted directed acyclic graph-based scheme and thus incur much less message overhead than the prevalent tree-based schemes.;Next, several different schemes of the edge-chasing algorithm in deadlock detection and resolution problem are introduced. They can eliminate redundant probes, stale probes and false deadlocks. The algorithms combined with those schemes have their own advantages and disadvantages. Our solutions employ an object-based antagonistic edge scheme. The number of probes initiated and their hops of the object-based antagonistic edge scheme are far fewer than those of the existing transaction-based antagonistic edge scheme. |
