distributed algorithms tend to be difficult to understand and even more difficult to prove correct. Using distributed deadlock detection as a running example, this paper presents a framework for stating, understanding...
详细信息
ISBN:
(纸本)0897910974
distributed algorithms tend to be difficult to understand and even more difficult to prove correct. Using distributed deadlock detection as a running example, this paper presents a framework for stating, understanding, and proving the correctness of, distributed algorithms for decision problems. The framework consists of a series of complexity levels. To simplify the initial levels, we treat the data structure of the algorithm as a database, and use the database notions of views and transaction atomicity. For each complexity level, we state theorems that need to be proved for each algorithm. The framework is illustrated using several existing deadlock detection algorithms. Finally, it is shown that the framework suggests new algorithms using the best features of several existing algorithms.
The extendible hash file is a dynamic data structure that is an alternative to B-trees for use as a database index. While there have been many algorithms proposed to allow concurrent access to B-trees, similar solutio...
详细信息
ISBN:
(纸本)0897910974
The extendible hash file is a dynamic data structure that is an alternative to B-trees for use as a database index. While there have been many algorithms proposed to allow concurrent access to B-trees, similar solutions for extendible hash files have not appeared. This paper presents solutions to allow for concurrency that are based on locking protocols and minor modifications in the data structure. Another question that deserves consideration is whether these indexing structures can be adapted for use in a distributed database. Among the motivations for distributing data are increased availability and ease of growth;however, unless data structures in the access path are designed to support those goals, they may not be realized. Some first attempts at adapting extendible hash files for distributed data are described.
The original motivation for this paper came from an attempt to find a model for office systems which could be used to provide the basis for either an implementation or simulation. It was realized that the office is ju...
详细信息
The BETA programming language is developed as part of the BETAproject. The purpose of this project is to develop concepts,constructs and tools in the field of programming and programminglanguages. BETA has been develo...
详细信息
ISBN:
(纸本)0897910907
The BETA programming language is developed as part of the BETAproject. The purpose of this project is to develop concepts,constructs and tools in the field of programming and programminglanguages. BETA has been developed from 1975 on and the variousstages of the language are documented in [BETA a].The application area of BETA is programming of embedded as wellas distributedcomputing systems. For this reason a major goal hasbeen to develop constructs that may be efficiently *** the BETA language is intended to have a few number ofbasic but general constructs. It is then necessary that theabstraction mechanisms are powerful in order to define morespecialized *** is an object oriented language like SIMULA 67([SIMULA]) and SMALLTALK ([SMALLTALK]). By this is meant that aconstruct like the SIMULA class/subclass mechanism is fundamentalin BETA. In contrast to SMALLTALK, BETA is a language in the ALGOL60 ([ALGOL]) *** 67 is a system description and a programming *** DELTA language ([DELTA]) is a system description language only,allowing description of full concurrency, continuous change andcomponent interaction, developed from a SIMULA conceptual *** started from the system concepts of DELTA, but is aprogramming language, drawing upon a large number of contributionsto programming research in the 1970s. A basic idea in BETA is tobuild the language upon one, general abstraction mechanism --- thepattern ([BETA a 77]) --- covering both data, procedural andcontrol abstractions, substituting constructs like class,procedure, function and *** objects, procedure activation records andvariables are all regarded as special cases of the basic buildingblock of program executions: the entity. A pattern thusdescribes a category of entities with identical *** entity consists of a set of attributes and anaction-part. An attribute may be a data-item or apattern. The action-part is a sequence of imperativ
In the computing science community there is a growing belief that the traditional von Neumann programming model will be superceded in the 1990's by a new decentralised programming model. Various "revolutionar...
详细信息
We describe a reliability algorithm being considered for DDM, a distributed database system under development at Computer Corporation of America. The algorithm is designed to tolerate clean site failures in which site...
ISBN:
(纸本)9780897910972
We describe a reliability algorithm being considered for DDM, a distributed database system under development at Computer Corporation of America. The algorithm is designed to tolerate clean site failures in which sites simply stop running. The algorithm allows the system to reconfigure itself to run correctly as sites fail and recover. The algorithm solves the subproblems of atomic commit and replicated data handling in an integrated manner.
The extendible hash file is a dynamic data structure that is an alternative to B-trees for use as a database index. While there have been many algorithms proposed to allow concurrent access to B trees similar solution...
ISBN:
(纸本)9780897910972
The extendible hash file is a dynamic data structure that is an alternative to B-trees for use as a database index. While there have been many algorithms proposed to allow concurrent access to B trees similar solutions for extendible hash files have not appeared. In this paper, we present solutions to allow for concurrency that are based on locking protocols and minor modifications in the data *** question that deserves consideration is whether these indexing structures can be adapted for use in a distributed database. Among the motivations for distributing data are increased availability and ease of growth, however, unless data structures in the access path are designed to support those goals, they may not be realized. We describe some first attempts at adapting extendible hash files for distributed data.
distributed algorithms tend to be difficult to understand and even more difficult to prove correct. Using distributed dead-lock detection as a running example this paper presents a framework for stating, understanding...
ISBN:
(纸本)9780897910972
distributed algorithms tend to be difficult to understand and even more difficult to prove correct. Using distributed dead-lock detection as a running example this paper presents a framework for stating, understanding, and proving the correctness of distributed algorithms for decision problems. The framework consists of a series of complexity levels. To simplify the initial levels, we treat the data structure of the algorithm as a database, and use the database notions of views and transaction atomicity. For each complexity level, we state theorems that need to be proved for each algorithm. The framework is illustrated using several existing deadlock detection algorithms. Finally, it is shown that the framework suggests new algorithms using the best features of several existing algorithms.
Grapevine is a distributed, replicated system that provides message delivery, naming, authentication, resource location, and access control services in an internet of computers. The system, described in a previous pap...
ISBN:
(纸本)9780897911153
Grapevine is a distributed, replicated system that provides message delivery, naming, authentication, resource location, and access control services in an internet of computers. The system, described in a previous paper [1], was designed and implemented several years ago. We now have had operational experience with the system under substantial load. This experience has proved the original design sound in most aspects, but there also have been some surprises. In this paper we report what we have learned from using Grapevine. Our experience may offer some help to designers of new *** is implemented as a program that is run on a set of dedicated server computers. Client programs o f Grapevine run on various workstation and server computers attached to an internet. The services provided by Grapevine are divided into the message service and the registration *** message service accepts messages prepared by clients for delivery to individual recipients and distribution lists. Messages are buffered in inboxes on message servers until the recipient requests them. Any message server can accept any message for delivery, thus providing a replicated submission service. A computer system mall user has inboxes on at least two message servers, thus replicating the delivery path for the user.
暂无评论