the problem of predicting the reliability of a distributed system based on the principles of Byzantine agreement is addressed. the system is considered inoperable or failed if Byzantine agreement cannot be guaranteed....
详细信息
the problem of predicting the reliability of a distributed system based on the principles of Byzantine agreement is addressed. the system is considered inoperable or failed if Byzantine agreement cannot be guaranteed. the reliability models depend on a unified model of interactive consistency, which is based on a unique fault taxonomy appropriate for distributed systems. the unified model takes advantage of the fact that some faults may not be of an arbitrary nature, while still allowing for the fact that some faults may be arbitrary. A closed-form expression for the reliability and the mean time to failure of systems based on the unified model is derived. Each processor is allowed to have multiple failure modes, and the contribution of the interactive consistency algorithm is explicitly taken into account. the practical value of this unified model in designing ultrareliable systems is demonstrated by several examples.
A distributed algorithm based on echo algorithms is presented which constructs the minimum-weight spanning tree in a general undirected graph. In the worst case, the algorithm needs at most (2m + 2(n-1) log (n/2)) mes...
详细信息
A distributed algorithm based on echo algorithms is presented which constructs the minimum-weight spanning tree in a general undirected graph. In the worst case, the algorithm needs at most (2m + 2(n-1) log (n/2)) messages and (2d log n) time, where d is the diameter of the network. In the best case, it needs only 2m messages and 2d time. the algorithm works in phases, and each phase consists of a down wave and an up wave. When the number of fragments is cut by at least one half in each phase, it needs at most O(log n) phases. On average, the algorithm needs only O(m) messages and O(d) time. the algorithm itself is simple, so that other distributed algorithms based on it can be derived more easily.
A service execution mechanism is designed to provide users transparent access to computational services in a distributed environment. the central idea in this approach is that computations available to the user in a d...
详细信息
A service execution mechanism is designed to provide users transparent access to computational services in a distributed environment. the central idea in this approach is that computations available to the user in a distributed system should be treated as services, where a service is a user-level computation that is offered by one or more machines. the identification of a service is separate from its execution for all computations available to the user. this abstraction allows the details of performing a service to be hidden from the user, and allows the user to specify what services he/she would like to use and not be concerned with where or how the services are invoked. the author's experience with a prototype implementation is reviewed. It is concluded that the service mechanism is a small cost in the total time to execute a simple local service, and an insignificant cost for more computation-intensive services. For services that are invoked remotely, additional costs may be incurred for probing during selection, but these costs are negligible in comparison to the costs of invocation.
An experimental distributed system based on an integrated system design was built that incorporates user-level or environmental application requirements into the design issues of the distributed operating system Drago...
详细信息
An experimental distributed system based on an integrated system design was built that incorporates user-level or environmental application requirements into the design issues of the distributed operating system Dragon Slayer. the key for making use of the Dragon Slayer services, in supporting applications requesting a high amount of reliability under completely decentralized control, is the definition of the concept of distributed objects. these were used as the basis for a paradigm of distributedcomputingthat allows users to neglect the distribution of services and responses. How distributed objects are managed in Dragon Slayer is outlined. the distributed objects are logical objects which may be partitioned. the parts or fractions may be distributed over several nodes. they may even exist in multiple copies or version. In order to prepare the ground for requirements regarding distributed object management, a taxonomy of object-oriented approaches and their methods of managing distributed object operations is given. A set of necessary conditions for the design of distributed operating system services that are to support such management methods under completely decentralized control is determined. the major issues of the distributed operating system development Dragon Slayer are described which satisfy these conditions.
A model and correctness criteria for timed atomic commitment (TAC) are presented which require the processes to be functionally consistent, but allow the outcome to include an exceptional state, indicating that timing...
详细信息
A model and correctness criteria for timed atomic commitment (TAC) are presented which require the processes to be functionally consistent, but allow the outcome to include an exceptional state, indicating that timing constraints have been violated. Correct TAC behavior is defined by presenting an abstract description of the processes involved in the commitment and minimal correctness criteria for their behavior. the correctness criteria capture the intuitive notion that an exception outcome should only occur in the presence of faults, and an aborted outcome should only occur if faults occur or some process votes no. A centralized two-phase commit protocol was modified to meet the correctness criteria by introducing deadlines on the various stages the participants go through (voting and performing), and on the decision phase for the coordinator. the deadlines are derived using several system parameters: maximum message delay, clock drift, and execution time. the protocol is then shown to be correct.
A probabilistic method is proposed for reading remote clocks in distributed systems subject to unbounded random communication delays. the method can achieve clock synchronization precisions superior to those attainabl...
详细信息
A probabilistic method is proposed for reading remote clocks in distributed systems subject to unbounded random communication delays. the method can achieve clock synchronization precisions superior to those attainable by previously published clock synchronization algorithms. the method can be used to improve the precision of both internal and external synchronization algorithms. the approach is probabilistic because it does not guarantee that a processor can always read a remote clock with an a priori specified precision;however, by retrying a sufficient number of times, a process can read the clock of another process with a given precision with a probability as close to one as desired. An important characteristic of the method is that, when a process succeeds in reading a remote clock, it knows the actual reading precision achieved. the use of the remote clock reading methods is illustrated by presenting a time service which maintains externally (and, hence, internally) synchronized clocks in the presence of process, communication, and clock failures.
Analytical models are presented that use Petri nets for fault-tolerant schemes used in distributed systems. these models are used in the quantitative evaluation and selection of good fault-tolerant schemes for specifi...
详细信息
Analytical models are presented that use Petri nets for fault-tolerant schemes used in distributed systems. these models are used in the quantitative evaluation and selection of good fault-tolerant schemes for specific system configurations. Several different fault-tolerant schemes that can be modeled using Petri nets are discussed in detail. these schemes include rollback recovery with checkpointing, recovery blocks, N-version programming, and conversations. After a brief review of Petri net models, extension of the Petri net models to incorporate fault-tolerant schemes is considered. A methodology for evaluating a fault-tolerant scheme for a specific system configuration and the steps involved in building a Petri net model of a fault-tolerant system are described. the subnet primitives involved in building these models are identified and an algorithm for building the models automatically is described. Examples illustrating this extended Petri net model are discussed and numerical results are presented to show the applicability of the models.
Using two branch-and-bound (B&B) algorithms, an optimal solution is proposed to the problem of allocating (or assigning withthe subsequent scheduling considered) periodic tasks to a set of heterogeneous processin...
详细信息
Using two branch-and-bound (B&B) algorithms, an optimal solution is proposed to the problem of allocating (or assigning withthe subsequent scheduling considered) periodic tasks to a set of heterogeneous processing nodes (PNs) of a distributed real-time system. the allocation objective is to minimize the maximum normalized task response time, called the system hazard, subject to precedence constraints among the tasks to be allocated. First, the task system is modeled with a task graph, which describes computation and communication modules as well as the precedence constraints among them. Second, the exact system hazard of a complete assignment is determined so that an optimal assignment can be derived. this exact cost is obtained by optimally scheduling the modules assigned to each PN with a B&B algorithm guided by the dominance relationship between simultaneously schedulable modules. third, to reduce the amount of computation needed for an optimal assignment, a lower-bound system hazard that is obtainable with a polynomial time algorithm is derived. this lower-bound cost, together withthe exact cost of a complete assignment, is used to guide the search for an optimal assignment efficiently. Examples are provided to demonstrate the concept, utility, and power of the approach.
A ring-based media access control protocol and architecture, Fast Ring, which combines the best features of the token ring and contention ring, is proposed. For this protocol, a free token circulates on the ring when ...
详细信息
A ring-based media access control protocol and architecture, Fast Ring, which combines the best features of the token ring and contention ring, is proposed. For this protocol, a free token circulates on the ring when the ring is idle. A ready station can transmit either by capturing the token or sensing the ring idle. the protocol works in such a way that the ready node which captures the free token, before or while transmitting, is able to continue transmission. All the other contending nodes have to stop their transmissions and then send the abort signal when they receive the upstream transmission. After its transmission, the successful station puts a free token on the ring and the protocol enters the token mode. It behaves like the token ring protocol until the ring becomes idle again when all the ready nodes complete their transmissions. Comparison of the performance of fast ring withthose of contention ring, token ring, and carrier-sense multiaccess with collision detection protocols shows that the fast ring outperforms all these local area network protocols over the whole throughput range at all transmission rates.
An algorithm is presented that defects for termination of distributed computations by an auxiliary controlling agent. the algorithm assigns a weight W, 0 >
An algorithm is presented that defects for termination of distributed computations by an auxiliary controlling agent. the algorithm assigns a weight W, 0 >
暂无评论