bluuebunny/crossref_metadata_2025 huggingface dataset:
Caching and incrementalisation in the java query language
Authors: Willis Darren , Pearce David J. , Noble James
Published: October 2008

Many contemporary object-oriented programming languages support first-class queries or comprehensions. These language extensions make it easier for programmers to write queries, but are generally implemented no more efficiently than the code using collections, iterators, and loops that they replace. Crucially, whenever a query is re-executed, it is recomputed from scratch. We describe a general approach to optimising queries over mutable objects: query results are cached, and those caches are incrementally maintained whenever the collections and objects underlying those queries are updated. We hope that the performance benefits of our optimisations may encourage more general adoption of first-class queries by object-oriented programmers.
Interprocedural query extraction for transparent persistence
Authors: Wiedermann Ben , Ibrahim Ali , Cook William R.
Published: October 2008

Transparent persistence promises to integrate programming languages and databases by allowing programs to access persistent data with the same ease as non-persistent data. In this work we demonstrate the feasibility of optimizing transparently persistent programs by extracting queries to efficiently prefetch required data. A static analysis derives query structure and conditions across methods that access persistent data. Using the static analysis, our system transforms the program to execute explicit queries. The transformed program composes queries across methods to handle method calls that return persistent data. We extend an existing Java compiler to implement the static analysis and program transformation, handling recursion and parameterized queries. We evaluate the effectiveness of query extraction on the OO7 and TORPEDO benchmarks. This work is focused on programs written in the current version of Java, without languages changes. However, the techniques developed here may also be of value in conjunction with object-oriented languages extended with high-level query syntax.
Deep typechecking and refactoring
Authors: Tatlock Zachary , Tucker Chris , Shuffelton David , Jhala Ranjit , Lerner Sorin
Published: October 2008

Large software systems are typically composed of multiple layers, written in different languages and loosely coupled using a string-based interface. For example, in modern web-applications, a server written in Java communicates with a database back-end by passing in query strings. This widely prevalent approach is unsafe as the analyses developed for the individual layers are oblivious to the semantics of the dynamically constructed strings, making it impossible to statically reason about the correctness of the interaction. Further, even simple refactoring in such systems is daunting and error prone as the changes must also be applied to isolated string fragments scattered across the code base.

We present techniques for deep typechecking and refactoring for systems that combine Java code with a database back-end using the Java Persistence API [10]. Deep typechecking ensures that the queries that are constructed dynamically are type safe and that the values returned from the queries are used safely by the program. Deep refactoring builds upon typechecking to allow programmers to safely and automatically propagate code refactorings through the query string fragments.

Our algorithms are implemented in a tool called QUAIL. We present experiments evaluating the effectiveness of QUAIL on several benchmarks ranging from 3,369 to 82,907 lines of code.We show that QUAIL is able to verify that 84% of query strings in our benchmarks are type safe. Finally, we show that QUAIL reduces the number of places in the code that a programmer must look at in order to perform a refactoring by several orders of magnitude.
Join patterns for visual basic
Authors: Russo Claudio V.
Published: October 2008

We describe an extension of Visual Basic 9.0 with asynchronous concurrency constructs - join patterns - based on the join calculus. Our design of Concurrent Basic (CB) builds on earlier work on Polyphonic C# and Comega. Since that work, the need for language-integrated concurrency has only grown, both due to the arrival of commodity, multi-core hardware, and the trend for Rich Internet Applications that rely on asynchronous client-server communication to hide latency. Unlike its predecessors, CB adopts an event-like syntax that should be familiar to existing VB programmers. Coupled with Generics, CB allows one to declare re-useable concurrency abstractions that were clumsy to express previously. CB removes its ancestors' inconvenient inheritance restriction, while providing new extensibility points useful in practical applications that must co-exist with or want to exploit alternative threading models available on the platform. CB is implemented as an extension of the production VB 9.0 compiler.
Jolt
Authors: Shankar Ajeet , Arnold Matthew , Bodik Rastislav
Published: October 2008

It has been observed that component-based applications exhibit
object churn
, the excessive creation of short-lived objects, often caused by trading performance for modularity. Because churned objects are short-lived, they appear to be good candidates for stack allocation. Unfortunately, most churned objects escape their allocating function, making escape analysis ineffective.

We reduce object churn with three contributions. First, we formalize two measures of churn,
capture
and
control
(15). Second, we develop lightweight dynamic analyses for measuring both
capture
and
control
. Third, we develop an algorithm that uses
capture
and
control
to inline portions of the call graph to make churned objects non-escaping, enabling churn optimization via escape analysis.

