bluuebunny/crossref_metadata_2025 huggingface dataset:
Environment behavior models for scenario generation and testing automation
Authors: Auguston Mikhail , Michael James Bret , Shing Man-Tak
Published: November 2005

This paper suggests an approach to automatic scenario generation from environment models for testing of real-time reactive systems. The behavior of the system is defined as a set of events (event trace) with two basic relations: precedence and inclusion. The attributed event grammar (AEG) specifies possible event traces and provides a uniform approach for automatically generating, executing, and analyzing test cases. The environment model includes a description of hazardous states in which the system may arrive and makes it possible to gather statistics for system safety assessment. The approach is supported by a generator that creates test cases from the AEG models. We demonstrate the approach with case studies of prototypes for the safety-critical computer-assisted resuscitation algorithm (CARA) software for a casualty intravenous fluid infusion pump and the Paderborn Shuttle System.
Early estimation of defect density using an in-process Haskell metrics model
Authors: Sherriff Mark , Nagappan Nachiappan , Williams Laurie , Vouk Mladen
Published: November 2005

Early estimation of defect density of a product is an important step towards the remediation of the problem associated with affordably guiding corrective actions in the software development process. This paper presents a suite of in-process metrics that leverages the software testing effort to create a defect density prediction model for use throughout the software development process. A case study conducted with Galois Connections, Inc. in a Haskell programming environment indicates that the resulting defect density prediction is indicative of the actual system defect density.
Case studies on fault detection effectiveness of model based test generation techniques
Authors: Paradkar Amit
Published: November 2005

Model-based test generation (MBTG) is becoming an area of active research. These techniques differ in terms of (1) modeling notations used, and (2) the adequacy criteria used for test generation. This paper (1) reviews different classes of MBTG techniques at a conceptual level, and (2) reports results of two case studies comparing various techniques in terms of their fault detection effectiveness. Our results indicate that MBTG technique which employs mutation and explicitly generates state verification sequences has better fault detection effectiveness than those based on boundary values, and predicate coverage criteria for transitions. Instead of a default adequacy criteria, certain techniques allow the user to specify test objectives in addition to the model. Our experience indicates that the task of defining appropriate test objectives is not intuitive. Furthermore, notations provided to describe such test objectives may have inadequate expressive power. We posit the need for a suitable fault modeling notation.
Distributed performance testing using statistical modeling
Authors: Karr Alan F. , Porter Adam A.
Published: November 2005

This article briefly presents some of our recent research in distributed continuous performance analysis. In general this work pushes substantial parts of performance analysis out of developer laboratories and onto remote, end-user machines.To do this effectively we have found it useful to recast performance analysis as a model-based experimental design and execution problem.Our experience suggests that this approach has merit, but that much future work remains to be done. We therefore discuss some of the limitations of our current efforts and describe some plans for future work.
The effect of code coverage on fault detection under different testing profiles
Authors: Cai Xia , Lyu Michael R.
Published: November 2005

Software testing is a key procedure to ensure high quality and reliability of software programs. The key issue in software testing is the selection and evaluation of different test cases. Code coverage has been proposed to be an estimator for testing effectiveness, but it remains a controversial topic which lacks of support from empirical data. In this study, we hypothesize that the estimation of code coverage on testing effectiveness varies under different testing profiles. To evaluate the performance of code coverage, we employ coverage testing and mutation testing in our experiment to investigate the relationship between code coverage and fault detection capability under different testing profiles. From our experimental data, code coverage is simply a moderate indicator for the capability of fault detection on the whole test set. However, it is clearly a good estimator for the fault detection of exceptional test cases, but a poor one for test cases in normal operations. For other testing profiles, such as functional testing and random testing, the correlation between code coverage and fault coverage is higher in functional test than in random testing, although these different testing profiles are complementary in the whole test set. The effects of different coverage metrics are also addressed in our experiment.
Model-based specification and testing applied to the Ground-Based Midcourse Defense (GMD) system
Authors: Lakey Peter B.
Published: November 2005

Cognitive Concepts LLC (CC) is a small business that specializes in software reliability engineering. In the past several years CC has become convinced that the best available practice for software reliability on complex systems is model-based specification and testing (MST). CC completed a small business innovative research project with the Missile Defense Agency in 2004 in which the goal was to demonstrate the feasibility and value of applying MST on some aspect of the National Missile Defense (NMD). This paper describes the results of that research effort.
Value-based quality processes and results
Authors: Boehm Barry
Published: November 2005

Cost effectiveness is one of the important issues for developing products in a life cycle. And review is a key activity that can detect defects from the early stage and fix them. This paper provides Value-based review techniques adding cost effectiveness into review processes and reports on an experiment on Value-based review. Through the experiment, the Value-based review is shown to have higher cost effectiveness in review processes.
Software quality economics for defect-detection techniques using failure prediction
Authors: Wagner Stefan , Seifert Tilman
Published: November 2005

Defect-detection techniques, like reviews or tests, are still the prevalent method to assure the quality of software. However, the economics behind those techniques are not fully understood. It is not always obvious when and for how long to use which technique. A cost model for defect-detection techniques is proposed that uses a reliability model and expert opinion for cost estimations and predictions. It is detailed enough to allow fine-grained estimates but also can be used with different defect-detection techniques not only testing. An application of the model is shown using partly data from an industrial project.
QFD application in software process management and improvement based on CMM
Authors: Liu Xiaoqing (Frank) , Sun Yan , Kane Gautam , Kyoya Yuji , Noguchi Kunio
Published: November 2005

Capability Maturity Model (CMM) from Software Engineering Institute has been used successfully by many organizations for software process improvement. However, there exists a disconnection between business goals and maturity levels. A new framework using Quality Function Deployment (QFD) is developed to deal with this problem. This framework serves three purposes: (1) it provides a connection between business requirements and CMM; (2) it proposed a methodology for the priority assessment of requirements from multiple perspectives; and (3) it helps identify a set of software process improvement actions based on business requirements and CMM.
Improving quality through software process improvement in Thailand
Authors: Phongpaibul Monvorath , Boehm Barry
Published: November 2005

For almost 10 years there have been attempts in Thailand to improve software quality by adopting western software process improvement models. Only 17 of the 380 companies in Thailand were able to implement software process models that we see here in the US. 14 out of the 17 companies were not able to improve their process to a higher level. Why were companies not successful in implementing these software process models? Did they find other ways to improve quality? The objective of this paper is to analyze the experiences of software developers, project managers and executive managers in implementing these software process models in Thailand. The results will show that cultural differences are a key factor to this problem. Thai people have different cultural values. which we will explore further in this paper.
Software quality development and assurance in RUP, MSF and XP
Authors: Zuser Wolfgang , Heil Stefan , Grechenig Thomas
Published: November 2005

The support of software quality in a software development process may be regarded under two aspects: first, by providing techniques, which support the development of high quality software and second, by providing techniques, which assure the required quality attributes in existing artifacts. Both approaches have to be combined to achieve effective and successful software engineering.In this study, we compare three of the most industrially relevant software development process models (Rational Unified Process (RUP), Microsoft Solution Framework (MSF) and Extreme Programming (XP)) regarding their software quality support in terms of software quality development and software quality assurance. Based on the results we propose a de-facto standard for quality support in software development process models.
Quality, cleanroom and formal methods
Authors: Langari Zarrin , Pidduck Anne Banks
Published: November 2005

We have proposed a new approach to software quality combining cleanroom methodologies and formal methods. Cleanroom emphasizes defect prevention rather than defect removal. Formal methods use mathematical and logical formalizations to find defects early in the software development lifecycle. These two methods have been used separately to improve software quality since the 1980's. The combination of the two methods may provide further quality improvements through reduced software defects. This result, in turn, may reduce development costs, improve time to market, and increase overall product excellence.Defects in computer software are costly. Their detection is usually postponed to the test phase, and their removal is also a very time consuming and expensive task. Cleanroom software engineering is a methodology which relies on preventing the defects, rather than removing them. It is based on incremental development and it emphasizes the development phase. An enhancement to this methodology is presented in this paper, which combines formal methods and cleanroom. The efficiency of the new model rests on an appropriate logical representation, to write the specification of the intended system. In the new model, design plans are formally verified before any implementation is done. The advantages of finding defects in the early stages are decreased cost and increased quality. Results show that, by using formal methods, a higher quality will be achieved and the software project can also benefit from the existing mechanized tools of these two techniques.
Dealing with imprecise quality factors in software design
Authors: Noppen Joost , van den Broek Pim , Aksit Mehmet
Published: November 2005

