bluuebunny/crossref_metadata_2025 huggingface dataset:
Software portability gains realized with METAH and Ada95
Authors: Lewis Bruce
Published: October 2004

MetaH is an Architecture Description Language (ADL) developed to express and evaluate the software architecture of avionics and flight control systems. It is intended for not only description and analysis, but also for integration of the software components on the specified embedded hardware. This automated composition to specification with glue code generation allows rapid development and evolution of real-time embedded mission and safety critical systems. It also provides very high portability in these complex systems for software application code across various execution environments. This is accomplished by leveraging language and O/S standards, minimizing component dependencies, and by constructing component timing relationships to specification across differing execution platforms.This paper describes MetaH and provides the results of porting a highly time sensitive application across significantly different embedded hardware/software execution environments. We initially developed a reusable MetaH specification for missile architectures, populated it with software components reengineered from a production missile system, and executed it on single and dual i80960MC target configurations. We then retargeted this application to single and dual Pentium target configurations; and to a single PowerPC configuration. We compare the costs of these exercises with estimated costs to do the same tasks using traditional methods.In each of these cases the high portability and supported functionality of Ada95 was a significant enabler. Current trends say that future avionics systems and perhaps other safety critical applications will require space and time partitioning. Should Ada95 and the Ravenscar profile support these capabilities?
Modeling and schedulability analysis in the development of real-time distributed Ada systems
Authors: Gutiérrez J. Javier , Drake José M. , Harbour Michael González , Medina Julio L.
Published: October 2004

The paper proposes a model for specific Ada structures that can be integrated into our methodology for modeling and performing schedulability analysis in the development phases of distributed real-time applications written in Ada 95 and using its Annexes D and E. This methodology is based on independently modeling the platform, the logical components used, and the real-time situations of the application itself (real-time transactions, workload or timing requirements). The specific models presented in the paper provide support for the automated analysis of local and remote access to distributed services; hence, if a procedure of a remote call interface is invoked from a component assigned to a remote node, the corresponding communication model (with marshalling, transmission, dispatching, and unmarshalling of messages) is implicitly integrated into the overall model that is being analyzed.
Accessing delay queues
Authors: Burns A. , Wellings A. J.
Published: October 2004

A number of flexible scheduling schemes can be programmed in Ada 95 by combining the more advanced features the language provides. For example, imprecise computations would appear to be accommodated by the use of ATCs (with timing triggers) and dynamic priorities. Unfortunately with this type of scheme, it is difficult to ensure that the priority of the task, following the triggering event, is at the appropriate level. This problem is investigated and a potential solution is described. It involves opening up the implementation of the delay queue so that application code can be executed directly when the time is right.
Language issues of compiling Ada to hardware
Authors: Ward M. , Audsley N. C.
Published: October 2004

Implementing real-time systems on FPGAs allows for much easier timing analysis. However, not using a von-Neumann architecture for implementation raises issues with the specification of the Ada language.An alternative queuing and blocking policy is presented to allow priorities to be removed from the system. A new method of attaching variables to device registers using ports is presented. Changes to the interrupt handling mechanism made necessary by the freedom given by the change in implementation medium are discussed. These require a new library to provide the changes needed to target the implementation at FPGAs. Ways of indicating fine-grained parallelism at language level are examined to improve the parallelism used in the final circuit.
Asynchronous transfer of control in the real-time specification for java™
Authors: Brosgol Benjamin M. , Hassan Ricardo J. , Robbins Scott
Published: October 2004

The Real-Time Specification for Java provides a facility for Asynchronous Transfer of Control based on exception handling and a generalization of the interrupt() method from the Thread class. This mechanism allows the programming of useful idioms such as timeouts and thread termination without the latency found in polling, and it avoids the problems inherent in the Thread class's stop() and destroy() methods.
The tail & the dog
Authors: Chiasson Mike W.
Published: October 2004

The organizational structure of a new startup 'venture', including its business strategy, is strongly shaped by processes embedded within its developing e-commerce information system. An important question here and in general IS research is the role of individuals (agents) in the shaping and interpreting of both technological and organizational structures (structure). Various questions drawn from Giddens' (1984) structuration theory are used to highlight this agency-structure relationship, and initial results from an action research study within an e-commerce startup involved in developing an on-line "pop culture" magazine are described. Results indicate that at the outset, the e-commerce technology was shaped by two opposing groups within the organization, focused on the business-to-consumer market. Once the system was completed, however, the various agents perceived tremendous business-to-business possibilities in the software. Consequently, they initiated a process to alter their strategic focus, and transformed their organizational processes. Future research directions of this "dog wagging its tail," and "tail wagging the dog" story toward systems development practice and research, and Giddens' structuration theory are discussed. Implications for e-commerce practice and research are discussed.
Comprehensive scheduling controls for Ada tasking
Authors: Elrad T.
Published: October 2004

