bluuebunny/crossref_metadata_2025 huggingface dataset:
Improving hash join performance through prefetching
Authors: Chen Shimin , Ailamaki Anastassia , Gibbons Phillip B. , Mowry Todd C.
Published: September 2007

Hash join algorithms suffer from extensive CPU cache stalls. This article shows that the standard hash join algorithm for disk-oriented databases (i.e. GRACE) spends over 80% of its user time stalled on CPU cache misses, and explores the use of CPU cache
prefetching
to improve its cache performance. Applying prefetching to hash joins is complicated by the data dependencies, multiple code paths, and inherent randomness of hashing. We present two techniques,
group prefetching
and
software-pipelined prefetching
, that overcome these complications. These schemes achieve 1.29--4.04X speedups for the join phase and 1.37--3.49X speedups for the partition phase over GRACE and simple prefetching approaches. Moreover, compared with previous cache-aware approaches (i.e. cache partitioning), the schemes are at least 36% faster on large relations and do not require exclusive use of the CPU cache to be effective. Finally, comparing the elapsed real times when disk I/Os are in the picture, our cache prefetching schemes achieve 1.12--1.84X speedups for the join phase and 1.06--1.60X speedups for the partition phase over the GRACE hash join algorithm.
Efficient top-
k
aggregation of ranked inputs
Authors: Mamoulis Nikos , Yiu Man Lung , Cheng Kit Hung , Cheung David W.
Published: September 2007

A top-
k
query combines different rankings of the same set of objects and returns the
k
objects with the highest combined score according to an aggregate function. We bring to light some key observations, which impose two phases that any top-
k
algorithm, based on sorted accesses, should go through. Based on them, we propose a new algorithm, which is designed to minimize the number of object accesses, the computational cost, and the memory requirements of top-
k
search with monotone aggregate functions. We provide an analysis for its cost and show that it is always no worse than the baseline “no random accesses” algorithm in terms of computations, accesses, and memory required. As a side contribution, we perform a space analysis, which indicates the memory requirements of top-
k
algorithms that only perform sorted accesses. For the case, where the required space exceeds the available memory, we propose disk-based variants of our algorithm. We propose and optimize a multiway top-
k
join operator, with certain advantages over evaluation trees of binary top-
k
join operators. Finally, we define and study the computation of top-
k
cubes and the implementation of roll-up and drill-down operations in such cubes. Extensive experiments with synthetic and real data show that, compared to previous techniques, our method accesses fewer objects, while being orders of magnitude faster.
Leadership, teamwork, and ethics in the development of IT professionals
Authors: Martin C. Dianne
Published: September 2007

Increasingly universities are placing student leadership as a central goal for education. Many seminal texts on leadership focus attention on the moral and transformative qualities of leadership, encouraging universities to become a site for leadership development. One way to operationalize this is for leadership development to become an integral part of the learning outcomes of the curricula within the student's major. In the context of the IT majors, such as computer science, information science, and information technology, the definition of leadership can be incorporated with the desired outcomes of teamwork and professionalism. Thus, the development of leadership capacity is combined with the development of high standards of professionalism and the ability to work well on teams in a variety of roles.
Computing relationships
Authors: Clear Tony
Published: September 2007

I had a bad email day on October 10 last year. First, a colleague in the States copied me on a response to an email he had just received for a meeting scheduled in New Zealand over a month earlier. The email seemed to have been filtered out by his university's email filter somehow, even though he and my local colleague who originated the email had been in regular contact for some time. The accompanying message read "The sender is not authorized to send to the destination. This can be the result of per host or per recipient filtering". Then I received notification that an email I had sent to Finland some five days earlier had not been received, with the message "Recipient address rejected: Greylisted for 60 seconds (see http:www.joensuu.fi/atteskus/ohjeet/postgrey.html)"...Mes sage could not be delivered for 5 days Message will be deleted from queue". Next came a warning on a message I had sent to Sweden "recipient address rejected: Greylisting in action, please try later... Warning message still undelivered after 4 hours. Will keep trying until message is 5 days old". Well I know that New Zealand is small and far from many other countries, but the thought that we had been globally blacklisted began to enter my mind. Paranoia was setting in...
Revising the IS undergraduate model curriculum
Authors: Topi Heikki
Published: September 2007

Writing my first
inroads
IS Education column requires stepping into big shoes. I take this opportunity to thank my mentor, friend, and colleague, Dr. John T. Gorgone, for the excellent work he has done with this column to keep the broader computing community aware of the events and issues under discussion in IS education, to promote new initiatives, and to form connections between IS and other computing disciplines. I am looking forward to building on the strong foundation his work has formed.
Reading and class work
Authors: Walker Henry M.
Published: September 2007

