Recent trends in computing systems, such as cloud computing, virtual execution environments, and grid computing, have been away from centralized designs towards highly extensible, open, and distributed systems comprising multiple independently-developed and operated subsystems. Such systems present a fundamental design challenge for applications that require real-time guarantees, due to the reliance upon all subsystem owners and developers to truthfully express their resource requirements. Currently, no real-time open system environment framework prevents a user from obtaining an ``unfair'' allocation of system resources by simply misrepresenting their subsystem's resource requirements. A solution is needed, that formally guarantees an efficient/equitable resource allocation among subsystems. The approach taken here is to apply a novel combination of real-time scheduling and game theory (i.e., algorithmic mechanism design) techniques, to design truth-inducing allocation mechanisms for shared real-time processing platforms. These techniques are proven and evaluated by developing a middleware implementation and a grid simulation for a real-time setting.
A trustworthy scheme for allocating time-critical resources among independently developed subsystems is a key to reducing development and operational costs, and increasing the reliability of the complex computing systems upon which our society and economy increasingly depend. Beyond direct benefits of the technology, this project furthers educational goals by actively involving undergraduate and underrepresented students in research.
The current trend in the design of computer systems has recently shifted away from closed, centralized systems towards more open and distributed systems. These design goals present a fundamental challenge for systems and organizations which require real-time guarantees. Examples of such applications infrastructure include cloud computing, virtual execution environment (VEE) technologies, and grid computing. Organizations are already developing infrastructure for such large-scale processing infrastructure. However, the current frameworks that support guarantees upon shared systems rely upon the clients to truthfully express their resource requirements. Currently, no real-time open system environment framework prevents an organization from obtaining an "unfair" allocation of system resources by simply misrepresenting their subsystem's resource requirements. It is essential to develop mechanisms and open system environment frameworks that ensure a fair allocation of resources among subsystems by accounting for organization behavior and providing incentives for a truthful expression of resource requirements. Intellectual Merit: We were the first to formulate the problem of competitive real-time open environments. As a starting point, we considered the setting where multiple clients with real-time requirements are competing for the use of a single processing resource. For this initial setting, we developed and implemented algorithms for determining the selection of clients that are granted access to the processing resource. Our algorithms ensured two important properties that are desirable in competitive environments: 1) the clients that value the resource most receive it (called "optimal"), and 2) no client has an incentive to lie about his/her real-time requirements or valuation of the resource (called "strategy-proof"). Unfortunately, the problem of obtaining a strategy-proof, optimal algorithm can be formally shown to be difficult to compute efficiently. Thus, our project also proposed approximation algorithms that guarantee a strategy-proof, near-optimal solution using a more time-efficient computation. From this starting point, we extended this setting to address the problem where each client has multiple computational modes and expresses a preference ordering over those modes. The challenges that this project addressed for this multi-mode setting were: 1) obtaining analytical techniques for ensuring that real-time requirements are met when modes are changed; 2) developing client selection algorithms and associated game-theoretic analysis to handle the multiple preferences being expressed by each client; 3) developing control-theoretic techniques to adapt to the energy/thermal constraints from performing computation for the system's clients; and 4) developing techniques to account for the interference between clients’ applications due to contention in the system's memory hierarchy. We have also obtained solutions for numerous allocation and scheduling problems in non-hard-real-time cloud/grid computing environments. One of the central challenges of managing such large-scale data-intensive systems is efficient and fair provisioning of resources such as CPUs, memory, storage, and the energy required to run these systems. In this project, we provided both optimal and provably near-optimal, strategy-proof algorithms for ensuring a fair, equitable, and efficient allocation of these cloud/grid resources to clients that also ensure revenue is maximized for the cloud/grid-service provider. In particular, our research addressed the following challenges: 1) adaptation to dynamically changing client demands for resources; 2) the formation of larger virtual organizations by a number of grid service providers; 3) minimizing energy consumption for standard parallel programming models; 4) designing efficient auctions of system resources; 5) efficiently computing the economic properties of these market-based systems; and 6) ensuring that privacy requirements are preserved in any allocation of resources. Broader Impact: The research outcomes of this project have been published in top journals including IEEE Transactions on Computers, IEEE Transactions on Parallel and Distributed Systems, ACM Transactions on Embedded Computing Systems, and the Journal of Parallel and Distributed Computing, and top conferences, including the Euromicro Conference on Real-Time Systems (ECRTS). Furthermore, the research resulting from this project has been recognized for its excellence in related research areas such as operations research; one publication from this project was selected as finalist for best paper award at the 2014 INFORMS annual meeting. The techniques and research developed in this project have already been incorporated into several computer science classes at Wayne State University. Two Ph.D. students and one Masters student involved in this project have graduated during the period of the project. Furthermore, the project also involves two other Ph.D. students and two undergraduate students, including a female Ph.D. student whose excellent research contributions on this project have received numerous awards from both the Wayne State University and the larger research community. Furthermore, several members of this project are actively involved in organizations such as the local student chapter of the ACM and ACM-W that help broaden participation of under-represented groups in computer science.
