bluuebunny/crossref_metadata_2025 huggingface dataset:
An approach to analyzing the information content of existing databases
Authors: Boulanger Danielle , March Salvatore T.
Published: October 2004

Traditionally, application databases have been developed for efficiency of computer operations. The logical structure of the data is buried in the database schemas, application programs, and users' and programmers' minds. To manage information as a corporate resource the logical data structures must be made explicit. In this way organizational databases can be conceptually integrated. The magnitude and complexity of corporate databases makes a manual approach to this task infeasible. We propose a computer aided approach. The approach is based on extracting implicit functional dependencies from existing database schemas and forming an Entity-Relationship representation. Where the semantics of the schema are unclear, rules are applied and additional input sought from the Data Administrator. Because of its widespread use in production systems, we focus on CODASYL Network DBMSs in this paper. The approach also has applications in databases from one DBMS to another.
Expert system applications in customer service
Authors: Schon Stephen , Helferich Omar Keith
Published: October 2004

The competitive edge of using expert system technology is beginning to have an impact on the marketplace. Described here are applications of expert system technology to customer service and many of the ideas presented here are applicable to other areas of business as well. This project was accomplished in cooperation with the Customer Service Department of a major U.S. chemical company, and this paper describes the design, implementation, and results of a diagnostic expert system prototype and the design of an Expert Inquiry Handler for customer service. The prototype design was based on a previously successful design by the authors, and the Expert Inquiry Handler design addresses what it means to do intelligent inquiry handling in customer service and how an Expert Inquiry Handler interfaces with its resources (data base and people) to accomplish its job.
Dragoon: an object-oriented notation supporting the reuse and distribution of Ada software
Authors: Atkinson C. , de Maio Andrea , Bayan R.
Published: October 2004

Among the more radical proposals for changes to the Ada standard in Ada9X are those advocating the introduction of "object-oriented" features exemplified by languages such as Smalltalk and Eiffel. DRAGOON is a language which supports the fundamental concepts of object-oriented programming in an Ada style, while retaining most of the features of current Ada. In other words it supports "Ada-oriented" object-oriented programming. It also employs enhanced forms of multiple inheritance to support concurrency and distribution. Therefore, although not designed specifically as a proposal for the Ada9X project, DRAGOON may serve as a basis for the development of Ada in an "object-oriented" direction. This paper provides a brief overview of the language.
Distributed Ada: a suggested solution for Ada 9X
Authors: Dobbing B.
Published: October 2004

This paper contains a suggested solution to the problems of implementing Ada in non-shared memory distributed systems for incorporation into Ada9X. The solution is based on three fundamental principles: firstly that there should be minimal disturbance to the existing Ada language definition; secondly that the security aspects of the language are not compromised; and thirdly that the requirements of implementors of distributed systems be met in full.
Flow control for real-time communication
Authors: Cohen Danny
Published: October 2004

Flow Control is a problem of resource allocation in communication systems; typically the critical resources are the bandwidth of the medium, memory space and processing capabilities.

Traditionally, protecting the resources of the communicating processes is called Flow Control, and the protecting the communication system is called Congestion Control. Hence, the flow control is the protection of one process from the other(s), and the congestion control is protection of the communication-system from the processes.

This note argues that real-time communication requires different flow control and congestion control schemes than the familiar ones used for non-real-time communication.
Bus, ring, star and tree local area networks
Authors: Boulton Peter I. P. , Lee E. Stewart
Published: October 2004

This paper examines some of the relative merits of Bus, Ring and Star topologies for Local Area Networks, and describes a new structure - the dual rooted tree. The latter produces superior performance for heavy loads and for impulse loads, while avoiding the message length limitations associated with CSMA LAN's. A 50 Mbit/s fibre-optic prototype network has been constructed and tested. A large (250 port) 50 Mbit/s fibre-optic field trial network is now being installed at the University of Toronto.
Security problems in computer communication systems
Authors: Turn Rein
Published: October 2004

At the present time there is a rapid growth in computer communications associated with terminal-based, multi-user computer systems, and in networks of computers [1,2,3]. Nearly all such systems communicate, process, or store information which is considered private or proprietary by their owners and users, or which must be safeguarded from unauthorized access as required by law. Furthermore, associated terminals, telecommunication systems, communication processors, and computers must be protected from intruders that may seek to alter programs or data in the system, or to disrupt the services provided. These threats are real, since it is not difficult to intercept transmissions in telecommunication networks [4,5], and it is possible to connect illicit terminals (or even computers) into the system for the purposes of "managing" the normal terminal-computer communications, masquerading as a legitimate user, or simply making the system unavailable to others [6,7].