Many years ago, I heard jokes about faculty transcribing material from a textbook onto the blackboard, students transcribing the board material into their notes, and the content going through the brains of neither.
Reflections on a history
Authors: Campbell Robert D.
Published: September 2007

After working in the two-year college environment for twenty-nine years, I've now relocated to The Graduate Center of the City University of New York, and so this will be my last column as Chair of the ACM Two-Year College Education Committee. It's more than fitting to use this opportunity to reflect on the auspicious history of this Committee.
Teaching online
Authors: Eshet Yoram
Published: September 2007

The rapid infiltration of instructional technologies into educational systems and corporations, confront teachers, trainers and instructors with situations that require the utilization of an ever-growing assortment of technical, cognitive, and sociological skills that are necessary in order to perform effectively in digital environments. These skills are termed collectively
'digital literacy'
. However, unlike the common attitude towards digital literacy in most studies of instructional technologies, it is more than just the technical ability to use digital devices properly. Digital literacy comprises a variety of cognitive skills that are utilized when teaching or learning at a distance, such as the ability to divide attention between students in an online lecture, the ability to teach effectively in a non-linear environment, and the ability decipher information from visual representations, as in user interfaces. In fact, digital literacy has become today a "survival skill" for present-days teachers that use technology for instruction; a key that helps them to employ successfully complex instructional strategies in their teaching.
IFIP educational activities
Authors: Turner A. Joe
Published: September 2007

This is the second in a series of columns about IFIP, the International Federation for Information Processing. In the previous (December 2006) column, we discussed the general organization and scope of IFIP. IFIP's members are computing societies, one per country except for the USA, where both ACM and the IEEE Computer Society are members.
Cutting apron strings
Authors: Astrachan Owen
Published: September 2007

Moore's law tells us there has been more than a thousand-fold increase in computing power in the last twenty years. Most of us likely search our library and (without too much exaggeration) the world while we sit in a chair and type. The Human Genome Project and the Sloan Digital Sky Survey are using the fruits of computer science to map the genome and the universe. The open source development model has transformed software development, commerce, and science. Many of us argue the merits of emacs compared to v1, why objects-first has failed, and whether induction should precede recursion.
Something is wrong with this picture
.
New alliances and continuing excellence
Authors: Popyack Jeffrey
Published: September 2007

Greetings, and welcome again to Upsilon Pi Epsilon (UPE), the International Honor Society for the Computing and Information Disciplines. This year has seen some revisions in operating procedures, along with new chapters, a new alliance, and another bumper crop of awards to deserving students. Probably the most exciting of our changes is the hope of bringing a regular presence to the SIGCSE winter meeting. When the ACM Computer Science Conference (CSC) ceased its annual operation a decade ago, it left the International Computer Programming Contest (ICPC) and UPE National Meeting without a home. For many reasons, largely fiscal matters and UPE's role in founding the ICPC, the National Meeting has followed the ICPC. Unfortunately, with SIGCSE and ICPC strong enough to stand on their own without the former "Computing Week" umbrella, these activities eventually diverged, leaving us with very little connection to SIGCSE aside from an occasional booth, and of course this column. Fortunately, we are planning to test the waters at SIGCSE 2008, which should bring us together with our most natural constituency, computer science educators. See you there!
Reflections on teaching discrete math for the first time
Authors: Henderson Peter B.
Published: September 2007

You may recall that the guest authors for the last Math CountS column were Rachelle DeCoste and Kevin L. Huggins, United States Military Academy at West Point. Rachelle and Kevin were each teaching, for the first time, a section of discrete mathematics for cadets majoring in computer science. Their contribution, "Teaching Discrete Math for the First Time" described their thoughts and methods of preparing to teach this course for the Fall 2006 team. That was to be the first of two columns they will be contributing --- before and after. Well, the "after" column was a bit longer than anticipated, so they have submitted it as a regular SIGCSE
inroads
paper entitled "Reflections on Teaching Discrete Math for the First Time". Please look for it in this issue, and I hope you will take some time to read the article. You will find it very interesting and informative.
Domino arrangements
Authors: Ginat David
Published: September 2007

The current issue's new challenge involves the development of elegant recursive formulas. Recursive formulation requires the specification of a task instance by smaller task instances. Suitable and insightful points of view may yield elegant and concise specifications. The challenge requires such points of view, in three levels of difficulty.
Nifty reflections
Authors: Parlante Nick
Published: September 2007

Nifty Assignments are nice and everything, but it's natural to wonder: Where are Nifty Assignments weakest?
Reflections on teaching discrete math for the first time
Authors: Huggins Kevin L. , DeCoste Rachelle
Published: September 2007

