bluuebunny/crossref_metadata_2025_split huggingface dataset:
AMp: a highly parallel atomic multicast protocol
Authors: Veríssimo P. , Rodrigues L. , Baptista M. 
Published: October 2004

This paper deals with the problem of reliable group communication for distributed applications, in the context of the Reliable Broadcast class of protocols. An atomic multicast protocol for token passing Lans is presented. The actual implementation is on an 8802/4 Token-bus, although it is applicable to 8802/5 Token-rings and the FDDI Fibre-Optic network.
The simplicity and efficiency of reliable broadcast protocols may be considerably improved, if the system fault model is restricted or convenient architectures are used. Fail-controlled communication components are used here to build an efficient reliable multicast protocol on top of the exposed MAC interface of a VLSI Lan controller. The architecture is built on standard Lans, in view of taking advantage of the availability of communications hardware and the possibility of coexistence with standard stations, in the same network.
The service offered allows transparent multicasting inside logical groups, which are dynamically created and updated. The primitive is highly parallel and provides atomic agreement and consistent delivery order, respecting logical precedence. These features are an important contribution for the implementation of high performance distributed computing systems.
Protocol validation in complex systems
Authors: West C. H. 
Published: October 2004

Protocol validation and verification techniques have been applied successfully for a number of years to a wide range of protocols. The increasing complexity of our communications systems requires us to examine existing techniques and make a realistic assessment of which techniques will be applicable to the complex systems of the future. We believe that validation techniques based on an exhaustive reachability analysis will not be effective. Sampling techniques, such as executing a random walk through the reachable state space, are effective in complex systems, since most protocol errors occur in many different states of the system.
More than 10 years have elapsed since the first automated validation techniques were first applied to communications protocols [1,2]. In the meantime, considerable advances have been made in validation technology, but more significantly, the scale and nature of the validation problem have changed. The communications systems that we need to validate today are significantly more complex than those of ten years ago. Our methods must evolve in order to address the current challenge.
This paper is concerned primarily with the nature of the validation process, and the results that we might reasonably expect to achieve when validating protocols in complex communications systems.
A file system supporting cooperation between programs
Authors: Reid Loretta Guarino , Karlton Philip L. 
Published: October 2004

File systems coordinate simultaneous access of files by concurrent client processes. Although several processes may read a file simultaneously, the file system must grant exclusive access to one process wanting to write the file. Most file systems consider processes to be antagonistic: they prevent one process from taking actions on a file that have any chance to harm to another process already using the file. If several processes need to cooperate in a more sophisticated manner in their use of a file, they must communicate explicitly among themselves.
The next three sections describe the file system procedures used by clients for using and sharing files. Section Two discusses how a client gains access to a file and how a client can respond if the file system asks it to give up a file it is using. Section Three discusses the mechanism by which a client might ask to be notified that a file is available for some access. Section Four discusses a controlled type of file access that lets clients read and write the same file at the same time.
Section Five comprises three examples of the cooperative features of the file system taken from the Xerox Development Environment. Section Six discusses the subtleties of writing the call-back procedures that clients provide to the file system to implement interprocess cooperation. Section Seven discusses the implementation of this file system.
A nested transaction mechanism for LOCUS
Authors: Mueller Erik T. , Moore Johanna D. , Popek Gerald J. 
Published: October 2004

Atomic transactions are useful in distributed systems as a means of providing reliable operation in the face of hardware failures. Nested transactions are a generalization of traditional transactions in which transactions may be composed of other transactions. The programmer may initiate several transactions from within a transaction, and serializability of the transactions is guaranteed even if they are executed concurrently. In addition, transactions invoked from within a given transaction fail independently of their invoking transaction and of one another, allowing use of alternate transactions to accomplish the desired task in the event that the original should fail. Thus nested transactions are the basis for a general-purpose reliable programming environment in which transactions are modules which may be composed freely.
A working implementation of nested transactions has been produced for LOCUS, an integrated distributed operating system which provides a high degree of network transparency. Several aspects of our mechanism are novel. First, the mechanism allows a transaction to access objects directly without regard to the location of the object. Second, processes running on behalf of a single transaction may be located at many sites. Thus there is no need to invoke a new transaction to perform processing or access objects at a remote site. Third, unlike other environments, LOCUS allows replication of data objects at more than one site in the network, and this capability is incorporated into the transaction mechanism. If the copy of an object that is currently being accessed becomes unavailable, it is possible to continue work by using another one of the replicated copies. Finally, an efficient orphan removal algorithm is presented, and the problem of providing continued operation during network partitions is addressed in detail.
Publishing
Authors: Powell Michael L. , Presotto David L. 
Published: October 2004

Publishingis a model and mechanism for crash recovery in a distributed computing environment. Published communication works for systems connected via a broadcast medium by recording messages transmitted over the network. The recovery mechanism can be completely transparent to the failed process and all processes interacting with it. Although published communication is intended for a broadcast network such as a bus, a ring, or an Ethernet, it can be used in other environments.Arecorderreliably stores all messages that are transmitted, as well as checkpoint and recovery information. When it detects a failure, the recorder may restart affected processes from checkpoints. The recorder subsequently resends to each process all messages which were sent to it since the time its checkpoint was taken, while ignoring duplicate messages sent by it.Message-based systems without shared memory can use published communications to recover groups of processes. Simulations show that at least 5 multi-user minicomputers can be supported on a standard Ethernet using a single recorder. The prototype version implemented in DEMOS/MP demonstrates that an error recovery can be transparent to user processes and can be centralized in the network.
Process migration in DEMOS/MP
Authors: Powell Michael L. , Miller Barton P. 
Published: October 2004

Process migration has been added to the DEMOS/MP operating system. A process can be moved during its execution, and continue on another processor, with continuous access to all its resources. Messages are correctly delivered to the process's new location, and message paths are quickly updated to take advantage of the process's new location. No centralized algorithms are necessary to move a process.
A number of characteristics of DEMOS/MP allowed process migration to be implemented efficiently and with no changes to system services. Among these characteristics are the uniform and location independent communication interface, and the fact that the kernel can participate in message send and receive operations in the same manner as a normal process.
The TRIPOS filing machine, a front end to a file server
Authors: Richardson M. F. , Needham R. M. 
Published: October 2004

This paper discusses an experiment which sets out to improve the performance of a number of single user computers which rely on a general purpose file server for their filing systems. The background is described in detail in reference [1], but for completeness it is necessary to say something about it here.
The Cambridge Distributed Computing System consists, at the time of writing, of between 50 and 60 machines of various types, connected by a digital communications ring. On the ring, there are two file servers [2], [3], which are general purpose (or "universal" [4]) in the sense that they have no commitment to a particular directory or access control structure. This is done in order that they may support several client systems, and so that new systems may be added without difficulty. We speak of a particular directory and access control structure implemented over the file server as "a filing system".
The distributed V kernel and its performance for diskless workstations
Authors: Cheriton David R. , Zwaenepoel Willy 
Published: October 2004

The distributed V kernel is a message-oriented kernel that provides uniform local and network interprocess communication. It is primarily being used in an environment of diskless workstations connected by a high-speed local network to a set of file servers. We describe a performance evaluation of the kernel, with particular emphasis on the cost of network file access. Our results show that over a local network:
1. Diskless workstations can access remote files with minimal performance penalty.
2. The V message facility can be used to access remote files at comparable cost to any well-tuned specialized file access protocol.
We conclude that it is feasible to build a distributed system with all network communication using the V message facility even when most of the network nodes have no secondary storage.
Inductive methods for proving properties of programs
Authors: Manna Zohar , Ness Stephen , Vuillemin Jean 
Published: October 2004

We have two main purposes in this paper. First, we clarify and extend known results about computation of recursive programs, emphasizing the difference between the theoretical and practical approaches. Secondly, we present and examine various known methods for proving properties of recursive programs. We discuss in detail two powerful inductive methods, computational induction and structural induction, illustrating their applications by various examples. We also briefly discuss some other related methods.
Our aim in this work is to introduce inductive methods to as wide a class of readers as possible and to demonstrate their power as practical techniques. We ask the forgiveness of our more theoretical-minded colleagues for our occasional choice of clarity over precision.
Decision problems in computational models
Authors: Paterson Michael S. 
Published: October 2004

