bluuebunny/crossref_metadata_2025 huggingface dataset:
Rank-maximal matchings
Authors: Irving Robert W. , Kavitha Telikepalli , Mehlhorn Kurt , Michail Dimitrios , Paluch Katarzyna E.
Published: April 2007

Suppose that each member of a set
A
of applicants ranks a subset of a set
P
of posts in an order of preference, possibly involving ties. A
matching
is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A
rank-maximal
matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [2003].We give an algorithm to compute a rank-maximal matching with running time
O
(min(
n
+
C
,
C
√
n
)
m
), where
C
is the maximal rank of an edge used in a rank-maximal matching,
n
is the number of applicants and posts and
m
is the total size of the preference lists.
When indexing equals compression
Authors: Foschini Luca , Grossi Roberto , Gupta Ankur , Vitter Jeffrey Scott
Published: April 2007

We report on a new experimental analysis of high-order entropy-compressed suffix arrays, which retains the theoretical performance of previous work and represents an improvement in practice. Our experiments indicate that the resulting text index offers state-of-the-art compression. In particular, we require roughly 20% of the original text size---without requiring a separate instance of the text. We can additionally use a simple notion to encode and decode block-sorting transforms (such as the Burrows--Wheeler transform), achieving a compression ratio comparable to that of bzip2. We also provide a compressed representation of suffix trees (and their associated text) in a total space that is comparable to that of the text alone compressed with gzip.
Statistical admission control using delay distribution measurements
Authors: Gopalan Kartik , Huang Lan , Peng Gang , Chiueh Tzi-Cker , Lin Yow-Jian
Published: April 2007

Growth of performance sensitive applications, such as voice and multimedia, has led to widespread adoption of resource virtualization by a variety of service providers (xSPs). For instance, Internet Service Providers (ISPs) increasingly differentiate their offerings by means of customized services, such as virtual private networks (VPN) with Quality of Service (QoS) guarantees or QVPNs. Similarly Storage Service Providers (SSPs) use storage area networks (SAN)/network attached storage (NAS) technology to provision virtual disks with QoS guarantees or QVDs. The key challenge faced by these xSPs is to maximize the number of
virtual resource units
they can support by exploiting the statistical multiplexing nature of the customers' input request load.While a number of measurement-based admission control algorithms utilize statistical multiplexing along the bandwidth dimension, they do not satisfactorily exploit statistical multiplexing along the delay dimension to guarantee distinct per-virtual-unit delay bounds. This article presents Delay Distribution Measurement (DDM) based admission control algorithm, the first measurement-based approach that effectively exploits statistical multiplexing along the delay dimension. In other words, DDM exploits the well-known fact that the actual delay experienced by most service requests (packets or disk I/O requests) for a virtual unit is usually far smaller than its worst-case delay bound requirement because multiple virtual units rarely send request bursts at the same time. Additionally, DDM supports virtual units with distinct probabilistic delay guarantees---virtual units that can tolerate more delay violations can reserve fewer resources than those that tolerate less, even though they require the same delay bound. Comprehensive trace-driven performance evaluation of QVPNs (using Voice over IP traces) and QVDs (using video stream, TPC-C, and Web search I/O traces) shows that, when compared to deterministic admission control, DDM can potentially increase the number of admitted virtual units (and resource utilization) by up to a factor of 3.
Process prioritization using output production
Authors: Etsion Yoav , Tsafrir Dan , Feitelson Dror G.
Published: April 2007

Desktop operating systems such as Windows and Linux base scheduling decisions on CPU consumption; processes that consume fewer CPU cycles are prioritized, assuming that interactive processes gain from this since they spend most of their time waiting for user input. However, this doesn't work for modern multimedia applications which require significant CPU resources. We therefore suggest a new metric to identify interactive processes by explicitly measuring interactions with the user, and we use it to design and implement a process scheduler. Measurements using a variety of applications indicate that this scheduler is very effective in distinguishing between competing interactive and noninteractive processes.
Metadata handling
Authors: Madhwacharyula Chitra L. , Davis Marc , Mulhem Philippe , Kankanhalli Mohan S.
Published: April 2007

This article addresses the problem of processing the annotations of preexisting video productions to enable reuse and repurposing of metadata. We introduce the concept of automatic content-based editing of preexisting semantic home video metadata. We propose a formal representation and implementation techniques for reusing and repurposing semantic video metadata in concordance with the actual video editing operations. A novel representation for metadata editing is proposed and an implementation framework for editing the metadata in accordance with the video editing operations is demonstrated. Conflict resolution and regularization operations are defined and implemented in the context of the video metadata editing operations.
Speed scaling to manage energy and temperature
Authors: Bansal Nikhil , Kimbrel Tracy , Pruhs Kirk
Published: April 2007

Speed scaling is a power management technique that involves dynamically changing the speed of a processor. We study policies for setting the speed of the processor for both of the goals of minimizing the energy used and the maximum temperature attained. The theoretical study of speed scaling policies to manage energy was initiated in a seminal paper by Yao et al. [1995], and we adopt their setting. We assume that the power required to run at speed
s
is
P
(
s
) =
s
α
for some constant α > 1. We assume a collection of tasks, each with a release time, a deadline, and an arbitrary amount of work that must be done between the release time and the deadline. Yao et al. [1995] gave an offline greedy algorithm YDS to compute the minimum energy schedule. They further proposed two online algorithms Average Rate (AVR) and Optimal Available (OA), and showed that AVR is 2
α − 1
α
α
-competitive with respect to energy. We provide a tight α
α
bound on the competitive ratio of OA with respect to energy.

We initiate the study of speed scaling to manage temperature. We assume that the environment has a fixed ambient temperature and that the device cools according to Newton's law of cooling. We observe that the maximum temperature can be approximated within a factor of two by the maximum energy used over any interval of length 1/
b
, where
b
is the cooling parameter of the device. We define a speed scaling policy to be cooling-oblivious if it is simultaneously constant-competitive with respect to temperature for all cooling parameters. We then observe that cooling-oblivious algorithms are also constant-competitive with respect to energy, maximum speed and maximum power. We show that YDS is a cooling-oblivious algorithm. In contrast, we show that the online algorithms OA and AVR are not cooling-oblivious. We then propose a new online algorithm that we call BKP. We show that BKP is cooling-oblivious. We further show that BKP is
e
-competitive with respect to the maximum speed, and that no deterministic online algorithm can have a better competitive ratio. BKP also has a lower competitive ratio for energy than OA for α ≥5.

Finally, we show that the optimal temperature schedule can be computed offline in polynomial-time using the Ellipsoid algorithm.
EXPINT---A MATLAB package for exponential integrators
Authors: Berland Håvard , Skaflestad Bård , Wright Will M.
Published: April 2007

Recently, a great deal of attention has been focused on the construction of exponential integrators for semilinear problems. In this article we describe a MATLAB
1
package which aims to facilitate the quick deployment and testing of exponential integrators, of Runge--Kutta, multistep, and general linear type. A large number of integrators are included in this package along with several well-known examples. The so-called φ functions and their evaluation is crucial for accuracy, stability, and efficiency of exponential integrators, and the approach taken here is through a modification of the scaling and squaring technique, the most common approach used for computing the matrix exponential.
Algorithm 863
Authors: Demetriou Ioannis C.
Published: April 2007

Fortran software is developed that calculates a best piecewise monotonic approximation tonunivariate data contaminated by random errors. The underlying method minimizes the weighted sum of the squares of the errors by requiringk− 1 sign changes in the first divided differences of the approximation, wherekis a given positive integer. Hence, the piecewise linear interpolant to the fit consists ofkmonotonic sections, alternately increasing and decreasing. This calculation can have aboutO(nk) local minima, because the positions of the turning points of the fit are integer variables of the problem. The method, however, by employing a dynamic programming technique divides the data into at mostkdisjoint sets of adjacent data and solves ak= 1 problem (monotonic fit or isotonic regression) for each set. So it calculates efficiently a global solution in onlyO(nσ +kσ2) computer operations whenk≥ 3, where σ is the number of local minima of the data, always bounded byn/2. This complexity reduces to onlyO(n) whenk= 1 ork= 2 (unimodal case). At the end of the calculation a spline representation of the solution and the corresponding Lagrange multipliers are provided. The software package has been tested on a variety of data sets showing a performance that does provide in practice shorter computation times than the complexity indicates in theory. An application of the method on identifying turning points and monotonic trends of data from 1947--1996 on the U.K. pound over the U.S. dollar exchange rate is presented. Generally, the method may have useful applications as, for example, in estimating the turning points of a function from some noisy measurements of its values, or in image and signal processing, or in providing a preliminary or complementary smoothing phase to further analyses of the data.
Spatial join techniques
Authors: Jacox Edwin H. , Samet Hanan
Published: April 2007

A variety of techniques for performing a spatial join are reviewed. Instead of just summarizing the literature and presenting each technique in its entirety, distinct components of the different techniques are described and each is decomposed into an overall framework for performing a spatial join. A typical spatial join technique consists of the following components: partitioning the data, performing internal-memory spatial joins on subsets of the data, and checking if the full polygons intersect. Each technique is decomposed into these components and each component addressed in a separate section so as to compare and contrast similar aspects of each technique. The goal of this survey is to describe the algorithms within each component in detail, comparing and contrasting competing methods, thereby enabling further analysis and experimentation with each component and allowing the best algorithms for a particular situation to be built piecemeal, or, even better, enabling an optimizer to choose which algorithms to use.
Efficient software implementation of embedded communication protocol controllers using asynchronous software thread integration with time- and space-efficient procedure calls
Authors: Kumar Nagendra J. , Asokan Vasanth , Shivshankar Siddhartha , Dean Alexander G.
Published: April 2007

The overhead of context switching limits efficient scheduling of multiple concurrent threads on a uniprocessor when real-time requirements exist. A software-implemented protocol controller may be crippled by this problem. The available idle time may be too short to recover through context switching, so only the primary thread can execute during message activity, slowing the secondary threads and potentially missing deadlines. Asynchronous software thread integration (ASTI) uses coroutine calls and integration, letting threads make independent progress efficiently, and reducing the needed context switches. We demonstrate the methods with a software implementation of an automotive communication protocol (J1850) and several secondary threads.
Efficient indexing data structures for flash-based sensor devices
Authors: Lin Song , Zeinalipour-Yazti Demetrios , Kalogeraki Vana , Gunopulos Dimitrios , Najjar Walid A.
Published: April 2007

Flash memory is the most prevalent storage medium found on modern
wireless sensor devices (WSDs)
. In this article we present two external memory index structures for the efficient retrieval of records stored on the local flash memory of a WSD. Our index structures,
MicroHash
and
MicroGF (micro grid files)
, exploit the asymmetric read/write and wear characteristics of flash memory in order to offer high-performance indexing and searching capabilities in the presence of a low-energy budget, which is typical for the devices under discussion. Both structures organize data and index pages on the flash media using a sorted by timestamp file organization. A key idea behind these index structures is that expensive random access deletions are completely eliminated. MicroHash enables equality searches by value in constant time and equality searches by timestamp in logarithmic time at a small cost of storing index pages on the flash media. Similarly, MicroGF enables spatial equality and proximity searches in constant time. We have implemented these index structures in nesC, the programming language of the TinyOS operating system. Our trace-driven experimentation with several real datasets reveals that our index structures offer excellent search performance at a small cost of constructing and maintaining the index.
Energy-efficient wireless sensor network design and implementation for condition-based maintenance
Authors: Tiwari Ankit , Ballal Prasanna , Lewis Frank L.
Published: April 2007

A new application architecture is designed for continuous, real-time, distributed wireless sensor networks. We develop a wireless sensor network for machinery condition-based maintenance (CBM) in small machinery spaces using commercially available products. We develop a hardware platform, networking architecture, and medium access communication protocol. We implement a single-hop sensor network to facilitate real-time monitoring and extensive data processing for machine monitoring. A new radio battery consumption model is presented and the battery consumption equation is used to select the most suitable topology and design an energy efficient communication protocol for wireless sensor networks. A new streamlined matrix formulation is developed that allows the base station to compute the best periodic sleep times for all the nodes in the network. We combine scheduling and contention to design a hybrid MAC protocol, which achieves 100% collision avoidance by using our modified RTS-CTS contention mechanism known as UC-TDMA protocol. A LabVIEW graphical user interface is described that allows for signal processing, including FFT, various moments, and kurtosis. A wireless CBM sensor network implementation on a heating and air conditioning plant is presented as a case study.
Informational privacy and its ontological interpretation
Authors: Floridi Luciano
Published: April 2007

The article provides an outline of the ontological interpretation of informational privacy based on information ethics (Floridi [forthcoming-b]). It is part of a larger project of research, in which I have developed the foundations of ideas presented here (Floridi [forthcoming-c]) and their consequences (Floridi [forthcoming-a])
Modeling the short-term dynamics of packet losses
Authors: Silveira Fernando , de Souza e Silva Edmundo
Published: April 2007

Packet loss models play an essential role in computer networks analysis. Performance evaluation studies often abstract the loss and delay characteristics of a path or network with a single end-to-end analytical model. This model should be able to represent the characteristics of the path and accurately reproduce the impact of delay and losses on the studied protocol while keeping complexity low.
On selection of candidates for opportunistic anypath forwarding
Authors: Zhong Zifei , Wang Junling , Nelakuditi Srihari , Lu Guor-Huar
Published: April 2007

Opportunistic routing schemes that exploit the broadcast nature of wireless transmissions for selecting the best next-hop at that instant among a set of candidates are being actively explored [1-3]. These schemes which we refer to as opportunistic
any-path
forwarding (OAPF), reduce the number of transmissions needed for reliable packet delivery.
Intranet model and metrics
Authors: Jacoby Grant A. , Luqi
Published: April 2007

Measuring intranet overall value contributions based on a corporation's critical business requirements.
Dynamic personalization of web sites without user intervention
Authors: Baraglia Ranieri , Silvestri Fabrizio
Published: April 2007

A novel online recommender system builds profiling models and offers suggestions without the user taking the lead.
Contextualizing usage research for interactive technology
Authors: Schultze Ulrike , Carte Traci A.
Published: April 2007

E-Commerce technologies are interactive in nature, yet most research on E-Commerce adoption and use fails to consider this feature and the technology's social context of use in its theorizing. In this paper, we seek to theorize the technological feature of interactivity in a social context of information asymmetry by studying the use of E-Commerce technology among car sales associates in the US. Drawing on Social Exchange Theory (Kelley, 1979), we develop a model of interactive technology use that incorporates the user's beliefs about his/her exchange partner, the user's attitude toward technology use and the technology's perceived usefulness for the work process it is impacting. After refining our model with insights gained from observations of and interviews with a few car sales associates, we then test our contextualized model of E-Commerce use with data collected from a national survey of car sales associates (n=137).Our results show that attitude and users' beliefs about their exchange partners improve our ability to predict IT use. Furthermore, the contexualization of TAM highlights the theory's assumptions about the unemotional and individually-focused nature of users' decision making with respect to IT use.
A combined register-stack architecture
Authors: Sites Richard L.
Published: April 2007

A stack is the simplest mechanism for evaluating arithmetic expressions, while a group of general registers is the simplest mechanism for quick access to a small number of common subexpressions or loop control variables. Until now, computers have been designed around either a stack mechanism or a register mechanism, but no machine has included both in a convenient way. In this paper, we propose a new combination architecture in which there are general registers, but one of these registers is the top of an evaluation stack. This combination is intended entirely for calculation, and is not related to the use of stacks in main memory for holding activation records of Algol-like procedures, or to the use of stacks for holding subroutine linkage information. The mechanism can be implemented entirely in a fixed number of hardware registers, with no elaborate stack spilling mechanism. The combination architecture meshes perfectly with existing general-register architectures, while providing the advantages of a stack for expression evaluation. One way to view the combination architecture is that it provides access to about twice as many fast registers with no increase in the number of instruction bits needed to address them.
Final report of the GSPC state-of-the-art subcommittee
Authors: Ewald R. H. , Fryer R.
Published: April 2007

This paper presents the final report of the ACM/SIGGRAPH Graphics Standards Planning Committee (GSPC) State-of-the-Art Subcommittee. This group's charter was to compare existing vector-oriented graphics packages to determine their similarities and differences. Eight graphics packages and the GSPC "Core System" were selected for review.
Architecting a reliable CMP switch architecture
Authors: Constantinides Kypros , Plaza Stephen , Blome Jason , Bertacco Valeria , Mahlke Scott , Austin Todd , Zhang Bin , Orshansky Michael
Published: April 2007

As silicon technologies move into the nanometer regime, transistor reliability is expected to wane as devices become subject to extreme process variation, particle-induced transient errors, and transistor wear-out. Unless these challenges are addressed, computer vendors can expect low yields and short mean-times-to-failure. In this article, we examine the challenges of designing complex computing systems in the presence of transient and permanent faults. We select one small aspect of a typical chip multiprocessor (CMP) system to study in detail, a single CMP router switch. Our goal is to design a
BulletProof
CMP switch architecture capable of tolerating significant levels of various types of defects. We first assess the vulnerability of the CMP switch to transient faults. To better understand the impact of these faults, we evaluate our CMP switch designs using circuit-level timing on detailed physical layouts. Our infrastructure represents a new level of fidelity in architectural-level fault analysis, as we can accurately track faults as they occur, noting whether they manifest or not, because of masking in the circuits, logic, or architecture. Our experimental results are quite illuminating. We find that transient faults, because of their fleeting nature, are of little concern for our CMP switch, even within large switch fabrics with fast clocks. Next, we develop a unified model of permanent faults, based on the time-tested bathtub curve. Using this convenient abstraction, we analyze the reliability versus area tradeoff across a wide spectrum of CMP switch designs, ranging from unprotected designs to fully protected designs with on-line repair and recovery capabilities. Protection is considered at multiple levels from the entire system down through arbitrary partitions of the design. We find that designs are attainable that can tolerate a larger number of defects with less overhead than naïve triple-modular redundancy, using domain-specific techniques, such as end-to-end error detection, resource sparing, automatic circuit decomposition, and iterative diagnosis and reconfiguration.
Properties and mechanisms of self-organizing MANET and P2P systems
Authors: Biskupski Bartosz , Dowling Jim , Sacha Jan
Published: April 2007

Despite the recent appearance of self-organizing distributed systems for Mobile Ad Hoc Networks (MANETs) and Peer-to-Peer (P2P) networks, specific theoretical aspects of both their properties and the mechanisms used to establish those properties have been largely overlooked. This has left many researchers confused as to what constitutes a self-organizing distributed system and without a vocabulary with which to discuss aspects of these systems. This article introduces an agent-based model of self-organizing MANET and P2P systems and shows how it is realised in three existing network systems. The model is based on concepts such as partial views, evaluation functions, system utility, feedback and decay. We review the three network systems, AntHocNet, SAMPLE, and Freenet, and show how they can achieve high scalability, robustness and adaptability to unpredictable changes in their environment, by using self-organizing mechanisms similar to those found in nature. They are designed to improve their operation in a dynamic, heterogeneous environment, enabling them to often demonstrate superior performance to state of the art distributed systems. This article is also addressed at researchers interested in gaining a general understanding of different mechanisms and properties of self-organization in distributed systems.
Minimizing the maximum absolute deviation
Authors: Sposito V. A.
Published: April 2007

In a recent educational technical note in SIGMAP, [3], Swanson and Woolsey outlined how one can determine the unknown parameters of a linear model under the criterion of minimizing the sum of absolute deviations. This note will demonstrate that one can also use linear programming procedures under the criterion of minimizing the maximum absolute deviation. This transformation to a linear programming problem is known, but not of wide extent; and is useful when one is trying to identify "outliers".
Research note
Authors: Robertson Edward L.
Published: April 2007

The general problem of formating microinstruction so as to minimize the width of words in control memory is shown to be computationally difficult. Hence, we should not attempt to solve the general case, but concentrate on heuristics for reasonable subcases.
General purpose emulation using the Hewlett-Packard 2100 minicomputer
Authors: Lewis Daniel W.
Published: April 2007

A taxanomy of methods for the implementation of general-purpose emulation projects on the Hewlett-Packard 2100 minicomputer is presented. The HP2100 is intended to be microprogrammed for instruction set extensions rather than general emulation. Problems encountered and solutions found through experience are discussed.
Open vs. Closed
Authors: Ford Richard
Published: April 2007

There is no better way to start an argument among a group of developers than proclaiming Operating System A to be "more secure" than Operating System B. I know this from first-hand experience, as previous papers I have published on this topic have led to reams of heated e-mails directed at me - including some that were, quite literally, physically threatening. Despite the heat (not light!) generated from attempting to investigate the relative security of different software projects, investigate we must.
Realtime Garbage Collection
Authors: Bacon David F.
Published: April 2007

Traditional computer science deals with the computation of correct results. Realtime systems interact with the physical world, so they have a second correctness criterion: they have to compute the correct result within a bounded amount of time. Simply building functionally correct software is hard enough. When timing is added to the requirements, the cost and complexity of building the software increase enormously.
Toward HW/SW integration
Authors: Shih Chi-Sheng , Tsao Shiao-Li , Chung Yeh-Ching , Hwang Shyh-In
Published: April 2007

Traditional Computer Science curricula focus on the training for logic reasoning and programming skills. System integration is often not covered in computer science curricula. As the embedded platforms migrate from 8-bit microprocessors to 32-bit microprocessors, the engineers require different skills to design modern embedded systems. The Computer Science faculties at several universities in Taiwan have collaborated to design a new course to meet such needs. In this course, we focus on the capability of integrating hardware and software in networked embedded systems. In particular, the students learn the skills for embedded real-time programming, multi-thread programming, low-power network protocols, security, and wireless networks protocol. In this article, we report the design rationale and current status of this course.
The development and deployment of embedded software curricula in Taiwan
Authors: Tsao Shiao-Li , Huang Tai-Yi , King Chung-Ta
Published: April 2007

The Embedded Software (ESW) consortium under the Very-Large-Scale Integration (VLSI) Circuits and Systems Education Program which is supervised by the Ministry of Education (MOE) of Taiwan was initiated in 2004 to develop and promote embedded software education. One of the major missions for this consortium is to develop and deploy embedded software curricula which are not well established in traditional computer science (CS) and electrical engineering (EE) education programs in Taiwan. Therefore, the ESW consortium has spent three years in developing embedded software curricula with total twelve new courses. In this paper, our strategies, implementation and experiences for developing and deploying embedded software curricula are presented.
On the composition of authenticated Byzantine Agreement
Authors: Lindell Yehuda , Lysyanskaya Anna , Rabin Tal
Published: April 2007

A fundamental problem of distributed computing is that of simulating a secure broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement (or Generals) and has been the focus of much research. Lamport et al. [1982] showed that in order to achieve Byzantine Agreement in the plain model, more than two thirds of the participating parties must be honest. They further showed that by augmenting the network with a public-key infrastructure for digital signatures, it is possible to obtain protocols that are secure for any number of corrupted parties. The problem in this augmented model is called “authenticated Byzantine Agreement”.In this article, we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols with a single common setup. We present surprising impossibility results showing that:(1) Authenticated Byzantine Agreement protocols that remain secure under parallel or concurrent composition (even for just two executions) and tolerate a third or more corrupted parties, do
not
exist.(2) Deterministic authenticated Byzantine Agreement protocols that run for
r
rounds and tolerate a third or more corrupted parties, can remain secure for at most 2
r
− 1 sequential executions.In contrast, we present randomized protocols for authenticated Byzantine Agreement that remain secure under sequential composition, for
any
polynomial number of executions. We exhibit two such protocols. In the first protocol, an honest majority is required. In the second protocol, any number of parties may be corrupted; however, the complexity of the protocol is in the order of 2

n

·
n
! for
n
parties. In order to have this polynomial in the security parameter
k
(used for the signature scheme in the protocol), this requires the overall number of parties to be limited to
O
(log
k
/log log
k
). The above results are achieved due to a new protocol for authenticated Byzantine Generals for three parties that can tolerate any number of faulty parties and composes sequentially.Finally, we show that when the model is further augmented so that in each session, all the participating parties receive a common session identifier that is unique to that session, then any polynomial number of authenticated Byzantine agreement protocols can be concurrently executed, while tolerating any number of corrupted parties.
Moving digital libraries into the student learning space
Authors: Marshall Byron B. , Chen Hsinchun , Shen Rao , Fox Edward A.
Published: April 2007

The GetSmart system was built to support theoretically sound learning processes in a digital library environment by integrating course management, digital library, and concept mapping components to support a constructivist, six-step, information search process. In the fall of 2002 more than 100 students created 1400 concept maps as part of selected computing classes offered at the University of Arizona and Virginia Tech. Those students conducted searches, obtained course information, created concept maps, collaborated in acquiring knowledge, and presented their knowledge representations. This article connects the design elements of the GetSmart system to targeted concept-map-based learning processes, describes our system and research testbed, and analyzes our system usage logs. Results suggest that students did in fact use the tools in an integrated fashion, combining knowledge representation and search activities. After concept mapping was included in the curriculum, we observed improvement in students' online quiz scores. Further, we observed that students in groups collaboratively constructed concept maps with multiple group members viewing and updating map details.
Argos
Authors: Portokalidis Georgios , Slowinska Asia , Bos Herbert
Published: April 2007

As modern operating systems and software become larger and more complex, they are more likely to contain bugs, which may allow attackers to gain illegitimate access. A fast and reliable mechanism to discern and generate vaccines for such attacks is vital for the successful protection of networks and systems. In this paper we present Argos, a containment environment for worms as well as human orchestrated attacks.
Argos
is built upon a fast x86 emulator which tracks network data throughout execution to identify their invalid use as jump targets, function addresses, instructions, etc. Furthermore, system call policies disallow the use of network data as arguments to certain calls. When an attack is detected, we perform 'intelligent' process- or kernel-aware logging of the corresponding emulator state for further offline processing. In addition, our own
forensics shellcode
is injected, replacing the malevolent shellcode, to gather information about the attacked process. By correlating the data logged by the emulator with the data collected from the network, we are able to generate accurate network intrusion detection signatures for the
exploits
that are immune to
payload
mutations. The entire process can be automated and has few if any false positives, thus rapid global scale deployment of the signatures is possible.
Solving the starting problem
Authors: Spear Michael F. , Roeder Tom , Hodson Orion , Hunt Galen C. , Levi Steven
Published: April 2007

Run-time conflicts can affect even the most rigorously tested software systems. A reliance on execution-based testing makes it prohibitively costly to test every possible interaction among potentially thousands of programs with complex configurations. In order to reduce configuration problems, detect developer errors, and reduce developer effort, we have created a new first class operating system abstraction, the application abstraction, which enables both online and offline reasoning about programs and their configuration requirements.We have implemented a subset of the application abstraction for device drivers in the Singularity operating system. Programmers use the application abstraction by placing declarative statements about hardware and communication requirements within their code. Our design enables Singularity to learn the input/output and interprocess communication requirements of drivers without executing driver code. By reasoning about this information within the domain of Singularity's strong software isolation architecture, the installer can execute a subset the system's resource management algorithm at install time to verify that a new driver will not conflict with existing software. This abstract representation also allows the system to run the full algorithm at driver start time to ensure that there are never resource conflicts between executing drivers, and that drivers never use undeclared resources.
Thorough static analysis of device drivers
Authors: Ball Thomas , Bounimova Ella , Cook Byron , Levin Vladimir , Lichtenberg Jakob , McGarvey Con , Ondrusek Bohus , Rajamani Sriram K. , Ustuner Abdullah
Published: April 2007

Bugs in kernel-level device drivers cause 85% of the system crashes in the Windows XP operating system [44]. One of the sources of these errors is the complexity of the Windows driver API itself: programmers must master a complex set of rules about how to use the driver API in order to create drivers that are good clients of the kernel. We have built a static analysis engine that finds API usage errors in C programs. The Static Driver Verifier tool (SDV) uses this engine to find kernel API usage errors in a driver. SDV includes models of the OS and the environment of the device driver, and over sixty API usage rules. SDV is intended to be used by driver developers "out of the box." Thus, it has stringent requirements: (1) complete automation with no input from the user; (2) a low rate of false errors. We discuss the techniques used in SDV to meet these requirements, and empirical results from running SDV on over one hundred Windows device drivers.
Experiences in building and operating ePOST, a reliable peer-to-peer application
Authors: Mislove Alan , Post Ansley , Haeberlen Andreas , Druschel Peter
Published: April 2007

Peer-to-peer (p2p) technology can potentially be used to build highly reliable applications without a single point of failure. However, most of the existing applications, such as file sharing or web caching, have only moderate reliability demands. Without a challenging proving ground, it remains unclear whether the full potential of p2p systems can be realized.To provide such a proving ground, we have designed, deployed and operated a p2p-based email system. We chose email because users depend on it for their daily work and therefore place high demands on the availability and reliability of the service, as well as the durability, integrity, authenticity and privacy of their email. Our system, ePOST, has been actively used by a small group of participants for over two years.In this paper, we report the problems and pitfalls we encountered in this process. We were able to address some of them by applying known principles of system design, while others turned out to be novel and fundamental, requiring us to devise new solutions. Our findings can be used to guide the design of future reliable p2p systems and provide interesting new directions for future research.
Language support for fast and reliable message-based communication in singularity OS
Authors: Fähndrich Manuel , Aiken Mark , Hawblitzel Chris , Hodson Orion , Hunt Galen , Larus James R. , Levi Steven
Published: April 2007

Message-based communication offers the potential benefits of providing stronger specification and cleaner separation between components. Compared with shared-memory interactions, message passing has the potential disadvantages of more expensive data exchange (no direct sharing) and more complicated programming.In this paper we report on the language, verification, and run-time system features that make messages practical as the sole means of communication between processes in the Singularity operating system. We show that using advanced programming language and verification techniques, it is possible to provide and enforce strong system-wide invariants that enable efficient communication and low-overhead software-based process isolation. Furthermore, specifications on communication channels help in detecting programmer mistakes early---namely at compile-time---thereby reducing the difficulty of the message-based programming model.The paper describes our communication invariants, the language and verification features that support them, as well as implementation details of the infrastructure. A number of benchmarks show the competitiveness of this approach.
Context-specific middleware specialization techniques for optimizing software product-line architectures
Authors: Krishna Arvind S. , Gokhale Aniruddha S. , Schmidt Douglas C.
Published: April 2007

Product-line architectures (PLAs) are an emerging paradigm for developing software families for distributed real-time and embedded (DRE) systems by customizing reusable artifacts, rather than hand-crafting software from scratch. To reduce the effort of developing software PLAs and product variants for DRE systems, developers are applying general-purpose -- ideally standard -- middleware platforms whose reusable services and mechanisms support a range of application quality of service (QoS) requirements, such as low latency and jitter. The generality and flexibility of standard middleware, however, often results in excessive time/space overhead for DRE systems, due to lack of optimizations tailored to meet the specific QoS requirements of different product variants in a PLA.This paper provides the following contributions to the study of middleware specialization techniques for PLA-based DRE systems. First, we identify key dimensions of generality in standard middleware stemming from framework implementations, deployment platforms, and middleware standards. Second, we illustrate how context-specific specialization techniques can be automated and used to tailor standard middleware to better meet the QoS needs of different PLA product variants. Third, we quantify the benefits of applying automated tools to specialize a standard Realtime CORBA middleware implementation. When applied together, these middleware specializations improved our application product variant throughput by ~65%, average- and worst-case end-to-end latency measures by ~43% and ~45%, respectively, and predictability by a factor of two over an already optimized middleware implementation, with little or no effect on portability, standard middleware APIs, or application software implementations, and interoperability.
A fresh look at the reliability of long-term digital storage
Authors: Baker Mary , Shah Mehul , Rosenthal David S. H. , Roussopoulos Mema , Maniatis Petros , Giuli TJ , Bungale Prashanth
Published: April 2007

