Alain Isaac Saias, Randomness versus Non-Determinism in Distributed Computing Technical Report MIT/LCS/TR-651, Laboratory for Computer Science, Massachusetts Institute Technology. Also, PhD thesis, Department of Math, Massachusetts Institute of Technology, October 1994. (Tar File).

Abstract

In randomized distributed computing, executions encounter branch points resolved either randomly or non-deterministically. Random decisions and non-deterministic choices interact and affect each other in subtle ways. This thesis is devoted to the analysis and illustration of the effects of the interplay between randomness and non-determinism in randomized computing.

Using ideas from game theory, we provide a general model for randomized computing which formalizes the mutual effects of randomization and non-determinism. An advantage of this model over previous models is that it is particularly effective for expressing mathematical proofs of correctness in two difficult domains in randomized computing. The first domain is the analysis of randomized algorithms where non-deterministic choices are made based on a limited knowledge of the execution history. The second domain concerns the establishment of lower- bounds and proofs of optimality.

The advantage of this model are described in the context of three problems. First, we consider the classical randomized algorithm for mutual exclusion~[49] of Rabin. This algorithm illustrates perfectly the difficulties encountered when the non-deterministic choices are resolved based on a limited knowledge of execution history.

We then analyze the Lehmann-Rabin Dining Philosophers algorithm (1981). Our analysis provides a general method for deriving probabilistic time bounds for randomized executions.

In the last part, we analyze a scheduling problem and give solutions in both the deterministic and the randomized cases. Lower bounds arguments show these solutions to be optimal. For the randomized case, we take full advantage of the game theoretic interpretation of our general model. In particular, the proof of optimality reflects Von-Neumann's duality for matrix games.