bluuebunny/crossref_metadata_2025 huggingface dataset:
Spritely NFS: experiments with cache-consistency protocols
Authors: Srinivasan V. , Mogul J.
Published: October 2004

File caching is essential to good performance in a distributed system, especially as processor speeds and memory sizes continue to improve rapidly while disk latencies do not. Stateless-server systems, such as NFS, cannot properly manage client file caches. Stateful systems, such as Sprite, can use explicit cache consistency protocols to improve both cache consistency and overall performance.

By modifying NFS to use the Sprite cache consistency protocols, we isolate the effects of the consistency mechanism from the other features of Sprite. We find dramatic improvements on some, although not all, benchmarks, suggesting that an explicit cache consistency protocol is necessary for both correctness and good performance.
RPC in the x-Kernel: evaluating new design techniques
Authors: Peterson L. , Hutchinson N. , O'Malley S. , Abbott M.
Published: October 2004

This paper reports our experiences implementing remote procedure call (RPC) protocols in the
x
-kernel. This exercise is interesting because the RPC protocols exploit two novel design techniques:
virtual protocols
and
layered protocols
. These techniques are made possible because the
x
-kernel provides an object-oriented infrastructure that supports three significant features: a uniform interface to all protocols, a late binding between protocol layers, and a small overhead for invoking any given protocol layer. For each design technique, the paper motivates the technique with a concrete example, describes how it is applied to the implementation of RPC protocols, and presents the results of experiments designed to evaluate the technique.
Lightweight remote procedure call
Authors: Bershad B. , Anderson T. , Lazowska E. , Levy H.
Published: October 2004

Lightweight Remote Procedure Call (LRPC) is a communication facility designed and optimized for communication between protection domains on the same machine.

In contemporary small-kernel operating systems, existing RPC systems incur an unnecessarily high cost when used for the type of communication that predominates — between protection domains on the same machine. This cost leads system designers to coalesce weakly-related subsystems into the same protection domain, trading safety for performance. By reducing the overhead of same-machine communication, LRPC encourages both safety and performance.

LRPC combines the control transfer and communication model of capability systems with the programming semantics and large-grained protection model of RPC. LRPC achieves a factor of three performance improvement over more traditional approaches based on independent threads exchanging messages, reducing the cost of same-machine communication to nearly the lower bound imposed by conventional hardware.

LRPC has been integrated into the Taos operating system of the DEC SRC Firefly multiprocessor workstation.
Generic virtual memory management for operating system kernels
Authors: Abrossimov E. , Rozier M. , Shapiro M.
Published: October 2004

We discuss the rationale and design of a Generic Memory management Interface, for a family of scalable operating systems. It consists of a general interface for managing virtual memory, independently of the underlying hardware architecture (e.g. paged versus segmented memory), and independently of the operating system kernel in which it is to be integrated. In particular, this interface provides abstractions for support of a single, consistent cache for both mapped objects and explicit I/O, and control of data caching in real memory. Data management policies are delegated to external managers.

A portable implementation of the Generic Memory management Interface for paged architectures, the Paged Virtual Memory manager, is detailed. The PVM uses the novel history object technique for efficient deferred copying. The GMI is used by the Chorus Nucleus, in particular to support a distributed version of Unix. Performance measurements compare favorably with other systems.
Low-synchronization translation lookaside buffer consistency in large-scale shared-memory multiprocessors
Authors: Rosenburg B.
Published: October 2004

Operating systems for most current shared-memory multiprocessors must maintain translation lookaside buffer (TLB) consistency across processors. A processor that changes a shared page table must flush outdated mapping information from its own TLB, and it must force the other processors using the page table to do so as well. Published algorithms for maintaining TLB consistency on some popular commercial multiprocessors incur excessively high synchronization costs. We present an efficient TLB consistency algorithm that can be implemented on multiprocessors that include a small set of reasonable architectural features. This algorithm has been incorporated in a version of the MACH operating system developed for the IBM Research Parallel Processor Prototype (RP3).
Process control and scheduling issues for multiprogrammed shared-memory multiprocessors
Authors: Tucker A. , Gupta A.
Published: October 2004

