Type of Document Dissertation Author Han, Kai Author's Email Address khan05@vt.edu URN etd-04162010-132432 Title Scheduling Distributed Real-Time Tasks in Unreliable and Untrustworthy Systems Degree PhD Department Electrical and Computer Engineering Advisory Committee

Advisor Name Title Ravindran, Binoy Committee Chair Athanas, Peter M. Committee Member Cao, Yang Committee Member Jensen, E. Douglas Committee Member Plassmann, Paul E. Committee Member Yang, Yaling Committee Member Keywords

- Distributed Real-Time Scheduling
- Gossip Protocols
- Mutual Exclusion
- Unreliable Systems
- Byzantine Attacks
- Time/Utility Functions
- Utility Accrual Scheduling
Date of Defense 2010-01-22 Availability unrestricted AbstractIn this dissertation, we consider scheduling distributed soft real-time tasks in unreliable(e.g., those with arbitrary node and network failures) and untrustworthy systems (e.g., those

with Byzantine node behaviors). We present a distributed real-time scheduling algorithm

called Gamma. Gamma considers a distributed (i.e., multi-node) task model where tasks are

subject to Time/Utility Function (or TUF) end-to-end time constraints, and the scheduling

optimality criterion of maximizing the total accrued utility. The algorithm makes three novel

contributions. First, Gamma uses gossip for reliably propagating task scheduling parameters

and for discovering task execution nodes. Second, Gamma achieves distributed real-time

mutual exclusion in unreliable environments. Third, the algorithm guards against potential

disruption of message propagation due to Byzantine attacks using a mechanism called

Launcher-Attacker-Infective-Susceptible-Immunized-Removed-Consumer (or LAISIRC). By

doing so, the algorithm schedules tasks with probabilistic termination-time satisfactions,

despite system unreliability and untrustworthiness.

We analytically establish several timeliness and non-timeliness properties of the algorithm

including probabilistic end-to-end task termination time satisfactions, optimality

of message overheads, mutual exclusion guarantees, and the mathematical model of the

LAISIRC mechanism. We conducted simulation-based experimental studies and compared

Gamma with its competitors. Our experimental studies reveal that Gamma’s scheduling algorithm

accrues greater utility and satisfies a greater number of deadlines than do competitor

algorithms (e.g., HVDF) by as much as 47% and 45%, respectively. LAISIRC is more tolerant

to Byzantine attacks than competitor protocols (e.g., Path Verification) by obtaining as much as 28% higher correctness ratio. Gamma’s mutual exclusion algorithm accrues greater

utility than do competitor algorithms (e.g., EDF-Sigma) by as much as 25%. Further, we

implemented the basic Gamma algorithm in the Emulab/ChronOS 250-node testbed, and

measured the algorithm’s performance. Our implementation measurements validate our

theoretical analysis and the algorithm's effectiveness and robustness.

Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access Han_K_D_2010.pdf2.90 Mb 00:13:24 00:06:53 00:06:02 00:03:01 00:00:15

Browse All Available ETDs by
( Author |
Department )

If you have questions or technical problems, please Contact DLA.