Title: Implicit Coscheduling: Coordinated Scheduling with Implicit 
       Information in Distributed Systems 

Speaker: Andrea Arpaci-Dusseau, U.C. Berkeley

Abstract 

Building fault-tolerant, scalable services in a distributed system has
typically involved complex implementations.  We believe that implicit
control can greatly simplify the construction of such services.  In an
implicitly-controlled system, cooperating components do not explicitly
contact other components for control or state information; instead,
components infer remote state by observing naturally-occurring local events
and their corresponding implicit information, i.e., information available
outside of a defined interface.

To concretely demonstrate the advantages of implicit control, we propose
implicit coscheduling, an algorithm for dynamically coordinating the
time-sharing of communicating processes across distributed machines.
Coordinated scheduling, required for communicating processes to leverage
the performance benefits of switch-based networks and low overhead
protocols, has traditionally been achieved with explicit coscheduling;
however, implementations of explicit coscheduling often suffer from
multiple failure points and interact poorly with client-server, interactive, 
and I/O-intensive jobs.  With implicit coscheduling, processes in a
general-purpose workload can coordinate their own scheduling by simply
reacting to implicit information, such as the round-trip time and arrival
rate of messages.

In this talk, we describe the two principle components of implicit
coscheduling: a fair, preemptive operating system scheduler and conditional
two-phase waiting, a generalization of traditional two-phase waiting in which
spin-time is increased depending upon events that occur while the process
waits. We show through both simulation and an implementation on a cluster of 
32 workstations that implicit coscheduling efficiently and fairly handles
competing applications with a wide range of communication characteristics.

For relevant papers and more information, see 
http://now.CS.Berkeley.EDU/Implicit


Biography:

Andrea C. Arpaci-Dusseau received her B.S. in Computer Engineering from
Carnegie Mellon University in 1991, and her M.S. in Computer Science from
University of California, Berkeley in 1994.  As a member of the Network of
Workstations project at U.C. Berkeley, she completed her Ph.D. in 1998 on
implicit coscheduling.  She is currently a postdoctoral researcher at
Stanford University, investigating operating system support for parallel
applications.