Shared-memory multiprocessors are frequently used in a time-sharing style with multiple parallel applications executing at the same time. In such an environment, where the machine load is continuously varying, the question arises of how an application should maximize its performance while being fair to other users of the system. In this paper, we address this issue. We first show that if the number of runnable processes belonging to a parallel application significantly exceeds the effective number of physical processors executing it, its performance can be significantly degraded. We then propose a way of controlling the number of runnable processes associated with an application dynamically, to ensure good performance. The optimal number of runnable processes for each application is determined by a centralized server, and applications dynamically suspend or resume processes in order to match that number. A preliminary implementation of the proposed scheme is now running on the Encore Multimax and we show how it helps improve the performance of several applications. In some cases the improvement is more than a factor of two. We also discuss implications of the proposed scheme for multiprocessor schedulers, and how the scheme should interface with parallel programming languages.
Leases: an efficient fault-tolerant mechanism for distributed file cache consistency
Authors: Gray C. , Cheriton D.
Published: October 2004

Caching introduces the overhead and complexity of ensuring consistency, reducing some of its performance benefits. In a distributed system, caching must deal with the additional complications of communication and host failures.

Leases
are proposed as a time-based mechanism that provides efficient consistent access to cached data in distributed systems. Non-Byzantine failures affect performance, not correctness, with their effect minimized by short leases. An analytic model and an evaluation for file access in the V system show that leases of short duration provide good performance. The impact of leases on performance grows more significant in systems of larger scale and higher processor performance.
The revised ARPANET routing metric
Authors: Khanna A. , Zinky J.
Published: October 2004

The ARPANET routing metric was revised in July 1987, resulting in substantial performance improvements, especially in terms of user delay and effective network capacity. These revisions only affect the individual link costs (or metrics) on which the PSN (packet switching node) bases its routing decisions. They do not affect the SPF (“shortest path first”) algorithm employed to compute routes (installed in May 1979). The previous link metric was packet delay averaged over a ten second interval, which performed effectively under light-to-moderate traffic conditions. However, in heavily loaded networks it led to routing instabilities and wasted link and processor bandwidth.

The revised metric constitutes a move away from the strict delay metric: it acts similar to a delay-based metric under lightly loads and to a capacity-based metric under heavy loads. It will not always result in shortest-delay paths. Since the delay metric produced shortest-delay paths only under conditions of light loading, the revised metric involves giving up the guarantee of shortest-delay paths under light traffic conditions for the sake of vastly improved performance under heavy traffic conditions.
Sirpent: a high-performance internetworking approach
Authors: Cheriton D. R.
Published: October 2004

A clear target for computer communication technology is to support a high-performance global internetwork. Current internetworking approaches use either concatenated virtual circuits, as in X.75, or a “universal” internetwork datagram, as in the DoD Internet IP protocol and the ISO connectionless network protocol (CLNP). Both approaches have significant disadvantages.

This paper describes Sirpent™ (Source Internetwork Routing Protocol with Extended Network Transfer)
1
, a new approach to an internetwork architecture that makes source routing the basis for interconnection, rather than an option as in IP. Its benefits include simple switching with low per-packet processing and delay, support for accounting and congestion control, and scalability to a global internetwork. It also supports flexible, user-controlled routing such as required for security, policy-based routing and realtime applications. We also propose a specific internetwork protocol, called VIPER™
2
, as a realization of the Sirpent approach.
Flexible aggregation of channel bandwidth in primary rate ISDN
Authors: Burren J. W.
Published: October 2004

This paper describes an algorithm that allows a number of 64 Kbps ISDN circuits running between the same pair of subscribers to be aggregated into a single wideband circuit. The algorithm permits flexible aggregation in the sense that the bandwidth of the wideband circuit may be changed by the addition or removal of 64 Kbps circuits without disturbing the flow of data on the wideband channel. The paper also describes an implementation of this algorithm in an apparatus that interfaces a LAN to a primary rate ISDN interface. This interface is built using an array of transputers, and can achieve high utilization of the bandwidth available on the primary rate channel.
Dynamic bandwidth management of primary rate ISDN to support ATM access
Authors: Harita B. R. , Leslie I. M.
Published: October 2004

One of the principle advantages of Asynchronous Transfer Mode (ATM) access is that variable rate streams can be supported efficiently. In order to preserve this efficiency when using ATM on an underlying circuit switched network, such as primary rate ISDN, flexible control of the underlying circuit bandwidth must be provided. This paper discusses techniques used to provide dynamic management of variable rate circuits to support ATM access. Models are presented for some of these control schemes and their performance is studied through a combination of simulation and analysis. Techniques implemented for an experimental network providing ATM access on primary rate ISDN are presented.
A loop-free extended Bellman-Ford routing protocol without bouncing effect
Authors: Cheng C. , Riley R. , Kumar S. P. R. , Garcia-Luna-Aceves J. J.
Published: October 2004