JOLT is a lightweight dynamic churn optimizer that uses our algorithms. We embedded JOLT in the JIT compiler of the IBM J9 commercial JVM, and evaluated JOLT on large application frameworks, including Eclipse and JBoss. We found that JOLT eliminates over 4 times as many allocations as a state-of-the-art escape analysis alone.
Annotation refactoring
Authors: Tansey Wesley , Tilevich Eli
Published: October 2008

Since annotations were added to the Java language, many frameworks have moved to using annotated Plain Old Java Objects (POJOs) in their newest releases. Legacy applications are thus forced to undergo extensive restructuring in order to migrate from old framework versions to new versions based on annotations (
Version Lock-in
). Additionally, because annotations are embedded in the application code, changing between framework vendors may also entail largescale manual changes (
Vendor Lock-in
).

This paper presents a novel refactoring approach that effectively solves these two problems. Our approach infers a concise set of semantics-preserving transformation rules from two versions of a single class. Unlike prior approaches that detect only simple structural refactorings, our algorithm can infer general composite refactorings and is more than 97% accurate on average. We demonstrate the effectiveness of our approach by automatically upgrading more than 80K lines of the unit testing code of four open-source Java applications to use the latest version of the popular JUnit testing framework.
Analysis and reduction of memory inefficiencies in Java strings
Authors: Kawachiya Kiyokuni , Ogata Kazunori , Onodera Tamiya
Published: October 2008

This paper describes a novel approach to reduce the memory consumption of Java programs, by focusing on their "string memory inefficiencies". In recent Java applications, string data occupies a large amount of the heap area. For example, about 40% of the live heap area is used for string data when a production J2EE application server is running. By investigating the string data in the live heap, we identified two types of memory inefficiencies -- "duplication" and "unused literals". In the heap, there are many string objects that have the same values. There also exist many string literals whose values are not actually used by the application. Since these inefficiencies exist as live objects, they cannot be eliminated by existing garbage collection techniques, which only remove dead objects. Quantitative analysis of Java heaps in real applications revealed that more than 50% of the string data in the live heap is wasted by these inefficiencies. To reduce the string memory inefficiencies, this paper proposes two techniques at the Java virtual machine level, "StringGC" for eliminating duplicated strings at the time of garbage collection, and "Lazy Body Creation" for delaying part of the literal instantiation until the literal's value is actually used. We also present an interesting technique at the Java program level, which we call "BundleConverter", for preventing unused message literals from being instantiated. Prototype implementations on a production Java virtual machine have achieved about 18% reduction of the live heap in the production application server. The proposed techniques could also reduce the live heap of standard Java benchmarks by 11.6% on average, without noticeable performance degradation.
Generics of a higher kind
Authors: Moors Adriaan , Piessens Frank , Odersky Martin
Published: October 2008

With Java 5 and C# 2.0, first-order parametric polymorphism was introduced in mainstream object-oriented programming languages under the name of generics. Although the first-order variant of generics is very useful, it also imposes some restrictions: it is possible to abstract over a type, but the resulting type constructor cannot be abstracted over. This can lead to code duplication. We removed this restriction in Scala, by allowing type constructors as type parameters and abstract type members. This paper presents the design and implementation of the resulting type constructor polymorphism. Furthermore, we study how this feature interacts with existing object-oriented constructs, and show how it makes the language more expressive.
The visitor pattern as a reusable, generic, type-safe component
Authors: Oliveira Bruno C.d.S. , Wang Meng , Gibbons Jeremy
Published: October 2008

The V
ISITOR
design pattern shows how to separate the structure of an object hierarchy from the behaviour of traversals over that hierarchy. The pattern is very flexible; this very flexibility makes it difficult to capture the pattern as anything more formal than prose, pictures and prototypes.

We show how to capture the essence of the V
ISITOR
pattern as a reusable software library, by using advanced type system features appearing in modern object-oriented languages such as Scala. We preserve
type-safety statically and modularly
: no reflection or similar mechanisms are used and modules can be independently compiled. The library is
generic
, in two senses: not only is it parametrised by both the return type and the shape of the object hierarchy, but also it allows a number of implementation choices (internal versus external control, imperative versus functional behaviour, orthogonal aspects such as tracing and memoisation) to be specified by parameters rather than fixed in early design decisions. Finally, we propose a generalised
datatype
-like notation,on top of our visitor library: this provides a convenient functional decomposition style in object-oriented languages.
Constrained types for object-oriented languages
Authors: Nystrom Nathaniel , Saraswat Vijay , Palsberg Jens , Grothoff Christian
Published: October 2008

