Fault-Tolerant Scheduling and Broadcast Problems

Liestman, Arthur Lee

Permalink

https://hdl.handle.net/2142/66448 Copy

Description

Title

Fault-Tolerant Scheduling and Broadcast Problems

Author(s)

Liestman, Arthur Lee

Issue Date

1981

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Computer Science

Language

eng

Abstract

• Incorporating fault-tolerance into a computer system involves redundancy and therefore increases the system's cost. An investigation into this cost is initiated by considering the application of fault-tolerance to two standard problems: scheduling responses to periodic requests in a real-time system and broadcasting messages on communication networks. The faults considered in these problems result from timing errors and communication line failures, respectively. For both problems fault-tolerant techniques are incorporated into the system and various costs are analyzed.
• A single-processor computing system is to execute a set of jobs each of which consists of a sequence of periodic requests. Each job's request period is a multiple of the next smallest request period. Such a system is termed simply periodic. Two algorithms are provided for each service: a primary which produces a good quality service but is subject to timing errors and an alternate which produces an acceptable response and by definition is not subject to timing errors. The best schedule is obviously one that successfully executes the primary algorithm for each request. A schedule is fault-tolerant if it guarantees that one of the responses will successfully execute prior to the deadline.
• Several scheduling algorithms are developed for variations of this problem including a dynamic scheduling algorithm which produces an optimal fault-tolerant schedule. That is, at each point in time the number of primaries scheduled is maximum among those schedules which guarantee that all deadlines will be met. A mechanism is described in which a tree of schedules may be precomputed and used to implement the actions of this dynamic algorithm in a real-time system.
• Consider a graph G = (V,E) which represents a communications network. One member of the network has a message which is to be disseminated to all the other members. This is to be accomplished as quickly as possible by a series of calls over the network. The series of calls is constrained by the following: (1)each call requires one unit of time, (2)any member may participate in at most one cell per time unit, and (3)a member can only call an adjacent member. This process is referred to as broadcasting. In the event that a communications link fails the message may not be disseminated to all of the network members. By incorporating redundancy in the calling scheme the completion of the broadcast may be guaranteed in the presence of up to k faults. This process is referred to as k fault-tolerant broadcasting.
• Several problems related to fault-tolerant broadcasting are investigted. Graphs which admit k fault-tolerant broadcast schemes are investigated, concentrating on the trade off between the time allowed for broadcasting and the number of edges required in the graphs. A survey of known "optimal" graphs is given. Fault-tolerant broadcasting in grid or grid-like graphs is also considered. The results show that the addition of 1 fault-tolerance to the broadcasting process in grids requires a small increase in the time required for broadcasting and an increase in system utilization.

Graduation Semester

1981

Type of Resource

text

Permalink

http://hdl.handle.net/2142/66448

Owning Collections