bluuebunny/crossref_metadata_2025 huggingface dataset:
An introductory course in computer communication and networks
Authors: Narten Thomas , Yavatkar Raj
Published: October 2004

This paper reports on the curriculum contents and experience obtained in the teaching of a semester-long introductory course in computer communication networks. The course is aimed at first year graduate and senior undergraduate students and covers a broad survey of networking issues. We focus on all seven layers of the OSI reference model and assign four major programming projects to reinforce the ideas covered in lectures. Projects include writing the client side of a client-server program that implements a sliding window data-link layer protocol complete with acknowledgements and retransmissions, writing client and server programs that interact via remote procedure calls, and writing client and server programs that use UDP datgrams to locate and register services with a name server utility and TCP to actually invoke services registered with the name server.
The Department of Defense communications in the 21st century
Authors: Paoletti L. M.
Published: October 2004

The Department of Defense (DoD) is one of the biggest users of communications in the world. Communications systems are used not only for the administration of the Department, but, most critically, for the command and control of force structures. To this end, the Defense Communications Agency (DCA) strives to ensure that the Department's missions are carried out with state-of-the-art communications systems. In this article an architecture is postulated to achieve the Department's objective of rapid, reliable, secure exchange of information at an affordable price. The goal is one system for all communications services (data, voice, video, imagery) including Office Automation (OA) needs.This article was written with the view toward communications systems which are commonly referred to as fixed systems used on military bases and for long-haul transport of information, rather than tactical communications systems used on mobile platforms such as armored vehicles, ships, and airplanes. However, due to advances in VLSI and flexibilities afforded by new transmission frameworks and switching fabrics, the concepts described in this article could apply to tactical systems as well.The views contained in this article are those of the author and should not be interpreted as necessarily representing the official policies, either expressed or implied, of DCA and DoD.
Eliminating periodic packet losses in the 4.3-Tahoe BSD TCP congestion control algorithm
Authors: Wang Zheng , Crowcroft Jon
Published: October 2004

The congestion control algorithm embedded in the 4.3-Tahoe BSD TCP implementation has dramatically improved congestion control over the Internet. However, several recent simulation studies on the dynamics of this algorithm has revealed that the algorithm exhibits clear oscillatory patterns in sending window size, round trip delay and bottleneck queue length. In this paper, we present a new congestion signal scheme and a dual traffic adjustment strategy. Simulation results show that our modifications can eliminate the periodic packet losses and substantially reduce the traffic oscillation.
The Q-bit scheme
Authors: Rose O.
Published: October 2004

Modern protocols designed for high-speed networks mostly adapt the rate at which packets are transmitted to control the flow of data between a sender and a receiver, and to control the load put upon the underlying network. In this article, the use of rate-adaption to realize 'congestion avoidance', a recently proposed highly sophisticated technique to control overload-conditions in networks is examined. With a simple analytical model of the system, expressions which help to tune it are derived. By directly comparing the resulting system to the well-known DECbit scheme which uses a window to adapt the load it is shown that most of the limitations of this scheme can be eliminated while preserving its advantages. More specific, because of the direct adaption of a rate fairness can be guaranteed in general topologies. This is possible without the need to put the burden of enforcing fairness on the (in a high-speed network already heavily loaded) routers. Finally the system can better adapt to varying packet-sizes, thus offering greater robustness and efficiency when used in real networks.
A bibliography on performance issues ATM networks
Authors: Nikloaidis I. , Onvural Raif O.
Published: October 2004

The Asynchronous Transfer Mode (ATM) is the transport mode of choice for B-ISDN. In order for high speed networks to become a reality, a number of performance issues has to be resolved. In recent years, there has been a growing interest in the literature in developing performance models to explore a wide range of performance problems varying from understanding the performance of a switch architecture to implementing efficient congestion control mechanisms and light weight transport protocols. In this paper, we briefly discuss various performance problems that arise in ATM networks and provide a bibliography of related papers reported in the literature.
Trends in telecommunication management and configurations
Authors: Carlson Patricia J. , Wetherbe James C.
Published: October 2004

A survey which investigated organizational management of telecommunications and the current and future configurations of telecommunications equipment showed some expected results and some surprises. The survey showed that public academic institutions are in advance of private institutions in the acquisition of different types of telecommunication equipment and connections. Also surprisingly widespread is the use in academic institutions of connections usually identified with business. Fully 8% of the academic institutions report being connected to customers, 14% indicate use of EDI, and 16% indicate connection to suppliers. Another surprising result is that previous investment in telecommunications is a better predictor than revenue (for business firms) or size of student body (for academic institutions) of the presence of rare telecommunications options, if they have acquired experience by a steady progression of telecommunications acquisitions. A final, perhaps more predictable, result concerns the evolution of telecommunication configurations in organizations of all types toward more interconnectability and in the directions of organization wide networks. Over 70% of the organizations are working toward organization wide networks but only 24% to 25% of the organizations consider that they have attained this goal. This trend is evident in both the academic and business environments. While it is not clear how this will impact the availability of data, it is apparent that a need for more interconnectability and ease of communication is being felt by organizations at this time.
A bound on the shift function in terms of the Busy Beaver function
Authors: Julstrom Bryant A.
Published: October 2004

The Busy Beaver function Σ(
n
) is the maximum number of 1's a halting n-state Turing machine may leave on an initially blank tape. The shift function
S
(
n
) is the maximum number of moves such a machine may make before it halts. This paper shows that
S
(
n
) < Σ(20n), then uses this result to prove that both Σ(
n
and
S
(
n
) are non-computable and their non-computability is equivalent to the undecidability of the halting problem. Demonstrations that several other functions are also non-computable apply a construction used in the proof of the bound on
S
(
n
).
Protected kernels and Ada 9X real-time facilities
Authors: Wrege D. E.
Published: October 2004

Many of the Ada 9X mappings will have a dramatic impact on current implementations of Ada run-time executives. This impact is particularly severe for the case of run-time systems that are implemented with protected kernels, often required in real-time military imbedded systems. Further, we believe that run-time systems that provide these new 9X facilities will be required to use techniques that are less efficient than current run-time systems at providing Ada 83 tasking services. Consequently, existing Ada systems tha t meet performance requirements may require modification to
tread water
.This report considers the proposed 9X changes which affect the implementation of real-time Ada run-time systems, addresses why these features impact the run-time, and, where possible, suggests optimizations to minimize the performance impact on
properly implemented
applications.
The BBFS Filesystem Model
Authors: Hillyer Bruce K. , Robinson Bethany S.
Published: October 2004

BBFS is a broadband filesystem research effort to support emerging applications that place intense demands on communications, computation, and data storage. Past research often addresses these needs with new special-purpose filesystems, such as transactional filesystems, replicated filesystems, real-time filesystems, and multimedia filesystems. A goal of BBFS is to be extensible so new mechanisms can be incorporated into a stable filesystem model.
A Toolkit for Interposing User Code at the System Interface
Authors: Jones Michael B.
Published: October 2004

Many contemporary operating systems utilize a system call interface between the operating system and its clients. Increasing numbers of systems are providing low-level mechanisms for intercepting and handling system calls in user code. Nonetheless, they typically provide no higher-level tools or abstractions for effectively utilizing these mechanisms. Using them has typically required reimplementation of a substantial portion of the system interface from scratch, making the use of such facilities unwieldy at best.I am currently constructing an object-oriented toolkit which substantially increases the ease of interposing user code between clients and instances of the system interface by allowing such code to be written in terms of the high-level objects provided by this interface, rather than in terms of the intercepted system calls themselves. This toolkit helps enable new interposition agents to be written which otherwise would not have been attempted.I am also currently using this toolkit to construct several agents including: protected environments for running untrusted binaries, modified filesystem namespaces, logical devices implemented entirely in user space, transparent network data compression and/or encryption agents, and system call tracing tools. Examples of other interesting agents which could be built include: transactional software environments, and emulators for other operating system environments.
On Ada packages, types and task types
Authors: Llamosí Albert
Published: October 2004

Two important uses of Ada packages are analyzed. Namely, for defining abstract data types and for defining task subsystems. Their advantages are only summarized, since they are well known, but the advantages and drawbacks of alternative ways of achieving such purposes are discussed and a uniform style of use is sustained, as well as the need for a specific notation for compound task types.
Call and connection management
Authors: Ahuja S. R. , Ensor J. R.
Published: October 2004

This is an extended abstract of a paper presented to Multimedia '92. A demonstration ISDN based multipoint multimedia conferencing system is described, together with a proposed protocol architecture for such applications.
Real-time synchronization control in multimedia distributed systems
Authors: Li Li , Karmouch A. , Georganas N. D.
Published: October 2004

Two basic synchronization problems are involved in the distributed multimedia systems. One of them is the simultaneous real-time data delivery. Simultaneous Real Time Data Delivery (SRTDD) refers to delivering multimedia data in different data streams belonging to the same time interval simultaneously. In this paper, an entire SRTDD control scheme for multimedia transmission is established. We propose a layered architecture which can be mapped to the OSI model to support the SRTDD control. The segment delivery protocols for real-time multimedia data streams are addressed. A practical segmentation method is also developed for real-time voice and video.
Defining more efficient transfer syntax for application layer PDUs in field bus applications
Authors: Cardoso Artur , Tovar Eduardo
Published: October 2004

This paper proposes a set of coding rules suitable for usage in the Field Bus Application Layer Services. The major considerations presented in this document were adopted as a working basis in the ESPRIT project 5206, FICIM (Field bus Integration into Computer Integrated Manufacturing). As an input from FICIM to the international standardization work, in particular to the ISA SP 50 / IEC 65C WG6 committees, this proposal was the object of a survey, and its adoption in the International Standard for Field Bus Networks is under discussion at the time of this writing.
Rate controls in standard transport layer protocols
Authors: Eldridge Charles A.
Published: October 2004

Flow control mechanisms in current datagram switching networks currently have several responsibilities, including avoiding congestion and avoiding overruns. In particular, networks and end-systems rely heavily upon the window mechanisms specified in current transport protocol standards such as TCP and TP4. These responsibilities will increase in future systems. This paper develops a connection model in order to assess the extent to which transport protocol data rates can be controlled using this available mechanism. Under very low delays, window-based flow control is not effective in slowing the rates at which a sender introduces data to the network or internetwork. Therefore, direct rate controls will be needed to enforce policies or to optimize performance across a variety of users and media.
The effects of virtually addressed caches on virtual memory design and performance
Authors: Inouye Jon , Konuru Ravindranath , Walpole Jonathan , Sears Bart
Published: October 2004

Recent times have witnessed rapid advances in microprocessor technology resulting in an order of magnitude performance improvement every few years. These developments in hardware have been paralleled by several prominent trends in operating system design, the most notable being a move towards message-passing micro-kernels. However, operating system performance has not kept pace with that of the underlying hardware. It has become apparent that design changes to enhance processor performance can have adverse effects on operating system performance. This problem arises when the architectural assumptions implicit in an operating system's design are inappropriate for the architectures on which it executes.This paper examines one specific area in which operating system design assumptions appear to be in conflict with trends in modern processor architecture. We focus on the performance effects of virtually addressed caches on two contemporary operating systems (Mach and Chorus). We present experimental results to illustrate the impact of virtually addressed caches on the performance of primitive virtual memory operations, and higher-level operations, such as inter-process communication, that utilize these primitive operations. The main goal of the paper is to encourage operating system designers to revisit some of the basic architectural assumptions implicit in modern operating system designs.
Design of optimal distributed file systems
Authors: Borghoff Uwe M.
Published: October 2004

In this paper, the problem of determining an optimal location strategy for an individual program execution is considered. In addition, we propose a heuristic approach for the dynamic file allocation problem. In order to reduce the complexity of the optimization problems, a cluster-based approach is used.To access the data files of a distributed file system, a user initiates a program execution. Based on the current allocation of the program and data files as well as the knowledge about the characteristics of the programs, a first optimization calculates the optimal cluster for each individual program execution. The objective of this optimization is the minimization of the intercluster traffic of an individual program execution. Within the optimal cluster, a simple load-balancing strategy is used to determine the corresponding executing node.A second optimization looks for file allocations where the global intercluster traffic is minimized subject to the following constraints: minimal number of file copies, availability, and storage capacity.Experimental results showing the efficiency of the proposed algorithms are examined, and the implications of the model for the design of very large distributed file systems are discussed.
Supporting real-time applications in an Integrated Services Packet Network
Authors: Clark David D. , Shenker Scott , Zhang Lixia
Published: October 2004

This paper considers the support of real-time applications in an
Integrated Services Packet Network
(ISPN). We first review the characteristics of real-time applications. We observe that, contrary to the popular view that real-time applications necessarily require a fixed delay bound, some real-time applications are more flexible and can adapt to current network conditions. We then propose an ISPN architecture that supports two distinct kinds of real-time service:
guaranteed
service, which is the traditional form of real-time service discussed in most of the literature and involves pre-computed worst-case delay bounds, and
predicted
service which uses the measure performance of the network in computing delay bounds. We then propose a packet scheduling mechanism that can support both of these real-time services as well as accommodate datagram traffic. We also discuss two other aspects of an overall ISPN architecture: the service interface and the admission control criteria.
Internet routing over large public data networks using shortcuts
Authors: Tsuchiya Paul F.
Published: October 2004

With the emergence of large switched public data networks that are well-suited to connectionless internets, for instance SMDS, it is possible that larger and larger numbers of internet users will get their connectivity from large public data networks whose native protocols are not the same as the user's internet protocol. This results in a routing problem that has not yet been addressed. That is, large numbers of routers (potentially tens of thousands) must be able to find direct routes to each other in a robust and efficient way. This paper describes a solution to the problem, called shortcut routing, that incorporates 1) a sparse graph of logical connectivity between routers, 2) hierarchical addressing among the public data network subscribers, and 3) the use of “entry router” information in packets to allow routers to find one hop “shortcuts” across the multi-hop logical graph.
Dynamic Time Windows
Authors: Faber Theodore , Landweber Lawrence H. , Mukherjee Amarnath
Published: October 2004

We present a feedback congestion control method, Dynamic Time Windows, for use in high speed wide area networks based on controlling source variance. It is part of the two-level integrated congestion control system introduced in our earlier work[1].

The method consists of a packet admission control system and a feedback system to dynamically control source burstiness. Source throughput is not modulated as with traditional packet windows, allowing system throughput to remain high while avoiding congestion. Furthermore, the admission control bounds congestion times in the network, allowing feedback to be effective in the face of large bandwidth delay products.

The basic control mechanisms are analogs to traditional packet windows applied to controlling time windows - a new mechanism which allows switches to modulate source variances. The proposed system is simulated, and the results reported and analyzed. Enhancements to the basic system are also proposed and analyzed.

We wish to stress that the system described here is the second level of a two-level congestion control. Previous work[1] concentrated on the switch queueing mechanism, Pulse, while this work is a detailed examination of the feedback system used to adjust time windows to changing network load.
Performance analysis of an asynchronous multi-rate crossbar with bursty traffic
Authors: Stirpe Paul , Pinsky Eugene
Published: October 2004

One of the most promising approaches to building high speed networks and distributed multiprocessors is the use of optical interconnections. The basic component of such a system is a switch (interconnection network) that has a capacity of interconnecting a large number of inputs to outputs. In this paper we present an analysis of an

N
1

x

N
2

asynchronous crossbar switch model for all-optical circuit-switching networks that incorporates multi-rate arrival traffic with varied arrival distributions. We compare the model behavior using traffic loads derived from the Binomial, Pascal, and Poisson statistical distributions. We give efficient algorithms to compute the performance measures. We analyze the effect of load changes from particular traffic distribution streams on system performance and give a simple “economic” interpretation.
Image transfer
Authors: Turner Charles J. , Peterson Larry L.
Published: October 2004

The transfer of digital images between data archives and scientific workstations is likely to consume a significant amount of network bandwidth in the very near future. This paper examines the image transfer problem from an end-to-end perspective, that is, it describes a complete image transfer protocol that takes into account both the nature of digital imagery and the properties of the underlying network. Specifically, it describes a simple algorithm for encoding images into network packets in such a way that the receiver can recover from dropped packets without requiring the sender to retransmit them. Avoiding retransmissions has the advantages of improving response time and eliminating the need to buffer data at the sender.
Update on MIS research
Authors: Lending Diane , Wetherbe James C.
Published: October 2004

MIS research between 1984 and 1990 is categorized by university, journal and type of research. The results are compared to a previous study conducted in 1984 which analyzed research conducted between 1977 and 1983. The amount of MIS research has almost doubled during the period of the study as has the number of universities producing MIS research. The leading producers of research are the University of Minnesota, MIT, Harvard, the University of Pittsburgh and New York University. This article provides in depth analysis of journals and types of research being conducted.
The advantages of electronic data interchange
Authors: Bergeron François , Raymond Louis
Published: October 2004

The purpose of this research was to identify success factors of EDI implementation and the benefits organizations could obtain by using this technology. The success factors found empirically in a field study of 140 Canadian enterprises are the organizational support, the implementation process, the control procedures and the level of EDI integration in the firm. The level of success also depends upon the level of imposition of EDI by partners. The study found evidence that, in order of importance, the benefits of EDI implementation are improvements in terms of information quality, transaction speed, administrative costs, strategic advantage and operations management.
An alternative to asynchronous transfer of control in Ada 9X
Authors: Antonelli Charles J. , Volz Richard A.
Published: October 2004

We have observed the introduction of the asynchronous transfer of control (herein named ATC) into Ada 9X with some concern. We analyze the fundamental problems of ATC in the real-time environment and propose an alternative solution which we believe has improved properties.
Replacing passive tasks with Ada9X protected records
Authors: Locke C. Douglass , Mesler Thomas J. , Vogel David R.
Published: October 2004

Ada 83 has often been criticized for its lack of a lightweight data synchronization primitive. Compiler vendors have responded to this criticism by implementing the Haberman-Nassi algorithm with a construct called a
passive
task. The Ada 9X Project has proposed a change to the Ada language adding a
protected record
construct to support lightweight synchronization. In this paper, we illustrate the changes in coding required to convert an application originally designed to exploit passive tasking to use the protected record construct instead. The resulting software engineering effects of using passive tasks and protected recordsre then compared for this sample task set. We conclude by discussing some protected recorded semantics that may require further clarification and/or modification, and some of the trade-offs that result.
Building group decision support rooms using "off-the-shelf" computing resources: prospects and issue
Authors: Roth Roberta M. , Wood William C. , Hahm Ronald , Power Daniel J.
Published: October 2004

The concept of a decision support system (GDSS) is appealing to many organizations as ways are sought to improve the productivity of group meetings. Unfortunately, the purchase or development of group decision support systems may be prohibitively expensive. This paper explores an alternative way of acquiring GDSS capabilities. First, the fundamental features of a GDSS are identified based upon a review of literature. These features provide a framework in which to identify GDSS requirements and capabilities. Then, an implemented GDSS composed of off-the-shelf software and readily available hardware is described. A general model is presented for GDSS developers that clarifies choices and options that must be made when assembling a GDSS using off-the-shelf components. The article closes with a discussion of important issues for developers of "off-the-shelf" GDSSs.
Visibility representations of planar graphs (abstract)
Authors: Tollis Ioannis G.
Published: October 2004

Interesting representations of graphs results from mapping vertices into horizontal segments and edges into vertical segments drawn between visible vertex-segments. (Two parallel segments of a given set are visible if they can be joined by a segment orthogonal to them, which does not intersect any other segment.) Such representations are called visibility representations. These representations find applications in VLSI layout, algorithm animation, visual languages and CASE tools. We consider three types of visibility representations: (
i
) Weakvisibility representation, if two vertices are adjacent then their corresponding segments must be visible. (
ii
) ε-visibility representation, where vertices can be represented by open, closed, or semiclosed horizontal segments in the plane such that two vertices are adjacent if and only if their associated segments are visible. (
iii
) Strong-visibility representation, where vertices are represented by closed horizontal segments such that two vertices are adjacent if and only if their corresponding segments are visible. We discuss various types of visibility representations of planar graphs on the plane, cylinder, and sphere.
Drawing compound digraphs and its application to an idea organizer (abstract)
Authors: Sugiyama Kozo
Published: October 2004

An
upward
drawing of an acyclic digraph is a planar straight-line drawing with the additional requirement that all the edges flow in the same direction, e.g., from bottom to top. The literature on the problem of constructing upward drawings of important classes of digraphs is surveyed. First, it is show that there is a family of binary trees with n vertices requiring Ω(
n
log
n
) area for any upward drawing; moreover, that bound is tight, i.e. each binary tree with
n
vertices can be drawn with
O
(
n
log
n
) area. Second, motivated by the elegant
H
-tree layout algorithm for constructing non-upward drawings of complete binary trees, an algorithm is presented for constructing an upward drawing of a complete binary tree with
n
vertices in
O(n)
area. This result is extended to the drawings of
Fibonacci trees
. Third, it is shown that the area requirement of upward drawings of series-parallel digraphs crucially depends on the choice of planar embedding. Also, parallel and sequential drawing algorithms are presented that are optimal with respect to both the time complexity and to the area achieved. Several results show that while series-parallel digraphs have a rather simple and well understood combinatorial structure, naive drawing strategies lead to drawings with exponential area, and clever algorithms are needed to achieve optimal area.
Algorithms for orthogonal drawings (abstract)
Authors: Tamassia Roberto
Published: October 2004

The Andreev-Thurston circle packing theorem is generalized and improved in three ways. First, to arbitrary maps on closed surfaces. Second, we get the simultaneous circle packing of the map and its dual map so that, in the corresponding straight-line representations of the map and the dual, any two edges dual to each other cross at the right angle. The necessary and sufficient condition for a map to have such a primal-dual circle packing representation is that its universal cover is 3-connected (the map has no "planar" 2-separations). Finally, a polynomial time algorithm is obtained that given a map
M
and a rational number ε > 0 finds an ε-approximation for the primal-dual circle packing representation of
M.
In particular, we get a polynomial time algorithm for geodesic convex representation of reduced maps on arbitrary surfaces.
An automatic layout facility (abstract)
Authors: Liotta Giuseppe
Published: October 2004

We introduce a new method to optimize the required area, minimum angle and number of bends of planar drawings of graphs on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. With this method linear time an space algorithms can be designed for many graph drawing problems.
(i)
We show that every triconnected planar graph
G
can be drawn convexly with straight lines on an (2
n
-4)×(
n
-2) grid.
(ii)
If
G
has maximum degree four (three), then
G
can be drawn orthogonal with at most [3
n
/2] + 3 (at most [
n
/2] + 1) bends on an
n
×
n
grid ([
n
/2] × [
n
/2] grid, respectively).
(iii)
If
G
has maximum degree
d
, then
G
can be drawn planar on an (2
n
-6) × (3
n
-6) grid with minimum angle larger than 1/d-2 radians and at most 5
n
-15 bends. These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g. concerning visibility representations, are included.
Metadatabase solutions for enterprise information integration problems
Authors: Hsu Cheng , Rattner Laurie
Published: October 2004

The success of modern information technology in the past decades has brought about the proliferation of systems dedicated to individual groups of applications and functions. This proliferation, in turn, has led to the need for enterprise-wide management and integration of information, and has triggered major efforts such as systems integration, re-engineering, and computer integrated manufacturing. Nonetheless, achieving such integration remains a challenge.To effectively manage information resources and to coordinate processing at a global level requires concepts and technologies that overcome the difficult problems arising from, among other things, combining data with knowledge and managing concurrent multi-database systems. The metadatabase approach offers fresh promise to solve some of these fundamental problems. The basic functionalities and architecture of the metadatabase model are described in this paper. Several examples central to information management are also included to illustrate how the metadatabase approach can be deployed to better manage enterprise-wide information resources.
Determining the shortest process migration paths for program compilation using a dynamic programming approach
Authors: Wong K. C.
Published: October 2004

Programs written in multiple, partially disjoint versions of a high-level language may have to
migrate
for program compilation in the environment in which the versions are distributed. The decisions made during program compilation concerning which node is to be selected from the possible ones supporting those disjoint features constitute a
process migration path.
The shortest paths which minimize the time spent in process migration can be determined using a
dynamic programming
approach. The approach is versatile in that it determines
some
of the shortest paths in a branch-and-bound way and determines
all
of the shortest paths in a non-brute force way by pruning those branches at the turning points that version expansion is not necessary.
A status report on research in transparent informed prefetching
Authors: Patterson R. Hugo , Gibson Garth A. , Satyanarayanan M.
Published: October 2004

This paper focuses on extending the power of caching and prefetching to reduce file read latencies by exploiting application level hints about future I/O accesses. We argue that systems that disclose high-level knowledge can transfer optimization information across module boundaries in a manner consistent with sound software engineering principles. Such Transparent Informed Prefetching (TIP) systems provide a technique for converting the high throughput of new technologies such as disk arrays and log-structured file systems into low latency for applications. Our preliminary experiments show that even without a high-throughput I/O subsystem TIP yields reduced execution time of up to 30% for applications obtaining data from a remote file server and up to 13% for applications obtaining data from a single local disk. These experiments indicate that greater performance benefits will be available when TIP is integrated with low level resource management policies and highly parallel I/O subsystems such as disk arrays.
Extending device management in Minix
Authors: Kavka C. , Printista M. , Gallard R.
Published: October 2004

Minix is a Unix clone Operating System, designed by Tanembaum ([2],[3]) to allow beginners to do practical training in Operating Systems area. In this context the present paper describes the work done by a group of undergraduates implementing extensions in device management. Problems in the original code, detected during the analysis and development stages, are also reported.
A taxonomy of issues in name systems design and implementation
Authors: Yeo A. K. , Ananda A. L. , Koh E. K.
Published: October 2004

In the last decade, name systems have grown from a single centrally-controlled server providing only host name to physical address mapping, to a complex system consisting of multiple and distributed servers, providing not only name mapping, but also general directory lookup services. These advances are due in part to the increase in size, complexity and heterogeneity of distributed systems. This paper presents a taxonomy of design and implementation issues in building a name system.
A protocol processing architecture for networked multimedia computers
Authors: Gopalakrishnan R. , Bovopoulos Andreas D.
Published: October 2004

Multimedia workstation architectures differ from current architectures in these respects --- they have multiple specialized processing units, a high speed I/O interconnect mechanism, a high speed broadband network interface and a real-time multitasking operating system (OS) that provides QoS guarantees. These systems will primarily be used to run distributed applications that require high network throughput and predictable delay and delay jitter for real-time traffic. We argue the need for a different protocol organization and processing architecture in order to achieve this. We show how the emerging hardware architecture and OS structures favor a "decentralized protocol processing" approach, that takes advantage of the data delivery mechanism provided by the hardware to improve in-band (protocol data) processing, and the sophisticated OS mechanisms based on communicating objects to improve the out-of band (control) processing. We discuss the need for providing end-to-end QoS guarantees for applications and discuss how it can be naturally incorporated in the proposed architecture.
A non-blocking transaction data flow graph based approach for replicated data
Authors: Reddy P. Krishna , Bhalla S.
Published: October 2004

Regplicated data management systems adopt the 1-copy serializability criteria for processing transactions. In order to achieve this goal, many approaches, rely on obtaining votes from other sites, for processing update requests. In this paper, a technique for generation of precedence graphs for each transaction execution is proposed. The transaction data flow graph approach is a fully distributed approach. The proposed technique, is free from deadlocks, and avoids resubmission of transactions.
Splaying a search tree in preorder takes linear time
Authors: Chaudhuri R. , Höft H.
Published: October 2004

In this paper we prove that if the nodes of an arbitrary no-node binary search tree T are splayed in the preorder sequence of T then the total time is O(n). This is a special case of the splay tree traversal conjecture of Sleator and Tarjan.
Experimental testing of transport protocol
Authors: Rafiq O , Chraïbi C , Castanet R
Published: October 2004

This paper describes the interactive testing of ISO transport protocol we carryed out by using the so-called astride technique. The transport protocol class tested is class 2. So far more than two hundreds testing cases have been designed and applied. The testing design approach is based on empirical principles somewhat similar to those used in compiler validation. Testing results are discussed.
A multiply-and-accumulate selection algorithm for dynamic entropy coding
Authors: Irwin D
Published: October 2004

Entropy coding is a well-known tool for reducing the redundancy present in communication signals. As a signal's redundancy is reduced, the bandwidth required for its transmission over a low-noise channel also decreases. Memory requirements may likewise be reduced for coded information stored in low-error media. A method is presented for determining entropy codes by means of a sequence of multiply-and-accumulate and look-up operations. Structuring the process in such a fashion allows the effective use of a digital signal processor for dynamically generating adaptive codes in response to changing source statistics.
A proposal for an improved network layer of an LAN
Authors: Rossi G , Garavaglia C
Published: October 2004

A distributed system is an interconnected network of autonomous processing elements that is characterized by a decentralized control. In the last years, many activities have been addressed to the study and definition of distributed algorithms and languages, in order to design distributed applications and take advantage of the facilities of computer networks.
An extended X.400 architectural model
Authors: Medina M
Published: October 2004

This paper presents an update of a model generated in the AMIGO project supported by the CEC (Comission of the European Community) in the framework of the action COST-11ter. It collects together comments made at the meeting of the IFIP WG6.5 held in Oslo, 2-5 December 1985. Acknowledgements go to the attendees of that meeting and to the members of the AMIGO project for the contributions they made.
Computer support for knowledge workers: A review of laboratory experiments
Authors: Leitheiser Robert L
Published: October 2004

The focus of system design and evaluation has shifted from increasing computer efficiency to improving human/computer effectiveness. The new emphasis is especially critical when the users of the system are not information systems specialists or clerical support personnel, but highly paid knowledge workers. This paper presents a framework for organizing experimental studies in human/computer interaction and suggesting new research opportunities. The framework is applied to a review of 39 experiments in the areas of database management, decision support, text processing, graphics processing, calculation, and operating systems. Studies are assessed for their coverage of experimental variables and organized according to their findings.
Authentication and revocation in SPM extended abstract
Authors: Calvelli Claudio , Varadharajan Vijay
Published: October 2004

SPM formalism can be used to specify the protection structure of a system, and it also provides an algorithm to decide if some privileges can be granted to some subjects. This paper extends the model to take into account authentication and revocation. The authentication extension gives an algorithm to find out which authentication steps must be taken by a subject in order to gain some privileges. The revocation extension allows to decide whether certain privileges can be given back after they have been revoked. The two extensions are independent in the sense that each one corresponds to a change to a different part of the decision algorithm.
Fault tolerance
Authors: Romanovsky Alexander B.
Published: October 2004

The purpose of this paper is to single out and generalize about the essential features and properties of synchronization and to argue in favour of the idea of designing and developing fault tolerance for distributed computer system on the basis of a multilevel synchronization system. We propose to consider designing and developing a hierarchical system of synchronizing redundant components in these systems the first and foremost stage in providing fault tolerance in application systems. The general peculiarities of using synchronization system for this end are considered.
Distributed algorithm for K-entries to critical section based on the directed graphs
Authors: Naimi Mohamed
Published: October 2004

This paper proposes a token based mutual exclusion algorithm for distributed systems that allows K simultaneous entries to a critical section. In the algorithm, a logical directed graph is maintained in a connected network.This algorithm does not use sequence numbers, and the number of messages required to provide mutual exclusion, is between 0 and 2*(N-l) where N is the number of processes in the network.
Linda meets Minix
Authors: Ciancarini P. , Guerrini N.
Published: October 2004

Currently large interest is devoted to the development of systems supporting parallel and distributed programming over a network of workstations. We are exploring operating system support for this kind of programming, that instead is usually implemented at the user process level. We have chosen the Linda model as the basis of a programming system for networks of personal computers running Minix, a Unix-like operating system for personal computers.In this paper we shortly describe the Minix operating system and its services for remote communication based on the Amoeba protocol. We have extended Minix with new communication primitives based on Linda; we show their implementation, describing the new system architecture, and compare the new system with other Linda implementations.
Operating systems and cost management
Authors: Kulkarni Dinesh C. , Banerji Arindam , Cohn David L.
Published: October 2004

This paper introduces the emerging area of operating system-based cost management. It argues that new developments are dramatically shortening the time constants in cost-based decisions and markedly increasing their complexity. This is particularly true of mobile computing where usage charges will be applied to communication and to the rapidly developing market in for-fee services. Consequently, system software must become aware of costs and must include the user in its optimization process. This paper is an attempt to initiate discussion about operating system services that deal with monetary costs and mentions some basic issues involved. The work has several speculative components; especially those that deal with prediction of interfaces that involve charges. It looks at the evolving nature of computing costs and introduces the notion of a cost-aware abstraction which requires the transfer of money in return for some service.
Variable granularity cache coherence
Authors: Mummert L. , Satyanarayanan M.
Published: October 2004

Weak connectivity is characterized by slow or intermittent networks. Distributed file systems using weak connections must function in spite of limited bandwidth and frequent connectivity changes. Callback-based cache coherence schemes were designed to minimize client-server communication, but with an underlying assumption that the network is fast and reliable (i.e., a LAN). This paper
large presents granularity callbacks
as a way to reduce the client-server communication necessary to maintain file cache coherence. Large granularity callbacks trade off precision of invalidation for speed of validation after connectivity changes.
On mutual exclusion in faulty distributed systems
Authors: Bouabdallah Abdelmadjid
Published: October 2004

In this paper, we present an extension of the fault-tolerant mutual exclusion algorithm of [1] to make it deadlock-free when a node requesting critical section or when a node executing its critical section fails. The proposed algorithm requires
O
(√
tn
) messages per critical section entry (in a network of
n
nodes) and
O
(
t
√
tn
) messages when a node fails (
t
− 1 is the upper bound of the node failures).
A taxonomy of proof systems (part 1)
Authors: Goldreich Oded
Published: October 2004

Several alternative formulations of the concept of an efficient proof system are nowadays coexisting in our field. These systems include the classical formulation of
NP, interactive proof systems
(giving rise to the class
IP
)
computationally-sound proof systems
, and
probabilistically checkable proofs
(
PCP
) which are closely related to
multi-prover interactive proofs
(
MIP
). Although these notions are sometimes introduced using the same generic phrases, they are actually very different in motivation, applications and expressive power. The main objective of this essay is to try to clarify these differences.
Computer science laboratories
Authors: Ross R.
Published: October 2004

In the second issue of the
News
(volume 24, number 2) this year I described the new breadth-first introductory curriculum in place at Montana State University, focusing on the role that theory plays in the four lecture courses constituting the curriculum. In the third issue (volume 24, number 3) an abbreviated syllabus was given for the four course sequence. During the interim, I have received numerous e-mail requests for more complete information, which indicates a growing interest in breadth-first, integrated approaches to the computer science curriculum as proposed in the
Denning Report
and
Computing Curricula 1991
(cited in the last two issues). In this installment of the
Forum
some of the interesting aspects of the laboratory component of the curriculum are described.
A bibliography on minimax trees
Authors: Diderich Claude G.
Published: October 2004

This article lists all theoretical and practical papers, theses and reports known to the author on the subject of studying minimax trees and analyzing sequential and parallel minimax tree search algorithms.The items of the bibliography are listed in alphabetical order in accordance with the first author's name. Items not marked are in my collection or are available to me (if there are any hard-to-obtain items in this group, I would be happy to make copies of them available). Others, e.g. items marked with a star (*), are cited elsewhere as relevant, but are yet unavailable to me (I would appreciate receiving copies of these from anyone who has access to them).This bibliography is available in computer readable BIBT
E
X form by sending an e-mail request to the author or by anonymous ftp from valkyries.andrew.cmu.edu in directory /pub/chess/texts. The labels indicated are they keys used in the BIBT
E
X version of the bibliography. Any corrections as well as new items to this bibliography are kindly requested and highly appreciated in advance. Finally the author wishes to thank all the people who have helped in building this bibliography.
Ada and C
Authors: Nakao Zensho , Kinjo Masaya , Nakama Masahiro
Published: October 2004

Some fundamental differences between Ada and C as the language for operating system description are listed up, specifically, those differences observed in translating the C-based MINIX operating system into Ada are collected; there are also given concrete illustrative program examples.