bluuebunny/crossref_metadata_2025 huggingface dataset:
Improving the start-up behavior of a congestion control scheme for TCP
Authors: Hoe Janey C.
Published: October 2004

Based on experiments conducted in a network simulator and over real networks, this paper proposes changes to the congestion control scheme in current TCP implementations to improve its behavior during the start-up period of a TCP connection.The scheme, which includes Slow-start, Fast Retransmit, and Fast Recovery algorithms, uses acknowledgments from a receiver to dynamically calculate reasonable operating values for a sender's TCP parameters governing when and how much a sender can pump into the network. During the start-up period, because a TCP sender starts with default parameters, it often ends up sending too many packets and too fast, leading to multiple losses of packets from the same window. This paper shows that recovery from losses during this start-up period is often unnecessarily time-consuming.In particular, using the current Fast Retransmit algorithm, when multiple packets in the same window are lost, only one of the packet losses may be recovered by each Fast Retransmit; the rest are often recovered by Slow-start after a usually lengthy retransmission timeout. Thus, this paper proposes changes to the Fast Retransmit algorithm so that it can quickly recover from multiple packet losses without waiting unnecessarily for the timeout. These changes, tested in the simulator and on the real networks, show significant performance improvements, especially for short TCP transfers. The paper also proposes other changes to help minimize the number of packets lost during the start-up period.
Measuring the performance of communication middleware on high-speed networks
Authors: Gokhale Aniruddha , Schmidt Douglas C.
Published: October 2004

Conventional implementations of communication middleware (such as CORBA and traditional RPC toolkits) incur considerable over-head when used for performance-sensitive applications over high-speed networks. As gigabit networks become pervasive, inefficient middleware will force programmers to use lower-level mechanisms to achieve the necessary transfer rates. This is a serious problem for mission/life-critical applications (such as satellite surveillance and medical imaging).This paper compares the performance of several widely used communication middleware mechanisms on a high-speed ATM network. The middleware ranged from lower-level mechanisms (such as socket-based C interfaces and C++ wrappers for sockets) to higher-level mechanisms (such as RPC, hand-optimized RPC and two implementations of CORBA - Orbix and ORBeline). These measurements reveal that the lower-level C and C++ implementations outperform the CORBA implementations significantly (the best CORBA throughput for remote transfer was roughly 75 to 80 percent of the best C/C++ throughput for sending scalar data types and only around 33 percent for sending structs containing binary fields), and the hand-optimized RPC code performs slightly better than the CORBA implementations. Our goal in precisely pinpointing the sources of overhead for communication middleware is to develop scalable and flexible CORBA implementations that can deliver gigabit data rates to applications.
Internet mobility 4×4
Authors: Cheshire Stuart , Baker Mary
Published: October 2004

Mobile IP protocols allow mobile hosts to send and receive packets addressed with their home network IP address, regardless of the IP address of their current point of attachment in the Internet.While some recent work in Mobile IP focuses on a couple of specific routing optimizations for sending packets to and from mobile hosts [Joh96] [Mon96], we show that a variety of different optimizations are appropriate in different circumstances. The best choice, which may vary on a connection-by-connection or even a packet-by-packet basis, depends on three factors: the characteristics the protocol should optimize, the permissiveness of the networks over which the packets travel and the level of mobile-awareness of the hosts with which the mobile host corresponds.Of the sixteen possible routing choices that we identify, we describe the seven that are most useful and discuss their benefits and limitations. These optimizations range from the most costly, which provides completely transparent mobility in all networks, to the most economical, which does not attempt to conceal location information. In particular, hosts should retain the option to communicate conventionally without using Mobile IP whenever appropriate.Further, we show that all optimizations can be described using a 4×4 grid of packet characteristics. This makes it easier for a mobile host, through a series of tests, to determine which of the currently available optimizations is the best to use for any given correspondent host.
Synchronization and communication in the T3E multiprocessor
Authors: Scott Steven L.
Published: October 2004

This paper describes the synchronization and communication primitives of the Cray T3E multiprocessor, a shared memory system scalable to 2048 processors. We discuss what we have learned from the T3D project (the predecessor to the T3E) and the rationale behind changes made for the T3E. We include performance measurements for various aspects of communication and synchronization.The T3E augments the memory interface of the DEC 21164 microprocessor with a large set of explicitly-managed, external registers (E-registers). E-registers are used as the source or target for all remote communication. They provide a highly pipelined interface to global memory that allows dozens of requests per processor to be outstanding. Through E-registers, the T3E provides a rich set of atomic memory operations and a flexible, user-level messaging facility. The T3E also provides a set of virtual hardware barrier/eureka networks that can be arbitrarily embedded into the 3D torus interconnect.
Evaluation of architectural support for global address-based communication in large-scale parallel machines
Authors: Krishnamurthy Arvind , Schauser Klaus E. , Scheiman Chris J. , Wang Randolph Y. , Culler David E. , Yelick Katherine
Published: October 2004

