bluuebunny/crossref_metadata_2025 huggingface dataset:
Teaching empirical skills and concepts in computer science using random walks
Authors: Braught Grant
Published: November 2005

An argument is made for integrating the study of empirical skills and concepts into the computer science curriculum. With reference to past work an incremental approach is advocated for the study of these skills and concepts. A unique assignment that exemplifies the advocated approach is presented. This assignment, based on the study of random walks, is intended to introduce empirical investigation as early as is possible, during the first week of the first course. Two extensions to this assignment, one for the first course and one for a programming languages course, are discussed and used to illustrate the advocated incremental approach.
Design patterns for database pedagogy
Authors: Marlowe Thomas J. , Ku Cyril S. , Benham James W.
Published: November 2005

Courses in Relational Databases largely use a domain-specific design approach different from that used in the rest of the curriculum. Use of the Unified Process, UML, and Design Patterns as a pedagogical approach for Databases can leverage previous student experience with design, make knowledge from Database courses more immediately relevant elsewhere, and create greater continuity across the curriculum. This approach allows issues in logical design and in implementation to be more easily connected with similar concerns in other courses (for example, Software Engineering), and supports greater and easier transfer of design between Relational and Object-Oriented Databases, and between databases and embedding applications.
Exploring XML for data exchange in the context of an undergraduate database curriculum
Authors: Dietrich Suzanne W. , Urban Susan D. , Ma Hua , Xiao Yang , Patel Shama
Published: November 2005

The relationship between XML and database management systems has become an important topic for coverage at the undergraduate level. This paper presents an approach to teaching the use of XML through the study of data exchange. After a brief review of XML, the paper provides a tutorial on the different features that are provided in major relational database products for the import and export of XML, providing a discussion of how these features can be used as implementation exercises for students. In addition to addressing the use of XML for data exchange in relational systems, the paper also provides an overview of several teaching tools that are also used in the study of XML for object-oriented data and also for the exchange of object-oriented and object-relational data.
Automated tutoring for a database skills training environment
Authors: Kenny Claire , Pahl Claus
Published: November 2005

Universities are increasingly offering courses online. Feedback, assessment, and guidance are important features of this online courseware. Together, in the absence of a human tutor, they aid the student in the learning process. We present a programming training environment for a database course. It aims to offer a substitute for classroom based learning by providing synchronous automated feedback to the student, along with guidance based on a personalized assessment. The automated tutoring system should promote procedural knowledge acquisition and skills training. An automated tutoring feature is an integral part of this tutoring system.
A real-time information warfare exercise on a virtual network
Authors: Walden James
Published: November 2005

Information warfare exercises, such as "Capture the Flag," serve as a capstone experience for a computer security class, giving students the opportunity to apply and integrate the security skills they learned during the class. However, many information security classes don't offer such exercises, because they can be difficult, expensive, time-consuming, and risky to organize and implement. This paper describes a real-time "Capture the Flag" exercise, implemented using a virtual network with free, open-source software to reduce the risk and effort of conducting such an exercise.
Experience with an industry-driven capstone course on game programming
Authors: Parberry Ian , Roden Timothy , Kazemzadeh Max B.
Published: November 2005

Game programming classes have been offered at the University of North Texas continuously since 1993. The classes are project based, and feature collaborative coursework with art majors in UNT's School of Visual Arts. We discuss the design that enables them to simultaneously provide both training for students intending employment in the game industry, and a capstone experience for general computer science undergraduates.
Ubiquitous presenter
Authors: Wilkerson Michelle , Griswold William G. , Simon Beth
Published: November 2005

The University of Washington's Classroom Presenter lecturing system enables an active lecturing environment by combining a standard electronic slide presentation format with the capability for extemporaneous ink annotations by instructors and students using Tablet PCs. Thus, it can promote more interactive, student-centered learning. While many students may own laptops, few are yet Tablet devices. Also, Presenter uses multicast networking, which has availability and reliability issues. Ubiquitous Presenter (UP) expands Presenter via common web technologies to support non-Tablet audiences and enhance student control. UP enables students, using internet web browsers, to (a) synchronously or asynchronously view the slides and ink that are broadcast by the instructor, as well as (b) provide contextual submissions via text overlaid on the instructor's slides. The only compromises are that non-Tablet students cannot produce ink, and that professor ink is provided after a small time delay.
AlgorithmA project
Authors: Bernstein Marc , FitzGerald Kelly M. , Macdonell James P. , Concepcion Arturo I.
Published: November 2005