X10 is a modern object-oriented language designed for productivity and performance in concurrent and distributed systems. In this setting, dependent types offer significant opportunities for detecting design errors statically, documenting design decisions, eliminating costly run-time checks (e.g., for array bounds, null values), and improving the quality of generated code.

We present the design and implementation of
constrained types
, a natural, simple, clean, and expressive extension to object-oriented programming: A type C{c} names a class or interface C and a
constraint
c on the immutable state of C and in-scope final variables. Constraints may also be associated with class definitions (representing class invariants) and with method and constructor definitions (representing preconditions). Dynamic casting is permitted. The system is parametric on the underlying constraint system: the compiler supports a simple equality-based constraint system but, in addition, supports extension with new constraint systems using compiler plugins.
Efficient local type inference
Authors: Bellamy Ben , Avgustinov Pavel , de Moor Oege , Sereni Damien
Published: October 2008

Inference of static types for local variables in Java bytecode is the first step of any serious tool that manipulates bytecode, be it for decompilation, transformation or analysis. It is important, therefore, to perform that step as accurately and efficiently as possible. Previous work has sought to give solutions with good worst-case complexity.

We present a novel algorithm, which is optimised for the common case rather than worst-case performance. It works by first finding a set of minimal typings that are valid for all assignments, and then checking whether these minimal typings satisfy all uses. Unlike previous algorithms, it does not explicitly build a data structure of type constraints, and it is easy to implement efficiently. We prove that the algorithm produces a typing that is both sound (obeying the rules of the language) and as tight as possible.

We then go on to present extensive experiments, comparing the results of the new algorithm against the previously best known method. The experiments include bytecode that is generated in other ways than compilation of Java source. The new algorithm is always faster, typically by a factor 6, but on some real benchmarks the gain is as high as a factor of 92. Furthermore, whereas that previous method is sometimes suboptimal, our algorithm always returns a tightest possible type.

We also discuss in detail how we handle primitive types, which is a difficult issue due to the discrepancy in their treatment between Java bytecode and Java source. For the application to decompilation, however, it is very important to handle this correctly.
Efficient software model checking of soundness of type systems
Authors: Roberson Michael , Harries Melanie , Darga Paul T. , Boyapati Chandrasekhar
Published: October 2008

This paper presents novel techniques for checking the soundness of a type system automatically using a software model checker. Our idea is to systematically generate every type correct intermediate program state (within some finite bounds), execute the program one step forward if possible using its small step operational semantics, and then check that the resulting intermediate program state is also type correct--but do so efficiently by detecting similarities in this search space and pruning away large portions of the search space. Thus, given only a specification of type correctness and the small step operational semantics for a language, our system automatically checks type soundness by checking that the progress and preservation theorems hold for the language (albeit for program states of at most some finite size). Our preliminary experimental results on several languages--including a language of integer and boolean expressions, a simple imperative programming language, an object-oriented language which is a subset of Java, and a language with ownership types--indicate that our approach is feasible and that our search space pruning techniques do indeed significantly reduce what is otherwise an extremely large search space. Our paper thus makes contributions both in the area of checking soundness of type systems, and in the area of reducing the state space of a software model checker.
Delegation-based semantics for modularizing crosscutting concerns
Authors: Schippers Hans , Janssens Dirk , Haupt Michael , Hirschfeld Robert
Published: October 2008

We describe semantic mappings of four high-level programming languages to our delegation-based machine model for aspect-oriented programming. One of the languages is a class-based object-oriented one. The other three represent extensions thereof that support various approaches to modularizing crosscutting concerns. We explain informally that an operational semantics expressed in terms of the model's concepts preserves the behavior of a program written in one of the high-level languages. We hence argue our model to be semantically sound in that sense, as well as sufficiently expressive in order to correctly support features such as class-based object-oriented programming, the open-classes and pointcut-and-advice flavors of aspect-oriented programming, and dynamic layers. For the latter, being a core feature of context-oriented programming, we also provide a formal semantics.
A theory of aspects as latent topics
Authors: Baldi Pierre F. , Lopes Cristina V. , Linstead Erik J. , Bajracharya Sushil K.
Published: October 2008

After more than 10 years, Aspect-Oriented Programming (AOP) is still a controversial idea. While the concept of aspects appeals to everyone's intuitions, concrete AOP solutions often fail to convince researchers and practitioners alike. This discrepancy results in part from a lack of an adequate theory of aspects, which in turn leads to the development of AOP solutions that are useful in limited situations.

We propose a new theory of aspects that can be summarized as follows: concerns are latent topics that can be automatically extracted using statistical topic modeling techniques adapted to software. Software scattering and tangling can be measured precisely by the entropies of the underlying topic-over-files and files-over-topics distributions. Aspects are latent topics with high scattering entropy.

The theory is validated empirically on both the large scale, with a study of 4,632 Java projects, and the small scale, with a study of 5 individual projects. From these analyses, we identify two dozen topics that emerge as general-purpose aspects across multiple projects, as well as project-specific topics/concerns. The approach is also shown to produce results that are compatible with previous methods for identifying aspects, and also extends them.

Our work provides not only a concrete approach for identifying aspects at several scales in an unsupervised manner but, more importantly, a formulation of AOP grounded in information theory. The understanding of aspects under this new perspective makes additional progress toward the design of models and tools that facilitate software development.
Towards adaptive programming
Authors: Simpkins Christopher , Bhat Sooraj , Isbell Charles , Mateas Michael
Published: October 2008

Current programming languages and software engineering paradigms are proving insufficient for building intelligent multi-agent systems--such as interactive games and narratives--where developers are called upon to write increasingly complex behavior for agents in dynamic environments. A promising solution is to build adaptive systems; that is, to develop software written specifically to adapt to its environment by changing its behavior in response to what it observes in the world. In this paper we describe a new programming language, An Adaptive Behavior Language (A2BL), that implements adaptive programming primitives to support partial programming, a paradigm in which a programmer need only specify the details of behavior known at code-writing time, leaving the run-time system to learn the rest. Partial programming enables programmers to more easily encode software agents that are difficult to write in existing languages that do not offer language-level support for adaptivity. We motivate the use of partial programming with an example agent coded in a cutting-edge, but non-adaptive agent programming language (ABL), and show how A2BL can encode the same agent much more naturally.
Cyclops
Authors: Chi Ying-Ju , Oliveira Ricardo , Zhang Lixia
Published: October 2008

In this paper we present Cyclops, a system that collects and displays information of AS-level connectivity extracted from looking glasses, route-servers and BGP tables and updates of hundreds of routers across the Internet. From an operational standpoint, Cyclops provides ISPs a view of how their connectivity is perceived from the outside, enabling a comparison between their observed connectivity and their intended connectivity. ISPs can use the tool to detect and diagnose BGP misconfigurations, route leakages or hijacks based on false AS path. From a research standpoint, Cyclops is able to provide a quick snapshot of the AS-level connectivity of each network, and provides mechanisms to infer the root cause of BGP (de)peerings, which is an important input to the study of AS-level topology models and inter-domain routing protocols.
Practical issues with using network tomography for fault diagnosis
Authors: Huang Yiyi , Feamster Nick , Teixeira Renata
Published: October 2008

This paper investigates the practical issues in applying network tomography to monitor failures. We outline an approach for selecting paths to monitor, detecting and confirming the existence of a failure, correlating multiple independent observations into a single failure event, and applying existing binary networking tomography algorithms to identify failures. We evaluate the ability of network tomography algorithms to correctly detect and identify failures in a controlled environment on the VINI testbed.
You must be joking...
Authors: Faloutsos Michalis
Published: October 2008

The proof is in the pudding. Never have truer words been spoken. If only research was a lavish meal that concluded with a pudding. But now, what is a researcher to do?
General writing guidelines for technology and people with disabilities
Authors: Cavender Anna , Trewin Shari , Hanson Vicki
Published: October 2008

The recommendations in this article reflect current thinking on language for writing in the academic accessibility community. Certain words or phrases can (intentionally or unintentionally) reflect bias or negative, disparaging, or patronizing attitudes toward people with disabilities and in fact any identifiable group of people. Because language can convey these things, it can influence our impressions, attitudes, and even actions. Choosing language that is neutral, accurate, and represents the preference of the groups to which it refers can convey respect and integrity.
Image management in a virtualized data center
Authors: Tan Tingxi , Simmonds Rob , Arlt Bradley , Arlitt Martin , Walker Bruce
Published: October 2008

