bluuebunny/crossref_metadata_2025 huggingface dataset:
Two approaches to teaching software components using Ada 95
Authors: Gibson David S.
Published: October 2004

Abstract data types (ADTs) have been used for many years to teach the specification and implementation of software components. With the advent of object-oriented programming languages (OOPLs), many ADT specifications and implementations are now encoded in OOPLs as classes. OOPLs typically provide a variety of language mechanisms that support data abstraction and make classes convenient for encoding ADT specifications and implementations. In particular, the inheritance mechanism supported by OOPL classes provides useful ways of relating ADT specifications and implementations. The Ada programming language has always provided solid support for specification and implementation of ADTs with its package construct. The 1995 revision to Ada (Ada 95) added a variety of powerful new language mechanisms such as tagged types (full-fledged inheritance), abstract types, and hierarchical library units. Each of these new Ada language mechanisms, in addition to packages, can be used in various combinations to support the specification, implementation, and extension of ADTs. In this paper, we compare two approaches used to teach to second-year undergraduates specification and implementation of software components in Ada. The first approach is a traditional Ada approach relying solely on the package mechanism to support data abstraction. The second approach relies heavily on Ada's newer object-oriented language mechanisms in addition to hierarchical library units.
A laboratory study of consumers' preferences and purchasing behavior with regards to software components
Authors: Hong Se-Joon , Lerch F. Javier
Published: October 2004

Component-based software development is widely regarded as a promising approach to improving productivity and quality. However, progress in component-based software development has been slower than expected. A possible explanation for this slow progress is that there are not enough software components that can satisfy users (consumers). From this perspective, the purpose of this paper is to increase our knowledge about consumers of software components and to understand what aspects of software components are likely to affect consumer behavior. Specifically, this paper seeks to establish links between objective features of software components and consumers' preferences and purchasing behavior.The pragmatic utility of using objective features as predictors of consumers' behavior in regard to software components can be high. Since these objective features are under the direct control of producers, by understanding the relationship between the objective features and consumer behavior, producers can more effectively develop software components adapted to consumers' needs. We conducted this research in an artificial environment using a system called SofTrade, which was built for the purpose of teaching and studying the design, production, marketing, and purchasing of software components. Our results suggest that objective features of software components can be effective predictors of consumers' preferences and purchasing behavior, and therefore may provide practical guidance to software component producers regarding how to develop more marketable software components.
Provisioning on-line games
Authors: Chang Francis , Feng Wu-chang , Feng Wu-chi , Walpole Jonathan
Published: October 2004

This poster describes the results of a 500 million packet trace of a popular on-line, multiplayer, game server. The results show that the traffic behavior of this heavily loaded game server is highly predictable and can be attributed to the fact that current game designs target the saturation of the narrowest, last-mile link (i.e. 56k modems). Specifically, in order to maximize the interactivity of the game itself and to provide relatively uniform experiences between players playing over different network speeds, on-line games typically fix their usage requirements in such a way as to saturate the network link of their lowest speed players. While the traffic observed is highly predictable, the trace also indicates that these on-line games provide significant challenges to current network infrastructure. As a result of synchronous game logic requiring an extreme amount of interactivity, a close look at the trace reveals the presence of large, highly periodic, bursts of small packets. With such stringent demands on interactivity, routers must be designed with enough capacity to quickly route such bursts without delay. As current routers are designed for bulk data transfers with larger packets, a significant, concentrated deployment of on-line game servers will have the potential for overwhelming current networking equipment.
Communication complexity for file synchronization is undecidable
Authors: Gupta Vijay Shivshanker
Published: October 2004

Wide-area wireless mobile computing environments present interesting challenges for the problem of file synchronization between laptop computers and servers in backbone networks. Wide-area wireless networks are bandwidth-constrained and expensive, thereby making it difficult to synchronize the files in an eager fashion. The problem of file synchronization for laptop computers has been actively studied for more than a decade, and one of the most intriguing questions has been "how little communication is sufficient for file synchronization?" Technically, this is equivalent to the question: "what is the communication complexity for file synchronization?" This article proves the undecidability of the communication complexity for update propagation in a replicated file system if one is willing to transmit operation-based updates.
ACM SIGACT news distributed computing column 8
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 "Distributed Computing Research Issues in Grid Computing" by Henri Casanova. Many thanks to Henri for contributing to this issue.
Simple authenticated key agreement protocol resistant to password guessing attacks
Authors: Yeh Her-Tyan , Sun Hung-Min
Published: October 2004