During the design of a software system impreciseness can manifest itself in for instance the requirements or performance estimations. While it is common to eliminate the impreciseness by information that can not be justified, it is better to model the impreciseness since it is the most accurate description that is available at the current point in time. In this paper we present an approach, which allows the explicit specification of quality estimations and quality requirements including the imprecise nature. In this approach the impreciseness is modeled and addressed using representations from probability theory and fuzzy set theory.
ARIES
Authors: Higo Yoshiki , Kamiya Toshihiro , Kusumoto Shinji , Inoue Katsuro
Published: November 2005

In this paper, we explain our refactoring support tool
Aries.
Aries
characterizes code clones by several metrics, and suggests how to remove them.
A real time measure of software system families
Authors: Kiebusch Sebastian , Franczyk Bogdan , Speck Andreas
Published: November 2005

Software systems with inherent real time characteristics have become the driving force in many areas of technology like the automotive sector. Control functions of cars, driver assistance as well as systems for information and entertainment are accomplished by software driven control units. Due to the high complexity and development effort of real time systems, these resources have to be reused. Software system families are a promising solution to gain a cost reduction by reusing common software assets in different variants of an automobile. To support the economic management of this development approach we need software metrics to estimate the effort of building embedded software system families. Techniques of size measurement and cost estimation for software system families are highly insufficient in general and do not exist for the automotive domain. Therefore this article describes a conglomerate of innovative metrics to analyze a realtime perspective of embedded software system families in the automotive domain. These size metrics calculate an unadjusted measure of software driven control units to indicate and estimate their development costs.
An empirical assessment of using stereotypes to improve reading techniques in software inspections
Authors: Staron Miroslaw , Kuzniarz Ludwik , Thurn Christian
Published: November 2005

Stereotypes were introduced into the Unified Modeling Language (UML) in order to provide a means of customizing the language for particular needs. The stereotypes can increase the comprehension of UML diagrams and therefor influence reading techniques used for inspections of software artefacts. In this paper we evaluate how the usage of stereotypes in UML designs influences outcomes of three reading techniques used for verification and validation of UML models. The study presented in this paper is done in the context of the UML domain modeling, but the results can be generalized to other kinds of models expressed in UML. The results show that the presence of stereotypes improves the efficiency and effectiveness of the studied methods and shows the magnitude of the improvements. We also investigate which of the reading techniques are the most efficient and effective for analysis of UML designs with stereotypes.
Pyro
Authors: Blank Douglas , Kumar Deepak , Meeden Lisa , Yanco Holly
Published: November 2005

In this article we describe a programming framework called Pyro, which provides a set of abstractions that allows students to write platform-independent robot programs. This project is unique because of its focus on the pedagogical implications of teaching mobile robotics via a top-down approach. We describe the background of the project, its novel abstractions, its library of objects, and the many learning modules that have been created from which curricula for different types of courses can be drawn. Finally, we explore Pyro from the students' perspective in a case study.
Three years of using robots in an artificial intelligence course
Authors: Kumar Amruth N.
Published: November 2005

We have been using robots in our artificial intelligence course since fall 2000. We have been using the robots for open-laboratory projects. The projects are designed to emphasize high-level knowledge-based AI algorithms. After three offerings of the course, we paused to analyze the collected data and to see if we could answer the following questions: (i) Are robot projects effective at helping students learn AI concepts? (ii) What advantages, if any, can be attributed to using robots for AI projects? (iii) What are the downsides of using robots for traditional projects in AI? In this article we discuss the results of our evaluation and list the lessons learned.
An intelligent agent approach for teaching neural networks using LEGO® handy board robots
Authors: Imberman Susan P.
Published: November 2005

In this article we describe a project for an undergraduate artificial intelligence class. The project teaches neural networks using LEGO® handy board robots. Students construct robots with two motors and two photosensors. Photosensors provide readings that act as inputs for the neural network. Output values power the motors and maintain the robot along the designated path. In doing this project, students come to realize the difference between training a neural network and the trained neural network. The fun factor associated with this project has encouraged students to elect artificial intelligence as part of their course of study.
Flexible cross-domain event delivery for quality-managed multimedia applications
Authors: Poellabauer Christian , Schwan Karsten
Published: November 2005

