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
Abstract In 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.pdf 2.90 Mb 00:13:24 00:06:53 00:06:02 00:03:01 00:00:15

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