Multivalued Possibilities Mappings

Abstract

Abstraction mappings are one of the major tools used to construct correctness proofs for concurrent algorithms. Several examples are given of situations in which it is useful to allow the abstraction mappings to be multivalued. The examples involve algorithm optimization, algorithm distribution, and proofs of time bounds. Abstraction mappings are one of the major tools that the author and colleagues use to construct correctness proofs for concurrent (including distributed) algorithms. In this paper, she tries to make one major point about such mappings: that it is useful to allow them to be multivalued. That is, often when one maps a low-level algorithm L to a high- level algorithm H, one would like to allow several states of H to correspond to a single state of L. I believe that any useful framework for describing abstraction mappings should include the ability to describe multivalued mappings.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1990
Accession Number
ADA226110

Entities

People

  • Nancy Lynch

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Buildings And Structures
  • Classification
  • Computer Science
  • Computers
  • Construction
  • Contracts
  • Data Management
  • Inequalities
  • Intervals
  • Machines
  • Message Systems
  • Numbers
  • Optimization
  • Security
  • Sequences

Fields of Study

  • Computer science
  • Engineering

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Geodesy
  • Theoretical Analysis.