Faded Parsons Problems (FPPs) are a variant of Parsons Problems in which students reconstruct short pieces of code by filling in blanks (''fades'') and rearranging pre-written scrambled lines of code. We are particularly interested in FPPs' demonstrated superiority over code-writing or code-comprehension exercises for scaffolding the teaching of advanced programming concepts. However, little is known about how the choice of what to fade (i.e. which tokens to blank out in the scrambled code lines) affects an FPP's difficulty and efficacy, and existing Parsons Problems research does not address advanced classrooms. Code for italics .xx. Code for bolTo inform the choice of what to fade, and potentially allow automated fading of a reference solution for formative assessments, we devise a conceptual guide for constructing FPP ''fading strategies'' informed by guidelines from prior work as well as our own experience. Using this guide, we generate three strategies that are variably aware of the context of the program text they fade. We compare the strategies using a between-subjects study in which students solve FPPs around an advanced software engineering topic. We find that the difficulty and efficacy of the problems, as measured by time on task, qualitative surveys, and long-term retention, does not appear to depend on context-awareness, but also find that random choices are, in some senses, ''more obfuscating'' than our other strategies. We conclude that our simplest strategy suffices for the future study of automatic fading of FPPs scaffolding advanced topics.

Collaboration is a crucial part of computing education. The increase in AI capabilities over the last couple of years is bound to profoundly affect all aspects of systems and software engineering, including collaboration. In this position paper, we consider a scenario where AI agents would be able to take on any role in collaborative processes in computing education. We outline these roles, the activities and group dynamics that software development currently include, and discuss if and in what way AI could facilitate these roles and activities. The goal of our work is to envision and critically examine potential futures. We present scenarios suggesting how AI can be integrated into existing collaborations. These are contrasted by design fictions that help demonstrate the new possibilities and challenges for computing education in the AI era.

Requirements Elicitation (RE) is a crucial software engineering skill that involves interviewing a client and then devising a software design based on the interview results. We propose conditioning a large language model to play the role of the client during a chat-based interview. We evaluate our approach in a study (n=120) using both a qualitative survey and quantitative observations about participants' work. Our positive findings suggest a new way to practice critical RE skills in a scalable and realistic manner without the overhead of arranging live interviews.

An application's architecture is frequently refactored after deployment to accommodate its users' evolving needs. However, we currently lack a repeatable, consistent method to teach high-level collaborative design skills. Drawing on the serious play framework, we advance an existing analog exercise for scaffolding collaborative design using a new system: the LLM-managed application overview. From an instructor prompt, the system generates an overview detailing an entire application using CRC cards -- common industry design aids that forego any code or implementation detail. Students individually edit the cards to redesign the application's architecture, while the system simulates the effects of these edits by updating emulated code metrics and estimating redesign cost. Returning to their teams, students discuss the cost and complexity of their designs before selecting and refining a single solution. By the activity's end, the students will have practiced all the design skills necessary for a months-long cycle of development, without the students or the instructor manually managing any implementation details.

Most of the attention on GenAI in computing education has focused on programming-centric tasks, such as code generation, giving feedback on code, or providing synthetic programming partners. Yet in advanced software engineering and project courses, interpersonal skills such as team meetings or customer interviews are equally important but difficult and instructor-intensive to teach realistically. GenAI presents the possibility of scaffolding the teaching of some of these practices by enabling exercises in which students develop the ability to investigate a topic by iteratively asking questions to find a solution. The goal is to create scenarios in which students train to interact with humans in real-world situations, simulating these interactions in a controlled, guided environment. These simulations could help students practice and refine ''soft skills,'' such as teamwork and interviewing, by mimicking the types of exchanges and problem-solving they would encounter in professional environments. This approach allows learners to engage in realistic communication exercises, improving their ability to handle complex, interpersonal tasks through repeated practice with AI-guided feedback. As an example, we envision examples that include requirements elicitation with customers, development team meetings, and discussion with potential investors, to name just a few.

Mastering algorithms and graph theory requires students to understand both the theoretical concepts and the practical mechanics. While most current assessments focus on the practical aspects, a deeper understanding of the theoretical concepts is often more crucial for truly grasping the material. Visualizations aim to help bridge this gap by allowing students to interact with data structures to trace traversals and outputs dynamically. We introduce an interactive tool through an online assessment platform that will enable students to click on different nodes and/or edges to dynamically change a graph model. There are numerous use cases, from introductory data structures and traversals such as depth-first and breadth-first search to more complicated algorithms such as tracing hypercube node processing. Although there are currently decorative components that display graphs and can be supplemented with submission elements, we hypothesize that by combining both features into one, students' learning will be significantly more effective. Through such a tool, we plan to assess students' performance in regard to (a) their score, (b) completion time, and (c) student satisfaction with the interactive assessments. We plan to analyze the types of errors students make depending on whether they are in the control or experimental groups. Further, we aim to assess how abstracting interactive assessment tools can be applied to introductory computer science courses to bridge the gap between proficiency and mastery learning.

Delivery of affordable, secure, and scalable assessments is an essential component of large university courses, whether online or in-person. The transition to Computer-Based Testing (CBT) has a transformational effect on pedagogy. Modern CBT systems provide almost unlimited flexibility in the types of questions they can support for manual grading and autograding. In this BoF, faculty interested in learning about various components of CBT and how to implement it at their institution are invited to ask their questions and learn from others who have already done this. To facilitate these discussions, in this BOF we will break into four smaller groups to discuss CBT pedagogy, building and sharing question banks, technical or logistical considerations, and building buy-in from all levels of the institution.

Parsons Problems and Faded Parsons Problems have been shown to be effective in helping students in programming courses transition from passive learning, such as lectures or textbooks, to active learning in the form of writing code. We present FPPgen, an authoring system that largely automates the conversion of existing open-ended code-writing exercises to Faded Parsons Problems (FPPs). FPP solutions can be machine-checked using either spec-based autograding, in which student solutions are evaluated against instructor-provided test cases, or mutation-based autograding, in which students produce one or more unit tests that are evaluated using mutation testing. Our system allows creating exercises that rely on complex libraries and helper functions, such as student code intended to be run as part of a complex framework-based application. Our system also gracefully supports cumulative multi-part problems, in which later parts build on earlier parts. Python and Ruby exercises are currently supported, but FPPgen is language-agnostic and adding autograders for other languages is straightforward. In our experience so far, instructors can draft simple questions in less than an hour and mutation-based questions in about two hours as open-ended coding questions, and student helpers can use our tools to convert these to FPPs in less than an hour. FPPgen is in active use in both beginning and advanced large-enrollment programming courses in a CS undergraduate program at a large US university.

Table transformations are a critical skill to master in order to fluently work with data. In introductory data science courses, however, students have found these transformations particularly challenging to learn. One complex transformation is the pivot transformation, which reorganizes a table based on aggregation and summarizing along selected columns and rows. Current assessments test student understanding in static scenarios. Thus, there is an opportunity to help students explicitly work through the steps and variables needed to express a pivot transformation in a randomizable manner. As such, we explore whether a dynamic digital assessment for the pivot transformation can effectively achieve mastery learning towards this skill. Our design is inspired by Parsons problems, in which answer components (pivot table output labels and values) can be composed into the output of a pivot transformation. A question can be derived from a small randomized dataset, and randomized Pandas code that operates upon the dataset and can be autograded. We plan to conduct a pilot study with data science students to investigate whether 1) using a programmable online platform to practice pivot tables helps improve performance on exams, and 2) randomization and instant feedback on the online platform contribute to improved student learning.

