bluuebunny/crossref_metadata_2025 huggingface dataset:
Confronting the assumptions underlying the management of knowledge
Authors: Stewart Kathy A. , Baskerville Richard , Storey Veda C. , Senn James A. , Raven Arjan , Long Cherie
Published: October 2004

Knowledge and knowledge management are receiving tremendous interest from both practitioners and academics. Although knowledge management is often accepted as a very useful organizational activity, a number of the assumptions underlying knowledge management have not been investigated. This paper examines four knowledge management assumptions: knowledge is worth managing, organizations benefit from managing knowledge, knowledge can be managed, and little risk is associated with managing knowledge. The assumptions are analyzed at strategic and operational levels, and both negating and supporting evidence is presented. Based on this analysis, a framework for research in knowledge management is proposed. The framework is used to generate a number of key questions that should be addressed in knowledge management research. Particular attention is given to goals and rewards as well as to the role of information technology in knowledge management.
Computational geometry column 43
Authors: O'Rourke Joseph
Published: October 2004

The concept of pointed pseudo-triangulations is defined and a few of its applications described.
Real-time convergence of Ada and Java
™
Authors: Brosgol Ben , Dobbing Brian
Published: October 2004

Two independent recent efforts have defined extensions to the Java platform that intend to satisfy real-time requirements. This paper summarizes the major features of these efforts, compares them to each other and to Ada 95's Real-Time Annex, and argues that their convergence with Ada95 may serve to complement rather than compete with Ada in the real-time domain.
Using Ada 95 in a compiler course
Authors: Taft S. Tucker
Published: October 2004

In this extended abstract, we describe the use of Ada 95 in a Compiler Construction Course.
Detecting concurrently executed pairs of statements using an adapted MHP algorithm
Authors: Chen Zhenqiang , Xu Baowen , Yu Huiming
Published: October 2004

Information about which pairs of statements in a program can be executed concurrently is important for improving the accuracy of dataflow analysis, optimizing programs, and detecting errors. This paper presents a new method named Concurrent Control Flow Graph for representing concurrent Ada 95 programs in a simple and precise way. Based on this method, we develop an Adapted MHP algorithm that can statically detect all pairs of statements that may be executed concurrently. This algorithm checks not only whether a rendezvous can be triggered, but also whether it can be finished. Although this algorithm generates a conservative superset of the perfect pairs of statements, it is more precise than many existing methods.
Vetronics technology testbed
Authors: Pritchett William , Wood Brian
Published: October 2004

The Vetronics (
ve
hicle elec
tronics
) Technology Testbed (VTT) is a research project being developed by the U.S Army Tank-Automotive Research Development and Engineering Center (TARDEC). The main objective of the VTT is to demonstrate the capability of one crewmember to perform the functions of both the vehicle Commander and Driver. The demonstration was required to take place while operating over military-significant terrain and while performing a military-significant mission. In order to accomplish this objective, TARDEC adapted and integrated crew station designs (Figure 1) developed under the Crewman's Associate Advanced Technology Demonstrator (ATD).In addition, hardware and software developed under the INter-Vehicle Embedded Simulation Technology (INVEST) Science and Technology Objective (STO) was used to create realistic simulated operating and training scenarios for the crewmembers. Another goal of the project was to demonstrate the technology in a platform comparable (mobility, size, weight, etc.) to the currently envisioned Future Combat Vehicle (FCV).Several key technologies and capabilities were incorporated into the VTT and include the following:• Drive-by-wire capability• Day and night operation• Indirect vision as the primary vision• Three-dimensional (3D) audio system• Speech Recognition and Generation• Multi-function displays with touch screens• Embedded simulation as an enabling technology for embedded training, mission rehearsal, battlefield visualization and after action review• WSTAWG Operating Environment (OE) [1]• Joint Variable Message Format (JVMF) [2]• Communication via voice intercom and SINCGARS radios
Unicorn
Authors: Ong T. M. , Lim T. M. , Lee B. S. , Yeo C. K.
Published: October 2004

Unicorn provides an architecture using Java to harness the vast processing power on the Internet for distributed computing applications. It employs the code-shipping paradigm to broker this processing power. The client can either make use of the suite of applications provided by Unicorn or upload his own applications to the server together with the data to be processed. These tasks are distributed in parallel to idle hosts logged on to the Unicorn server. A set of Unicorn programming tools, including the Unicorn Application Interface and Broker ServerLite (a scaled-down version of Unicorn Broker Server), is distributed to clients to facilitate applications development. The framework handles all the communication needs of the broker and hosts, leaving the clients to concentrate on the functionality of their applications. In addition, a mechanism for resource pricing has been incorporated to provide incentives for sharing of processing power. The clients are charged and host systems are paid according to the resources used. The broker takes a commission in the transactions.
Large-scale experimental study of Internet performance using video traffic
Authors: Loguinov Dmitri , Radha Hayder
Published: October 2004