One of the functions for which Ada needs more expressive power is scheduling control. Scheduling controls provide a mechanism for comprehensive scheduling.

In order to evaluate any concurrent language for its ability to control a multi-events environment, we need to have a general set for classifying all possible controls. Such a classification can exploit the expressive power of any concurrent language, and thus be used to provide us with a priori knowledge regarding the capacity of the language to be used for a specific application. It will also enable us to suggest the best environment for the application at hand. Evaluating Ada against these control capacities will provide us with a scientific approach to the issue of forming an integrated design of comprehensive scheduling controls for Ada.
An interface-based Ada programming support environment
Authors: DeLoach Scott A.
Published: October 2004

Programming Support Environments (PSEs) have recently been the focus of much research directed at producing new methods for developing software more efficiently and reliably. The traditional approach to developing PSEs has been to create a number of novel tools, and then integrate the tools together by adding a common database and modifying the interfaces between the tools until they can work together. Recently, however, it has been recognized that the interfaces between the tools and the rest of the environment are critical, and perhaps more important, than the tools themselves. To be useful in solving the larger problems currently associated with software, a PSE must be able to adapt and provide new capabilities, and be available to a relatively large number of users on a variety of machines.The goal of this research was to determine whether PSEs based on abstract interfaces provide enhanced portability and extensibility over traditionally designed environments. To accomplish this goal, a prototype interface-based PSE was developed and then compared against traditional environments to determine which had better portability and extensibility. First, an interface model was developed to define exactly what types of interface assumptions must be specified to define an appropriate abstract interface. Next, a prototype APSE based on that interface model was designed, specified, and implemented. Finally, this prototype APSE was measured against traditionally designed environments using original environment portability and extensibility metrics.
The design and implementation of a Karel compiler and interpreter
Authors: Hoskins Rose
Published: October 2004

"The Design and Implementation of a Karel Compiler and Interpreter"This paper details the design and implementation of a system which compiles and interprets programs written in Karel, a simple robotic language with significant possibilities as an educational tool for beginning programmers, which system was coded in the Ada programming language. Moreover, the paper also discusses several of the features of Ada which actually facilitated the system design.
Understanding and improving operating system effects in control flow prediction
Authors: Li Tao , John Lizy Kurian , Sivasubramaniam Anand , Vijaykrishnan N. , Rubio Juan
Published: October 2004

Many modern applications result in a significant operating system (OS) component. The OS component has several implications including affecting the control flow transfer in the execution environment. This paper focuses on understanding the operating system effects on control flow transfer and prediction, and designing architectural support to alleviate the bottlenecks. We characterize the control flow transfer of several emerging applications on a commercial operating system. We find that the exception-driven, intermittent invocation of OS code and the user/OS branch history interference increase the misprediction in both user and kernel code.We propose two simple OS-aware control flow prediction techniques to alleviate the destructive impact of user/OS branch interference. The first one consists of capturing separate branch correlation information for user and kernel code. The second one involves using separate branch prediction tables for user and kernel code. We study the improvement contributed by the OS-aware prediction to various branch predictors ranging from simple Gshare to more elegant Agree, Multi-Hybrid and Bi-Mode predictors. On 32K entries predictors, incorporating OS-aware techniques yields up to 34%, 23%, 27% and 9% prediction accuracy improvement in Gshare, Multi-Hybrid, Agree and Bi-Mode predictors, resulting in up to 8% execution speedup.
Energy-efficient computing for wildlife tracking
Authors: Juang Philo , Oki Hidekazu , Wang Yong , Martonosi Margaret , Peh Li Shiuan , Rubenstein Daniel
Published: October 2004

