Probabilistic System Analysis

Members of the TDS group have carried out several projects involving the analysis of specific probabilistic systems. This work has been based on our probabilistic modelling work. Results include errors found in existing systems, correctness proofs for systems, and the discovery of new proof techniques. Some of these projects include:

Work by Pogosyants and Segala on analyzing the Aspnes-Herlihy randomized consensus algorithm.

The discovery of errors in a well-known probabilistic mutual exclusion algorithm PODC94, Saias thesis.

A new correctness proof, including a probabilistic time bound, for the Lehmann-Rabin randomized Dining Philosophers algorithm PODC94, Saias thesis, PODC95, Segala thesis.

The design and analysis of a new and efficient probabilistic distributed spanning tree protocol.

Analysis of Ben-Or's probabilistic asynchronous consensus protocol in Segala's PhD thesis.

The design and analysis of a probabilistic maximum independent set algorithm. STOC94

Analysis of a probabilistic fault diagnosis strategy in Saias' thesis.

TOC / LCS / MIT Last modified: Thu Nov 6 22:08:13 1997	Comments?