Industrial research firms such as Gartner and IDC are predicting an explosion in the number of online services in the coming years. Virtualization technologies could play an important role in such a world, as they create an opportunity to provide services in a cost-effective manner. However, to achieve ideal savings, more dynamic environments must be created, with Virtual Machines (VMs) being provisioned and altered on-the-fly. Management issues arise when using these elastic resources at scale. In this study, we provide an initial investigation of performance and scalability issues for image management in a virtualized data center. Results provided show that the choice of storage solution and access protocol matters. For example, our tests show the time to start a VM from a local hard drive under I/O intensive workload increases by a factor of 15 and for certain shared storage options, this factor increases to 30 times.
Fine-grained energy profiling for power-aware application design
Authors: Kansal Aman , Zhao Feng
Published: October 2008

Significant opportunities for power optimization exist at application design stage and are not yet fully exploited by system and application designers. We describe the challenges developers face in optimizing software for energy efficiency by exploiting application-level knowledge. To address these challenges, we propose the development of automated tools that profile the energy usage of various resource components used by an application and guide the design choices accordingly. We use a preliminary version of a tool we have developed to demonstrate how automated energy profiling helps a developer choose between alternative designs in the energy-performance trade-off space.
How to parameterize models with bursty workloads
Authors: Casale Giuliano , Mi Ningfang , Cherkasova Ludmila , Smirni Evgenia
Published: October 2008

Although recent advances in theory indicate that burstiness in the service time process can be handled effectively by queueing models (e.g.,MAP queueing networks [2]), there is a lack of understanding and of practical results on how to perform model parameterization, especially when this parameterization must be derived from limited coarse measurements.

We propose a new parameterization methodology based on the index of dispersion of the service process at a server, which is inferred by observing the number of completions within the concatenated busy periods of that server. The index of dispersion together with other measurements that reflect the "estimated" mean and the 95th percentile of service times are used to derive a MAP process that captures well burstiness of the true service process.

Detailed experimentation on a TPC-W testbed where all measurements are obtained via a commercially available tool, the HP (Mercury) Diagnostics, shows that the proposed technique offers a simple yet powerful solution to the difficult problem of inferring accurate descriptors of the service time process from coarse measurements. Experimental and model prediction results are in excellent agreement and argue strongly for the effectiveness of the proposed methodology under bursty or simply variable workloads.
Towards realistic file-system benchmarks with CodeMRI
Authors: Agrawal Nitin , Arpaci-Dusseau Andrea C. , Arpaci-Dusseau Remzi H.
Published: October 2008

Benchmarks are crucial to understanding software systems and assessing their performance. In file-system research, synthetic benchmarks are accepted and widely used as substitutes for more realistic and complex workloads. However, synthetic benchmarks are largely based on the benchmark writer's interpretation of the real workload, and how it exercises the system API. This is insufficient since even a simple operation through the API may end up exercising the file system in very different ways due to effects of features such as caching and prefetching. In this paper, we describe our first steps in creating "realistic synthetic" benchmarks by building a tool, CodeMRI. CodeMRI leverages file-system domain knowledge and a small amount of system profiling in order to better understand how the benchmark is stressing the system and to deconstruct its workload.
Synchronized network emulation
Authors: Weingärtner Elias , Schmidt Florian , Heer Tobias , Wehrle Klaus
Published: October 2008

Network emulation, in which real systems interact with a network simulation, is a common evaluation method in computer networking research. Until now, the simulation in charge of representing the network has been required to be real-time capable, as otherwise a time drift between the simulation and the real network devices may occur and corrupt the results. In this paper, we present our work on synchronized network emulation. By adding a central synchronization entity and by virtualizing real systems for means of control, we can build-up network emulations which contain both unmodified x86 systems and network simulations of any complexity.
What are our standards for validation of measurement-based networking research?
Authors: Krishnamurthy Balachander , Willinger Walter
Published: October 2008

Standards? What standards?
Running applications efficiently in online social networks
Authors: Curry Roger , Kiddle Cameron , Markatchev Nayden , Simmonds Rob , Tan Tingxi , Arlitt Martin , Walker Bruce
Published: October 2008

In the past several years, online social networks (OSNs) such as Facebook and MySpace have become extremely popular with Internet users. Such sites are popular with users because they simplify both communication among "communities" and access to applications. Application developers are attracted to these sites also, as they are able to exploit "word-of-mouth" marketing, which these OSN sites have embodied into their user experience. A challenge for developers though is managing the application, as it is difficult to predict how successful the marketing will be. Our solution combines an OSN, Virtual Appliances, and a utility computing environment together. We demonstrate our solution using the Facebook portal (OSN), the Fire Dynamics Simulator (application), and a utility environment we built using tools such as Condor, Moab and Xen. The application is supported using Virtual Appliances, which interact with our flexible infrastructure to dynamically expand and contract based on user demand. Thus, we are able to make much more efficient use of the underlying physical infrastructure. We believe that our solution also has great potential for enterprise IT environments. Initial feedback suggests combining an OSN with our flexible infrastructure provides a much better user experience than the traditional, standalone use of the (legacy) application, and simplifies the management and increases the effective utilization of the underlying IT resources.
Automatic quality of experience measuring on video delivering networks
Authors: De Vera Daniel , Rodríguez-Bocca Pablo , Rubino Gerardo
Published: October 2008