Distributed algorithms for shortest-path problems are important in the context of routing in computer communication networks. We present a protocol that maintains the shortest-path routes in a dynamic topology, that is, in an environment where links and nodes can fail and recover at arbitrary times. The novelty of this protocol is that it avoids the bouncing effect and the looping problem that occur in the previous approaches of the distributed implementation of Bellman-Ford algorithm. The bouncing effect refers to the very long duration for convergence when failures happen or weights increase, and the nonterminating exchanges of messages, or counting-to-infinity behavior, in disconnected components of the network resulting from failures. The looping problems cause data packets to circulate and, thus, waste bandwidth. These undesirable effects are avoided without any increase in the overall message complexity of previous approaches required in the connected part of the network. The time complexity is better than the distributed Bellman-Ford algorithm encountering failures. The key idea in the implementation is to maintain only loop-free paths, and search for the shortest path only from this set.
Internet routing
Authors: Narten T.
Published: October 2004

Comprising an estimated 60,000 hosts, the DARPA Internet is the largest existing internet. This paper traces the routing information protocols used by Internet gateways to build routing tables that define the paths datagrams traverse as they travel between end systems. We articulate the weaknesses and limitations of the most commonly used routing protocols, including RIP, GGP, and HELLO and examine how the protocols interact with each other and with EGP. Finally, we trace the evolution of routing as the Internet has grown from a single backbone (ARPANET) to its present inclusion of the ARPANET, Milnet, and NSFnet cross-country networks.
Probabilistic testing of protocols
Authors: Sidhu D. P. , Chang C.-S.
Published: October 2004

Test sequences are used for the conformance testing of communication protocols to standards. This paper discusses a new approach to generating test sequences. The approach is based on probabilistic concepts about protocol state transitions and communication channels. The novel feature of the test sequences generated by this technique is that the most probable states of a protocol will be tested more promptly.
The LOCUS distributed operating system
Authors: Walker Bruce , Popek Gerald , English Robert , Kline Charles , Thiel Greg
Published: October 2004

LOCUS is a distributed operating system which supports transparent access to data through a network wide filesystem, permits automatic replication of storage, supports transparent distributed process execution, supplies a number of high reliability functions such as nested transactions, and is upward compatible with Unix. Partitioned operation of subnet's and their dynamic merge is also supported.

The system has been operational for about two years at UCLA and extensive experience in its use has been obtained. The complete system architecture is outlined in this paper, and that experience is summarized.
Experience with Grapevine (Summary)
Authors: Schroeder Michael D. , Birrell Andrew D. , Needham Roger M.
Published: October 2004

Grapevine is a distributed, replicated system that provides message delivery, naming, authentication, resource location, and access control services in an internet of computers. The system, described in a previous paper [1], was designed and implemented several years ago. We now have had operational experience with the system under substantial load. This experience has proved the original design sound in most aspects, but there also have been some surprises. In this paper we report what we have learned from using Grapevine. Our experience may offer some help to designers of new systems.

Grapevine is implemented as a program that is run on a set of dedicated server computers. Client programs o f Grapevine run on various workstation and server computers attached to an internet. The services provided by Grapevine are divided into the message service and the registration service.

The message service accepts messages prepared by clients for delivery to individual recipients and distribution lists. Messages are buffered in inboxes on message servers until the recipient requests them. Any message server can accept any message for delivery, thus providing a replicated submission service. A computer system mall user has inboxes on at least two message servers, thus replicating the delivery path for the user.
ATM
Authors: Crowcroft Jon , McAuley Derek
Published: October 2004

The following four papers were selected from submissions for a proposed workshop that was to have been held during the 2002 ACM SIGCOMM Conference. Due to time, we cancelled the event, but the papers capture some of the past, present and future lessons to be gleaned from the whole ATM experience, and we felt that these lessons should be provided with a forum.
From protocol stack to protocol heap
Authors: Braden Robert , Faber Ted , Handley Mark
Published: October 2004

Questioning whether layering is still an adequate foundation for networking architectures, this paper investigates non-layered approaches to the design and implementation of network protocols. The goals are greater flexibility and control with fewer feature interaction problems. The paper further proposes a specific non-layered paradigm called
role-based architecture
.
Transience of peers & streaming media
Authors: Bawa Mayank , Deshpande Hrishikesh , Garcia-Molina Hector
Published: October 2004