Large-scale parallel machines are incorporating increasingly sophisticated architectural support for user-level messaging and global memory access. We provide a systematic evaluation of a broad spectrum of current design alternatives based on our implementations of a global address language on the Thinking Machines CM-5, Intel Paragon, Meiko CS-2, Cray T3D, and Berkeley NOW. This evaluation includes a range of compilation strategies that make varying use of the network processor; each is optimized for the target architecture and the particular strategy. We analyze a family of interacting issues that determine the performance trade-offs in each implementation, quantify the resulting latency, overhead, and bandwidth of the global access operations, and demonstrate the effects on application performance.
A quantitative analysis of loop nest locality
Authors: McKinley Kathryn S. , Temam Olivier
Published: October 2004

This paper analyzes and quantifies the locality characteristics of numerical loop nests in order to suggest future directions for architecture and software cache optimizations. Since most programs spend the majority of their time in nests, the vast majority of cache optimization techniques target loop nests. In contrast, the locality characteristics that drive these optimizations are usually collected across the entire application rather than the nest level. Indeed, researchers have studied numerical codes for so long that a number of commonly held assertions have emerged on their locality characteristics. In light of these assertions, we use the Perfect Benchmarks to take a new look at measuring locality on numerical codes based on references, loop nests, and program locality properties. Our results show that several popular assertions are at best overstatements. For example, we find that temporal and spatial reuse have balanced roles within a loop nest and most reuse across nests and the entire program is temporal. These results are consistent with high hit rates, but go against the commonly held assumption that spatial reuse dominates. Another result contrary to popular assumption is that misses within a nest are overwhelmingly conflict misses rather than capacity misses. Capacity misses are a significant source of misses for the entire program, but mostly correspond to potential reuse between different loop nests. Our locality measurements reveal important differences between loop nests and programs; refute some popular assertions; and provide new insights for the compiler writer and the architect.
Analysis of branch prediction via data compression
Authors: Chen I-Cheng K. , Coffey John T. , Mudge Trevor N.
Published: October 2004

Branch prediction is an important mechanism in modern microprocessor design. The focus of research in this area has been on designing new branch prediction schemes. In contrast, very few studies address the theoretical basis behind these prediction schemes. Knowing this theoretical basis helps us to evaluate how good a prediction scheme is and how much we can expect to improve its accuracy.In this paper, we apply techniques from data compression to establish a theoretical basis for branch prediction, and to illustrate alternatives for further improvement. To establish a theoretical basis, we first introduce a conceptual model to characterize each component in a branch prediction process. Then we show that current "two-level" or correlation based predictors are, in fact, simplifications of an optimal predictor in data compression, Prediction by Partial Matching (PPM).If the information provided to the predictor remains the same, it is unlikely that significant improvements can be expected (asymptotically) from two-level predictors, since PPM is optimal. However, there are a rich set of predictors available from data compression, several of which can still yield some improvement in cases where resources are limited. To illustrate this, we conduct trace-driven simulation running the Instruction Benchmark Suite and the SPEC CINT95 benchmarks. The results show that PPM can outperform a two-level predictor for modest sized branch target buffers.
Value locality and load value prediction
Authors: Lipasti Mikko H. , Wilkerson Christopher B. , Shen John Paul
Published: October 2004

Since the introduction of virtual memory demand-paging and cache memories, computer systems have been exploiting spatial and temporal locality to reduce the average latency of a memory reference. In this paper, we introduce the notion of
value locality,
a third facet of locality that is frequently present in real-world programs, and describe how to effectively capture and exploit it in order to perform
load value prediction.
Temporal and spatial locality are attributes of storage locations, and describe the future likelihood of references to those locations or their close neighbors. In a similar vein,
value locality
describes the likelihood of the recurrence of a previously-seen value within a storage location. Modern processors already exploit
value locality
in a very restricted sense through the use of control speculation (i.e. branch prediction), which seeks to predict the future value of a single condition bit based on previously-seen values. Our work extends this to predict entire 32- and 64-bit register values based on previously-seen values. We find that, just as condition bits are fairly predictable on a per-static-branch basis, full register values being loaded from memory are frequently predictable as well. Furthermore, we show that simple microarchitectural enhancements to two modern microprocessor implementations (based on the PowerPC 620 and Alpha 21164) that enable
load value prediction
can effectively exploit
value locality
to collapse true dependencies, reduce average memory latency and bandwidth requirements, and provide measurable performance gains.
Shasta
Authors: Scales Daniel J. , Gharachorloo Kourosh , Thekkath Chandramohan A.
Published: October 2004

