Predictability for real-time command and control

Abstract

This paper describes a new and different paradigm for real-time command and control that we show can provide a static, polynomial-time scheduling algorithm. Current efforts in real -time scheduling have been unable to predict system performance, and use a unpredictable "dynamic" scheduling algorithm. The Nation’s Air Traffic Control (ATC) System has been unable to satisfy performance requirements, and is extremely expensive. An editorial in "USA Today" (419-1999) cites expenditures in ATC at $41 billion. But, current multiprocessor technology cannot do the job. The FAA wisely required a “proof of concept” study before the (AAS) contract. But that study, after expending a billion dollars, was abandoned, and production moved forward. AAS was canceled in 1995 exactly in line with real-time scheduling theory predictions. Garey, Graham, and Johnson state: "For these scheduling problems, no efficient optimization algorithm has yet been found, and indeed, none is expected.”[9]. Stankovic et. al. state: "…complexity results show most real-time multiprocessing scheduling is NP -hard.” [6]. We offer a completely different approach, that has been shown to overcome the severe limitations of multiprocessi ng. Additionally, we show that real-time parallel-processing techniques can be statically scheduled to solve the set of tasks making up the ATC problem for a worst-case environment.