Teaching a class for the first time is always a challenge. Add to the new experience a team-teaching approach and a professor teaching outside of his comfort zone, and things get even more complicated. In this article we evaluate our team-teaching of Discrete Math to computer science majors at the United States Military Academy. We share the aspects of the course that we think were successful as well as those that we would alter the next time around. This article should help any instructor as he/she prepares to teach a new course, particularly one in discrete mathematics.
Failure rates in introductory programming
Authors: Bennedsen Jens , Caspersen Michael E.
Published: September 2007

It is a common conception that CS1 is a very difficult course and that failure rates are high. However, until now there has only been anecdotal evidence for this claim. This article reports on a survey among institutions around the world regarding failure rates in introductory programming courses. The article describes the design of the survey and the results. The number of institutions answering the call for data was unfortunately rather low, so it is difficult to make firm conclusions. It is our hope that this article can be the starting point for a systematic collection of data in order to find solid proof of the actual failure and pass rates of CS1.
Attitudes and beliefs about computer science among students and faculty
Authors: Lewis Clayton
Published: September 2007

What students think about a discipline --- its structure, usefulness, and how it can be learned --- plays an important role in shaping how they approach it. Just as faculty aim to have students learn the facts and skills of a discipline, so they may also want to shape students' beliefs and attitudes. This study reports the attitudes of undergraduate computer science students early and late in the curriculum, and compares them with the beliefs and attitudes of faculty in the same department. The results show where students think what faculty would like them to think, where they do not, and whether there is evidence that senior students agree more or less with faculty than do students in introductory courses. The results can guide curricular improvements.
Integrating reflective writing in CS/IS
Authors: Stone Jeffrey A. , Madigan Elinor M.
Published: September 2007

The ability to communicate effectively is a critical attribute for graduates of CS/IS programs. A challenge for CS/IS educators is how best to create experiential learning activities for students that allow for enhanced learning outcomes. In this paper we summarize a set of experiential learning activities coupled with the use of reflective writing. These activities are designed to build cognitive connections between academic theory and real-world applications. Sample experiences for both the freshmen and upper division levels are described, as well as discussion of and the results obtained from reflective writing activities.
Putting the
science
into computer science
Authors: Solomon Justin
Published: September 2007

This paper describes why the study of algorithms should be a fundamental component of the standard introductory computer science (CS) curriculum. By shifting the focus of basic CS classes from
implementation
to
concept
, educators can greatly enhance student understanding and course relevance despite rapidly-changing paradigms, technologies, and programming languages. Teaching algorithms also encourages the development of other more generalized skills, including the scientific method, problem-solving, modeling, and technical communication.
Braided learning
Authors: Preston Christina
Published: September 2007

This short paper highlights some of the features of online debate in an established international e-community of practice, The MirandaNet Fellowship. The debate started by an ICT co-coordinator who requested members online to send evidence within twenty-four hours that will prevent his head from banning social software on the school network. Salient features of this braided text include the variety of participant perspectives, the range of responses from different cultures, the pragmatic experience expressed and the demands for action. In the future, wikis might provide the best environment for deeper online collaboration.
An open source software culture in the undergraduate computer science curriculum
Authors: Dionisio John David N. , Dickson Caskey L. , August Stephanie E. , Dorin Philip M. , Toal Ray
Published: September 2007

Open source software has made inroads into mainstream computing where it was once the territory of software altruists, and the open source culture of technological collegiality and accountability may benefit education as well as industry. This paper describes the
Recourse
project, which seeks to transform the computer science undergraduate curriculum through teaching methods based on open source principles, values, ethics, and tools.
Recourse
differs from similar projects by bringing the open source culture into the curriculum comprehensively, systematically, and institutionally. The current state of the project is described, and initial results from a pilot exercise are presented.
(1)
Java visual debugger
Authors: Rafieymehr Ali , McKeever Richard
Published: September 2007

We have developed a visual debugger for Java programs (JVD) that makes use of smooth continuous graphical animation and runtime state history retention to display program state during execution, in order to consider the viability of this approach in the context of both software engineering and computer science education.
A low-cost PIC unit for teaching computer hardware fundamentals to undergraduates
Authors: Sarkar Nurul I. , Craig Trevor M.
Published: September 2007

This paper describes a low-cost PIC16F84-based system suitable for classroom demonstrations and laboratory projects in undergraduate computer hardware courses. The effectiveness of this system as an aid to student learning and comprehension is also discussed.
IREEL
Authors: Dairaine Laurent , Jourjon Guillaume , Lochin Emmanuel , Ardon Sebastien
Published: September 2007

