the authors present a general methodology for bounding the range of sequence numbers utilized in a distributed program to order events. this methodology requires explicit knowledge of bounds on the rate at which proce...
详细信息
the authors present a general methodology for bounding the range of sequence numbers utilized in a distributed program to order events. this methodology requires explicit knowledge of bounds on the rate at which processes may increment sequence numbers and the time required to transmit a message. It may also require the inclusion of additional synchronization in a distributed application which utilizes the bounded sequence numbers. the methodology is demonstrated in three contexts. It is shown how a scheme for bounding sequence numbers on requests for network mutual exclusion is consistent withthe methodology. Sequence numbers are bound in a network mutual exclusion protocol. the methodology is utilized to bound the size of sequence numbers used in successive fault-tolerant broadcasts among a group of fail-stop processors. In all three cases, with totally different message-passing patterns and means of incrementing sequence numbers, consistent application of the methodology is stressed.
the demands on a heterogeneous distributed file system are outlined, and the design and implementation of a prototype to meet these demands are described. this prototype, the Heterogeneous Computer Systems file system...
详细信息
the demands on a heterogeneous distributed file system are outlined, and the design and implementation of a prototype to meet these demands are described. this prototype, the Heterogeneous Computer Systems file system (HFS), provides a network-wide file system supporting a simple record-oriented file model. through this standard file model, the HFS provides global access to files stored locally in many different file types. the HFS is implemented as a set of HFS servers, one running on each participating host. Each HFS server extends its host's local file system by fielding remote requests for files stored locally, translating those requests into the appropriate local file system calls, and returning any information so obtained. this prototype HFS implementation is used on a network composed of VAX systems running Unix, Sun systems running 4.2BSD Unix, and Xerox Dandelions running XDE.
the use of weakly consistent memories in distributed shared memory systems to combat unacceptable network delay and to allow such systems to scale is proposed. Proposed memory correctness conditions are surveyed, and ...
详细信息
the use of weakly consistent memories in distributed shared memory systems to combat unacceptable network delay and to allow such systems to scale is proposed. Proposed memory correctness conditions are surveyed, and how they are related by a weakness hierarchy is demonstrated. Multiversion and messaging interpretations of memory are introduced as means of systematically exploring the space of possible memories. Slow memory is presented as a memory that allows the effects of writes to propagate slowly through the system, eliminating the need for costly consistency maintenance protocols that limit concurrency. Slow memory processes a valuable locality property and supports a reduction from traditional atomic memory. thus slow memory is as expressive as atomic memory. this expressiveness is demonstrated by two exclusion algorithms and a solution to M. J. Fischer and A. Michael's (1982) dictionary problem on slow memory.
A formalism for comparing the average execution time of distributed protocols is provided. the comparisons are made independently of the properties of the network on which the protocols are executed. the formalism tak...
详细信息
A formalism for comparing the average execution time of distributed protocols is provided. the comparisons are made independently of the properties of the network on which the protocols are executed. the formalism takes into account computation time, the time to transfer information, the time spent by a site waiting to synchronize with other sites, and the overlap among them. A framework in which the information transfer and synchronization requirements of a protocol are separately and explicitly specified is developed. A knowledge formalism is used to specify the protocol's specification requirements. Transformations on protocols which may change the synchronization structure, the information transferred, or the amount of local computation are defined. It is shown that, if a sequence of such transformations can be applied to a protocol to obtain another protocol, the final protocol runs at least as fast as the initial. Two notions of comparison, containment and reducibility, are given, and their properties are explored. Several protocols, including those for atomic commitment and snapshot recording, are analyzed to illustrate the technique.
the authors propose three different two-phase commit (2PC) protocols that ensure that, even in the presence of permanent node failures, all sane nodes participating in a particular transaction eventually terminate the...
详细信息
the authors propose three different two-phase commit (2PC) protocols that ensure that, even in the presence of permanent node failures, all sane nodes participating in a particular transaction eventually terminate the transaction in a consistent way. A node is defined to be sane if it eventually recovers from failures. these protocols, called open 2PC protocols, are based on a tree-of-processes model and provide means for transferring the coordinator function within process trees. Besides describing the open 2PC protocols in detail, the authors compare these protocols with regard to their message and time complexity. they also include a discussion of related work.< >
the authors introduce two techniques for allocating and managing buffers in support of distributed system operation and evaluate the resulting system behavior. For this evaluation a methodology that permits the develo...
详细信息
the authors introduce two techniques for allocating and managing buffers in support of distributed system operation and evaluate the resulting system behavior. For this evaluation a methodology that permits the development of an analytic model is introduced. Withthe help of this model, it becomes possible to fine-tune the buffer allocation policies in realistic system configurations.< >
A fairness property, called U-fairness, is studied in the context of the design of distributed systems with multiparty interactions. this is done with an overlapping model of concurrency. A distributed algorithm imple...
详细信息
A fairness property, called U-fairness, is studied in the context of the design of distributed systems with multiparty interactions. this is done with an overlapping model of concurrency. A distributed algorithm implementing the fairness notion is presented. U-fairness is shown to be more appropriate to the design of distributed systems than other known fairness notions because it provides an abstraction for stable property detection whereas the other fairness notions do not.< >
Incomplete hypercubes are analyzed. the elementary properties of complete hypercubes and a routing algorithm for incomplete hypercubes are briefly reviewed. Structural properties, including diameter, mean message trav...
详细信息
Incomplete hypercubes are analyzed. the elementary properties of complete hypercubes and a routing algorithm for incomplete hypercubes are briefly reviewed. Structural properties, including diameter, mean message traversal, and traffic density, of incomplete hypercube computers with size 2/sup n/+2/sup k/, 0 >
Two location policies that, by adapting to the system load, capture the advantages of receiver-initiated, sender-initiated, and symmetrically initiated algorithms are presented. A key feature of these location policie...
详细信息
Two location policies that, by adapting to the system load, capture the advantages of receiver-initiated, sender-initiated, and symmetrically initiated algorithms are presented. A key feature of these location policies is that they are general and can be used in conjunction with a broad range of existing transfer policies. By means of simulation, two representative algorithms making use of these adaptive location policies are shown to be stable and to improve performance significantly relative to nonadaptive policies.< >
A case study of the design and performance of remote rendezvous, an interprocessor communication mechanism, is presented. Remote rendezvous extends the Ada rendezvous model to handle distributed communication. In many...
详细信息
A case study of the design and performance of remote rendezvous, an interprocessor communication mechanism, is presented. Remote rendezvous extends the Ada rendezvous model to handle distributed communication. In many ways its semantics and implementations are similar to remote procedure call and send-receive-reply. the design is compared withthat of similar systems. the major contribution of this work is a description of real design choices that trade space for reliability, real-time response, and ease of application evolution.< >
暂无评论