It is difficult to teach students proper software engineering methodology in a classroom setting. Without hands-on experience, students may not understand why the software engineering process exists. By teaching students via a mock company experience, teaching software engineering can become a rewarding experience while showing the students how simple it is to follow the correct process. Here we show how in the microcosm of a mock software company it is possible to teach very real lessons about software engineering, unfamiliar technologies, teamwork and the realization that when a project ends, the code does not disappear.
Teaching students to hack
Authors: Logan Patricia Y. , Clarkson Allen
Published: November 2005

Teaching "hacking" as a legitimate means of training students in how to protect a future employer's data assets has been introduced into courses with increasing frequency. The introduction of "red teaming" and attack-based exercises into information security courses presents a potential ethical problem. This paper explores the issues involved in designing an information security course with lab components that involve destructive actions.
Alternatives to two classic data structures
Authors: Okasaki Chris
Published: November 2005

Red-black trees and leftist heaps are classic data structures that are commonly taught in Data Structures (CS2) and/or Algorithms (CS7) courses. This paper describes alternatives to these two data structures that may offer pedagogical advantages for typical students.
RAPTOR
Authors: Carlisle Martin C. , Wilson Terry A. , Humphries Jeffrey W. , Hadfield Steven M.
Published: November 2005

When students are learning to develop algorithms, they very often spend more time dealing with issues of syntax rather than solving the problem. Additionally, the textual nature of most programming environments works against the learning style of the majority of students. RAPTOR is a visual programming environment, designed specifically to help students envision their algorithms and avoid syntactic baggage. RAPTOR programs are created visually and can be executed visually by tracing the execution through the program. Required syntax is kept to a minimum. Students preferred expressing their algorithms visually, and were more successful creating algorithms using RAPTOR than using a traditional language or writing flowcharts.
IRONCODE
Authors: Bailey Mark W.
Published: November 2005

To become proficient programmers, novices must develop the skills of writing, reading, debugging, and testing code. We believe that learning to write short pieces of code correctly the first time helps strengthen all of these skills. In this paper, we describe a type of exercise, called IRONCODE, that helps develop the code-once skill. We describe the exercise, the programming environment, its implementation, and our experiences using IRONCODE in a second semester programming class.
Results from the evaluation of the effectiveness of an online tutor on expression evaluation
Authors: Kumar Amruth N.
Published: November 2005

Researchers have been developing online tutors for various disciplines, including Computer Science. Educators are increasingly using online tutors to supplement their courses. Are online tutors effective? Can they help students learn? If so, what features contribute to their effectiveness? We will examine these questions in the context of an online tutor that we developed for introductory Computer Science. The tutor is designed to help students learn expression evaluation in C++/Java.We evaluated the tutor over several years, in multiple sections of Computer Science I each year. We used controlled tests with differential treatments, and used pre and post-tests to evaluate the effectiveness of the tutor. Our results show that online tutors indeed help students learn. Students who use the tutor for practice learn better than those who use a printed workbook. Students who receive both graphic visualization and text explanation learn better than those who receive only graphic visualization. Students who use graphic visualization learn better than those who receive no explanation. These results will be of interest to both developers and users of online tutors.
PL-detective
Authors: Diwan Amer , Jackson Michele H. , Waite William M. , Dickerson Jacob
Published: November 2005

Last year we described the PL-Detective, a system for building exercises and demonstrations in a programming languages course. One of the main goals of the PL-Detective was to provide an experimental environment with which students could interact in order to discover the information that they needed to complete the exercise. In this paper we evaluate the PL-Detective with respect to this goal. We present data from a class of 29 groups of two or three students that used the PL-Detective for 11 exercises. Our data shows that students are both effective and efficient at getting information from the PL-Detective.
On understanding the statics and dynamics of object-oriented programs
Authors: Ragonis Noa , Ben-Ari Mordechai
Published: November 2005

This paper describes research into the influence of using static (class and object) visualization on understanding program flow in object-oriented programming. We found that the advantages of using the static visualization in the first stages of learning could become disadvantages in the advanced stages. The teacher must be aware of these pitfalls and plan the learning sequence accordingly. We think that the BlueJ learning environment that we used should be augmented with dynamic visualization so that students can coordinate the static and dynamic aspects of object-oriented programs.
"The Babel experiment"
Authors: Pavlov Vladimir L. , Yatsenko Anton
Published: November 2005

In this paper we present the original method of intensive hands-on training in Object-oriented Analysis and Design (OOA/OOD) with the Unified Modeling Language (UML). The method has been successfully used by the authors for three years. During the training, the students:

go through the communication problems that are typical for large software development projects