This paper presents a novel e-learning platform called IREEL. IREEL is a virtual laboratory allowing students to drive experiments with real Internet applications and end-to-end protocols in the context of networking courses. This platform consists in a remote network emulator offering a set of pre-defined applications and protocol mechanisms. Experimenters configure and control the emulation and the end-systems behavior in order to perform tests, measurements, and observations on protocols or applications operating under controlled specific networking conditions. A set of end-to-end mechanisms, mainly focusing on transport and application-level protocols, are currently available. IREEL is scalable and easy to use thanks to an ergonomic web interface.
Search engine ranking efficiency evaluation tool
Authors: Alhalabi Wadee S. , Kubat Miroslav , Tapia Moiez
Published: September 2007

In view of the recent progress in the field of internet search engines, there is a growing need for mechanisms to evaluate the performance of these useful and popular tools. So far, the vast majority of researchers have relied on the information-retrieval metrics of "precision" and "recall" that quantify the occurrence of "hits" and "misses" in the returned list of documents. What they fail to do is to measure the quality of the ranking that the search engine has provided. This paper wants to rectify the situation. We discuss the issue in some detail, and then propose a new mechanism that we believe is better suited for our needs.
Revisiting novice programmer errors
Authors: Yarmish Gavriel , Kopec Danny
Published: September 2007

Although programmer errors have been investigated, only a limited range of error types typically made by novices have been scrutinized. In this paper we present an expanded classification of the types of errors considered in previous research. In particular, problems which require the use of more difficult program constructs such as nested loops, arrays, recursion and functions have been somewhat neglected. We hope this paper will encourage other researchers to further analyze the types of errors advanced novices will make and the types of misunderstandings which underlie such errors.
Learning computer programming and role of errors in design
Authors: Lomako Gennady
Published: September 2007

Computer programming teaching should include problem analysis and a hierarchical decomposition of objects and actions that enable programmers to develop meaningful models of objects and multi-layered interfaces and thus be able to choose the level of complexity and protection they need. Programmers are expected to use error-detecting and correcting codes. Application development should include evaluation methods that could assess design solutions during program development and avoid errors during program execution. We discuss a software development and test diagram and programming project requirements.
Reducing medical errors using secure RFID technology
Authors: Anshel Michael , Levitan Sarah
Published: September 2007

RFID technology can successfully be used to reduce medical errors. This technology can aid in the accurate matching of patients with their medications and treatments. The enthusiasm for using RFID technology in medical settings has been tempered by privacy concerns. We discuss new encryption methods that address these concerns.
Vulnerabilities of RFID systems in infant abduction protection and patient wander prevention
Authors: Saad Mohamed K. , Ahamed Syed V.
Published: September 2007

This paper presents penetration attacks and abduction drills conducted in a healthcare facility relying on RFID security system to prevent infant abduction and patient wander. The objective is to provide a better understanding to the limitations and weaknesses existing in the current used technology that is applied in different hospitals, and to provide guidelines for healthcare facility administration to change their policies in a way that cover vulnerabilities that exist in the current RFID security systems.
Redundant features of design in blackboard (LMS) and user error
Authors: Quarless D. A.
Published: September 2007

Assessment has become a ubiquitous and iterative activity of education. Instructional computing in its simplest terms involves the creation of integrated toolkits (resources) for use in the learning process. The increasing prevalence of Learning/Course Management Systems in higher education is providing some new opportunities to explore and assess the design of such systems in reaching their purpose as integrated platforms that create online learning environments. Certain web-based design features have some likeliness to result in user errors. Blackboard is such a case study.
Design error and reusabilty
Authors: Small Margot
Published: September 2007

Failure to account for the placement of components of a complex system on different servers leads to problems in reusability. We examine a case involving an Enterprise JavaBean (EJB) application using Java 2 Platform, Enterprise Edition (J2EE). In creating an EJB entity bean class to represent persistent data, the designer assumed that all EJB client objects would be local. Attempts by developers, whose programs were on another server, to create an entity bean object, failed. Lack of documentation by the original designer and lack of training in use of entity beans led to long delays in construction of new applications.
JIT instrumentation
Authors: Olszewski Marek , Mierle Keir , Czajkowski Adam , Brown Angela Demke
Published: September 2007

As modern operating systems become more complex, understanding their inner workings is increasingly difficult. Dynamic kernel instrumentation is a well established method of obtaining insight into the workings of an OS, with applications including debugging, profiling and monitoring, and security auditing. To date, all dynamic instrumentation systems for operating systems follow the probe-based instrumentation paradigm. While efficient on fixed-length instruction set architectures, probes are extremely expensive on variable-length ISAs such as the popular Intel x86 and AMD x86-64. We propose using just-in-time (JIT) instrumentation to overcome this problem. While common in user space, JIT instrumentation has not until now been attempted in kernel space. In this work, we show the feasibility and desirability of kernel-based JIT instrumentation for operating systems with our novel prototype, implemented as a Linux kernel module. The prototype is fully SMP capable. We evaluate our prototype against the popular Kprobes Linux instrumentation tool. Our prototype outperforms Kprobes, at both micro and macro levels, by orders of magnitude when applying medium- and fine-grained instrumentation.
Whodunit
Authors: Chanda Anupam , Cox Alan L. , Zwaenepoel Willy
Published: September 2007