Password-based mechanism is the widely used method for user authentication. Many password-based authenticated key exchange protocols have been proposed to resist password guessing attacks. In this paper, we present a simple authenticated key agreement protocol called
SAKA
which is simple and cost-effective. To examine its security, we provide a formal proof of security to show its strength against both passive and active adversaries. Compared with the previously best protocols,
SAKA
has less number of steps and less computation cost.
On the value of threshold signatures
Authors: Borselius Niklas , Mitchell Chris J. , Wilson Aaron
Published: October 2004

Threshold signature schemes are examples of threshold cryptosystems, as introduced by Desmedt, [4]. The purpose of this paper is to present a rather simple alternative to threshold signatures which raises questions about the value of such schemes, at least when applied to the mobile agent scenario.
STFS
Authors: Jun Lu , Xianliang Lu , Guangchun Luo , Hong Han , Xu Zhou
Published: October 2004

This paper presents a novel high performance file system: Same Track File System (STFS) based on the researches of the character of modern disk drive. This paper firstly analyses the non-linear seek latency character of modern disk drive, and then indicates the drawback of FFS due to small writes. Then, this paper describes a novel disk layout of STFS: putting the meta-data and data into the same track. This disk layout of STFS can effectively depress the seek overhead of small writes and greatly improve file system throughput. The experiments of this paper show that STFS is a high performance file system.
Using Ravenscar to support fault-tolerant real-time applications
Authors: Pinho Luís Miguel , Vasques Francisco
Published: October 2004

Recently, a framework was proposed intended to support the development of replicated and distributed Ravenscar applications. This framework provides a transparent abstraction for application replication, allowing applications to be developed without considering replication and distribution issues. However, it is also necessary to assess if the Ravenscar profile is expressive enough for the implementation of this complex middleware. Therefore, this paper presents some conclusions that were drawn on the implementation of a prototype of the framework.
Protected ceiling changes
Authors: Real Jorge , Crespo Alfons , Wellings Andy , Burns Alan
Published: October 2004

The inclusion of dynamic ceiling priorities in Ada is a topic of discussion in the Real-Time Ada community. Several approaches have been discussed in previous editions of the International Real-Time Ada Workshop, which have allowed to identify the problems associated with this issue, mainly the interaction of such feature with tasking, consistency and efficiency of implementation. In this paper, a new approach for dynamic ceilings is presented. It is based on implementing the ceiling change as a predefined protected operation itself, which allows to eliminate the potential for data corruption that other approaches introduce, without the need for additional locks.The paper also discusses the use of the proposed operation in the context of mode changes.
From the chair
Authors: Sipior Janice C. , Schatzberg Laurie , Leidner Dorothy , Niederman Fred , Lending Diane
Published: October 2004

Greetings to SIGMIS members and a warm welcome to CPR (Computer Personnel Research) members!As you know, our merger with SIGCPR became official in July 2002. Please join in welcoming CPR members at "The Second Annual ACM-SIGMIS Reception: A Special Welcome to CPR," to be held as an ACM-SIGMIS event prior to the International Conference on Information Systems (ICIS2002) in Barcelona, Spain, December 15 - 18, 2002. Light refreshments will be served.Finally, I would like to extend a warm thank you to our Information Director, Parag C. Pendharkar who worked very hard at maintaining our SIGMIS website. I would like to take this opportunity to introduce and welcome Diane Lending as the newly appointed Information Director.We encourage and welcome your active participation in SIGMIS. Should you wish to volunteer, provide suggestions or other input, please feel free to contact any one of us. We look forward to seeing you in Barcelona!
Product and project challenges in electronic commerce software development
Authors: Hevner Alan R. , Collins Rosann W. , Garfield Monica J.
Published: October 2004

Electronic commerce (E-commerce) software development organizations face unique challenges based on rapidly changing markets, demanding customers with ill-defined requirements, and resulting priority conflicts between product line development and customer projects. A model of this unique development environment is identified with important linkages among the product function, the project function, and the underlying software development function within an organization. Guided by this model of the E-commerce development environment, a case study of a medium-sized E-commerce company was conducted. Based on this study, eight critical challenges to the successful development of top quality software systems are identified. From these challenges a research model and propositions are presented. As each challenge is discussed unique impacts of the E-commerce environment are reinforced by direct quotes from in-depth interviews. On-going research will draw upon the research model and propositions to provide insights on how best to develop software products and deliver customer projects in E-commerce environments.
ACM SIGACT news distributed computing column 9
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 "Incentives and Internet Computation" by Joan Feigenbaum and Scott Shenker. Many thanks to them for contributing to this issue.
Software products framework for diagnosing network problems
Authors: MacInnes Alan
Published: October 2004