obtain the successful experience of applying UML to overcome these problems.

The essence of the method is that a team of students is supposed to design a software system. They have several hours to complete the task. During this timeframe verbal and written communication is forbidden, and the UML is the only allowed language. This training is a kind of experiment for students -- they are to discover whether UML is "a real language" that is suitable and beneficial for a project team.The training was successfully delivered more than ten times in both academic and corporate environments and generated positive feedback from students and customers.
A Java framework for experimentation with steganography
Authors: Hunt Kenny
Published: November 2005

This article describes a Java framework for experimentation with fundamental steganographic techniques. The framework is built on top of Java's image processing libraries and provides extensible handles for customization and experimentation. The framework is designed and presented with a view towards incorporation into an undergraduate computer science curriculum.
Using image processing projects to teach CS1 topics
Authors: Wicentowski Richard , Newhall Tia
Published: November 2005

As Computer Science educators, we know that students learn more from projects that are fun and challenging, that seem "real" to them, and that allow them to be creative in designing their solutions. When we have students beating down our office doors wanting to show us what they've done, we know we have designed a project that truly meets its pedagogical goals. In CS1 courses, it is often difficult to come up with large, real-world programming projects that are at an appropriate level and that really excite students. This is particularly true in the first half of the course when students are learning basic programming and problem solving skills. We found that assignments based on image processing are an effective way to teach many CS1 topics. Because students enjoy working on the projects, they come away with a solid understanding of the topics reinforced by the projects. In this paper, we discuss many ways in which image processing could be used to teach CS1 topics. As an example, we present two image processing projects that we use in our CS1 course. These large, real-world programs are designed so that students can successfully master them early in their first semester of programming. Even though our CS1 course is taught using the C programming language, these projects could easily be used by a CS1 course in C, C++, or Java. We provide starting point code for Java and C versions of the projects, and provide sample assignment write-ups on our project webpage [12].
Teaching entering students to think like computer scientists
Authors: Turner Elise H. , Turner Roy M.
Published: November 2005

This paper describes a new course developed at University of Maine to help students better understand the discipline of computer science and to aid us in recruiting and retaining majors. The course verview of computer science, but also, through focusing on particular topics at an advanced level, begins to teach students how computer scientists think about problems. The course has been taught in Fall 2002, 2003 and 2004. This paper describes the course and discusses our results from the first two years.
Using peer review in teaching computing
Authors: Gehringer Edward F. , Chinn Donald D. , Pérez-Quiñones Manuel A. , Ardis Mark A.
Published: November 2005

For generations, the academic community has relied on peer review as a way of encouraging scholarship and enhancing the knowledge base. Peer review has been widely used in the classroom since at least the 1970s, with hundreds of papers on its use in diverse academic fields appearing in the literature (for a comprehensive survey, see [1]). Its use appears to be on the upswing, given the current interest in active learning and teamwork. In computer science, peer review seems to have very broad application. It can be used to evaluate the contributions of various members to a project team; it can be used for design documents and code reviews, in writing assignments, and in capstone project courses. The experience of the panelists is illustrative of the wide range of peer-review practices. This panel will serve to introduce the audience to some of these applications. Since many computer-science instructors have experimented with peer review, we are anxious to have them share their experiences during the open discussion period.
Effective incorporation of ethics into courses that focus on programming
Authors: Califf Mary Elaine , Goodwin Mary
Published: November 2005

This paper discusses some of the issues involved in incorporating ethics material into programming courses. Incorporating ethics into such courses raises particular challenges because of the time-intensive nature of the courses and because of the difficulty of finding material that is both relevant to the course and comprehensible to the students. The paper presents four case studies that we have used successfully when incorporating ethics material into our own programming courses.
Computer literacy
Authors: Hoffman Mark E. , Vance David R.
Published: November 2005

Do new college students already know much of what has previously been taught in our computer literacy courses (assuming a functional definition of knowledge according to which students are proficient with personal computer and Internet applications)? We conducted a survey of incoming first-year students at Quinnipiac University to learn not only their skill level with a representative range of technology tasks, but also from whom they learned these tasks. Results provide a profile of students who report learning many technology tasks primarily on their own. We propose a taxonomy according to which native technology tasks are learned with family support, social and educational technology task categories are supported by friends and teachers, respectively, and optional technology tasks are learned with little support. Our results will help in the design of appropriate computer literacy courses.
Design process for a non-majors computing course
Authors: Guzdial Mark , Forte Andrea
Published: November 2005

There is growing interest in computing courses for non-CS majors. We have recently built such a course that has met with positive response. We describe our design process, which includes involvement of stakeholders and identifying a context that facilitates learning. We present evaluation results on success rates (approximately 90% of the students earn an A, B, or C) and impact of the course on students over time (80% report that the class has influenced them more than a semester later).
Just-in-time teaching for CS0
Authors: Bailey Tammy , Forbes Jeffrey
Published: November 2005

Just-in-Time Teaching (JiTT) is a teaching and learning strategy based on the interaction between web-based study assignments and an active learner classroom. The essence of JiTT is the
feedback loop
formed by the students' preparation outside the classroom that shapes their in-class experience. The goal of JiTT is to use feedback to guide teaching and to empower and motivate learners. This paper describes a successful implementation of the JiTT strategy for an introductory computer science course.
Patterns of plagiarism
Authors: Daly Charlie , Horgan Jane
Published: November 2005

We used a new technique to analyse how students plagiarise programs in an introductory programming course. This involved placing a watermark on a student's program and monitoring programs for the watermark during assignment submission. We obtained and analysed extensive and objective data on student plagiarising behaviour. In contrast to the standard plagiarism detection approaches based on pair comparison, the watermark based approach allows us to distinguish between the supplier and the recipient of the code. This gives us additional insight into student behaviour. We found that the dishonest students did not perform significantly worse than the honest students in the exams. However, when dishonest students are further classified into supplier and recipient, it emerged that the recipient students performed significantly worse than the suppliers.
Factors influencing the shrinking pipeline in high schools
Authors: Eidelman Larisa , Hazzan Orit
Published: November 2005

The study described in this article continues research on gender-related issues in Computer Science education by focusing on the differences between two sectors in the Israeli high school system -- the Jewish sector (majority) and the Arab sector (minority). As it turns out, the under-representation of female high school students in CS studies is significantly more salient in the majority sector. This study explores this situation and attempts to explain it. We also explain how the findings of this research can be applied to other countries and societies.
The effects of individual differences on CS2 course performance across universities
Authors: Lewis Tracy L. , Chase J. D. , Pérez-Quiñones Manuel A. , Rosson Mary Beth
Published: November 2005

Research is presented that examined the effects of various measures of prior computer science experience and cognitive abilities on overall performance in a CS2 course. Participants selected from the CS2 course at two southeastern state universities were used within this study, resulting in a sample size of 161 (School A, n = 76; School B, n = 85). School A is a mid-sized comprehensive university and School B is a large research-intensive university.Self-reported data were collected on measures of experience in object-oriented processing, UNIX programming, web design, computing platforms, and various CS experience. Further, cognitive abilities measures of spatial orientation, visualization, logical reasoning, and flexibility were administered.The results show that the schools significantly differed on all measures of cognitive ability and most measures of prior computer science experience. The schools also differed on the extent to which these measures were related to overall course performance. The results suggest that, for school A, the cognitive ability visualization and the prior computer science experience measure of OO processing were significantly related to course performance. However, when examining school B, no measures were found significant.
Towards concrete concurrency
Authors: Jacobsen Christian L. , Jadud Matthew C.
Published: November 2005

In a world of ad-hoc networks, highly interconnected mobile devices and increasingly large supercomputer clusters, students need models of computation that help them think about dynamic and concurrent systems. Many of the tools currently available for introducing students to concurrency are difficult to use and are not intrinsically motivating. To provide an authentic, hands-on, and enjoyable introduction to concurrency, we have ported
occam π
, a language whose expressive powers are especially compelling for describing communicating dynamic reactive processes, to the LEGO Mindstorms.
Efficient use of robots in the undergraduate curriculum
Authors: Challinger Judith
Published: November 2005

In this paper we describe how a single Khepera II robot was used for an assignment in a senior level course on graphical user interface implementation. The assignment required each student to implement a graphical user interface for remotely controlling a Khepera II robot. From the author's point of view, the focus of the project was how to efficiently and effectively allow the 35 students enrolled in the course to have access to the robot for the purposes of testing and debugging. Furthermore, two of the students were enrolled through the distance education program and were remotely located. The intent was to see if an assignment making use of the robot would stimulate student interest, and whether it could be done with a minimal investment in hardware, lab, and instructor resources. The students were surveyed at the conclusion of the assignment in order to assess the effectiveness of the assignment. The results of this survey are presented, along with plans for future work.
A design for team peer code review
Authors: Trytten Deborah A.
Published: November 2005

The software industry needs our graduates to have significant and meaningful experiences with teamwork. A new design has been developed for a teamwork exercise based on peer code review. This design uses the three Ss of building assignments for cooperative learning: Same problem, Specific choices, and Simultaneous report. Students perform peer code review individually, and within and between stable small groups. The code can be sanitized student work or may be altered by the instructor to meet specific course learning objectives. The review is done in three phases. First, individuals answer yes or no to questions that evaluate the quality of the design and code. Then each group answers the same set of questions. When the groups have completed their evaluation, the class joins together to reveal and discuss the answers. This design was successfully implemented during the 2003-2004 academic year in an introductory programming class. This design is applicable to more advanced classes with significant programming assignments. Future work includes extending this structure to give students experience with other software engineering artifacts early in their academic careers.
Enhancing team knowledge
Authors: Smarkusky D. , Dempsey R. , Ludka J. , de Quillettes F.
Published: November 2005

Information technology projects are growing in complexity and require teams to solve problems and develop solutions. With current undergraduate, computer science and information systems curricula, students graduate with technical skills, but lack team project experiences. We have identified and developed team knowledge modules that are being taught to students in an effort to increase awareness of team process fundamentals and build the foundation of an effective team player. In this paper we present the challenges that we face with team projects and then discuss team knowledge modules that are being taught to incoming freshmen to engage students in a curriculum that requires team projects in each course. We conclude with our assessment results and show comparisons of student team knowledge by instruction and experience.
Affective assessment of team skills in agile CS1 labs
Authors: McKinney Dawn , Denton Leo F.
Published: November 2005

Team experiences can be important learning experiences, and industry highly values team skills in graduates. Low retention rates might also be improved with early team experiences because team experiences have been linked to increases in the sense of belonging, a key retention factor. Team experiences in upper-level courses could also benefit from earlier team experiences. The purpose of this paper is to describe and evaluate an early use of teams in the second semester of our CS1 sequence. The instructional methodology drew heavily upon the professional practices of an agile software development model, Extreme Programming. These professional practices fostered the development of team skills during a semester-long project in a closed lab. The evaluation of our experience revealed aspects of the good, the bad, and the ugly. Areas for improvement and future work are also explained.
Cooperative learning techniques in CS1
Authors: Beck Leland L. , Chizhik Alexander W. , McElroy Amy C.
Published: November 2005

A set of cooperative learning exercises were designed for use in a Java-based CS1 course. The exercises used specific roles to focus students' attention on key concepts of the Java language, and on key mental processes of programming and problem solving. A controlled experiment was conducted to evaluate the effectiveness of this approach. The results show that the cooperative learning experience had a significant positive effect on student performance, and may have been of special benefit to women and minority students.
Teaching design patterns in CS1
Authors: Wick Michael R.
Published: November 2005

Design patterns are an important element of today's undergraduate curricula. However, their inherent complexities often make them difficult for entry-level students to even partially grasp. In this paper, we describe the latest in our continuing efforts to build educational materials appropriate for infusing design patterns in entry-level computer science courses.
An address translation simulator
Authors: Robbins Steven
Published: November 2005

Virtual memory is a major topic in undergraduate operating systems courses. One aspect of virtual memory, address translation, is often covered in an abstract way. When examples are given, only a piece of the translation is done, using a small translation lookaside buffer or a small single-level page table. Since most students learn best by doing rather than watching, the topic is best understood by having students do realistic address translations. This is problematic since it involves lookup from several large tables of data which are difficult to fit on a piece of paper. The address translation simulator described here solves this problem by presenting the student with complete page tables in a way that allows simple navigation of these tables. The simulator can be used for both teaching and student evaluation.
Informatics
Authors: Kay David G. , van der Hoek André , Richardson Debra J.
Published: November 2005

Because the field of computer science has broadened so much in recent years, traditional degree programs are becoming crowded with new courses, each introducing its own "essential" topic. However, with more and more such courses, it is no longer possible to cover every topic in a single, coherent, four-year program. Many alternative approaches are available to address this situation. At UC Irvine, we have chosen a solution in which we offer four coordinated degree programs: a B.S. in Computer Science & Engineering, a conventional B.S. in Computer Science, a new B.S. in Informatics, and a broad overview B.S. in Information and Computer Science. Of these, the B.S. in Informatics is the most innovative, focusing on software and information design. Context plays a particularly strong role in our B.S. in Informatics: Placing software development in context is critical to the delivery of successful solutions, and we educate our students accordingly. We present our definition of informatics, detail our curriculum, describe its pedagogical characteristics and objectives, and conclude with some critical observations regarding informatics and its place in computer science education.
Software engineering education (SEEd)
Authors: Henderson Peter B.
Published: November 2005