The protection of a computer communication system against the various threats involves: (1) identification, and authentication of the identity, (2) controlled access to computers and their data bases, and (3) protection of the data in transit in the telecommunication system. Associated with each are a number of problems -- conceptual, as well as technical -- and a variety of solutions. In this brief survey, the emphasis is on the problems.
A formalised technique for expressing message generators
Authors: Payne A. J.
Published: October 2004

The testing of real time systems for overload conditions is often performed by systems exercisers and message generators. Messages are usually expressed informally for their content, whilst languages use much formality in their definition. This paper gives a formalised description of messages and their contents so that they may be generated in defined proportions for testing real time systems.

The first part of the paper surveys the previous work that has been done in the field. In the second section we develop a theoretical model of the problem. Part three describes a method for collecting information which can be used to drive the theoretical model. The fourth portion gives the algorithms for generating the test data. In the fifth part examples demonstrate how effective the system is.
Graph theory applied to optimal connectivity in computer networks
Authors: McQuillan J. M.
Published: October 2004

This is a report on some of the research that has been carried out in applying graph theoretical results to communications networks. The networks that we wish to investigate here consist of computers at various sites which are linked together by telecommunications circuits.

Many of the results of graph theory may be applied to such networks; we will restrict ourselves to the consideration of connectivity. In designing a computer communications network, it is desirable to provide good connectivity among all sites at reasonable cost. For this reason, extremes like the fully-connected network (too expensive) and the star network (only as reliable as its center) are usually not considered. The connectivity constraints or reliability measures can be stated in different ways, and analytic techniques have been developed for some of these measures. Further, procedures for the synthesis of well-connected networks have also been invented.

The reliability of communications networks is an important issue in their design and operation. Telecommunications circuits become noisy and unusable, and the communications computers may also fail. This report is a survey of that part of applied graph theory which is useful in the study of the connectivity of communications networks.
SDLC and BSC on satellite links
Authors: Traynham K. C. , Steen R. F.
Published: October 2004

The emergence of satellite communication links offers the data communication designer increased throughput, but at the same time forces him to deal with greatly increased signal transmit time which may eliminate all potential throughput increases. Using a mathematical model, this paper compares batch throughput efficiency of two IBM line control methods, Binary Synchronous Communications (BSC) and Synchronous Data Link Control (SDLC), along with some hypothetical extensions to SDLC. Although the model treats links of any description, the focus here is on links with long signal transit time and low bit error rate, such as satellite links. Classic analog terrestrial links are included for comparison.

The model consists of an information source with an infinite supply of data transmitting to an information sink which transmsits no data but does acknowledge received frames as defined in the various protocols. Throughput efficiency is defined as the ratio of the time spent by the data source transmitting original information bytes (i.e., bytes in the SDLC or BSC Information Field, excluding those bytes retransmitted due to errors) to the time spent transmitting all bytes (i.e., information, control, and error recovery) plus time taken by any gaps in continuous transmission.

The comparison applies to steady-state batch transmission, so the link is assumed to be point-to-point. Both full duplex and half duplex protocols are considered in SDLC, but only half duplex protocols are contained in BSC. A hypothetical extension to SDLC, Asynchronous Response Mode (ARM), and SDLC Normal Response Mode (NRM) are included in full duplex. The model shows no difference in throughput efficiency between half duplex NRM and ARM, so only one result is presented for half duplex SDLC. Both SDLC and BSC are data link control architectures; for details concerning a particular implementation, the reader should consult the product description. More detail on SDLC and BSC is available in References 1-4.

Two transmission links are considered. The terrestrial analog link consists of traditional analog facilities, while the satellite link consists of only a satellite connection between the end points (i.e., the end points are very close to the satellite earth stations, such that negligible transit time and link errors are introduced in the terminal-to-earth station links). Each link is characterized by its bit error rate (BER) and round trip delay (RTD). Bit error rate is the long-term average of bit errors per bit transmitted, while round trip delay is defined as the amount of time between the last bit of a given SDLC frame or BSC block being transmitted and the first bit of its response being received at the source. RTD includes the time (in seconds) necessary to generate and transmit a line-control response at the receiving end, as well as any delay in equipment between the end points. Results are obtained using a simple bit-independent error model.

The next section describes the applicable equations, while the following section discusses results.
Notes on the X.25 procedures for virtual call establishment and clearing
Authors: Bochmann Gregor V.
Published: October 2004

The packet level of the CCITT Recommendation X.25 describes how the virtual circuit communication service of public packet-switched data networks can be used. The recommendation contains in particular a specification of how to establish and clear virtual circuits through a given DTE-DCE interface. We comment in this paper on the following three aspects of these procedures for call establishment and clearing:

(a) The recommendation contains state diagrams to clarify the operation of the DTE-DCE interface. The reader may assume that the diagrams show, at each instant in time, the unambiguous state of the interface. This is, however, not always true since the DTE and the DCE may be in different states.

(b) We have analysed the operation of the interface using a finite state validation method, and have found that in some rare cases a conflicting situation (i.e. when the DTE and the DCE are in different states) may sustain through the repetitions of some cyclic behavior.

(c) The procedures of X.25 are very symmetrical. However, the packet level call establishment procedure contains a non-symmetrical element for the handling of call collisions. We consider as alternatives some symmetrical procedures for this purpose.

For each of these aspects we try to explain the problem and give some suggestions for its solution.
The ISO connectionless transport standards
Authors: Stein Scott A.
Published: October 2004

The term Open Systems Interconnection (OSI) has increased in familiarity to those involved in distributed processing and data communications to such an extent that an understanding of the architecture it describes and the principles behind its development have quite nearly become commonplace. OSI consists of two closely related pieces: the OSI Basic Reference Model, ISO 7498, which provides a coordinated framework for the development of protocols to support distributed processing environments; and the set of related protocols which achieve that objective. The Reference Model describes an architecture wherein functions which provide communications are separated into a hierarchy of seven layers. Each layer provides services to the next higher layer, utilizing the services provided by subordinate layers in order to achieve that end. At each layer, protocols are employed to convey information between peer layer entities in communicating systems. When in compliance with the suite of standard protocols prescribed for OSI, systems are considered to be "open".

Initially, ISO 7498 defined only the requirements of connection mode services within the Reference Model. However, in recognition of the importance which connectionless-mode applications play in the data communications environment, an addendum to ISO 7498 was produced which defines the requirements for connectionless-mode services in the Reference Model. The purpose of this paper is to present an overview of the development of connectionless-mode service and protocol within the Transport Layer of the OSI Reference Model.
The effectiveness of computer graphics for decision support
Authors: Hwang Mark I. H. , Wu Bruce J. P.
Published: October 2004

This research uses meta---analysis, a quantitative literature review technique, to integrate and combine the results fromseveral presentation format studies. The motivation behind this research is twofold: the conflicting research results found in the literature, and the lack of a cumulative body of knowledge. Meta---analysis is a research technique that provides a means for cumulating research findings across studies. In addition, meta-analysis can resolve differences found in previous studies by isolating the effect of moderator variables. This research found very strong evidence of the existence of one moderator variable, task complexity, which may have resulted in reported inconsistencies from prior presentation format research. Furthermore, an inverted "U---shaped" curve may explain the relationship between the effectiveness of graphs and task complexity. Specifically, using graphical data achieves better decision---making performance when the task is moderately complex. When the task complexity is either too low or too high, there is no performance difference between graphical and tabular presentation formats.
MIS research directions
Authors: Teng James T. C. , Galletta Dennis F.
Published: October 2004

Several studies have addressed important issues for MIS Research, but until now no empirical studies have been conducted to asses how MIS researchers themselves view the relatively new field. This survey of 397 MIS researchers revealed preferences for research methods and current areas of concentration, current studies being conducted, publication history, and other factors of interest. It found the subjects' assessment of the quality of MIS research relatively low and that they feel there is an overemphasis on transient topics, rather than on topics of lasting significance. There is continuing evidence of fragmentation in the field. Few MIS researchers appear to rely on research frameworks. However, there is overall optimism that the quality of MIS research has been improving, and will continue to improve in the future. Implications for the future of MIS research are then discussed.
Telecommunication research in information systems
Authors: Adams Dennis A. , Lacity Mary C. , Mullins James R.
Published: October 2004

Telecommunications management is becoming a top priority of IS executives. Executives concerns range from network establishment and getting connectivity to using IS for competitive advantage. In a rapidly changing environment, these executives search for guidance and insights. Unfortunately they might find limited help from IS research. An extensive literature review of more than 9800 articles covering over eleven years of MIS research showed that academicians have not placed the same emphasis as practitioners on telecommunications management. Furthermore, the majority of telecommunications research focuses on lower level management issues, such as installing a network, rather than using IS for competitive advantage. More research in telecommunications is needed to provide IS executives with insights on how to manage the telecommunications function.
The architecture and design of a collaborative environment for systems definition
Authors: Chen Minder , Nunamaker Jay F.
Published: October 2004