To meet end users' quality-of-service (QoS) requirements, online quality management for multimedia applications must include appropriate allocation of the underlying computing platform's resources. Previous work has developed novel operating system (OS) functionality for dynamic QoS management, including multimedia or real-time CPU schedulers and OS extensions for online performance monitoring and for adaptations, as well as QoS-aware applications that adapt their behavior to gain additional benefits from such functionality. This article describes a general OS mechanism that may be used to implement a wide variety of online quality management functions. ECalls is a communication mechanism that implements multiple cross-domain calling conventions that can be customized to the quality management needs of applications. The ECalls mechanism is based on the notions of events, event channels, and event handlers. Using events, applications can share relevant QoS attributes with OS services, and OS-level resource management services can efficiently provide monitoring data to target applications or application managers. Dynamically generated event handlers can be used to customize event delivery to meet diverse application needs, for example, to achieve high scalability for Web servers or small jitter for real-time data delivery.
Temporal event clustering for digital photo collections
Authors: Cooper Matthew , Foote Jonathan , Girgensohn Andreas , Wilcox Lynn
Published: November 2005

Organizing digital photograph collections according to events such as holiday gatherings or vacations is a common practice among photographers. To support photographers in this task, we present similarity-based methods to cluster digital photos by time and image content. The approach is general and unsupervised, and makes minimal assumptions regarding the structure or statistics of the photo collection. We present several variants of an automatic unsupervised algorithm to partition a collection of digital photographs based either on temporal similarity alone, or on temporal and content-based similarity. First, interphoto similarity is quantified at multiple temporal scales to identify likely event clusters. Second, the final clusters are determined according to one of three clustering goodness criteria. The clustering criteria trade off computational complexity and performance. We also describe a supervised clustering method based on learning vector quantization. Finally, we review the results of an experimental evaluation of the proposed algorithms and existing approaches on two test collections.
Coordinated enroute multimedia object caching in transcoding proxies for tree networks
Authors: Li Keqiu , Shen Hong
Published: November 2005

Transcoding is a promising technology that allows systems to effect a quality-versus-size tradeoff on multimedia objects. As audio and video applications have proliferated on the Internet, caching in transcoding proxies has become an important technique for improving network performance, especially in mobile networks. This article addresses the problem of coordinated enroute multimedia object caching in transcoding proxies for tree networks. We formulate this problem as an optimization problem based on our proposed model, in which multimedia object caching decisions are made on all enroute caches along the routing path by integrating both object placement and replacement policies and cache status information along the routing path of a request is used to determine the optimal locations for caching multiple versions of the same multimedia object. We propose an optimal solution using dynamic programming to compute the optimal locations. We also extend this solution to solve the same problem for several constrained cases, including constraints on the cost gain per node and on the number of versions to be placed. Our model is evaluated on different performance metrics through extensive simulation experiments. The implementation results show that our model significantly outperforms existing models that consider Web caching in transcoding proxies either on a single path or at individual nodes.
Comprehending large code bases - the skills required for working in a "brown fields" environment
Authors: Clear Tony
Published: November 2005

In the search for answers to the effective teaching of programming at the beginner level, we are now seeing broader programs of research investigate the distinctions between reading, comprehending and writing small programs [1], [2]. In New Zealand we have joined this work with the "Bracelet" project, in which multiple institutions will investigate how students comprehend small computer programs. We hope this may help answer critical teaching and assessment questions.
Associate-degree transfer curriculum in software engineering
Authors: Campbell Robert D.
Published: November 2005

In 2004, curricular guidelines for undergraduate programs in Software Engineering were published under the title
Software Engineering 2004: Curriculum Guidelines for Undergraduate Degree Programs in Software Engineering.
That report, together with accompanying materials, can be found at http://www.computer.org/education/. That work was the result of a joint task force of the IEEE-CS and the ACM; this task force included Beth Hawthorne, a member of the ACM Two-Year College Education Committee.
Honor societies, college and service
Authors: Popyack Jeffrey
Published: November 2005

Greetings! A session I attended at the 2005 annual meeting of the Association of College Honor Societies (ACHS) [1] came at a critical juncture. It has stimulated some serious thought on my part about service learning, the role of service in the college curriculum, and what it might mean for computer science educators in particular.
Mathematics in the curricula
Authors: Henderson Peter B.
Published: November 2005

Please take a few minutes to read Tony Ralston's excellent editorial "Do We Need ANY Mathematics in Computer Science Curricula?" in this issue of
inroads.
His editorial, in conjunction with another excellent document "Computing Curricula 2004 Overview Report" [1], are very timely. Tony talks about the historical perspective of mathematics in CS/SE education and direction in which we might head. The CC2004 Overview Report presents the current state of curricula for computing disciplines. Both complement and reinforce each other in several ways.
Active and cooperative learning
Authors: McConnell Jeffrey J.
Published: November 2005