This article describes a full video delivery network monitoring suite. Our monitoring tool offers a new view of a video delivery network, based on the quality as perceived by final users (what is nowadays called Quality of Experience, in short QoE). We measure the perceived quality at the client side by means of the recently proposed PSQA technology, by studying the video flows at the frame level. The developed monitoring suite is a completely free-software application, based on well-known technologies such as Simple Network Management Protocol or Round Robin Databases, which can be executed in various operating systems. In this short article we explain the tool implementation and we present some of the measurements performed with it.
Continuous monitoring of wide-area wireless networks
Authors: Ormont Justin , Walker Jordan , Banerjee Suman
Published: October 2008

In this work, we present an infrastructure for monitoring and visualizing performance of a wide-area wireless network, We present a unique, vehicle-mounted platform and a testbed for wide-area wireless experimentation. The testbed nodes are mounted on metro transit city buses in Madison, WI, and are currently equipped with both cellular EV-DO* and WiFi interfaces. Our initial goal for this infrastructure is to continuously monitor characteristics and performance of large-scale wireless networks, e.g., city-wide mesh networks or cellular networks. In such networks, customers experience a very large range of geographic and mobility-related radio environments. A vehicle-mounted platform, with fairly deterministic mobility patterns, can provide an efficient, low-cost, and robust method to gather much needed performance data on parameters like RF coverage, available bandwidth, and impact of mobility. Our demonstration outlines the framework of such a distributed measurement system. We also showcase the potential benefits by presenting our initial measurements from this testbed through the use of intuitive visualization interface.
An overview of OpenAirInterface wireless network emulation methodology
Authors: Anouar Hicham , Bonnet Christian , Câmara Daniel , Filali Fethi , Knopp Raymond
Published: October 2008

The OpenAirInterface wireless network emulator, a tool with the dual objective of performing protocol and application performance evaluation, in addition to real-time layer 2/3 protocol implementation validation, is described. The current example protocol implementations closely resemble those of evolving UMTS-LTE and 802.16e/m networks with the additional possibility for creating mesh network topologies. They do not provide any form of compliance, however, with these standards. The emulation environment comes in both real-time and non-real-time flavors based on RTAI/Linux open-source developments. Novel ideas for physical layer (PHY) abstraction are also reviewed.
Busy period analysis of finite QBD processes
Authors: Garikiparthi Chaitanya , van de Liefvoort Appie , Mitchell Ken
Published: October 2008

We present the number of customers served and the length of a busy period for finite quasi birth and death (QBD) processes where either one or both of the arrival or service processes can be serially correlated or interdependent. Special cases include the G/G/1/K, M/G/1/K, and G/M/1/K queues. The resulting algorithms are linear algebraic in nature and are easily implemented. The solutions allow studies on how the moments and correlations in the arrival and service processes affect the busy period. This includes the probability of serving exactly
n
customers during a busy period and the moments of the length of the busy period for different system (queue) sizes. We present an example of a QBD process where arrival and service processes are strongly dependent.
Finding the optimal quantum size
Authors: Gupta Varun
Published: October 2008

We consider the round robin (RR) scheduling policy where the server processes each job in its buffer for at most a fixed quantum, q, in a round-robin fashion. The processor sharing (PS) policy is an idealization of the quantum-based round-robin scheduling in the limit where the quantum size becomes infinitesimal, and has been the subject of many papers. It is well known that the mean response time in an M/G/1/PS queue depends on the job size distribution via only its mean. However, almost no explicit results are available for the round-robin policy. For example, how does the variability of job sizes affect the mean response time in an M/G/1/RR queue? How does one choose the optimal quantum size in the presence of switching overheads? In this paper we present some preliminary answers to these fundamental questions.
Joint rate-and-power allocation for multi-channel spectrum sharing networks
Authors: Wu Yuan , Tsang Danny H. K.
Published: October 2008