Application level multicast schemes have traditionally been evaluated with respect to the
efficiency penalties
incurred in migrating the multicast functionality from the network layer to the application layer. We argue that the current performance measures, and therefore design strategies, are
incomplete
as they do not consider transience of peers. The routers in application level multicast systems are participant clients, and not infrastructure units. As such, the assumptions on the behavior of these application routers are significantly different from the infrastructure routing units that traditional research has dealt with, especially in a peer-to-peer setting where peers are multi-use and the management is decentralized. we argue that the transience in peer behavior has
implications on end-performance enabled
. We outline a design philosophy that seeks to
separate
policy decisions in handling peer behavior from the end-application at a basic infrastructural
peering layer.
As a proof of concept, we have implemented a peering layer prototype, which is available for download.
Current issues in packet switch design
Authors: Minkenberg Cyriel , Luijten Ronald P. , Abel François , Denzel Wolfgang , Gusat Mitchell
Published: October 2004

Addressing the ever growing capacity demand for packet switches, current research focuses on scheduling algorithms or buffer bandwidth reductions. Although these topics remain relevant, our position is that the primary design focus for systems beyond 1 Tb/s must be shifted to aspects resulting from packaging disruptions. Based on trends such as increased link rates and improved CMOS technologies, we derive new design factors for such switch fabrics. For instance, we argue that the packet round-trip transmission time
within
the fabric has become a major design parameter. Furthermore, we observe that high-speed fabrics have become extremely dependent on serial I/O technology that is both high speed
and
high density. Finally, we conclude that in developing the architecture, packaging constraints must be put first and not as an afterthought, which also applies to solving the tremendous power consumption challenges.
Routing on a curve
Authors: Nath Badri , Niculescu Dragoş
Published: October 2004

Relentless progress in hardware technology and recent advances in sensor technology, and wireless networking have made it feasible to deploy large scale, dense ad-hoc networks. These networks together with sensor technology can be considered as the enablers of emerging models of computing such as embedded computing, ubiquitous computing, or pervasive computing. In this paper, we propose a new paradigm called trajectory based forwarding (or TBF), which is a generalization of source based routing and Cartesian routing. We argue that TBF is an ideal technique for routing in dense ad-hoc networks. Trajectories are a natural namespace for describing route paths when the topology of the network matches the topography of the physical surroundings in which it is deployed which by very definition is embedded computing.We show how simple trajectories can be used in implementing important networking protocols such as flooding, discovery, and network management. Trajectory routing is very effective in implementing many networking functions in a quick and approximate way, as it needs very few support services. We discuss several research challenges in the design of network protocols that use specific trajectories for forwarding packets.
The MCTS operating system
Authors: Elshoff James L. , Ward Mitchel R.
Published: October 2004

The Multiple Console Time Sharing System, MCTS, implemented at the General Motors Research Laboratories is described. An overview of the logical and physical structures of the operating system is presented.Significant concepts embodied in the operating system are discussed. The system multi-programs among a variable number of tasks, each in an independent virtual memory. A virtual input/output access method is the only one provided. All input/output is performed by polling, no interrupts are used. The operating system is structured exactly like a customer task with only a few special privileges.The MCTS operating system is conceptually simple. The system programmers write in a PL/I-like languaged called MALUS. The system programmers work in an environment very similar to the environment normally associated with an application programmer. The paper discusses the system programmer's environment and some experiences during the development of the operating system.
A simple approach to operating system generation and initialization
Authors: Ward Mitchel R.
Published: October 2004

System initialization or system generation is the creation of a viable operating system from a collection of individual program modules. For many operating systems the initialization process is a very long and complex procedure. During the development of the MCTS operating system at GMR, an initialization procedure was designed and implemented with simplicity and flexibility as key design goals.The emphasis on simplicity and flexibility was applied in two distinct aspects of the initialization process, The first was simplicity and flexibility of use. A system programmer was given an interactive procedure which allowed him to very easily modify key initialization parameters, The second aspect was the simple and flexible design of the initialization programs. As development of MCTS continued, so did the initialization programs, hence their design was kept simple and flexible to meet the changing requirements of a developing system.This paper describes the design and development of MCTS system initialization procedures beginning with an 'emptyheaded' computer and ending with a semi-automatic system initialization procedure.
UNIX
Authors: Miller Richard
Published: October 2004

The use of top-down design methods and high-level languages in producing portable applications software is well established. By applying the same principles at the systems programming level, portability can be extended to the operating system itself.Although the Unix operating system was developed for a specific computer (the DEC PDPll), its concise and elegant design and the careful selection of 'primitives' which it provides make it an ideal candidate for portability. This paper describes the experience of adapting Unix to an Interdata 7/32.
Making internet communities work
Authors: Krieger Bernhard L. , Müller Philipp S.
Published: October 2004