Information about the value of active and cooperative learning for students does not typically provide hints for making it work in the classroom. This and subsequent articles in this series will discuss tips and tricks that help to make classroom activities successful. This first article gives a brief background on active and cooperative learning. The background for dramas or kinesthetic learning activities that get students to physically act out a concept or algorithm are also discussed along with some example activities of this type.
2D array implementation of sorted lists
Authors: Hu Chenglie
Published: November 2005

The ideas and key algorithms of a sorted list data structure based on a 2-dimensional (2D) array container are presented. It is shown that with an appropriately chosen number of rows, the efficiency of insertion and deletion is much improved compared to traditional approaches of using 1D arrays or linked structures. Yet, the binary search capability is retained. While such a data structure may deserve further exploration for its practical merit, its real value may well be in data structure classes, where the implementations and related issues provide sources for challenging projects. In addition, the implementation also provides a good example in understanding 2D arrays implemented as array of arrays in an object-oriented language.
The power of notation
Authors: Warms Tom M.
Published: November 2005

A system of notations for tracing programs devised by the author is shown to be of use in modeling operations on pointers. Typical examples using linked lists are provided.
List processing
Authors: Rolfe Timothy J.
Published: November 2005

This paper discusses a possible student project for use within the Data Structures and Algorithms treatment of linked lists. Students can explicitly compare the recursive list-oriented MergeSort algorithm with iterative list-oriented MergeSort algorithms (with O(
n
) space overhead) including the "Natural MergeSort." The author's experimental results are shown for implementations in C and in Java.
Introductory teaching of imperative programming through an anthropomorphic computation model
Authors: Savidis Anthony
Published: November 2005

The introduction to imperative programming for computer science students that possess little or no programming knowledge, involves many teaching challenges to effectively deliver concepts such as algorithm, computation, program variable and program instruction. In this process, students are required to record and assimilate many new concepts and to manipulate symbols and rules having no evident real-world analogy. In this context, we have designed a programming language called Flip (i.e.
F
ront-end language for
i
ntroduction to
p
rogramming) having a runtime model that reflects a real-world computation metaphor we call the "computational servant". All Flip instructions and definitions are documented as well-defined "bureaucratic-style" activities performed by the servant, involving typical office objects like pencil, notebook, eraser, clips, rolling paper and post-it labels. The key metaphoric characteristic of the Flip language is that it "uses" a traditional notebook with numbered pages and rows to store program content (including variables), while programs written in the Flip language can be directly compiled and run using a standard C++ compiler (as far as the Flip header file is included).
Ludwig
Authors: Shaffer Steven C.
Published: November 2005

An online programming tutoring and assessment system is described, and the results of a preliminary study are presented. Ten students in an introductory C++ programming course used the system; both qualitative and quantitative data were collected and suggest that a future large-scale implementation will yield beneficial results
On the number of recursive calls of recursive functions
Authors: Manolopoulos Yannis
Published: November 2005

The advantages and disadvantages of recursion are early introduced to students. Simplicity in coding but time and space inefficiency during execution are the main characteristics. In many occasions, recursive formulae lead to recursive functions/procedures that are highly inefficient as calls with the same parameters are executed several times. Here, we elaborate on a previous report [2], where a generalized analysis is carried out to derive the number of recursive calls of a recursive formula, the calculation of the Fibonacci numbers in particular. Here we re-examine the problem using a different and simpler approach, which generalizes as well.
Advanced non-distributed operating systems course
Authors: Wiseman Yair
Published: November 2005

The use of Non-Distributed Operating Systems is very common and old. Many researchers feel that this field of research is outmoded, and therefore put their efforts into Distributed Operating Systems. Advanced Operating Systems courses generally include an overview of the topical issues of research in the Operating System field. Many instructors prefer using Distributed Operating Systems subjects in order to give their students the contemporary research atmosphere. This encourages graduate students to research Distributed Operating Systems topics. We suggest that Non-Distributed Operating Systems is still an important field worthy of being expanded in graduate courses. An example for such a course is given. This course has been successfully taught in Bar-Ilan University during 2004.
A design-first curriculum for teaching Java in a CS1 course
Authors: Moritz Sally H. , Blank Glenn D.
Published: November 2005

Pedagogies for teaching object-oriented programming in an introductory course are still under much debate. We present a design-first approach, which teaches problem-solving techniques using elements of UML. Objects are still introduced early in the curriculum. We also present two tools to support our curriculum: multimedia courseware to help students learn the basic concepts of objects and classes, and an IDE that includes both a UML interface and interactive tools to allow easy experimentation.
External sponsored projects
Authors: James Richard H.
Published: November 2005