Affordable, secure, and scalable assessment delivery is an essential component of large university courses, whether online or in-person. The switch to Computer-Based Testing (CBT) can have a surprising, and almost transformational effect on pedagogy. Modern CBT systems provide almost unlimited flexibility in the types of questions they can support, for both manual grading and autograding, and CBT has now been adopted at several universities and is under serious consideration at others. In this BoF, faculty interested in learning about CBT and how to implement it at their institution are invited to ask their questions. Faculty experienced with CBT are invited to share how CBT has changed their approach, pedagogy, and behavior and how to advocate for its adoption.

In this work, we present the development of an automated extension tool that supports flexible extension policies. Students interact with a wide range of extension policies in similar ways; in particular, some students repeatedly request multi-day long extensions. When scaled to courses with hundreds or potentially thousands of students, course staff time is the limiting resource preventing adequate student support. We present a tool to help automate a range of extension processes. The use of this tool should reduce staff load while increasing individualized student support, through email communication and consequent recovery of student agency. Our early research questions are: Does the extension tool reduce barriers and stigma around asking for assistance? Does the tool lessen the wait time between requesting and receiving an extension, and how does the tool improve students' learning experience in the course? These questions will help inform us about how an automated tool for flexible extensions helps support growing course sizes and students who may not otherwise receive the support they need for their success and well-being in the course.

Equitable grading practices and flexible deadline policies have previously demonstrated positive student learning and well-being outcomes. In this poster, we contribute a framework for flexible extension policies that emphasize equitable grading. We then analyze extension requests and grades obtained by students in a Data Science course with a flexible extension policy. We present two research questions based on this data. RQ1: How does the length of an extension relate to student performance on the corresponding assignment? RQ2: How does student extension usage across the semester relate to students' learning of the content?

We propose a new exercise format for an upper-division software engineering course. The exercises scaffold the gap between the "box and arrows" representation of a complex software architecture and the nuts-and-bolts realization of that architecture in code. A qualitative study with 12 upper-division computer science students explored the effectiveness of these exercises as a teaching tool and opportunities to improve them. All participants desire for these new exercises to be incorporated into their course, self-rating the exercises as educational and confidence-boosting, suggesting these new types of exercises will pave the way for more confident and competent software engineers.

Abstract Context Women have historically been underrepresented in Software Engineering, due in part to the stereotyped assumption that women are less technically competent than men. Pair programming is both widely used in industry and has been shown to increase student interest in Software Engineering, particularly among women; but if those same gender biases are also present in pair programming, its potential for attracting women to the field could be thwarted. Objective We aim to explore the effects of gender bias in pair programming. Specifically, in a remote setting in which students cannot directly observe the gender of their peers, we study whether the perception of the partner, the behavior during programming, or the style of communication of Software Engineering students differ depending on the perceived gender of their remote partner. To our knowledge, this is the first study specifically focusing on the impact of gender stereotypes and bias within pairs in pair programming. Method We have developed an online pair-programming platform () that provides a collaborative editing window and a chat pane, both of which are heavily instrumented. Students in the control group had no information about their partner’s gender, whereas students in the treatment group could see a gendered avatar representing the other participant as a man or as a woman. The gender of the avatar was swapped between programming tasks to analyze 45 variables related to the collaborative coding behavior, chat utterances, and questionnaire responses of 46 pairs in the original study at the University of Seville, and 23 pairs in the external replication at the University of California, Berkeley. Results We did not observe any statistically significant effect of the gender bias treatment, nor any interaction between the perceived partner’s gender and subject’s gender, in any of the 45 response variables measured in the original study. In the external replication, we observed statistically significant effects with moderate to large sizes in four dependent variables within the experimental group, comparing how subjects acted when their partners were represented as a man or a woman. Conclusions The results in the original study do not show any clear effect of the treatment in remote pair programming among current Software Engineering students. In the external replication, it seems that students delete more source code characters when they have a woman partner, and communicate using more informal utterances, reflections and yes/no questions when they have a man partner, although these results must be considered inconclusive because of the small number of subjects in the replication, and because when multiple test corrections are applied, only the result about informal utterances remains significant. In any case, more mixed methods replications are needed in order to confirm or refute the results in the same and other Software Engineering students populations.

"A's for All (as time and interest allow)" is a position that says it is increasingly possible to aim for a world in which students can achieve any grade (level of mastery) that they are willing to work for, even if some students take longer than others or require more practice to get there. Achieving this goal would have profound effects on fairness, equity, and participation in computing, to say nothing of student learning outcomes. We describe what this goal would entail, why it is worth pursuing, what the mechanism and policy requirements are for making progress, and why now is a good time to do it. We give specific and actionable recommendations, many based on our own experience so far, that our colleagues who are excited about the approach can put into immediate practice, and address a number of concerns and objections that our proposal may raise. Importantly, our proposed approach is not all-or-nothing, but all-or-something: there are many things instructors can do within existing policy frameworks and course constraints to move their course experience in this direction.

Pair Programming (PP) is both a common practice in professional software engineering and a valuable pedagogical tool. Disciplined user-centric research on pair programming can answer important questions about how students use and benefit from PP. We have developed a platform called Twincode that includes features to support pair programming assignments, comprehensive instrumentation to enable studying how the PP partners interact, and additional tools to help in analyzing the instrumentation, in particular for utterance tagging in discourse analysis. This demo will take the audience through the entire process of conducting research on the Twincode platform: from users pair programming on the platform, to utterance tagging of user date, to data analysis in support of research questions.

Student teaching assistants (TAs) are essential contributors to CS education and are often the first point of contact for many students. Given increasing evidence that student achievement is directly correlated to a positive classroom climate, an effective TA must possess not only strong domain and pedagogical skills, but also the skills necessary to maintain an inclusive, welcoming, and supportive classroom environment. Our view is that there is no meaningful separation between pedagogical and climate skills: rather than "compartmentalizing" climate into specific workshops or modules of a course, our semester-long required TA preparation course treats classroom climate as a lens through which traditional pedagogical skills are viewed, such as giving presentations that encourage participation, creating equitable assessments, and creating successful student groups by fostering belonging. We describe a climate-first, scalable, modular TA training curriculum with open-source and curated teaching materials, suitable for in-person or remote instruction, that serves hundreds of first-time TAs each year, and which student feedback suggests is meeting our goals.

Testing and test-writing are key skills for software engineers. Yet most CS curricula spend insufficient time on testing, and some studies have even found that graduating CS students enter developer jobs without these skills. We argue that test writing is a programming pattern that, at least when going beyond simple input/output test cases, is new and unfamiliar to most students, so that teaching test-writing requires not only teaching the strategic concepts of thinking about testing, but also how to instantiate the "arrange--act--assert" pattern of which all tests consist. Teaching how to recognize and instantiate this pattern is complicated by having to learn how to use testing frameworks and libraries---essentially a syntactic obstacle. Faded Parsons Problems (FPPs) have been shown to be a novel and effective type of exercise for exposing students to programming patterns by varying the amount of scaffolding provided. FPPs give similar learning gains to code-writing exercises but are preferred by students, and can be designed to "scaffold away'' some syntactic obstacles that can impede students' ability to become fluent in test-writing. To our knowledge, neither FPPs nor the original Parsons Problems have previously been proposed to teach advanced programming patterns to advanced students. We present our design of a system for creating variably-scaffolded test-writing exercises in the form of FPPs, including autograding tests using existing autograding solutions augmented with techniques from mutation testing.

