/ Edward A. Billard / Assistant Professor
/ Alice Riedmiller / Research Associate
The Operating Systems Laboratory is participating in both top-down education and state-of-the-art research.
In education, the first phase of development of a workstation-based laboratory is nearing completion. The laboratory has a special layout for teams of programmers to share 18 Sun-based workstations, connected to a network, along with a multimedia Macintosh.
In addition to new hardware, the laboratory has developed special simulation tools for students to learn the practical and theoretical aspects of queueing systems and operating systems. The software is written in a new high-level script language that allows the rapid-prototyping of software, particularly educational software. It is expected that this script language will allow the laboratory to develop new and better software for educational purposes.
Students have been invited into the laboratory to test and examine the new software; it is apparent that students can quickly grasp the essentials of queueing networks using a graphical user interface. Students have begun SCCP, an extra-curricular project involving a set of queueing network experiments. This will prepare the students for future course work and research in both operating systems and performance evaluation.
In research, a set of 13 technical reports have been written that cover autonomous decentralized systems, distributed queueing systems, distributed decision making with delayed information, and adaptive methods. The major themes are stability, adaptation, and group formation under the constraint of delayed information. The general goal of the research in the laboratory is to establish principles that improve the performance of highly distributed systems. A typical approach is to model systems with delay differential equations.
For example, a new research area, Autonomous Decentralized Systems (ADS), has emerged and the goal is to model such systems as queueing networks with a high degree of uncertainty, analyze the behavior of these systems, and provide mechanisms for improved performance. The application is the processing of jobs in a factory environment or a distributed computing system. The systems require adaptability, reliability, and expandability; the solutions are characterized by self-organizing and learning behaviors. The agents, or controllers, in the system make autonomous decisions and are expected to maintain reasonable performance, even as the system operates under aged or misleading information or evolves into unforeseen environments.
Some of the topics covered are the
Some of the specific topics on stability are the
We continue to work on the publication of these results and the formulation of general models of distributed systems. Recently, the laboratory has received notification that two journal papers and seven conference papers have been accepted for publication.
Refereed Journal Papers
We investigate how delayed communication affects the dynamic formation of groups in distributed systems, where all decision-making agents join the same group because each expects to improve its own performance. For example, distributed job schedulers may form a group to utilize the idle resources of other members within the group. Forming a group is a search problem and we examine agents which use the feedback mechanism of stochastic learning automata to carry out this search. Although a group formation may have the potential for synergy, the agents must successfully coordinate their actions within the group relevant to the application. For example, job schedulers who form a group must still balance the load among the shared resources; that is, the collective actions of the schedulers need to be coordinated and greedy schedulers who all pick the same processor may not be successful. Agents may find that working alone is more desirable since their actions need not be coordinated and the results of their own actions are more predictable. An additional challenge to the search problem is to cope with the delay in communication between the agents. The purpose of this study is to model systems where agents adaptively search for compatible co-workers, under the constraint of delayed communication. With insufficient communication, the agents decide to work alone (and receive a modest benefit) but, with sufficient communication, the agents make the more advantageous decision to work together.
In a distributed system, a group of agents have a potential for improved performance depending on their ability to utilize shared resources. This potential synergy raises the question of whether agents should work together in a system-wide group, i.e. a coalition, or whether they should work alone. In general, there is uncertainty as to whether a coalition will form; this uncertainty can arise for various reasons, such as adaptive strategies of the agents or random faults in the system. In this paper, we present a model for performance based upon the probability of coalition formation. The results indicate a limit in potential performance for adaptive agents and, in particular, the global and local maxima along with regions of non-stability. In addition, the model shows how performance is affected by the knowledge environment of the distributed system, that is, the architecture of the system with respect to the distribution of information. Four environments are examined as illustrations of these general categories of information distribution: global information; inaccessible information; local information residing in autonomous agents; and information residing in a master control agent. The results show the distinctions between the environments with respect to probabilistic coalition formation and also demonstrate the loss in environments without communication as compared to a baseline communication environment.
A new model for distributed decision making, distributed game automata, focuses on how communication affects the quality of decisions. The goal is to limit communication between decision makers such that overhead costs are reduced but good decisions still result. Learning automata play repeated games with payoffs quantifying the performance in a distributed application. Each automaton's view of the global state is periodically updated by communication from other automata of their local state (i.e. current strategy probabilities). Because of infrequent communication and transmission delays, received state information may become stale: an example game illustrates the mutually conflicting decisions that can result. Simulation and analytic results show that there exists a maximum communication delay before decision quality begins to suffer, however, with sufficient communication, the agents adapt to a coordinated policy.
Refereed Proceeding Papers
Each job scheduling agent in large decentralized load balancing systems generally must consider whether it is advantageous to offload jobs to remote hosts when the local load is too high. Although processing power may appear to be available at a very distant host, two problems arise due to the transmission delay between the two systems. Predictably, the response time of the job is adversely affected as the job spends valuable time in transit, but a more subtle problem involves the value, or reliability, of the state information regarding job queues. The longer the delay between systems, the less an agent should value the state information of the remote system. We examine the performance of agents in topologies with different proximity (in terms of the average number of hops between hosts) and show that adaptive agents prefer to work with agents in close proximity. That is, the agents prefer localized decision making due to more valuable information and these agents perform better than non-adaptive agents which consider only the delays in job transmission.
Spectral analysis is applied to detect instabilities in load balancing algorithms, both static and dynamic, in a decentralized system. The model is a variation of the Huberman-Hogg model of computational ecosystems, with the addition of queues. Decisions concerning the most efficient resource are based on aged information caused by the physical decentralization of the resources from the users and the methods used for updating state information. We present the data reduction techniques to achieve a good view of the instabilities, along with examples at various delays. The results show the dependency of the period and amplitude of oscillations with respect to the delays. In particular, the static algorithm exhibits a period that is double the delay whereas the dynamic algorithm's period is quadruple the delay.
Each job scheduling agent in large decentralized load balancing systems generally has a set of remote hosts (i.e. its scope of control) to consider for offloading when the local load is too high. Typically, each agent's scope of control includes all the hosts in the system. We investigate the potential performance benefits of limiting the size of each agent's scope of control. The larger the scope of control, the less often state information can be communicated, and old state information can lower the quality of load balancing decisions. The smaller the scope of control, the less opportunity an agent has for finding a lightly loaded host for offloading. Agents adaptively modify their scope of control over time based on feedback regarding the success of load balancing decisions and act as a self-organizing system to efficiently share available processing power.
Distributed decision makers are modeled as players in a game with two levels. High level decisions concern the game environment and determine the willingness of the players to form a coalition (or group). Low level decisions involve the actions to be implemented within the chosen environment. Coalition and action strategies are determined by probability distributions which are updated using learning automata schemes. The payoffs are also probabilistic and there is uncertainty in the state vector since information is delayed. The goal is to reach equilibrium in both levels of decision making; the results show the conditions for instability, based on the age of information.
The Huberman-Hogg model of computational ecosystems is applied to resources with queues. The previous theoretical results indicate that instabilities, due to delayed information, can be controlled by adaptive mechanisms, particularly schemes which employ diverse past horizons. A stochastic learning automaton, with rewards based on queueing parameters, is implemented to test the theoretical results. The effects of the learning step size and horizon are shown for systems with various delays and traffic intensities. Long horizons permit non-adaptive agents to achieve similar results, with the possible loss of responsiveness to dynamic environments.
Technical Reports
Academic Activities
Reviewed papers for IEEE Trans. Comp.
Reviewed papers for IEEE Trans. Syst. Man. Cybern.
Others
Alice Riedmiller.
Edited 12 technical reports in the Operating Systems Laboratory.