Some of the assertions about programs which we might be interested in proving are concerned with correctness, equivalence, accessibility of subroutines and guarantees of termination. We should like to develop techniques for determining such properties efficiently and intelligently wherever possible. Though theory tells us that for a realistic programming language almost any interesting property of the behaviour is effectively undecidable, this situation may not be intolerable in practice. An unsolvability result just gives us warning that we may not be able to solve all of the problems we are presented with, and that some of the ones we can solve will be very hard.
In such circumstances it is very reasonable to try and determine necessary or sufficient conditions on programs for our techniques to be assured of success; however, in this paper we shall discuss a more qualitative, indirect, approach. We consider a range of more or less simplified computer models, chosen judiciously to exemplify some particular feature or features of computation. A demonstration of unsolvability in such a model reveals more accurately those sources which can contribute to unsolvability in a more complicated structure. On the other hand a decision procedure may illustrate a technique of practical use. It is our thesis that this kind of strategy of exploration can and will yield insight and practical advances in the theory of computation. Provided that the model retains some practical relevance, the dividends are the greater the nearer the decision problem lies to the frontier between solvability and unsolvability.
Translating recursion schemes into program schemes
Authors: Garland Stephen J. , Luckham David C. 
Published: October 2004

Here and in a further paper [2] we study translations between schemes and related equivalence problems, i.e., problems of determining whether two schemes in a given class are equivalent. In particular, we are concerned with the question of developing methods for attacking these problems. It seems to us that some “general methods” ought to exist or, at least, a general form ought to be given to the existing “tricks”. In these papers we present four methods: applying the theory of formal languages, programming, measuring the complexity of a computation, and “cutting and pasting” (roughly speaking, the application of a method due to Rabin and Scott [8] to bound the search necessary to determine if two schemes will behave differently).
Although a few of the results are true for some general notion of scheme, we have nearly always had in mind, for the sake of illustration, just three specific classes of schemes: program schemes, program schemes augmented with counters, and recursively defined schemes. The greater part of the study is restricted to monadic schemes (i.e., schemes containing only functions and predicates of a single argument), and in the case of recursively defined schemes, we are concerned almost exclusively with the single variable monadic recursion schemes introduced by de Bakker and Scott in [1].
On the structure and control of commands
Authors: Stephenson C. J. 
Published: October 2004

An interactive command language, with its underlying data, defines a command environment. In general a command environment supports a number of commands which once issued perform non-interactively, and which when finished leave the old command environment in control. It also supports some special commands which move to other command environments, after which commands are interpreted according to a different set of rules.
The usefulness of a command environment can be extended by programming it, i.e. by dynamically constructing and conditionally executing sequences of its commands; but, unlike a programming language, a command language does not usually contain any general-purpose variables or means for conditional execution. These facilities can however be provided by a command control language, which makes it possible to construct sequences or commands to be issued to the currently active command environment from a program.
A command control language is described, and the usefulness, limitations and repercussions of command language programming are discussed.
The UNIX time-sharing system
Authors: Ritchie Dennis M. , Thompson Ken 
Published: October 2004

UNIX is a general-purpose, multi-user, interactive operating system for the Digital Equipment Corporation PDP-1 1/40 and 11/45 computers. It offers a number of features seldom found even in larger operating systems, including
1. A hierarchical file system incorporating demountable volumes,
2. Compatible file, device, and inter-process I/O,
3. The ability to initiate asynchronous processes,
4. System command language selectable on a per-user basis,
5. Over 100 subsystems including a dozen languages.
This paper discusses the usage and implementation of the file system and of the user command interface.
The case for capability based computers (Extended Abstract)
Authors: Fabry R. S. 
Published: October 2004

The idea of a capability which acts like a ticket authorizing the use of some resource was developed by Dennis and Van Horn as a generalization of addressing and protection schemes such as the code- words of the Rice computer, the descriptors of the Burroughs machines, and the segment and page tables in computers such as the GE-645 and IBM 360/67. Dennis and Van Horn generalized the earlier schemes by extending them to include not just memory, but all systems resources: memory, processes, input/output devices, and so on; and by stressing the explicit manipulation of access control by nonsystem programs. The idea is that a capability is a special kind of address for an object, that these addresses can be created only by the supervisor, and that in order to use any object, one must address it via one of these addresses. The name comes from the fact that having one of these special kinds of addresses for a resource provides one with the capability to use the resource.
The use of capabilities as a protection mechanism has been the subject of considerable interest and is now fairly well understood. Access control schemes using capabilities and capability -like notions are, as a whole, the most flexible and general schemes available. It will in fact be assumed that the reader is familiar with the advantages of capabilities for protection put-poses; a somewhat different advantage of capabilities will be developed here.
Formal requirements for virtualizable third generation architectures
Authors: Popek Gerald J. , Goldberg Robert P. 
Published: October 2004