Learning to recognize and apply programming patterns — reusable abstractions of code — is critical to becoming a proficient computer scientist. However, many introductory Computer Science courses do not teach patterns, in part because teaching these concepts requires significant curriculum changes. As an alternative, we explore how a novel user interface for practicing coding — Faded Parsons Problems — can support introductory Computer Science students in learning to apply programming patterns. We ran a classroom-based study with 237 students which found that Faded Parsons Problems, or rearranging and completing partially blank lines of code into a valid program, are an effective exercise interface for teaching programming patterns, significantly surpassing the performance of the more standard approaches of code writing and code tracing exercises. Faded Parsons Problems also improve overall code writing ability at a comparable level to code writing exercises, but are preferred by students.

poster Share on Exploring the Impact of Gender Bias on Pair Programming Authors: Aslihan Akalin UC Berkeley, USA UC Berkeley, USAView Profile , Nathaniel Weinman UC Berkeley, USA UC Berkeley, USAView Profile , Katherine Stasaski UC Berkeley, USA UC Berkeley, USAView Profile , Armando Fox UC Berkeley, USA UC Berkeley, USAView Profile Authors Info & Claims ICER 2021: Proceedings of the 17th ACM Conference on International Computing Education ResearchAugust 2021 Pages 435–437https://doi.org/10.1145/3446871.3469790Online:17 August 2021Publication History 0citation80DownloadsMetricsTotal Citations0Total Downloads80Last 12 Months80Last 6 weeks16 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

While project-based software engineering courses aim to provide learning opportunities grounded in professional processes, it is not always possible to replicate every process in classrooms due to course constraints. Previous studies observed how students react to various processes and gave retroactive recommendations. In this study, we instead combine a field study on professional Agile (eXtreme Programming, XP) teams and an established team process taxonomy to proactively select team processes to incorporate in a project-based software engineering course. With collected knowledge from the field study, we choose three XP processes to augment the design of a mature software engineering project course. We choose processes that are 1) considered important by professionals, and 2) complete with respect to coverage of the taxonomy's main categories. We then compare the augmented course design with the original design in a case study. Our results suggest that 1) even without extra resources, adding these new processes does not interfere with learning opportunities for XP processes previously existing in the course design; 2) student teams experience similar benefits from these new processes as professional teams do, and students appreciate the usefulness and value of the processes. In other words, our approach allows instructors to make conscious choices of XP processes that improve student learning outcomes while exposing students to a more complete set of processes and thus preparing them better for professional careers. Course designers with limited resources are encouraged to use our methodology to evaluate and improve the designs of their own project-based courses.

Introductory programming classes teach students to program using worked examples, code tracing, and code writing exercises. Parsons Problems are an educational innovation in which students unscramble provided lines of code, as a step towards bridging the gap between reading and writing code. Though Parsons Problems have been found effective, there is some evidence that students can use syntactic heuristics to help them solve these problems without fully understanding the solution.. To address this limitation, we introduce Faded Parsons Problems, a variation of Parsons Problems where parts of the provided code are incomplete. We explore a specific instantiation of this idea, Blank-Variable Parsons Problems, in which all variable names are blanked out. Unlike another Parsons Problem variation - adding distractor code lines - Blank-Variable Parsons can be automatically created from a solution without additional effort from an instructor. A 75 minute pilot study with CS1 students indicates that solving standard Parsons Problems does not lead to short-term near-transfer in code writing, suggesting a need for problems with less scaffolding. Additionally, students self-report Blank-Variable Parsons as fitting in difficulty between Parsons Problems and code writing, suggesting Blank-Variable Parsons may be one opportunity to fill this gap.

A recent in-class exam in a software engineering course included a section in which students had to write code and/or tests under conditions they might face on real software engineering projects, including complex, multi-part coding questions in which later parts of the question build on earlier parts. To avoid "cascading penalties" on later questions that build on earlier ones, students could reveal the answer for any question during the exam for a "reveal penalty": If the student identified the correct place in the code to copy and paste the revealed answer, they would get 20% of the question points. That is, by simply revealing every answer and copy-pasting it correctly, even the weakest student should be able to achieve 20% of the points for the coding portion of the exam. In this paper, we study how students used this mechanism. Surprisingly, some students chose to take zero points for certain questions rather than revealing the answer, and some who asked for an answer to be revealed were unable to correctly incorporate it to get the question correct. We also find a correlation between student scores on the non-coding multiple-choice section of the exam, which had no hints/reveals available, and the coding section, even though students who performed poorly on the non-coding first half of the exam should have been able to score well on the coding part by using the reveal mechanism. That is, weak students did not benefit as much as would be expected from revealable answers. Pedagogical interpretation of these results informs our future use of the "buy a hint" format for coding-based exams.

Agile/XP (Extreme Programming) software teams are expected to follow a number of specific practices in each iteration, such as estimating the effort (”points”) required to complete user stories, properly using branches and pull requests to coordinate merging multiple contributors’ code, having frequent ”standups” to keep all team members in sync, and conducting retrospectives to identify areas of improvement for future iterations. We combine two observations in developing a methodology and tools to help teams monitor their performance on these practices. On the one hand, many Agile practices are increasingly supported by web-based tools whose ”data exhaust” can provide insight into how closely the teams are following the practices. On the other hand, some of the practices can be expressed in terms similar to those developed for expressing service level objectives (SLO) in software as a service; as an example, a typical SLO for an interactive Web site might be ”over any 5-minute window, 99% of requests to the main page must be delivered within 200ms” and, analogously, a potential Team Practice (TP) for an Agile/XP team might be ”over any 2-week iteration, 75% of stories should be ’1-point’ stories”. Following this similarity, we adapt a system originally developed for monitoring and visualizing service level agreement (SLA) compliance to monitor selected TPs for Agile/XP software teams. Specifically, the system consumes and analyzes the data exhaust from widely-used tools such as GitHub and Pivotal Tracker and provides team(s) and coach(es) a ”dashboard” summarizing the teams’ adherence to various practices. As a qualitative initial investigation of its usefulness, we deployed it to twenty student teams in a four-sprint software engineering project course. We find an improvement of the adherence to team practice and a positive students’ self-evaluations of their team practices when using the tool, compared to previous experiences using an Agile/XP methodology. The demo video is located at https://youtu.be/A4xwJMEQh9c and a landing page with a live demo at https://isa-group.github.io/2019-05-eagle-demo/.

Linear operators used in iterative methods like conjugate gradient have typically been implemented either as ""matrix-driven"" subroutines backed by explicit sparse or dense matrices, or as ""matrix-free"" subroutines that implement specific linear operations directly (e.g. FFTs). The matrix-driven approach is generally more portable because it can target widely-available BLAS libraries, but it can be inefficient in terms of time and space complexity. In contrast, the matrix-free approach is more performant because it leverages structure in operations, but it requires each operator be re-implemented on each new platform. To increase performance and portability, we propose a hybrid approach that represents linear operators as expression trees. Leaf nodes in the tree are either matrix-free or matrix-driven operators, and interior nodes represent mathematical compositions (sums, products, transposes) or structural compositions (stacks, block diagonals, etc.) of the leaf operators. This representation enables expert-guided reordering and fusion transformations that can improve performance or reduce memory pressure. We implement our approach in a domain-specific language called Indigo. We assess Indigo on image reconstruction problems arising in four application areas: magnetic resonance imaging, ptychography, magnetic particle imaging, and fluorescent microscopy. We give performance results from vendor BLAS libraries, and we introduce specializations to Sparse BLAS routines that achieve near-Roofline performance on multi-core, many-core, and GPU systems.

