Accession Number : ADA288587

Title :   Specifying Weak Sets.

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s) : Wing, Jeannette M. ; Steere, David C.

PDF Url : ADA288587

Report Date : SEP 1994

Pagination or Media Count : 21

Abstract : We present formal specifications of a new abstraction, weak sets, which can be used to alleviate high latencies when retrieving data from a wide-area information system like the World Wide Web. In the presence of failures, concurrency, and distribution, clients performing queries may observe behavior that is inconsistent with the stringent semantic requirements of mathematical sets. For example, an element retrieved and returned to the client mav be subsequently deleted before the query terminates. We chose to specify formally the behavior of weak sets because we wanted to understand the varying degrees of inconsistency clients might be willing to tolerate and to understand the tradeoff between providing strong consistency guarantees and implementing weak sets efficiently. Our specification assertion language uses a novel construct that lets us model reachability explicitly; with it, we can distinguish between the existence of an object and its accessibility. The specifications were instrumental in understanding the design space, and we are currently implementing The most permissive of the specifications in several types of Unix systems.

Descriptors :   *COMPUTER PROGRAMMING, *COMPUTER FILES, *SET THEORY, REQUIREMENTS, GLOBAL, INFORMATION SYSTEMS, SEMANTICS, CONSISTENCY, GUARANTEES, ACCESS, MATHEMATICS, TRADE OFF ANALYSIS, INTERROGATION, AREA COVERAGE, LOW STRENGTH.

Subject Categories : Theoretical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE