bluuebunny/crossref_metadata_2025 huggingface dataset:
The structure and performance of interpreters
Authors: Romer Theodore H. , Lee Dennis , Voelker Geoffrey M. , Wolman Alec , Wong Wayne A. , Baer Jean-Loup , Bershad Brian N. , Levy Henry M.
Published: October 2004

Interpreted languages have become increasingly popular due to demands for rapid program development, ease of use, portability, and safety. Beyond the general impression that they are "slow," however, little has been documented about the performance of interpreters as a class of applications.This paper examines interpreter performance by measuring and analyzing interpreters from both software and hardware perspectives. As examples, we measure the MIPSI, Java, Perl, and Tcl interpreters running an array of micro and macro benchmarks on a DEC Alpha platform. Our measurements of these interpreters relate performance to the complexity of the interpreter's virtual machine and demonstrate that native runtime libraries can play a key role in providing good performance. From an architectural perspective, we show that interpreter performance is primarily a function of the interpreter itself and is relatively
independent
of the application being interpreted. We also demonstrate that high-level interpreters' demands on processor resources are comparable to those of other complex compiled programs, such as gcc. We conclude that interpreters, as a class of applications, do not currently motivate special hardware support for increased performance.
Compiler-based prefetching for recursive data structures
Authors: Luk Chi-Keung , Mowry Todd C.
Published: October 2004

Software-controlled data prefetching offers the potential for bridging the ever-increasing speed gap between the memory subsystem and today's high-performance processors. While prefetching has enjoyed considerable success in array-based numeric codes, its potential in pointer-based applications has remained largely unexplored. This paper investigates compiler-based prefetching for pointer-based applications---in particular, those containing recursive data structures. We identify the fundamental problem in prefetching pointer-based data structures and propose a guideline for devising successful prefetching schemes. Based on this guideline, we design three prefetching schemes, we automate the most widely applicable scheme (
greedy prefetching
) in an optimizing research compiler, and we evaluate the performance of all three schemes on a modern superscalar processor similar to the MIPS R10000. Our results demonstrate that compiler-inserted prefetching can significantly improve the execution speed of pointer-based codes---as much as 45% for the applications we study. In addition, the more sophisticated algorithms (which we currently perform by hand, but which might be implemented in future compilers) can improve performance by as much as twofold. Compared with the only other compiler-based pointer prefetching scheme in the literature, our algorithms offer substantially better performance by avoiding unnecessary overhead and hiding more latency.
Exploiting dual data-memory banks in digital signal processors
Authors: Saghir Mazen A. R. , Chow Paul , Lee Corinna G.
Published: October 2004

Over the past decade, digital signal processors (DSPs) have emerged as the processors of choice for implementing embedded applications in high-volume consumer products. Through their use of specialized hardware features and small chip areas, DSPs provide the high performance necessary for embedded applications at the low costs demanded by the high-volume consumer market. One feature commonly found in DSPs is the use of dual data-memory banks to double the memory system's bandwidth. When coupled with high-order data interleaving, dual memory banks provide the same bandwidth as more costly memory organizations such as a dual-ported memory. However, making effective use of dual memory banks remains difficult, especially for high-level language (HLL) DSP compilers.In this paper, we describe two algorithms --- compaction-based (CB) data partitioning and partial data duplication --- that we developed as part of our research into the effective exploitation of dual data-memory banks in HLL DSP compilers. We show that CB partitioning is an effective technique for exploiting dual data-memory banks, and that partial data duplication can augment CB partitioning in improving execution performance. Our results show that CB partitioning improves the performance of our kernel benchmarks by 13%-40% and the performance of our application benchmarks by 3%-15%. For one of the application benchmarks, partial data duplication boosts performance from 3% to 34%.
Reducing network latency using subpages in a global memory environment
Authors: Jamrozik Hervé A. , Feeley Michael J. , Voelker Geoffrey M. , Evans James , Karlin Anna R. , Levy Henry M. , Vernon Mary K.
Published: October 2004

New high-speed networks greatly encourage the use of network memory as a cache for virtual memory and file pages, thereby reducing the need for disk access. Because pages are the fundamental transfer and access units in remote memory systems, page size is a key performance factor. Recently, page sizes of modern processors have been increasing in order to provide more TLB coverage and amortize disk access costs. Unfortunately, for high-speed networks,
small
transfers are needed to provide low latency. This trend in page size is thus at odds with the use of network memory on high-speed networks.This paper studies the use of
subpages
as a means of reducing transfer size and latency in a remote-memory environment. Using trace-driven simulation, we show how and why subpages reduce latency and improve performance of programs using network memory. Our results show that memory-intensive applications execute up to 1.8 times faster when executing with 1K-byte subpages, when compared to the same applications using full 8K-byte pages in the global memory system. Those same applications using 1K-byte subpages execute up to 4 times faster than they would using the disk for backing store. Using a prototype implementation on the DEC Alpha and AN2 network, we demonstrate how subpages can reduce remote-memory fault time; e.g., our prototype is able to satisfy a fault on a 1K subpage stored in remote memory in 0.5 milliseconds, one third the time of a full page.
Operating system support for improving data locality on CC-NUMA compute servers
Authors: Verghese Ben , Devine Scott , Gupta Anoop , Rosenblum Mendel
Published: October 2004

The dominant architecture for the next generation of shared-memory multiprocessors is CC-NUMA (cache-coherent non-uniform memory architecture). These machines are attractive as compute servers because they provide transparent access to local and remote memory. However, the access latency to remote memory is 3 to 5 times the latency to local memory. CC-NOW machines provide the benefits of cache coherence to networks of workstations, at the cost of even higher remote access latency. Given the large remote access latencies of these architectures, data locality is potentially the most important performance issue. Using realistic workloads, we study the performance improvements provided by OS supported dynamic page migration and replication. Analyzing our kernel-based implementation, we provide a detailed breakdown of the costs. We show that sampling of cache misses can be used to reduce cost without compromising performance, and that TLB misses may not be a consistent approximation for cache misses. Finally, our experiments show that dynamic page migration and replication can substantially increase application performance, as much as 30%, and reduce contention for resources in the NUMA memory system.
A taxonomy of coordination mechanisms used by real-time processes
Authors: Fernandez José L.
Published: October 2004

A taxonomy of the coordination mechanisms for the synchronization and communication of concurrent processes is proposed. The taxonomy deals with the issues of a real-time software architecture that are application domain independent. The taxonomy will help the designer select the best coordination mechanism for a particular situation.A software reuse domain analysis methodology has been used to develop the taxonomy. While Ada is the programming language that has been considered here, some of the attributes and guidelines are still valid for other programming languages.
A very fast algorithm for RAM compression
Authors: Rizzo Luigi
Published: October 2004

Compressed virtual memory systems have been suggested, and in some cases implemented, to improve the effectiveness of use of physical RAM. However, most proposals and/or implementations are based on adaptive compression algorithms which achieve good compression ratios, but are slow compared to a local disk. Hence, they can only give some advantage with very slow (e.g. network-mounted) swap devices. In this paper we show that in many cases memory pages contain highly compressible data, with a very large amount of zero-valued elements. This suggests the replacement of slow, adaptive compression algorithms with very fast ones based on static Huffman codes.We present one such algorithm which, paired with a careful layout of the data, is able to compress 4KB pages at 40MB/s even when implemented in software on an inexpensive Pentium 100 system. We also show that the algorithm can achieve interesting compression ratios despite its simplicity.Since the compression/decompression speed of our algorithms exceeds disk bandwidth, its use in a compressed VM system can lead to both memory savings and speed improvements in servicing page faults. In this paper we discuss some possible applications of the algorithm in a compressed VM system.
Some better results estimating the shift function in terms of busy beaver function
Authors: Yang Ruiguang , Ding Longyun , Xu Shurun
Published: October 2004

About the relation between the shift function S(n) and the busy
beaver function Σ(n), there have been some results. In 1992,
A. Julstrom gave his result: S(n) < Σ(20n); in 1994, Wang
Kewen and Xu Shurun obtained: S(n) < Σ(10n). In this
paper, we shall show that S(n) ≤ Σ(3n -f c)(c is a
constant).
Journals to Die For
Authors: Hemaspaandra Lane A.
Published: October 2004

Following in the tracks of Pullum's search for the perfect
linguistics journal, we hunt the perfect theory journal.
Building shared trees using a one-to-many joining mechanism
Authors: Carlberg Ken , Crowcroft Jon
Published: October 2004

This paper presents a new approach for building shared trees which have the capability of providing multiple routes from the joining node onto an existing tree. The approach follows a design parameter of CBT and PIM in that it operates independently of any unicast routing protocol. However, a paradigm shift is introduced such that trees are built in an on-demand basis through the use of a one-to-many joining mechanism. In addition, the paper presents optimisations of the new mechanism to help constrain its impact in the case where many receivers exist for a given multicast group.
A unifying methodology for handovers of heterogeneous connections in wireless ATM networks
Authors: Toh C.-K.
Published: October 2004

The aim of Wireless ATM is to provide multi-media services to mobile users. While existing research on Wireless ATM are focussed on handovers of unicast connections, handovers of multicast connections have not been investigated. While conventional multicast join and leave operations occur over the same path, this is not the case during mobile host migrations in a Wireless ATM network. In this paper, we reveal how handovers of multicast connections can be achieved in a manner irrespective of whether these multicast trees are source-, server- or core-based. More importantly, we demonstrate how the enhanced hybrid handover protocol incorporating crossover switch discovery can be used to support handovers of heterogeneous (i.e., unicast and multicast) connections in a uniform and unified manner, for Wireless ATM LANs employing either the centralised or distributed connection management scheme.
Dummynet
Authors: Rizzo Luigi
Published: October 2004

Network protocols are usually tested in operational networks or in simulated environments. With the former approach it is not easy to set and control the various operational parameters such as bandwidth, delays, queue sizes. Simulators are easier to control, but they are often only an approximate model of the desired setting, especially for what regards the various traffic generators (both producers and consumers) and their interaction with the protocol itself.In this paper we show how a simple, yet flexible and accurate network simulator -
dummynet
- can be built with minimal modifications to an existing protocol stack, allowing experiments to be run on a standalone system.
dummynet
works by intercepting communications of the protocol layer under test and simulating the effects of finite queues, bandwidth limitations and communication delays. It runs in a fully operational system, hence allowing the use of real traffic generators and protocol implementations, while solving the problem of simulating unusual environments. With our tool, doing experiments with network protocols is as simple as running the desired set of applications on a workstation.A FreeBSD implementation of
dummynet
, targeted to TCP, is available from the author. This implementation is highly portable and compatible with other BSD-derived systems, and takes less than 300 lines of kernel code.
AIS
Authors: Weber Ron
Published: October 2004

In 1997, the Association for Information Systems will enter its third year of operations. Like any fledgling organization, we have had our "ups and downs." I am greatly encouraged; however, by the substantial progress I believe we have made. In this regard, I would like to acknowledge the fine work done by my two predecessors, Professors Bill King and Niels Björn-Andersen, and my colleagues on the AIS Council.
Conversational group service
Authors: Romanovsky Alexander B.
Published: October 2004

The purpose of this paper is to propose a way of tolerating software (design) faults in distributed systems relying on the well-known conversation (atomic action) approach. To do this, we shall consider differences between two programming paradigms: group communication and conversations, and discuss how a group communication service can be used to provide design fault tolerance by conversations. The main characteristics and peculiarities of this new conversational group service are described.
Quantum cryptanalysis of hash and claw-free functions
Authors: Brassard Gilles , Høyer Peter , Tapp Alain
Published: October 2004

In this note, we give a quantum algorithm that finds collisions in arbitrary τ-to-one functions after only
O
(
3
√
N
/τ) expected evaluations of the function. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Furthermore, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.
The OMG, CORBA, Orbix and Ada
Authors: Clarke David
Published: October 2004

An Object Request Broker (ORB) mediates between applications - including distributed ones. This document presents the design goals and philosophy that lead IONA Technologies to produce the object request broker, Orbix. The Ada language binding is described, and some simple programming examples are given to illustrate its operation.The introduction discusses the needs for ORBs and the industry initiatives that arose from that need - culminating in the OMG's CORBA specifications.
Small forwarding tables for fast routing lookups
Authors: Degermark Mikael , Brodnik Andrej , Carlsson Svante , Pink Stephen
Published: October 2004

For some time, the networking community has assumed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry with the
longest matching prefix
, a task that has been thought to require hardware support at lookup frequencies of millions per second.We present a forwarding table data structure designed for quick routing lookups. Forwarding tables are small enough to fit in the cache of a conventional general purpose processor. With the table in cache, a 200 MHz Pentium Pro or a 333 MHz Alpha 21164 can perform a few million lookups per second. This means that it is feasible to do a full routing lookup for each IP packet at gigabit speeds without special hardware.The forwarding tables are very small, a large routing table with 40,000 routing entries can be compacted to a forwarding table of 150-160 Kbytes. A lookup typically requires less than 100 instructions on an Alpha, using eight memory references accessing a total of 14 bytes.
Skyscraper broadcasting
Authors: Hua Kien A. , Sheu Simon
Published: October 2004

We investigate a novel multicast technique, called
Skyscraper Broadcasting
(SB), for video-on-demand applications. We discuss the data fragmentation technique, the broadcasting strategy, and the client design. We also show the correctness of our technique, and derive mathematical equations to analyze its storage requirement. To assess its performance, we compare it to the latest designs known as
Pyramid Broadcasting
(PB) and
Permutation-Based Pyramid Broadcasting
(PPB). Our study indicates that PB offers excellent access latency. However, it requires very large storage space and disk bandwidth at the receiving end. PPB is able to address these problems. However, this is accomplished at the expense of a larger access latency and more complex synchronization. With SB, we are able to achieve the low latency of PB while using only 20% of the buffer space required by PPB.
Internet routing instability
Authors: Labovitz Craig , Malan G. Robert , Jahanian Farnam
Published: October 2004

This paper examines the network inter-domain routing information exchanged between backbone service providers at the major U.S. public Internet exchange points. Internet routing instability, or the rapid fluctuation of network reachability information, is an important problem currently facing the Internet engineering community. High levels of network instability can lead to packet loss, increased network latency and time to convergence. At the extreme, high levels of routing instability have lead to the loss of internal connectivity in wide-area, national networks. In this paper, we describe several unexpected trends in routing instability, and examine a number of anomalies and pathologies observed in the exchange of inter-domain routing information. The analysis in this paper is based on data collected from BGP routing messages generated by border routers at five of the Internet core's public exchange points during a nine month period. We show that the volume of these routing updates is several orders of magnitude more than expected and that the majority of this routing information is redundant, or pathological. Furthermore, our analysis reveals several unexpected trends and ill-behaved systematic properties in Internet routing. We finally posit a number of explanations for these anomalies and evaluate their potential impact on the Internet infrastructure.
Dynamics of random early detection
Authors: Lin Dong , Morris Robert
Published: October 2004

In this paper we evaluate the effectiveness of Random Early Detection (RED) over traffic types categorized as non-adaptive, fragile and robust, according to their responses to congestion. We point out that RED allows unfair bandwidth sharing when a mixture of the three traffic types shares a link. This unfairness is caused by the fact that at any given time RED imposes the same loss rate on all flows, regardless of their bandwidths.We propose Fair Random Early Drop (FRED), a modified version of RED. FRED uses per-active-flow accounting to impose on each flow a loss rate that depends on the flow's buffer use.We show that FRED provides better protection than RED for adaptive (fragile and robust) flows. In addition, FRED is able to isolate non-adaptive greedy traffic more effectively. Finally, we present a "two-packet-buffer" gateway mechanism to support a large number of flows without incurring additional queueing delays inside the network. These improvements are demonstrated by simulations of TCP and UDP traffic.FRED does not make any assumptions about queueing architecture; it will work with a FIFO gateway. FRED's per-active-flow accounting uses memory in proportion to the total number of buffers used: a FRED gateway maintains state only for flows for which it has packets buffered, not for all flows that traverse the gateway.
Network text editor (NTE)
Authors: Handley Mark , Crowcroft Jon
Published: October 2004

IP Multicast, Lightweight Sessions and Application Level Framing provide guidelines by which multimedia conferencing tools can be designed, but they do not provide specific solutions. In this paper, we use these design principles to guide the design of a multicast based shared editor, and examine the consequences of taking a loose consistency approach to achieve good performance in the face of network failures and losses.
Proof of a fundamental result in self-similar traffic modeling
Authors: Taqqu Murad S. , Willinger Walter , Sherman Robert
Published: October 2004

We state and prove the following key mathematical result in self-similar traffic modeling: the superposition of many
ON/OFF
sources (also known as
packet trains
) with strictly alternating
ON
- and
OFF
-periods and whose
ON
-periods or
OFF
-periods exhibit the
Noah Effect
(i.e., have high variability or infinite variance) can produce aggregate network traffic that exhibits the
Joseph Effect
(i.e., is self-similar or long-range dependent). There is, moreover, a simple relation between the parameters describing the intensities of the Noah Effect (high variability) and the Joseph Effect (self-similarity). This provides a simple physical explanation for the presence of self-similar traffic patterns in modern high-speed network traffic that is consistent with traffic measurements at the source level. We illustrate how this mathematical result can be combined with modern high-performance computing capabilities to yield a simple and efficient linear-time algorithm for generating self-similar traffic traces.We also show how to obtain in the limit a Lévy stable motion, that is, a process with stationary and independent increments but with infinite variance marginals. While we have presently no empirical evidence that such a limit is consistent with measured network traffic, the result might prove relevant for some future networking scenarios.
A cluster-based approach for routing in dynamic networks
Authors: Krishna P. , Vaidya N. H. , Chatterjee M. , Pradhan D. K.
Published: October 2004

The design and analysis of routing protocols is an important issue in dynamic networks such as packet radio and ad-hoc wireless networks. Most conventional protocols exhibit their least desirable behavior for highly dynamic interconnection topologies. We propose a new methodology for routing and topology information maintenance in dynamic networks. The basic idea behind the protocol is to divide the graph into a number of overlapping clusters. A change in the network topology corresponds to a change in cluster membership. We present algorithms for creation of clusters, as well as algorithms to maintain them in the presence of various network events. Compared to existing and conventional routing protocols, the proposed cluster-based approach incurs lower overhead during topology updates and also has quicker reconvergence. The effectiveness of this approach also lies in the fact that existing routing protocols can be directly applied to the network --- replacing the nodes by clusters.
Connection closures adding application-defined behaviour to network connections
Authors: Rooney S.
Published: October 2004

