Scheduling Distributed Real-Time Tasks in Unreliable and Untrustworthy Systems

Simple item page
dc.contributor.authorHan, Kaien
dc.contributor.committeechairRavindran, Binoyen
dc.contributor.committeememberYang, Yalingen
dc.contributor.committeememberPlassmann, Paul E.en
dc.contributor.committeememberJensen, E. Douglasen
dc.contributor.committeememberCao, Yangen
dc.contributor.committeememberAthanas, Peter M.en
dc.contributor.departmentElectrical and Computer Engineeringen
dc.date.accessioned2014-03-14T20:09:48Zen
dc.date.adate2010-05-06en
dc.date.available2014-03-14T20:09:48Zen
dc.date.issued2010-01-22en
dc.date.rdate2010-05-06en
dc.date.sdate2010-04-16en
dc.description.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.en
dc.description.degreePh. D.en
dc.identifier.otheretd-04162010-132432en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-04162010-132432/en
dc.identifier.urihttp://hdl.handle.net/10919/26917en
dc.publisherVirginia Techen
dc.relation.haspartHan_K_D_2010.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectDistributed Real-Time Schedulingen
dc.subjectGossip Protocolsen
dc.subjectMutual Exclusionen
dc.subjectUnreliable Systemsen
dc.subjectByzantine Attacksen
dc.subjectTime/Utility Functionsen
dc.subjectUtility Accrual Schedulingen
dc.titleScheduling Distributed Real-Time Tasks in Unreliable and Untrustworthy Systemsen
dc.typeDissertationen
thesis.degree.disciplineElectrical and Computer Engineeringen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.namePh. D.en

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Han_K_D_2010.pdf
Size:
2.76 MB
Format:
Adobe Portable Document Format
Download

Collections

Doctoral Dissertations