Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for +publisher:"Wayne State University" +contributor:("Nathan W. Fisher"). Showing records 1 – 2 of 2 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Wayne State University

1. Mohammadi, Anwar. Truthful Mechanisms For Real-Time System Scheduling In Competitive Environments.

Degree: MS, Computer Science, 2012, Wayne State University

In a non-competitive environment, sporadic real-time task scheduling on a single processor is well understood. In this thesis, we consider a competitive environment comprising several real-time tasks vying for execution upon a shared single processor. Each task obtains a value if the processor successfully schedules all its jobs. Our objective is to select a feasible subset of these tasks to maximize the sum of values of selected tasks. We consider both dynamic-priority and static-priority scheduling algorithms. There are algorithms for solving these problems in non-competitive settings. However, we consider these problems in an economic setting in which each task is owned by a selfish agent. Each agent reports the characteristics of her own task to the processor owner. The processor owner uses a mechanism to allocate the processor to a subset of agents and to determine the payment of each agent. Since agents are selfish, they may try to manipulate the mechanism to obtain the processor. We are interested in truthful mechanisms in which it is always in agents' best interest to report the true characteristics of their tasks. We design exact and approximate truthful mechanisms for this competitive environment and study their performance. Advisors/Committee Members: Nathan W. Fisher.

Subjects/Keywords: Competitive Environments; Earliest-Deadline First; Mechanism Design; Rate-Monotonic; Sporadic Task Systems; Computer Sciences

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Mohammadi, A. (2012). Truthful Mechanisms For Real-Time System Scheduling In Competitive Environments. (Masters Thesis). Wayne State University. Retrieved from https://digitalcommons.wayne.edu/oa_theses/239

Chicago Manual of Style (16th Edition):

Mohammadi, Anwar. “Truthful Mechanisms For Real-Time System Scheduling In Competitive Environments.” 2012. Masters Thesis, Wayne State University. Accessed January 22, 2020. https://digitalcommons.wayne.edu/oa_theses/239.

MLA Handbook (7th Edition):

Mohammadi, Anwar. “Truthful Mechanisms For Real-Time System Scheduling In Competitive Environments.” 2012. Web. 22 Jan 2020.

Vancouver:

Mohammadi A. Truthful Mechanisms For Real-Time System Scheduling In Competitive Environments. [Internet] [Masters thesis]. Wayne State University; 2012. [cited 2020 Jan 22]. Available from: https://digitalcommons.wayne.edu/oa_theses/239.

Council of Science Editors:

Mohammadi A. Truthful Mechanisms For Real-Time System Scheduling In Competitive Environments. [Masters Thesis]. Wayne State University; 2012. Available from: https://digitalcommons.wayne.edu/oa_theses/239


Wayne State University

2. Dewan, Farhana. Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems.

Degree: PhD, Computer Science, 2014, Wayne State University

Compositional real-time research has become one of the emerging trends in embedded and real-time systems due to the increasing scale and complexity of such systems. In this design paradigm, a large system is decomposed into smaller and simpler components, each of which abstracts their temporal requirements via interfaces. Such systems are mostly implemented by resource partitions to ensure that the components receive resources according to their interfaces. Potential implementations of a resource partition are via server-based interfaces or demand-based interfaces. In this context, our thesis in this dissertation is as follows: Currently, server-based interfaces ensure strong temporal isolation among components at the cost of resource over-provisioning whereas demand-based interfaces precisely model the resource demand of a component without the guarantee of temporal isolation. For both these models, efficient and effective resource allocation as well as strict temporal isolation among components can be achieved. Specifically, we can obtain efficient and near-optimal bandwidth allocation schemes and admission controllers for periodic resource model and arbitrary demand-based interface respectively. Furthermore, efficient slack reclamation technique can be obtained to allocate unused processing resources at runtime while still enforcing the given interface. To support our thesis, we address efficient resource allocation among components with server-based interfaces by providing fully-polynomial-time approximation schemes (FPTAS) for allocating processing resource to components scheduled by earliest-deadline-first (EDF) or fixed-priority (FP) scheduling algorithm. For enforcing temporal isolation of demand-based interfaces, we provide a parametric approximate admission control algorithm, which has polynomial-time complexity in terms of number of active jobs in the system and the approximation parameter. Finally, to address efficient reclamation of unused processing resources, we give a novel technique to optimally and efficiently determine maximum allowable runtime slack for a component with arbitrary interface, considering active jobs in the system and guaranteeing system schedulability even for worst-case future job arrival scenarios. We expect that these techniques can ultimately be used to minimize the size, weight, and power requirements of real-time and embedded systems by reducing the processing resource requirements of such systems. Advisors/Committee Members: Nathan W. Fisher.

Subjects/Keywords: Admission Control; Approximation Algorithm; Compositional Real-Time Systems; Real-Time Interface; Resource Allocation; Slack Reclamation; Computer Sciences

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Dewan, F. (2014). Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems. (Doctoral Dissertation). Wayne State University. Retrieved from https://digitalcommons.wayne.edu/oa_dissertations/880

Chicago Manual of Style (16th Edition):

Dewan, Farhana. “Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems.” 2014. Doctoral Dissertation, Wayne State University. Accessed January 22, 2020. https://digitalcommons.wayne.edu/oa_dissertations/880.

MLA Handbook (7th Edition):

Dewan, Farhana. “Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems.” 2014. Web. 22 Jan 2020.

Vancouver:

Dewan F. Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems. [Internet] [Doctoral dissertation]. Wayne State University; 2014. [cited 2020 Jan 22]. Available from: https://digitalcommons.wayne.edu/oa_dissertations/880.

Council of Science Editors:

Dewan F. Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems. [Doctoral Dissertation]. Wayne State University; 2014. Available from: https://digitalcommons.wayne.edu/oa_dissertations/880

.