DATE: Thursday, June 7, 2001
TIME: 12:30 pm - 6:30 pm
PLACE: Roberts Hall, Singleton Room


Digital video of each of the presentations is now available at The CMU Universal Digital Library.

SPEAKER: Hari Balakrishnan, MIT Lab for Computer Science
The Cricket Indoor Location System
Context-aware applications, which are able to adapt their behavior and human interface to their external environmental context such as their physical location, are an important class of applications in emerging pervasive computing environments. I will describe Cricket, a system that provides applications (and users) with location information, and exports a convenient API for location-aware applications. Cricket uses active ceiling- or wall-mounted beacons and passive listeners attached to devices, and provides different forms of location information to applications, including (i) logical spaces, such as which side of a room the device is in, (ii) the physical coordinates of the device in some coordinate system (e.g., GPS), and (iii) the orientation ("heading") of the device with respect to some coordinate system. This combination of features makes Cricket unique, and it works well inside buildings; as a result, it enables a variety of applications from speech-driven active maps, to directional viewfinders, to navigation aids for blind (and sighted) people. I will discuss how Cricket's hardware and software work, how well the system works, and talk about its API and how it eases application development.

BIO: Hari Balakrishnan is the KDD Career Development Assistant Professor of Communications Technology in the Department of Electrical Engineering and Computer Science and a member of the Laboratory for Computer Science (LCS) at MIT. He leads the Networks and Mobile Systems group at LCS, which explores research issues in wireless and mobile systems and computer networks. His current research interests are in pervasive context-aware networking and in developing robust infrastructures for the future Internet.

SPEAKER: Maurice Herlihy, Brown University
A Tale of Two Directories: Implementing Distributed Shared
Objects in Java

A directory service keep tracks of the location and status of mobile objects in a distributed system. This paper describes our experience implementing two distributed directory protocols as part of the Aleph toolkit, a distributed shared object system implemented in Java. One protocol is a conventional home-based protocol, in which a fixed node keeps track of the object's location and status. The other is a novel arrow protocol, based on a simple path-reversal algorithm. We were surprised to discover that the arrow protocol outperformed the home protocol, sometimes substantially, across a range of system sizes. This talk describes a series of experiments testing whether the discrepancy is due to an artifact of the Java run-time system (such as differences in thread management or object serialization costs), or whether it is something inherent in the protocols themselves.

BIO:Maurice Herlihy is interested in practical and theoretical aspects of distributed computing. He has an A.B. in Mathematics from Harvard and a Ph.D. degree in Computer Science from M.I.T. He has been a faculty member at the CMU Computer Science department and a member of research staff at Digital Equipment Corporation's Cambridge Research Lab. In 1994, he joined the faculty at the Brown University Computer Science Department.

SPEAKER: Mike Jones, Microsoft Research
Predictability Requirements of a Soft Modem
Soft Modems use the main processor to execute modem functions traditionally performed by hardware on the modem card. To function correctly, soft modems require that ongoing signal processing computations be performed on the host CPU in a timely manner. Thus, signal processing is a commonly occurring background real-time application - one running on systems that were not designed to support predictable real-time execution. This paper presents a detailed study of the performance characteristics and resource requirements of a popular soft modem. Understanding these requirements should inform the efforts of those designing and building operating systems needing to support soft modems. Furthermore, we believe that the conclusions of this study also apply to other existing and upcoming soft devices, such as soft Digital Subscriber Line (DSL) cards. We conclude that (1) signal processing in an interrupt handler is not only unnecessary but also detrimental to the predictability of other computations in the system and (2) a real-time scheduler can provide predictability for the soft modem while minimizing its impact on other computations in the system.