In this abstract, we propose a study on joint rate-and-power allocation problem for multi-channel spectrum sharing networks (SSNs). We formulate this cross-layer optimization problem as a non-cooperative potential game
G

JRPA

in which each user has a coupled two-tuple strategy, i.e., simultaneous rate and multi-channel power allocations. A multi-objective cost function is designed to represent user's awareness of both QoS provisioning and power saving. Using the game-theoretic formulation, we investigate the properties of Nash equilibrium (N.E.) for our
G

JRPA

model, including its existence, and properties of QoS provisioning as well as power saving. Furthermore, a layered structure is derived by applying Lagrangian dual decomposition to
G

JRPA

and a distributed algorithm is proposed to find the N.E. via this structure.
Characterizing the miss sequence of the LRU cache
Authors: Jelenković Predrag R. , Kang Xiaozhu
Published: October 2008

Renewed interest in caching systems stems from their wide-spread use for reducing the document download latency over the Internet. Since caches are usually organized in a hierarchical manner, it is important to study the performance properties of tandem caches. The first step in understanding this problem is to characterize the miss stream from one single cache since it represents the input to the next level cache. In this regard, we discover that the miss stream from one single cache is approximated well by the superposition of a number of asymptotically independent renewal processes. Interestingly, when this weakly correlated miss sequence is fed into another cache, this barely observable correlation can lead to measurably different caching performance when compared to the independent reference model. This result is likely to enable the development of a rigorous analysis of the tandem cache performance.
Fluid level in a reservoir with an on-off source
Authors: Gupta Varun , Harrison Peter G.
Published: October 2008

We obtain the Laplace transform of the fluid level probability density function, in terms of the on-period density function, for a fluid queue (or reservoir) with on-off input at equilibrium. We further obtain explicit expressions for the moments of fluid level in terms of the moments of the on-period and hence derive an algorithm for the moments of fluid level at every queue in a tandem network. It turns out that to calculate the kth moment at the ith queue, only the first
k
+1 moments of the on-period of the input process to the first queue are required.
Self-assembling sweep-and-sleep sensor systems
Authors: Kwak K. J. , Baryshnikov Y. M. , Coffman E. G.
Published: October 2008

This paper describes a self-assembling sleep-wake sensor system that is scalable, easily implemented, and energy conserving. Sensors actively detecting events form wave fronts that sweep the sensor field. An application of concepts from cellular automata theory accounts for much of its novelty. The system has additional, highly desirable properties such as a self-healing capability, fault tolerance, asynchronous operation, seamless accommodation of obstacles in the sensor field, and it is highly effective even in the case of intelligent intruders, i.e., those who know sensor design and sensor locations. System performance is a focus of the paper, and, as in the study of the emergent behavior of cellular automata, an instructive example of experimental mathematics. Related open questions in mathematical performance analysis are reviewed.
The case for active block layer extensions
Authors: Guerra Jorge , Useche Luis , Bhadkamkar Medha , Koller Ricardo , Rangaswami Raju
Published: October 2008

Self-managing storage systems have recently received attention from the research community due to their promised ability of continuously adapting to best reflect high-level system goal specifications. However, this eventuality is currently being met by both conceptual and practical challenges that threaten to slow down the pace of innovation. We argue that two fundamental directions will help evolve the state of self-managing storage systems: (i) a standardized development environment for self-management extensions that also addresses ease of deployment, and (ii) a theoretical framework for reasoning about behavioral properties of individual and collective self-management extensions. We propose Active Block Layer Extensions (ABLE), an operating system infrastructure that aids the development and manages the deployed instances of self-management extensions within the storage stack. ABLE develops a theory behind block layer extensions that helps address key questions about overall storage stack behavior, data consistency, and reliability. We exemplify specific storage self-management solutions that can be built as stackable extensions using ABLE. Our initial experience with ABLE and few block layer extensions that we have been building, leads to believe that the ABLE infrastructure can substantially simplify the development and deployment of robust, self-managing, storage systems.
Towards distributed storage resource management using flow control
Authors: Gulati Ajay , Ahmad Irfan
Published: October 2008

