We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time, which we formalize as a problem of scheduling the edges of a weighted multigraph. Although the general problem ...
详细信息
ISBN:
(纸本)0897911105
We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time, which we formalize as a problem of scheduling the edges of a weighted multigraph. Although the general problem is NP-complete, we identify polynomial time solvable special cases and derive good performance bounds for several natural approximation algorithms. The above results assume the existence of a central controller, but we also show how the approximation algorithms, along with their performance guarantees, can be adapted to a distributed regime.
Two design rules which aid the construction of distributedcomputing systems and the provision of fault tolerance are described, namely that: (i) a distributedcomputing system should be functionally equivalent to the...
详细信息
ISBN:
(纸本)0818605014
Two design rules which aid the construction of distributedcomputing systems and the provision of fault tolerance are described, namely that: (i) a distributedcomputing system should be functionally equivalent to the individual computing systems of which it is composed, and (ii) fault tolerant systems should be constructed from generalized fault tolerant components. The reasoning behind these two 'recursive structuring principles', and the consequences of attempting to adhere to them, are discussed. Where appropriate this discussion is illustrated by reference to a distributed system based on UNIX that is now operational at Newcastle and several other locations. This system has been implemented by adding a software subsystem, known as the Newcastle Connection, to each of a set of UNIX systems. By this means the authors has constructed a distributed system which is functionally equivalent at both the user and the program level to a conventional uniprocessor UNIX system.
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...
详细信息
The distributed V kernel is a message-oriented kernel that provides uniform local and network interprocess communication. It is primarily being used in an environment of diskless workstations connected by a high-speed...
详细信息
作者：
Mohan, C.Lindsay, B.IBM
San Jose Research Lab San Jose CA USA IBM San Jose Research Lab San Jose CA USA
This paper describes two efficient distributed transaction commit protocols, the Presumed Abort (PA) and Presumed Commit (PC) protocols, which have been implemented in the distributed data base system R. PA and PC are...
详细信息
ISBN:
(纸本)0897911105
This paper describes two efficient distributed transaction commit protocols, the Presumed Abort (PA) and Presumed Commit (PC) protocols, which have been implemented in the distributed data base system R. PA and PC are extensions of the well-known two-phase (2P) commit protocol. PA is optimized for read-only transactions and a class of multi-site update transactions, and PC is optimized for other classes of multi-site update transactions. The optimizations result in reduced inter-site message traffic and log writes, and, consequently, a better response time for such transactions. We derive the new protocols in a step-wise fashion by modifying the 2P protocol.
R∗ is an experimental prototype distributed database management system. The computation needed to perform a sequence of multisite user transactions in R∗ is structured as a tree of processes communicating over virtual...
详细信息
This paper describes an application of Byzantine Agreement to distributed transaction commit. We replace the second phase of one of the commit algorithms with Byzantine Agreement, providing certain trade-offs and adva...
详细信息
ISBN:
(纸本)0897911105
This paper describes an application of Byzantine Agreement to distributed transaction commit. We replace the second phase of one of the commit algorithms with Byzantine Agreement, providing certain trade-offs and advantages at the time of commit and providing speed advantages at the time of recovery from failure. The present work differs from that presented in left bracket DoSt82b right bracket by increasing the scope (handling a general tree of processes, and multi-cluster transactions) and by providing an explicit set of recovery algorithms. We also provide a model for classifying failures that allows comparisons to be made among various proposed distributed commit algorithms. The context for our work is the Highly Available Systems project at the IBM San Jose Research Laboratory.
Commit protocols guarantee the consistency of distributed databases in absence of any failures. A commit protocol is resilient to a class of failures if it is possible to guarantee that a) databases at all operational...
详细信息
ISBN:
(纸本)0897910974
Commit protocols guarantee the consistency of distributed databases in absence of any failures. A commit protocol is resilient to a class of failures if it is possible to guarantee that a) databases at all operational sites in presence of these failures are consistent and b) other sites can be recovered consistently with these sites when the failure is repaired. It is proved that quorum-based termination protocols perform very well in the presence of network partitioning. If the central site is reliable, we can prove that centralized commit protocols indeed perform better than all decentralized ones. Thus, the general preference for centralized commit protocols is justified.
The proceedings contain 30 papers. The topics discussed include: dynamic systems and their distributed termination;UIDs as internal names in a distributed file system;testing incomplete specifications of distributed s...
ISBN:
(纸本)0897910818
The proceedings contain 30 papers. The topics discussed include: dynamic systems and their distributed termination;UIDs as internal names in a distributed file system;testing incomplete specifications of distributed systems;distributed communication via global buffer;language constructs and support systems for distributedcomputing;efficient schemes for parallel communication;distributed multi-destination routing: the constraints of local information;randomized parallel communication;language concepts for distributed processing of large arrays;four combinators for concurrency;bounds on information exchange for byzantine agreement;a refinement of Kahn's semantics to handle nondeterminism and communication refinement of Kaiin's semantics to handle non-determinism and communication;understanding and using asynchronous message passing;on the distribution of an assertion;real time resource allocation in distributed systems;finding safe paths in a faulty environment;on-the-fly deadlock prevention;edge locks and deadlock avoidance in distributed systems;and a distributed algorithm for detecting resource deadlocks in distributed systems.
Complex systems (such as distributed ones) should be specified before they are implemented. Even more advantages accrue if the specifications are executable, so that behaviors of the specified systems can be tested. T...
详细信息
暂无评论