bluuebunny/crossref_metadata_2025 huggingface dataset:
Ada for MS-Windows applications
Authors: Pukite Paul R.
Published: October 2004

Standard Ada constructs such as package specifications, generics, tasking, and exceptions support the construction of reliable, maintainable, and reusable Microsoft Windows applications. This letter presents examples of how to use some of these constructs in the practical design of Ada programs running under Windows. These include the specification of dialog box interfaces and the use of generic packages for interapplication data exchange.
The infinite version of an open communication complexity problem is independent of the axioms of set theory
Authors: Fortnow Lance , Kurtz Stuart , Whang Duke
Published: October 2004

In 1986, Babai, Frankl and Simon (BFS86) defined the polynomial hierarchy in communication complexity and asked whether Σ

ee

2
= Φ

ee

2
. In order to tackle this problem, researchers have looked at an infinite version. We recently became aware of a paper from 1979 where Miller [Mil79] shows that this infinite version is independent of the axioms of set theory. In this note we will describe Miller's result and give a simplified proof of one direction by showing that the continuum hypothesis implies that Σ
r
2
= Φ
r
2
p
(R × R).
An introduction to ultimately periodic sets of integers
Authors: Matos Armando B.
Published: October 2004

We summarize some of the theory and an application of a new method for representing "periodic" sets of integers. A much more detailed discussion will be presented in [5].
Optimal privacy and authentication on a portable communications system
Authors: Carlsen Ulf
Published: October 2004

Beller, Chang and Yacobi [2] have recently proposed a set of secret key and public key protocols to meet authentication and privacy requirements for conversation set-up protocols for the initiating party of portable communication systems. This paper improves upon the protocols to obtain a higher assurance of authentication and key distribution. Conversation set-up protocols for the responding party are discussed, a public key protocol providing end-to-end authentication and privacy is described, and relative as well as collective merits of the protocols are emphasised.
Combining optimism and pessimism to produce high availability in distributed transaction processing
Authors: Crichlow Joel M.
Published: October 2004

In a distributed system some or all of the data items are replicated and stored at separate nodes. This increases the availability of these items and it is then possible to complete transactions faster than in single node systems. Hovever the concurrent processing of transactions at separate nodes can generate inconsistencies in the stored information. Some mechanism must be employed to address the inconsistencies that can arise. A system has been designed that allows a transaction to be processed immediately (optimistically) at any individual node in a replicated system as long as the transaction satisfies a cost bound criterion. Such a transaction can make external responses but it does not alter the database. All transactions are also run in a global one-copy serializable manner (pessimistically) at which time their updates are committed. It may be necessary to make another external response. The transaction processing system is expressed as a simple computational model and the correctness of the system is discussed.
A quality of service architecture
Authors: Campbell Andrew , Coulson Geoff , Hutchison David
Published: October 2004

For applications relying on the transfer of multimedia, and in particular continuous media, it is essential that quality of service (QoS) is guaranteed system-wide, including end-systems, communications systems and networks. Although researchers have addressed many isolated areas of QoS provision, little attention has so far been paid to the definition of an integrated and coherent framework that incorporates QoS interfaces, management and mechanisms across all architectural layers. To address this deficiency, we are developing a Quality of Service Architecture (QoS-A) which offers a framework to specify and implement the required performance properties of multimedia applications over high-performance ATM-based networks. The QoS-A incorporates the notions of flow, service contract and flow management. Flows characterise the production, transmission and eventual consumption of single media streams, service contracts are binding agreements between users and providers and flow management provides for the monitoring and maintenance of the contracted QoS levels. This paper provides an overview of the QoS-A and focuses particularly on the role of the transport service and protocol in the architecture. We describe a multimedia enhanced transport service (METS), flow management and transport layer service contract. We show how QoS levels contracted at the transport service interface can be assured in the context of our local ATM environment.
Ranking institutional contributions to decision support systems research
Authors: Eom Sean B.
Published: October 2004

This research investigates the types and contributions of DSS research conducted by major MIS doctoral institutions in the U.S. and Canada. The primary data for this study were gathered from a total of 692 citing articles in the DSS area over the past 20 years (1971-1990) and the database file of cited references that consists of a total of 15,030 records taken from the 692 citing articles.This research ranks 85 MIS doctoral institutions in the U.S. and Canada in terms of their contributions to decision support systems research during the period of 1971 through 1990 using a citation analysis. Among those doctoral institutions, three universities are identified as leading DSS research schools: MIT, the University of Minnesota, and the University of Texas-Austin.
A comparative analysis of MIS project selection mechanisms
Authors: McKeen James D. , Guimaraes Tor , Wetherbe James C.
Published: October 2004

MIS projects are selected by any of four different groups within organizations---top management, steering committees, user departments and MIS departments. Because of their inherent differences, each of these groups is likely to favor different types of MIS projects. That is, they exhibit different selection biasing. An investigation of the nature and extent of this biasing is examined in this research.Data were collected from 176 MIS projects selected from 60 organizations. Projects were categorized as being selected by top management, steering committees, user departments or MIS departments, and specific characteristics (size, risk, and organizational commitment) were measured for each project.As hypothesized, the research showed that projects selected by different groups did indeed differ significantly with respect to these characteristics. Projects selected by top management do not tend to be more strategic, profitable, resource consuming or risky, or more related to organizational well-being than those chosen by other project selection groups. These projects did, however, tend to experience the longest start delay and elapsed development time.Projects selected by steering committees tended to be larger and riskier, and to require more organizational change. Formal cost-benefit analysis is more predominant, but surprisingly, projects selected are not more cross-functional in scope.User department-selected projects, comparatively, are smaller, more quickly developed, and involve the fewest users, layers of management and business functions.MIS-selected projects have more of an integration focus and follow more logical sequences in development. Their projects experience fewer delays in deliberation and duration, and less concern is given to cost-benefit analysis.The paper concludes by presenting the implications of having each of these groups select MIS projects. Using this information, organizations can establish or assess the effect of using different mechanism for selecting MIS projects.
Database querying and constraint programming
Authors: Kanellakis Paris
Published: October 2004

The declarative programming paradigms used in constraint languages can lead to powerful extensions of relational database query languages. This is an overview of recent progress on such constraint query languages, with a list of related open theoretical computer science questions.
Computational Geometry Column 24
Authors: O'Rourke Joseph
Published: October 2004

Open problems from the Tenth ACM Symposium on Computational Geometry and the Sixth Canadian Conference on Computational Geomerty listed tersely.The Tenth ACM Symposium on Computational Geometry was held June 6--8, 1994 in Stony Brook, New York, USA, and the Sixth Canadian Conference on Computational Geometry was held August 2--6, 1994 in Saskatoon, Saskatchewan, Canada. The problems listed below were either suggested or referenced by the authors of the indicated papers. Papers are identified by the last names of the authors; the start page in the proceedings in indicated in brackets.
Delegation with Ada 9x
Authors: Räihä Liisa
Published: October 2004

Delegation is a technique used object oriented programming. It is shown with small examples how it can be used with Ada 9x.
Ada's design goals and object-oriented programming
Authors: Carter Jeffrey R.
Published: October 2004

Ada was designed to support and enforce software-engineering principles to promote the development of programs which are easy to read and understand. Ada 9X, the proposed revision to Ada 83, includes features for object-oriented programming, including inheritance and dispatching. Object-oriented programming is shown to emphasize ease of writing over readability and under-standability, violating one of Ada's main design goals. A significant example demonstrates that object-oriented programming reduces readability and understandability.
Is natural language querying practical?
Authors: Dekleva Sasa M.
Published: October 2004

The study reported here involved the use of the natural language query system INTELLECT. It evaluated the level of correct interpretation to investigate whether the use of such a system is practical. Two sets of queries generated by two groups of senior-level business students were used. Questions from the first set were generated by "naïve" students who were untrained, and not aware that they were providing queries which were to be executed by a computer. Students from the second group attended a short lecture and understood that they were to generate natural language queries to be executed by a computer. INTELLECT's lexicon was augmented in stages. The level of correct interpretation achieved in this study is far above any previously reported and suggests that existing natural language query systems may be practical. key features in the accuracy of interpretation were user training and iterative lexicon enhancement.
How much is information systems research addressing key practitioner concerns?
Authors: Szajna Bernadette
Published: October 2004

The results of a series of three surveys, published by the MIS Quarterly, have designated issues of primary concern to IS practitioners. In addition, Gillenson and Stutz have recently identified the major publication outlets for IS research. By mapping the topics addressed in these research publications with the primary issues of concern to the practitioner, this study responds to the question of how much IS researchers are addressing key practitioners concenrs. Findings suggest that IS researchers have been focusing on important practical issues but that these issues were critical to IS practitioners in the early 1980's. While some of these issues, such as end-user computing, data management, and software development may be of such abiding interest that it is appropriate to continue research in these areas, other topics have yet to receive the attention that they might deserve. The findings also specify practitioner issues that have experienced an increase or decrease in research interest and the publication outlets that emphasize primary practitioner issues.
Experiences with a high-speed network adaptor
Authors: Druschel Peter , Peterson Larry L. , Davie Bruce S.
Published: October 2004

This paper describes our experiences, from a software perspective, with the OSIRIS network adaptor. It first identifies the problems we encountered while programming OSIRIS and optimizing network performance, and outlines how we either addressed them in the software, or had to modify the hardware. It then describes the opportunities provided by OSIRIS that we were able to exploit in the host operating system (OS); opportunities that suggested techniques for making the OS more effective in delivering network data to application programs. The most novel of these techniques, called
application device channels
, gives application programs running in user space direct access to the adaptor. The paper concludes with the lessons drawn from this work, which we believe will benefit the designers of future network adaptors.
An architecture for wide-area multicast routing
Authors: Deering Stephen , Estrin Deborah , Farinacci Dino , Jacobson Van , Liu Ching-Gung , Wei Liming
Published: October 2004

Existing multicast routing mechanisms were intended for use within regions where a group is widely represented or bandwidth is universally plentiful. When group members, and senders to those group members, are distributed
sparsely
across a wide area, these schemes are not efficient; data packets or membership report information are occasionally sent over many links that do
not
lead to receivers or senders, respectively. We have developed a multicast routing architecture that efficiently establishes distribution trees across wide area internets, where many groups will be sparsely represented. Efficiency is measured in terms of the state, control message processing, and data packet processing, required across the entire network in order to deliver data packets to the members of the group.

Our Protocol Independent Multicast (PIM) architecture: (a) maintains the traditional IP multicast service model of receiver-initiated membership; (b) can be configured to adapt to different multicast group and network characteristics; (c) is not dependent on a specific unicast routing protocol; and (d) uses soft-state mechanisms to adapt to underlying network conditions and group dynamics. The robustness, flexibility, and scaling properties of this architecture make it well suited to large heterogeneous inter-networks.
Experiences of building an ATM switch for the local area
Authors: Black Richard , Leslie Ian , McAuley Derek
Published: October 2004

The Fairisle project was concerned with ATM in the local area. An earlier paper [9] described the preliminary work and plans for the project. Here we present the experiences we have had with the Fairisle network, describing how implementation has changed over the life of the project, the lessons learned, and some conclusions about the work so far.
Asymptotic resource consumption in multicast reservation styles
Authors: Mitzel Danny J. , Shenker Scott
Published: October 2004

The goal of network design is to meet the needs of resident applications in an efficient manner. Adding real-time service and point-to-multipoint multicast routing to the Internet's traditional point-to-point best effort service model will greatly increase the Internet's efficiency in handling point-to-multipoint real-time applications. Recently, the RSVP resource reservation protocol has introduced the concept of “reservation styles”, which control how reservations are aggregated in multipoint-to-multipoint real-time applications. In this paper, which is an extension of [9], we analytically evaluate the efficiency gains offered by this new paradigm on three simple network topologies: linear, m-tree, and star. We compare the resource utilization of more traditional reservation approaches to the RSVP reservation styles in the asymptotic limit of large multipoint applications. We find that in several cases the efficiency improvements scale linearly in the number of hosts.
Design and implementation of a configurable mixed-media file system
Authors: Maffeis Silvano
Published: October 2004

In this paper we describe the design and implementation of a configurable mixed-media file system. The attribute
configurable
means that a file system serving a specific application area can be realized out of a library of reusable file system classes. The attribute
mixed-media
stands for the file system's ability to integrate different media types (RAM, harddisks, WORM optical disks, CDROMs, tape devices, RAIDs etc.) into a virtual storage, and making applications unaware of this aggregation. A prototype C++ implementation of the proposed design, called the V
ANILLA
file system, is presented and its performance assessed. Raw-write performance is up to 4.5 times higher than in a standard Sun OS file system. We will also demonstrate how various storage organization forms, especially hierarchies, arrays, and mirrors of both local and remote storages, can be realized using the proposed file system class library.
Response to a note on structured interrupts
Authors: Hills Ted
Published: October 2004

In
Structured Interrupts
[2] I propose a machine-independent mechanism for handling hardware and software interrupts. In
A Note on Structured Interrupts
[1], Pradeep Hatkanagalekar points out several inadequacies in the model I proposed in
Structured Interrupts
, and suggests solutions. I concur with most of his suggestions, but differ with the last.
Trace
Authors: Spinellis Diomidis
Published: October 2004

A log of operating system calls made by a process can be used for debugging, profiling, verification and reverse engineering. Such a log can be created by acting as an intermediary between the traced process and the operating system. We describe the design and implementation of such a tool under the MS-DOS operating system environment, and provide some examples of its uses.
A model of user information satisfaction
Authors: Shirani Ashraf , Aiken Milam , Reithel Brian
Published: October 2004

Previous investigations of the User Information Satisfaction construct have approached the definition of satisfaction from a narrow perspective. The focus was primarily on the attributes of the system, with scant attention paid to the attributes of the user or of the organizational context in which system usage occurs. This article presents an alternative model of user information satisfaction that explains satisfaction as a consequence of the combination of user, organizational, and system characteristics. User and organizational characteristics combine to create a set of preimplementation expectations regarding the information system. After implementation, the gap between the actual system characteristics and the expected characteristics forms the basis for confirmation/disconfirmation of the expectations. It is the type and degree of confirmation/disconfirmation that forms the basis for User Information Satisfaction. The inclusion of user expectations in the model provides a new approach to understanding the variables and processes that lead to user information satisfaction.
AMS formalism
Authors: Ang James S. K. , Hong Jianz
Published: October 2004

The Activity Manager System (AMS) formalism anchored on key concepts such as activity, action, activity network, state, and MOPA (Memory Organization Packets for Activities) is capable of modeling a broad spectrum of office activities, ranging from the structured to the ill-structured, in a rigorous and comprehensive manner. The formalism can also be used to guide the development of Office Information Systems (OISs). It is domain independent and is particularly suited for the hierarchical representation of procedural knowledge. The formalism has the following features: 1) As in the rule-based formalism, control is separated from knowledge, and programming is replaced by the explicit, declarative representation of packets of knowledge; 2) Using the activity network concept, we can obtain an explicit hierarchical representation of procedural knowledge; 3) The activity concept provides the formalism with a representation of a rule-like entity; and 4) The MOPA concept plays the role of organizing and reconstructing knowledge in an appropriate manner, and allows the dynamic generation of Activity Networks at various levels of abstraction. The formalism as a theoretical underpinning for the development of OISs has been demonstrated at Bull's Advanced Studies Laboratory by Ader (in developing the office model) and Li (in developing the AMS).
Interactive control restructuring
Authors: Bruno Jeanette M. , Rosenkrantz Daniel J.
Published: October 2004

An interactive algorithm for improving control flow is introduced. This algorithm has been implemented within the ENCORE re-engineering environment. The objective of the algorithm is to restructure input code so as to simplify the control flow. A key feature of the algorithm is that is permits user control during the restructuring. The algorithm also handles, in a natural manner, multiple return statements, multiple loop exits, multi-level loop exits and endless loops.
A programmable network interface for a message-based multicomputer
Authors: Singh Raj K. , Tell Stephen G. , Bharrat Shaun J.
Published: October 2004

As fiber-optic gigabit networks are being deployed, supercomputer network interfaces are becoming the communication bottleneck. The Network Interface Unit (NIU) is a high-performance network interface for Pixel Planes 5, a custom, message-based multicomputer. The design offers both performance and programmability through a balance of data-handling in hardware an embedded processor. In this paper, we describe the NIU hardware and firmware architecture. We present results of performance measurements and assess the applicability of this design for the targeted environment. We also comment on its suitability for other environments and outline plans for the future work.
Semi-membership algorithms
Authors: Denny-Brown Derek , Han Yenjo , Hemaspaandra Lane A. , Torenvliet Leen
Published: October 2004

A semi-membership algorithm for a set
A
is, informally, a program that when given any two strings determines which is logically more likely to be in
A
.
A
flurry of interest in this topic in the late seventies and early eighties was followed by a relatively quiescent half-decade. However, in the 1990s there has been a resurgence of interest in this topic. We survey recent work on the theory of semi-membership algorithms.
Two-way one-counter automata accepting bounded languages
Authors: Petersen H.
Published: October 2004

We show that languages such as
&Ltilde;
= {0

n

1

n
2

|
n
≥ 1} and
&Lcirc;
= {0

n

1

2

n

|
n
≥ 1} can be accepted by deterministic two-way one-counter automata.
The quasilinear isomorphism challenge
Authors: Regan Kenneth W. , Wang Jie
Published: October 2004

We show that all the basic facts about the Berman-Hartmanis Isomorphism Conjecture carry over from polynomial to quasilinear time bounds. However, we show that the connection between unique-accepting NTMs and one-way functions, which underlies much subsequent work on the B-H conjecture, breaks down for quasilinear time under relativizations. Hence we have a whole new ballgame, on a tighter playing field.
EDUCATION FORUM: Project Impact:
Authors: Ross Rocky
Published: October 2004

During the academic year it is sometimes difficult to find the inspiration to write this column because of the many other pressing responsibilities we all face as faculty. But to even remember the due date of the next installment gets tough in July when one is standing in the middle of a mountain river, fly rod in hand, relishing the cool mountain air and the clear, rushing water. Ah, well, here goes...
Annotated bibliography on Distributed Queue Dual Bus (DQDB)
Authors: Sadiku Matthew N. O. , Arvind A. S.
Published: October 2004

Since its adoption in November 1987 by the IEEE 802.6 committee, the distributed-queue dual-bus (DQDB) subnetwork has generated a significant interest due to the simplicity of its medium access control protocol. This intense interest has lead to a literature explosion on DQDB. This paper is an attempt to provide both the veteran and the beginners with an annotated bibliography of related papers on DQDB.
Annotated bibliography on network management
Authors: Znaty Simon , Sclavos Jean
Published: October 2004

This annotated bibliography covers the various aspects of network management. It contains a list of papers being ordered according to the four network management models, namely, functional, architectural, informational and relational.
Data traffic in a new centralized switch node architecture for LAN
Authors: Khalil Ehab A. , Khalid M. , Kekre H. B.
Published: October 2004

A new switch-node architecture for data traffic for integrated services in a Local Area Network (LAN) is proposed. Specifically it has been designed to provide service to the following two broad types of traffic:1. Connectionless service for Interactive Data (ID) traffic.2. Connection-oriented service for Non-Interactive Data (NID) traffic.The topology of the switch-node is a bus. The key feature of the proposed scheme is the
centralization
, which has been exploited to provide the requisite flexibility for handling every class of traffic. The shared transmission medium is a short high speed bus which enjoys a fundamental advantage relative to distributed approaches in that the propagation delay along the length of the bus is smaller than the transmission time of a single bit. This feature can be exploited to provide simplicity and efficiency in accessing the transmission medium. The performance of the proposed media-access scheme and the centralized scheduling policy for interactive and non-interactive data traffics have been analyzed through simulation. The simulation study shows the actual efficiency of the switch-node, and proves that the proposed concurrent dual buses switch-node architecture with its centralized scheduling policy is a strong candidate to form the core of an efficient ISDN.
Design features of high level layers in LAHNOS, a local area heterogeneous network operating system
Authors: Aguirre G. , Errecalde M. , Esquivel S. , Leguizamon G. , Gallard R.
Published: October 2004

This paper describes the kernel and user interface designs of a Network Operating System for a Local Heterogeneous Area Network. The main goal of the project is to create a kernel to manage the distribution of a restricted set of functions or services between the network nodes, allowing portability of these functions within machine and Operating Systems heteregeneities upon which the kernel is built.Facing the problem throughout the Object and Client-Server Paradigms we attempt to provide the user with a dynamic availability of, till now isolated, resources by means of a user-friendly interface.
The system architecture of the Heidelberg transport system
Authors: Wolf Lars C. , Herrtwich R. G.
Published: October 2004

HeiTS, the Heidelberg Transport System, is designed for communication of continuous-media data. The purpose of HeiTS is the exchange of digital audio and video with quality of service guarantees. The system environment of HeiTS has to coordinate real-time and non-real-time functions. Most parts of HeiTS run in user space; it uses some kernel-based mechanisms such as a real-time CPU scheduler and device drivers. On top of HeiTS exists a control system which allows for the construction of applications controlling continuous-media streams. This paper describes the architecture of HeiTS and the mechanisms of its system environment we have implemented on AIX and OS/2 platforms.
FTP access as a user-defined file system
Authors: Gschwind Michael K.
Published: October 2004

Current methods of accessing services provided in the internet require users to know several interfaces. We show that integrating these services into the file naming spaces brings considerable benefits: users are able to use different services by a simple file access. This mechanism is general enough so that all applications can use the available services. Our idea is demonstrated by the implementation of a file server which handles ftp access transparently. This server was integrated into the regular file name space by using the NFS interface, thus avoiding the need to relink the kernel and ensuring portability.
A note on
structured interrupts
Authors: Hatkanagalekar Pradeep
Published: October 2004

In "Structured Interrupts" Ted Hills[3] proposed a framework to model interrupts so that the traditional
machine dependent
Interrupt-Handling can be analyzed in a
machine independent
fashion. In this paper we point out certain faults/inadequacies in the proposed model and suggest modifications to it take care of the same.
Comparing data synchronization in Ada 9X and Orca
Authors: Bal Henri E.
Published: October 2004

Protected object types are one of three major extensions to Ada 83 proposed by Ada 9X. This language feature is intended for light-weight data synchronization between tasks. The Orca parallel programming language has a very similar construct, the shared data-object, with which we have over five years of experience, both in usage and implementation. This paper compares protected objects and shared data-objects, with regard to design, usage, and implementation.
Translation of the protected type mechanism in Ada 83
Authors: Ledru Pascal
Published: October 2004

Several features of the Ada 94 language are useful to improve the efficiency of Ada programs. Especially the protected type mechanism is useful to improve the efficiency of concurrent Ada programs sharing common data structures. In order to facilitate the transition to Ada 94 before Ada 94 compilers are widely available, this paper proposes the use of an adapter which can be either a methodology, or an automatic translator. The adapter accepts source including protected objects and produces Ada 83 source. The results of several tests show that the performances of concurrent programs can be dramatically improved by using protected objects.
Workshop on mobile computing systems and applications, December 1994
Authors: Satyanarayanan M.
Published: October 2004

The goal of this two-day meeting was to foster interaction between active workers in mobile computing, with a view toward cross-fertilization of ideas. Given the youth of the field, such interactions could have substantial impact on its future direction. In keeping with this goal, the conference organizers chose to have a small, informal workshop rather than a larger and more formal conference. The workshop was sponsored by the IEEE Computer Society Technical Committee on Operating Systems, in cooperation with ACM SIGOPS and USENIX.The workshop was held on Thursday and Friday December 8-9 1994 at the Dream Inn in Santa Cruz. The weather was beautiful and the oceanside locale spectacular --- alas, it is not clear whether these helped or hindered the workshop, since many longing looks were evident on the faces of participants as they gazed out of the windows! The General Chair, Darrell Long, had done an excellent job of selecting the workshop site and setting the stage for the workshop. He was assisted in local arrangements by two student volunteers, Jim Cummiskey and Chane Fullmer.What follows is a summary of the discussions that took place during the workshop. It is based on notes taken by four student volunteers (Peter Grillo, C.K. Toh, Adrian Friday, and N. Asokan). They did an excellent job of taking detailed and complete notes. Any errors or omissions in this document are certainly my responsibility, not theirs.This digest is intended to be a supplement to the papers in the proceedings, not a substitute. Rather than producing a verbatim transcript, I've tried to focus on those interactions that seemed most insightful, controversial or evoked most response from the audience. Such a report must, by its very nature, be subjective. I've tried to be as objective as possible, but I'm sure there are places where my personal biases show through. My apologies in advance if you attended the workshop and your favorite comment, question or discussion isn't mentioned here.
Interrupts as threads
Authors: Kleiman Steve , Eykholt Joe
Published: October 2004

Most operating system implementations contain two fundamental forms of asynchrony; processes (or equivalently, internal threads) and interrupts. Processes (or threads) synchronize using primitives such as mutexes and condition variables, while interrupts are synchronized by preventing their occurrence for a period of time. The latter technique not only is expensive, but it locks out interrupts on the possibility that an interrupt will occur and interfere with the particular critical section of code that was interrupted.In the Solaris 2 implementation of UNIX [Eykholt 92] [Kleiman 92], these two forms are unified into a single model, threads. Interrupts are converted into threads using a low overhead technique. This allows a single synchronization model to be used throughout the kernel. In addition, it lowers the number of times in which interrupts are locked out, it removes the overhead of masking interrupts, and allows modular code to be oblivious to the interrupt level it is called at.
Reducing disk power consumption in a portable computer
Authors: Klostermeyer William F. , Srinivas Kankanahalli
Published: October 2004

The problem of minimizing disk power consumption in portable personal computers is studied. Two online algorithms for determining when to stop spinning a disk are presented and analyzed using competitive analysis techniques.
An object-oriented file system—an example of using the class hierarchy framework concept
Authors: Smolik Tomas
Published: October 2004

This paper presents the design of an object-oriented file system which was developed as a part of the "OBJIX Object-Oriented Operating System" project. The file system is a self-contained program system which is decomposed using a standard object-oriented framework concept. A novel approach to object-oriented frameworks, the Class Hierarchy Framework concept recapitulated in this paper, is employed in structuring components of the file system. Further, this paper illustrates on an example how the file system pursues a typical system call.
Migration of processes, files, and virtual devices in the MDX operating system
Authors: Schrimpf Harald
Published: October 2004

Load management in distributed systems is usually focused on balancing process execution and communication load. Stress on storage media and I/O-devices is considered only indirectly or disregarded. For I/O-intensive processes this imposes severe restrictions on balancing algorithms: processes have to be placed relative to fixed allocated resources. Therefore, beyond process migration, there is a need for a migration of all operating system objects, like files, pipes, timers, virtual terminals, and print jobs. In addition to new options for balancing cpu loads, this also makes it possible to balance the loads associated with these objects like storage capacity or I/O-bandwidth.This paper presents a concept for a general migration of nearly all operating system objects of a UNIX environment. The migrations of these objects work all in the same UNIX compliant and transparent manner. Objects can be moved throughout a distributed system independently of each other and at any time, according to a user defined policy. The migration mechanism is implemented as part of the MDX operating system; we present performance measurements. We believe that most of the mechanism can also apply to other message-passing based distributed operating systems.
A quasi-optimal cluster allocation strategy for parallel program execution in distributed systems using genetic algorithms
Authors: Esquivel S. , Leguizamon G. , Gallard R.
Published: October 2004

This paper shows an approach to find quasi-optimal solutions to the first optimization stage of parallel program tasks allocation problem, in an internet distributed system. The user initiates program execution from an arbitrary node in an arbitrary cluster, the parallel tasks comprising the program migrate to quasi-optimal clusters using an strategy that tries to minimize intercluster traffic of the parallel program execution.Genetic algorithms (GAs) [11] are used to provide a set of timely, quasi-optimal solutions.
An intelligent dynamic load balancer for workstation clusters
Authors: Ju Jiubin , Xu Gaochao , Yang Kun
Published: October 2004

A key issue of dynamic load balancing in a loosely couple distributed system is selecting appropriate jobs to transfer. In this paper, a job selection policy based on on-line predicting behaviors of jobs is proposed. Tracing is used at the beginning of execution of a job to predicate the approximate execution time and resource requirements of the job to make a correct decision about whether transferring the job is worthwhile. A dynamic load balancer using the job selection policy has been implemented. Experimental measurement results show that it is able to improve mean response time of jobs and resource utilization of systems substantially compared with the one without selecting job policy.
New directions for integrated circuit cards operating systems
Authors: Paradinas Pierre , Vandewalle Jean-Jacques
Published: October 2004

Integrated circuit cards or smart cards are now well-known. Applications such as electronic purses (cash units stored in cards), subscriber identification cards used in cellular telephone or access keys for pay-TV and information highways emerge in many places with millions of users. More services are required by applications providers and card holders. Mainly, new integrated circuit cards evolve towards non-predefined multi-purpose, open and multi-user applications. Today, operating systems implemented into integrated circuit cards cannot respond to these new trends. They have evolved from simple operating systems defining an hardware abstraction level up to file management systems or database management systems where the card behavior was defined once at the manufacturing level or by the card issuer. The needs for open and flexible card life cycle enabling to accommodate executable code loaded by different service providers require a new generation of smart cards. Operating systems based on object-oriented technologies are key components for future integrated circuit cards applications.
On group communication in large-scale distributed systems
Authors: Babaoğlu Özalp , Schiper André
Published: October 2004

An increasing number of applications with reliability requirements are being deployed in distributed systems that span large geographic distances or manage large numbers of objects. We consider the process group mechanism as an appropriate application structuring paradigm in such large-scale distributed systems. We give a formal characterization for the attribute "large scale" as applied to distributed systems and examine the technical problems that need to be solved in making group technology scalable. Our design advocates multiple roles for group membership over a minimal set of abstractions and primitives. The design is currently being implemented on top of "off-the-shelf" technologies for both communication and computation.
SPIN
—an extensible microkernel for application-specific operating system services
Authors: Bershad Brian N. , Chambers Craig , Eggers Susan , Maeda Chris , McNamee Dylan , Pardyak Przemysław , Savage Stefan , Sirer Emin Gün
Published: October 2004

Application domains such as multimedia, databases, and parallel computing, require operating system services with high performance and high functionality. Existing operating systems provide fixed interfaces and implementations to system services and resources. This makes them inappropriate for applications whose resource demands and usage patterns are poorly matched by the services provided. The
SPIN
operating system enables system services to be defined in an application-specific fashion through an
extensible
microkernel. It offers applications fine-grained control over a machine's logical and physical resources through run-time
adaptation
of the system to application requirements.
Address space sparsity and fine granularity
Authors: Liedtke Jochen
Published: October 2004

To fully exploit the potential of large address spaces, e.g. 2
64
-byte, the sparsity problem has to be solved in an efficient manner. Current address translation schemes either cause enormous space overhead (page table trees) or do not support address space structuring, object grouping and mixed page sizes (inverted page tables). Furthermore, an essential handicap of current virtual address spaces is their coarse granularity. It restricts the concept's relevance to low level OS technology. Without this constraint, mapping could be a vertically integrating paradigm, useful on all levels from hardware up to application programming.Guarded page tables help solving both problems. They permit significant extensions of the current programming model without performance degradation: sparse occupation and coarse-grain (4K) pages can be handled by purely conventional hardware; fine-grain (down to 16-byte) pages without fine-grain aliasing become also possible using conventional cache and TLB technology combined with stochastically colored allocation. Unrestricted aliasing and unlimited user level mapping without performance degradation may become possible by hardware innovation.
Objects to the rescue! or
httpd
: the next generation operating system
Authors: Black Andrew P. , Walpole Jonathan
Published: October 2004

This position paper suggests that object-oriented operating systems may provide the means to meet the ever-growing demands of applications. As an example of a successful OOOS, we cite the http daemon. To support the contention that
httpd
is in fact an operating system, we observe that it implements uniform naming, persistent objects and an invocation meta-protocol, specifies and implements some useful objects, and provides a framework for extensibility.We also believe that the modularity that is characteristic of OO systems should provide a performance benefit rather than a penalty. Our ongoing work in the Synthetix project at OGI is exploring the possibilities for advanced optimizations in such systems.
Computational geometry column 26
Authors: O'Rourke Joseph
Published: October 2004

An advance on Conway's thrackle conjecture is described.
Two recent algorithms for the global minimum cut problem
Authors: Subramanian Ashok
Published: October 2004

This article provides a self-contained exposition of two recent algorithms for the Global Minimum Cut problem. In this problem, we are given an undirected graph with positive weights on its edges, and we seek a proper subset
S
of the vertices that minimizes the total weight of all edges that have exactly one endpoint in
S
. Unlike traditional approaches to this problem, the new algorithms are not based on network flow computations. Instead they are based on a decomposition of the weighted graph into a sequence of weighted forests. The decomposition is used to identify a light set of edges that contains every light cutset of the graph. In general, such a decomposition requires too much space (and hence time) to write down. However, there is an efficient graph search procedure, Maximum Adjacency Search, that can be used to compute an implicit representation of such a decomposition in
O
(
m
+
n
log
n
) time.The first algorithm we discuss, due to Nagamochi and Ibaraki [5, 6], requires
O
(
n
) invocations of Maximum Adjacency Search to compute a global minimum cut. The second algorithm, due to Matula [4], requires
O
(log
n
) invocations of Maximum Adjacency Search to compute an approximately minimum cut. We do not discuss here the randomized algorithms of Karger or the matroid-based approach of Gabow.
A survey of linear programming in randomized subexponential time
Authors: Goldwasser Michael
Published: October 2004

Three papers were published in 1992, each providing a combinatorial, randomized algorithm solving linear programming in subexponential expected time. Bounds on independent algorithms were proven, one by Kalai, and the other by Matousek, Sharir, and Welzl. Results by Gärtner combined techniques from these papers to solve a much more general optimization problem in similar time bounds.Although the algorithms by Kalai and Sharir-Welzl seem remarkably different in style and evolution, this paper demonstrates that one of the variants of Kalai's algorithm is identical (although dual) to the algorithm of Sharir-Welzl. Also the implication of Gärtner's framework on future improvements is examined more carefully.
Computational geometry
Authors: O'Rourke Joseph
Published: October 2004

The recent breakthrough of Halperin and Sharir on the complexity of lower envelopes of surfaces is described.
Nomadic computing—an opportunity
Authors: Kleinrock Leonard
Published: October 2004

We are in the midst of some truly revolutionary changes in the field of computer-communications, and these offer opportunities and challenges to the research community. One of these changes has to do with nomadic computing and communications. Nomadicity refers to the system support needed to provide a rich set of capabilities and services to the nomad as he moves from place to place in a transparent and convenient form. This new paradigm is already manifesting itself as users travel to many different locations with laptops, PDA's, cellular telephones, pagers, etc. In this paper we discuss some of the open issues that must be addressed as we bring about the system support necessary for nomadicity. In addition, we present some of the considerations with which one must be concerned in the area of wireless communications, which forms one (and only one) component of nomadicity.
The ALOHA System
Authors: Kuo F. F.
Published: October 2004

THE ALOHA SYSTEM is composed of a related series of contracts and grants from a variety of funding agencies with principal support from ARPA, which deal with two main themes: computer communications (TASK 1), and computer structures (TASK 2).Under computer-communications there is work in (a) Studies on computer communications using radio and satellites, (b) The development of a prototype radio-linked time-sharing network, (c) System studies and planning for a Pacific area computer communications network linking major universities in the U.S., Japan, Australia and other Pacific countries.Under computer structures, we are engaged in research/development in multiprocessor computing structures, computer networks, and geographically distributed computing systems. This work is being undertaken in two phases: 1) the establishment of a research facility and 2) the research work itself. The research facility is centered around the BCC 500 computing system.
Selecting sequence numbers
Authors: Tomlinson Raymond S.
Published: October 2004

A characteristic of almost all communication protocols is the use of unique numbers to identify individual pieces of data. These identifiers permit error control through acknowledgement and retransmission techniques. Usually successive pieces of data are identified with sequential numbers and the identifiers are thus called sequence numbers.This paper discusses techniques for selecting and synchronizing sequence numbers such that no errors will occur if certain network characteristics can be bounded and if adequate data error detection measures are taken. The discussion specifically focuses on the protocol described by Cerf and Kahn
(1),
but the ideas are applicable to other similar protocols.
Improving round-trip time estimates in reliable transport protocols
Authors: Karn Phil , Partridge Craig
Published: October 2004

As a reliable, end-to-end transport protocol, the ARPA Transmission Control Protocol (TCP) uses positive acknowledgements and retransmission to guarantee delivery. TCP implementations are expected to measure and adapt to changing network propagation delays so that its retransmission behavior balances user throughput and network efficiency. However, TCP suffers from a problem we call
retransmission ambiguity
: when an acknowledgment arrives for a segment that has been retransmitted, there is no indication which transmission is being acknowledged. Many existing TCP implementations do not handle this problem correctly.This paper reviews the various approaches to retransmission and presents a novel and effective approach to the retransmission ambiguity problem.