This paper is concerned with performance debugging of multi-tier applications, such as commonly found in servers and dynamic-content web sites. Existing tools and techniques for profiling such applications are not general enough to track and profile transactions in a generic multi-tier application. We propose transactional profiling that provides a general solution to this problem. We provide novel algorithms and techniques to track and profile transactions that flow through shared memory, events, stages or via interprocess communication using messages. We also measure interference among concurrent transactions.

We describe the design and implementation of Whodunit, our prototype transactional profiler. We demonstrate the correctness of our proposed algorithm for tracking transaction flow through shared memory using Apache and MySQL. Using Whodunit we are able to track and profile transactions that flow through shared memory, events, stages or via message passing, and measure the interference among concurrent transactions. We illustrate the use of Whodunit in obtaining the transactional profile of web servers, a web proxy cache and a bookstore application.
Exploiting nonstationarity for performance prediction
Authors: Stewart Christopher , Kelly Terence , Zhang Alex
Published: September 2007

Real production applications ranging from enterprise applications to large e-commerce sites share a crucial but seldom-noted characteristic: The relative frequencies of transaction types in their workloads are
nonstationary
, i.e., the transaction mix changes over time. Accurately predicting application-level performance in business-critical production applications is an increasingly important problem. However, transaction mix nonstationarity casts doubt on the practical usefulness of prediction methods that ignore this phenomenon.

This paper demonstrates that transaction mix nonstationarity
enables
a new approach to predicting application-level performance as a function of transaction mix. We exploit nonstationarity to circumvent the need for invasive instrumentation and controlled benchmarking during model calibration; our approach relies solely on lightweight passive measurements that are routinely collected in today's production environments. We evaluate predictive accuracy on two real business-critical production applications. The accuracy of our response time predictions ranges from 10% to 16% on these applications, and our models generalize well to workloads very different from those used for calibration.

We apply our technique to the challenging problem of predicting the impact of application consolidation on transaction response times. We calibrate models of two testbed applications running on dedicated machines, then use the models to predict their performance when they run together on a shared machine and serve very different workloads. Our predictions are accurate to within 4% to 14%. Existing approaches to consolidation decision support predict post-consolidation
resource utilizations
. Our method allows
application-level performance
to guide consolidation decisions.
Thread clustering
Authors: Tam David , Azimi Reza , Stumm Michael
Published: September 2007

The major chip manufacturers have all introduced chip multiprocessing (CMP) and simultaneous multithreading (SMT) technology into their processing units. As a result, even low-end computing systems and game consoles have become shared memory multiprocessors with L1 and L2 cache sharing within a chip. Mid- and large-scale systems will have multiple processing chips and hence consist of an SMP-CMP-SMT configuration with non-uniform data sharing overheads. Current operating system schedulers are not aware of these new cache organizations, and as a result, distribute threads across processors in a way that causes many unnecessary, long-latency cross-chip cache accesses.

In this paper we describe the design and implementation of a scheme to schedule threads based on sharing patterns detected online using features of standard performance monitoring units (PMUs) available in today's processing units. The primary advantage of using the PMU infrastructure is that it is fine-grained (down to the cache line) and has relatively low overhead. We have implemented our scheme in Linux running on an 8-
way
Power5 SMP-CMP-SMT multi-processor. For commercial multithreaded server workloads (VolanoMark, SPECjbb, and RUBiS), we are able to demonstrate reductions in cross-chip cache accesses of up to 70%. These reductions lead to application-reported performance improvements of up to 7%.
Latency and bandwidth-minimizing failure detectors
Authors: So Kelvin C. W. , Sirer Emin Gün
Published: September 2007

Failure detectors are fundamental building blocks in distributed systems.
Multi-node failure detectors
, where the detector is tasked with monitoring
N
other nodes, play a critical role in overlay networks and peer-to-peer systems. In such networks, failures need to be detected quickly and with low overhead. Achieving these properties simultaneously poses a difficult tradeoff between detection latency and resource consumption.