In this paper, we analyze the results of a seven-month real-time streaming experiment, which was conducted between a number of unicast dialup clients, connecting to the Internet through access points in more than 600 major U.S. cities, and a backbone video server. During the experiment, the clients streamed low-bitrate MPEG-4 video sequences from the server over paths with more than 5,000 distinct Internet routers. We describe the methodology of the experiment, the architecture of our NACK-based streaming application, study end-to-end dynamics of 16 thousand ten-minute sessions (85 million packets), and analyze the behavior of the following network parameters: packet loss, round-trip delay, oneway delay jitter, packet reordering, and path asymmetry. We also study the impact of these parameters on the quality of real-time streaming.
A bandwidth advisor for wireless networks
Authors: Judd Glenn , Steenkiste Peter
Published: October 2004

Many network intensive applications can benefit substantially from reasonable estimates of future available bandwidth. As a simple example, consider a user, John, that is about to board a flight that is leaving shortly. Using his palmtop equipped with the Aura ubiquitous computing system, John has just finished editing some very large documents that he needs to email over the airport's wireless network. Just before he begins transmission, a 747 begins deplaning passengers at a gate adjacent to where John is waiting; these deplaning passengers are heavily loading the network in John's cell. John's Aura client contacts the bandwidth advisor and learns that there is insufficient bandwidth for John to complete his transmission before his plane leaves. Fortunately, Aura learns from the bandwidth advisor that a nearby cell has ample bandwidth which enables John to move into that cell briefly and complete his transmission before catching his plane.The utility of bandwidth advisors has lead to efforts such as Remos and the Network Weather Service which have investigated providing bandwidth advice in wired network settings. This research builds on this previous work by developing a bandwidth advisor that is specifically tuned for wireless networks, and is suited to the needs of mobile applications.
Multi-modal network protocols
Authors: Balan Rajesh Krishna , Akella Aditya , Seshan Srini
Published: October 2004

Many of the basic parameters of a ubiquitous computing environment are highly variable. For example, rate of mobility, quality of wireless communication, density of communicating nodes, power constraints and computational constraints all vary greatly from situation to situation. Unfortunately, existing routing protocols, transport protocols and adaptive applications can only adapt in a limited way. One feature that is missing from many systems is the ability to identify gross operating conditions and take on very different modes of operation. Such adaptability would improve the efficiency of many solutions. We use the term multi-modal protocols to describe systems that adapt in this way. We have explored two such systems: Wireless TCP and Overlay Routing.
Generating realistic routing tables in a test-lab
Authors: Maennel Olaf , Feldmann Anja
Published: October 2004

Lots of new features are added to the Internet every day to improve quality of service. These features include RED, fair queuing, etc. Unfortunately testing and evaluation of the effectiveness of these mechanisms in test environments is often limited by the simplicity of the test setup. Yet, variability is necessary to locate equipment bugs and to evaluate the features benefits. As a result the real test is the deployment in the operational network - not a sound testing methodology.As a first step towards addressing this problem, we are building a tool that can generate realistic routing tables of arbitrary size and updates of arbitrary frequency. To this end, we first define a set of metrics that can capture important characteristics of routing tables and routing updates. Next, we present insights of a characterization of measured routing tables and updates and identify some key insights. These results are then used to parameterize our tool. Finally, we describe the key ideas behind the tool and conclude with a brief discussion of future work.
Sources of dissatisfaction in end-user support
Authors: Shaw Nancy C. , DeLone William H. , Niederman Fred
Published: October 2004

Organizations are investing in information technology for an ever-increasing number of end-user tasks. Extracting benefits from these investments increasingly depends on supporting effective use of information technology and satisfying information technology users. This research explores the end-user support factors that correlate with user satisfaction. This survey of 484 end-users examines 21 potential end-user computing support factors, such as system response time and user training in terms of their perceived importance to the end-user and the performance of IS staff in supporting each. Service quality, the gap between perceived importance and performance for each support factor, is computed. The relationships between these service quality gaps and user satisfaction are tested across different user groups (faculty, non-IS staff and students). Larger service quality gaps in the following support factors were correlated with lower user satisfaction in at least one of the three user groups: IS staff response time, IS staff technical competence, software upgrades, ease of access, cost effectiveness of the system, user understanding, documentation to support training, and data security/privacy. These results are compared to the support factors identified as significant in previous empirical studies.
Simulating inheritance with Ada
Authors: Perez E.
Published: October 2004

Inheritance is one of the key concepts of the object-oriented paradigm. In this article, we briefly review a very commonly known model of inheritance---Smalltalk 80---and the different steps that are taken in the inheritance process. We then analyze the Ada concept of derived types in order to simulate the inheritance mechanism that has been presented. By means of short Ada examples, it is shown how the derived types can help us with each of the steps defined in the model of inheritance presented.
An integrated Ada programming environment: AWA
Authors: Xing G. , Rau H. , Liu B. , Shen J. , Zhu M.-Y.
Published: October 2004

Programming environments are one of the hottest research topics in today's computer science society. This report presents our initial efforts on understanding the concept of a programming environment and a first attempt on building an integrated Ada programming environment.
Service specification and protocol construction for the transport layer
Authors: Murphy S. L. , Shankar A. U.
Published: October 2004

In a computer network, the transport layer uses the service offered by the network layer and in turn offers its users the transport service of reliable connection management and data transfer. We provide a formal specification of the transport service in terms of an event-driven system and safety and progress properties. We construct three verified transport protocols that offer the transport service. The first transport protocol assumes a perfect network service, the second assumes loss-only network service, and the third assumes loss, reordering and duplication network service.

Our transport service specifications are very realistic. Each user can be closed, listening, active opening, passive opening, open, or closing. A local incarnation number uniquely identifies every active opening and listening duration. Users can issue requests for connection, listening, closing, data send, etc. The transport layer issues indications for successful or unsuccessful connection, closing, data reception, etc. A connection is established only if one user requested the connection and the other was listening, or both requested the connection. A user receives data only from the appropriate incarnation of the distant user, and receives it insequence, without loss or duplication. Progress properties ensure that every outstanding user request is eventually responded to by an appropriate transport indication.

Our protocols are constructed by stepwise refinement of the transport service. The construction method automatically generates a verification that the protocols satisfy the transport service. One distinctive feature of our protocol construction is that the events and verification of the data transfer function is directly obtained from any one of the numerous verified single-incarnation data transfer protocols already presented in the literature.
Measured capacity of an Ethernet: myths and reality
Authors: Boggs D. R. , Mogul J. C. , Kent C. A.
Published: October 2004

Ethernet, a 10 Mbit/sec CSMA/CD network, is one of the most successful LAN technologies. Considerable confusion exists as to the actual capacity of an Ethernet, especially since some theoretical studies have examined operating regimes that are not characteristic of actual networks. Based on measurements of an actual implementation, we show that for a wide class of applications, Ethernet is capable of carrying its nominal bandwidth of useful traffic, and allocates the bandwidth fairly. We discuss how implementations can achieve this performance, describe some problems that have arisen in existing implementations, and suggest ways to avoid future problems.
The use of business graphics
Authors: Dennis Alan R.
Published: October 2004

Business graphics are any form of graphics used by individual knowledge workers to support their activities. The classification system presented in this paper can be used to identify graphics needs and classify graphic system features. The classification system has six dimensions: form, media, quality, speed, ease of learninglease of use, and flexibility. In a study at Queen's University, most of the business graphics produced with micro-computers were text charts used to support oral presentations. Most end users preferred easy-to-use microcomputer-based tools to more flexible mainframe tools. Surprisingly, users with little prior computer experience were as likely to use computer generated computer graphics (and use the microcomputer tools themselves to create business graphics), as their more experienced counterparts. This pattern differs sharply from that on the university's central mainframe, where experienced users prepare mostly graphs.
A real-time expert system for computer network monitor and control
Authors: Dunning Barton B. , Switlik John
Published: October 2004

SEMACS is a continuous, real-time expert monitor and control system that actively and passively monitors a computer network. It detects and diagnoses hardware and software problems with the network and provides advice and solutions to anoperator in his domain of influence. It was developed jointly by Sperry and one of its customers during an Expert Systems Apprenticeship with the Sperry Knowledge Systems Center. The prototype system, which includes all major components of the final, operational system, was developed over a period of six weeks, and an operational system was put on-line within 3 months of starting the project.
Performance modelling of the Orwell basic access mechanism
Authors: Zafirovic M. , Niemegeers I. G.
Published: October 2004

Orwell is a high speed slotted ring. Its protocol uses destination release of the slots. Because of this the carried load can be much larger than the transmission rate. A new analytical model of the Orwell basic access mechanism is presented in this paper. The model shows to be accurate and usable over a wide range of parameters. The performance analysis of the Orwell basic access mechanism is presented.
The Sigma network
Authors: Saito K.
Published: October 2004

The Sigma network is one of the most important element of the Sigma system which is designed to improve productivity of a software.

The Sigma network has been developed in order to establish a infrastructure which acts as development environment provided by logically integrated Sigma workstations spread over various companies and inside the companies which approve the concept of the Sigma system. It is also included in the scope of its development to enrich application programs mainly for message communication required by network community.

The network supports IEEE802.3, digital packet exchange (X.25) and serial line under the TCP/IP layer and realizes end-to-end immediate communication.

Sigma network is a name oriented virtual network defined by hierarchical name space (domain) and named objects placed under the domains. Its key feature lies in the network management mechanism, i.e. Name Server.
Adaptive routing in Burroughs network architecture
Authors: Rosenberg J. L. , Gruchevsky S. A. , Piscitello D. M.
Published: October 2004

The routing function used for Burroughs Network Architecture (BNA) to determine the best routes for traffic through the network is known as the
Burroughs Integrated Adaptive Routing System
, or BIAS™
1

Based on the algorithm devised for the MERIT Computer Network [3], BIAS™ is a decentralized, deterministic system which adapts to changes in network topology automatically. The Current BIAS™ routing architecture incorporates improvements [1] in the original algorithm which significantly reduce the recovery time from failures of nodes or links and is virtually loop-free, even during recovery from those failures.

BIAS™ automatically re-determines the best routes for traffic throughout the network in response to the following changes to the network topology:

a node (an end system or intermediate system) is added to the network;

a node is removed from the network;

the cost of transiting a node is changed;

a logical link (LAN, leased or switched circuit, X.25 virtual circuit) is added to the network;

a link is removed from the network; and/or

the cost of transiting a link is changed.
The IC system for protocol development
Authors: Cohen D. M. , Guinther T. M.
Published: October 2004

The realization of a new protocol is a long and complicated procedure whose inherent technical difficulty is exacerbated by the scarcity of useful tools. This paper discusses the initial use of a system that is being developed by Bell Communication Research to help in the specification, analysis, and implementation of communications protocols. This paper describes the application of this system to the specification and implementation of an industry standard protocol.
Strategies for decentralized resource management
Authors: Stumm M.
Published: October 2004

Decentralized resource management in distributed systems has become more practical with the availability of communication facilities that support multicasting. In this paper we present several example solutions for managing resources in a decentralized fashion, using multicasting facilities. We review the properties of these solutions in terms of scalability, fault tolerance and efficiency. We conclude that decentralized solutions compare favorably to centralized solutions with respect to all three criteria.
A network environment for computer-supported cooperative work
Authors: Whitescarver J. , Mukherji P. , Turoff M. , DeBlock R. J. , Czech R. M. , Paul B. K.
Published: October 2004

A second generation computer supported cooperative work system called Electronic Information Exchange System (EIES2) is described in this paper. The EIES2 communications environment allows users to network across geographical constraints using asynchronous or synchronous communications. The architecture of the network environment is decentralized, and is implemented using modern standards, and an easy-to-use user interface.

At the heart of EIES2 is a high-level, object oriented pseudo machine which incorporates a distributed, communications-oriented database.

The set of tools provided by the EIES2 communications environment is well suited for implementing group communication systems that have an extensive set of user features built into it. These tools are well suited to support the group communication model described by the AMIGO task force (IFIP 6.5 and ISO TC97/SC18/WG64). The EIES2 application layer protocols, using CCITT/ISO X.410 Remote Operations, support a distributed object oriented database.
Integrating X.400 message handling into the IBM VM/SP environment
Authors: Fischer K. , Racke W. F.
Published: October 2004

A prototype X.400 message handling system for IBM's VM/SP operating system is discussed. The system is designed to provide smooth integration of X.400 services into the predominantly used means of interpersonal communication in the VM/SP environment (RSCS). The system provides native X.400 services to its users and therefore is not a gateway between RSCS and X.400 protocols.
Receiver-initiated busy-tone multiple access in packet radio networks
Authors: Wu C. , Li V.
Published: October 2004

The ALOHA and Carrier Sense Multiple Access (CSMA) protocols have been proposed for packet radio networks (PRN). However, CSMA/CD which gives superior performance and has been successful applied in local area networks cannot be readily applied in PRN since the locally generated signals will overwhelm a remote transmission, rendering it impossible to tell whether a collision has occurred or not. In addition, CSMA and CSMA/CD suffer from the “hidden node” problem in a multihop PRN. In this paper, we develop the Receiver-Initiated Busy-Tone Multiple Access Protocol to resolve these difficulties. Both fully connected and multihop networks are studied. The busy tone serves as an acknowledgement and prevents conflicting transmissions from other nodes, including “hidden nodes”.
Fragmentation considered harmful
Authors: Kent C. A. , Mogul J. C.
Published: October 2004

