Next: Computer Networks Laboratory Up: Department of Computer Previous: Distributed Parallel Processing

Operating Systems Laboratory

/ 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 final phase of development of a workstation-based laboratory has been completed. The laboratory has a special layout for programmers to share 19 Sun-based workstations and 4 X terminals, connected to the laboratory file server via a network. In addition, a multi-media Macintosh has a scanner, video camera, video recorder, and television monitor.

An office for students has been built next to the laboratory for lab assistants, lab members, and visiting students. The lab assistants are exceptional students who help with lab software and exercises; the lab members are students who have made significant progress on their projects; and the visiting students are from other laboratories who are doing temporary work in the Operating Systems Lab. The students use the office to work on special projects for the laboratory and for general homework. Some of these students acted as teaching assistants for the Operating Systems course. They have been trained on special new software, developed in the lab, that demonstrates concurrent programming - an important aspect of the course.

In addition to concurrent programming, the laboratory has developed special simulation tools for students to learn the practical and theoretical aspects of queueing systems. The software is written in a new high-level script language (Tcl/Tk) that allows the rapid-prototyping of software, particularly educational software. The software has been used in the Performance Evaluation course and another tool has been used in the Database course.

Students in SCCP 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, operating systems, databases, automata, sorting, and graph theory. The advanced students design their own queueing experiments and/or write their own graphical user interfaces.

Three seniors are doing their Graduation Research in the laboratory - the topic is Distributed Minimum-Weight Spanning Tree. This is much more difficult than a centralized version and involves the exchange of nine different message types.

The students are implementing the distributed algorithm in C and need to be concerned with message encoding and the requeueing of messages. In addition, each student is researching special areas including 1) Tcl/Tk to build a GUI for the MST, 2) networked messages, and 3) experiments on message complexity.

In research, two new refereed journal articles have been accepted for publication this year (and four previously accepted journal articles appeared this year). The members of the lab also had an interesting paper in ACM Software Engineering Notes on the use of Tcl/Tk for managing lightweight processes.

The major themes of the research 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. 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

  1. value of localized decision making in decentralized control;

  2. sharing of global resources among autonomous agents;

  3. use of randomization in load balancing queueing systems;

    and some of the specific topics on stability are the

  1. stability of dynamic groups in distributed systems;

  2. stability of computational ecosystems with queues and learning automata;

  3. stability of goal-directed versus response-directed algorithms;

  4. stability of adaptive methods in hierarchical game structures;

  5. stability of a prisoner's dilemma with delayed information;

  6. stability of database transaction processing.

Refereed Journal Papers

  1. E. Billard. Stabilizing distributed queueing systems using feedback based on diversity. accepted, IEEE Trans. Systems, Man, Cybernetics, 1996.

    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. The instabilities are controlled with appropriate choices of parameters and reward mechanism. Long horizons permit non-adaptive agents to achieve similar results, with the possible loss of responsiveness to dynamic environments.

  2. E. Billard. Evolutionary strategies of stochastic learning automata in the prisoner's dilemma. BioSystems, accepted, 1995.

    Stochastic learning automata ( SLA) model stimulus-response species which receive feedback from the environment and adjust their mixed strategies in a Prisoner's Dilemma. A large heterogeneous population consists of {\em SLA} applying different strategies (i.e., different learning parameters) and other players applying deterministic strategies, Tit-For-Tat ( TFT) or Always-Defect ( ALLD). The predicted equilibria determine the payoffs within a generation for applying particular strategies and these equilibria are confirmed by simulation. The resultant population dynamics over many generations show that {\em SLA} with insensitive penalty responses strongly favor defection and dominate in subsequent generations over SLA with sensitive penalty responses. The SLA strategies are not evolutionarily stable as they can be invaded by TFT or ALLD. With the introduction of memory in the stimulus-response model, SLA learn to cooperate with TFT players.

Refereed Proceeding Papers

  1. E. Billard. A fluid model of shortest queue routing: Delayed feedback and inherent periodicity. In IEEE Conference on Decision and Control, 1996.

    A controller selects the shortest queue for data entering a network, however, the state of the queues is subject to a delay $\tau$. A fluid-flow model approximates the packet arrivals, with analysis and simulation showing the inherent periodicity of peak loads. A formula for periodicity is derived for $r$ channels with utilization $\rho$ and is approximated by $\rho r\tau$ for a large number of channels.

Unrefereed Papers

  1. E. Billard and A. Riedmiller. A GUI for a manager of lightweight processes. In ACM Software Engineering Notes, number 5, pages 48--50, 1995.

Technical Reports

  1. Edward A. Billard. Dynamics of distributed transaction processing: Load sharing versus locality preference. Technical Report, 95-1-003, February 2, 16pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

Next: Computer Networks Laboratory Up: Department of Computer Previous: Distributed Parallel Processing
October 1996