This paper presents an overview of major functional components that should be considered for inclusion as part of a network software product. These functional components support the activity of diagnosing problems in the network environment.
Speculative synchronization
Authors: Martínez José F. , Torrellas Josep
Published: October 2004

Barriers, locks, and flags are synchronizing operations widely used programmers and parallelizing compilers to produce race-free parallel programs. Often times, these operations are placed suboptimally, either because of conservative assumptions about the program, or merely for code simplicity.We propose
Speculative Synchronization,
which applies the philosophy behind Thread-Level Speculation (TLS) to explicitly parallel applications. Speculative threads execute past active barriers, busy locks, and unset flags instead of waiting. The proposed hardware checks for conflicting accesses and, if a violation is detected, offending speculative thread is rolled back to the synchronization point and restarted on the fly. TLS's principle of always keeping a
safe thread
is key to our proposal: in any speculative barrier, lock, or flag, the existence of one or more safe threads at all times guarantees forward progress, even in the presence of access conflicts or speculative buffer overflow. Our proposal requires simple hardware and no programming effort. Furthermore, it can coexist with conventional synchronization at run time.We use simulations to evaluate 5 compiler- and hand-parallelized applications. Our results show a reduction in the time lost to synchronization of 34% on average, and a reduction in overall program execution time of 7.4% on average.
Automatically characterizing large scale program behavior
Authors: Sherwood Timothy , Perelman Erez , Hamerly Greg , Calder Brad
Published: October 2004

Understanding program behavior is at the foundation of computer architecture and program optimization. Many programs have wildly different behavior on even the very largest of scales (over the complete execution of the program). This realization has ramifications for many architectural and compiler techniques, from thread scheduling, to feedback directed optimizations, to the way programs are simulated. However, in order to take advantage of time-varying behavior, we must first develop the analytical tools necessary to automatically and efficiently analyze program behavior over large sections of execution.Our goal is to develop automatic techniques that are capable of finding and exploiting theLarge Scale Behaviorof programs (behavior seen over billions of instructions). The first step towards this goal is the development of a hardware independent metric that can concisely summarize the behavior of an arbitrary section of execution in a program. To this end we examine the use ofBasic Block Vectors.We quantify the effectiveness of Basic Block Vectors in capturing program behavior across several different architectural metrics, explore the large scale behavior of several programs, and develop a set of algorithms based on clustering capable of analyzing this behavior. We then demonstrate an application of this technology to automatically determine where to simulate for a program to help guide computer architecture research.
Bytecode fetch optimization for a Java interpreter
Authors: Ogata Kazunori , Komatsu Hideaki , Nakatani Toshio
Published: October 2004

Interpreters play an important role in many languages, and their performance is critical particularly for the popular language Java. The performance of the interpreter is important even for high-performance virtual machines that employ just-in-time compiler technology, because there are advantages in delaying the start of compilation and in reducing the number of the target methods to be compiled. Many techniques have been proposed to improve the performance of various interpreters, but none of them has fully addressed the issues of minimizing redundant memory accesses and the overhead of indirect branches inherent to interpreters running on superscalar processors. These issues are especially serious for Java because each bytecode is typically one or a few bytes long and the execution routine for each bytecode is also short due to the low-level, stack-based semantics of Java bytecode. In this paper, we describe three novel techniques of our Java bytecode interpreter,
write-through top-of-stack caching (WT), position-based handler customization (PHC), and position-based speculative decoding (PSD),
which ameliorate these problems for the PowerPC processors. We show how each technique contributes to improving the overall performance of the interpreter for major Java benchmark programs on an IBM POWER3 processor. Among three, PHC is the most effective one. We also show that the main source of memory accesses is due to bytecode fetches and that PHC successfully eliminates the majority of them, while it keeps the instruction cache miss ratios small.
Maté
Authors: Levis Philip , Culler David
Published: October 2004

Composed of tens of thousands of tiny devices with very limited resources ("motes"), sensor networks are subject to novel systems problems and constraints. The large number of motes in a sensor network means that there will often be some failing nodes; networks must be easy to repopulate. Often there is no feasible method to recharge motes, so energy is a precious resource. Once deployed, a network must be reprogrammable although physically unreachable, and this reprogramming can be a significant energy cost.We present Maté, a tiny communication-centric virtual machine designed for sensor networks. Maté's high-level interface allows complex programs to be very short (under 100 bytes), reducing the energy cost of transmitting new programs. Code is broken up into small capsules of 24 instructions, which can self-replicate through the network. Packet sending and reception capsules enable the deployment of ad-hoc routing and data aggregation algorithms. Maté's concise, high-level program representation simplifies programming and allows large networks to be frequently reprogrammed in an energy-efficient manner; in addition, its safe execution environment suggests a use of virtual machines to provide the user/kernel boundary on motes that have no hardware protection mechanisms.
Enabling trusted software integrity
Authors: Kirovski Darko , Drinić Milenko , Potkonjak Miodrag
Published: October 2004