Deployment of shared storage systems is increasing with rapid adoption of virtualization technologies to provide flexible sharing, isolation, better management and high utilization of resources.
Quality of service (QoS)
in such environments is quite desirable for meeting IO demands of virtual machines. The lack of QoS support at typical storage arrays, simultaneous access by multiple hosts and concerns regarding under-utilization of resources makes this problem quite challenging. In this paper, we study the problem of providing fairness among hosts accessing a storage array in a distributed manner while maintaining high efficiency. Towards this goal, we investigate whether local latency estimates at each host can be used to detect overload and whether limiting host issue queue lengths can provide fairness across hosts. In principle, the approach is similar to mechanisms used by TCP at each host for flow control. Initial experiments and simulation results for control mechanism provide encouragement to develop a complete framework.
Providing differentiated QoS for peer-to-peer file sharing systems
Authors: Ge Ping , Cai Hailong
Published: October 2008

In this paper, we propose a new Cluster Server Architecture (CSA) to realize an enhanced differentiated QoS in P2P file sharing systems. CSA adopts two approaches to provide a better QoS for dedicated users than standard users: (1) expedited forwarding messages of dedicated users and system maintenance messages at each node to speedup their response times, and (2) temporarily caching and instantly supplying routing information for dedicated users to reduce their self-organization overhead and warm-up time. Both theoretical analysis and simulation results show that our proposed architecture and algorithms effectively and efficiently implement a differentiated QoS model in P2P file sharing systems. The CSA introduces only modest overhead but still retains a good scalability and robustness.
Evaluation of interrupt handling timeliness in real-time Linux operating systems
Authors: Regnier Paul , Lima George , Barreto Luciano
Published: October 2008

Several real-time Linux extensions are available nowadays. Two of those extensions that have received special attention recently are Preempt-RT and Xenomai. This paper evaluates to what extent they provide deterministic guarantees when reacting to external events, an essential characteristic when it comes to real-time systems. For this, we define two simple experimental approaches. Our results indicate that Preempt-RT is more prone to temporal variations than Xenomai when the system is subject to overload scenarios.
Using a file working set model to speed up the recovery of Peer-to-Peer backup systems
Authors: Colaço Eduardo M. , Oliveira Marcelo Iury S. , Soares Alexandro S. , Brasileiro Francisco , Guerrero Dalton S.
Published: October 2008

The high churn and low bandwidth characteristics of peer-to-peer (P2P) backup systems make recovery a time-consuming activity that increases the system's outage. This is especially disturbing from the user's perspective, because during outage the user is prevented from carrying out useful work. Nevertheless, at any given time, a user typically requires only a small number of her files to continue working. If the backup system is able to quickly recover these files, then the system's outage can be greatly reduced, even if a large portion of the data lost is still being recovered. In this paper, we evaluate the use of a file system working set model to support efficient recovery of a P2P backup system. By exploiting a simple LRU-like working set model, we have designed a recovery mechanism that substantially reduces outage and allows the user to return to work more quickly. The simulations we have performed show that even this simple model is able to reduce the outage by as much as 80%, when compared to the state-of-practice in P2P backup recovery.
Power management in the EPOS system
Authors: Wiedenhoft Geovani Ricardo , Wanner Lucas Francisco , Gracioli Giovani , Fröhlich Antônio Augusto
Published: October 2008

Power management strategies for embedded systems typically rely on static, application driven deactivation of components (e.g. sleep, suspend), or on dynamic voltage and frequency scaling. However, the design and implementation of these strategies in embedded operating system often fail to deal with real-time and quality-of-service (QoS) requirements.

The EPOS system implements an infra-structure that supports both static (application-driven) and dynamic (system-driven) power management. In this work, this infrastructure is used to explore energy as a parameter for QoS in embedded systems, with the goal of guaranteeing energy consumption metrics, while preserving the deadlines of essential (hard real-time) tasks. Given a set of real-time tasks and their associated energy consumption, we provide equations to check schedulability in project-time. At runtime, a preemptive scheduler for imprecise tasks prevents the execution of optional subtasks whenever there is the possibility of deadline loss or depletion of the energy source. We show that this mechanism is effective in controlling energy consumption and ensuring "best-effort" computation without deadline loss.
Using model checkers in an introductory course on operating systems
Authors: Hamberg Roelof , Vaandrager Frits
Published: October 2008

During the last three years, we have been experimenting with the use of the Uppaal model checker in an introductory course on operating systems for first-year Computer Science students at the Radboud University Nijmegen. The course uses model checkers as a tool to explain, visualize and solve concurrency problems. Our experience is that students enjoy to play with model checkers because it makes concurrency issues tangible. Even though it is hard to measure objectively, we think that model checkers really help students to obtain a deeper insight into concurrency. In this article, we report on our experiences in the classroom, explain how mutual exclusion algorithms, semaphores and monitors can conveniently be modeled in Uppaal, and present some results on properties of small, concurrent patterns.