Defining systems requirements and specifications is a collaborative effort among managers, users, and systems developers. The difficulty of systems definition is caused by the human's limited cognitive capabilities, that is compounded by the complexity of group communication and coordination processes. Current system analysis methodologies are first evaluated regarding to the level of support to users. Since systems definition is a knowledge-intensive activity, the knowledge contents and structures employed in systems definition are discussed. For any large-scale system, no one person possesses all the knowledge that is needed, therefore, the authors proposed a collaborative approach to systems definition. The use of a group decision support system (GDSS) for systems definition is first described and limitations of the current GDSS are identified. The architecture and design of a collaborative computer-aided software engineering (CASE) environment, called C-CASE, is then discussed. C-CASE can be used to assist users in defining the requirements of their organization and information systems as well as to analyze the consistency and completeness of the requirements. C-CASE integrates GDSS and CASE such that users can actively participate in the requirements elicitation process. Users can use the metasystem capability of C-CASE to define domain specific systems definition languages, which are adaptable to different systems development settings. An example of using C-CASE in a collaborative environment is given. The implications C-CASE and the authors' ongoing research are also discussed.
Support for specifying temporal behavior in Ada designs
Authors: Buhr R. J. A. , Karam G. M. , Casselman R.
Published: October 2004

MachineCharts
is a visual design notation that has both structural and temporal semantics. An
Abstract Controller Machine
(ACM) is an element of the notation that encapsulates the temporal behavior defined by a requirements entity and expresses it through an
event/action
interface. This interface is used by the design components to implement the communications semantics between entities that were present in the requirements model. To support the ACM concept as part of design, it has been integrated into
TimeBench
, a design environment targeted to support Ada software design and development.
What price reusability?
Authors: Favaro John
Published: October 2004

This paper reports on experiences gained from a year-long industrial development project that made use of a popular repository of reusable components. The results of applying an existing framework for quantifying the economics of reuse are presented.
The CAEDE performance analysis tool
Authors: Woodside C. M. , Hagos E. M. , Neron E. , Buhr R. J. A.
Published: October 2004

A performance analysis tool which has been built into the CAEDE environment for design of Ada software is described. In the 'software CAD' philosophy of CAEDE this could be one of several analysis tools to be used on design, before generating application code. The analyzer has a practical interface for software designers and computes system throughputs for various design options and processor speeds and allocations, as well as finding bottlenecks and task utilizations, etc. Both an early version of these calculations, which is performed in the distribution version CAEDE1.5, and a more advanced research version are described.
A new congestion control scheme
Authors: Wang Zheng , Crowcroft Jon
Published: October 2004

Recently there have been many measures proposed to tackle the problem of congestion in computer networks. In this paper, we first analyze some of the measures and then present a new scheme in which the optimal operating point is obtained by evaluation of throughput gradient and resource sharing is adjusted only at the beginning and the end of a connection. Simulation results show that the scheme converges to an optimal operating point quickly and fairly.
The design and implementation of a log-structured file system
Authors: Rosenblum Mendel , Ousterhout John K.
Published: October 2004

This paper presents a new technique for disk storage management called a
log-structured file system
. A log-structured file system writes all modifications to disk sequentially in a log-like structure, thereby speeding up both file writing and crash recovery. The log is the only structure on disk; it contains indexing information so that files can be read back from the log efficiently. In order to maintain large free areas on disk for fast writing, we divide the log into
segments
and use a
segment cleaner
to compress the live information from heavily fragmented segments. We present a series of simulations that demonstrate the efficiency of a simple cleaning policy based on cost and benefit. We have implemented a prototype log-structured file system called Sprite LFS; it outperforms current Unix file systems by an order of magnitude for small-file writes while matching or exceeding Unix performance for reads and large writes. Even when the overhead for cleaning is included, Sprite LFS can use 70% of the disk bandwidth for writing, whereas Unix file systems typically can use only 5--10%.
The implications of cache affinity on processor scheduling for multiprogrammed, shared memory multiprocessors
Authors: Vaswani Raj , Zahorjan John
Published: October 2004

In a shared memory multiprocessor with caches, executing tasks develop "affinity" to processors by filling their caches with data and instructions during execution. A scheduling policy that ignores this affinity may waste processing power by causing excessive cache refilling.Our work focuses on quantifying the effect of processor reallocation on the performance of various parallel applications multiprogrammed on a shared memory multiprocessor, and on evaluating how the magnitude of this cost affects the choice of scheduling policy.We first identify the components of application response time, including processor reallocation costs. Next, we measure the impact of reallocation on the cache behavior of several parallel applications executing on a Sequent Symmetry multiprocessor. We also measure, the performance of these applications under a number of alternative allocation policies. These experiments lead us to conclude that on current machines processor affinity has only a very weak influence on the choice of scheduling discipline, and that the benefits of frequent processor reallocation (in response to the changing parallelism of jobs) outweigh the penalties imposed by such reallocation. Finally, we use this experimental data to parameterize a simple analytic model, allowing us to evaluate the effect of processor affinity on future machines, those containing faster processors and larger caches.
Implementation and performance of Munin
Authors: Carter John B. , Bennett John K. , Zwaenepoel Willy
Published: October 2004