This paper describes Shasta, a system that supports a shared address space in software on clusters of computers with physically distributed memory. A unique aspect of Shasta compared to most other software distributed shared memory systems is that shared data can be kept coherent at a fine granularity. In addition, the system allows the coherence granularity to vary across different shared data structures in a single application. Shasta implements the shared address space by transparently rewriting the application executable to intercept loads and stores. For each shared load or store, the inserted code checks to see if the data is available locally and communicates with other processors if necessary. The system uses numerous techniques to reduce the run-time overhead of these checks. Since Shasta is implemented entirely in software, it also provides tremendous flexibility in supporting different types of cache coherence protocols. We have implemented an efficient cache coherence protocol that incorporates a number of optimizations, including support for multiple communication granularities and use of relaxed memory models. This system is fully functional and runs on a cluster of Alpha workstations.The primary focus of this paper is to describe the techniques used in Shasta to reduce the checking overhead for supporting fine granularity sharing in software. These techniques include careful layout of the shared address space, scheduling the checking code for efficient execution on modern processors, using a simple method that checks loads using only the value loaded, reducing the extra cache misses caused by the checking code, and combining the checks for multiple loads and stores. To characterize the effect of these techniques, we present detailed performance results for the SPLASH-2 applications running on an Alpha processor. Without our optimizations, the checking overheads are excessively high, exceeding 100% for several applications. However, our techniques are effective in reducing these overheads to a range of 5% to 35% for almost all of the applications. We also describe our coherence protocol and present some preliminary results on the parallel performance of several applications running on our workstation cluster. Our experience so far indicates that once the cost of checking memory accesses is reduced using our techniques, the Shasta approach is an attractive software solution for supporting a shared address space with fine-grain access to data.
An integrated compile-time/run-time software distributed shared memory system
Authors: Dwarkadas Sandhya , Cox Alan L. , Zwaenepoel Willy
Published: October 2004

On a distributed memory machine, hand-coded message passing leads to the most efficient execution, but it is difficult to use. Parallelizing compilers can approach the performance of hand-coded message passing by translating data-parallel programs into message passing programs, but efficient execution is limited to those programs for which precise analysis can be carried out. Shared memory is easier to program than message passing and its domain is not constrained by the limitations of parallelizing compilers, but it lags in performance. Our goal is to close that performance gap while retaining the benefits of shared memory. In other words, our goal is (1) to make shared memory as efficient as message passing, whether hand-coded or compiler-generated, (2) to retain its ease of programming, and (3) to retain the broader class of applications it supports.To this end we have designed and implemented an integrated compile-time and run-time software DSM system. The programming model remains identical to the original pure run-time DSM system. No user intervention is required to obtain the benefits of our system. The compiler computes data access patterns for the individual processors. It then performs a source-to-source transformation, inserting in the program calls to inform the run-time system of the computed data access patterns. The run-time system uses this information to aggregate communication, to aggregate data and synchronization into a single message, to eliminate consistency overhead, and to replace global synchronization with point-to-point synchronization wherever possible.We extended the Parascope programming environment to perform the required analysis, and we augmented the TreadMarks run-time DSM library to take advantage of the analysis. We used six Fortran programs to assess the performance benefits: Jacobi, 3D-FFT, Integer Sort, Shallow, Gauss, and Modified Gramm-Schmidt, each with two different data set sizes. The experiments were run on an 8-node IBM SP/2 using user-space communication. Compiler optimization in conjunction with the augmented run-time system achieves substantial execution time improvements in comparison to the base TreadMarks, ranging from 4% to 59% on 8 processors. Relative to message passing implementations of the same applications, the compile-time run-time system is 0-29% slower than message passing, while the base run-time system is 5-212% slower. For the five programs that XHPF could parallelize (all except IS), the execution times achieved by the compiler optimized shared memory programs are within 9% of XHPF.
Hiding communication latency and coherence overhead in software DSMs
Authors: Bianchini R. , Kontothanassis L. I. , Pinto R. , De Maria M. , Abud M. , Amorim C. L.
Published: October 2004