Although student experience with large-scale software development projects contributes significantly to their education, the burden of managing projects for external sponsors can be equally significant for the faculty. While sponsored projects provide more real-world experiences, can the additional demands on the faculty be too much? This paper explores the lessons we have learned over six years of faculty experience with sponsored projects.
Usability of Rational Rose and Visio in a software engineering course
Authors: Shumba Rose
Published: November 2005

Rational Rose (Rose) and Microsoft Visio (Visio) are the two commonly used UML modeling tools in software engineering courses. In the fall of 2002, a project to evaluate the usability of Rose and Visio for UML modeling in an undergraduate software engineering class was started. Through a questionnaire survey, student experiences of using Rose and Visio for UML modeling were collected and analyzed. This paper outlines our findings from the research project, tool features, diagram creation, available documentation, multi-tasking ability and produced output.
Controversy on how to teach CS 1
Authors: Bruce Kim B.
Published: November 2005

A discussion took place on the SIGCSE mailing list in late March of 2004 that raised important issues on how to teach introductory courses using Java. This article attempts to summarize several of the important points raised during this discussion, among them whether or how objects should be taught early or late in a CS 1 course, or indeed, whether object-oriented languages should be postponed until a second course.
Evaluation of design strategies for stochastically assembled nanoarray memories
Authors: Gojman Benjamin , Rachlin Eric , Savage John E.
Published: November 2005

A key challenge facing nanotechnologies is learning to control uncertainty introduced by stochastic self-assembly. In this article, we explore architectural and manufacturing strategies to cope with this uncertainty when assembling nanoarrays, crossbars composed of two orthogonal sets of parallel nanowires (NWs) that are differentiated at their time of manufacture. NW deposition is a stochastic process and the NW encodings present in an array cannot be known in advance. We explore the reliable construction of memories from stochastically assembled arrays. This is accomplished by describing several families of NW encodings and developing strategies to map external binary addresses onto internal NW encodings using programmable circuitry. We explore a variety of different mapping strategies and develop probabilistic methods of analysis. This is the first article that makes clear the wide range of choices that are available.
Nanowire-based programmable architectures
Authors: Dehon André
Published: November 2005

Chemists can now construct wires which are just a few atoms in diameter; these wires can be selectively field-effect gated, and wire crossings can act as diodes with programmable resistance. These new capabilities present both opportunities and challenges for constructing nanoscale computing systems. The tiny feature sizes offer a path to economically scale down to atomic dimensions. However, the associated bottom-up synthesis techniques only produce highly regular structures and come with high defect rates and minimal control during assembly. To exploit these technologies, we develop nanowire-based architectures which can bridge between lithographic and atomic-scale feature sizes and tolerate defective and stochastic assembly of regular arrays to deliver high density universal computing devices. Using 10nm pitch nanowires, these nanowire-based programmable architectures offer one to two orders of magnitude greater mapped-logic density than defect-free lithographic FPGAs at 22nm.
Model-driven design and deployment of service-enabled web applications
Authors: Manolescu Ioana , Brambilla Marco , Ceri Stefano , Comai Sara , Fraternali Piero
Published: November 2005

Significant effort is currently invested in application integration, enabling business processes of different companies to interact and form complex multiparty processes. Web service standards, based on WSDL (Web Service Definition Language), have been adopted as process-to-process communication paradigms. However, the conceptual modeling of applications using Web services has not yet been addressed. Interaction with Web services is often specified at the level of the source code; thus, Web service interfaces are buried within a programmatic specification.In this article, we argue that Web services should be considered first-class citizens in the specification of Web applications. Thus, service-enabled Web applications should benefit from the high-level modeling and automatic code generation techniques that have long been advocated for Web application design and implementation. To this end, we extend a declarative model for specifying data-intensive Web applications in two directions: (i) high-level modeling of Web services and their interactions with the Web applications which use them, and (ii) modeling and specification of Web applications implementing new, complex Web services.Our approach is fully implemented within a CASE tool allowing the high-level modeling and automatic deployment of service-enabled Web applications.
Optimal methods for coordinated enroute web caching for tree networks
Authors: Li Keqiu , Shen Hong , Chin Francis Y. L. , Zheng Si Qing
Published: November 2005