Munin is a distributed shared memory (DSM) system that allows shared memory parallel programs to be executed efficiently on distributed memory multiprocessors. Munin is unique among existing DSM systems in its use of
multiple consistency protocols
and in its use of
release consistency
. In Munin, shared program variables are annotated with their expected access pattern, and these annotations are then used by the runtime system to choose a consistency protocol best suited to that access pattern. Release consistency allows Munin to mask network latency and reduce the number of messages required to keep memory consistent. Munin's multiprotocol release consistency is implemented in software using a
delayed update queue
that buffers and merges pending outgoing writes. A sixteen-processor prototype of Munin is currently operational. We evaluate its implementation and describe the execution of two Munin programs that achieve performance within ten percent of message passing implementations of the same programs. Munin achieves this level of performance with only minor annotations to the shared memory programs.
Disconnected operation in the Coda file system
Authors: Kistler James J. , Satyanarayanan M.
Published: October 2004

Disconnected operation
is a mode of operation that enables a client to continue accessing critical data during temporary failures of a shared data repository. An important, though not exclusive, application of disconnected operation is in supporting portable computers. In this paper, we show that disconnected operation is feasible, efficient and usable by describing its design and implementation in the Coda File System. The central idea behind our work is that
caching of data
, now widely used for performance, can also be exploited to improve
availability
.
Empirical studies of competitve spinning for a shared-memory multiprocessor
Authors: Karlin Anna R. , Li Kai , Manasse Mark S. , Owicki Susan
Published: October 2004

A common operation in multiprocessor programs is acquiring a lock to protect access to shared data. Typically, the requesting thread is blocked if the lock it needs is held by another thread. The cost of blocking one thread and activating another can be a substantial part of program execution time. Alternatively, the thread could spin until the lock is free, or spin for a while and then block. This may avoid context-switch overhead, but processor cycles may be wasted in unproductive spinning. This paper studies seven strategies for determining whether and how long to spin before blocking. Of particular interest are
competitive
strategies, for which the performance can be shown to be no worse than some constant factor times an optimal off-line strategy. The performance of five competitive strategies is compared with that of always blocking, always spinning, or using the optimal off-line algorithm. Measurements of lock-waiting time distributions for five parallel programs were used to compare the cost of synchronization under all the strategies. Additional measurements of elapsed time for some of the programs and strategies allowed assessment of the impact of synchronization strategy on overall program performance. Both types of measurements indicate that the standard blocking strategy performs poorly compared to mixed strategies. Among the mixed strategies studied, adaptive algorithms perform better than non-adaptive ones.
A multi-service storage architecture
Authors: Bacon Jean , Moody Ken , Thomson Sue , Wilson Tim
Published: October 2004

This paper gives an overview of a new Multi Service Storage Architecture (MSSA) which has been designed for a broader range of clients than traditional file servers and in particular for emerging clients such as real-time multimedia applications.The proposed architecture is an open hierarchy of services in which both unstructured and structured data are supported. Any client which requires high performance and a minimal service can use the lowest level directly. A principal-specific capability scheme is used for protection.The paper outlines the designs of the two basic components of the architecture, the Low Level and High Level Storage Services (LLSS and HLSS). The LLSS has a traditional storage service interface, at the byte sequence or subsequence level, and exploits non-volatile memory to achieve high performance. The HLSS provides optional support for structured objects through a flexible but efficient storage type generation scheme together with existence control and concurrency control at any required granularity.We have developed tools for performance evaluation which allow us to monitor the LLSS under artificial load generators and benchmarks as well as local applications. As a side effect we can compare the properties of these loads.We outline how the storage services are being used as a basis for a directory service, a database programming language, an integrated virtual memory system and the representation, storage and retrieval of structured multimedia objects with synchronisation between components.
A simple reliable globally-ordered broadcast service
Authors: Oestreicher Dan
Published: October 2004