Project-based learning is an important teaching method in software engineering education. However, it is unclear how student projects can be evaluated objectively and systematically in classrooms. Measurements used in industry, such as quality of the codebase, are not the only expected outcomes in classrooms; informative assessments in project-based learning require more details about how students behave as individuals and as a team. In this paper, we establish the importance of measuring processes in project-based software engineering courses and present metrics mined from software development tools for monitoring and observing processes to facilitate teaching. A case study at a US university confirms that 1) teams with better conformance to software development processes achieve better outcomes, and 2) our approach can be used to design metrics that serve as early detectors of violations to software development processes. Our results suggest that instructors for software engineering courses can use our approach to design process metrics for systematic, targeted, and automatic evaluation of team projects. Furthermore, metrics designed using our approach can be used as building blocks for automated systems, and thus increase the scalability of project-based software engineering courses.

Pencil-and-paper coding questions on computer science exams are unrealistic: real developers work at a keyboard with extensive resources at hand, rather than on paper with few or no notes. We address the challenge of administering a proctored exam in which students must write code that passes instructor-provided test cases as well as writing test cases of their own. The exam environment allows students broad access to Internet resources they would use for take-home programming assignments, while blocking their ability to use that facility for direct communication with colluders. Our system supports cumulative questions (in which later parts depend on correctly answering earlier parts) by allowing the test-taker to reveal one or more hints by sacrificing partial credit for the question. Autograders built into the exam environment provide immediate feedback to the student on their exam grade. In case of grade disputes, a virtual machine image reflecting all of the student's work is preserved for later inspection. While elements of our scheme have appeared in the literature (autograding, semi-locked-down computer environments for exam-taking, hint "purchasing"), we believe we are the first to combine them into a system that enables realistic in-class coding-based exams with broad Internet access. We report on lessons and experience creating and administering such an exam, including autograding-related pitfalls for high-stakes exams, and invite others to use and improve on our tools and methods.

Formative feedback is important for learning. Code-tracing is a vital skill in computer science learning. We set out to deliver formative feedback to students on code-tracing, constructed-response assessments by building a student error model using insights gained from inspecting the assessment's frequent wrong answers. Moreover, we compared two different kinds of hints: reteaching and knowledge integration. We found wrong answer co-occurrence provides useful information for our model. However, we were unable to find evidence in our intervention experiment that our hints improved student outcomes on post-test questions. Therefore, we also report here our results on a retrospective, exploratory analysis to understand potential reasons why our results are null.

Quantifying the value of developers’ code contributions to a software project requires more than simply counting lines of code or commits. We define the development value of code as a combination of its structural value (the effect of code reuse) and its non-structural value (the impact on development). We propose techniques to automatically calculate both components of development value and combine them using Learning to Rank. Our preliminary empirical study shows that our analysis yields richer results than those obtained by human assessment or simple counting methods and demonstrates the potential of our approach.

Constructed-response, code-tracing questions ("What would Python print?") are good formative assessments. Unlike selected-response questions simply marked correct or incorrect, a constructed wrong answer can provide information on a student's particular difficulty. However, constructed-response questions are resource-intensive to grade manually, and machine grading yields only correct/incorrect information. We analyzed incorrect constructed responses from code-tracing questions in an introductory computer science course to investigate whether a small subsample of such responses could provide enough information to make inspecting the subsample worth the effort, and if so, how best to choose this subsample. In addition, we sought to understand what insights into student difficulties could be gained from such an analysis.

Teaching software development teams can be difficult to scale. Based on various cloud-based software development tools, Teamscope provides automated or semi-automated metrics to improve the scalability of a course with team projects. Metrics developed in Teamscope provide a synthesized view of a student team. Our preliminary results have shown the validity of these metrics. We also present a case study of applying metrics to teaching software development course in this paper.

Teaching students to write code with good style is important but difficult: in-depth feedback currently requires a human. AutoStyle, a style tutor that scales, offers adaptive, real-time holistic style feedback and hints as students improve their code. An in-situ study with 103 undergraduate students in a CS class compared AutoStyle to a control tutor which only offered ABC score. While students improved the style of their code in both cases, students working with AutoStyle were more likely to use an appropriate language idiom and to improve their recognition of good style. However, students struggled to implement style improvements, even when hints recommended specific functions.

In contrast to multiple-choice or selected response questions, constructed response questions can result in a wide variety of incorrect responses. However, constructed responses are richer in information. We propose a technique for using each student's constructed responses in order to identify a subset of their stable conceptual misunderstandings. Our approach is designed for courses with so many students that it is infeasible to interpret every distinct wrong answer manually. Instead, we label only the most frequent wrong answers with the misunderstandings that they indicate, then predict the misunderstandings associated with other wrong answers using statistical co-occurrence patterns. This tiered approach leverages a small amount of human labeling effort to seed an automated procedure that identifies misunderstandings in students. Our approach involves much less effort than inspecting all answers, substantially outperforms a baseline that does not take advantage of co-occurrence statistics, proves robust to different course sizes, and generalizes effectively across student cohorts.

Deep neural networks (DNNs) have undergone a surge in popularity with consistent advances in the state of the art for tasks including image recognition, natural language processing, and speech recognition. The computationally expensive nature of these networks has led to the proliferation of implementations that sacrifice abstraction for high performance. In this paper, we present Latte, a domain-specific language for DNNs that provides a natural abstraction for specifying new layers without sacrificing performance. Users of Latte express DNNs as ensembles of neurons with connections between them. The Latte compiler synthesizes a program based on the user specification, applies a suite of domain-specific and general optimizations, and emits efficient machine code for heterogeneous architectures. Latte also includes a communication runtime for distributed memory data-parallelism. Using networks described using Latte, we demonstrate 3-6x speedup over Caffe (C++/MKL) on the three state-of-the-art ImageNet models executing on an Intel Xeon E5-2699 v3 x86 CPU.

This research investigates how to introduce synchronous interactive peer learning into an online setting appropriate both for crowdworkers (learning new tasks) and students in massive online courses (learning course material). We present an interaction framework in which groups of learners are formed on demand and then proceed through a sequence of activities that include synchronous group discussion about learner-generated responses. Via controlled experiments with crowdworkers, we show that discussing challenging problems leads to better outcomes than working individually, and incentivizing people to help one another yields still better results. We then show that providing a mini-lesson in which workers consider the principles underlying the tested concept and justify their answers leads to further improvements. Combining the mini-lesson with the discussion of the multiple-choice question leads to significant improvements on that question. We also find positive subjective responses to the peer interactions, suggesting that discussions can improve morale in remote work or learning settings.

The results of a study of online peer learning suggests that it may be advantageous to automatically assign students to small peer learning groups based on how many students initially get answers to questions correct.

While large-scale automatic grading of student programs for correctness is widespread, less effort has focused on automating feedback for good programming style:} the tasteful use of language features and idioms to produce code that is not only correct, but also concise, elegant, and revealing of design intent. We hypothesize that with a large enough (MOOC-sized) corpus of submissions to a given programming problem, we can observe a range of stylistic mastery from naïve to expert, and many points in between, and that we can exploit this continuum to automatically provide hints to learners for improving their code style based on the key stylistic differences between a given learner's submission and a submission that is stylistically slightly better. We are developing a methodology for analyzing and doing feature engineering on differences between submissions, and for learning from instructor-provided feedback as to which hints are most relevant. We describe the techniques used to do this in our prototype, which will be deployed in a residential software engineering course as an alpha test prior to deploying in a MOOC later this year.

A challenge in introductory and intermediate programming courses is understanding how students approached solving a particular programming problem, in order to provide feedback on how they might improve. In both Massive Open Online Courses (MOOCs) and large residential courses, such feedback is difficult to provide for each student individually. To multiply the instructor's leverage, we would like to group student submissions according to the general problem-solving strategy they used, as the first stage of a ``feedback pipeline''. We describe ongoing explorations of a variety of clustering algorithms and similarity metrics using a corpus of over 800 student submissions to a simple programming assignment from a programming MOOC. We find that for a majority of submissions, it is possible to automatically create clusters such that an instructor ``eyeballing'' some representative submissions from each cluster can readily describe qualitatively what the common elements are in student submissions in that cluster. This information can be the basis for feedback to the students or for comparing one group of students' approach with another's.