Web caching is an important technology for improving the scalability of Web services. One of the key problems in coordinated enroute Web caching is to compute the locations for storing copies of an object among the enroute caches so that some specified objectives are achieved. In this article, we address this problem for tree networks, and formulate it as a maximization problem. We consider this problem for both unconstrained and constrained cases. The constrained case includes constraints on the cost gain per node and on the number of object copies to be placed. We present dynamic programming-based solutions to this problem for different cases and theoretically show that the solutions are either optimal or convergent to optimal solutions. We derive efficient algorithms that produce these solutions. Based on our mathematical model, we also present a solution to coordinated enroute Web caching for autonomous systems as a natural extension of the solution for tree networks. We implement our algorithms and evaluate our model on different performance metrics through extensive simulation experiments. The implementation results show that our methods outperform the existing algorithms of either coordinated enroute Web caching for linear topology or object placement (replacement) at individual nodes only.
Flash crowd mitigation via adaptive admission control based on application-level observations
Authors: Chen Xuan , Heidemann John
Published: November 2005

We design an adaptive admission control mechanism,
network early warning system
(NEWS), to protect servers and networks from flash crowds and maintain high performance for end-users. NEWS detects flash crowds from performance degradation in responses and mitigates flash crowds by admitting incoming requests adaptively. We evaluate NEWS performance with both simulations and testbed experiments. We first investigate a network-limited scenarion in simulations. We find that NEWS detects flash crowds within 20 seconds. By discarding 32% of incoming requests, NEWS protects the target server and networks from overloading, reducing the response packet drop rate from 25% to 2%. For admitted requests, NEWS increases their response rate by two times. This performance is similar to the best static rate limiter deployed in the same scenario. We also investigate the impact of detection intervals on NEWS performance, showing it affects both detection delay and false alarm rate. We further consider a server memory-limited scenario in testbed experiments, confirming that NEWS is also effective in this case. We also examine the runtime cost of NEWS traffic monitoring in practice and find that it consumes little CPU time and relatively small memory. Finally, we show NEWS effectively protects bystander traffic from flash crowds.
Multiresolution storage and search in sensor networks
Authors: Ganesan Deepak , Greenstein Ben , Estrin Deborah , Heidemann John , Govindan Ramesh
Published: November 2005

Wireless sensor networks enable dense sensing of the environment, offering unprecedented opportunities for observing the physical world. This article addresses two key challenges in wireless sensor networks: in-network storage and distributed search. The need for these techniques arises from the inability to provide persistent, centralized storage and querying in many sensor networks. Centralized storage requires multihop transmission of sensor data to Internet gateways which can quickly drain battery-operated nodes.Constructing a storage and search system that satisfies the requirements of data-rich scientific applications is a daunting task for many reasons: (a) the data requirements may be large compared to available storage and communication capacity of resource-constrained nodes, (b) user requirements are diverse and range from identification and collection of interesting event signatures to obtaining a deeper understanding of long-term trends and anomalies in the sensor events, and (c) many applications are in new domains where a priori information may not be available to reduce these requirements.This article describes a
lossy, gracefully degrading storage model
. We believe that such a model is necessary and sufficient for many scientific applications since it supports both progressive data collection for interesting events as well as long-term in-network storage for in-network querying and processing. Our system demonstrates the use of in-network wavelet-based summarization and progressive aging of summaries in support of long-term querying in storage and communication-constrained networks. We evaluate the performance of our linux implementation and show that it achieves: (a) low communication overhead for multiresolution summarization, (b) highly efficient drill-down search over such summaries, and (c) efficient use of network storage capacity through load-balancing and progressive aging of summaries.
Efficient disk replacement and data migration algorithms for large disk subsystems
Authors: Seo Beomjoo , Zimmermann Roger
Published: November 2005

Random data placement, which is efficient and scalable for large-scale storage systems, has recently emerged as an alternative to traditional data striping. In this report, we study the
disk replacement problem
(DRP) to find a sequence of disk additions and removals for a storage system, while migrating the data and respecting the following constraints: (1) the data is initially balanced across the existing distributed disk configuration, (2) the data must again be balanced across the new configuration, and (3) the data migration cost must be minimized. In practice, migrating data from old disks to new devices is complicated by the fact that the total number of disks connected to the storage system is often limited by a fixed number of available slots and not all the old and new disks can be connected at the same time. This article presents solutions for both cases where the number of disk slots is either unconstrained or constrained.
Performance directed energy management for main memory and disks
Authors: Li Xiaodong , Li Zhenmin , Zhou Yuanyuan , Adve Sarita
Published: November 2005