A practical basis for implementing fault tolerant applications is described. At the application programming level a set of group communication and transaction handling primitives is provided. A fault tolerant globally--ordered broadcast service provides the basis for those primitives.The design is based on Kaashoek & Tanenbaum's reliable broadcast [4], [5], but modified, and implemented on a standard Unix system using the industry--standard TCP/IP protocol family.The implementation of the broadcast service is simple, and could be implemented at a low level to provide a new type of reliable LAN, or it can be implemented by using spare cycles on server machines which are also performing other tasks. The implementation of the group primitives using the broadcast service is not so simple, and is indicated, but not described in detail.Code size and performance figures are given for an implementation of the system.
An implementation for small databases with high availability
Authors: Lam Kwok-yan
Published: October 2004

A technique for implementing the kind of small databases that frequently occur in the design of operating systems and distributed systems is presented. This technique is based on the checkpointing mechanism for maintaining data persistence. It can be regarded as a hybrid of the stable storage approach and the master-slave approach to fault tolerance, and is especially suitable for systems that support the processor pool paradigm of computation. This scheme has been used to implement a monitoring service for a distributed system. The resulting implementation has the desired property of being simultaneously simple, efficient, reliable, and available.
Fairness in processor scheduling in time sharing systems
Authors: Haldar S. , Subramanian D. K.
Published: October 2004

Loosely, fairness is the assurance of granting each request, from a set of requests, within a predetermined bounded time even though the request scheduling primitives are unfair or random. The fairness property has been studied, in solutions to the mutual exclusion problem, from theoretical point of view. Many fair solutions to the mutual exclusion problem have been proposed in recent years. This paper presents one illustration to show how the concepts of fairness could be incorporated in processor scheduling in time sharing systems. First, it looks at some shortcomings associated with the round robin scheduler used in the time sharing systems, and then presents a fair version of the round robin scheduler.
Structured programming with limited private types in Ada
Authors: Baker Henry G.
Published: October 2004

Many traditional styles of programming cannot cope with the limitations of Ada limited private types. We present a style of programming that enables structured programming in Ada with limited private types. The problem of "finalization" is safely and cleanly handled through the use of a generic package which guarantees that a variable of the limited private type will be finalized even in the presence of exceptions.Finalization is often desired in order to perform
automatic garbage collection
, whether by reference counting or by marking. We have proved our structured technique by developing a garbage-collected Lisp system in Ada in which the Lisp values are instances of a limited private type. The Ada code was so highly structured, that it was generated automatically using a simple compiler. The garbage collector in this system was easily and safely implemented, and different garbage collection techniques were tested without affecting user code.
On Superpolylogarithlnic Subexponential Functions (Part I)
Authors: Sherman Alan T.
Published: October 2004

A
superpolylogarithmic subexponential function
is any function that asymptotically grows faster than any polynomial of any logarithm but slower than any exponential. We present a recently discovered nineteenth-century manuscript about these functions, which in part because of their applications in cryptology, have received considerable attention in contemporary computer science research. Attributed to the little-known yet highly-suspect composer/mathematician Maria Poopings, the manuscript can be sung to the tune of "Supercalifragilisticexpialidocious" from the musical
Mary Poppins.
In addition, we prove three ridiculous facts about superpolylogarithmic subexponential functions. Using novel extensions to the popular DTIME notation from complexity theory, we also define the complexity class Super PolyLog/SubExp, which consists of all languages that can be accepted within deterministic superpolylogarithmic subexponential time. We show that this class is notationally intractable in the sense that it cannot be conveniently described using existing terminology. Surprisingly, there is some scientific value in our notational novelties; moreover, students may find this paper helpful in learning about growth rates, asymptotic notations, cryptology, and reversible computation.
Dynamics of congestion control and avoidance of two-way traffic in an OSI testbed
Authors: Wilder Rick , Ramakrishnan K. K. , Mankin Allison
Published: October 2004

An extensive set of measurements were made in an OSI testbed to study the behavior of congestion control and avoidance. Testbed systems used the Connectionless Network Protocol (CLNP) and Transport Protocol Class 4 (TP4), which had been modified to perform the CE-bit [10] congestion avoidance and the "CUTE" [6] congestion recovery algorithms.We found that two-way traffic has dynamics which can significantly decrease fairness among competing connections using congestion avoidance. We present experiments that demonstrate this problem and our analysis of how two-way traffic results in reduced fairness. This analysis led us to develop an effective modification to the congestion avoidance algorithms to maintain fairness with two-way traffic.Our analysis of experimental results also points to undesirable interactions between two-way traffic dynamics and a sending strategy that times data transmissions, by the receipt of acknowledgements. These interactions reinforce burstiness of transmissions. therefore increasing buffering requirements and delay in routers. They may also decrease throughput.
Experience with formal methods in protocol development
Authors: Sidhu Deepinder , Chung Anthony , Blumer Thomas P.
Published: October 2004