Ongoing student feedback on course content and assignments can be valuable for MOOC instructors in the absence of face-to-face-interaction. To collect ongoing feedback and scalably identify valuable suggestions, we built the MOOC Collaborative Assessment and Feedback Engine (M-CAFE). This mobile platform allows MOOC students to numerically assess the course, their own performance, and provide textual suggestions about how the course could be improved on a weekly basis. M-CAFE allows students to visualize how they compare with their peers and read and evaluate what others have suggested, providing peer-to-peer collaborative filtering. We evaluate M-CAFE based on data from two EdX MOOCs.

No abstract available.

Massive open online courses (MOOCs) rely primarily on discussion forums for interaction among students. We investigate how forum design affects student activity and learning outcomes through a field experiment with 1101 participants on the edX platform. We introduce a reputation system, which gives students points for making useful posts. We show that, as in other settings, use of forums in MOOCs is correlated with better grades and higher retention. Reputation systems additionally produce faster response times and larger numbers of responses per post, as well as differences in how students ask questions. However, reputation systems have no significant impact on grades, retention, or the students' subjective sense of community. This suggests that forums are essential for MOOCs, and reputation systems can improve the forum experience, but other techniques are needed to improve student outcomes and community formation. We also contribute a set of guidelines for running field experiments on MOOCs.

Pair programming, a form of collaborative learning where two programmers work on the same computer, enhances learning in novice programmers and improves code quality in experienced programmers. Remote pair programming (RPP) brings the pedagogical technique of pair programming to the distributed online environment of Massively Open Online Courses (MOOCs). edX's CS169 Software as a Service MOOC successfully uses a Google+ community for students to generate their own RPP events or join events created by their peers. This paper examines survey results summarizing the RPP experiences and RPP technologies of student pairings in the Fall 2013 offering of CS169. In the future, the aim is to generalize RPP methodology through analyzing RPP sessions, expand applications of RPP to other MOOCs and traditional classrooms, and compare its effectiveness to in-person pair programming.

We study effects of introducing a real-time chatroom into a massive open online course with several thousand students, supplementing an existing forum. The chatroom was supported by teaching assistants, and generated thousands of lines of discussion by 28\% of 681 consenting chat condition participants, mostly on-topic. Despite this, chat activity remained low ($\mu=8.2$ messages per hour) and we could find no significant effect of chat use on objective or subjective dependent variables such as grades, retention, forum participation, or students' sense of community. Further investigation reveals that only 12\% of chat participants have substantive interactions, while the remainder are either passive or have trivial interactions that are unlikely to result in learning.

Peer learning, in which students discuss questions in small groups, has been widely reported to improve learning outcomes in traditional classroom settings. Classroom-based peer learning relies on students being in the same place at the same time to form peer discussion groups, but this is rarely true for online students in MOOCs. We built a software tool that facilitates chat-based peer learning in MOOCs by 1) automatically forming ad-hoc discussion groups and 2) scaffolding the interactions between students in these groups. We report on a pilot deployment of this tool; post-use surveys administered to participants show that the tool was positively received and support the feasibility of synchronous online collaborative learning in MOOCs.

For an instructor who is teaching a massive open online course (MOOC), what is the best way to understand their class? What is the best way to view how the students are interacting with the content while the course is running? To help prepare for the next iteration, how should the course's data be best analyzed after the fact? How do these instructional monitoring needs differ between online courses with tens of thousands of students and courses with only tens? This paper reports the results of a survey of 92 MOOC instructors who answered questions about which information they find useful in their course, with the end goal of creating an information display for MOOC instructors.

Pair programming, a form of collaborative learning where two programmers work on the same computer, enhances learning in novice programmers and improves code quality in experienced programmers. Remote pair programming (RPP) brings the pedagogical technique of pair programming to the distributed online environment of Massively Open Online Courses (MOOCs). UC BerkeleyX's CS169 Software as a Service MOOC successfully uses a Google+ community for students to generate their own RPP events or join events created by their peers. We will examine survey results summarizing the RPP experiences and RPP technologies of student pairings in the Fall 2013 offering of CS169, as well as analyze RPP sessions. In the future, the aim is to generalize RPP methodology, expand its applications to other MOOCs and traditional classrooms, and compare its effectiveness to in-person pair programming.

High-level productivity languages such as Python, Matlab, and R are popular choices for scientists doing data analysis. However, for today's increasingly large datasets, applications written in these languages may run too slowly, if at all. In such cases, an experienced programmer must typically rewrite the application in a less-productive performant language such as C or C++, but this work is intricate, tedious, and often non-reusable. To bridge this gap between programmer productivity and performance, we extend an existing framework that uses just-in-time code generation and compilation. This framework uses the SEJITS methodology, (Selective Embedded Just-In-Time Specialization [11]), converting programs written in domain specific embedded languages (DSELs) to programs in languages suitable for high performance or parallel computation.

High performance is a crucial consideration when executing a complex analytic query on a massive semantic graph. In a semantic graph, vertices and edges carry attributes of various types. Analytic queries on semantic graphs typically depend on the values of these attributes; thus, the computation must view the graph through a filter that passes only those individual vertices and edges of interest. Knowledge Discovery Toolbox (KDT), a Python library for parallel graph computations, is customizable in two ways. First, the user can write custom graph algorithms by specifying operations between edges and vertices. These programmer-specified operations are called semiring operations due to KDT's underlying linear-algebraic abstractions. Second, the user can customize existing graph algorithms by writing filters that return true for those vertices and edges the user wants to retain during algorithm execution. For high productivity, both semiring operations and filters are written in a high-level language, resulting in relatively low performance due to the bottleneck of having to call into the Python virtual machine for each vertex and edge. In this work, we use the Selective Embedded JIT Specialization (SEJITS) approach to automatically translate semiring operations and filters defined by programmers into a lower-level efficiency language, bypassing the upcall into Python. We evaluate our approach by comparing it with the high-performance Combinatorial BLAS engine, and show our approach enables users to write in high-level languages and still obtain the high performance of low-level code. We also present a new roofline model for graph traversals, and show that our high-performance implementations do not significantly deviate from the roofline. Overall, we demonstrate the first known solution to the problem of obtaining high performance from a productivity language when applying graph algorithms selectively on semantic graphs.

Abstract—Communication-optimal algorithms are known for square matrix multiplication. Here, we obtain the first communication-optimal algorithm for all dimensions of rectangular matrices. Combining the dimension-splitting technique of Frigo, Leiserson, Prokop and Ramachandran (1999) with the recursive BFS/DFS approach of Ballard, Demmel, Holtz, Lipshitz and Schwartz (2012) allows for a communication-optimal as well as cache- and network-oblivious algorithm. Moreover, the implementation is simple: approximately 50 lines of code for the shared-memory version. Since the new algorithm minimizes communication across the network, between NUMA domains, and between levels of cache, it performs well in practice on both shared- and distributed-memory machines. We show significant speedups over existing parallel linear algebra libraries both on a 32-core shared-memory machine and on a distributed-memory supercomputer. Index Terms—communication-avoiding algorithms; linear algebra; matrix multiplication I.

