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.
Praveen Jayachandran is a doctoral candidate at the University of Illinois at Urbana-Champaign. His research interests are in the area of performance and resource management of distributed systems and networks. His doctoral thesis focuses on developing a reduction-based schedulability theory for the end-to-end delay analysis of workflows in distributed systems. He received the best student paper award at the Euromicro Conference on Real-Time Systems, 2007, and the best paper award at the same conference in 2009. He received the C.S. and Jane Liu award from the Department of Computer Science at the University of Illinois in 2008, awarded to a graduate student showing exceptional research promise early in their graduate studies. He is also a recipient of the Vodafone fellowship, 2007-08, and the Andrew and Shana Laursen fellowship, 2005-06.