Much research has been conducted on energy management for memory and disks. Most studies use control algorithms that dynamically transition devices to low power modes after they are idle for a certain threshold period of time. The control algorithms used in the past have two major limitations. First, they require painstaking, application-dependent manual tuning of their thresholds to achieve energy savings without significantly degrading performance. Second, they do not provide performance guarantees.This article addresses these two limitations for both memory and disks, making memory/disk energy-saving schemes practical enough to use in real systems. Specifically, we make four main contributions. (1) We propose a technique that provides a performance guarantee for control algorithms. We show that our method works well for all tested cases, even with previously proposed algorithms that are not performance-aware. (2) We propose a new control algorithm,
Performance-Directed Dynamic
(PD), that dynamically adjusts its thresholds periodically, based on available slack and recent workload characteristics. For memory, PD consumes the least energy when compared to previous hand-tuned algorithms combined with a performance guarantee. However, for disks, PD is too complex and its self-tuning is unable to beat previous hand-tuned algorithms. (3) To improve on PD, we propose a simpler, optimization-based, threshold-free control algorithm,
Performance-Directed Static
(PS). PS periodically assigns a static configuration by solving an optimization problem that incorporates information about the available slack and recent traffic variability to different chips/disks. We find that PS is the best or close to the best across all performance-guaranteed disk algorithms, including hand-tuned versions. (4) We also explore a hybrid scheme that combines PS and PD algorithms to further improve energy savings.
APSS
Authors: Zhou Lidong , Schneider Fred B. , Van Renesse Robbert
Published: November 2005

APSS, a proactive secret sharing (PSS) protocol for asynchronous systems, is explained and proved correct. The protocol enables a set of secret shares to be periodically refreshed with a new, independent set, thereby thwarting mobile-adversary attacks. Protocols for asynchronous systems are inherently less vulnerable to denial-of-service attacks, which slow processor execution or delay message delivery. So APSS tolerates certain attacks that PSS protocols for synchronous systems cannot.
The concept of layered proving trees and its application to the automation of security protocol verification
Authors: Dojen Reiner , Coffey Tom
Published: November 2005

Security protocols are one of the most critical elements in enabling the secure communication and processing of information. The presence of flaws in published protocols highlights the complexity of security protocol design. Only formal verification can provide strong confidence in the correctness of security protocols and is considered an imperative step in their design. This paper presents a new theoretical concept, called Layered Proving Trees, for automatically applying logical postulates in logic-based security protocol verification.An algorithm for the new concept is introduced and the soundness and completeness of the technique is proved. Empirical results on the performance of the algorithm are presented. The presented proofs and empirical results demonstrate the feasibility and effectiveness of the Layered Proving Tree approach.
An overview of embedded system design education at berkeley
Authors: Sangiovanni-Vincentelli Alberto L. , Pinto Alessandro
Published: November 2005

Embedded systems have been a traditional area of strength in the research agenda of the University of California at Berkeley. In parallel to this effort, a pattern of graduate and undergraduate classes has emerged that is the result of a distillation process of the research results. In this paper, we present the considerations that are driving our curriculum development and we review our undergraduate and graduate program. In particular, we describe in detail a graduate class (EECS249: Design of Embedded Systems: Modeling, Validation and Synthesis) that has been taught for six years. A common feature of our education agenda is the search for fundamentals of embedded system
science
rather than embedded system design techniques, an approach that today is rather unique.
Undergraduate embedded system education at Carnegie Mellon
Authors: Koopman Philip , Choset Howie , Gandhi Rajeev , Krogh Bruce , Marculescu Diana , Narasimhan Priya , Paul Joann M. , Rajkumar Ragunathan , Siewiorek Daniel , Smailagic Asim , Steenkiste Peter , Thomas Donald E. , Wang Chenxi
Published: November 2005

Embedded systems encompass a wide range of applications, technologies, and disciplines, necessitating a broad approach to education. We describe embedded system coursework during the first 4 years of university education (the U.S. undergraduate level). Embedded application curriculum areas include: small and single-microcontroller applications, control systems, distributed embedded control, system-on-chip, networking, embedded PCs, critical systems, robotics, computer peripherals, wireless data systems, signal processing, and command and control. Additional cross-cutting skills that are important to embedded system designers include: security, dependability, energy-aware computing, software/systems engineering, real-time computing, and human--computer interaction. We describe lessons learned from teaching courses in many of these areas, as well as general skills taught and approaches used, including a heavy emphasis on course projects to teach system skills.