Structured peer-to-peer overlay networks such as CAN, Chord, Pastry, and Tapestry can be used to implement Internet-scale application-level multicast. There are two general approaches to accomplishing this: tree building and flooding. This paper evaluates these two approaches using two different types of structured overlay: 1) overlays which use a form of generalized hypercube routing, e.g., Chord, Pastry and Tapestry, and 2) overlays which use a numerical distance metric to route through a Cartesian hyperspace, e.g., CAN. Pastry and CAN are chosen as the representatives of each type of overlay. To the best of our knowledge, this paper reports the first head-to-head comparison of CAN-style versus Pastry-style overlay networks, using multicast communication workloads running on an identical simulation infrastructure. The two approaches to multicast are independent of overlay network choice, and we provide a comparison of flooding versus tree-based multicast on both overlays. Results show that the tree-based approach consistently outperforms the flooding approach. Finally, for tree-based multicast, we show that Pastry provides better performance than CAN.

This paper indicates that a scalable fault-tolerant name service can be provided utilizing an overlay network and that such a name service can scale along a number of dimensions: it can be sized to support a large number of clients, it can allow large numbers of concurrent lookups on the same name or sets of names, and it can provide name lookup latencies measured in seconds. Furthermore, it can enable updates to be made pervasively visible in times typically measured in seconds for update rates of up to hundreds per second. We explain how many of these scaling properties for the name service are obtained by reusing some of the same mechanisms that allowed the underlying overlay network to scale. Finally, we observe that the overlay network is sensitive to bandwidth and CPU limitations.

This paper presents the design philosophy and initial design decisions of Herald: a highly scalable global event notification system that is being designed and built at Microsoft Research. Herald is a distributed system designed to transparently scale in all respects, including numbers of subscribers and publishers, numbers of event subscription points, and event delivery rates. Event delivery can occur within a single machine, within a local network or Intranet, and throughout the Internet. Herald tries to take into account the lessons learned from the successes of both the Internet and the Web. Most notably, Herald is being designed, like the Internet, to operate correctly in the presence of numerous broken and disconnected components. The Herald service will be constructed as a set of protocols governing a federation of machines within cooperating but mutually suspicious domains of trust. Like the Web, Herald will try to avoid, to the extent possible, the maintenance of globally consistent state and will make failures part of the client-visible interface.

Workstations and personal computers are increasingly being used for applications with real-time characteristics such as speech understanding and synthesis, media computations and I/O. and animation, often concurrently executed with traditional nonreal-time workloads.This paper presents a system that can schedule multiple independent activities so that: activities can obta& minimum guaranteed execution rates with application-specified reservation granularities via CPU Reservations, CPU Reservations, which are of the form "reserve X units of time out of every Y units", provide not just an average case execution rate of X/Y over long periods of time, but the stronger guarantee that from any instant of time, by Y time units later, the activity will have executedfor at least X time units, applications can use Time Constraints to schedule tasks by deadlines, with on-time completion guaranteed for tasks with accepted constraints, and both CPU Reservations and Time Constraints are implemented very efficiently.In particular, CPU scheduling overhead is bounded by a constant and is not a function of the number of schedulable tasks.Other key scheduler properties are: l activities cannot violate other activities' guarantees, l time constraints and CPU reservations may be used together, separately, or not at all (which gives a round-robin schedule), with well-defined interactions between all combinations, and l spare CPU time is fairly shared among all activities.The Rialto operating system, developed at Microsoft Research, achieves these goals by using a precomputed schedule, which is the fundamental basis of this work.

This paper describes ongoing investigations into algorithms for modular distributed real-time resource management. These investigations are being conducted in the context of the Rialto operating system-an object-based real-time kernel and programming environment currently being developed within Microsoft Research. Some of the goals of this research include developing appropriate real-time programming abstractions to allow multiple independent real-time programs to dynamically coexist and share resources on the same hardware platforms. Use of these abstractions is intended both to allow individual applications to reason about their own resource requirements and for per-machine system resource planner applications to reason about and control resource allocations between potentially competing applications. The set of resources being managed is dynamically extensible, and may include remote resources in distributed environments. The local planner conducts resource negotiations with individual applications on behalf of the user, with the goal of maximizing the user's perceived utility of the set of running applications with respect to resource allocations for those applications.

Summary form only given, as follows. Static models are not appropriate for next-generation distributed real-time applications that are likely to be adaptive in nature, (for example, to provide a high degree of fault tolerance). During the last few years, the real-time systems community has started to counter this criticism by extending traditional work to cover newer application domains, The central problem remains, however, that the concept of adaptivity is often domain-specific and sometimes ill-defined in the context of bringing distributed real-time systems concept into better focus. Accordingly, be it resolved that future distributed embedded and real-time applications will be adaptive and that meanings, challenges and research paradigms await discovery. The charge to the panel is to defend (or to dismiss as fluff) the above resolution.

Many contemporary operating systems utilize a system call interface between the operating system and its clients. Increasing numbers of systems are providing low-level mechanisms for intercepting and handling system calls in user code. Nonetheless, they typically provide no higher-level tools or abstractions for effectively utilizing these mechanisms. Using them has typically required reimplementation of a substantial portion of the system interface from scratch, making the use of such facilities unwieldy at best.This paper presents a toolkit that substantially increases the ease of interposing user code between clients and instances of the system interface by allowing such code to be written in terms of the high-level objects provided by this interface, rather than in terms of the intercepted system calls themselves. This toolkit helps enable new interposition agents to be written, many of which would not otherwise have been attempted.This toolkit has also been used to construct several agents including: system call tracing tools, file reference tracing tools, and customizable filesystem views. Examples of other agents that could be built include: protected environments for running untrusted binaries, logical devices implemented entirely in user space, transparent data compression and/or encryption agents, transactional software environments, and emulators for other operating system environments.

Mach, a multiprocessor operating system kernel providing capability-based interprocess communication, and Matchmaker, a language for specifying and automating the generation of multi-lingual interprocess communication interfaces, are presented. Their usage together providing a heterogeneous, distributed, object-oriented programming environment is described. Performance and usage statistics are presented. Comparisons are made between the Mach/Matchmaker environment and other related systems. Possible future directions are examined.

Matchmaker, a language used to specify and automate the generation of interprocess communication interfaces, is presented. The process of and reasons for the evolution of Matchmaker are described. Performance and usage statistics are presented. Comparisons are made between Matchmaker and other related systems. Possible future directions are examined.