Internetworks can be built from many different kinds of networks, with varying limits on maximum packet size. Throughput is usually maximized when the largest possible packet is sent; unfortunately, some routes can carry only very small packets. The IP protocol allows a gateway to
fragment
a packet if it is too large to be transmitted. Fragmentation is at best a necessary evil; it can lead to poor performance or complete communication failure. There are a variety of ways to reduce the likelihood of fragmentation; some can be incorporated into existing IP implementations without changes in protocol specifications. Others require new protocols, or modifications to existing protocols.
Synchronization
Authors: Belpaire Gerald
Published: October 2004

This paper exposes an idea to define a framework within which this twofold reality will be reflected, together with a method to define with precision the problems of synchronization at their proper level of abstraction. As such, it attempts to give an answer to the question of understanding what characterizes a problem of synchronization, how it is related to a programming method and what are the aspects of its implementation.
Some considerations for a high performance message-based interprocess communication system
Authors: McQuillan John M. , Walden David C.
Published: October 2004

We continue to be concerned with interprocess communications systems (such as those described in references 1, 2, and 3 and called “thin-wire” communications systems in reference 4) which are suitable for communication between processes that are not co-located in the same operating system but rather reside in different operating systems on different computers connected by a computer communications network. Further, the systems with which we are concerned are assumed to communicate using addressed messages (e.g., reference 5) which are multiplexed onto the logical communications channel between the source process and the destination process, rather than using such traditional methods as shared memory (an impossibility for distributed communicating processes) or dedicated physical communications channels between pairs of processes desiring to communicate (which is considered to be prohibitively expensive).
Review of
Petri Net Algebra
Authors: Mikolajczak Boleslaw
Published: October 2004

Many contemporary computing systems are concurrent and distributed. Many approaches to concurrency formalization have been introduced over last forty years. This monograph combines two theories of concurrency: process algebras and Petri nets. One can hope that combining several competing theories that are mutually complementary can produce a formalism that will be practically useful. This is the primary motivation of the book. The book investigates structural and behavioral aspects of these two models. It also shows strong equivalence between these two models. Process algebras have the following advantages: allow study of connectives directly related to actual programming languages, are compositional, come with a variety of concomitant and derived logics that support reasoning about important properties of systems, and come with variety of algebraic laws that help in systems' refinement and in proving corrctness. Petri nets clearly distinguish local states and local activities of a system (places and transitions, respectively), global states and activities can be derived from basic concepts, Petri nets are graphical, and as bipartite graphs have strong links to graph theory and linear algebra. These last two facts can be used for the verification of systems.
Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services
Authors: Gilbert Seth , Lynch Nancy
Published: October 2004

When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three. In this note, we prove this conjecture in the asynchronous network model, and then discuss solutions to this dilemma in the partially synchronous model.
Comments on "transparent user-level process checkpoint and restore for migration" by Bozyigit and Wasiq
Authors: Rauch Felix , Stricker Thomas M.
Published: October 2004

The simple checkpointing and migration system for UNIX processes as described in the article of Bozyigit and Wasiq [1] can be improved in two ways: First by a technique to checkpoint and migrate applications without the need to recompile them and second by an alternative approach to precisely locate all the data segments of a process that need to be checkpointed. We fully acknowledge the difficulty to do checkpointing or even portable checkpointing for the general case of processes and do not claim to solve the many remaining problems with the simplistic checkpointing and migration approaches presented in the earlier article. Still we are aware of many systems and applications where a simple solution is extremely helpful once it also works with binaries.
The concept of
causal-phase
ordering for overlapped broadcasts
Authors: Amanton Laurent , Naïmi Mohamed
Published: October 2004

The virtual synchrony has received a lot of attention in the literature due to it's importance for distributed applications. Most of algorithms that determine global states cut program's execution without taking account of messages groups. The processes exchange messages without a particular ordering inside each phase. But messages of two successive phases must be ordered according to the causal relation. The paper presents the concept of causal-phase and an algorithm, which guarantees that the change of phase of a distributed system is safely performed, i.e., that the causal ordering of the messages events is being respected. In contrast to previous approaches, our protocol is able to handle the multi-initiator case where the change of phase is simultaneously requested by several sub-processes without requiring any kind of master process. This special scheduling establishes a synchronization between two distinct phases that may overlap, while preserving the asynchrony of the communications, without blocking the processes.
A peering architecture for ubiquitous IP multicast streaming
Authors: Yeo C. K. , Lee B. S. , Er M. H.
Published: October 2004