In this paper we propose the use of a PCI-based programmable
protocol controller
for hiding communication and coherence overheads in software DSMs. Our protocol controller provides three different types of overhead tolerance: a) moving basic communication and coherence tasks away from computation processors; b) prefetching of diffs; and c) generating and applying diffs with hardware assistance. We evaluate the isolated and combined impact of these features on the performance of TreadMarks. We also compare performance against two versions of the Shrimp-based AURC protocol. Using detailed execution-driven simulations of a 16-node network of workstations, we show that the greatest performance benefits provided by our protocol controller come from our hardware-supported diffs. Reducing the burden of communication and coherence transactions on the computation processor is also beneficial but to a smaller extent. Prefetching is not always profitable. Our results show that our protocol controller can improve running time performance by up to 50% for TreadMarks, which means that it can double the TreadMarks speedups. The overlapping implementation of TreadMarks performs as well or better than AURC for 5 of our 6 applications. We conclude that the simple hardware support we propose allows for the implementation of high-performance software DSMs at low cost. Based on this conclusion, we are building the NCP
2
parallel system at COPPE/UFRJ.
Parallel computing in Ada
Authors: Paprzycki Marcin , Zalewski Janusz
Published: October 2004

The aim of this paper is to present the basic issues related to the use of Ada in parallel computing. It is argued that there exists a gap between the most popular area of parallel computing research, scientific computing, and the interests of Ada community. A number of new research directions and curricular changes are proposed.
OOP vs. readability
Authors: Carter Jeffrey R.
Published: October 2004

A previous paper discussed the relationship between the object-oriented-programming (OOP) feature known in Ada 95 as dispatching and Ada's expressed design goal of emphasizing ease of reading and understanding over ease of writing [1]. A comparison of Barnes' alert-system example [2] using Ada-95 dispatching and using Ada-83 composition showed that dispatching emphasized ease of writing over ease of reading, while composition emphasized ease of reading over ease of writing. This led to the conclusion that the goals of dispatching conflict with Ada's expressed design goals.Dispatching is half of OOP; the other half is inheritance, correctly called type extension in Ada 95. This paper examines the relationship between inheritance and Ada's expressed design goal of emphasizing ease of reading and understanding over ease of writing.Object-oriented design (OOD), as introduced by Booch [3], emphasizes the software-engineering principles of locality, encapsulation, and information hiding. Ada 83 supports such OOD well; using OOD and Ada results in easy-to-read programs that exhibit low coupling and high cohesion. OOD is independent of OOP: Fully object-oriented designs may be implemented using composition methods familiar to Ada-83 users without any need for OOP features (inheritance and dispatching). OOP features may likewise be used without OOD.
TASH
Authors: Westley Terry J.
Published: October 2004

A binding to Tcl from Ada is described. The goal of this binding is to make scripting language features, such as associative arrays, regular expression matching, and execution of OS commands available to an Ada programmer and to allow a Tcl programmer to use Ada in place of C where needed. This binding exploits several new features of Ada 95 that make interfacing to C much cleaner and more direct than Ada 83.
Cyclic redundancy checks in Ada95
Authors: Duerinckx Guido
Published: October 2004

Among the many error detection techniques used in (tele)communications, the Cyclic Redundancy Check (CRC) is probably the most powerful one. Roughly speaking the CRC is merely a modulo-2 division of the data (bits) to be transmitted by some 'magical' polynomial known for its high error detection capabilities. CRCs permit ensure that data transmitted over noisy media arrive intact.A common use of CRCs among industrial partners in large software development to projects is to identify quickly shared files. This is the case in the aerospace industry for instance, at least in Europe. CRCs can be computed for any sort of file, be it a document file processed by a COTS word processor, an image file, source code, a data file an executable file. The chances that two different files produce the same CRC checksum are astronomically small. It is our experience it never happened since our involvement in the ARIANE 5 program, the new European launcher, six years ago.A major issue however is due to the many variations among CRCs algorithms. For instance, most UNIX platforms provide a CRC checksum command, but few of them compute the same CRC checksum for a given file (obviously, the file format being identical). This issue has been addressed by the X/Open standardisation committee in charge of the UNIX specification. The so-called X/Open Single UNIX Specification [1], nicknamed UNIX95, contains a precise description of a CRC algorithm, which fully complies with the POSIX one [2]. As UNIX vendors are actually upgrading their product to become UNIX95 branded, one may expect these variations will disappear in the near future, in the UNIX world at least.In this paper we present an implementation of the POSIX/UNIX95 CRC algorithm in Ada95. Our purpose is three-fold. Firstly we want to provide standard source code that can be recompiled on any platform, UNIX-like or not, and be reused by other projects. Secondly we want the implementation to be scalable, typically from a 16-bit CRC ckecksum up to (at least) a 64-bit CRC ckecksum, as 64 bit CPUs become available on the market. The scalability goal is achieved by designing a generic implementation, the POSIX/UNIX95 CRC being a specific 32-bit of instantiation of it. The implementation is based on previous well designed and optimized work done in C [3], the purpose here is not to reinvent the wheel but to make it generic and scalable. Thirdly, the implementation illustrates some of the of new features of the Ada95 language: shifting and rotating procedures, modular types, aliased accesses, generic formal package, child packages and exception information, to name a few.
An object-oriented approach to automated generation of challenge examinations using Ada 95
Authors: Littlefield Arthur Irving
Published: October 2004