Preventing execution of unauthorized software on a given computer plays a pivotal role in system security. The key problem is that although a program at the beginning of its execution can be verified as authentic, while running, its execution flow can be redirected to externally injected malicious code using, for example, a buffer overflow exploit. Existing techniques address this problem by trying to detect the intrusion at run-time or by formally verifying that the software is not prone to a particular attack.We take a radically different approach to this problem. We aim at intrusion prevention as the core technology for enabling secure computing systems. Intrusion prevention systems force an adversary to solve a computationally hard task in order to create a binary that can be executed on a given machine. In this paper, we present an exemplary system--SPEF--a combination of architectural and compilation techniques that ensure software integrity at run-time. SPEF embeds encrypted, processor-specific constraints into each block of instructions at software installation time and then verifies their existence at run-time. Thus, the processor can execute only properly installed programs, which makes installation the only system gate that needs to be protected. We have designed a SPEF prototype based on the ARM instruction set and validated its impact on security and performance using the MediaBench suite of applications.
ECOSystem
Authors: Zeng Heng , Ellis Carla S. , Lebeck Alvin R. , Vahdat Amin
Published: October 2004

Energy consumption has recently been widely recognized as a major challenge of computer systems design. This paper explores how to support energy as a first-class operating system resource. Energy, because of its global system nature, presents challenges beyond those of conventional resource management. To meet these challenges we propose the Currentcy Model that unifies energy accounting over diverse hardware components and enables fair allocation of available energy among applications. Our particular goal is to extend battery lifetime by limiting the average discharge rate and to share this limited resource among competing task according to user preferences. To demonstrate how our framework supports explicit control over the battery resource we implemented ECOSystem, a modified Linux, that incorporates our currentcy model. Experimental results show that ECOSystem accurately accounts for the energy consumed by asynchronous device operation, can achieve a target battery lifetime, and proportionally shares the limited energy resource among competing tasks.
Joint local and global hardware adaptations for energy
Authors: Sasanka Ruchira , Hughes Christopher J. , Adve Sarita V.
Published: October 2004

This work concerns algorithms to control energy-driven architecture adaptations for multimedia applications, without and with dynamic voltage scaling (DVS). We identify a broad design space for adaptation control algorithms based on two attributes: (1) when to adapt or
temporal
granularity and (2) what structures to adapt or
spatial
granularity. For each attribute, adaptation may be
global
or
local.
Our previous work developed a temporally and spatially global algorithm. It invokes adaptation at the granularity of a full frame of a multimedia application (temporally global) and considers the entire hardware configuration at a time (spatially global). It exploits int
er-
frame execution time variability, slowing computation just enough to eliminate idle time before the real-time deadline.This paper explores temporally and spatially local algorithms and their integration with the previous global algorithm. The local algorithms invoke architectural adaptation within an application frame to exploit int
ra-
frame execution variability, and attempt to save energy without affecting execution time. We consider local algorithms previously studied for non-real-time applications as well as propose new algorithms. We find that, for systems without and with DVS, the local algorithms are effective in saving energy for multimedia applications, but the new integrated global and local algorithm is best for the systems and applications studied.
Dynamic dead-instruction detection and elimination
Authors: Butts J. Adam , Sohi Guri
Published: October 2004

We observe a non-negligible fraction--3 to 16% in our benchmarks--of
dynamically dead instructions,
dynamic instruction instances that generate unused results. The majority of these instructions arise from static instructions that also produce useful results. We find that compiler optimization (specifically instruction scheduling) creates a significant portion of these
partially dead
static instructions. We show that most of the dynamically instructions arise from a small set of static instructions that produce dead values most of the time.We leverage this locality by proposing a dead instruction predictor and presenting a scheme to avoid the execution of predicted-dead instructions. Our predictor achieves an accuracy of 93% while identifying over 91% of the dead instructions using less than 5 KB of state. We achieve such high accuracies by leveraging future control flow information (i.e., branch predictions) to distinguish between useless and useful instances of the same static instruction.We then present a mechanism to avoid the register allocation, instruction scheduling, and execution of predicted dead instructions. We measure reductions in resource utilization averaging over 5% and sometimes exceeding 10%, covering physical register management (allocation and freeing), register file read and write traffic, and data cache accesses. Performance improves by an average of 3.6% on an architecture exhibiting resource contention. Additionally, our scheme frees future compilers from the need to consider the costs of dead instructions, enabling more aggressive code motion and optimization. Simultaneously, it mitigates the need for good path profiling information in making inter-block code motion decisions.
An exercise in constructing multi-phase communication protocols
Authors: Chow C. H. , Gouda M. G. , Lam S. S.
Published: October 2004