New techniques in the implementation of out-of-band control in ATM networks are causing both industry and research laboratories to look again at the whole question of ATM signalling. These techniques devolve the control from the network devices into a higher level distributed processing environment, resulting in simpler network devices and more flexible control architectures.This paper takes this idea one stage further and suggests that at least in some cases, the only place in which control can be exerted without inhibiting applications is within the applications themselves. We call the combination of an application defined control policy and a network connection a
connection closure
.
An efficient multicast protocol using de Bruijn structure for mobile computing
Authors: Wei David S. L. , Naik Kshirasagar
Published: October 2004

In this paper, we design a protocol to efficiently deliver multicast messages to mobile computers. The main concern in the design of such a protocol is to ensure that each message is delivered exactly once to each mobile host in a multicast group. However, the requirements of avoiding multiple delivery of a message, and of a host not missing a message are not easy to efficiently satisfy in a mobile environment. To satisfy these requirements, an earlier work had to actually broadcast a multicast message. The novelty of our approach is that we satisfy the multicast requirements without broadcasting a message, which is central to the efficiency of our protocol. We structure the mobile support stations (MSS) as a de Bruijn network, and define a multicast tree on the network. A multicast message is routed on a multicast tree on a de Bruijn network. Assuming that there are
N
MSS's in a network, a multicast group of mobile hosts belong to the cells of
N
MSS's, τ is the maximum of the time to route a message between two adjacent MSS's, Λ is the sum of the mobility rates of all mobiles in a multicast group, λ

max

is the maximum among the mobility rates, and φ is the
cell cross-over time
of a mobile, our protocol runs with a message complexity of
O
(
min
(
N
log
N, N
) + Λ log
N
) and a communication delay of
O
(τ log
N
+ λ

max

φ). Thus, our protocol is very efficient when a message is multicast to a small number of mobile hosts. To show the practicability of structuring a set of MSS's as a de Bruijn network, we have demonstrated how a de Bruijn network can be emulated as a collection of
virtual paths
on an arbitrarily connected ATM network.
Performance of centralized bandwidth reservation protocol in AVPNs
Authors: Verma Ashish , Venkataram Pallapa
Published: October 2004

ATM based Virtual Private Networks(AVPNs) are embedded in public ATM network to provide an efficient transport service to a multisite customer using virtual levels of ATM. In this paper we propose a centralized protocol for resource allocation in AVPNs and compare its performance with that of the previously proposed strategies. We analyze the protocol to get average burst delay and burst loss probability in case of finite buffering at the customer sites.
The macroscopic behavior of the TCP congestion avoidance algorithm
Authors: Mathis Matthew , Semke Jeffrey , Mahdavi Jamshid , Ott Teunis
Published: October 2004

In this paper, we analyze a performance model for the TCP Congestion Avoidance algorithm. The model predicts the bandwidth of a sustained TCP connection subjected to light to moderate packet losses, such as loss caused by network congestion. It assumes that TCP avoids retransmission timeouts and always has sufficient receiver window and sender data. The model predicts the Congestion Avoidance performance of nearly all TCP implementations under restricted conditions and of TCP with Selective Acknowledgements over a much wider range of Internet conditions.We verify the model through both simulation and live Internet measurements. The simulations test several TCP implementations under a range of loss conditions and in environments with both drop-tail and RED queuing. The model is also compared to live Internet measurements using the TReno diagnostic and real TCP implementations.We also present several applications of the model to problems of bandwidth allocation in the Internet. We use the model to analyze networks with multiple congested gateways; this analysis shows strong agreement with prior work in this area. Finally, we present several important implications about the behavior of the Internet in the presence of high load from diverse user communities.
Delivering the FRICE of IS management
Authors: Farr Phillip D. , Kappelman Leon
Published: October 2004

As Director of Management Information Services, Phillip D. Farr is responsible for the information technology (IT) function at American Petrofina, Inc. (FINA). His responsibilities include long-term planning, as well as day-to-day operations. FINA (AMEX: FI) is a Dallas-based company engaged in crude oil and natural gas exploration and production; petroleum products refining, marketing, and transportation; as well as the manufacturing and marketing of petrochemicals and plastics. Organized in 1956, FINA is part of an international group of companies affiliated with Petrofina S.A. head-quartered in Brussels, Belgium. In 1995 FINA had revenues over $3.6 billion, employed nearly 2700 people, and had over 2700 company-branded service stations.
AIS
Authors: Bjorn Andersen Niels
Published: October 2004

In an old song from the resistance movement in Denmark during the Second World War, one of the key lines is "for the old trees falling, there will be new trees growing up."
IFIP
Authors: Davis Gordon B.
Published: October 2004

This column discusses the IFIP World Computer Congress held every two years. The most recent IFIP World Congress was held in Canberra, Australia, in September of 1996. The Fifteenth IFIP World Congress will be in Vienna, Austria, and Budapest, Hungary, from August 31 to September 4, 1998. The World Congress in the year 2000 will be held in Beijing, China.
PRIISM
Authors: Bui Tung X.
Published: October 2004

