An efficient protocol for leader election in an asynchronous complete network is presented. the time complexity of the protocol is better than the currently known protocols for this problem. A message optimal protocol...
详细信息
ISBN:
(纸本)0818621443
An efficient protocol for leader election in an asynchronous complete network is presented. the time complexity of the protocol is better than the currently known protocols for this problem. A message optimal protocol is presented that requires O(N/log N) time, where N is the number of nodes in the network. Also given is family of protocols with message and time complexities O(Nk) and O(N/k) respectively, where log N ≤ k ≤ N. Many problems such as spanning tree construction, computing a global function, etc., are equivalent to leader election in terms of their message and time complexities, and therefore the author's results also improve the time complexity of these problems.
A probabilistic comparison algorithm is presented which requires O(f log n) bits to be transmitted to identify the corrupt pages in a file (where n is the number of pages and f is the maximum number of pages that coul...
详细信息
ISBN:
(纸本)0818621443
A probabilistic comparison algorithm is presented which requires O(f log n) bits to be transmitted to identify the corrupt pages in a file (where n is the number of pages and f is the maximum number of pages that could be corrupted), which improves on previous results on the growth of communicated bits as functions of both n and of f. If both copies compared are corrupt, only twice the number of bits is required as for the previous case. Further, if multiple copies are used for comparison, then the product of the number of copies times the number of bits sent from each of these copies to the comparison site grows as O(f log n). A lower bound which establishes the optimality of the algorithm to within a constant factor is provided.
Replication has been primarily used as a means of increasing availability in distributed systems. It is known that replication can mitigate the costs of accessing remotely stored data in distributed systems. Replicati...
详细信息
ISBN:
(纸本)0818621443
Replication has been primarily used as a means of increasing availability in distributed systems. It is known that replication can mitigate the costs of accessing remotely stored data in distributed systems. Replication control protocols in the literature have stopped short of addressing availability and performance concerns. these issues are addressed by contributing a classification of replicas with each class having different consistency requirements. Metareplicas keep track of up-to-date replicas for recently accessed objects and changes in data reference localities. thus they allow many transaction operations to synchronously execute at only a single (and often local) replica. Pseudoreplicas are non-permanent replicas that facilitate localized execution of transaction operations. True replicas are permanent replicas that increase the availability of operations and data. A replication control protocol is presented.
A syntax-oriented model for naming feature-based specification of services is provided. the model allows a service to evolve or reconfigure in functionality by adding and removing features and still coexist with its p...
详细信息
ISBN:
(纸本)0818621443
A syntax-oriented model for naming feature-based specification of services is provided. the model allows a service to evolve or reconfigure in functionality by adding and removing features and still coexist with its previous versions. the model's two aspects are examined. Withthis model for specifying services, name server functions may be factorized from service specific functions and implemented in a generic fashion in terms of parse and match operations and function invocations. this model can provide significant extension to such naming schemes as X.500 and the Universal Naming Protocol in supporting feature-based service interfaces.
this panel discussion covers the following: effective instrumentation as the key to effective monitoring;distributed monitoring systems as a basis for general purpose distributed multiprocessors;problems and prospects...
详细信息
ISBN:
(纸本)0818621443
this panel discussion covers the following: effective instrumentation as the key to effective monitoring;distributed monitoring systems as a basis for general purpose distributed multiprocessors;problems and prospects;performance monitoring, fact and fancy;and software aspects.
Primitives for broadcast communication that have been integrated withthe Amoeba distributed operating system are introduced. the semantics of the broadcast primitives are simple and easy to understand, but are still ...
详细信息
ISBN:
(纸本)0818621443
Primitives for broadcast communication that have been integrated withthe Amoeba distributed operating system are introduced. the semantics of the broadcast primitives are simple and easy to understand, but are still powerful. the proposed primitives, for example, guarantee global ordering of broadcast messages. the proposed primitives are also efficient: a reliable broadcast can be done in just slightly more than two messages, so the performance is comparable to a remote procedure call. In addition, the primitives are flexible;user applications can, for example, trade performance against fault-tolerance.
A token-based distributed mutual exclusion algorithm is presented. the algorithm assumes a fully connected, reliable physical network and a directed acyclic graph (DAG) structured logical network. the number of messag...
详细信息
ISBN:
(纸本)0818621443
A token-based distributed mutual exclusion algorithm is presented. the algorithm assumes a fully connected, reliable physical network and a directed acyclic graph (DAG) structured logical network. the number of messages required to provide mutual exclusion is dependent upon the logical topology imposed on the nodes. Using the best topology, the algorithm attains comparable performance to a centralized mutual exclusion algorithm;i.e., three messages per critical section entry. the algorithm achieves minimal heavy-load synchronization delay and imposes very little storage overhead.
Several existing distributed file systems provide reliability by server replication. An alternative approach is to use dual-ported disks accessible to a server and a backup. the two approaches are compared by examinin...
详细信息
ISBN:
(纸本)0818621443
Several existing distributed file systems provide reliability by server replication. An alternative approach is to use dual-ported disks accessible to a server and a backup. the two approaches are compared by examining an example of each. Deceit is a replicated file server that emphasizes flexibility. HA-NFS is an example of the second approach that emphasizes efficiency and simplicity. the two file servers run on the same hardware and implement SUN's NFS protocol. the comparison shows that replicated servers are more flexible and tolerant of a wider variety of faults. On the other hand, the dual-ported disks approach is more efficient and simpler to implement. When tolerating single failure, dual-ported disks also give somewhat better availability.
the justification, design, and performance of the Stealthdistributed scheduler is discussed. the goal of Stealth is to exploit the unused computing capacity of a workstation-based distributed system (WDS) without und...
详细信息
the justification, design, and performance of the Stealthdistributed scheduler is discussed. the goal of Stealth is to exploit the unused computing capacity of a workstation-based distributed system (WDS) without undermining the predictability in quality of service that a WDS provides to workstation owners. It is shown that the liberal approach taken by the Stealthdistributed scheduler is a promising method of exploiting the vast quantity of unused computing capacity typically present in a WDS, while preserving predictability of service for workstation owners.< >
A simple owner protocol for implementing a causal distributed shared memory (DSM) is presented, and it is argued that this implementation is more efficient than comparable coherent DSM implementations. Moreover, it is...
详细信息
A simple owner protocol for implementing a causal distributed shared memory (DSM) is presented, and it is argued that this implementation is more efficient than comparable coherent DSM implementations. Moreover, it is shown that writing programs for causal memory is no more difficult than writing programs for atomic shared memory.< >
暂无评论