Search

An experimental software tool for simulating the behavior of distributed algorithms is proposed. The primary motivation for developing the tool is to study distributed database algorithms. Also, a classification of techniques presently used for distributed database problems of concurrency control and recovery is presented. This classification will be used to reduce the experimentation necessary to compare the performance of alternative algorithms. The study and development of distributed algorithms in general and distributed database algorithms in particular is behavior of distributed systems. Both intuition and present-day analytical tools are inadequate to characterize their behavior. Another barrier to understanding such algorithms is the complexity of their interaction, due to the potential lack of synchronization between nodes of a distributed system. Finally, it is not yet clear what 'good' behaviors are reasonable to expect from a distributed system. As a result, a multitude of algorithms may exist for solving a single problem, but without more experience and analysis, their behavior cannot be well understood or compared. This report describes an approach to providing the experience necessary for understanding the behavior of these algorithms. (Author)

A global state of a distributed transaction system is consistent if no transactions are in progress. A global checkpoint is a transaction which must view a globally consistent system state for correct operation. We present an algorithm for adding global checkpoint transactions to an arbitrary distributed transaction system. The algorithm is non-intrusive in the sense that checkpoint transactions do not interfere with ordinary transactions in progress; however, the checkpoint transactions still produce meaningful results. (Author), Prepared in cooperation with Washington Univ., Seattle. Dept. of Computer Science, Contract N00014-80-C-0221. Sponsored in part by Grants NSF-MCS77-02474, NSF-MCS77-15628, and NSF-MCS80-03337.

A global state of a distributed transaction system is consistent if no transactions are in progress. A global checkpoint is a transaction which must view a globally consistent system state for correct operation. We present an algorithm for adding global checkpoint transactions to an arbitrary distributed transaction system. The algorithm is non-intrusive in the sense that check-point transactions do not interfere with ordinary transactions in progress; however, the checkpoint transactions still produce meaningful results. (Author), Prepared in cooperation with Georgia Inst. of Tech., Atlanta, Contracts DAAG29-79-C-0155 and N00014-79-C-0873, Sponsored n part by Grants NSF-MCS77-02474, NSF-MCS77-15628 and NSF-MCS80-03337.

The problem is considered of locating a number of identical resources at nodes of a tree so as to minimize the total expected cost of servicing a set of random requests for the resources. The cost of servicing a request is the tree distance from the requesting node to the node at which the resource satisfying the request is located. An algorithm for finding an optimal placement of resources is presented., Prepared in cooperation with Georgia Inst. of Tech., Atlanta. Contracts N00014-79-C-0873 and DAAG29-79-C-0155.

Consider the problem of locating t resources on the nodes of a complete binary tree of n leaves so as to minimize the expected total distance from each of t simultaneous random requests at the leaves to the resource with which each is optimally matched. The optimal placement of resources yields an expected total distance of at most ct + 2 log(n/t). Such a placement can be found in time 0(log n). (Author), Prepared in cooperation with Georgia Inst. of Tech., Atlanta, Contract DAAG29-79-C-0155.