Developers of rapidly growing applications must be able to anticipate potential scalability problems before they cause performance issues in production environments. A new type of data independence, called scale independence, seeks to address this challenge by guaranteeing a bounded amount of work is required to execute all queries in an application, independent of the size of the underlying data. While optimization strategies have been developed to provide these guarantees for the class of queries that are scale-independent when executed using simple indexes, there are important queries for which such techniques are insufficient.

High performance is a crucial consideration when executing a complex analytic query on a massive semantic graph. In a semantic graph, vertices and edges carry "attributes" of various types. Analytic queries on semantic graphs typically depend on the values of these attributes; thus, the computation must either view the graph through a "filter" that passes only those individual vertices and edges of interest, or else must first materialize a subgraph or subgraphs consisting of only the vertices and edges of interest. The filtered approach is superior due to its generality, ease of use, and memory efficiency, but may carry a performance cost.

Domain-expert productivity programmers desire scalable application performance, but usually must rely on efficiency programmers who are experts in explicit parallel programming to achieve it. Since such programmers are rare, to maximize reuse of their work we propose encapsulating their strategies in mini-compilers for domain-specific embedded languages (DSELs) glued together by a common high-level host language familiar to productivity programmers. The nontrivial applications that use these DSELs perform up to 98% of peak attainable performance, and comparable to or better than existing hand-coded implementations. Our approach is unique in that each mini-compiler not only performs conventional compiler transformations and optimizations, but includes imperative procedural code that captures an efficiency expert's strategy for mapping a narrow domain onto a specific type of hardware. The result is source- and performance-portability for productivity programmers and parallel performance that rivals that of hand-coded efficiency-language implementations of the same applications. We describe a framework that supports our methodology and five implemented DSELs supporting common computation kernels.

Newly-released web applications often succumb to a "Success Disaster," where overloaded database machines and resulting high response times destroy a previously good user experience. Unfortunately, the data independence provided by a traditional relational database system, while useful for agile development, only exacerbates the problem by hiding potentially expensive queries under simple declarative expressions. As a result, developers of these applications are increasingly abandoning relational databases in favor of imperative code written against distributed key/value stores, losing the many benefits of data independence in the process. Instead, we propose PIQL, a declarative language that also provides scale independence by calculating an upper bound on the number of key/value store operations that will be performed for any query. Coupled with a service level objective (SLO) compliance prediction model and PIQL's scalable database architecture, these bounds make it easy for developers to write success-tolerant applications that support an arbitrarily large number of users while still providing acceptable performance. In this paper, we present the PIQL query processing system and evaluate its scale independence on hundreds of machines using two benchmarks, TPC-W and SCADr.

Large-scale, user-facing applications are increasingly moving from relational databases to distributed key/value stores for high-request-rate, low-latency workloads. Often, this move is motivated not only by key/value stores' ability to scale simply by adding more hardware, but also by the easy to understand predictable performance they provide for all operations. For complex queries, this approach often requires onerous explicit index management and imperative data lookup by the developer. We propose PIQL, a Performance Insightful Query Language that allows developers to express many queries found on these websites while still providing strict bounds on the number of I/O operations that will be performed.

Evaluating the resiliency of stateful Internet services to significant workload spikes and data hotspots requires realistic workload traces that are usually very difficult to obtain. A popular approach is to create a workload model and generate synthetic workload, however, there exists no characterization and model of stateful spikes. In this paper we analyze five workload and data spikes and find that they vary significantly in many important aspects such as steepness, magnitude, duration, and spatial locality. We propose and validate a model of stateful spikes that allows us to synthesize volume and data spikes and could thus be used by both cloud computing users and providers to stress-test their infrastructure.

Contemporary datacenters comprise hundreds or thousands of machines running applications requiring high availability and responsiveness. Although a performance crisis is easily detected by monitoring key end-to-end performance indicators (KPIs) such as response latency or request throughput, the variety of conditions that can lead to KPI degradation makes it difficult to select appropriate recovery actions. We propose and evaluate a methodology for automatic classification and identification of crises, and in particular for detecting whether a given crisis has been seen before, so that a known solution may be immediately applied. Our approach is based on a new and efficient representation of the datacenter's state called a fingerprint, constructed by statistical selection and summarization of the hundreds of performance metrics typically collected on such systems. Our evaluation uses 4 months of trouble-ticket data from a production datacenter with hundreds of machines running a 24x7 enterprise-class user-facing application. In experiments in a realistic and rigorous operational setting, our approach provides operators the information necessary to initiate recovery actions with 80% correctness in an average of 10 minutes, which is 50 minutes earlier than the deadline provided to us by the operators. To the best of our knowledge this is the first rigorous evaluation of any such approach on a large-scale production installation.

Large-scale websites are increasingly moving from relational databases to distributed key-value stores for high request rate, low latency workloads. Often this move is motivated not only by key-value stores' ability to scale simply by adding more hardware, but also by the easy to understand predictable performance they provide for all operations. While this data model works well, lookups are only done by primary key. More complex queries require onerous, explicit index management and imperative data lookups by the developer. We demonstrate PIQL, a Performance Insightful Query Language that allows developers to express many of the queries found on these websites, while still providing strict bounds on the number of I/O operations for any query.

One of the most challenging aspects of managing a very large data warehouse is identifying how queries will behave before they start executing. Yet knowing their performance characteristics - their runtimes and resource usage - can solve two important problems. First, every database vendor struggles with managing unexpectedly long-running queries. When these long-running queries can be identified before they start, they can be rejected or scheduled when they will not cause extreme resource contention for the other queries in the system. Second, deciding whether a system can complete a given workload in a given time period (or a bigger system is necessary) depends on knowing the resource requirements of the queries in that workload. We have developed a system that uses machine learning to accurately predict the performance metrics of database queries whose execution times range from milliseconds to hours. For training and testing our system, we used both real customer queries and queries generated from an extended set of TPC-DS templates. The extensions mimic queries that caused customer problems. We used these queries to compare how accurately different techniques predict metrics such as elapsed time, records used, disk I/Os, and message bytes. The most promising technique was not only the most accurate, but also predicted these metrics simultaneously and using only information available prior to query execution. We validated the accuracy of this machine learning technique on a number of HP Neoview configurations. We were able to predict individual query elapsed time within 20% of its actual time for 85% of the test queries. Most importantly, we were able to correctly identify both the short and long-running (up to two hour) queries to inform workload management and capacity planning.

We describe a novel application of using data mining and statistical learning methods to automatically monitor and detect abnormal execution traces from console logs in an online setting. Different from existing solutions, we use a two stage detection system. The first stage uses frequent pattern mining and distribution estimation techniques to capture the dominant patterns (both frequent sequences and time duration). The second stage use principal component analysis based anomaly detection technique to identify actual problems. Using real system data from a 203-node Hadoop cluster, we show that we can not only achieve highly accurate and fast problem detection, but also help operators better understand execution patterns in their system.

Surprisingly, console logs rarely help operators detect problems in large-scale datacenter services, for they often consist of the voluminous intermixing of messages from many software components written by independent developers. We propose a general methodology to mine this rich source of information to automatically detect system runtime problems. We first parse console logs by combining source code analysis with information retrieval to create composite features. We then analyze these features using machine learning to detect operational problems. We show that our method enables analyses that are impossible with previous methods because of its superior ability to create sophisticated features. We also show how to distill the results of our analysis to an operator-friendly one-page decision tree showing the critical messages associated with the detected problems. We validate our approach using the Darkstar online game server and the Hadoop File System, where we detect numerous real problems with high accuracy and few false positives. In the Hadoop case, we are able to analyze 24 million lines of console logs in 3 minutes. Our methodology works on textual console logs of any size and requires no changes to the service software, no human input, and no knowledge of the software's internals.