Building Internet communities has been hailed as one of the major strategic innovations of theNew Economy, both as a stand-alone model or as a supplement to sustain competitive advantage for normal business models. Community based business models aim to profit from the value that is created when Internet communities solve problems of collective action, by controlling access, aggregating data, or realizing side-payments.The current literature on community based business models relies on methodological individualism to explain why members join and leave Internet communities. However, such an approach cannot sufficiently describe and explain communities because they are by definition more than an aggregation of its members.We, on the other hand, offer a metaphorical approach to conceptualize communities. Metaphors have a double function for communities: to explain the community to its members and thereby legitimize and reproduce it, and to describe the belief of community members to outsiders in order to operationalize it.With the metaphorical approach we develop a framework to build profitable Internet communities. If an internet community can be legitimized and reproduced community-value is created. However, that does not yet mean that it can be translated into profit, as many I Internet entrepreneurs had to realize. To translate the community-value into profit, the communal entrepreneur must position it in its competitive environment.
Using model checking to debug device firmware
Authors: Kumar Sanjeev , Li Kai
Published: October 2004

Device firmware is a piece of concurrent software that achieves high performance at the cost of software complexity. They contain subtle race conditions that make them difficult to debug using traditional debugging techniques. The problem is further compounded by the lack of debugging support on the devices. This is a serious problem because the device firmware is trusted by the operating system.Model checkers are designed to systematically verify properties of concurrent systems. Therefore, model checking is a promising approach to debugging device firmware. However, model checking involves an exponential search. Consequently, the models have to be small to allow effective model checking.This paper describes the abstraction techniques used by the ESP compiler to extract abstract models from device firmware written in ESP. The abstract models are small because they discard some of the details in the firmware that is irrelevant to the particular property being verified. The programmer is required to specify the abstractions to be performed. The ESP compiler uses the abstraction specification to extract models conservatively. Therefore, every bug in the original program will be present in the extracted model.This paper also presents our experience with using Spin model checker to develop and debug VMMC firmware for the Myrinet network interfaces. An earlier version of the ESP compiler yielded models that were too large to check for system-wide properties like absence of deadlocks. The new version of the compiler generated abstract models that were used to identify several subtle bugs in the firmware. So far, we have not encountered any bugs that were not caught by Spin.
Practical, transparent operating system support for superpages
Authors: Navarro Juan , Iyer Sitararn , Druschel Peter , Cox Alan
Published: October 2004

Most general-purpose processors provide support for memory pages of large sizes, called superpages. Superpages enable each entry in the translation lookaside buffer (TLB) to map a large physical memory region into a virtual address space. This dramatically increases TLB coverage, reduces TLB misses, and promises performance improvements for many applications. However, supporting superpages poses several challenges to the operating system, in terms of superpage allocation and promotion tradeoffs, fragmentation control, etc. We analyze these issues, and propose the design of an effective superpage management system. We implement it in FreeBSD on the Alpha CPU, and evaluate it on real workloads and benchmarks. We obtain substantial performance benefits, often exceeding 30%; these benefits are sustained even under stressful workload scenarios.
TAG
Authors: Madden Samuel , Franklin Michael J. , Hellerstein Joseph M. , Hong Wei
Published: October 2004

We present the Tiny AGgregation (TAG) service for aggregation in low-power, distributed, wireless environments. TAG allows users to express simple, declarative queries and have them distributed and executed efficiently in networks of low-power, wireless sensors. We discuss various generic properties of aggregates, and show how those properties affect the performance of our in network approach. We include a performance study demonstrating the advantages of our approach over traditional centralized, out-of-network methods, and discuss a variety of optimizations for improving the performance and fault tolerance of the basic solution.
Supporting time-sensitive applications on a commodity OS
Authors: Goel Ashvin , Abeni Luca , Krasic Charles , Snow Jim , Walpole Jonathan
Published: October 2004

Commodity operating systems are increasingly being used for serving time-sensitive applications. These applications require low-latency response from the kernel and from other system-level services. In this paper, we explore various operating systems techniques needed to support time-sensitive applications and describe the design of our Time-Sensitive Linux (TSL) system. We show that the combination of a high-precision timing facility, a well-designed preemptible kernel and the use of appropriate scheduling techniques is the basis for a low-latency response system and such a system can have low overhead. We evaluate the behavior of realistic time-sensitive user- and kernel-level applications on our system and show that, in practice, it is possible to satisfy the constraints of time-sensitive applications in a commodity operating system without significantly compromising the performance of throughput-oriented applications.
TENEX
Authors: Bobrow Daniel G. , Burchfiel Jerry D. , Murphy Daniel L. , Tomlinson Raymond S.
Published: October 2004

