Accession Number : ADA182177

Title :   Hierarchical Correctness Proofs for Distributed Algorithms.

Descriptive Note : Master's thesis,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Lynch,Nancy A ; Tuttle,Mark S

PDF Url : ADA182177

Report Date : 03 Apr 1987

Pagination or Media Count : 90

Abstract : This thesis introduces a new model for distributed computation in asynchronous networks, the input-output automaton. This simple, powerful model captures in a novel way the game-theoretic interaction between a system and its environment, and allows fundamental properties of distributed computation such as fair computation to be naturally expressed. Futhermore, this model can be used to construct modular, hierarchical correctness proofs of distributed algorithms. This thesis defines the input-output automaton model, and presents an interesting example of how this model can be used to construct such proofs.

Descriptors :   *ALGORITHMS, *INPUT OUTPUT MODELS, DISTRIBUTION, GAME THEORY, INTERACTIONS, COMPUTATIONS, MODELS, ASYNCHRONOUS COMPUTERS, THESES, DISTRIBUTED DATA PROCESSING

Subject Categories : Computer Systems
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE