MESSIAHS involved research into support for distributed, hierarchical scheduling of tasks on autonomous, heterogeneous computing systems. Many researchers have studied related problems of determining near-optimal task placement in such systems. However, these algorithms assume the existence of mechanisms to gather information about the system, move tasks, and perform other related operations. We defined and constructed exactly those mechanisms, and in an abstract fashion that allows them to be generalized to other distributed architectures.
Autonomous systems consist of one or more systems connected by a message-passing communications medium; at the lowest level, a processor is an autonomous system with no subsystems. Processors within the same system may be of different type. Thus, autonomous systems are hierarchical constructs. The internal makeup of an autonomous system is private information, and is not necessarily shared with exterior systems. This is typical of the guiding principle of autonomous systems: all information, behavior, and policy pertaining to it is private and local to that system. Any sharing of this information is at the discretion of the local system.
The goals of our research were to provide mechanisms for efficient implementations of scheduling policies on systems ranging from a few workstations on a local-area network to thousands of machines spread over a large geographical area and connected by arbitrary interconnection links. We examined the requirements of these systems for different levels of security, reliability, load sharing, and location transparency. We then characterized these and other properties in a scalable mechanism that does not impose undue load demands, and is capable of supporting a wide range of distributed scheduling policies.
This work was done under a NASA Fellowship by Steve Chapin, now on the faculty at Syracuse University (chapin@ecs.syr.edu). Steve's Ph.D. dissertation was supervised by Gene Spafford. Some of our results are reported in:
Dr. Chapin also cites some results from his MESSIAHS work in his chapter on distributed scheduling in The Computer Science and Engineering Handbook by CRC Press, A. Tucker ed., 1997.
Future work on MESSIAHS may be conducted by Dr. Chapin; Professor Spafford may or may not conduct future research in this area.