Over the last two years, PRIISM, via its members, has participated in three major conferences and workshops whose effort was to focus on research and policy issues related to the information revolution in the Pacific Rim. This increased interest is no accident. It has been suggested that we will soon enter a "Pacific Century," in which the world's economic center of gravity, having shifted from Asia to Europe and then to North America, is now returning to Asia. But it is returning to a very diverse Asia, with many regional differences in language, culture, ideology, income levels and income distribution, and economic policies. Despite this diversity, most - if not all - of the leaders of Asian countries are firmly convinced that IT will help propel their country into the Information Age. Indeed, many nations in Asia Pacific have recently begun to design and implement their widely-publicized national information infrastructures (NIIs). In the previous edition of this column, NII was identified as one of the major information technology issues in the Pacific.
Audience engagement in multimedia presentations
Authors: Webster Jane , Ho Hayes
Published: October 2004

Engagement in training and educational presentations facilitates learning. This paper describes engagement and proposes that it is conceptually similar to the state of playfulness, a construct increasingly applied to studies of human-computer interactions. It then describes how multimedia technologies can influence listeners' engagement during presentations. Results from pilot and main studies suggest that students' engagement in multimedia presentations can be increased by developing presentations that provide more challenge, feedback, presenter control, and variety. The paper concludes by discussing implications for research and practice.
The role of work, play, and fun in microcomputer software training
Authors: Perry Elissa L. , Ballou Deborah J.
Published: October 2004

A field study of MBA students enrolled in a microcomputer software training class was conducted. Trainees' expectations of the extent to which the training would be like work and play were collected prior to the training and their perceptions of the extent to which the training was like work and play were collected after the training. In addition, trainees' perceptions of the extent to which the training was fun were also measured. Results indicated that play perceptions operated as a suppressor variable. Post-training play perceptions had a marginally significant and negative effect on learning and increased the positive and significant effect of post-training fun perceptions on learning. Results also indicated that despite the fact that much of the training occurred on the computer, trainers influenced trainees' perceptions that the training seemed like work, play, and fun. Finally, learning was negatively affected when trainees with high pre-training play expectations perceived trainers to have a high work orientation in the training. These results suggest that play and fun perceptions have potentially important consequences for learning and that trainers play an important role in influencing these perceptions in microcomputer training.
The Game of Life with Ada tasks
Authors: Levine Gertrude
Published: October 2004

The Game of Life is a popular programming project, both in computer science courses and on the World Wide Web. It is commonly implemented with a bounded array of values representing the cells of life. This project provides an appealing visual representation of cells living or dying over repeated generations.An Ada implementation using tasks allows a number of interesting features. State information can be retained between calls. A generic declaration defines a conceptually unbounded grid, which a distributed implementation with tasks can potentially implement. Tasking communication provides an exercise in both inter-cell communication and in deadlock prevention. Lastly, the independence of cell communication can allow for relaxing the synchronization of cell generations.
COCOON
Authors: Welch Lonnie R.
Published: October 2004

The software engineering techniques of reuse, encapsulation and information hiding are increasingly being employed in the construction of large, concurrent software systems. Simultaneously, hardware platforms continue to increase in sophistication, particularly in the area of concurrency. Thus, systems engineers are confronted with the problem of bridging the gap between (1) large computer-based software systems composed of tasks and ADTs/objects and (2) parallel and distributed computer platforms. Thus, this paper describes the COCOON (Creator Of Concurrent Object-OrieNted Systems) toolset. COCOON bridges the gap between object-oriented Ada software and distributed architectures. It partitions tasks, packages and subprograms, and assigns partitions to physical processors. The toolset automatically produces a distribution specification.
Software reusability issues in code and design
Authors: Kim Hyoseob , Boldyreff Cornelia
Published: October 2004

The phenomenal growth in the costs of producing software over the last three decades has forced the computing industry to look for alternative strategies to that implied by the waterfall model of computer system development. One frequently observed solution is flint of reusing existing software artifacts in the construction of new ones; this technique is known as
software reuse.
In this paper, software reusability issues are studied both at the code and design level.
A case study on design pattern discovery in Ada
Authors: Kim Hyoseob , Boldyreff Cornelia
Published: October 2004

Little assistance, if any, is given to personnel who design software. This has caused the production of software which is less evolvable and of low quality. A case study was carried out to investigate the implications of design patterns during software building. The results suggest that design patterns can facilitate our understanding of software systems and reusing software designs in our future software building.
Increasing throughput in ATM/B-ISDN using simple buffer management and selective discarding
Authors: Chatterjee Samir , Xiao Wen
Published: October 2004