IP Multicast has been widely used for the distribution of real-time video. However, a large portion of the Internet is not multicast-enabled. Such networks rely on static relays and static tunnels to support video streaming. Being static, the streaming cannot readily adjust to the changing network conditions. This paper proposes an application level overlay using peering technology for seamless ubiquitous multimedia streaming across both multicast and unicast networks. The overlay comprises an auto-configurable tree of dynamic client relays incorporating a lightweight gossip mechanism to monitor prevailing network conditions and to improve the tree robustness. Clients can dynamically switch to other parents if they experience a poor QoS. Experimental results show that the overlay provides much better quality delivery than conventional unicast relay services.
Review ofDynamic Logic (Foundations of Computing)
Authors: Pucella Riccardo
Published: October 2004

In the 1960s, as programming languages were being used to write larger programs, those programs became harder to understand, and people began to worry about issues such as correctness, that is, determining whether a program computed what it was supposed to compute. As a consequence, researchers started to look into the pragmatics of programming, leading among others to a criticism of the GOTO statement [2] and the development of structured programming by Knuth and Wirth. These greatly helped writing programs that were easier to understand, but the issue of showing program correct remained. Undoubtedly helped by the fact that programs had a cleaner structure, researchers began investigating formal approaches to proving programs correct, or, in general, proving that programs satisfied properties of interest. Most approaches involved deriving the proof of a property as one was writing the program, taking advantage of the structured way these programs were written [3, 8]. These approaches were formalized, leading to the total or partial correctness assertions of Hoare [10] or the weakest-precondition calculus of Dijkstra [3]. Essentially, the logic of Hoare dealt with assertions {A}P{B} around a programP,indicating that ifAwere true, executing programPwould result inBbeing true. Inference rules indicated how to transform assertions about programs into assertions about larger programs. For instance, if {A}P1{B} and {B}P2{C} were true, then one could infer that {A}P1;P2{B} was true, with the intuitive reading ofP1;P2as the sequential composition ofP1andP2.Many more formal systems along such lines were devised, and they collectively acquired the namelogics of programs,orprogram logics.In a 1976 landmark paper, Pratt recognized that many such program logics could best be understood as modal logics, by essentially associating with every program a modal operator [13]. His idea was developed and refined by Fischer and Ladner [6] and others, culminating into a particular form of program logic calledDynamic Logic.Basically, the recognition of the relationship between program logic and modal logic allowed researchers to make use of the vast array of results on modal logics.The book "Dynamic Logic", by Harel, Kozen, and Tiuryn, offers a self-contained introduction to the subject. The earlier treatments on the subject are either dated, such as the survey by Harel [9] giving the state of the field in 1984, or study Dynamic Logic as a non-trivial extension of modal logic [7]. The latter approach is much more abstract and technically involved. In this review, I hope to give a taste for the subject by looking at its simplest incarnation, the propositional variant of Dynamic Logic, called PDL. (The book describes both the propositional and the first-order variants.) Following which, I will return to the structure of the book, and some personal opinions.
Can a computer proof be elegant?
Authors: Seiden Steve
Published: October 2004

In computer science, proofs about computer algorithms are par for the course. Proofs
by
computer algorithms, on the other hand, are not so readily accepted. We present one viewpoint on
computer assisted proofs,
or what we call proofs via the
computational method
[13]. While one might expect pure mathematicians to be a bit leery of the computational method, one would hope that computer scientists would be more receptive. In the author's experience, this has not been the case. The comment one often hears is "Can't you find a better proof"? One of the arguments given against the computational method is that a computer assisted proof cannot possibly be
elegant.
We question this argument here.It is important to define precisely what the computational method is. In the computational method we seek to
prove
results using a computer program. More specifically, given a theorem we want to prove, we exhibit a computable Boolean function
f
and prove that the truth of
f
implies the theorem. Next, we give an algorithm for computing
f.
Finally, we execute this algorithm on a computer. If all goes well, the theorem is proven. The first (as far as we know) and most famous use of the computational method was in the proof of the four-color theorem by Appel and Haken [2]. This should be contrasted with the use of a computer to find a proof that is easily checked by hand. For instance, a counter-example found via a computer search, as in [9, 10], is not an example of the computational method.As the proof of the four-color theorem was the first use of the computational method, it generated a large amount of controversy. Foremost among the decryers of the Appel and Haken proof was Halmos [7, page 578], who states:By an explosion I mean a load noise, an unexpected and exciting announcement, but not necessarily a good thing. Some explosions open new territories and promise great future developments; others close a subject and seem to lead nowhere. …the four-color theorem [is] of the second [kind].Halmos goes further, attacking the computational method in general, stating "Down with oracles, I say---they are of no use in mathematics". While we cannot speak to the four-color theorem proof---the author has not seen it---we disagree with Halmos' assertion that computer proofs have no use in mathematics.In [13], we tried to give some motivation for using the computational method and address some of the complaints against it. We tried to argue that, in certain cases, a computer proof may be preferable to a traditional one. However, we feel that one point overlooked in [13], namely the question of elegance of computer proofs, should be addressed. Other authors have also addressed the question of computer aided proofs. For some alternative viewpoints, see [3, 4, 5, 7, 11, 12, 14].
Review of
Spectral Graph Theory
Authors: Lurie Jacob
Published: October 2004