BIO: Michael B. Jones is a member of the Systems and Networking Research Group at Microsoft Research. At Microsoft he has worked on Consumer Real-Time systems, the Rialto real-time operating system kernel, the Rialto/NT system, and the Tiger video fileserver. The goal of the consumer real-time research, of which the Rialto and Rialto/NT systems are part, is enabling independently developed real-time applications to successfully and predictably co-exist, both with each other and with non-real-time applications. He recently helped start the Herald project, whose goal is to build a publish/subscribe event notification service deployed as a self-configuring federation of peers designed to scale to Internet size and to provide timely delivery of notifications. He organized and co-chaired the first USENIX Windows NT Workshop. He co-chaired the Fourth USENIX Symposium on Operating Systems Design and Implementation (OSDI 2000). He is a member of the USENIX Association board of directors. Michael earned his Ph.D. in Computer Science from Carnegie Mellon University in 1992, where he was a member of the Mach project. He was a technical reviewer for the POSIX threads standards effort. His interests include operating systems, adaptive real-time systems, parallel and distributed systems, networking, musical performance, outdoor activities, and his fellow human beings.

SPEAKER: Jochen Liedtke, University of Karlsruhe, Germany
L4Ka - Vision, Pitfalls, and Status Quo
Microkernels are minimal but highly flexible kernels. Both conventional and non-classical operating systems can be built on top or adapted to run on top of them. Microkernel-based architectures should particularly support extensibility and customizability, robustness including reliability and fault tolerance, protection and security. After desastrous results in the early 90's, the microkernel approach now seems to be promising, although it still bears a lot of research risks. The LKa research project aims at substantiating and establishing a methodology for system construction that helps to manage ever-increasing OS complexity and minimizes legacy dependence. Our vision is a microkernel technology that can be and is used advantageously for constructing any general or customized operating system including pervasive systems, deep-computing systems, and huge servers. The talk not only describes the fundamental vision but also discusses in depth the currently known open problems (many of them are related to real time) and analyzes the surprises and pitfalls we experienced so far.

SPEAKER: Andrew Myers, Cornell University
Enforcing Confidentiality in Low-Level Programs
Protecting confidential data is a thorny problem for computer security: standard security mechanisms are either inadequate or impractically restrictive. A promising approach is to use static program analysis to enforce information flow properties; however, previous work in this area has at least two of the following three weaknesses:
- No proof that information is controlled
- No support for imperative programming with higher-order functions
- Not applicable to low-level code
I will present an expressive, low-level language that provably provides information flow security. A key innovation is the use of ordered linear continuations as the fundamental control construct. Source-level control constructs (if, while, exceptions) can be translated into this construct without increasing restrictiveness, thus permitting security verification after compiling a secure source language.

BIO: Andrew Myers received his Ph.D. in Computer Science from MIT in 1999. He is currently an Assistant Professor at Cornell University. His research interests are in computer security, programming language design and implementation, and distributed and persistent object systems.

SPEAKER: Brian Noble, University of Michigan
Mobile Network Estimation
Mobile systems must adapt their behavior to changing network conditions. To do this, they must accurately estimate available network capacity. Producing quality estimates is challenging, because network observations are noisy - particularly in mobile, ad hoc networks. Current systems estimate network capacity through simple, exponentially weighted moving average (EWMA) filters. These filters are either able to detect true changes quickly or to mask observed noise and transients, but cannot do both. In this talk, we present a set of filters designed to react quickly to persistent changes while tolerating transient noise. Such filters are designed to be agile when possible, but stable when necessary, adapting their behavior to prevailing conditions. We evaluate these filters in a variety of networking conditions, including persistent and transient change, congestion, and topology changes. We find that one filter, based on techniques from statistical process control, provides performance superior to the other three. Compared to two EWMA filters, one agile and the other stable, it is able to offer the agility of the former in four of five scenarios and the stability of the latter in three of four scenarios.

BIO: Brian Noble is an Assistant Professor of Electrical Engineering and Computer Science at the University of Michigan. His research centers on software supporting mobile computing systems and their users. He received the Ph.D. in Computer Science from Carnegie Mellon University in 1998, where he worked on the Odyssey and Coda projects.

For Further Seminar Info: