Praveen Jayachandran
University of Illinois at Urbana-Champaign
Thursday, April 29, 10:00am, ENS 637
Feasible Region Calculus: A Reduction-based Schedulability Theory for Distributed Real-Time Systems
The diminishing size and cost of hardware has led to a recurrent trend of growing scale and complexity in several classes of systems such as embedded systems, server farms, cyber-physical systems, ad hoc wireless networks, and sensor networks. Avionics and automotive systems are heading towards increased automation, with several stages of processing for various real-time tasks within a distributed computing environment. Each search query answered by Google, typically goes through thirty different stages of computation, with the server farm itself comprising of thousands of processors. Manufacturing plants in every industry have tens of specialized servers, producing hundreds of parts that follow different routes through the system. Cyber-physical systems, as an umbrella term for various personal and military applications, has gained a lot of momentum, with the NSF identifying it as a key focus area for research. An important and extremely challenging problem in such systems is to compose end-to-end properties such as delay, throughput, stability, robustness, security, and functional correctness, from those of their individual components.
As part of my doctoral research, I have addressed this compositional problem for a broad category of timing properties. The theory we are developing, which we call Feasible Region Calculus, provides a fundamental understanding of the end-to-end delay of work flows that share resources within the system. A guiding philosophy of the theory has been to develop reduction rules, similar to circuit theory and control theory, that enable the distributed system to be transformed to an equivalent hypothetical centralized processor system for the purposes of analysis, such that the end-to-end properties are preserved. The transformation significantly reduces the complexity and improves the accuracy of the analysis with increasing system scale. While we have successfully demonstrated this reduction-based approach to the analysis of end-to-end delay in large distributed systems and networks, we have only scratched the surface of a largely unexplored territory. I wish to generalize this approach to the study of other important end-to-end properties in distributed systems and networks. Further, I envision that the scope of the theory can be extended to realms outside computing, such as project management as well.