Violations of service level objectives (SLO) in Internet services are urgent conditions requiring immediate attention. Previously we explored (I. Cohen et al., 2004) an approach for identifying which low-level system properties were correlated to high-level SLO violations (the metric attribution problem). The approach is based on automatically inducing models from data using pattern recognition and probability modeling techniques. In this paper we extend our approach to adapt to changing workloads and external disturbances by maintaining an ensemble of probabilistic models, adding new models when existing ones do not accurately capture current system behavior. Using realistic workloads on an implemented prototype system, we show that the ensemble of models captures the performance behavior of the system accurately under changing workloads and conditions. We fuse information from the models in the ensemble to identify likely causes of the performance problem, with results comparable to those produced by an oracle that continuously changes the model based on advance knowledge of the workload. The cost of inducing new models and managing the ensembles is negligible, making our approach both immediately practical and theoretically appealing.

Our ability to design and deploy large complex systems is outpacing our ability to understand their behavior. How do we detect and recover from "heisenbugs," which account for up to 40% of failures in complex Internet systems, without extensive application-specific coding? Which users were affected, and for how long? How do we diagnose and correct problems caused by configuration errors or operator errors? Although these problems are posed at a high level of abstraction, all we can usually measure directly are low-level behaviors---analogous to driving a car while looking through a magnifying glass. Machine learning can bridge this gap using techniques that learn "baseline" models automatically or semi-automatically, allowing the characterization and monitoring of systems whose structure is not well understood a priori. I'll discuss initial successes and future challenges in using machine learning for failure detection anbd diagnosis, configuration troubleshooting, attribution (which low-level properties appear to be correlated with an observed high-level effect such as decreased performance), and failure forecasting.

We present a method for automatically extracting from a running system an indexable signature that distills the essential characteristic from a system state and that can be subjected to automated clustering and similarity-based retrieval to identify when an observed system state is similar to a previously-observed state. This allows operators to identify and quantify the frequency of recurrent problems, to leverage previous diagnostic efforts, and to establish whether problems seen at different installations of the same site are similar or distinct. We show that the naive approach to constructing these signatures based on simply recording the actual ``raw'' values of collected measurements is ineffective, leading us to a more sophisticated approach based on statistical modeling and inference. Our method requires only that the system's metric of merit (such as average transaction response time) as well as a collection of lower-level operational metrics be collected, as is done by existing commercial monitoring tools. Even if the traces have no annotations of prior diagnoses of observed incidents (as is typical), our technique successfully clusters system states corresponding to similar problems, allowing diagnosticians to identify recurring problems and to characterize the ``syndrome'' of a group of problems. We validate our approach on both synthetic traces and several weeks of production traces from a customer-facing geoplexed 24 x 7 system; in the latter case, our approach identified a recurring problem that had required extensive manual diagnosis, and also aided the operators in correcting a previous misdiagnosis of a different problem.

Most Internet services (e-commerce, search engines, etc.) suffer faults. Quickly detecting these faults can be the largest bottleneck in improving availability of the system. We present Pinpoint, a methodology for automating fault detection in Internet services by: 1) observing low-level internal structural behaviors of the service; 2) modeling the majority behavior of the system as correct; and 3) detecting anomalies in these behaviors as possible symptoms of failures. Without requiring any a priori application-specific information, Pinpoint correctly detected 89%-96% of major failures in our experiments, as compared with 20%-70% detected by current application-generic techniques.

Cluster hash tables (CHTs) are key components of many large-scale Internet services due to their highly-scalable performance and the prevalence of the type of data they store. Another advantage of CHTs is that they can be designed to be as self-managing as a cluster of stateless servers. One key to achieving this extreme manageability is reboot-based recovery that is predictably fast and has modest impact on system performance and availability. This "cheap" recovery mechanism simplifies management in two ways. First, it simplifies failure detection by lowering the cost of acting on false positives. This enables one to use statistical techniques to turn hard-to-catch failures, such as node degradation, into failure, followed by recovery. Second, cheap recovery simplifies capacity planning by recasting repartitioning as failure plus recovery to achieve zero-downtime incremental scaling. These low-cost recovery and scaling mechanisms make it possible for the system to be continuously self-adjusting, a key property of self-managing systems.

Developers write Web service composition programs in terms of functionalities (e.g., "WebSearch") to postpone choosing which services of the same functionality to invoke (Google or Yahoo). We provide a higher level of abstraction than this for higher reuse. We express high-level "patterns" (e.g., "SearchAndCollectData") as both objects that can be "specialized" to particular applications ("SearchAnd-DownloadPapers" vs. "SearchAndAddBooksInCart") and objects that are reusable in the construction of higher-level ones. Our approach lets developers write patterns in terms of high-level functionalities (e.g., "CollectData ") and later decide on services to compose that have lower-level functionalities (e.g., "DownloadPapers" or "addBooksIn-Carts"). We describe our prototype and show an example of nested pattern specialization. We also discuss a reuse trade-off, showing that too much abstraction makes the pattern less expressive. Rather, we suggest developers capture what must be guaranteed in every context of invocation, regardless of the service selection.

Ubiquitous computing environments accrete slowly over time rather than springing into existence all at once. Mechanisms are needed for incremental integration- the problem of how to incrementally add or modify behaviors in existing ubicomp environments. Examples include adding new input modalities and choreographing the behavior of existing independent applications. The iROS event heap, via its publish-subscribe coordination mechanism, provides the foundation for interoperation through event intermediation, but does not directly provide facilities for expressing these intermediations. The patch panel provides a general facility for retargeting event flow. Intermediations can be expressed as simple event translation mappings or as more complex finite-state machines. We describe an implemented prototype of the patch panel, including examples of its use drawn from real life applications in production use in the iRoom ubiquitous computing environment.

To programmatically discover and interact with services in ubiquitous computing environments, an application needs to solve two problems: (1) is it semantically meaningful to interact with a service? If the task is "printing a file", a printer service would be appropriate, but a screen rendering service or CD player service would not. (2) If yes, what are the mechanics of interacting with the service - remote invocation mechanics, names of methods, numbers and types of arguments, etc.? Existing service frameworks such as Jini and UPnP conflate these problems - two services are "semantically compatible" if and only if their interface signatures match. As a result, interoperability is severely restricted unless there is a single, globally agreed-upon, unique interface for each service type. By separating the two subproblems and delegating different parts of the problem to the user and the system, we show how applications can interoperate with services even when globally unique interfaces do not exist for certain services.

The dynamism and heterogeneity in ubicomp environments on both short and long time scales implies that middleware platforms for these environments need to be designed ground up for portability, extensibility and robustness. In this paper, we describe how we met these requirements in iROS, a middleware platform for a class of ubicomp environments, through the use of three guiding principles - economy of mechanism, client simplicity and levels of indirection. Apart from theoretical arguments and experimental results, experience through several deployments with a variety of apps, in most cases not done by the original designers of the system, provides some validation in practice that the design decisions have in fact resulted in the intended portability, extensibility and robustness. A retrospective examination of the system leads the authors to the following lesson: A logically-centralized design and physically-centralized implementation enables the best behavior in terms of extensibility and portability along with ease of administration, and sufficient behavior in terms of scalability and robustness.

We present ideas on how to structure software systems for high availability by considering MTTR/MTTF characteristics of components in addition to the traditional criteria, such as functionality or state sharing. Recursive restartability (RR), a recently proposed technique for achieving high availability, exploits partial restarts at various levels within complex software infrastructures to recover from transient failures and rejuvenate software components. Here we refine the original proposal and apply the RR philosophy to Mercury, a COTS-based satellite ground station that has been in operation for over 2 years. We develop three techniques for transforming component group boundaries such that time-to-recover is reduced, hence increasing system availability. We also further RR by defining the notions of an oracle, restart group and restart policy, while showing how to reason about system properties in terms of restart groups. From our experience with applying RR to Mercury, we draw design guidelines and lessons for the systematic application of recursive restartability to other software systems amenable to RR.