Over the past decade, mobile computing and wireless communication have become increasingly important drivers of many new computing applications. The field of wireless sensor networks particularly focuses on applications involving autonomous use of compute, sensing, and wireless communication devices for both scientific and commercial purposes. This paper examines the research decisions and design tradeoffs that arise when applying wireless peer-to-peer networking techniques in a mobile sensor network designed to support wildlife tracking for biology research.The ZebraNet system includes custom tracking collars (nodes) carried by animals under study across a large, wild area; the collars operate as a peer-to-peer network to deliver logged data back to researchers. The collars include global positioning system (GPS), Flash memory, wireless transceivers, and a small CPU; essentially each node is a small, wireless computing device. Since there is no cellular service or broadcast communication covering the region where animals are studied, ad hoc, peer-to-peer routing is needed. Although numerous ad hoc protocols exist, additional challenges arise because the researchers themselves are mobile and thus there is no fixed base station towards which to aim data. Overall, our goal is to use the least energy, storage, and other resources necessary to maintain a reliable system with a very high `data homing' success rate. We plan to deploy a 30-node ZebraNet system at the Mpala Research Centre in central Kenya. More broadly, we believe that the domain-centric protocols and energy tradeoffs presented here for ZebraNet will have general applicability in other wireless and sensor applications.
Design and evaluation of compiler algorithms for pre-execution
Authors: Kim Dongkeun , Yeung Donald
Published: October 2004

Pre-execution is a promising latency tolerance technique that uses one or more helper threads running in spare hardware contexts ahead of the main computation to trigger long-latency memory operations early, hence absorbing their latency on behalf of the main computation. This paper investigates a source-to-source C compiler for extracting pre-execution thread code automatically, thus relieving the programmer or hardware from this onerous task. At the heart of our compiler are three algorithms. First,
program slicing
removes non-critical code for computing cache-missing memory references, reducing pre-execution overhead. Second,
prefetch conversion
replaces blocking memory references with non-blocking prefetch instructions to minimize pre-execution thread stalls. Finally,
threading scheme selection
chooses the best scheme for initiating pre-execution threads, speculatively parallelizing loops to generate thread-level parallelism when necessary for latency tolerance. We prototyped our algorithms using the Stanford University Intermediate Format (SUIF) framework and a publicly available program slicer, called
Unravel
[13], and we evaluated our compiler on a detailed architectural simulator of an SMT processor. Our results show compiler-based pre-execution improves the performance of 9 out of 13 applications, reducing execution time by 22.7%. Across all 13 applications, our technique delivers an average speedup of 17.0%. These performance gains are achieved fully automatically on conventional SMT hardware, with only minimal modifications to support pre-execution threads.
Enhancing software reliability with speculative threads
Authors: Oplinger Jeffrey , Lam Monica S.
Published: October 2004

This paper advocates the use of a monitor-and-recover programming paradigm to enhance the reliability of software, and proposes an architectural design that allows software and hardware to cooperate in making this paradigm more efficient and easier to program.We propose that programmers write monitoring functions assuming simple sequential execution semantics. Our architecture speeds up the computation by executing the monitoring functions speculatively in parallel with the main computation. For recovery, programmers can define fine-grain transactions whose side effects, including all register modifications and memory writes, can either be committed or aborted under program control. Transactions are implemented efficiently by treating them as speculative threads.Our experimental results suggest that monitored execution is more amenable to parallelization than regular program execution. Code monitoring is sped up by a factor of 1.5 by exploiting single-thread instruction-level parallelism, and by an additional factor of 1.6 using thread-level speculation. This results in an overall improvement of 2.5 times and a sustained 5.4 instructions-per-cycle performance. A monitored execution that used to be 2.5 times slower executes with a degradation of only 12% when compared to the performance on the baseline machine. We also show that the concept of fine-grain transactional programming is useful in catching buffer overrun errors through a number of real-life examples.
A comparative study of arbitration algorithms for the Alpha 21364 pipelined router
Authors: Mukherjee Shubhendu S. , Silla Federico , Bannon Peter , Emer Joel , Lang Steve , Webb David
Published: October 2004

Interconnection networks usually consist of a fabric of interconnected routers, which receive packets arriving at their input ports and forward them to appropriate output ports. Unfortunately, network packets moving through these routers are often delayed due to conflicting demand for resources, such as output ports or buffer space. Hence, routers typically employ
arbiters
that resolve conflicting resource demands to maximize the number of matches between packets waiting at input ports and free output ports. Efficient design and implementation of the algorithm running on these arbiters is critical to maximize network performance.This paper proposes a new arbitration algorithm called
SPAA
(Simple Pipelined Arbitration Algorithm), which is implemented in the Alpha 21364 processor's on-chip router pipeline. Simulation results show that SPAA significantly outperforms two earlier well-known arbitration algorithms: PIM (Parallel Iterative Matching) and WFA (Wave-Front Arbiter) implemented in the SGI Spider switch. SPAA outperforms PIM and WFA because SPAA exhibits matching capabilities similar to PIM and WFA under realistic conditions when many output ports are busy, incurs fewer clock cycles to perform the arbitration, and can be pipelined effectively. Additionally, we propose a new prioritization policy called the
Rotary Rule,
which prevents the network's adverse performance degradation from saturation at high network loads by prioritizing packets already in the network over new packets generated by caches or memory.
Programming language optimizations for modular router configurations
Authors: Kohler Eddie , Morris Robert , Chen Benjie
Published: October 2004

Networking systems such as Ensemble, the
x
-kernel, Scout, and Click achieve flexibility by building routers and other packet processors from modular components. Unfortunately, component designs are often slower than purpose-built code, and routers in particular have stringent efficiency requirements. This paper addresses the efficiency problems of one component-based router, Click, through optimization tools inspired in part by compiler optimization passes. This pragmatic approach can result in significant performance improvements; for example, the combination of three optimizations reduces the amount of CPU time Click requires to process a packet in a simple IP router by 34%. We present several optimization tools, describe how those tools affected the design of Click itself, and present detailed evaluations of Click's performance with and without optimization.
Evolving RPC for active storage
Authors: Sivathanu Muthian , Arpaci-Dusseau Andrea C. , Arpaci-Dusseau Remzi H.
Published: October 2004

We introduce Scriptable RPC (SRPC), an RPC-based framework that enables distributed system services to take advantage of active components. Technology trends point to a world where each component in a system (whether disk, network interface, or memory) has substantial computational capabilities; however, traditional methods of building distributed services are not designed to take advantage of these new architectures, mandating wholesale change of the software base to exploit more powerful hardware. In contrast, SRPC provides a direct and simple migration path for traditional services into the active environment.We demonstrate the power and flexibility of the SRPC framework through a series of case studies, with a focus on active storage servers. Specifically, we find three advantages to our approach. First, SRPC improves the performance of distributed file servers, reducing latency by combining the execution of operations at the file server. Second, SRPC enables the ready addition of new functionality; for example, more powerful cache consistency models can be realized on top of a server that exports a simple NFS-like interface. Third, SRPC simplifies the construction of distributed services; operations that are difficult to coordinate across client and server can now be co-executed at the server, thus avoiding costly agreement and crash-recovery protocols.
A stateless, content-directed data prefetching mechanism
Authors: Cooksey Robert , Jourdan Stephan , Grunwald Dirk
Published: October 2004

Although central processor speeds continues to improve, improvements in overall system performance are increasingly hampered by memory latency, especially for pointer-intensive applications. To counter this loss of performance, numerous data and instruction prefetch mechanisms have been proposed. Recently, several proposals have posited a
memory-side
prefetcher; typically, these prefetchers involve a distinct processor that executes a program slice that would effectively prefetch data needed by the primary program. Alternative designs embody large state tables that learn the miss reference behavior of the processor and attempt to prefetch likely misses.This paper proposes
Content-Directed Data Prefetching,
a data prefetching architecture that exploits the memory allocation used by operating systems and runtime systems to improve the performance of pointer-intensive applications constructed using modern language systems. This technique is modeled after conservative garbage collection, and prefetches "likely" virtual addresses observed in memory references. This prefetching mechanism uses the underlying data of the application, and provides an 11.3% speedup using
no additional processor state.
By adding less than ½% space overhead to the second level cache, performance can be further increased to 12.6% across a range of "real world" applications.
Partial information classes
Authors: Nickelsen Arfst , Tantau Till
Published: October 2004

In this survey we present partial information classes, which have been studied under different names and in different contexts in the literature. They are defined in terms of partial information algorithms. Such algorithms take a word tuple as input and yield a small set of possibilities for its characteristic string as output. We define a unified framework for the study of partial information classes and show how previous notions fit into the framework. The framework allows us to study the relationship of a large variety of partial information classes in a uniform way. We survey how partial information classes are related to other complexity theoretic notions like advice classes, lowness, bi-immunity, NP-completeness, and decidability.
Deconstructing paxos
Authors: Boichat Romain , Dutta Partha , Frølund Svend , Guerraoui Rachid
Published: October 2004

The celebrated Paxos algorithm of Lamport implements a fault-tolerant deterministic service by replicating it over a distributed message-passing system. This paper presents a deconstruction of the algorithm by factoring out its fundamental algorithmic principles within two abstractions: an eventual leader election and an eventual register abstractions. In short, the leader election abstraction encapsulates the liveness property of Paxos whereas the register abstraction encapsulates its safety property. Our deconstruction is faithful in that it preserves the resilience and efficiency of the original Paxos algorithm in terms of stable storage logs, message complexity, and communication steps. In a companion paper, we show how to use our abstractions to reconstruct powerful variants of Paxos.
The architecture of the universe network
Authors: Leslie Ian M , Needham Roger M , Burren John W , Adams Graham C
Published: October 2004

The Universe Network is composed of a number of local area networks at various sites in the U. K., joined by high capacity data links. Apart from one token ring, all of the local area networks are Cambridge rings; the high capacity data links are provided by a 1 Mbit/s satellite broadcast channel. The Universe Project encompasses both the design and implementation of the network, and a program of experiments which make use of the network. One of the notable features of the network is that a host's view of communication over the network is no different from communication over a single ring; no internet protocol is used.
Managed file distribution on the universe network
Authors: Cooper Christopher S
Published: October 2004

The file distribution system on the Universe Network consists of a distributed set of co-operating agents which provide clients with a reliable bulk file collection, transfer and delivery service. The agent systems incorporate specialised techniques for optimizing use of the satellite channel, as well as making available facilities for broadcast file distribution. The distributed system architecture and protocols are described, with emphasis on the separation of control and data transfer. A detailed presentation is given of the way in which agents interact with both hosts and other agents to achieve both reliability and robustness in the face of breaks in host or network availability. A description is given of the special transfer methods used and some of the possible applications for such a system. An indication is given of possible future developments to enable evolution from an experimental to service system.
The satellite transmission protocol of the universe project
Authors: Waters A. Gillian , Adams Christopher J.
Published: October 2004

The Universe network uses a broadcast satellite channel to connect local area networks into a high speed wide area network. The satellite channel is scheduled using a packet TDMA scheme. Time allocation is controlled by one site acting as master, but is based on indications received from each participating site about its own requirements. The TDMA scheduling is thus based not on circuits or the requirements of individual packets, but on a picture of the distributed requirements of the network as a whole. The paper describes the protocol currently implemented on the Universe network and looks forward to a more general way of applying this technique.
Serial link protocol design
Authors: Fletcher John G.
Published: October 2004

There are certain technical design principles for link communication protocols which, if followed, result in a protocol that is less complex in both concept and implementation, but at the same time provides better service, than if the principles are not followed. These principles include modularization into sub-protocols, symmetry between the nodes on the link, and use of the state-exchange model of a conversation rather than the command-response model. The principles are described, the extent to which they are followed by the standard protocol X.25, level 2, is examined, and a protocol adhering to them is presented.
The use of broadcast techniques on the universe network
Authors: Waters A. Gillian , Adams Christopher J. , Leslie Ian M. , Needham Roger M.
Published: October 2004

The Universe network is being used to explore broadcasting techniques in a highly integrated computer communications experiment connecting local area networks via a broadcast satellite channel. The broadcast protocol which has been devised within the Project provides a versatile framework in which different types of broadcast applications can be carried out. The requirements and definition of this protocol are described, and details are given of how the broadcast satellite channel is used and the implementation of the protocols in the system which provides satellite access from each site. Experimental use of the protocol is also described, in particular its use for file distribution. The paper also aims to show how the protocols could be used for more advanced applications.
Petri nets are good for protocols
Authors: Courtiat J. P. , Ayache J. M. , Algayres B.
Published: October 2004

This paper is intended to survey the applicability of Petri nets for protocol, as well as for service specification and validation. At the specification level, different classes of nets are introduced, and emphasis is given to the modular specification of a protocol layer. At the validation level, the analysis techniques implemented in the CAD package OGIVE/OVIDE are presented, and are used in order to prove safety and progress properties of a protocol layer. Finally, the specification and validation of the ISO Transport protocol is chosen as a significant example of the proposed design methodology.
Automated verification of connection management of NBS class 4 transport protocol
Authors: Sidhu Deepinder P. , Blumer Thomas P.
Published: October 2004

In a recent paper, the authors discussed verification of the connection management aspects of the NBS Class 4 transport protocol. An automated protocol development technique was used to verify a subset of the protocol with respect to the protocol properties of completeness, deadlock freeness, livelock freeness, boundedness, and termination. The analysis pointed out several error situations in which the completeness property did not hold for the protocol. This note summarizes the results of the automated analysis and also proposes some plausible solutions to the problems identified in the current specification.
A method of automatic proof for the specification and verification of protocols
Authors: Cavalli Ana R.
Published: October 2004

In this paper we apply a method of automatic proof to verify some properties of a computer network protocol. The method used is defined as an extension of classical resolution to temporal operators (@@@@), (@@@@), (@@@@) and
Until
. We define a
Precedes
operator that is very useful for the specification of protocols. The method has the form of a set of recursive rules. The examples that we give are FIFO and LIFO queues and the alternating bit protocol, and the properties that we verify are livennes properties of the Sender and Receiver processes in order to prove a liveness property of the global system.
A temporal ordering specification of some session services
Authors: Carchiolo Vincenza , Faro Alberto , Scollo Giuseppe
Published: October 2004

The achievement of widely accepted standards for Open Systems Interconnection (OSI) is closely tied to the ability of producing unambiguous and implementation independent specifications of related protocols and services. LOTOS, the
L
anguage f
O
r
T
emporal
O
rdering
S
pecification, is a Formal Description Technique (FDT) whose definition, though not completed, has already reached such a state as to allow trial specifications of rather sophisticated services and protocols. This paper explores the specification in LOTOS of some of the session services whose discussion is underway within various standardization bodies. Conciseness of specification is tried by adopting a few notational variants which are guessed to be useful at various OSI layers. The session services selected for this trial specification comprise the Basic Combined Subset (BCS) enriched with the Expedited Data service.
Factors affecting the performance of distributed applications
Authors: Lantz Keith A. , Nowicki William I. , Theimer Marvin M.
Published: October 2004

A major reason for the rarity of distributed applications, despite the proliferation of networks, is the sensitivity of their performance to various aspects of the network environment. Contrary to much popular opinion, we demonstrate that CPU speed remains the predominant factor. With respect to network issues, we focus on two approaches to performance enhancement: (1) Improving the performance of reliable, byte-stream protocols such as TCP; (2) the use of high-level protocols that reduce the frequency and volume of communication.
A performance model for hardware/software issues in computer-aided design of protocol systems
Authors: Woodside C. M. , Montealegre R. , Buhr R. J. A.
Published: October 2004

Protocol execution can run into bottlenecks which are due to implementation decisions rather than to the protocol rules. The performance effects of processor saturation, buffer management strategy, allocation of functions between host and front-end, and hardware-software interactions due to special hardware attributes can, in principle, be predicted at the design stage by analytic performance models. The paper describes the process of construction of such a model for the data transfer stage of a simple transport protocol resembling an OSI class 4 protocol, including queueing for critical sections which protect the buffer pools and connection state information. The model is part of a computer-aided design process for communications systems, currently under development.
Automatic update of replicated topology data bases
Authors: Jaffe Jeffrey M. , Segall Adrian
Published: October 2004

In computer communication networks, routing is often accomplished by maintaining copies of the network topology and dynamic performance characteristics in various network nodes. The present paper describes an algorithm that allows complete flexibility in the placement of the topology information. In particular, we assume that an arbitrary subset of network nodes are capable of maintaining the topology. In this environment, protocols are defined to allow automatic updates to flow between these more capable nodes. In addition, protocols are defined to allow less capable nodes to report their topology data to the major nodes, and acquire route information from them.
Automated testing of protocol specifications and their implementations
Authors: Ural H. , Probert R. L.
Published: October 2004

A highly automated approach is proposed for validating the consistency of distinct representations of an identical software functionality. This approach is based on checking whether the observable behaviors presented by software functionality representations given in different levels of abstraction are consistent with one another. These representations are encoded in a relatively mechanical way as procedures in sequential PROLOG, a very high level language. The approach is extremely flexible, straight-forward to use, and particularly appropriate to layered protocol architectures. As well, the approach leads to more reliable and less tedious, less error-prone test harness construction and maintenance. A number of variations and extensions of the approach are given. The use of this approach is illustrated in the context of communication protocols design and evaluation.
Performance analysis of an access method suitable for the integration of voice and data
Authors: Behr J. P. , Killat U.
Published: October 2004

This contribution describes a new type of an integrated system's architecture which reconciles the diverging needs of both, stream traffic of 64 kbit/s and bursty traffic of low and high data rates.

The total capacity of a unidirectional bus is subdivided into a high-speed channel and a certain number of time slots for stream traffic.

The capacity of the high-speed channel can dynamically be adjusted according to the amount of time slots required for stream traffic. Due to the dynamic creation and deletion of time slots, the subsystem for 64-kbit/s channels is almost blocking-free.

The same mechanism is used to control access to the high-speed channel, and to determine the fraction of the total capacity dedicated to the high-speed channel.

The performance of the proposed access mechanism has been investigated by means of system modelling and simulation. The results show that besides its ability to accommodate 64-kbit/s channels it compares quite favourably with other LAN concepts like CSMA/CD.
Some critical considerations on the ISO/OSI RM from a network implementation point of view
Authors: Popescu-Zeletin R.
Published: October 2004

The paper outlines the conceptual and practical aspects encountered in the design and implementation of a heterogeneous computer network based on the standardization output.

We discuss the feasability of the reference model and its related standards from a design, implementation and operational point of view focussing on the adopted solutions and their rationales.
Communication primitives supporting the execution of atomic actions at remote sites
Authors: Rothermel Kurt
Published: October 2004

A request manager is described that provides a set of communication primitives supporting the cooperation between processes requesting service and processes providing service. These communication primitives allow the initiation and termination of atomic actions at remote sites. They also maintain recoverable action state tables, which can be used to recall uncompleted actions during restart recovery. The presented request manager is a good foundation on which to develop application oriented high-level primitives as well as language level primitives.

Besides a detailed description of the services offered by the request manager, the paper develops a request management protocol that, no matter what happens, insures the atomic property of actions. Evaluation nets, which are a modified form of Petri nets, are applied to describe this protocol.
On the performance of slotted ALOHA in a spread spectrum environment
Authors: Economopoulos Panos , Molle Mart L.
Published: October 2004

We present an extension of the slotted ALOHA protocol for use in a spread spectrum packet radio environment. With spread spectrum, we assume that
N
distinct codes are available, and that each code can be treated as a separate channel. Running an independent copy of the protocol on each of these channels would be undesirable, since each user would have to select one channel to monitor for packets addressed to it, inducing a logical partitioning of the user population into
N
groups. To preserve the logical connectivity of the network, we examine the effect of separating packet transmissions into two parts, a short
preamble,
which is sent over a public channel, and followed by the
body,
> which is sent over a private channel. We assume that
m
of the available codes are used as preamble channels, and the remaining
N - m
codes are used for actual packet transmissions. If
m (@@@@) N
, then the network can support broadcast and multicast packets, and still make use of all of the available channels.
Some issues in protocol implementation testing
Authors: Cerny E.
Published: October 2004

Communication between various makes of communication equipment and across international boundaries is becoming easier due to the continuing development of international standards on communication protocols, such as those defined by ISO for Open Systems Interworking (OSI). Although the agreement to use standard protocols by the various parties involved is the first necessary step towards OSI, it is not sufficient without assuring that the protocols be correctly implemented in the communication equipment.

The assessment of the adherence of a communication protocol implementation to its specification relies on testing as its main tool. The development of the tests and their application (the architecture of the test system) have properties and constraints which make them different from those currently created for testing hardware and software systems.

In the remainder of the presentation, these constraints and problems as related to the successful development of a protocol test system will be reviewed. They will be separated into those aspects which pertain more to the form of the test support system (the system architecture), and to those which influence the selection of effective test interaction sequences. This division is slightly arbitrary, for some of the issues have effect on both of the above components of the test system.
The organizational consequences of office automation: refining measurement techniques
Authors: Morell Jonathan A.
Published: October 2004

Data is reported regarding the impact of personal computer use in the Naval Military Personnel Command. The emphasis is on furthering knowledge of variables which may be affected by the introduction of office automation, and of how those variables might be measured. Particular attention was paid to the problem of abstracting generalizable measures from descriptions of what people did with their computers.Analysis of results revealed six general categories of impact, each with several specific, measurable indicators. The general categories include: budgeting, information for planning or administration, amount of time saved, uses of time saved, "information creation", and communication. Examples of measurable indicators of each category are: budgeting - percent of allocated budget spent within a fiscal year; planning and administration- currency of available data; use of time saved accomplishment of new tasks; information creation - development of "private" data bases; and communication - development of "private" data bases; and communication - expectations concerning data that should be available.The intent is to demonstrate that an effort to measure the impact of office automation can be successful, and to urge others to undertake similar analyses with other data sets. Together, such efforts would lead to much improved understanding of how office automation affects activity within organizations.
Organizational issues of end-user computing
Authors: Amoroso Donald L.
Published: October 2004

End-user computing environments are rapidly growing in many organizations. This growth is due primarily to the proliferation of microcomputers and the availability of user-friendly software. However, the end-user computing environment is still poorly understood by practitioners, academics, and vendors. Most managers agree that a basic understanding of the end-user computing environment is necessary in order to effectively manage it. This article attempts to define the scope of the end-user computing and integrate a variety of publications into a common research framework. Several managerial frameworks are presented which address the risks of end-user development. Finally, implications are drawn from the available literature in order to provide managerial direction to firms with growing end-user computing environments.
Plugging the holes in the sieve of eratosthenes
Authors: Dritc K.
Published: October 2004

Several subtle errors in an Ada tasking realization of the well-known Sieve of Eratosthenes algorithm are revealed and corrected. By discussing them here, we hope to increase the tutorial value of the original publication (G. E. Anderson in
Ada Letters
, September/October 1988).
Ada on a hypercube
Authors: Clapp R. , Mudge T.
Published: October 2004

The widespread use of parallel machines, and hypercubes in particular, is being held back by the lack of high-order parallel programming languages. In this paper we discuss the issues involved in establishing an existing language that supports parallel processing, Ada, on a hypercube multiprocessor. The majority of the paper addresses the requirements and implementation of the run-time system, which is the key to establishing any parallel language. First, the requirements of the run-time system for Ada are described from a machine-independent point of view. Next, the approach taken toward implementing this system on a hypercube is discussed, with considerations given for language-level program partitioning and interprocessor communication performance. Finally, the status of our current implementation is discussed and some concluding remarks are made about parallel languages in general, based on our experiences.
Wiretap: an experimental multiple-path routing algorithm
Authors: Mills David L.
Published: October 2004

This paper introduces Wiretap, an experimental routing algorithm which computes maximum-likelihood diversity routes for packet-radio stations sharing a common broadcast channel, but with some stations hidden from others. The wiretapper observes the paths (source routes) used by other stations sending traffic on the channel and, using a heuristic set of factors and weights, constructs speculative paths for its own traffic. The algorithm is presented as an example of maximum-likelihood routing and database management techniques useful for richly connected networks of mobile stations. Of particular interest are the mechanisms to compute, select, rank and cache a potentially large number of speculative routes when only limited computational resources are available.A prototype implementation has been constructed and tested for the AX.25 packet-radio channel now in widespread use in the amateur-radio community. Its design is similar in many respects to the SPF algorithm used in the ARPANET and NSFNET backbone networks, and is in fact a variation of the Viterbi algorithm, which constructs maximum-likelihood paths on a graph according to a weighted sum of factors assigned to the nodes and edges.
Security in a secure capability-based system
Authors: Landau Charles R.
Published: October 2004

Capability-based systems such as KeyKOS support mandatory and discretionary security policies without identifying the source of every request. Some misconceptions about such systems are clarified.
An efficient reliable broadcast protocol
Authors: Kaashoek M. Frans , Tanenbaum A. S. , Hummel S. F.
Published: October 2004

Many distributed and parallel applications can make good use of broadcast communication. In this paper we present a (software) protocol that simulates reliable broadcast, even on an unreliable network. Using this protocol, application programs need not worry about lost messages. Recovery of communication failures is handled automatically and transparently by the protocol. In normal operation, our protocol is more efficient than previously published reliable broadcast protocols. An initial implementation of the protocol on 10 MC68020 CPUs connected by a 10 Mbit/sec Ethernet performs a reliable broadcast in 1.5 msec.
The need for closure in large distributed systems
Authors: Neuman B. C.
Published: October 2004

As the size of a distributed system grows it becomes increasingly difficult for users to find their way around. One solution for this problem is user centered naming. A problem with user centered naming is that it has the potential to cause confusion and to make sharing difficult. This problem can be avoided if the system supports closure. Although the same name may refer to different objects at different times, the context in which the name is to be evaluated is always known.
The MARUTI hard real-time operating system
Authors: Levi S. , Tripathi S. K. , Carson S. D. , Agrawala A. K.
Published: October 2004

The MARUTI operating system is designed to support real-time applications on a variety of hardware systems. The kernel supports objects as primitive entities, and provides a communication mechanism that allows transparent distribution in networked systems. Fault tolerance is provided through replication and consistency-control mechanisms. Most importantly, MARUTI supports guaranteed-service scheduling, in which jobs that are accepted by the system are verified to satisfy general time constraints.Guaranteed-service scheduling means that, given a job with a set of service requirements and time constraints, the system automatically verifies the schedulability of each component of the job with respect to the job's constraints and those of other jobs in the system. These time constraints include those that govern interrupt processing, which allows the MARUTI approach to succeed where tess rigorous approaches do not. The result is that MARUTI applications can be executed in a predictable, deterministic fashion.