In this paper, we examine this central tradeoff, formalize it as an optimization problem and analytically derive the optimal closed form formulas for multi-node failure detectors. We provide two variants of the optimal solution for optimality metrics appropriate for two different deployment scenarios. √
s-LM
is a
latency-minimizing
optimal failure detector that achieves the lowest average failure detection latency given a fixed bandwidth constraint for system maintenance. √
s-BM
is a
bandwidth-minimizing
optimal failure detector that meets a desired detection latency target with the least amount of bandwidth consumed. We evaluate our optimal results with node lifetimes chosen from bimodal and Pareto distributions, as well as real-world trace data from PlanetLab hosts, web sites and Microsoft PCs. Compared to standard failure detectors in wide use, √
s
failure detectors reduce failure detection latencies by 40% on average for the same bandwidth consumption, or conversely, reduce the amount of bandwidth consumed by 30% for the same failure detection latency.
Removing the memory limitations of sensor networks with flash-based virtual memory
Authors: Lachenmann Andreas , Marrón Pedro José , Gauger Matthias , Minder Daniel , Saukh Olga , Rothermel Kurt
Published: September 2007

Virtual memory has been successfully used in different domains to extend the amount of memory available to applications. We have adapted this mechanism to sensor networks, where, traditionally, RAM is a severely constrained resource. In this paper we show that the overhead of virtual memory can be significantly reduced with compile-time optimizations to make it usable in practice, even with the resource limitations present in sensor networks.

Our approach,
ViMem
, creates an efficient memory layout based on variable access traces obtained from simulation tools. This layout is optimized to the memory access patterns of the application and to the specific properties of the sensor network hardware.

Our implementation is based on TinyOS. It includes a pre-compiler for nesC code that translates virtual memory accesses into calls of
ViMem's
runtime component.
ViMem
uses flash memory as secondary storage. In order to evaluate our system we have modified nontrivial existing applications to make use of virtual memory. We show that its runtime overhead is small even for large data sizes.
A virtual machine for sensor networks
Authors: Müller René , Alonso Gustavo , Kossmann Donald
Published: September 2007

Sensor networks are increasingly being deployed for a wide variety of tasks. Today, in these networks, the development, deployment, and maintenance of applications are performed largely ad-hoc. Existing platforms help somewhat but also introduce implicit trade-offs. In one extreme, low-level programming platforms and languages make programming cumbersome and error-prone. In the other extreme, declarative approaches greatly facilitate programming but restrict what can be done. In both cases, additional limitations include lack of support for concurrency, difficulties in changing applications, and insufficient abstractions from low-level details. This paper presents SwissQM, a virtual machine designed to address all these limitations. SwissQM offers a platform-independent programming abstraction that is geared towards data acquisition and in-network data processing.
Macroprogramming heterogeneous sensor networks using cosmos
Authors: Awan Asad , Jagannathan Suresh , Grama Ananth
Published: September 2007

In this paper, we present COSMOS, a novel architecture for macroprogramming heterogeneous sensor network systems. Macroprogramming specifies aggregate system behavior, as opposed to device-specific programs that code distributed behavior using explicit messaging. COSMOS is comprised of a macroprogramming language,
mPL
, and an operating system,
mOS
. mPL macroprograms are statically verifiable compositions of reusable user-specified, or system supported
functional components
. The mOS node/network operating system provides component management and a lean execution environment for mPL programs in heterogeneous resource-constrained sensor networks. It provides runtime application instantiation, with over-the-air reprogramming of the network. COSMOS facilitates composition of complex real-world applications that are robust, scalable and adaptive in dynamic data-driven sensor network environments. An important and novel aspect of COSMOS is the ability to easily extend its component basis library to add rich macroprogramming abstractions to mPL, tailored to domain and resource constraints, without modifications to the OS. Applications built on COSMOS are currently in use at the Bowen Labs for Structural Engineering, in Purdue University, for high-fidelity structural monitoring. We present a detailed description of the COSMOS architecture, its various components, and a comprehensive experimental evaluation using macro- and micro- benchmarks to demonstrate performance characteristics of COSMOS.
Secure file system versioning at the block level
Authors: Wires Jake , Feeley Michael J.
Published: September 2007

In typical file systems, valuable data is vulnerable to being accidentally or maliciously deleted or overwritten. Versioning file systems protect data from accidents by transparently retaining old versions, but do less well in protecting data from malicious attack. These systems remain vulnerable to attackers who gain unauthorized access to prune old file versions, who bypass the file system to directly manipulate storage, or who exploit bugs in any part of the operating system.

This paper presents VDisk, a secure, block-level versioning system that adds file-grain versioning to a standard, unmodified file system. VDisk consists of a set of untrusted user-mode tools and a trusted, secure kernel that is implemented within an isolated Xen virtual machine domain. The secure kernel is designed to be simple and thus trustworthy. This kernel logs file-system updates to a secure log, exports a read-only view of the log to the rest of the system and securely removes unwanted versions from the log. Secure cleaning is implemented in a two-level manner. An untrusted, user-mode cleaner selects log entries for reclamation and submits cleaning requests to the trusted VDisk kernel along with a proof that the request satisifies the device's version-retention policy. The secure kernel verifies the proof and updates the log.
Automatic configuration of internet services
Authors: Zheng Wei , Bianchini Ricardo , Nguyen Thu D.
Published: September 2007