Specifying a graph is equivalent to specifying its adjacency relation, which may be encoded in the form of a matrix. This suggests that study of the adjacency matrix from a linear-algebraic point of view might yield valuable information about graphs. In particular, any invariant associated to the matrix is also an invariant associated to the graph, and might have combinatorial meaning. Spectral graph theory is the study of the relationship between a graph and the eigenvalues of matrices (such as the adjacency matrix) naturally associated to that graph. This book looks at the subject from a geometric point of view, exploiting an analogy between a graph and a Riemannian manifold: Chung defines the
Laplacian
of a graph, a matrix closely related to the adjacency matrix, in analogy with the continuous case and studies the eigenvalues of this Laplacian.There are several reasons that these eigenvalues may be of interest. On the purely mathematical level, the eigenvalues have the advantage of being an extremely natural invariant which behaves nicely under operations such as Cartesian product and disjoint union. From a combinatorial point of view, the eigenvalues of a graph are related to many other more "discrete" invariants. From a geometric point of view, there are many respects in which the eigenvalues of a graph behave like the spectrum of a compact Riemannian manfiold. For the computationally-minded, the eigenvalues of a graph are easy to compute, and their relationship to other invariants can often yields good approximations to less tractible computations.
Reprints from
Computing Reviews
Authors: Seiferas Joel
Published: October 2004

As a service to our readers.
SIGACT News
has an agreement
with
Computing Reviews
to reprint 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 subjects. Including
models of computation, formal languages. computational complexity
theory. analysis of algorithms and logics and semantics of
programs. ACM members can receive a subscription to
Computing
Reviews
for $45 per year by writing to ACM headquarters.
Exception propagation
Authors: Sandén Bo I.
Published: October 2004

As an introduction to this session, a brief background of the topic was discussed.Propagation deals with the communication of information regarding unexpected happenings from one context to another within a software system.For exception handling, there are three dimensions to the process of design:
Information content
--- what to tell
Receptors
--- whom to tell
Strategy
--- when to tellWithin these three dimensions, there are four primary design considerations:
Responsibility
--- Which units of the structure detect the unexpected event, which units communicate the events, and which units perform recovery?
Granularity of information
--- How much detail needs to be in the information that is communicated regarding the unexpected event? Fine-grained information may be necessary for recovery purposes, while more coarse-grained information may be sufficient for simple indication of errors.
Types of information
--- The nature of the information propagated needs to be decided. Possibilities include describing the origin of the exception, the cause of the exception, or the recovery strategy to be followed.
Exception mapping
--- What transformations or manipulations of the exception information are performed as it passes over context boundaries within the system? This aspect is at the core of designing propagation into a system, and is driven by decisions made for the first three considerations.Mapping of exceptions across program segment boundaries, that is, the propagation of the exceptions, can take place in four general ways.---
Refinement
- where the exceptions are filtered, with some being stopped and others being propagated.---
Generalization
- where the exceptions are aggregated to create exception abstractions.---
Translation
- where the exceptions are mapped one-to-one but with a change of name or information content.---
Preservation
- where the exceptions are mapped unchanged.
Except for exception handling …
Authors: Romanovsky Alexander , Sandén Bo
Published: October 2004

Exception handling in Ada has a number of well-known problems. It allows for the propagation of unhandled and anonymous exceptions, it is error-prone and it is inappropriate for some language features such as tasking and tagged types. Ada programs with exceptions can be difficult to understand, develop, modify and analyse, and the exception handling features can be misused in a number of ways.In this paper we introduce the requirements for good exception handling features. We classify the problems with Ada exception handling into two subsets: serious conceptual problems that require an improvement of the language features, and problems attributable to the misuse of the existing features. Problems in the second category can be solved by improving programmers' understanding of the features and ways of using them.
Exceptions as types
Authors: Leroy Pascal
Published: October 2004

