bluuebunny/crossref_metadata_2025 huggingface dataset:
Document generation using ASIS tools
Authors: Hovater Steven V.
Published: October 2004

The Ada Semantic Interface Specification offers a unique capability to Ada development projects: the ability to construct tools that navigate through the semantic network formed by one's compiled code. In particular, producing accurate documentation based upon existing source code is a possibility; if one can identify the composite types that act as messages between different parts of one's system, then it is entirely feasible to generate an interface description document based upon the actual content of the code, thus automating what has been historically, a tedious process. …
Computational geometry column 40
Authors: O'Rourke Joseph
Published: October 2004

It has recently been established by Below, De Loera, and Richter-Gebert that finding a minimum size (or even just a small) triangulation of a convex polyhedron is NP-complete. Their 3SAT-reduction proof is discussed.
Review of: Modern Graph Theory by Béla Bollobás
Authors: Čenek E. W
Published: October 2004

Graph Theory is still a relatively young subject, and debate still rages on what material constitutes the core results that any introductory text should include. Bollobás has chosen to introduce graph theory - including recent results - in a way that emphasizes the connections between (for example) the Tutte polynomial of a graph, the partition functions of theoretical physics, and the new knot polynomials, all of which are interconnected.On the other hand, graph theory is also rooted strongly in computing science, where it is applied to many different problems; Bollobás's treatment is completely theoretical and does not address these applications. Or, in more practical terms, he is concerned whether a solution exists, rather than asking whether the solution can be computed in a reasonably efficient manner.One of the pleasures of working in graph theory is the abundance of problems available to solve. Unlike many more traditional areas of Mathematics, knowing the core results and proofs is frequently insufficient. Often solving a new problem requires a new approach, or a subtle twist on an existing one, combined with some bare knuckle work. Bollobás emphasizes this in the problems available at the end of each chapter; he includes in total 639 problems, ranging from the reasonably straightforward to the very difficult. I spent time with friends working on these problems, and was intrigued by the variety of the proofs that we came up with.
Comments on “An approach to the formal verification of the two-party crytographic protocols” by Zhang, Li and Xiao
Authors: Ji Dongyao , Wang Yuming
Published: October 2004

We show that the method proposed by Zhang, Li and Xiao in [2] is not a general method for verifying the two-party cryptographic protocols.
Causal consistency in mobile environment
Authors: Ram D. Janaki , Mahesh M. Uma , Chandra Sekhar N. S. K. , Babu Chitra
Published: October 2004

Causal consistency stipulates that causally dependent writes to data items should be executed in causal order. Traditionally this has been done by causally ordered message delivery using vector clocks. In a vector clock of size N, each element of the vector corresponds to each of the N hosts in the system and hence the message overhead is Θ(
N
). In a mobile environment the number of hosts can not be fixed because hosts join and leave the system dynamically. Hence traditional vector clocks are not suitable in a mobile environment. Consistency of a system consisting of M data items can be maintained using a vector in which each element corresponds to each data item. We propose a mechanism for maintaining causal consistency whose message overhead is Θ(
M
). Such a model will be advantageous in a mobile environment, because the message overhead is independent of the number of hosts. Further in applications such as collaboration the number of data items is small. Also, the delivery of a message is never inhibited due to causally overwritten messages.
Ordered Multicast and Distributed Swap
Authors: Herlihy Maurice , Tirthapura Srikanta , Wattenhofer Rogert
Published: October 2004

A multicast protocol is
ordered
(or
totally ordered
) if it ensures that messages multicast to a group of nodes are delivered in the same order at each destination node, even when those messages are generated concurrently from several sources. Ordered multicast is a natural foundation for push-based cache coherence and certain kinds of middleware.This paper shows how to reduce the complex problem of enforcing multicast ordering to a simpler distributed coordination problem we call
distributed swap.
Any distributed swap protocol can transform an unordered reliable multicast into an ordered multicast in a modular way.We introduce two novel distributed swap protocols, and discuss their corresponding ordered multicast protocols. These protocols have lower latency than more obvious approaches based on distributed counting.
Session
Authors: Asplund Lars
Published: October 2004

The session, named
New Scheduling and Dispatching Policies
, was chaired by Juan de la Puente and covered a couple of new scheduling policies. A Non-Preemptive dispatching policy was proposed by Alan Burns. A suggestion to have per-task dispatching policies was presented by Michael González Harbour, where the per-task policies could be one of FIFO_Within_Priorities, Round_Robin_With_Priorities, or Sporadic_Server. Michael also proposed adding CPU-time budgeting capabilities to the language.
Session summary
Authors: Harbour Michael González , Pinho Luis Miguel
Published: October 2004

The objective of this session was to discuss aspects related to the integration of real-time and distribution capabilities in Ada. Special focus was given to:- the integration of the Real-Time and Distributed Systems Annexes;- Ravenscar and Distributed Systems.
Report of session
Authors: Dobbing Brian , Vardanega Tullio
Published: October 2004

As a `first' in the history of IRTAW, the workshop devoted a full session to the analysis of the real-time extensions currently proposed for a mainstream language in direct competition with Ada, that is Java. The objective of the session was to offer the group the opportunity to reflect on the status and rationale of the latest definition of the real-time extensions promulgated by the J Consortium. A subsequent IRTAW session addressed the analysis of the real-time extensions defined by the Real-Time Expert Group led by Sun Microsystems.
Implementation of mode changes with the Ravenscar profile
Authors: Alonso Alejandro , Antonio de la Puente Juan
Published: October 2004

The use of concurrency in the development of safety-critical systems has not been recommended for a long time. Recently, a safe Ada tasking subset has been defined, known as the Ravenscar Profile. The imposed restrictions invalidated most of the proposed implementations for dealing with mode changes.In this paper, it is described an implementation approach for mode changes, that is compliant with the Ravenscar Profile. It relies on the decoupling between jobs and tasks and on centralizing tasks activations in a system manager. The proposed ideas have been tested with the ORK, which is a kernel integrated with the GNAT compiler for developing and executing applications that follow the Ravenscar Profile.
Non-preemptive dispatching and locking policies
Authors: Burns Alan
Published: October 2004

In this short paper two new pragmas are introduced and defined. Together they allow non-preemptive scheduling to be specified for Ada Programs. The syntax, rules and dynamic semantics for the scheme are described. Use is made of an additional execution resource --- the execution-token.
Time warp operating system
Authors: Jefferson D. , Beckman B. , Wieland F. , Blume L. , Diloreto M.
Published: October 2004

This paper describes the Time Warp Operating System, under development for three years at the Jet Propulsion Laboratory for the Caltech Mark III Hypercube multi-processor. Its primary goal is concurrent execution of large, irregular discrete event simulations at maximum speed. It also supports any other distributed applications that are synchronized by virtual time.

The Time Warp Operating System includes a complete implementation of the Time Warp mechanism, and is a substantial departure from conventional operating systems in that it performs synchronization by a general distributed process rollback mechanism. The use of general rollback forces a rethinking of many aspects of operating system design, including programming interface, scheduling, message routing and queueing, storage management, flow control, and commitment.

In this paper we review the mechanics of Time Warp, describe the TWOS operating system, show how to construct simulations in object-oriented form to run under TWOS, and offer a qualitative comparison of Time Warp to the Chandy-Misra method of distributed simulation. We also include details of two benchmark simulations and preliminary measurements of time-to-completion, speedup, rollback rate, and antimessage rate, all as functions of the number of processors used.
Implementation of Argus
Authors: Liskov B. , Curtis D. , Johnson P. , Scheifer R.
Published: October 2004

Argus is a programming language and system developed to support the construction and execution of distributed programs. This paper describes the implementation of Argus, with particular emphasis on the way we implement atomic actions, because this is where Argus differs most from other implemented systems. The paper also discusses the performance of Argus. The cost of actions is quite reasonable, indicating that action systems like Argus are practical.
Log files: an extended file service exploiting write-once storage
Authors: Finlayson R. , Cheriton D.
Published: October 2004

A log service provides efficient storage and retrieval of data that is written sequentially (append-only) and not subsequently modified. Application programs and subsystems use log services for recovery, to record security audit trails, and for performance monitoring. Ideally, a log service should accommodate very large, long-lived logs, and provide efficient retrieval and low space overhead.

In this paper, we describe the design and implementation of the Clio log service. Clio provides the abstraction of
log files
: readable, append-only files that are accessed in the same way as conventional files. The underlying storage medium is required only to be append-only; more general types of write access are not necessary. We show how log files can be implemented efficiently and robustly on top of such storage media—in particular, write-once optical disk.

In addition, we describe a general application software storage architecture that makes use of log files.

This work was supported in part by the Defense Advanced Research Projects Agency under contracts N00039-84-C-0211 and N00039-86-K-0431, by National Science Foundation grant DCR-83-52048, and by Digital Equipment Corporation, Bell-Northern Research and AT&T Information Systems.
A middleware toolkit for client-initiated service specialization
Authors: Eisenhauer Greg , Bustamante Fabián E. , Schwan Karsten
Published: October 2004

As the Internet matures, streaming data services are taking an increasingly important place alongside traditional HTTP transactions. The need to dynamically adjust the delivery of such services to changes in available network and processing resources has spawned substantial research on application-specific methods for dynamic adaptation, including video and audio streaming applications. Such adaptation techniques are well developed, but they are also highly specialized, with the client (receiver) and server (sender) implementing well-defined protocols that exploit content-specific stream properties. This paper describes our efforts to bring the benefits of such content-aware, application-level service adaptation to all types of streaming data and to do so in a manner that is efficient and flexible. Our contribution in this domain is ECho, a high-performance event-delivery middleware system. ECho's basic functionality provides efficient binary transmission of event data with unique features that support dynamic data-type discovery and service evolution. ECho's contribution to data stream adaptation is in the mechanisms it provides for its clients to customize their data flows through type-safe dynamic server extension.
View-based consistency and false sharing effect in distributed shared memory
Authors: Huang Z. , Sun C. , Purvis M. , Cranefield S.
Published: October 2004

This paper proposes a novel
View-based Consistency
model for Distributed Shared Memory. A view is a set of ordinary data objects that a processor has the right to access in a data-race-free program. The
View-based Consistency
model requires that the data objects of a
view
are made up-to-date only before a processor accesses them. Compared with other memory consistency models, the
View-based Consistency
model can achieve data selection without user annotation and reduce more false sharing effect.
Multimedia data storage and representation issues on tertiary storage subsystems
Authors: Vakali Athena , Terzi Evimaria
Published: October 2004

Storage of multimedia data is a critical issue for the overall system's performance and functionality. Multimedia applications must be able to support a variety of data defined as
multimedia objects.
Multimedia data consist of various objects such as text, image, video and graphics, which need to be synchronized and meet certain timing requirements. The development and evolution of these new applications characterized by high storage needs resulted in strengthening the role and importance of Tertiary Storage Systems. Recent technological advances have resulted in wide availability of commercial products offering near-line, robot-based, tertiary storage libraries. Therefore, such libraries have become an important component of modern large-scale storage servers. The issue of optimal data placement strategies in tertiary storage is considered below. Different configurations of tape libraries and magnetic tape technologies as well as the special attributes of stored data have an impact on the optimal placement.
Transparent checkpointing and rollback recovery mechanism for Windows NT applications
Authors: Zhang Youhui , Wang Dongsheng , Zheng Weimin
Published: October 2004

Clusters of industry-standard computers running Windows NT are emerging as a competitive alternative for large-scale parallel computing. However, clusters have increased susceptibility to failure especially when they contain many nodes. Therefore it is necessary to implement high availability on Windows NT. This paper introduces the Checkpoint and Rollback Recovery (CRR) mechanism on Windows NT and presents

WinNTCkpt,

a Checkpointing and recovery tool implemented by us.

WinNTCkpt

can be used to transparently checkpoint and recover applications running on Windows NT. To use this tool, user is only required to provide the application's executable code instead of source code.

WinNTCkpt

also provides a set of CRR APIs for users to construct applications with high availability. Owing to API interception and thread injection mechanisms,

WinNTCkpt

endows some existing applications with CRR functions.

WinNTCkpt

has been proved valid for Windows NT 4.0 and Windows 2000 applications.
Transport issues in the network file system
Authors: Nowicki Bill
Published: October 2004

The Sun Network File System (NFS) is a popular protocol to access files across a network [Sandberg 86]. NFS is implemented on machines as different as Personal Computers, and Cray-2 supercomputers. It uses Sun Remote Procedure Call [Sun 88] and External Data Representation [Sun 87] specifications, which can be used on a variety of transport protocols. The original design goal for NFS was to support small clusters of machines on local area networks. Thus a datagram protocol (UDP) was chosen to simplify transport.Using a connection-less transport protocol meant that nothing explicitly needed to be done to handle server or network failures. However, the use of NFS has expanded to cover much larger and more complicated networks than was ever anticipated. This has caused some NFS users to experience the problems of congestion and flow controI that transport protocols have been designed to address. This paper discucsses some alternatives for NFS transport protocols. Other issues such as inter-domain authentication, are not discussed here.
An overview of UNP
Authors: Peterson Larry L.
Published: October 2004

The paper gives a brief introduction to UNP: the Universal Naming Protocol. UNP specifies a generic
attribute-based
name server upon which a variety of high-level naming services---including white- and yellow-page services---can be built.
Notable abbreviations in telecommunications
Authors: Barz Hans W.
Published: October 2004

Two years ago I already published the first version of abbreviations - see [1]. Compared to the first edition the number of abbreviations has doubled.
An ISO TP4-TP0 Gateway
Authors: Landweber Lawrence H. , Tasman Mitchell , Yeong Wengyik
Published: October 2004

The ISO TP4 and TP0 transport layer protocols and associated network service paradigms cannot interoperate, yet both are likely to be in common use. To allow users of TP4 to communicate with users of TP0, transport layer gateways will be needed. This paper discusses several design alternatives, and describes a prototype gateway implementation.
Dynamical behavior of rate-based flow control mechanisms
Authors: Bolot Jean-Chrysostome , Shankar A. Udaya
Published: October 2004

Flow control mechanisms are essential for the efficient and stable operation of store-and-forward networks. New transport protocols, such as VMTP and NETBLT, intend to use rate-based flow control. We present a model in which a network with connections subject to rate-based flow control is considered as a dynamical system, i.e., a set of coupled differential equations. We consider two scenarios: (1) a single connection over a long delay path involving a bottleneck; and (2) two connections with different roundtrip delays that share a common bottleneck. For a recently proposed control scheme, we obtain closed-form solutions for the dynamical model in both transient and steady state regimes, and evaluate appropriate performance measures. We compare our results with those obtained by others using experimental and simulation approaches.
Axon
Authors: Sterbenz James P. G. , Parulkar Gurudatta M.
Published: October 2004

This paper describes the design of
network virtual storage
(NVS) in the Axon host communication architecture for distributed applications. The Axon project is investigating an integrated design of host architecture, operating systems, and communication protocols to allow applications to utilise the high bandwidth provided by the next generation of communication networks. N
VS
extends segmented paged virtual storage management and address translation mechanisms to include segments located across an internetwork. This provides the ability to efficiently use the shared memory paradigm in non-local environments, as well as the support for a very high speed end-to-end data path between demanding applications such as scientific visualisation and imaging.
Defense data network security architecture
Authors: Shirey Robert W.
Published: October 2004

The Department of Defense (DOD) is changing the security structure of the Defense Data Network. Existing classified backbones are merging to form a single segment. DISNET, that uses a new host - to - host encryption system. When completed, DISNET will carry classified data of all security levels, while MILNET continues to carry unclassified traffic. MILNET is being strengthened by link encryption devices on trunk and access lines. Subscriber computers and network elements in both DISNET and MILNET will have to satisfy at least Class C2 (Controlled Access Protection) of the DOD Trusted Computer System Evaluation Criteria. There are no similar plans for the Internet.
Network management capabilities for switched multi-megabit data service
Authors: Piscitello David M. , Sher Patrick J.
Published: October 2004

This paper discusses network management capabilities for a specific BOC data service, SMDS, and the role that a BOC network providing this service can play in the overall management strategy of a subscriber owned and operated data network. The paper describes user needs for managing the computing equipment and communications services that comprise a data network, and suggests several ways in which a BOC network could offer network management features that complement and are synergistic with the management practices applied in today's data networks. A set of candidate management information is discussed that could be offered by a BOC network providing SMDS to complement the base of information essential to maintaining the operational data network of the customer.
Access to a public switched multi-megabit data service offering
Authors: Dix F. R. , Kelly M. , Klessig R. W.
Published: October 2004

Switched Multi-megabit Data Service (SMDS) is a service concept resulting from work at Bell Communications Research. SMDS is a public, packet switched data service that provides LAN-like performance and features over a metropolitan or wide area. It is targeted at the rapidly emerging need for high performance LAN interconnection and deployment is expected in 1991. To meet the early time objectives of SMDS, it was necessary to define the Subscriber-Network Interface (SNI) and to specify the associated SMDS Interface Protocols (SIP) to facilitate the availability of both customer premises equipment (CPE) and network equipment. The interface and associated protocols are based on the connectionless part of the IEEE P802.6 DQDB MAN MAC proposed standard.
Internetworking using switched multi-megabit data service in TCP/IP enviroments
Authors: Piscitello David M. , Kramer Michael
Published: October 2004

TCP/IP based networks were among the earliest and most successful applications of Local Area Network technologies, and TCP/IP-based internets continue to be a testing ground for emerging high performance transmission technologies as well as the distributed processing applications they support. As distributed processing applications become increasingly available in the next decade, consumer demand for high performance transmission services will extend beyond the distance serviceable by LANs; users will want the same service from their long distance data networks as they get from local networks.Switched Multi-megabit Data Service (SMDS) is a public network service concept designed to satisfy these service requirements. Networks which support SMDS will provide a service analogous to Local Area Networks across metropolitan and eventually wide area distances. The features of SMDS reflect many of the characteristics that make communication via LANs attractive for existing and future distributed processing applications: large packet sizes, high bandwidth, low delay, and multi-cast addressing.This paper identifies the technological and economical factors which contributed first to the emergence of LAN and now MAN technologies, and in particular focuses on how SMDS might be used in TCP/IP environments. A brief description of SMDS is provided, followed by a study of the relationship between SMDS and the DOD Internet Model and a description of the ways in which the service could play a role in existing and future TCP/IP-based internets.
Connecting remote FDDI installations with single-mode fiber, dedicated lines, or SMDS
Authors: Lang, Bellcore Lawrence J. , Watson James , Services Ameritech
Published: October 2004

The Fiber Distributed Data Interface (FDDI) is emerging as an important ANSI standard for high-performance data networking. Many users will install FDDI at different sites, and then want to connect these installations while sacrificing as little performance as possible. This paper discusses several technically practical ways to connect remote FDDI installations, including: using FDDI as a metropolitan area network by extending with single-mode fiber or with a SONET mapping, using bridges or routers coupled with dedicated lines, and using bridges or routers connected with Switched Multi-megabit Data Service (SMDS).
Reprint from computing reviews
Authors: Loui Michael C.
Published: October 2004

As a service to our readers,
SIGACT News
has reached an agreement to reprint reviews that originally appeared in
Computing Reviews
of books and articles of interest to the theoretical computer science community.
Computing Reviews
is a monthly journal that publishes critical reviews on a broad range of computing subjects, including models of computation, formal languages, computational complexity theory, analysis of algorithms, and logics and semantics of programs. ACM members can receive a subscription to
Computing Reviews
for $32 per year by writing to ACM headquarters.
The journal review column
Authors: Parberry Ian
Published: October 2004

The journal review column is established to provide readers of
SIGACT News
with up-to-date information on journals and journal-like publications which carry articles of potential interest to theoretical computer scientists. It will include research, survey, review and "popular" publications, theory journals and applied journals, general journals and specialized journals, with the common thread being that they are receptive to theoretical computer science. The term "theoretical computer science" will be interpreted broadly.It is the intent of the column to inform, not to rank or in any way pass judgement on the quality of journals or the articles published therein. Journals to be reviewed include, but are not necessarily restricted to the list appearing in the first column (
SIGACT News
, Vol. 12, No. 3, pp. 27--28, 1989). Suggestions from readers of the column are welcome.
Separating data and control transfer in distributed operating systems
Authors: Thekkath Chandramohan A. , Levy Henry M. , Lazowska Edward D.
Published: October 2004

Advances in processor architecture and technology have resulted in workstations in the 100+ MIPS range. As well, newer local-area networks such as ATM promise a ten- to hundred-fold increase in throughput, much reduced latency, greater scalability, and greatly increased reliability, when compared to current LANs such as Ethernet.

We believe that these new network and processor technologies will permit tighter coupling of distributed systems at the hardware level, and that distributed systems software should be designed to benefit from that tighter coupling. In this paper, we propose an alternative way of structuring distributed systems that takes advantage of a communication model based on remote network access (reads and writes) to protected memory segments.

A key feature of the new structure, directly supported by the communication model, is the separation of
data transfer
and
control transfer
. This is in contrast to the structure of traditional distributed systems, which are typically organized using message passing or remote procedure call (RPC). In RPC-style systems, data and control are inextricably linked—all RPCs must transfer both data and control, even if the control transfer is unnecessary.

We have implemented our model on DECstation hardware connected by an ATM network. We demonstrate how separating data transfer and control transfer can eliminate unnecessary control transfers and facilitate tighter coupling of the client and server. This has the potential to increase performance and reduce server load, which supports scaling in the face of an increasing number of clients. For example, for a small set of file server operations, our analysis shows a 50% decrease in server load when we switched from a communications mechanism requiring both control transfer and data transfer, to an alternative structure based on pure data transfer.
Reactive synchronization algorithms for multiprocessors
Authors: Lim Beng-Hong , Agarwal Anant
Published: October 2004

Synchronization algorithms that are efficient across a wide range of applications and operating conditions are hard to design because their performance depends on unpredictable run-time factors. The designer of a synchronization algorithm has a choice of
protocols
to use for implementing the synchronization operation. For example, candidate protocols for locks include test-and-set protocols and queueing protocols. Frequently, the best choice of protocols depends on the level of contention: previous research has shown that test-and-set protocols for locks outperform queueing protocols at low contention, while the opposite is true at high contention.

This paper investigates reactive synchronization algorithms that dynamically choose protocols in response to the level of contention. We describe reactive algorithms for spin locks and fetch-and-op that choose among several shared-memory and message-passing protocols. Dynamically choosing protocols presents a challenge: a reactive algorithm needs to select and change protocols efficiently, and has to allow for the possibility that multiple processes may be executing different protocols at the same time. We describe the notion of
consensus objects
that the reactive algorithms use to preserve correctness in the face of dynamic protocol changes.

Experimental measurements demonstrate that reactive algorithms perform close to the
best
static choice of protocols at all levels of contention. Furthermore, with mixed levels of contention, reactive algorithms outperform passive algorithms with fixed protocols, provided that contention levels do not change too frequently. Measurements of several parallel applications show that reactive algorithms result in modest performance gains for spin locks and significant gains for fetch-and-op.
Integration of message passing and shared memory in the Stanford FLASH multiprocessor
Authors: Heinlein John , Gharachorloo Kourosh , Dresser Scott , Gupta Anoop
Published: October 2004

The advantages of using message passing over shared memory for certain types of communication and synchronization have provided an incentive to integrate both models within a single architecture. A key goal of the FLASH (FLexible Architecture for SHared memory) project at Stanford is to achieve this integration while maintaining a simple and efficient design. This paper presents the hardware and software mechanisms in FLASH to support various message passing protocols. We achieve low overhead message passing by delegating protocol functionality to the programmable node controllers in FLASH and by providing direct user-level access to this messaging subsystem. In contrast to most earlier work, we provide an integrated solution that handles the interaction of the messaging protocols with virtual memory, protected multiprogramming, and cache coherence. Detailed simulation studies indicate that this system can sustain message-transfers rates of several hundred megabytes per second, effectively utilizing projected network bandwidths for next generation multiprocessors.
Software overhead in messaging layers
Authors: Karamcheti Vijay , Chien Andrew A.
Published: October 2004

Despite improvements in network interfaces and software messaging layers, software communication overhead still dominates the hardware routing cost in most systems. In this study, we identify the sources of this overhead by analyzing software costs of typical communication protocols built atop the active messages layer on the CM-5. We show that up to 50–70% of the software messaging costs are a direct consequence of the gap between specific network features such as arbitrary delivery order, finite buffering, and limited fault-handling, and the user communication requirements of in-order delivery, end-to-end flow control, and reliable transmission. However, virtually all of these costs can be eliminated if routing networks provide higher-level services such as in-order delivery, end-to-end flow control, and packet-level fault-tolerance. We conclude that significant cost reductions require changing the constraints on messaging layers: we propose designing networks and network interfaces which simplify or replace software for implementing user communication requirements.
eNVy
Authors: Wu Michael , Zwaenepoel Willy
Published: October 2004

This paper describes the architecture of eNVy, a large non-volatile main memory storage system built primarily with Flash memory. eNVy presents its storage space as a linear, memory mapped array rather than as an emulated disk in order to provide an efficient and easy to use software interface.

Flash memories provide persistent storage with solid-state memory access times at a lower cost than other solid-state technologies. However, they have a number of drawbacks. Flash chips are write-once, bulk-erase devices whose contents cannot be updated in-place. They also suffer from slow program times and a limit on the number of program/erase cycles. eNVy uses a copy-on-write scheme, page remapping, a small amount of battery backed SRAM, and high bandwidth parallel data transfers to provide low latency, in-place update semantics. A cleaning algorithm optimized for large Flash arrays is used to reclaim space. The algorithm is designed to evenly wear the array, thereby extending its lifetime.

Software simulations of a 2 gigabyte eNVy system show that it can support I/O rates corresponding to approximately 30,000 transactions per second on the TPC-A database benchmark. Despite the added work done to overcome the deficiencies associated with Flash memories, average latencies to the storage system are as low as 180ns for reads and 200ns for writes. The estimated lifetime of this type of storage system is in the 10 year range when exposed to a workload of 10,000 transactions per second.
Avoiding conflict misses dynamically in large direct-mapped caches
Authors: Bershad Brian N. , Lee Dennis , Romer Theodore H. , Chen J. Bradley
Published: October 2004

This paper describes a method for improving the performance of a large direct-mapped cache by reducing the number of conflict misses. Our solution consists of two components: an inexpensive hardware device called a Cache Miss Lookaside (CML) buffer that detects conflicts by recording and summarizing a history of cache misses, and a software policy within the operating system's virtual memory system that removes conflicts by dynamically remapping pages whenever large numbers of conflict misses are detected. Using trace-driven simulation of applications and the operating system, we show that a CML buffer enables a large direct-mapped cache to perform nearly as well as a two-way set associative cache of equivalent size and speed, although with lower hardware cost and complexity.
LCM
Authors: Larus James R. , Richards Brad , Viswanathan Guhan
Published: October 2004

Higher-level parallel programming languages can be difficult to implement efficiently on parallel machines. This paper shows how a flexible, compiler-controlled memory system can help achieve good performance for language constructs that previously appeared too costly to be practical.

Our compiler-controlled memory system is called Loosely Coherent Memory (LCM). It is an example of a larger class of Reconcilable Shared Memory (RSM) systems, which generalize the replication and merge policies of cache-coherent shared-memory. RSM protocols differ in the action taken by a processor in response to a
request
for a location and the way in which a processor
reconciles
multiple outstanding copies of a location. LCM memory becomes temporarily inconsistent to implement the semantics of C** parallel functions efficiently. RSM provides a compiler with control over memory-system policies, which it can use to implement a language's semantics, improve performance, or detect errors. We illustrate the first two points with LCM and our compiler for the data-parallel language C**.
Reducing branch costs via branch alignment
Authors: Calder Brad , Grunwald Dirk
Published: October 2004

Several researchers have proposed algorithms for basic block reordering. We call these
branch alignment
algorithms. The primary emphasis of these algorithms has been on improving instruction cache locality, and the few studies concerned with branch prediction reported small or minimal improvements. As wide-issue architectures become increasingly popular the importance of reducing branch costs will increase, and branch alignment is one mechanism which can effectively reduce these costs.

In this paper, we propose an improved branch alignment algorithm that takes into consideration the architectural cost model and the branch prediction architecture when performing the basic block reordering. We show that branch alignment algorithms can improve a broad range of static and dynamic branch prediction architectures. We also show that a program performance can be improved by approximately 5% even when using recently proposed, highly accurate branch prediction architectures. The programs are compiled by any existing compiler and then transformed via binary transformations. When implementing these algorithms on a Alpha AXP 21604 up to a 16% reduction in total execution time is achieved.
DCG
Authors: Engler Dawson R. , Proebsting Todd A.
Published: October 2004

Dynamic code generation allows aggressive optimization through the use of runtime information. Previous systems typically relied on ad hoc code generators that were not designed for retargetability, and did not shield the client from machine-specific details. We present a system,
dcg
, that allows clients to specify dynamically generated code in a machine-independent manner. Our one-pass code generator is easily retargeted and extremely efficient (code generation costs approximately 350 instructions per generated instruction). Experiments show that dynamic code generation increases some application speeds by over an order of magnitude.
Fine-grain access control for distributed shared memory
Authors: Schoinas Ioannis , Falsafi Babak , Lebeck Alvin R. , Reinhardt Steven K. , Larus James R. , Wood David A.
Published: October 2004

This paper discusses implementations of fine-grain memory access control, which selectively restricts reads and writes to cache-block-sized memory regions. Fine-grain access control forms the basis of efficient cache-coherent shared memory. This paper focuses on low-cost implementations that require little or no additional hardware. These techniques permit efficient implementation of shared memory on a wide range of parallel systems, thereby providing shared-memory codes with a portability previously limited to message passing.

This paper categorizes techniques based on where access control is enforced and where access conflicts are handled. We incorporated three techniques that require no additional hardware into Blizzard, a system that supports distributed shared memory on the CM-5. The first adds a software lookup before each shared-memory reference by modifying the program's executable. The second uses the memory's error correcting code (ECC) as cache-block valid bits. The third is a hybrid. The software technique ranged from slightly faster to two times slower than the ECC approach. Blizzard's performance is roughly comparable to a hardware shared-memory machine. These results argue that clusters of workstations or personal computers with networks comparable to the CM-5's will be able to support the same shared-memory interfaces as supercomputers.
Approaches to the development of multi-dimensional databases
Authors: Hasan Helen , Hyland Peter , Dodds David , Veeraraghavan Raja
Published: October 2004

The paper explores the manner in which an organization's data and information can be effectively utilized to assist an organization to achieve its business objectives. With the increased popularity of data warehousing and executive information systems, there is renewed interest by IT practitioners in data models and database structures, in particular multi-dimensional forms, which have joined their relational counterparts as legitimate tools for extracting vital business information from an organization's operational data. As much of the current literature on multi-dimensional databases comes in the form of white papers from the creators of multi-dimensional systems, there is a need for a more objective and theoretical analysis of this area, particularly on aspects that concern application developers and end users. To this end, the paper presents an analysis of four case studies involving the development of multidimensional databases applications. The initial two cases used different approaches, one top-down and one bottom-up. The successful aspects of these cases were used to create a "middle-out" approach that guided two subsequent case studies, thereby demonstrating that the dimensional view of data does provide managers with an effective means of making sense of organizational data.
Profiles of MIS doctoral candidates
Authors: Larsen Kai R. T. , Neely M. Pamela
Published: October 2004

Little is known about which qualities MIS department search committees are looking for in candidates when conducting a faculty search at the assistant professor level. This paper examines the qualities being sought by institutions focusing on research, teaching, or both. The actual teaching and research performance of students in the field is then used to find clusters of students and to examine the performance of different clusters. Finally, lessons for students and academic programs are discussed in terms of fit of the faculty candidate and the academic department.
A simple standardized Ada command line interface
Authors: Gicca Greg
Published: October 2004

This paper describes an implementation approach for developing a common command-line interface for Ada tools. This paper is not directed towards tool vendors but rather to contractors that may have small internal tools development groups to supplement their purchase of tools from vendors.The paper first describes the reasoning behind the approach taken to develop a common command-line user interface. It then describes in some detail the design of the user interface package developed. An Ada package specification for the described subsystem is then presented, followed by some conclusions.
Tasks as abstraction mechanisms
Authors: Cohen Norman H.
Published: October 2004

At first glance, packages appear to be tools for abstraction and information hiding, while tasks appear to be tools for the expression of concurrency. In many cases, however, tasks are a more appropriate vehicle than packages for abstraction and information hiding. This paper explores the use of tasks for roles traditionally assigned to packages. We emerge with an expanded notion of the role of tasks in programming.
A note on the modified CRC
Authors: Berry T. G.
Published: October 2004

The theory underlying the modification of the CRC which is used in protocols such as HDLC and ADCCP is sketched, and a possible pitfall in the implementation is described.
An improved persitent CSMA algorithm without collision detection
Authors: Salati Claudio
Published: October 2004

The paper presents a new version of the CSMA algorithm which improves the performances of 1-persistent CSMA without the need of collision detection, and without any rescheduling of frames, and thus any waste of bandwidth. Performances are evaluated both through experimental data and through a mathematical argument, which explains the reasons of the improvement.
The defense message system
Authors: Shirey Robert W.
Published: October 2004

The U.S. Department of Defense (DoD) plans to modernize the Defense Message System (DMS) to reduce costs and improve services. DMS includes all hardware, software, procedures, standards, facilities, and personnel used to exchange messages electronically in DoD. DMS today has two separate parts. The AUTODIN system handles formal messages between organizations, and the Defense Data Network's electronic mail system handles other messages. The DMS plan has a target architecture, for the year 2008, that integrates those separate systems, uses CCITT X.400 message handling and X.500 directory services, and provides writer-to-reader security with the Secure Data Network System developed by the National Security Agency. The implementation strategy has three phases that extend over 20 years. The plan has an indirect but strong effect on the Internet outside DoD.
Limitations of the Kerberos authentication system
Authors: Bellovin S. M. , Merritt M.
Published: October 2004

The Kerberos authentication system, a part of MIT's Project Athena, has been adopted by other organizations. Despite Kerberos's many strengths, it has a number of limitations and some weaknesses. Some are due to specifics of the MIT environment; others represent deficiencies in the protocol design. We discuss a number of such problems, and present solutions to some of them. We also demonstrate how special-purpose cryptographic hardware may be needed in some cases.
An example of event-driven asynchronous scheduling with Ada
Authors: Chelini James V. , Hughes Donna D. , Hoffman Leonard J. , Brunelle Denise M.
Published: October 2004

The TARTAR CGN-36/NTU Baseline Development Program (CGN-36) required a preemptive scheduling mechanism that was both efficient and compatible with an Ada implementation targeted for the M68020 processor. As a result, CGN-36 developed an event-driven asynchronous scheduling package functioning as an extension of the selected vendor's (Systems Designers (SD)) Ada Run-Time Environment (RTE). This paper describes:Introduction. Why a standard Ada (rendezvous) approach would not work1. Synchronous versus Asynchronous trade-offs2. Design of the event-driven scheduler3. Validation issues4. Timing results5. Porting/Reuse issues6. Lessons learned
Linear benchmarks
Authors: Vestal Steve
Published: October 2004

This paper presents a language feature benchmarking technique that is based on the use of multiple sampling loops and linear regression. Multiple performance estimates for multiple parameters can be obtained simultaneously. A heuristic is presented to automatically adjust the number of iterations for the sampling loops. It is also possible to compute values that give some insight into the accuracy of the estimates. This paper gives an overview of how such benchmarks may be coded and discusses some preliminary experiments with this approach.
An example of event-driven asynchronous scheduling with Ada
Authors: Chelini James V. , Hughes Donna D. , Hoffman Leonard J. , Brunelle Denise M.
Published: October 2004

The TARTAR CGN-36/NTU Baseline Development Program (CGN-36) required a preemptive scheduling mechanism that was both efficient and compatible with an Ada implementation targeted for the m68020 processor. As a result, CGN-36 developed an event-driven asynchronous scheduling package functioning as an extension of the selected vendor's (Systems Designers (SD)) Ada Run-Time Environment (RTE). This paper describes:Introduction. Why a standard Ada (rendezvous) approach would not work1. Synchronous versus Asynchronous trade-offs2. Design of the event-driven scheduler3. Validation issues4. Timing results5. Porting/Reuse issues6. Lessons learned