Many real-life protocols can be observed to go through different phases performing a distinct function in each phase. We present a multi-phase model for such protocols. A phase is formally defined to be a network of communicating finite state machines with certain desirable correctness properties; these include proper termination, and freedom from deadlocks and unspecified receptions. A multi-function protocol is constructed by first constructing separate phases to perform its different functions. We discuss how to connect these phases together to implement the multi-function protocol such that the resulting network of communicating finite state machines is also a phase (i.e. it possesses the desirable properties defined for phases). A high-level session control protocol modeled after one in IBM's Systems Network Architecture is discussed, and constructed as a multi-phase protocol.
One-to-many interprocess communication in the V-system
Authors: Cheriton David R. , Zwaenepoel Willy
Published: October 2004

Interprocess communication (IPC) normally allows one process to communicate with only one other process at a time. One-to-many IPC allows one process to communicate simultaneously with a
group
of processes., possibly of unknown membership. While the broadcast and multicast facilities of local networks support efficient one-to-many communication between
hosts
, its use between
processes
has been limited by the lack of support in the distributed operating system. This paper describes the integration of one-to-many communication into V interprocess communication system. We discuss the different models of use and the reliability and present some initial applications.
Formal specification and validation of ISO transport protocol components, using petri nets
Authors: JÜrgensen Wolfgang , Vuong Son T.
Published: October 2004

In this paper, we provide the Petri net formal specifications of three important components of the ISO transport protocol: timeout mechanism, data transfer phase and connection establishment and release phases. A validation of these component Petri net specifications is then presented, followed by a discussion of its results.

The validations we conducted made use of a software tool based on OGIVE [1], which can check a given Petri net for general properties such as boundedness, properness and liveness, and designer defined structural properties using Petri net invariants.

We have extended OGIVE to allow for the checking of reception errors and state ambiguities as well.
Some operational tools in a OSI protocols study environment
Authors: Ansart J. P. , Rafiq O. , Castanet R. , Guitton P.
Published: October 2004

This paper deals with a strategy for a development chain of protocols (specification, validation, conformity testing) based on knowledge of the RHIN project methodology and the tools which this project produced. This methodology is based on finite state machines with predicates and includes “conceptual” tools for specification (PDIL)and for validation (VADILOC). “Experimental” tools play a part in conformity testing (STQ, Cerbere, Genepi). The interaction between conceptual and experimental tools is provided by a test sequence generator GAST which, starting from an automaton whose communication has been validated, provides sequences to be used by the test tools.
Analysis of channel access schemes for high-speed LANs
Authors: Pedersen Niels Nørup , Sharp Robin
Published: October 2004

A series of simulation studies into channel access protocols suitable for use in local area networks operating in baseband mode at bit rates of 100 Mbit/s or more is presented, and the usefulness of these protocols for supporting data transmission with mixed traffic is discussed.
Twentenet
Authors: Niemegeers I. G. , Vissers C. A.
Published: October 2004

This paper discusses design and performance aspects of Twentenet, one of the few implemented LANs which offers a service based on message priorities. The medium access mechanism uses the CSMA/CD principle, however with a deterministic collision resolution method. These characteristics make Twentenet suitable for real-time applications, as well as a mixture of real-time and non real-time applications. The general system structure is introduced followed by a detailed description of the priority access method. The performance of the system is shown for various traffic conditions and distributions of message priorities. The effect of system parameters, such as transmission rate, message length, cable length, and retry limits, is indicated.
A minimal duplex connection capability in the top three layers of the OSI reference model
Authors: Dolan M. F.
Published: October 2004