The primary objective of this paper is to analyze and evaluate the usefulness of object-oriented development and the Ada 95 programming language as applied to a specific software development project. A secondary objective is to show that structured development is still useful while applying object-oriented development and that the two methods can be integrated. The project is to develop an automated tool for generation of challenge examinations to test the knowledge of students in a given subject. The concepts of object-oriented and structured development are discussed and compared as they pertain to this problem domain. The methods are then applied and evaluated as the project is taken from analysis of the problem, through requirements specification, design, and implementation. During the requirements analysis and design phases, comparisons are made between object composition and functional decomposition, and rationale is discussed for the best places to use each. During the implementation phase, object-oriented features of the Ada 95 programming language are used as well as traditional structured programming techniques. Conclusions are summarized regarding the usefulness of the object-oriented paradigm and Ada 95 for this project, and the benefits of incorporating traditional structured development where it fits best.
Security functions for a file repository
Authors: Helme Arne , Stabell-Kulø Tage
Published: October 2004

When personal machines are incorporated into distributed systems a new mixture of threats is exposed. The security effort in the MobyDick project is aimed at understanding how privacy can be protected in this new environment. Our claim is that a two-step process for authentication and authorisation is required, but also sufficient. The research vehicle is a distributed file repository.
Security and log structured file systems
Authors: Stabell-Kulø Tage
Published: October 2004

A log structured file system (LFS) obtains its performance by refraining from seeking for blocks on the disk. Instead, new data is written into new blocks which is placed at the end of the log. This incurs a security issue by leaving data on disk that was supposed to be overwritten.To us, this shows how difficult it is for users concerned with their privacy, not to be lead astray. It also emphasizes how wide the gap is between an encryption channel and a user.
Design and implementation of a parallel pipe
Authors: Karges Jonathan , Ritter Otto , Suhai Sándor
Published: October 2004

The parallel pipe PAR_PIPE is a communication mechanism. Data which are written to the PAR_PIPE by a single process can be read by multiple processes concurrently in first-in-first-out manner, where all reading processes read the entire data stream. We use a dynamic partitioned buffer limited in size only by available hardware resources to ensure that the writing process cannot be blocked because of slow reading processes. In a further step we examine how far caching with an optimized saving policy on top of the file based buffer can improve the performance of the PAR_PIPE. Design and implementation of two versions of the PAR_PIPE (one without caching, one with caching) are described. We outline the general advantages of the PAR_PIPE over conventional UNIX shell script solutions and evaluate the results of performance measurements done for both PAR_PIPE versions.
Computational Geometry Column 30
Authors: O'Rourke Joseph
Published: October 2004

Several results from Combinatorial Geometry [PA95] are detailed.
Applying deductive database technology to network management
Authors: Sharda Nalin , Fatri Refyul , Abid Mohammad
Published: October 2004

Network Management is essential for successful operation of any communications network. Due to the complexity of modern networks, their management requires application of artificial intelligence based techniques. Two essential aspects of any Network Management system are, a large volume of data, and rules applied to this data. Deductive database systems cater for both. In this paper we examine the suitability of deductive database systems for Network Management application. Fundamentals of Network Management as well as deductive database systems are given. We describe a prototype Network Management system built to test the suitability of deductive database systems for Network Management.
Forecasting the next 50 years in information technology
Authors: Grover Varun
Published: October 2004

Predicting the information technology future? Nah! The great ones couldn't do it. How can we? Thomas Watson, the IBM chairman, said about 50 years ago that "there is a world market for maybe five computers." Ken Olson, founder of DEC couldn't find any "reason anyone would want a computer in their home" in 1977. And even Bill Gates thought in 1981, "640K ought to be enough for anybody." They were all dead wrong!
PRIISM
Authors: Bui Tung X.
Published: October 2004

PRIISM salutes this special DATABASE issue on "Forecasting the Next 50 Years in Information". This forward-looking initiative parallels PRIISM's effort to understand the evolution of information technology in the Pacific Rim.
An Ada-LISP interface generator
Authors: Das Souripriya , Schach Stephen R.
Published: October 2004

It has been recognized that neither of the two major programming approaches, procedural and non-procedural, can be optimal for every application. The availability of both paradigms in the same environment enables the programmer to choose the appropriate paradigm for each subtask, thereby leading to more efficient programs. In this paper we describe a system that has been developed for interfacing Franz LISP, a language particularly suitable for the non-procedural style of programming, and Ada, a powerful procedural language. This system enables the user to call Ada subprograms from within the Franz LISP environment. The system incorporates a generator which takes as input certain information about the Ada subprogram and then dynamically generates an Ada main unit which is utilized for interfacing. The system allows the user to take advantage of the power of the Ada programming language from within the Franz LISP environment.
Note on a problem with Reed and Long's FBR results
Authors: Robinson John T. , Devarakonda Murthy V.
Published: October 2004

This short note discusses a problem we found in a recent article in
Operating Systems Review
[1]. The problem is related to apparent inconsistencies in results presented for a data cache algorithm, known as FBR (frequency based replacement), which we first described in [2]. A property of this algorithm is that cache miss ratios obtained using FBR can be related to LRU cache miss ratios for any given trace. Application of this property to the results in [1] reveals apparent inconsistencies. These inconsistencies could be the result of errors either in implementing the algorithm or in recording the results. This note also highlights this property of FBR, which should help contribute to its understanding.
AFS and the Web
Authors: Satyanarayanan M. , Spasojevic Mirjana
Published: October 2004

Over the last few years, the World-Wide Web [2] has risen to dominance as a mechanism for wide-area information access. Each day brings new reports of the growth of the Web, and this trend shows no signs of abating any time soon. To many people, the Web and the Internet are synonymous. Unfortunately, success has exposed many limitations of the Web such as its tendency to overload the network and servers, its limited ability to control access to sensitive data, its lack of mechanisms for data consistency, and its susceptibility to network and server failures. It is now widely recognized that these problems must be solved for the continued growth of the Web.With much less fanfare, another world-wide information system, AFS, has also been operational on the Internet. AFS was originally designed to support the file sharing needs of a campus-sized community of five to seven thousand workstations [11, 15]. In current parlance, AFS was conceived as an information sharing mechanism for the
Intranet
of an organization. Since then, AFS has been evolved to function effectively over the Internet [17, 21]. Many organizations have been part of a single distributed Unix file name space supported by AFS. As of 1994, this system spanned well over 100 organizations world-wide, with each organization typically containing many tens or hundreds of clients. Measurements reported in a recent paper [20] confirm that AFS does indeed function effectively at this scale.The goal of this paper is to critically compare these two mechanisms for world-wide information access. We begin by asking the following questions:• What are the relative strengths and weaknesses of the two mechanisms?• Which of these differences are superficial, and which are deep?• Why is the Web so much more visible and popular?In performing this comparison, it is important to keep in mind that the two mechanisms are not addressing precisely the same problem. While AFS has the relatively narrow and well-defined goal of provided distributed Unix file access, the goal of the Web is broader and less explicit. Further, AFS is now stable and mature while many aspects of the Web are still evolving. In spite of these caveats, we believe that a comparison of the two mechanisms will provide useful insights.Our comparison shows that the Web and AFS are not really competing technologies. Rather, they represent complementary technologies that may be used together for mutual advantage. We present real-life examples to confirm that this potential can indeed be realized in practice.
A mobility-aware file system for partially connected operation
Authors: Dwyer Dane , Bharghavan Vaduvur
Published: October 2004

The advent of affordable off-the-shelf wide-area wireless networking solutions for portable computers will result in partial (or intermittent) connectivity becoming the common networking mode for mobile users. This paper presents the design of PFS, a mobility-aware file system specially designed for partially connected operation.PFS supports the extreme modes of full connection and disconnection gracefully, but unlike other mobile file systems, it also provides an interrace for mobility-aware applications to direct the file system in its caching and consistency decisions in order to fully exploit intermittent connectivity. Using PFS, it is possible for an application to maintain consistency on only the critical portions of its data files. Since PFS provides adaptation at the file system level, even unaware applications can 'act' mobile-aware as a result of the transparent adaptation provided by PFS.
Migration impact on load balancing—an experience on Amoeba
Authors: Zhu Weiping , Socko Piotr , Kiepuszewski Bartek
Published: October 2004

Load balancing has been extensive study by simulation, positive results were received in most of the researches. With the increase of the availability of distributed systems, a few experiments have been carried out on different systems. These experimental studies either depend on task initiation or task initiation plus task migration. In this paper, we present the results of an experimental study of load balancing using a centralized policy to manage the load on a set of processors. All experiments were carried out on an Amoeba system composed by a set of 386s and linked by 10Mbps Ethernet. The results on one hand indicate the necessity of a load balancing facility for a distributed system. On the other hand, the results question the impact of using process migration to increase system performance under the configuration used in our experiments.
Extending the Schematic Protection Model II
Authors: Varadharajan Vijay
Published: October 2004

The Schematic Protection Model, SPM, allows us to specify the protection structure of a system and gives an algorithm to reason about the transmission of privileges in the system. This paper extends the SPM model to address revocation of privileges.In [9], we had proposed an extension of the SPM to provide authentication. The two extensions are independent in the sense that each one affects a different part of the decision algorithm.
An evaluation of the real-time performances of SVR4.0 and SVR4.2
Authors: Zeadally Sherali
Published: October 2004