TENEX is a new time sharing system implemented on a DEC PDP-10 augmented by special paging hardware developed at BBN. This report specified a set of goals which are important for any time sharing system. It describes how the TENEX design and implementation achieve these goals. These include specifications for a powerful multiprocess large memory virtual machine, intimate terminal interaction, comprehensive uniform file and I/O capabilities, and clean flexible system structure. Although the implementation described here required some compromise to achieve a system operational within six months of hardware checkout, TENEX has met its major goals and provided reliable service at several sites and through the ARPA network.
The Multics input/output system
Authors: Feiertag R. J. , Organick E. I.
Published: October 2004

An I/O system has been implemented in the Multics system that facilitates dynamic switching of I/O devices. This switching is accomplished by providing a general interface for all I/O devices that allows all equivalent operations on different devices to be expressed in the same way. Also particular devices are referenced by symbolic names and the binding of names to devices can be dynamically modified. Available I/O operations range from a set of basic I/O calls that require almost no knowledge of the I/O System or the I/O device being used to fully general calls that permit one to take full advantage of all features of an I/O device but require considerable knowledge of the I/O System and the device. The I/O System is described and some popular applications of it, illustrating these features, are presented.
An algorithm for drum storage management in time-sharing systems
Authors: Greenberg Mark L.
Published: October 2004

An algorithm for efficiently managing the transfer of pages of information between main and secondary memory is developed and analyzed. The alogorithm applies to time-shared computer systems that use rotatlng magnetic drums as secondary storage devices. The algorithm is designed to provide efficient system performance when referenced pages are predominantly pre-loaded. However, the algorithm also provides optimum results for systems where all pages are loaded on demand. The nature of the improved performance which can be derived from page pre-loading strategy is discussed. Simulation results are presented which plot system performance as a function of main memory size.
On structuring operating systems with monitors
Authors: Keedy J. L.
Published: October 2004

This paper considers whether Hoare's monitor proposal for structuring operating systems could usefully be applied in the design of substantial operating systems for medium or large computers. Attention is drawn to problems which might arise in terms of the structural form of monitors, the approach to resource scheduling, and the monitor approach to synekrordsation and process scheduling. An appended note considers the related technique proposed by Wirth in the Modula language.
An implementation of capabilities on the PDP-11/45
Authors: Hoch Charles , Browne J. C.
Published: October 2004

This paper defines a capability implementation which uses the memory management hardware and the TRAP instruction of the higher members of the Digital Equipment Corporation PDP-11/XX (XX = 34, 45, 55, 70) to create a capability architecture processor. No modifications to hardware are necessary. The architecture created has a strong similarity to that of the Plessey 250. An operating system based on this architecture could provide a basis for implementation of highly reliable and secure software systems on a common and inexpensive minicomputer.
Object representation on a heterogeneous network
Authors: Girling C. Gray
Published: October 2004

This paper documents some of the author's recent research into representation and naming in local area communication networks. It outlines a simple and practical method of providing what could be called 'network capabilities', an effort being made to keep this topic distinct from those of data security, data communication, network configurations and protocols.
Detection and resolution of inconsistencies among distributed replicates of files
Authors: Brereton Pearl
Published: October 2004

If file replication is used as a means of improving file availability problems of mutual consistency arise when the network which connects copies is subject to partitioning. A method of detecting inconsistencies is presented and the problems associated with automatic resolution of conflicts are outlined.
Script
Authors: Francez Nissim , Hailpern Brent
Published: October 2004

In this paper, we introduce a new abstraction mechanism, called a
script
, which hides the low-level details that implement
patterns of communication
. A script localizes the communication between a set of
roles
(formal processes), to which actual processes
enroll
in order to participate in the action of the script. The paper discusses the addition of scripts to the languages CSP and Ada, as well as to a shared-variable language with monitors.
Solved problems, unsolved problems and non-problems in concurrency
Authors: Lamport Leslie
Published: October 2004

This is an edited transcript of a talk given at last year's conference. To preserve the flavor of the talk and the questions, I have done very little editing---mostly eliminating superfluous words and phrases, correcting especially atrocious grammar, and making the obvious changes needed when replacing slides by figures. The tape recorder was not functioning for the first few minutes, so I had to recreate the beginning of the talk.
A deadlock detection and recovery algorithm using the formalism of a directed graph matrix
Authors: Leibfried T. F.
Published: October 2004

A new method of detecting and resolving deadlocked processes in an operating system or database system is presented. It is based on matric theoretic principles and effectively automates tasks heretofore only achievable via adjacency list representations. Two algorithms are presented with examples for each.
The next generation of internetworking
Authors: Parulkar Gurudatta M.
Published: October 2004