Traditional problem determination techniques rely on static dependency models that are difficult to generate accurately in today's large, distributed, and dynamic application environments such as e-commerce systems. We present a dynamic analysis methodology that automates problem determination in these environments by 1) coarse-grained tagging of numerous real client requests as they travel through the system and 2) using data mining techniques to correlate the believed failures and successes of these requests to determine which components are most likely to be at fault. To validate our methodology, we have implemented Pinpoint, a framework for root cause analysis on the J2EE platform that requires no knowledge of the application components. Pinpoint consists of three parts: a communications layer that traces client requests, a failure detector that uses traffic-sniffing and middleware instrumentation, and a data analysis engine. We evaluate Pinpoint by injecting faults into various application components and show that Pinpoint identifies the faulty components with high accuracy and produces few false-positives.

Even after decades of software engineering research, complex computer systems still fail, primarily due to nondeterministic bugs that are typically resolved by rebooting. Conceding that Heisenbugs will remain a fact of life, we propose a systematic investigation of restarts as "high availability medicine." In this paper we show how recursive restartability (RR) - the ability of a system to gracefully tolerate restarts at multiple levels improves fault tolerance, reduces time-to-repair and enables system designers to build flexible, highly available software infrastructures. Using several examples of widely deployed software systems, we identify properties that are required of RR systems and outline an agenda for turning the recursive restartability philosophy into a practical software structuring tool. Finally, we describe infrastructural support for RR systems, along with initial ideas on how to analyze and benchmark such systems.

For many years, people have been trying to develop systems from modular, reusable components. The ideal is zero-code composition: building applications out of components without writing any new code. By investigating zero-code composition, our goal is to make composition easy enough to be of practical use to systems researchers and developers. We are focusing on identifying and removing systemic impediments to composition, and on exploiting composition to achieve systemwide properties, such as performance, scalability, and reliability.

Digital appliances designed to simplify everyday tasks are readily available to end consumers. For example, mobile users can retrieve Web content using handheld devices since content retrieval is well-supported by infrastructure services such as transformational proxies. However, the same type of support is lacking for input-centric devices, those that create content and allow users to share content. This lack of infrastructural support makes input-centric devices hard to use and less useful.The Appliance Data Services project seeks to explore a vision of an appliance computing world where users move data seamlessly among various devices. Based on this vision, we formulate three principles that guide the design of an architecture that helps realize this vision: bring devices to the forefront, minimize the number of device features, and place functionality in the network infrastructure. We evaluate our implementation of the ADS architecture based on these principles, and build applications using the ADS framework to evaluate the ease with which appliance computing applications can be built using the framework. We find that it is relatively simple to build and extend applications on ADS that make using digital devices easier, which results in the devices themselves becoming more useful.

We identifit three fundamental requirements for scalable network services: incremental scalability and oveflow growth provisioning, 24x7 availability through fault masking, and costeffectiveness.We argue that clusters of commodity workstations interconnected by a high-speed SAN are exceptionally well-suited to meeting these challenges for Internet-server workloads, provided the software infrastructure for managing partial failures and administering a large cluster does not have to be reinvented for each new service.To this end, we propose a general, layered architecture for building cluster-based scalable network services that encapsulates the above requirements for reuse, and a service-programming model based on composable workers thatpe$onn transformation, aggregation, caching, i and customization (TACC) of Internet content.For both performance and implementation simplicity, the architecture and TACC programming model exploit BASE, a weaker-than-ACID data semantics that results from trading consistency for availability and relying on sof state for robustness in failure management., Our ,qychitecture can be used as an "off the shelf * irtfrastructural platfonn for creating new network services, allowing authors to focus on the "content" of the service {by composing TACC building blocks) rather than its implementation.We discuss two real implemeritations of services based on this architecture: TranSend, a Web distillation proxy deployed to the UC Berkeley dialup IP population, and HotBot, the commercial implementation of the Inktomi search engine.We present detailed measurements of TranSend's performance based on substantial client traces, as well as anecdotal evidence from the TranSend and HotBot experience, to support the claims made for the architecture.

lligent services. Our extensions are orthogonal in that they provide an interface to a service, which complements the Web browsing experience but is independent of the content of any particular site. We base our experiments on the TranSend service at UC Berkeley, which performs lossy compression on inline images to accelerate dialup Web access for a community of 25,000 subscribers. The service keeps a separate "preferences profile" for each user, which allows each user to vary the aggressiveness of lossy compression, selectively turn off the service for certain pages, and select the type of interface provided for refinement of degraded (lossily compressed) content. We are exploring three technologies for implementing the TranSend service interface: HTML decoration, Java, and JavaS- Server Client Browser Client Browser Proxy Server Server cript. The accompanying video demonstrates prototypes of all three mechanisms. We no

The explosive growth of the Internet and the proliferation of smart cellular phones and handheld wireless devices is widening an already large gap between Internet clients. Clients vary in their hardware resources, software sophistication, and quality of connectivity, yet server support for client variation ranges from relatively poor to none at all. In this paper we introduce some design principles that we believe are fundamental to providing "meaningful" Internet access for the entire range of clients. In particular, we show how to perform on-demand datatype-specific lossy compression on semantically typed data, tailoring content to the specific constraints of the client. We instantiate our design principles in a proxy architecture that further exploits typed data to enable application-level management of scarce network resources. Our proxy architecture generalizes previous work addressing all three aspects of client variation by applying well-understood techniques in a novel way, resulting in quantitatively better end-to-end performance, higher quality display output, and new capabilities for low-end clients.

Even as mobile computing and network computing are gaining momentum, Internet security is sharing the spotlight. Security and authentication on open networks is difficult even without the additional risks posed by wireless media. At the same time, the hardware and software constraints imposed by “small” mobile devices such as PDA’s and smart phones are leading to the pervasive use of application-level proxies to mediate between clients and servers. To date, less attention has been focused specifically on securing the connection between the client and an application-level proxy, independently of any particular service. We describe how to provide secure access to application-level proxied services using an indirect protocol called Charon, which leverages the strong protocol and deployed infrastructure of Kerberos IV. Charon partitions the Kerberos client functionality into a very simple client module that does little more than DES encryption, and a Unix-hosted unprivileged proxy module that runs the remainder of the Kerberos client protocol and can interoperate with other proxy code that provides application-level proxy services. The client module is extremely lightweight and amenable to implementation even on the most modest PDA-class devices. The proxy is trusted as much as any other Kerberized service, but it never learns the user’s Kerberos password or ticketgranting service session key. As a result of this partitioning, clients can continue to enjoy the benefits of proxy-mediated access in a secure way, in addition to gaining secure access to and interoperability with existing Kerberized services.

We introduce visual constraint surfaces as a mechanism to effectively exploit visual constraints in the synthesis of uncertainty-tolerant robot motion plans. We first show how object features, together with their projections onto a camera image plane, define a set of visual constraint surfaces. These visual constraint surfaces can be used to effect visual guarded and visual compliant motions. We then show how the backprojection approach to fine-motion planning can be extended to exploit visual constraints. Specifically, by deriving a configuration space representation of visual constraint surfaces, we are able to include visual constraint surfaces as boundaries of the directional backprojection. By examining the effect of visual constraints as a function of the direction of the commanded velocity, we are able to determine new criteria for critical velocity orientations, i.e. velocity orientations at which the topology of the directional backprojection might change.>