UNIX is one of the most widely used operating systems on current workstations. However, UNIX was originally designed as a multitasking and time-sharing system with little concern for supporting real-time applications. Recent versions of UNIX have incorporated real-time features and the designers of these systems claim to provide better response times than the standard UNIX kernel. In order to assess the benefits of these new features and verify these claims, this paper compares the real-time performances of two popular versions of UNIX namely System V Release 4.0 and System V Release 4.2 for the Intel platform.
A joint authorisation scheme
Authors: Low Marie Rose , Malcolm James A.
Published: October 2004

There are many situations where more than one principal needs to give authorisation so that a single function can take place. Self-Authenticating Proxies provide a mechanism which may be suitably employed to support the requirements of joint authorisation.
Ada, C, C++, and Java vs. the Steelman
Authors: Wheeler David A.
Published: October 2004

This paper compares four computer programming languages (Ada95, C, C++, and Java) with the requirements of "Steelman", the original 1978 requirements document for the Ada computer programming language. This paper provides a view of the capabilities of each of these languages, and should help those trying to understand their technical similarities, differences, and capabilities.
Computational geometry column 31
Authors: O'Rourke Joseph
Published: October 2004

Several topics related to packing on a sphere are discussed: packing points, packing lines through the center, and packing
k
-flats in dimension
d.
Recent results on the single-source shortest paths problem
Authors: Raman Rajeev
Published: October 2004

We summarize the currently best known theoretical results for the single-source shortest paths problem for directed graphs with non-negative edge weights. We also point out that a recent result due to Cherkassky, Goldberg and Silverstein (1996) leads to even better time bounds for this problem than claimed by the authors.
Ada and Java on the WWW
Authors: Munck Robert G. , Hilliard Richard F.
Published: October 2004

The Java language for World-Wide Web (WWW, "Web") programming, a "cleaned-up" variant of C++, is currently receiving great amounts of publicity. It compiles to an executable byte-code that is run interpretively, making it object-code portable to any platform having an interpreter. The primary use is to download logic embedded in Web pages, allowing them to have animated images, automatic playing of digitized audio and video, syntactic checking of forms entries, interactive games, and other actions.Intermetrics is in the final testing phase for an Ada 95 compiler called AppletMagic™ that targets the same executable byte-codes and run-time environment as Java. Given the superior features and greater maturity of Ada and the compiler-writing expertise of Intermetrics, this represents an extraordinary opportunity to expand the use of Ada to a much wider programming community. This paper summarizes the underlying technology, reviews the history and characteristics of Java, compares Java, C++, and Ada, and finally discusses efforts to promote the use of Ada for Web programming.
Experience programming applets with Ada95
Authors: Kann Charles W. , Feldman Michael B. , Sibert John
Published: October 2004

Because of its ability to provide platform independent programs and active content on web pages, Java has created much excitement in the computer science community. However, much of the computer science community does not have a good understanding of the Java technology. Java is much more than simply a language for developing programs which run on web pages. It is an environment for developing programs which take advantage of the Internet, and the use of the Java language is only one piece of that environment. That other languages can be used to write programs which can take advantage of the Java environment is shown by the existence of two such languages, NetRexx [1] from IBM and AppletMagic(tm) [2], an implementation of Ada95 for the Java VM, from Intermetrics.George Washington University obtained a Beta copy of the AppletMagic(tm) compiler in January of 1996. Since that time, we have been attempting to include AppletMagic and Java in a Data Structures (CS2) course and a course on Design of User Interface Software. During this time we have developed some experience in using Ada95 to develop Java programs and applets, and some insights into how students use the Java environment. This paper will report on those experiences.We will first present an overview of the Java environment. Intended to provide readers who are unfamiliar with Java enough background to be able to understand the relationship of AppletMagic(tm) and the Java environment. The third section will cover the structure of applets, and how to create an applet in Ada. The fourth section will cover issues concerning using classes written in Java from Ada, and some of the experiences we have had in using Ada to develop Java programs and applets, Finally the fifth section will present conclusions we have drawn from using AppletMagic(tm) in our courses.
WebAda
Authors: Smith D. Douglas
Published: October 2004

The Ada community has used the power of the Internet to distribute computer resources and information; and most recently the
World Wide Web
(WWW) makes it easier to find those resources. Now, a tool called WebAda uses the Internet and the WWW to provide an interactive capability! [For the rest of this paper, I will use the term Internet to include the World Wide Web.]WebAda is an Ada development environment accessed via the World Wide Web. You don't download the compiler or any other software! You enter programs, set switches, compile, and see results through your favorite browser. In other words, your browser is the Graphical User Interface (GUI) to WebAda.The
Lovelace
Tutorial took an initial step to become interactive, providing a multiple choice quiz at the end of most tutorial pages. WebAda has taken the next step with an on-line development environment which integrates Ada tools and information.One could say WebAda is to the Internet as C is to Unix, or as Basic is to DOS. When you have Internet access, you have all of the capabilities of WebAda available.
Writing an OLE automation controller in Ada95
Authors: Bremmon Chad
Published: October 2004

Microsoft OLE provides a powerful toolset to the Microsoft WindowsNT/95 developer. We have experienced the development of an OLE Automation Controller in Ada95 and would like to discuss the experience. This paper details the steps necessary to develop an OLE Automation Controller in Ada95.
Ada in concert
Authors: Beidler Jack
Published: October 2004

In a concert, it is truly marvelous how a diverse group of musicians playing an assortment of musical instruments come together to produce beautiful music. A point that is frequently made by those familiar with the new Ada standard, referred to here as Ada(95), is how the features in Ada(95) come together to enhance the software development process. This paper contains several examples that illustrate how the new features in Ada(95) dramatically improve the correlation between the design of a solution and its eventual implementation at the source code level when compared to Ada(83).The example, binary tree packaging, illustrates the design and implementation of recursive data structures. A data structure is recursive if the structure contains one or more substructures of the type being defined. As a result, recursive data structures lend themselves to processing with recursive algorithms. Lists, binary trees, and n-ary trees are examples of data structures that may be defined recursively. The example presented here is a package that implements binary trees using a recursive paradigm. The paper compares an Ada 83 solution with a solution using Ada 95. The paper focuses on how Ada 95 allows us to create a solution that more closely mirrors the specifications for the recursive data structure with improved time, space, and coding efficiency over an Ada 83 implementation. In a sense, this paper provides one illustration of how the '95 standard improves Ada.
A rendezvous with Linda
Authors: Lundqvist Kristina , Wall Göran
Published: October 2004

The Ada 9X revision found the rendezvous mechanism too complex to implement as the communication mechanism in a distributed system. In this paper another distributed programming model, Linda, is related to the rendezvous mechanism. Linda can be used to allow tasks to communicate in a rendezvous like manner. Sequences of Linda operations that roughly corresponds to different rendezvous operations are given and a small extension of Linda is presented in order to handle more of the rendezvous constructs. Linda can be used to communicate across partitions as well as within partitions.
Low-level Ada tasking support for GNAT-performance and portability improvements
Authors: Baker T. P. , Oh Dong-Ik , Moon Seung-Jin
Published: October 2004

GNARL is the tasking runtime system of the Gnu NYU Ada95 Translator (GNAT). GNARL is divided into two main layers, the lower of which isolates dependences on a particular host operating system or real-time kernel. For portability, the primary implementation of this lower level accesses OS services via the POSIX interfaces. In this paper we describe our recent redesign of the low-level interface, to improve both performance and portability. Performance comparisons between the new and old runtime system on Solaris2.4 show up to approximately 40 percent improvement on tasking related operations.
Computational geometry column 32
Authors: O'Rourke Joseph
Published: October 2004

The proof of Dey's new k-set bound is illustrated.
Infrastructure issues related to theory of computing research
Authors: Fich Faith
Published: October 2004

This paper discusses a number of issues related to the support of research in Theory of Computing, including funding, evaluation of research, communication, interaction with other research areas, education, and employment. It is directed primarily to researchers in Theory of Computing and is meant to complement the Infrastructure Section of the committee report "Strategic Directions for Research in Theory of Computing".Theory of Computing is a field of Computer Science that uses mathematical techniques to understand the nature of computation and to design and analyze algorithms for important and fundamental problems. It provides important new ways of thinking about computation and lasting insights that are applicable to a wide variety of systems.There are a range of different research activities that occur within this field, including developing models (and ways to quantify the efficiency of algorithms in those models), determining the relationships among different models, designing new (provably correct) algorithms, analyzing the efficiency of various algorithms, proving lower bounds and impossibility, and explaining experimental results. Some researchers are better at posing interesting questions or opening up new directions for research; others are better at answering questions and developing new techniques to do so.In this paper, I wish to discuss a number of issues related to the support of research in Theory of Computing, including funding, evaluation of research, communication, interaction with other research areas, education, and employment. It is directed primarily to researchers in Theory of Computing and is meant to complement the Infrastructure Section of the committee report "Strategic Directions for Research in Theory of Computing", which is directed primarily to people outside our community. I will examine some things our community has done well, some recent innovations, and some suggestions to enhance our research environment. Finally, I will address the relationship of Theory of Computing with experimental computing and algorithmic engineering.