This paper describes a research effort concerned with the design of the next generation of internet architecture, which has been necessitated by two emerging trends. First, there will be at least a few orders of magnitude increase in data rates of communication networks in the next few years. For example, researchers are already prototyping networks with data rates of up to a few hundred Mbps, and are planning networks with data rates up to a few Gbps. Second, researchers from all disciplines of science, engineering, and humanities plan to use the communication infrastructure to access widely distributed resources in order to solve bigger and more complex problems. These trends provide new challenges and opportunities to researchers in the communication field. One such challenge is the design of what we call the very high speed internet (VHSI) abstraction which can help efficiently support guaranteed levels of performance for a variety of applications, and can cope with the ever increasing diversity of underlying networks with rapidly growing user population and needs. Our strategy towards achieving this ambitious goal comprises the following:• Design, specification, and prototype implementation of a novel multipoint
congram-oriented
service that can work well with connection-oriented and datagram high speed networks, can provide variable grade service on a need basis to its applications, and can provide adequate reconfigurability to deal with survivability requirements due to network failures.• Design and implementation of gateway architectures that can support data rates of a few hundred Mbps, can interface with diverse networks, and can implement the congram-oriented service without becoming a performance bottleneck.• Development of analytical and simulation models to evaluate important tradeoffs associated with the design of a congram-oriented protocol, the resource management on diverse networks, and the design of new gateway architectures.
How slow is one gigabit per second?
Authors: Partridge Craig
Published: October 2004