Virtual machine systems have been implemented on a limited number of third generation computer systems, for example CP-67 on the IBM 360/67. The value of virtual machine techniques to ease the development of operating systems, to aid in program transferability, and to allow the concurrent running of disparate operating systems, test and diagnostic programs has been well recognized. However, from previous empirical studies, it is known that many third generation computer systems, e.g. the DEC PDP-10, cannot support a virtual machine system.
In this paper, the hardware architectural requirements for virtual machine systems are discussed. First, a fairly specific definition of a virtual machine is presented which includes the aspects of efficiency, isolation, and identical behavior. A model of third generation-like computer systems is then developed. The model includes a processor with supervisor and user modes, memory that has a simple protection mechanism, and a trap facility. In this context, instruction behavior is then carefully characterized.
Commercial network security—does anyone care?
Authors: Burke Edmund L. 
Published: October 2004

Since World War II, the US government has had a comprehensive way to deal with communication security. Under pressure from commercial interests, the government moved in the 70's to make some communication security technology available in the form of the
D
ata
E
ncryption
S
tandard.

DES has been available for some time, yet there is little interest in the marketplace. The lack of interest could stem from unawareness or unconcern with security or from the feeling that data security is not the weak point in the system.
This session will investigate the techniques and vulnerabilities of commercial network security. Panel members will present their experiences with developmental and product activities aimed at providing security in a business environment. The panel will try to stimulate discussion on why there has been no market and what technical characteristics that market should have.
A methodology for the design of reliable communication networks in distributed processing systems
Authors: Besharatian Hossein 
Published: October 2004

The combined problem of the communication network design and resource allocation is studied for Distributed Data Processing (DDP) networks. The reliability measure for a distributed data processing system is used in order to enhance network reliability.
A model is proposed to determine an optimal DDP network and to allocate resources that maximize the reliability measure of the network, The model takes into consideration network topology, resource avaliability and channel capacity. It is shown that the model may be represented by a linear programming model.
Panel on multimedia computer mail—technical issues and future standards
Authors: Deutsch Debra P. , Forsdick Harry C. , Aceves J. J. Garcia Luna , Naffah Najah , Poggio Andrew , Postel Jonathan B. , White James E. , Kuo Franklin F. 
Published: October 2004

A computer-based message system (CBMS) consists of computer facilities that expedite the creation, management, and nonreal time distribution of messages. These systems are increasingly being used for formal and informal communication, supporting the distribution of textual messages. However, nontext media such as voice and graphics are very important for human interaction, and are becoming more and more important in computer system applications. As a result, there is a growing need for the support of media other than text in CBMS.
Before standards for multimedia CBMS can be implemented, there are many technical issues that must be addressed. These range from the design of new mechanisms for the distribution of multimedia mail, to the design of tools needed for editing nontext media. This panel will be discussing issues encountered in the development of multimedia CBMS and an outlook for standards for multimedia computer mail.
A function oriented corporate network
Authors: Wang P. S.-C. , Kimbleton S. R. 
Published: October 2004

The ITT/NET is an internal corporate network built to satisfy the distributed programming requirements of ITT technology and engineering communities. This paper describes the network: its goals, its architecture, its operational environment and prototype development activities.
The various issues involved in the construction of a Corporate Network based upon diverse, existing systems and communication methods are described in detail. The architectural and implementation decisions are discussed and justified. The programming process and the methodologies adopted are presented and some conclusions are drawn as to the practicality and usefulness of formal development methods in the context of this particular project.
Shortest paths and loop-free routing in dynamic networks
Authors: Awerbuch B. 
Published: October 2004

In this paper, we survey the existing methods for designing shortest paths routing algorithms for dynamic networks. We compare them based on worst-case communication and message complexity, and suggest new approach that yields a protocol with linear time and polynomial communication.
The main idea behind our approach is to use a “dynamic synchronizer”, which transforms a dynamic asynchronous network into static synchronous one. We believe this is an important methodology in design and analysis of communication protocols, that can be applied to other problems as well.