Analytical reasoning is central to code correctness, and every computer science curriculum aims to teach students how to achieve this objective in one form or another. With the acceptance of object-based computing and component-based software engineering, the need for analytical reasoning that is based on formal contracts to establish correctness of software across module boundaries has become ever more obvious. Yet there are few institutions that have integrated modular, analytical reasoning principles into their undergraduate curriculum. Among many reasons for this shortcoming are: the effort it takes overloaded faculty to integrate new ideas of any kind in their courses, the challenge of institutionalizing ideas within a specific context, and constraints of a particular college. This paper presents our experiences over nearly two decades at five different institutions with the hope that they will serve as useful curriculum examples for like-minded educators at other institutions.

Abstraction is a critical concept that underlies many topics in computing science. For example, in software engineering, the distinction between a component's behavior and its implementation is fundamental. Java provides two constructs that correspond to precisely this distinction: A Java interface is a client's abstract view of a component's behavior, while a class is a concrete implementation of that same component. We have developed a course that introduces Java while following a discipline of diligently decomposing every component into these two separate linguistic elements. In this course, interfaces are given the same prominence as classes since both are needed for a complete component. This approach is helpful to students by providing: (i) a clear manifestation of the role of abstraction in software systems, and (ii) a framework that naturally motivates many good coding practices adopted by professional programmers.

A strongly fair schedule is one in which tasks that are enabled infinitely often are also executed infinitely often. When tasks execute atomically, a strongly fair scheduler can be implemented in a maximal manner. That is, an algorithm exists that, for any valid schedule, is capable of generating that schedule. We show that this assumption of atomicity is necessary. That is, when task execution can be interleaved with other tasks, no algorithm is capable of generating all valid schedules. In other words, any algorithm that correctly generates some strongly fair schedules must also be incapable of generating some other valid schedules. This impossibility result is the first example of an implementable UNITY specification for which no maximal solution exists.

A common approach for introducing computer science to middle school students is to teach them a simple yet engaging programming language A different approach is to teach them some advanced topic independent of any particular language or syntax We describe a 3-hour workshop module designed to do both This module has been piloted with a group of thirty 8th grade girls. It uses the Scratch programming language to develop the advanced software engineering concepts of specifications, refinement, and composition After this module, students were enthusiastic about continuing to program in Scratch independently and also felt they learned something about computer science as a discipline.

Kinesthetic learning is a process in which students learn by actively carrying out physical activities rather than by passively listening to lectures. Pedagogical research indicates that kinesthetic learning is a fundamental, powerful, and ubiquitous learning style. To date, efforts to incorporate this learning style within the computer science curriculum have focussed on introductory courses. Material in upper-level courses, however, can also benefit from a similar approach. In particular, courses on distributed computing, by the very nature of the material they cover, are uniquely suited to exploiting this learning technique. We have developed and piloted a collection of kinesthetic activities for a senior undergraduate or graduate-level course on distributed systems. We give detailed descriptions of these exercises and discuss factors that contribute to their success.

Ideally, distributed algorithms isolate the side-effects of faults within local neighborhoods of impact. Failure locality quantifies this concept as the maximum radius of impact caused by a given fault. We present new locality results for the dining philosophers problem subject to crash failures. The optimal crash locality for dining is 0 in synchronous networks, but degrades to 2 in asynchronous networks. Using the eventually-perfect failure detector /spl diams/P , we construct the first known dining algorithms with crash locality 1 under partial synchrony. These algorithms close the failure-locality complexity gap and improve the crash tolerance of resource allocation algorithms in practical networks. We prove the optimality of our results with two fundamental theorems. First, no dining solution using /spl diams/P achieves locality 0. Second, /spl diams/P is the weakest failure detector in the Chandra-Toueg hierarchy to realize locality 1.

Rarely are the three pillars of academia---research, teaching, and service---addressed together, within one intellectually cohesive context in the graduate curriculum. Such a context is important for exposing students to the inter-relationships among these facets.This paper presents our experience with structuring graduate research seminar courses around the model of a "miniconference". Throughout the quarter, students pursue original research projects in the discipline of the seminar course. At the end of the quarter, students write their findings as technical conference papers, then act as the miniconference program committee in reviewing each other's submissions. Finally, the selected papers are presented at the miniconference. In addition to the model itself, we describe some variations in instantiation and an assessment of the benefits of this general approach.

Knowledge has proven to be a useful and fundamental formalism for reasoning about distributed systems. The application of this formalism, however entails a loss of volition on the part of processes about which something is known. This loss of volition is often not appropriate in loosely coupled distributed systems. In this paper we generalize the formal characterization of knowledge into one of belief. Belief has the advantage of allowing processes to maintain volition. We examine some of the similarities and surprising differences between knowledge and belief. We also present some examples of distributed applications that are more conveniently characterized with belief rather than knowledge.

During summer 2002, we ran a workshop module for a group of 28 eighth-grade girls. Our aim was ambitious: to introduce these students, ages 12 and 13, to computer science by focussing on the deep intellectual topic of self-stabilizing distributed algorithms and by imparting an intuitive appreciation for their use in fault tolerance. At the same time, we hoped to dispel some negative stereotypes of computer science. The module was a success according to evaluations and comments from the participants. This paper describes the sequence of exercises we developed as an elementary-level introduction to the graduate-level topics of fault tolerance and self-stabilization. We report them with the hope that others will try them in college classrooms, as we plan to do.

There are two basic parts to the behavioral specification of distributed systems: safety and progress. In earlier work, we developed a tool to monitor progress properties of CORBA components specified using the temporal operator transient. In this paper, we address the specification and testing of transient properties that are quantified (over both bounded and unbounded domains). We categorize typical quantifications that arise in practical systems and discuss possible implementation strategies. We define functional transients, a subclass of quantified transient properties that can be monitored in constant space and time. We outline the design and implementation of a tool for testing these properties in CORBA components.

When a client makes use of a remote component, it does not have direct access to the remote component's implementation or state information. By observing the component's interactions with its environment, however, the client can determine whether the component's behavior conforms to its promised specification. We present a distributedinfrastructure with which a client can make these observations and thereby increase its confidence in the correctness of the remote component. This infrastructure supports temporal specifications of distributed components with autonomous threads of control. It also supports multiple levels of confidence, with commensurate performance costs. As a proof-of-concept for this design, we have implemented a prototype in Java for distributed systems built using CORBA.

This paper describes the design of a distributed system built using Java that supports peer-to-peer communication among processes spread across a network. We identify the requirements of a software layer that supports distributed computing, and we propose a design that meets those requirements. Our primary concerns are (I) the identification, specification, and implementation of software components that can be composed in different ways to develop correct distributed applications; (2) reasoning about the components systematically; and (3) providing services to the components. This paper deals with the last of these concerns. Though our implementation uses Java, the fundamental ideas apply to any object-oriented language that supports messaging and threads. Alternative implementations use such languages coupled with object request brokers or remote procedure invocation mechanisms.