A minimal duplex connection capability is described as the ability to open, close, abort, and transfer data through a duplex connection between two application processes. The goal of this paper is to describe a minimal duplex connection capability for the top three layers of the Open Systems Interconnection (OSI) Reference Model that will be appropriate for use by very small Open Systems such as home computers. Such a connection capability would allow these small systems to interconnect with machines of arbitrary size. The approach taken is to use only the parameters on service primitives that are absolutely required to accomplish this connection service. The protocol and services necessary to accomplish such a minimal connection are described for the application, presentation, and session layers of the OSI Reference Model. The existing draft proposals for services and protocol for the session layer provide a basis for this duplex connection service. A minor modification to the session draft proposals is suggested. The services for the presentation and application layer are defined in terms of the tentative service primitives being considered in the international standards efforts. The transparent initial context defined for the presentation layer is used to minimize the work of that layer. The benefits of this minimal duplex connection capability are then discussed from the point of view of very small Open Systems.
An analysis of naming conventions for distributed computer systems
Authors: Terry Douglas B.
Published: October 2004

Name servers that collectively manage a global name space facilitate sharing of resources in a large internetwork by providing means of locating named objects. The efficiency with which the name space can be managed is strongly influenced by the adopted naming convention. Structured name spaces are shown to simplify name space management from both an administrative and system viewpoint. Formulae have been derived which allow one to quantitatively measure the effect of the distributed name server configuration on a given client's level of performance. In general, the cost of a name server query can be reduced by distributing replicated copies of name server database entries in a way that exploits the locality of clients' reference patterns.
An adaptive timeout algorithm for retransmission across a packet switching network
Authors: Edge Stephen William
Published: October 2004

This paper presents and analyses a simple algorithm for setting an adaptive timeout value at a source Host for end-to-end retransmission on a packet-switched connection. The algorithm allows the recipient Host to acknowledge arriving data in either original transmission order or out-of-order. The time out at the source Host is determined from current estimates - using exponentially weighted moving averages - of the mean and variance of successive acknowledgement delays. We show that when these delays are random variables forming certain stationary or non-stationary stochastic processes, the ensuing timeout gives a near-minimum retransmission delay, subject to some specified limit on the amount of unnecessary retransmission. This property is illustrated for a simulated sequence of acknowledgement delays obtained from loop delay measurements.
Beating the I/O bottleneck: a case for log-structured file systems
Authors: Ousterhout John , Douglis Fred
Published: October 2004

CPU speeds are improving at a dramatic rate, while disk speeds are not. This technology shift suggests that many engineering and office applications may become so I/O-limited that they cannot benefit from further CPU improvements. This paper discusses several techniques for improving I/O performance, including caches, battery-backed-up caches, and cache logging. We then examine in particular detail an approach called
log-structured file systems
, where the file system's only representation on disk is in the form of an append-only log. Log-structured file systems potentially provide order-of-magnitude improvements in write performance. When log-structured file systems are combined with arrays of small disks (which provide high bandwidth) and large main-memory file caches (which satisfy most read accesses), we believe it will be possible to achieve 1000-fold improvements in I/O performance over today's systems.
Data integrity and security of the corporate data base: the dilemma of end user computing
Authors: Corman Lawrence S.
Published: October 2004

This article addresses the data integrity issues and security risks created by the advent of end user computing. The author proposes possible alternatives which do not inhibit the growth of end user computing, yet provide support to the data base administrator's function. Activities such as uploading and downloading, data editing, and concurrency control are also discussed in this paper. In addition, microcomputer networking is proposed as one means by which a data base administrator may insure data integrity and security in an end user environment.
Suitening our nomenclature
Authors: Ramshaw L.
Published: October 2004

Donald E. Knuth has suggested an alternative name for a multiset that I like very much:
a suite
, as in a suite of rooms or a suite of dances. Please join me in replacing "multiset" and "bag" with "suite" in our mathematical lexicon.
Case diagrams: a first step to diagrammed management information bases
Authors: Case Jeffrey D. , Partridge Craig
Published: October 2004

A method for pictorially representing objects in a Management Information Base (MIB) used for network management is presented. Although the method presented here is limited in the kinds of information it can display, the authors believe that some method for diagramming MIBs like the one described here will be needed in the future.
EPEP: an operating system designed for experiment-control
Authors: Emck J. H. , Voskamp J. H. , van der Wal A. J.
Published: October 2004

This paper describes an operating system and programming environment designed specifically for use in data-acquisition and experiment-control. The system, EPEP, is interpreter-based, object-oriented and very flexible. Features include easy-to-handle library and multitasking facilities, as well as facilities for interactive intervention in experiments running under program control. The same facilities allow the development of programs while an experiment is running on the same system. After describing how EPEP presents itself to the user, a few aspects of the implementation are discussed. The EPEP operating system, together with the loaded libraries and user program(s), form a database. The construction of the objects in this database, including program data structure and process descriptor, is discussed.
Performance of REAL/IX