Finally, I am a bit ahead of the deadline curve. As promised in my previous
SEE
d column, John Knight is our guest columnist. His contribution "Focusing Software Education on Engineering" appears below. This is based upon his excellent CSEE&T 2004 keynote talk with the same title and some insights from his October 2004 ComputerWeekly.com article available at http://www.computerweekly.com/Article 134277.htm.
Factors affecting effective software quality management revisited
Authors: Gill Nasib S.
Published: November 2005

Developing a good software system is a very complex task. In order to produce a good software product, several measures for software quality attributes need to be taken into account. System complexity measurement plays a vital role in controlling and managing software quality because it generally affects the software quality attributes like software reliability, software testability and software maintainability. Thus, software quality assurance (SQA) needs to be addressed keeping in view the new strategies, tool, methodologies and techniques applicable to software development life cycle.This paper is primarily aimed at revisiting and examining peculiar aspects of software development process that affect software quality management process. These aspects of software development process include software reliability measurement, ISO approach applicable to software quality and some aspects related to software testing improvement. Software testing and evaluation methods/tools/techniques do not guarantee effective testing and ensure high software quality. The way to improve the effectiveness of testing is to improve the attitude of software developers towards testing.In this paper, all these factors affecting software quality management have been discussed as well as all the possible improvements have been suggested. The results of this paper may be quite helpful to the researchers in quantifying the specific measuring tools for these software quality attributes.
Generic methodology for open source software development
Authors: Roberts Keith A.
Published: November 2005

This is the outline proposal for a CASE tool and associated methodology for Open Source software development.
Expert systems development
Authors: Sagheb-Tehrani Mehdi
Published: November 2005

A discussion is presented of why some Expert Systems (ES) that organizations have developed are not successful. The concept of design process plays a very significant role in the outset of the Expert Systems Development (ESD) process. This concept has not been the subject of much debate and attention in ESD. From the authors' point of view, one of the main issues is how the designer (knowledge Engineer) thinks about the design process. In general, the designers' process is influenced by the knowledge engineer's conception. This paper endeavors to disclose some of the main factors related to knowledge engineer's conception of design process and an attempt is made to put forward a conceptual model of the expert systems' design process. This conceptual model is an initial step towards a successful implementation of ES projects.
Review of "Types and Programming Languages by Benjamin C. Pierce"; The MIT Press, 2002
Authors: Kindahl Mats
Published: November 2005

Type systems and type checking are playing an increasingly important role in the development of programming languages. Almost every programming language developed today are developed with type systems as an integral part of the language.
A short introduction to failure detectors for asynchronous distributed systems
Authors: Reynal Michel
Published: November 2005

Since the first version of Chandra and Toueg's seminal paper titled "Unreliable failure detectors for reliable distributed systems" in 1991, the failure detector concept has been extensively studied and investigated. This is not at all surprising as failure detection is pervasive in the design, the analysis and the implementation of a lot of fault-tolerant distributed algorithms that constitute the core of distributed system middleware.The literature on this topic is mostly technical and appears mainly in theoretically inclined journals and conferences. The aim of this paper is to offer an introductory survey to the failure detector concept for readers who are not familiar with it and want to quickly understand its aim, its basic principles, its power and limitations. To attain this goal, the paper first describes the motivations that underlie the concept, and then surveys several distributed computing problems showing how they can be solved with the help of an appropriate failure detector. So, this short paper presents motivations, concepts, problems, definitions, and algorithms. It does not contain proofs. It is aimed at people who want to understand basics of failure detectors.
The finite and the infinite in temporal logic
Authors: Pucella Riccardo
Published: November 2005

At the last TACAS in Barcelona, already almost a year ago, Alur, Etessami, and Madhusudan [2004] introduced CaRet, a temporal logic framework for reasoning about programs with nested procedure calls and returns. The details of the logic were themselves interesting (I will return to them later), but a thought struck me during the presentation, whether an axiomatization might help understand the new temporal operators present in CaRet. Thinking a bit more about this question quickly led to further questions about the notion of finiteness and infinity in temporal logic as it is used in Computer Science. This examination of the properties of temporal logic operators under finite and infinite interpretations is the topic that I would like to discuss here. I will relate the discussion back to CaRet towards the end of the article, and derive a sound and complete axiomatization for an important fragment of the logic.
The impact of residential broadband traffic on Japanese ISP backbones
Authors: Fukuda Kensuke , Cho Kenjiro , Esaki Hiroshi
Published: November 2005