Recent research has found that operators frequently misconfigure Internet services, causing various availability and performance problems. In this paper, we propose a software infrastructure that eliminates several types of misconfiguration by automating the generation of configuration files in Internet services, even as the services evolve. The infrastructure comprises a custom scripting language, configuration file templates, communicating runtime monitors, and heuristic algorithms to detect dependencies between configuration parameters and select ideal configurations. To demonstrate our infrastructure experimentally, we apply it to a realistic online auction service. Our results show that the infrastructure can simplify operation significantly while eliminating 58% of the misconfigurations found in a previous study of the same service. Furthermore, our results show that the infrastructure can efficiently determine the configuration parameters that lead to high performance as the service evolves through a hardware upgrade and the scheduled maintenance of a few nodes.
Concierge
Authors: Rellermeyer Jan S. , Alonso Gustavo
Published: September 2007

As mobile and embedded devices become widespread, the management and configuration of the software in the devices is increasingly turning into a critical issue. OSGi is a business standard for the life cycle management of Java software components. It is based on a service oriented architecture where functional units are decoupled and components can be managed independently of each other. However, the focus continuously shifts from the originally intended area of small and embedded devices towards large-scaled enterprise systems. As a result, implementations of the OSGi framework are increasingly becoming more heavyweight and less suitable for smaller computing devices. In this paper, we describe the experience gathered during the design of Concierge, an implementation of the OSGi specification tailored to resource-constrained devices. Comprehensive benchmarks show that Concierge performs better than existing implementations and consumes less resources.
Adaptive control of virtualized resources in utility computing environments
Authors: Padala Pradeep , Shin Kang G. , Zhu Xiaoyun , Uysal Mustafa , Wang Zhikui , Singhal Sharad , Merchant Arif , Salem Kenneth
Published: September 2007

Data centers are often under-utilized due to over-provisioning as well as time-varying resource demands of typical enterprise applications. One approach to increase resource utilization is to consolidate applications in a shared infrastructure using virtualization. Meeting application-level quality of service (QoS) goals becomes a challenge in a consolidated environment as application resource needs differ. Furthermore, for multi-tier applications, the amount of resources needed to achieve their QoS goals might be different at each tier and may also depend on availability of resources in other tiers. In this paper, we develop an adaptive resource control system that dynamically adjusts the resource shares to individual tiers in order to meet application-level QoS goals while achieving high resource utilization in the data center. Our control system is developed using classical control theory, and we used a black-box system modeling approach to overcome the absence of first principle models for complex enterprise applications and systems. To evaluate our controllers, we built a testbed simulating a virtual data center using Xen virtual machines. We experimented with two multi-tier applications in this virtual data center: a two-tier implementation of RUBiS, an online auction site, and a two-tier Java implementation of TPC-W. Our results indicate that the proposed control system is able to maintain high resource utilization and meets QoS goals in spite of varying resource demands from the applications.
STMBench7
Authors: Guerraoui Rachid , Kapalka Michal , Vitek Jan
Published: September 2007

Software transactional memory (STM) is a promising technique for controlling concurrency in modern multi-processor architectures. STM aims to be more scalable than explicit coarse-grained locking and easier to use than fine-grained locking. However, STM implementations have yet to demonstrate that their runtime overheads are acceptable. To date, empiric evaluations of these implementations have suffered from the lack of realistic benchmarks. Measuring performance of an STM in an overly simplified setting can be at best uninformative and at worst misleading as it may steer researchers to try to optimize irrelevant aspects of their implementations.

This paper presents STMBench7: a candidate benchmark for evaluating STM implementations. The underlying data structure consists of a set of graphs and indexes intended to be suggestive of many complex applications, e.g., CAD/CAM. A collection of operations is supported to model a wide range of workloads and concurrency patterns. Companion locking strategies serve as a baseline for STM performance comparisons. STMBench7 strives for simplicity. Users may choose a workload, number of threads, benchmark length, as well as the possibility of structure modification and the nature of traversals of shared data structures. We illustrate the use of STMBench7 with an evaluation of a well-known software transactional memory implementation.
Dynamic and adaptive updates of non-quiescent subsystems in commodity operating system kernels
Authors: Makris Kristis , Ryu Kyung Dong
Published: September 2007