Emerging Web services, such as email, photo sharing, and web site archives, must preserve large volumes of quickly accessible data indefinitely into the future. The costs of doing so often determine whether the service is economically viable. We make the case that these applications' demands on large scale storage systems over long time horizons require us to reevaluate traditional system designs. We examine threats to long-lived data from an end-to-end perspective, taking into account not just hardware and software faults but also faults due to humans and organizations. We present a simple model of long-term storage failures that helps us reason about various strategies for addressing some of these threats. Using this model we show that the most important strategies for increasing the reliability of long-term storage are detecting latent faults quickly, automating fault repair to make it cheaper and faster, and increasing the independence of data replicas.
RIMAC
Authors: Yao Xiaoyu , Wang Jun
Published: April 2007

Energy efficiency becomes increasingly important in today's high-performance storage systems. It can be challenging to save energy and improve performance at the same time in conventional (i.e. single-rotation-rate) disk-based storage systems. Most existing solutions compromise performance for energy conservation. In this paper, we propose a redundancy-based, two-level I/O cache architecture called RIMAC to address this problem. The idea of RIMAC is to enable data on the standby disk to be recovered by accessing data in the two-level I/O cache or on currently active/idle disks. At both cache and disk levels, RIMAC dynamically transforms accesses toward standby disks by exploiting parity redundancy in parity-based redundant disk arrays. Because I/O requests that require physical accesses on standby disks involve long waiting time and high power consumption for disk spin-up (tens of seconds for SCSI disks), transforming those requests to accesses in a two-level, collaborative I/O cache or on active disks can significantly improve both energy efficiency and performance.In RIMAC, we developed i) two power-aware read request transformation schemes called Transformable Read in Cache (TRC) and Transformable Read on Disk (TRD), ii) a power-aware write request transformation policy for parity update and iii) a second-chance parity cache replacement algorithm to improve request transformation rate. We evaluated RIMAC by augmenting a validated storage system simulator, disksim. For several real-life server traces including HP's cello 99, TPC-D and SPC's search engine, RIMAC is shown to reduce energy consumption by up to 33% and simultaneously improve the average response time by up to 30%.
Evaluating network processing efficiency with processor partitioning and asynchronous I/O
Authors: Brecht Tim , Janakiraman G. (John) , Lynn Brian , Saletore Vikram , Turner Yoshio
Published: April 2007

Applications requiring high-speed TCP/IP processing can easily saturate a modern server. We and others have previously suggested alleviating this problem in multiprocessor environments by dedicating a subset of the processors to perform network packet processing. The remaining processors perform only application computation, thus eliminating contention between these functions for processor resources. Applications interact with packet processing engines (PPEs) using an asynchronous I/O (AIO) programming interface which bypasses the operating system. A key attraction of this overall approach is that it exploits the architectural trend toward greater thread-level parallelism in future systems based on multi-core processors. In this paper, we conduct a detailed experimental performance analysis comparing this approach to a best-practice configured Linux baseline system.We have built a prototype system implementing this architecture, ETA+AIO (Embedded Transport Acceleration with Asynchronous I/O), and ported a high-performance web-server to the AIO interface. Although the prototype uses modern single-core CPUs instead of future multi-core CPUs, an analysis of its performance can reveal important properties of this approach. Our experiments show that the ETA+AIO prototype has a modest advantage over the baseline Linux system in packet processing efficiency, consuming fewer CPU cycles to sustain the same throughput. This efficiency advantage enables the ETA+AIO prototype to achieve higher peak throughput than the baseline system, but only for workloads where the mix of packet processing and application processing approximately matches the allocation of CPUs in the ETA+AIO system thereby enabling high utilization of all the CPUs. Detailed analysis shows that the efficiency advantage of the ETA+AIO prototype, which uses one PPE CPU, comes from avoiding multiprocessing overheads in packet processing, lower overhead of our AIO interface compared to standard sockets, and reduced cache misses due to processor partitioning.
Using queries for distributed monitoring and forensics
Authors: Singh Atul , Maniatis Petros , Roscoe Timothy , Druschel Peter
Published: April 2007

Distributed systems are hard to build, profile, debug, and test. Monitoring a distributed system - to detect and analyze bugs, test for regressions, identify fault-tolerance problems or security compromises - can be difficult and error-prone. In this paper we argue that declarative development of distributed systems is well suited to tackle these tasks. We present an application logging, monitoring, and debugging facility that we have built on top of the P2 system, comprising an introspection model, an execution tracing component, and a distributed query processor. We use this facility to demonstrate a range of on-line distributed diagnosis tools that range from simple, local state assertions to sophisticated global property detectors on consistent snapshots. These tools are small, simple, and can be deployed piecemeal on-line at any point during a system's life cycle. Our evaluation suggests that the overhead of our approach to improving and monitoring running distributed systems continuously is well in tune with its benefits.