TM

-fully preemptive real time UNIX
Authors: Furht Borko , Parker J. , Grostick D.
Published: October 2004

The UNIX® operating system, developed by AT&T Bell Laboratories, has become a standard operating system gaining rapid acceptance because of its superior flexibility, portability, and a number of support tools to increase programmer productivity. However, UNIX was originally designed for multitasking and time-sharing, and therefore conventional UNIX does not have an adequate response time and data throughput needed to support real-time applications.Many attempts have been made to adapt the UNIX kernel to provide a real-time environment. MODCOMP has developed REAL/IX operating system, which is a fully preemptive, low latency UNIX kernel. This paper discusses real-time performance of REAL/IX and compares it to MASSCOMP RTU operating system.
ARTS: a distributed real-time kernel
Authors: Tokuda H. , Mercer C. W.
Published: October 2004

ARTS is a distributed real-time operating system designed for a real-time systems testbed being developed at Camegle Mellon University. The objective of the testbed is to develop and verify advanced real-time computing technologies for a distributed environment. The tastbed consists of a set of SUN3 workstations connected by a real-time network based on IEEE 802.5 Token Ring and Ethernet. The goal of the ARTS Kernel is not to produce simply a fast real-time executive, but rather to provide users with a predictable, analyzable, and reliable distributed real-time computing environment. In particular, we have developed a real-time object model which is incorporated with a time fence protocol. The time fence protocol is used at every invocation in the object to detect the origin of timing errors. We also developed an integrated time-driven scheduling model and its scheduler based on the notion of policy/mechanism separation. Since each scheduling policy is implemented as a kernel object, a user can easily add policies or change the system's scheduling policy. A real-time toolset was also developed in order to predict the schedulability of the real-time activities.In this paper, we give an overview of the ARTS Kernel and ARTS real-time toolset. In particular, we introduce a real-time object model and the integrated time-driven scheduling model. We then describe the basic primitives and major components of the ARTS Kernel and the real-time toolset which consists of the schedulability analyzer,
Scheduler 1-2-3
, and the real-time monitor/debugger,
ARM.
HARTOS: a distributed real-time operating system
Authors: Kandlur D. D. , Kiskis D. L. , Shin K. G.
Published: October 2004

This paper outlines the design objectives and research goals for HARTOS, a distributed real-time operating system being developed at The University of Michigan. This effort is part of a larger research project to design and implement an experimental distributed real-time system called the Hexagonal Architecture for Real-Time Systems (HARTS). An important feature of HARTS is the use of an intelligent network processor to handle many of the functions relating to communications. The paper focuses on the communications aspects of the operating system and the control software kernel of the network processor. The preliminary version of the kernel provides good support for inter-process communication and distributed control. Its performance has been measured and analyzed and found to be comparable to that of other message passing systems like the V system.
Neural networks: a new technolgy for information processing
Authors: Klimasauskas C.
Published: October 2004

Neural networks are an innovative approach to information processing. Their characteristics lend themselves to directed analysis of the contents of computer data-bases. Potential payoffs from this include increased sales, decreased risk, and improved profitability. This presentation includes a brief look at the technology with an emphasis on providing a basic understanding of its characteristics and how they can be applied.
Real time Ada compilers for the 68020
Authors: Asplund L. , Carlsson M. , Wengelin S. , Bray G.
Published: October 2004

Three cross compilers hosted on a VAX/VMS for the Motorola 68020 processor have been evaluated. The target machine, a VME system with a MVME133 processor card and a MVME340 digital IO-card, has been set up in an environment with a function generator and an oscilloscope in order to measure the real time response. The compilers supply the run time kernel. It is possible to use Ada for real time applications, with the use of optimization of accept statements task switch times can come down to the order of 15 - 20 us.
The KEYSTONE system design methodology
Authors: Kiem Eric
Published: October 2004

The Keystone Methodology uses Entity-Relationship modeling to determine an optimum object-oriented packaging structure, which will exhibit minimum coupling and inter-dependencies between elements of a system and therefore maximum reusability potential. Furthermore, the resulting organization of the data dimension permits extensive use of a limited range of generics to provide complete data manipulation through the use of relational operations. The form and disposition of concurrent elements of a system can also be determined directly from the E-R model. The modeling process is proven and the implementation of the resulting design is systematic.
The AIDA experiment
Authors: Mazzanti F.
Published: October 2004

