This conference proceedings contains 37 papers, with 7 papers in abstract form. These papers represent preliminary reports of continuing research on principles of database systems. The main subjects are database theor...
详细信息
ISBN:
(纸本)0897912233
This conference proceedings contains 37 papers, with 7 papers in abstract form. These papers represent preliminary reports of continuing research on principles of database systems. The main subjects are database theory, logic programming, logic database languages, logical design of relational database schemes, dynamic query interpretation in relational databases, categorical databases, transaction commitment at minimal communication cost, concurrency control algorithms, relative knowledge in distributed databases, database update and specification, evaluation of recursive queries, relational calculus, optimizing datalog programs, and axiomatization and simplification rules for relational transactions.
distributed programs must often display graceful degradation, reacting adaptively to changes in the environment. Under ideal circumstances, the program's behavior satisfies a set of application-dependent constrain...
详细信息
This paper describes a technique for implementing the sort of small databases that frequently occur in the design of operating systems and distributed systems. We take advantage of the existence of very large virtual ...
详细信息
This paper develops linear time distributed algorithms for a class of problems in an asynchronous communication network. The main problem considered is finding the minimum-weight spanning tree. Any algorithm for any o...
详细信息
ISBN:
(纸本)9780897912211
This paper develops linear time distributed algorithms for a class of problems in an asynchronous communication network. The main problem considered is finding the minimum-weight spanning tree. Any algorithm for any one of the problems above requires at least OMEGA (E plus V log V) communication and and OMEGA (V) time in the general network. In this paper, we present new algorithms, which achieve those lower bounds. Our results enables to improve algorithms for many other problems in distributedcomputing, achieving lower bounds on their communication and time complexities.
Andrew is a distributedcomputing environment being developed in a joint project by Carnegie Mellon University and IBM. One of the major components of Andrew is a distributed file system which constitutes underlying m...
ISBN:
(纸本)089791242X
Andrew is a distributedcomputing environment being developed in a joint project by Carnegie Mellon University and IBM. One of the major components of Andrew is a distributed file system which constitutes underlying mechanism for sharing information. The goals of the Andrew file system are to support growth up to at least 7000 workstations (one for each student, faculty member, and staff at Carnegie Mellon) while providing users, application programs, and system administrators with the amenities of a shared file system.A fundamental result of our concern with scale is the design decision to transfer whole files between servers and workstations rather than some smaller unit such as records or blocks, as almost all other distributed file systems do. This paper examines the consequences of this and other design decisions and features that bear on the scalability of *** scale affects a distributed system in two ways: it degrades performance and it complicates administration and day-to-day operation. This paper addresses both concerns and shows that the mechanisms we have incorporated cope with them successfully. We start the initial prototype of the system, what we learned from it, and how we changed the system to improve performance. We compare its performance with that of a block-oriented file system, Sun Microsystems' NFS, in order to evaluate the whole file transfer strategy. We then turn to operability, and finish with issues related peripherally to scale and with the ways the present design could be enchanced.
We prove that it is impossible to express asynchronous message passing within the framework of first-order temporal logic with both future and past operators (as studied by Kamp). This is an extension of a result of S...
详细信息
The Butler system is a set of programs running on Andrew workstations at CMU that give users access to idle workstations. Current Andrew users use the system over 300 times per day. This paper describes the implementa...
详细信息
We present a fully abstract semantics for real-time distributedcomputing of the Ada and OCCAM kind in a denotational style. This semantics turns termination, communication along channels, and the time communication t...
详细信息
ISBN:
(纸本)0897912152
We present a fully abstract semantics for real-time distributedcomputing of the Ada and OCCAM kind in a denotational style. This semantics turns termination, communication along channels, and the time communication takes place, into observables. Yet it is the coarsest semantics to do so which is syntax-directed (this is known as full abstraction). It extends the linear history semantics for CSP of Francez, Lehman and Pnueli. Our execution model is based on maximizing concurrent activity as opposed to interleaving (in which only one action occurs at the time and arbitrary delays are incurred between actions). It is a variant of the maximal parallelism model of Salwicki and Müldner.
This paper deals with the problem of computing covers for the functional dependencies embedded in a subset of a given relation schema. We show how this problem can be simplified and present a new and efficient algorit...
详细信息
ISBN:
(纸本)0897912233
This paper deals with the problem of computing covers for the functional dependencies embedded in a subset of a given relation schema. We show how this problem can be simplified and present a new and efficient algorithm 'Reduction By Resolution' (RBR) for its solution. Though the problem of computing covers for embedded dependencies is inherently exponential, our algorithm behaves polynomially for several classes of inputs. RBR can be used for the solution of some related problems in the theory of database design, such as deciding whether a given database scheme is in Boyce-Codd Normal Form or decomposing a scheme into Boyce-Codd Normal Form.
We describe applications of a virtually synchronous environment for distributed programming, which underlies a collection of distributed programming tools in the ISIS2 system. A virtually synchronous environment allow...
详细信息
ISBN:
(纸本)089791242X
We describe applications of a virtually synchronous environment for distributed programming, which underlies a collection of distributed programming tools in the ISIS2 system. A virtually synchronous environment allows processes to be structured into process groups, and makes events like broadcasts to the group as an entity, group membership changes, and even migration of an activity from one place to another appear to occur instantaneously - in other words, synchronously. A major advantage to this approach is that many aspects of a distributed application can be treated independently without compromising correctness. Moreover, user code that is designed as if the system were synchronous can often be executed concurrently. We argue that this approach to building distributed and fault-tolerant software is more straightforward, more flexible, and more likely to yield correct solutions than alternative approaches.
暂无评论