If the reliability provided by the network is lower than that requested by the application, the error and flow control systems in the end-nodes must make up for the difference. While most applications use retransmission based schemes to recover lost data, ARQ based closed loop techniques may not be suitable for many new applications. Time sensitive information requiring no-loss of data would constitute a major segment of the emerging traffic (interactive web, videophones, CSCW) that typically employ Forward Error Correction (FEC) codes. Such codes send redundant information which help to recover lost data without retransmission. This paper shows that just plain FEC is not enough when one considers the fragmentation effects that takes place when legacy networks interwork with ATM. Simple yet powerful buffer management techniques can yield higher throughput thereby reducing block loss rates. A combination of a gatekeeping operation along with janitor routine that cleans up the buffer to preserve frames on an end-to-end basis is proposed. A simulation study demonstrates positive results. The proposed schemes even point towards efficient sizing of ATM switch buffers which guarantee no-loss transport of real-time information.
A fault-tolerant dynamic triangular mesh protocol for distributed mutual exclusion
Authors: Chang Ye-In , Chang Yao-Jen
Published: October 2004

In the paper, we propose a
dynamic triangular mesh protocol
for mutual exclusion, in which the nodes in the system are organized into a triangular mesh. A quorum contains three dynamic paths in the given triangular mesh and the quorum size is
k
that is
O
(√
N
), where
N
is the number of nodes in the system and is equal to
k
(
k
+1)/2. The protocol is fault-tolerant up to (
k
- 1) site failures and communication failures in the worst case, even when such failures lead to network partitioning. From our simulation study, the proposed protocol can have higher availability and less quorum size than Cheung et al.'s grid protocol. Moreover, the quorum size of the proposed protocol will be less than that in Kumar's HQC protocol when N is greater than or equal to 15, and can be less than that in Agrawal et al.'s tree quorum protocol when node failures occur.
Visualizing UNIX synchronization operations
Authors: Vogt Carsten
Published: October 2004

The synchronization of concurrent tasks is a fundamental topic in computer science education. Graphical tools that visualize the effects of synchronization operations are helpful to understand their effects and pitfalls.
PACO
and
ANDI
are one such tool. C programs using UNIX system calls for process and semaphore management are instrumented by PACO with specific output functions. When executing these programs, ANDI visualizes the effects of the system calls by a dynamic graphical output.
Review of Reasoning About Knowledge by Ronald Fagin, Joseph Halpern, Yoram Moses and Moshe Vardi
Authors: Dekhtyar Alexander
Published: October 2004