Most of currently available debugging tools for Ada do not allow to monitor enough in detail the powerful features of the language. For example, the help usually provided to the user for checking the program dependence from the particular characteristics of the language implementation, rarely goes beyond the detection of the most evident aspects. Similarly, no facilities are usually provided for detecting at run-time the occurrence of an erroneous execution, or for driving the program execution in all its aspects to generate the desired program effects.Possible directions for the improvement of debugging techniques to match the needs of Ada, and, more in general, of highly nondeterministic and concurrent languages, have been investigated as part of the activity of the EEC MAP project 755 "SFD-APSE", leading to the development of a prototype of an Advanced Interpreter/Debugger for Ada (AIDA). In this paper the experience gained with the project is briefly summarized, illustrating some of the useful features for a powerful and detailed monitoring of the execution of Ada programs.
Reprint from computing reviews
Authors: Loui M. C.
Published: October 2004

As a service to our readers,
SIGACT News
has reached an agreement to reprint review that originally appeared in
Computing Reviews
of books and articles of interest to the theoretical computer science community.
Computing Reviews
is a monthly journal that publishes critical reviews on a broad range of computing subject, including models of computation, formal languages, computational complexity theory, analysis of algorithms, and logics and semantics of programs. ACM members can receive a subscription of
Computing Reviews
for $30 per year by writing to ACM headquarters.
A colored petri net model for connection management services in MMS
Authors: Wang F.-Y. , Gildea K. , Rubenstein A.
Published: October 2004

This paper presents a Petri net (PN) model for Connection Management Services (CMS) of the Manufacturing Message Specification (MMS) which describes all possible sequences of service primitives that can occur during establishment, maintenance and termination of the connection and their relation at each service state. The PN model enables a complete and unambiguous specification to be derived for CMS. P-invariants and T-invariants analysis carried out on the connection PN provides useful information on the CMS behavior and specification for its implementation. It is claimed that PNs may offer a hierarchical mathematical description for the entire MMS protocol, a uniform representation for various level of abstraction of MMS protocol and an analytical model for protocol performance evaluation and analysis.
Defining faster transfer syntaxes for the OSI presentation protocol
Authors: Huitema C. , Doghri A.
Published: October 2004

In an heterogeneous environment, applications must agree the structure and a binary representation of the exchanged data. This can a priori be done by adopting by the two standards proposed by ISO: the
Abstract Syntax Notation 1
(ASN-1) and the
ASN-1 basic encoding rules
(ASN1-BER). However, the ASN1-BER conversion procedures are highly CPU consuming, which is not acceptable for several "high speed" applications. We propose to use the presentation layer negotiation to select faster transfer syntax. We have experimented with a first "light weight" syntax since 1988, and have just completed the definition a new "flat tree light weight syntax", which can be orders of magnitude faster than the ASN1-BER.
A delay-based approach for congestion avoidance in interconnected heterogeneous computer networks
Authors: Jain R.
Published: October 2004

In heterogeneous networks, achieving congestion avoidance is difficult because the congestion feedback from one subnetwork may have no meaning to sources on other subnetworks. We propose using changes in round-trip delay as an implicit feedback. Using a black-box model of the network, we derive an expression for the optimal window as a function of the gradient of the delay-window curve.The problems of selfish optimum and social optimum are also addressed. It is shown that without a careful design, it is possible to get into a race condition during heavy congestion, where each user wants more resources than others, thereby leading to a diverging condition.It is shown that congestion avoidance using round-trip delay is a promising approach. The approach has the advantage that there is absolutely no overhead for the network itself. It is exemplified by a simple scheme. The performance of the scheme is analyzed using a simulation model. The scheme is shown to be efficient, fair, convergent, and adaptive to changes in network configuration.The scheme as described works only for networks which can be modeled with queueing servers with constant service times. Further research is required to extend it for implementation in practical networks. Several directions for future research have been suggested.
A logic of authentication
Authors: Burrows M. , Abadi M. , Needham R.
Published: October 2004

Authentication protocols are the basis of security in many distributed systems, and it is therefore essential to ensure that these protocols function correctly. Unfortunately, their design has been extremely error prone. Most of the protocols found in the literature contain redundancies or security flaws.

A simple logic has allowed us to describe the beliefs of trustworthy parties involved in authentication protocols and the evolution of these beliefs as a consequence of communication. We have been able to explain a variety of authentication protocols formally, to discover subtleties and errors in them, and to suggest improvements. In this paper, we present the logic and then give the results of our analysis of four published protocols, chosen either because of their practical importance or because they serve to illustrate our method.