Communication protocols are complex software systems and key components of computer networks. They must be specified completely and implemented correctly. The development of a protocol typically involves several tedious steps. Experience has shown that the use of informal techniques in these steps of protocol development generally produces systems with errors and undesirable behaviors. Formal methods permit the development of highly
reliable
and easily
maintainable
communication protocols. This paper presents our experience with using formal methods in the specification, verification, implementation, and conformance testing of OSI protocols.
The metrobridge
Authors: Zielinski K. , Chopping M. , Milway D. , Hopper A. , Robertson B.
Published: October 2004

This paper describes the Metrobridge project - a distributed switch for connecting PC cards via a high-speed ATM-style backbone network. Initially the system architecture is outlined, then certain aspects are examined in more detail. Topics discussed include learning and routing algorithms, access/routing control, management functions, and applications.
Rationale for the proposed standard for a generic package of elementary functions for Ada
Authors: Dritz Kenneth W.
Published: October 2004

This paper supplements the "Proposed Standard for a Generic Package of Elementary Functions for Ada," written by the ISO-IEC/JTC1/SC22/WG9 (Ada) Numerics Rapporteur Group. Based on recommendations made jointly by the ACM SIGAda Numerics Working Group and the Ada-Europe Numerics Working Group, the proposed elementary functions standard is the first of several anticipated collateral standards to address the interrelated issues of portability, efficiency, and robustness of numerical software written in Ada. Organized as a series of questions and answers, this supplement outlines the reasoning by which the proposed standard came to acquire certain features and exclude others.
Rationale for the proposed standard for package of real and complex type declarations and basic operations for Ada (including vector and matrix types)
Authors: Hodgson Graham S.
Published: October 2004

This paper supplements the "Proposed Standard for Packages of Real and Complex Type Declarations and Basic Operations for Ada (including Vector and Matrix Types)", to be submitted by the ISO-IEC/JCT1/SC22/WG9 (Ada) Numerics Rapporteur Group. Based on recommendations made jointly by the Ada-Europe Numerics Working Group and the ACM SIGAda Numerics Working Group, the proposed real and complex vector and matrix standard is the third of several anticipated secondary standards to address the interrelated issues of portability, efficiency and robustness of numerical software written in Ada. Its purpose, features and development are outlined in this commentary.
Emulators; prospective instruments for instruction in systems programming
Authors: Olagunju Amos O , Borders Elvis
Published: October 2004

Microprogramming is a technique for implementing machine language instruction sets -- it is critical in today's computer architectures and operating systems. An emulator is a set of microprograms that implements the architecture of one machine on another; microprogramming is often used in emulation to make one computer system appear as if it were another. This paper presents the architecture for a microprogrammed computer system, the VSEM. The simulated virtual computer system, its monitor and a simulated concurrent PASCAL are discussed. The usefulness of the VSEM, its monitor and the concurrent PASCAL as vehicles for instruction in systems programming is addressed.
Efficient solutions to the replicated log and dictionary problems
Authors: Wuu Gene T J , Bernstein Arthur J
Published: October 2004

We propose efficient algorithms to maintain a replicated dictionary using a log in an unreliable network. A non-serializable approach is used to achieve high concurrency. The solutions are resilient to both node and communication failures. Optimizations are developed for networks which are not completely connected.
A security risk of depending on synchronized clocks
Authors: Gong Li
Published: October 2004

Many algorithms or protocols, in particular cryptographic protocols such as authentication protocols, use synchronized clocks and depend on them for correctness. This note describes a scenario where a clock synchronization failure renders a protocol vulnerable to an attack even
after
the faulty clock has been resynchronized. The attack exploits a postdated message by first suppressing it and replaying it later.
A mechanism of process group for application reliability in distributed systems
Authors: Hong Zhao , Li Huatian
Published: October 2004

Reliability is a very important aspect in distributed system studies and developments. In procedure control system and computer integrated manufacture system, for example, an application may relate to many application entities (processes) which may locate at several different sites. If one of the entities fails, the others may be affected. So every entity should be maintained to tolerate failures. We here propose a mechanism for tolerating failure, called distributed application entity group (DAEG), that will make an application entity reliable. In this mechanism, an application entity will be implemented with a process group, including several members that may locate at different sites. We present how the group communicates with other groups/entities in an application, how the entities in a group cooperate with each other and hold a consistent view about the group. In addition, time requirement is guaranteed by setting the timers. We introduce a method by which timer is used to check failures and to select a new group leader to let application it supports continue. We believe that the mechanism could support various application in distributed systems
Experiences in integrating distributed shared memory with virtual memory management
Authors: Ananthanarayanan R. , Menon Sathis , Mohindra Ajay , Ramachandran Umakishore
Published: October 2004