This paper investigates the effects of the rapidly-growing residential broadband traffic on commercial ISP backbone networks. We collected month-long aggregated traffic logs for different traffic groups from seven major ISPs in Japan in order to analyze the macro-level impact of residential broad-band traffic. These traffic groups are carefully selected to be summable, and not to count the same traffic multiple times.Our results show that (1) the aggregated residential broad-band customer traffic in our data exceeds 100Gbps on average. Our data is considered to cover 41% of the total customer traffic in Japan, thus we can estimate that the total residential broadband traffic in Japan is currently about 250Gbps in total. (2) About 70% of the residential broadband traffic is constant all the time. The rest of the traffic has a daily fluctuation pattern with the peak in the evening hours. The behavior of residential broadband traffic deviates considerably from academic or office traffic. (3) The total traffic volume of the residential users is much higher than that of office users, so backbone traffic is dominated by the behavior of the residential user traffic. (4) The traffic volume exchanged through domestic private peering is comparable with the volume exchanged through the major IXes. (5) Within external traffic of ISPs, international traffic is about 23% for inbound and about 17% for outbound. (6) The distribution of the regional broadband traffic is roughly proportional to the regional population.We expect other countries will experience similar traffic patterns as residential broadband access becomes widespread.
The state of the email address
Authors: Afergan Mike , Beverly Robert
Published: November 2005

Electronic mail is an unquestionably vital component of the Internet infrastructure. While the general perception of email is that it "just works," surprisingly little data is available to substantiate this claim. While SMTP is a mature technology of over twenty years, the architecture is increasingly strained by both normal and unsolicited load. In this paper we seek to provide a greater understanding of the behavior of Internet email as a system using active measurement.In order to survey a significant, diverse, and representative set of Internet SMTP servers, to which we have no administrative access, we develop a testing methodology that provides an email "traceroute" mechanism. Using this mechanism, we measure email loss, latency, and errors over the course of a month to popular, random, and Fortune 500 domains. Our initial results are
quite unexpected
and include
non-trivial loss rates, latencies longer than days, and significant and surprising errors.
While we present plausible explanations for some of these phenomena, there are several that we cannot, as of yet, explain. By better understanding Internet protocols which lack explicit end-to-end connection semantics, our eventual hope is to derive guidelines for designing future networks and more reliable email systems.
An analysis of TCP reset behaviour on the internet
Authors: Arlitt Martin , Williamson Carey
Published: November 2005

This paper presents a one-year study of Internet packet traffic from a large campus network, showing that 15-25% of TCP connections have at least one TCP RST (reset). Similar results have also been observed from measurements of other Internet links. The results in this paper show that reset connections arise from local events such as network outages, attacks, or reconfigurations, as well as from global trends in TCP usage. In particular, we identify application-level Web behaviour as the primary contributor to the global trend in reset TCP connections. The most prevalent anomaly is the absence of the normal connection termination handshake. Instead, connections are often reset by the client. We believe that particular implementations of HTTP/TCP connection management cause this global trend.
Analysis of long duration traces
Authors: Nelson Richard , Lawson Daniel , Lorier Perry
Published: November 2005

This paper introduces a new set of long duration captures of Internet traffic headers. The capture is being performed on a continuous on-going basis and is approaching a year in duration. Based on the current extent of the archive some typical analyses are presented, covering protocol mix, network trip times and TCP flag analysis.
An empirical study of "bogon" route advertisements
Authors: Feamster Nick , Jung Jaeyeon , Balakrishnan Hari
Published: November 2005

An important factor in the robustness of the interdomain routing system is whether the routers in autonomous systems (ASes) filter routes for "bogon" address space---i.e., private address space and address space that has not been allocated by the Internet Assigned Numbers Authority (IANA). This paper presents an empirical study of bogon route announcements, as observed at eight vantage points on the Internet. On average, we observe several bogon routes leaked every few days; a small number of ASes also temporarily leak hundreds of bogon routes. About 40% of these bogon routes are not withdrawn for at least a day. We observed 110 different ASes originating routes for bogon prefixes and a few ASes that were responsible for advertising a disproportionate number of these routes. We also find that some ASes that do filter unallocated prefixes continue to filter them for as long as five months after they have been allocated, mistakenly filtering valid routes. Both of these types of delinquencies have serious implications: the failure to filter valid prefixes can could make nefarious activities such as denial of service attacks difficult to trace; failure to update filters when new prefixes are allocated prevents legitimate routes from being globally visible.
IPv4 address allocation and the BGP routing table evolution
Authors: Meng Xiaoqiao , Xu Zhiguo , Zhang Beichuan , Huston Geoff , Lu Songwu , Zhang Lixia
Published: November 2005