At first blush, one would expect that increasing data network transfer rates by two orders of magnitude (from the ubiquitous 10 Mbit speed of today's LANs to the greater than 1 gigabit-per-second speeds we expect of networks in the early 1990s) would severely impact our choice of network protocols and architectures. This report presents the strawman argument that, in fact, moving to one-gigabit data rates presents surprisingly
few
problems.
Offering different services by server clusters
Authors: Liu Jing , Zheng Mingyang , Ju Jiubin
Published: October 2004

Nowadays operating systems on single servers have encountered a lot of trouble; server clusters are not able to offer different services for different clients. Under this circumstance, we put forward a new idea, that is, different clients are given different priority domains, thus can gain different services. We improve current resource management mechanism, and use it on server nodes in clusters. Experiment results show that the method is effective, and a cluster can provide different services to different clients, therefore the performance of server clusters are improved.
Partitioning based operating system
Authors: Luo Lei , Zhu Ming-Yuan
Published: October 2004

Automated aircraft control has traditionally been divided into distinct functions that are implemented separately (e.g., autopilot, auto-throttle, flight management); each function has its own fault-tolerant computer system, and dependencies among different functions are generally limited to the exchange of sensor and control data. A by-product of this federated architecture is that faults are strongly contained within the computer system of the function where they occur and cannot readily propagate to affect the operation of other functions.More modern avionics architectures contemplate supporting multiple functions on a single, shared, fanlt-tolerant computer system where natural fault containment boundaries are less sharply defined. Partitioning uses appropriate hardware and software mechanisms to restore strong fault containment to such integrated architectures.This paper examines the formal specification of partitioning and the mathematical properties in providing assurance for partitioning.
Reservation aware operating system for grid economy
Authors: Tse K. W. , Lam W. K. , Lun P. K.
Published: October 2004

Emerging Grid computing, computational resources and instruments are geographically distributed with diverse ownership, introducing a highly dynamic and unpredictable of resource using in Grid environment. Resource management, and scheduling in the Grid environment is complex to undertake. Multi-agent systems and economic model have been proposed to tackle the resource management problem, but little attentions were paid to the underlying technology supporting the scheduling abstractions. This paper proposes a design of reservation aware operating system that able to support the upper level scheduling abstraction in Grid environment. We have developed and evaluated a CPU resource reservation aware system.
ACM SIGACT news distributed computing column 11
Authors: Rajsbaum Sergio
Published: October 2004

The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification, internet, and the web.This issue consists of the paper "Reconstructing Paxos" by Romain Boichat, Partha Dutta, Svend Frølund, and Rachid Guerraoui. Many thanks to them for contributing to this issue.The celebrated Paxos algorithm of Lamport implements a fault-tolerant deterministic service by replicating it over a distributed message-passing system. In a companion paper [2], we presented a deconstruction of the algorithm by factoring out its fundamental algorithmic principles within two abstractions: an eventual leader election and an eventual register abstractions. Using those abstractions, we show in this paper how to reconstruct, in a modular manner, powerful variants of Paxos. In particular, we show how to (1) alleviate the need for stable storage access if some processes remain up for sufficiently long, (2) augment the resilience of the algorithm against unstable processes, (3) enable single process decision with shared commodity disks, and (4) reduce the number of communication steps during stable periods of the system.The Island of Paxos used to host a great civilisation which had developed a sophisticated parttime parliament protocol. Paxons codified various aspects of their parliament protocol which enabled them to easily adapt the protocol to specific functioning modes throughout the seasons. In particular, during winter, the parliament was heated and some legislators did never leave the chamber: their guaranteed presence helped alleviate the need for the writing of decrees on ledgers. This was easy to obtain precisely because the subprotocol used to "store and lock" decrees was precisely codified. In spring, and with the blooming days coming, some legislators could not stop leaving and entering the parliament. Their indiscipline prevented progress in the protocol. However, as the election subprotocol used to choose the parliament president was also precisely codified, the protocol could easily be adapted to cope with indisciplined legislators. During summer, very few legislators were in the parliament and it was hardly possible to pass any decree because of the lack of the necessary majority. Fortunately, it was easy to modify the subprotocol used to store and lock decrees and devise a powerful technique where a single legislator could pass decrees by directly accessing the ledgers of other legislators. Fall was a protest season and citizens wanted a faster procedure to pass decrees. Paxons noticed that, in most periods, messengers did not loose messages and legislators replied in time. They could devise a variant of the protocol that reduced the number of communication steps needed to pass decrees during those periods. Again, this optimisation was obtained through a simple refinement of the subprotocol used to propose new decrees.
Ramifications of re-introducing asynchronous exceptions to the Ada language
Authors: Quiggle Thomas J.
Published: October 2004

Re-introduction of asynchronous exceptions into the Ada language has been suggested as a means to solve certain problems in intertask communication. The author argues that such re-introduction would provide inconsistent and nondeterministic semantics, disallow several important classes of optimization, cause considerable distributed overhead, complicate program proof and verification efforts, prove error-prone to use, and offer little new functionality. Further discussions of alternate solutions to the requirements which motivated asynchronous exceptions are encouraged.
Usability of the Ada tasking-model
Authors: Bums A. , Wellings A. J.
Published: October 2004

This paper considers some of the issues surrounding the usability of Ada in real-time systems. Attention is focussed on the tasking model and a number of, arguably, deficient features of the language are described. None of the issues discussed can be termed critical as work-arounds are possible, although some of these are inefficient and may not be appropriate in time-critical situations. The 9X process presents an opportunity to reassess the tasking model. This could lead to proposals for language changes that are "desirable" if not stricdy "minimal".
An algebraic description of programs with assertions, verification and simulation
Authors: Burstall Rod M.
Published: October 2004

A program in flow diagram form is described by a function from a free category to the category of sets and relations. Attaching assertions to it is described as a natural transformation and so is simulation of one program by another with the same shape of flow diagram. These notions are used to prove the theorems justifying Floyd's method of proving correctness by verification and Milner's method of proving simulation, restricted to programs of similar form. The treatment is novel but the results are not new, except that non-deterministic programs are dealt with throughout.
A boundary between decidability and undecidability for parallel program schemata (Extended Abstract)
Authors: Miller Raymond E.
Published: October 2004

Some theorems showing undecidability for computational commutativity, boundedness, termination and determinacy of parallel program schemata are given. These results are then compared with contrasting decidability results in [1] showing that the deletion of the hypothesis of repetition-freeness from the decidability theorems produces undecidability.
On a laboratory for the study of automating programming
Authors: Cheatham T. E. , Wegbreit Ben
Published: October 2004

At the present time there is considerable interest in the general question of “automating programming:” there are a number of people actively doing research concerned with various aspects of the question and even a few projects exploring various practical issues via experimental implementations. The area encompassed by “automating programming” is a very broad one, particularly if one understands “programming” to include the entire spectrum of activities concerned with producing algorithms which are correct and effective in terms of certain design specifications. It is therefore to be expected that comparison of various techniques and integration of those techniques and the experimental facilities developed in a variety of institutions will be difficult and expensive unless there is some coordinated effort to provide a common framework to support such activities. We would note that at present it is relatively expensive just to construct sufficient programs to permit the investigation of and experimentation with some proposed technique of program automation; because of this many studies in the general area of programming automation are primarily “paper studies”.

It is the purpose of this note to provide an overview of the project currently under way at Harvard's Center for Research in Computing Technology, directed toward the implementation of a laboratory for the study of programming automation techniques. A more detailed discussion of our approach is provided in [1]. In the four sections which follow we will discuss briefly our view of the use of a program automation laboratory, the basis for and basic components of the facility currently being implemented, and finally, suggest that there are a variety of research areas which are strongly related to the question of automating programming in which the laboratory might be employed as a research tool.