While the duality between message-passing and shared memory for interprocess communication is well-known, the shared memory paradigm has drawn considerable attention in recent times even in distributed systems. Distributed Shared Memory (DSM) is the abstraction for supporting the notion of shared memory in a physically non-shared (distributed) architecture. It gives a uniform set of mechanisms for accessing local and remote memories. Further, by combining shared memory style synchronization with the actual data transport in the DSM design, it is possible to provide flexible sharing while assuring mutual exclusion when necessary. This research reports on our experience in implementing a DSM system in an object-based distributed operating system. The important observation from this experience is the need for a tight cooperation between the virtual memory management at each node and the mechanisms provided by the DSM. Such a cooperation is essential to assure good performance of the DSM mechanisms and make the shared memory paradigm viable in a distributed environment.
Merging expert systems with multimedia technology
Authors: Sipior Janice C. , Garrity Edward J.
Published: October 2004

Traditional methods of interaction with ES can be a burden to users who are forced to translate conceptualizations of problem attributes and characteristics into text form and then convert back to conceptualizations in interpreting and recommending solutions. This burden can be relieved by merging ES with multimedia technology. In addition to text, the user would be able to selectively access information with graphics, full-motion video, or animation; and hear with stereo sound, voice recording, or music. Such a combination provides a powerful interactive interface enabling the various facets of expertise to be more fully communicated to the user. This article describes multimedia expert systems and considerations for implementing them.
Critique of some trends in the TCS community in light of two controversies
Authors: Goldreich Oded
Published: October 2004

I criticize the growing influence of some "trade-unionism'' attitudes in the Theoretical Computer Science community. I trace these attitudes in the arguments used in two recent controversies which attracted much attention: the controversy on the acceptance rate in STOC/FOCS conferences and the controversy on anonymous submissions (in Crypto conferences). I believe that these attitudes stand in contradiction to the scientific progress and call for their abolishment.
Innovative teaching materials and methods for systems analysis and design
Authors: Olfman Lorne , Bostrom Robert P.
Published: October 2004

This article describes materials and methods for a course in systems analysis and design. While the article is prescriptive rather than empirical, it offers new directions for instructors who wish to adopt an action research approach to syllabus development. Information systems developers perform two roles in the process of managing a development project: the developer is both analyst/designer and facilitator. Traditional textbooks for systems analysis and design courses emphasize the analyst/designer role, but say little about the facilitator role. We have developed course materials and teaching methods to address facilitation skills: outcome thinking, group process, and communications. We also emphasize some analyst/designer skills that are not addressed in the traditional texts, such as creative thinking. socio-technical systems, and CASE tool concepts. Our teaching methods include the personal journal, which allows students to tailor classroom materials to their own needs, as well as other methods for providing experiential learning of course materials.
The diffusion of database machines
Authors: Hoffer Jeffrey A. , Alexander Mary B.
Published: October 2004

This article reports the results of an investigation of organizational assimilation of an emerging information technology—database machines. Results of database machine adoption and implementation are reported, with emphasis on practical implications for managing information technology diffusion. The importance of top management support and champions who push for adoption and implementation are indicated. Other factors discussed include technological awareness, vendor involvement,and training, among others. Built on innovation diffusion and IS implementation studies, a model of organizational-level adoption and implementation underpins the interpretation of the results.
A simulation study of forward error correction in ATM networks
Authors: Biersack Ernst W.
Published: October 2004

If the packet loss rate in a network is higher than the loss rate requested by an application, the transport protocol must make up for the difference in loss rate. In high bandwidth delay-product networks the latency introduced by retransmission-based error recovery schemes may be too high for applications with latency constraints. In this case,
Forward Error Correction
(FEC) can be used. FEC allows recovery from loss without retransmission. The amount of loss recovered strongly depends on the loss behavior of the network. FEC works best if losses are dispersed.We use simulation to study the loss behavior of an output buffered multiplexer for three different traffic scenarios. Our results show how the loss behavior of the multiplexer is affected by the traffic mix and the statistics of the sources. The more bursty the sources are the larger the loss rate and the higher the probability that losses will occur in bursts. We then investigate the effectiveness of an FEC scheme that can recover a fixed number of lost packets within a block of consecutive packets. For a heterogeneous traffic scenario consisting of video and burst sources, this scheme reduces the loss rate for the video sources by several orders of magnitude.