How much do you know ? How much do you know about what you know ? How much do you know about what someone else knows ? How much that someone else knows about what you know about what she knows, and how much do you know about that ?We started with a very simple question about knowledge, and almost immediately the chain of questions lead to complicated and hard to comprehend ones. Classic logic teaches us how one can reason about truth and falsehood of statements, but can it help us if we want to reason about our (or someone else's) knowledge ? And if the answer to the last question is "yes", then how can we achieve this goal ?These are just a few of the questions, that served as motivation for the book
Reasoning About Knowledge.
In the book authors discuss the extentions of classical logic that encapsulate the desired meaning of the statements such as "I know
X
", "I know that Alice knows
X
" and "Everyone knows that I know
X
".In the first chapters the book provides a number of motivating examples which lead the reader to an informal understanding of the authors' concept of knowledge. After that the notion of knowledge is being formalized by introduction of modal operators for knowledge, common knowledge and distributed knowledge into the classic Propositional logic. Kripke structures are introduced as models at the same time and the obtained modal logics are then studied closely with respect to their soundeness and completeness properties, as well as the complexity of decision procedures.Once the general background is layed out, authors start discussing a variety of applications of knowledge-based reasoning to other problems in such fields as AI and Communications. A number of chapters of the book are devoted to discussing multi-agent systems and their behavior. A concept of Common Knowledge and its relation to Agreement and Cooperation between agents is also discussed.The more detailed summary of the book is provided below.
On the properties of cryptographic protocols and the weaknesses of the BAN-like logics
Authors: Xu Shouhuai , Zhang Gendu , Zhu Hong
Published: October 2004

The researches on the cryptographic protocols, especially on the formal analysis methods, have been paid much attention to in the last two decades. However, the formal methods already presented can not perfectly prove a protocol really secure. In this paper, we unfold the properties that cryptographic protocols should possess and then prove, with respect to which, that the BAN-like logic tools have only limited capacity for proving a protocol really secure.
A model for a distributed OS automatic generation system
Authors: He Yanxiang , Cooley Donald H. , Zhang Jianping
Published: October 2004

While much work has been done in distributed operating system development, problems exist and much work is still to be done. To address some of the issues and problems associated with distributed operating systems the authors present a Model for a Distributed OS Automatic Generating System (DOSAGS), which is characterized by intelligence, integration and plasticity. The system structure, functions, work principles and key issues in the implementation of DOSAGS are presented in this paper. The authors believe that the distributed OS generated by DOSAGS represents a new generation of distributed Operating systems.
Tasking profiles (session summary)
Authors: Burns Alan , Baker Ted , Vardenaga Tullio
Published: October 2004

The objective of this session was to identify one or more restricted tasking profiles that would satisfy the certification requirements of high-integrity (safety-critical) real-time systems. Such a profile would also be likely to offer improved performance. Consideration was not given to the sequential parts of the language as they are being addressed by the HRG (annex H Rapporteur Group).
Outstanding language (session summary)
Authors: Pazy Offer , Kamrad Mike
Published: October 2004

To discuss any outstanding issues that the real-time community needs to recognize.
Object-oriented programming and real-time (session summary)
Authors: Wellings Andy , de la Puente Juan
Published: October 2004

The aim of the session is to discuss appropriate paradigms for using OOP in Real-Time Systems.
Components for the implementation of fixed priority real-time systems in ADA
Authors: Alonso Alejandro , de la Puente Juan Antonio , Tindell Ken
Published: October 2004

In recent years fixed-priority scheduling has received a lot of attention. Indeed, it could be said that it has become a mature approach to engineering real-time systems. The Ada language includes the necessary mechanisms for implementing this kind of systems.This paper reports the work done in order to implement in Ada a set of basic components for building fixed-priority real-time systems. These components provide support for periodic and sporadic tasks, fault detection and recovery, intertask communication and mode change. With respect to mode change, an improved implementation approach has been developed, based on a simple protocol.
Feature interactions with dynamic priorities
Authors: Burns A. , Wellings A. J.
Published: October 2004

A number of flexible scheduling schemes can be programmed in Ada 95 by combining the more advanced features the language provides. For example, imprecise computations would appear to be accommodated by the use of ATCs (with timing triggers) and dynamic priorities. Unfortunately with this type of scheme, it is difficult to ensure that the priority of the task, following the triggering event, is at the appropriate level. This problem is investigated and potential solutions are presented and assessed.
Future directions in Ada—distributed execution and heterogeneous language interoperability toolsets
Authors: Gargaro Anthony , Smith Gary , Theriault Ronald J. , Volz Richard A. , Waldrop Raymond
Published: October 2004

While the Ada community has seen and embraced the development of Ada 95 [1], with its enhanced object oriented features and various annexes, much of the rest of the commercial world continues to ignore Ada as a viable tool for software system building. Efforts have been ongoing for some time to provide rationale showing the superiority of Ada 95 over other choices such as C and C++, but with limited success in the commercial marketplace. In this paper, we put forward the idea that the Ada community should focus on: 1) interoperability with components built in other languages, and 2) convenient, easy to use toolsets for composing distributed systems from heterogeneous language components.
Using analytical approaches for high integrity Ada95 systems
Authors: Michell Stephen , Craigen Dan , Saaltink Mark
Published: October 2004

The paper reports on a recently completed analysis of the suitability of Ada95 for use in high integrity systems, describes the status of real-time features in this analysis, and identifies how the analysis could be extended to admit more features needed for real-time programs.
Reimplementing a multiprocess distributed paradigm for real-time systems in Ada 95
Authors: Vestal Steve , Guerby Laurent , Dewar Robert , McConnell David , Lewis Bruce
Published: October 2004

A specification/generation software tool for building hard real-time distributed systems was redeveloped to generate Ada 95 rather that Ada 83 and targeted to the GNAT Ada 95 compiler under Sun Solaris. The resulting simulator was tested with missile flight simulation code. Language issues discovered and paradigms used are discussed with recommendations in the paper. Performance data is provided.
Task termination and Ada 95
Authors: Wellings A. J. , Burns A. , Pazy O.
Published: October 2004

Ada 83 removed from the programmer the burden of coding potentially complex termination conditions between clients and servers by introducing an 'or terminate' option to the select statement. With the introduction of indirect communication (emphasised by the provision of protected objects in Ada 95), it is no longer straightforward to obtain program termination. This paper illustrates the problem and suggests that adding a terminate alternative to an entry call might solve the problem. The advantages and disadvantages of the approach are discussed.
Fault tolerance in distributed Ada 95
Authors: Wolf Thomas
Published: October 2004

In this paper we present a project to provide fault tolerance in distributed Ada 95 applications by means of replication of partitions. Replication is intended to be largely transparent to an application. A group communication system is used for replica management. We examine some of the possibilities for implementing such a system and highlight some of the difficulties encountered in the context of the programming language Ada 95.
Implications of data quality for spreadsheet analysis
Authors: Ballou Donald P. , Pazer Harold L. , Belardo Salvatore , Klein Barbara
Published: October 2004

This paper examines the impact of deficiencies in data quality on the results generated for spreadsheet applications. The purpose is to describe a framework which can be systematically used to determine the relative importance of potential errors in operational and judgmental data. Special emphasis is placed on analyzing the implications of deficiencies in data quality on projected spreadsheet results.