The purpose of this paper is to propose a new language feature, dubbed
exception types,
to support a more flexible exception paradigm in Ada. This mechanism attempts to retain compatibility with Ada 95, while providing a general communication framework similar to that which exists in C++ or Java.Ada 83 had a very basic exception mechanism. It was not possible to pass information when raising an exception, and exceptions were not integrated with the overall type structure of the language, making it impossible to pass exception-related information to subprograms, or to store it in data structures, etc.Ada 95 added slightly more powerful capabilities in this area, with the facilities provided by the predefined package Ada.Exceptions. However, the new mechanism is still only intended for very basic error detection and logging, and doesn't provide a general-purpose communication mechanism. It has the merit of clarifying the notions of exception identity and exception occurrence, but exceptions are still not integrated with the typing model like protected objects or tasks are.It is in fact possible to use the Message associated with an exception occurrence to pass (relatively small) objects when raising an exception, but this has to be done by marshalling the object into the string. While adequate for some purposes, this approach is unnecessarily contrived.This situation is very unfortunate, because other modern programming languages like C++ or Java, which are in other ways inferior to Ada, have a much more powerful exception mechanism.
On exceptions as first-class objects in Ada 95
Authors: Wolf Thomas
Published: October 2004

This short position paper argues that it might be beneficial to try to bring the exception model of Ada 95 more in-line with the object-oriented model of programming. In particular, it is felt that exceptions --- being such an important concept for the development of fault-tolerant software --- have deserved a promotion to first-class objects of the language. It is proposed to resolve the somewhat awkward dichotomy of exceptions and exception occurrences as it exists now in Ada 95 by treating exceptions as (tagged) types, and exception occurrences as their instances.
MOPping up exceptions
Authors: Mitchell S. E. , Burns A. , Wellings A. J.
Published: October 2004

This paper describes the development of a model for the reflective treatment of both application and environmentally sourced exceptions. We show how a variety of exception models can be implemented using an exception handler at the metalevel. The approach described allows for better separation of exceptional and normal error-free program code producing systems that are easier to understand and therefore maintain.
A socket-based manifestation of streams
Authors: Criley Marc A.
Published: October 2004

The Ada.Streams package, hereafter referred to simply as the Streams package, introduced into Ada 95 a standard mechanism for the storage and transmission of heterogeneous data within and amongst Ada programs. Section 13.13 of the Ada 95 LRM defines the streams features of the language, specifying the programmatic interface and behavior of this capability. It states that a "stream type may be implemented in various ways, such as an external sequential file, an internal buffer, or network channel." The Ada standard then goes on to define in Appendix A.12 the packages Streams.Stream_IO, Text_IO.Text_Streams, and Wide_Text_IO.Text_Streams, which provide stream-oriented operations on files.Files, however, are merely one option for the implementation of stream-based communication. By suitably extending the Stream package's Root_Stream_Type and providing corresponding Read and Write procedures, a stream can be associated with any communication or storage medium. Applications employing the standard stream-oriented attributes defined in LRM 13.13.2 can transparently communicate, store, or load data items as governed by the application's extension of a stream.This paper illustrates and implements a simple socket-based extension of a stream to demonstrate the flexibility of the Ada 95 Stream capability and the ease with which streams can be associated with other communication media.
Conflict resolution for readers and writers
Authors: Levine Gertrude
Published: October 2004

For those of us who have been teaching Operating Systems for years, you may remember with nostalgia the days when Operating Systems texts [ex: Deitel 1984] included Ada code to illustrate solutions for concurrency problems. I find concurrency the most difficult topic to teach in Operating Systems, and expressing solutions in Ada is a strong teaching aid. Ada's tasking construct is powerful and readable. In addition, an Ada Programming Support Environment enables hands-on experimentation.The Readers/Writers problem, a classic mutual exclusion synchronization problem, puzzled computer science professionals for years. Explaining these solutions, as presented in current Operating Systems texts, is daunting.We contrast code expressed in
C
to that proposed by Burns [Burns1985] and Barnes [Barnes1995] for readability. We then suggest a slight modification to obtain what we consider to be a preferred solution, one that illuminates concurrency issues in general.
Diversely designed classes for use by multiple tasks
Authors: Romanovsky Alexander
Published: October 2004

This paper proposes a new N-version programming (NVP) scheme which allows several caller tasks to jointly use components which are designed diversely. Diversity is applied here at the level of classes in such a way that several version classes (objects) are developed separately and independently, and are encapsulated into a diversely designed object. Such objects are to be implemented in a special stylised way to incorporate a controlling mechanism which would deal with task and version synchronisation, adjudication of version output parameters and states, faulty version recovery, etc. The general approach is demonstrated using Ada. We outline the characteristics of applications which benefit from using such NVP scheme, discuss the engineering of diversely designed objects and of the software which uses them and describe several possible extensions of the scheme.