Continuously running systems require kernel software updates applied to them without downtime. Facilitating fast reboots, or delaying an update may not be a suitable solution in many environments, especially in pay-per-use high-performance computing clusters and mission critical systems. Such systems will not reap the benefits of new kernel features, and will continue to operate with kernel security holes unpatched, at least until the next scheduled maintenance downtime. To address these problems we developed an on-the-fly kernel updating system that enables commodity operating systems to gain adaptive and mutative capabilities without kernel recompilation or reboot. Our system, DynAMOS, employs a novel and efficient dynamic code instrumentation technique termed
adaptive function cloning
. Execution flow can be switched adaptively among multiple editions of functions, possibly concurrently running. This approach becomes the foundation for dynamic replacement of non-quiescent kernel subsystems when the timeliness of an update depends on synchronization of multiple kernel paths. We illustrate our experience by dynamically updating core subsystems of the Linux kernel.
Sealing OS processes to improve dependability and safety
Authors: Hunt Galen , Aiken Mark , Fähndrich Manuel , Hawblitzel Chris , Hodson Orion , Larus James , Levi Steven , Steensgaard Bjarne , Tarditi David , Wobber Ted
Published: September 2007

In most modern operating systems, a process is a hardware-protected abstraction for isolating code and data. This protection, however, is selective. Many common mechanisms---dynamic code loading, run-time code generation, shared memory, and intrusive system APIs---make the barrier between processes very permeable. This paper argues that this traditional
open process architecture
exacerbates the dependability and security weaknesses of modern systems.

As a remedy, this paper proposes a
sealed process architecture
, which prohibits dynamic code loading, self-modifying code, shared memory, and limits the scope of the process API. This paper describes the implementation of the sealed process architecture in the Singularity operating system, discusses its merits and drawbacks, and evaluates its effectiveness. Some benefits of this sealed process architecture are: improved program analysis by tools, stronger security and safety guarantees, elimination of redundant overlaps between the OS and language runtimes, and improved software engineering.

Conventional wisdom says open processes are required for performance; our experience suggests otherwise. We present the first macrobenchmarks for a sealed-process operating system and applications. The benchmarks show that an experimental sealed-process system can achieve performance competitive with highly-tuned, commercial, open-process systems.
Sprint
Authors: Camargos Lásaro , Pedone Fernando , Wieloch Marcin
Published: September 2007

Sprint is a middleware infrastructure for high performance and high availability data management. It extends the functionality of a standalone in-memory database (IMDB) server to a cluster of commodity shared-nothing servers. Applications accessing an IMDB are typically limited by the memory capacity of the machine running the IMDB. Sprint partitions and replicates the database into segments and stores them in several data servers. Applications are then limited by the aggregated memory of the machines in the cluster. Transaction synchronization and commitment rely on total-order multicast. Differently from previous approaches, Sprint does not require accurate failure detection to ensure strong consistency, allowing fast reaction to failures. Experiments conducted on a cluster with 32 data servers using TPC-C and a micro-benchmark showed that Sprint can provide very good performance and scalability.
Tashkent+
Authors: Elnikety Sameh , Dropsho Steven , Zwaenepoel Willy
Published: September 2007

We present a
memory-aware
load balancing (MALB) technique to dispatch transactions to replicas in a replicated database. Our MALB algorithm exploits knowledge of the working sets of transactions to assign them to replicas in such a way that they execute in main memory, thereby reducing disk I/O. In support of MALB, we introduce a method to estimate the size and the contents of transaction working sets. We also present an optimization called
update filtering
that reduces the overhead of update propagation between replicas.

We show that MALB greatly improves performance over other load balancing techniques -- such as round robin, least connections, and locality-aware request distribution (LARD) -- that do not use explicit information on how transactions use memory. In particular, LARD demonstrates good performance for read-only static content Web workloads, but it gives performance inferior to MALB for database workloads as it does not efficiently handle large requests. MALB combined with update filtering further boosts performance over LARD.

We build a prototype replicated system, called Tashkent+, with which we demonstrate that MALB and update filtering techniques improve performance of the TPC-W and RUBiS benchmarks. In particular, in a 16-replica cluster and using the ordering mix of TPC-W, MALB doubles the throughput over least connections and improves throughput 52% over LARD. MALB with update filtering further improves throughput to triple that of least connections and more than double that of LARD. Our techniques exhibit super-linear speedup; the throughput of the 16-replica cluster is 37 times the peak throughput of a standalone database due to better use of the cluster's memory.
Forth & small systems report
Authors: Frenger Paul
Published: September 2007

In July 2005 I ran across an ad in
Electronic Products
[1] for an optical mouse sensor by Agilent Technologies. Like many people, I find using an optical mouse to be superior to the old ball-in-a-cage type mouse (which I first saw demonstrated on the Xerox
Star
workstation at the National Computer Conference in Dallas, June 1976). Inevitably, I was curious to learn what makes it tick (or "squeak") ... that's my
Tinkertoy®
mentality at work. I clipped the article, filed it and totally forgot about it until recently.