The IP address consumption and the global routing table size are two of the vital parameters of the Internet growth. In this paper we quantitatively characterize the IPv4 address allocations made over the past six years and the global BGP routing table size changes during the same period of time. About 63,000 address blocks have been allocated since the beginning of the Internet, of which about 18,000 address blocks were allocated during our study period, from November 1997 to August 2004. Among these 18,000 allocations, 90% of them started being announced into the BGP routing table within 75 days after the allocation, while 8% of them has not been used up to now. Among all the address blocks that have ever been used, 45% of them were split into fragments smaller than the original allocated blocks; without these fragementations, the current BGP table would have been about half of its current size. Furthermore, we found that the evolution of BGP routing table consists of both the appearance of new prefixes and the disappearance of old prefixes. While the change of the BGP routing table size only reflects the combined results of the two processes, the dynamics of either process is much higher than that of the BGP table size. Finally, we classify routing prefixes into
covering
and
covered
ones, and examine their evolution separately. For the covered prefixes, which account for almost half of the BGP table size, we infer their practical motives such as multihoming, load balancing, and traffic engineering, etc., via a classification method.
Comparison of two approaches to dynamic programming
Authors: van den Broek Pim , Noppen Joost
Published: November 2005

Both in mathematics and in computer science Dynamic Programming is a well known concept. It is an algorithmic technique, which can be used to write efficient algorithms, based on the avoidance of multiple executions of identical subcomputations. Its definition in both disciplines is however quite different. The aim of this paper is to compare both definitions. It is shown that the computer science approach is more efficient, since it avoids the execution of unneeded subcomputations, whereas the mathematical approach has greater possibilities of reducing memory requirements.
Addendum to Etude on theme of Dijkstra
Authors: Shilova S. O. , Shilov N. V.
Published: November 2005

After publication of our paper
Etude on theme of Dijkstra
in September issue of v.35 of SIGACT News [1], we had a very interesting communication with Dr. John Hershberger related to the topic of the paper.
Etude
was not a research paper, but presented a tutorial for undergraduate students who are engaged with programming contests (like ACM ICPC). The tutorial was a part of a special undergraduate course at Novosibirsk State University (Russia) and was based on E. Dijkstra's heuristic search solution of non-crossing matching problem on the plane.
Review of "Linear Optimization and Extensions -- Problems and Solutions by Dimitris Alevas and Manfred Padberg", Springer-Verlag, 450 pages, $54.95
Authors: Oliveira Carlos A. S.
Published: November 2005

Linear Optimization and Extensions -- Problems and Solutions
- is a solution manual for another book, released in 2000, by the second author [1]. The original book is a comprehensive introduction to the topics of linear programming and combinatorial optimization. The current book, therefore, has the initial goal of providing hints, and solutions for the problems there stated.
Review of "Introduction to the Design and Analysis of Algorithms by Ananay Levitin", Addison-Wesley
Authors: Fahle William
Published: November 2005

This is a beginning algorithms book, suitable for the late undergraduate or early graduate computer science student. Subjects covered include an introduction of the concept of algorithms, a taxonomy of various algorithms and design techniques, up through a preliminary discussion of the topics of complexity and computability. The subject of algorithms is, of course, well known and fundamental to the computer sciences. This book provides an introduction to the subject through the use of some well-known and not so well-known puzzles and computing problems.
Specifying confidentiality
Authors: Pucella Riccardo
Published: November 2005

I would like to start my tenure as editor of the Logic Column by thanking Jon Riecke, who has edited this column since 1998. The Logic Column serves as a showcase of the many connections between logic and computer science. Logic has been connected with computer science since the early days of Turing. In the past few decades, logical methods have had a considerable impact. To get a sense of the range of applications, consider the 2001 NSF/CISE Workshop on The Unusual Effectiveness of Logic in Computer Science (see http: //www. cs. rice. edu/~vardi/logic/). An article derived from the workshop appeared in theBulletin of Symbolic Logic[Halpern et al. 2001], and it is an exceedingly good read. If you get a copy of that issue of the Bulletin, make sure to also have a look at the article by Buss et al. [2001], which discusses the current state of mathematical logic.
Two attacks on a user friendly remote authentication scheme with smart cards
Authors: Hwang Kuo-Feng , Liao I-En
Published: November 2005

Recently, Wu and Chieu proposed a user-friendly remote authentication scheme with smart card. In their scheme, the users can choose and change their passwords freely. However, their scheme is insecure. In this paper, we propose two attacks on their scheme.