bluuebunny/crossref_metadata_2025 huggingface dataset:
Semidefinite programming based algorithms for sensor network localization
Authors: Biswas Pratik , Lian Tzu-Chen , Wang Ta-Chung , Ye Yinyu
Published: October 2006

An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite program that can be solved efficiently.The basic model is extended in order to account for noisy distance information. In particular, a maximum likelihood based formulation and an interval based formulation are discussed. The SDP solution can then also be used as a starting point for steepest descent based local optimization techniques that can further refine the SDP solution.We also describe the extension of the basic method to develop an iterative distributed SDP method for solving very large scale semidefinite programs that arise out of localization problems for large dense networks and are intractable using centralized methods.The performance evaluation of the technique with regard to estimation accuracy and computation time is also presented by the means of extensive simulations.Our SDP scheme also seems to be applicable to solving other Euclidean geometry problems where points are locally connected.
Spin MOSFETs as a basis for spintronics
Authors: Sugahara Satoshi , Tanaka Masaaki
Published: October 2006

This article reviews a recently proposed new class of spin transistors referred to as spin metal-oxide-semiconductor field-effect transistors (spin MOSFETs), and their integrated circuit applications. The fundamental device structures, operating principle, and theoretically predicted device performance are presented. Spin MOSFETs potentially exhibit significant magnetotransport effects, such as large magneto-current, and also satisfy important requirements for integrated circuit applications such as high transconductance, low power-delay product, and low off-current. Since spin MOSFETs can perform signal processing and logic operations and can store digital data using both charge transport and spin degrees of freedom, they are expected to be building blocks for memory cells and logic gates in spin-electronic integrated circuits. Novel spin-electronic integrated circuit architectures for nonvolatile memory and reconfigurable logic employing spin MOSFETs are also presented.
A thread monitoring system for multithreaded Java programs
Authors: Moon Sewon , Chang Byeong-Mo
Published: October 2006

To assist developing robust multithreaded software, we develop a thread monitoring system for multithreaded Java programs, which can trace or monitor running threads and synchronization. We design a monitoring system which has options to select interesting threads and synchronized actions. Using this tool, programmers can monitor only interesting threads and synchronization in more details by selecting options, and can detect a deadlock. It also provides profile information after execution, which summarizes behavior of running threads and synchronized actions during execution. We implement the system based on code inlining, and presents some experimental results.
The BlackWidow High-Radix Clos Network
Authors: Scott Steve , Abts Dennis , Kim John , Dally William J.
Published: October 2006

This paper describes the radix-64 folded-Clos network of the Cray BlackWidow scalable vector multiprocessor. We describe the BlackWidow network which scales to 32K processors with a worstcase diameter of seven hops, and the underlying high-radix router microarchitecture and its implementation. By using a high-radix router with many narrow channels we are able to take advantage of the higher pin density and faster signaling rates available in modern ASIC technology. The BlackWidow router is an 800 MHz ASIC with 64 18.75Gb/s bidirectional ports for an aggregate offchip bandwidth of 2.4Tb/s. Each port consists of three 6.25Gb/s differential signals in each direction. The router supports deterministic and adaptive packet routing with separate buffering for request and reply virtual channels. The router is organized hierarchically [13] as an 8×8 array of tiles which simplifies arbitration by avoiding long wires in the arbiters. Each tile of the array contains a router port, its associated buffering, and an 8×8 router subswitch. The router ASIC is implemented in a 90nm CMOS standard cell ASIC technology and went from concept to tapeout in 17 months.
Slackened Memory Dependence Enforcement
Authors: Garg Alok , Rashid M. Wasiur , Huang Michael
Published: October 2006

An efficient mechanism to track and enforce memory dependences is crucial to an out-of-order microprocessor. The conventional approach of using cross-checked load queue and store queue, while very effective in earlier processor incarnations, suffers from scalability problems in modern high-frequency designs that rely on buffering many in-flight instructions to exploit instruction-level parallelism. In this paper, we make a case for a very different approach to dynamic memory disambiguation. We move away from the conventional exact disambiguation strategy and adopt an opportunistic method: we allow loads and stores to access an L0 cache as they are issued out of program order, hoping that with such a laissez-faire approach, most loads actually obtain the right value. To guarantee correctness, they execute a second time in program order to access the nonspeculative L1 cache. A discrepancy between the two executions triggers a replay. Such a design completely eliminates the necessity of real-time violation detection and thus avoids the conventional approach's complexity and the associated scalability issue. We show that even a simplistic design can provide similar performance level achieved with a conventional queue-based approach with optimisticallysized queues. When simple, optional optimizations are applied, the performance level is close to that achieved with ideally-sized queues.
A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching
Authors: Brodie Benjamin C. , Taylor David E. , Cytron Ron K.
Published: October 2006

We present and evaluate an architecture for highthroughput pattern matching of regular expressions. Our approach matches multiple patterns concurrently, responds rapidly to changes in the pattern set, and is well suited for synthesis in an ASIC or FPGA. Our approach is based on a new and easily pipelined state-machine representation that uses encoding and compression techniques to improve density. We have written a compiler that translates a set of regular expressions and optimizes their deployment in the structures used by our architecture. We analyze our approach in terms of its throughput, density, and efficiency. We present experimental results from an implementation in a commodity FPGA, showing better throughput and density than the best known approaches.
Interconnect-Aware Coherence Protocols for Chip Multiprocessors
Authors: Cheng Liqun , Muralimanohar Naveen , Ramani Karthik , Balasubramonian Rajeev , Carter John B.
Published: October 2006

Improvements in semiconductor technology have made it possible to include multiple processor cores on a single die. Chip Multi-Processors (CMP) are an attractive choice for future billion transistor architectures due to their low design complexity, high clock frequency, and high throughput. In a typical CMP architecture, the L2 cache is shared by multiple cores and data coherence is maintained among private L1s. Coherence operations entail frequent communication over global on-chip wires. In future technologies, communication between different L1s will have a significant impact on overall processor performance and power consumption. On-chip wires can be designed to have different latency, bandwidth, and energy properties. Likewise, coherence protocol messages have different latency and bandwidth needs. We propose an interconnect composed of wires with varying latency, bandwidth, and energy characteristics, and advocate intelligently mapping coherence operations to the appropriate wires. In this paper, we present a comprehensive list of techniques that allow coherence protocols to exploit a heterogeneous interconnect and evaluate a subset of these techniques to show their performance and power-efficiency potential. Most of the proposed techniques can be implemented with a minimum complexity overhead.
Algorithmic construction of sets for
k
-restrictions
Authors: Alon Noga , Moshkovitz Dana , Safra Shmuel
Published: October 2006

This work addresses
k-restriction problems
, which unify combinatorial problems of the following type: The goal is to construct a short list of strings in Σ

m

that satisfies a given set of
k
-wise demands. For every
k
positions and every demand, there must be at least one string in the list that satisfies the demand at these positions. Problems of this form frequently arise in different fields in Computer Science.The standard approach for deterministically solving such problems is via almost
k
-wise independence or
k
-wise approximations for other distributions. We offer a generic algorithmic method that yields considerably smaller constructions. To this end, we generalize a previous work of Naor et al. [1995]. Among other results, we enhance the combinatorial objects in the heart of their method, called splitters, and construct
multi-way splitters
, using a new discrete version of the topological
Necklace Splitting Theorem
[Alon 1987].We utilize our methods to show improved constructions for
group testing
[Ngo and Du 2000] and
generalized hashing
[Alon et al. 2003], and an improved inapproximability result for SET-COVER under the assumption
P
≠
NP
.
Asian trio's adoption of Linux-based open source development
Authors: Chae Bongsug (Kevin) , McHaney Roger
Published: October 2006

Three Asian economic heavyweights---China, Japan, and South Korea---join IT forces.
Externally verifiable code execution
Authors: Seshadri Arvind , Luk Mark , Perrig Adrian , Doorn Leendert van , Khosla Pradeep
Published: October 2006

Using hardware- and software-based techniques to realize a primitive for externally verifiable code execution.
A wide-area Distribution Network for free software
Authors: Bakker Arno , Steen Maarten Van , Tanenbaum Andrew S.
Published: October 2006

The Globe Distribution Network (GDN) is an application for the efficient, worldwide distribution of freely redistributable software packages. Distribution is made efficient by encapsulating the software into special distributed objects which efficiently replicate themselves near to the downloading clients. The Globe Distribution Network takes a novel, optimistic approach to stop the illegal distribution of copyrighted and illicit material via the network. Instead of having moderators check the packages at upload time, illegal content is removed and its uploader's access to the network permanently revoked only when the violation is discovered. Other protective measures defend the GDN against internal and external attacks to its availability. By exploiting the replication of the software and using fault-tolerant server software, the Globe Distribution Network achieves high availability. A prototype implementation of the GDN is available from http://www.cs.vu.nl/globe/.
Small-scale peer-to-peer overlays
Authors: Gordon Minor
Published: October 2006

Scalability and efficient global search in large-scale peer-to-peer overlays often come at the expense of small-scale, local interactions between peers. For many users, local operations such as browsing, messaging, and direct content exchange between nodes may be more useful than access to the network as a whole. In this note we sketch the design of a small-scale overlay for applications such as ticketing systems, editorial coordination, and ad hoc workflows that currently rely on more general and less efficient mediums such as e-mail. Peers in the overlay form local economies and attempt to maximize user-directed utility functions.
Systematic topology analysis and generation using degree correlations
Authors: Mahadevan Priya , Krioukov Dmitri , Fall Kevin , Vahdat Amin
Published: October 2006

Researchers have proposed a variety of metrics to measure important graph properties, for instance, in social, biological, and computer networks. Values for a particular graph metric may capture a graph's resilience to failure or its routing efficiency. Knowledge of appropriate metric values may influence the engineering of future topologies, repair strategies in the face of failure, and understanding of fundamental properties of existing networks. Unfortunately, there are typically no algorithms to generate graphs matching one or more proposed metrics and there is little understanding of the relationships among individual metrics or their applicability to different settings. We present a new, systematic approach for analyzing network topologies. We first introduce the
d
K-series of probability distributions specifying all degree correlations within
d
-sized subgraphs of a given graph
G
. Increasing values of
d
capture progressively more properties of
G
at the cost of more complex representation of the probability distribution. Using this series, we can quantitatively measure the distance between two graphs and construct random graphs that accurately reproduce virtually all metrics proposed in the literature. The nature of the
d
K-series implies that it will also capture any future metrics that may be proposed. Using our approach, we construct graphs for
d
=0, 1, 2, 3 and demonstrate that these graphs reproduce, with increasing accuracy, important properties of measured and modeled Internet topologies. We find that the
d
=2 case is sufficient for most practical purposes, while
d
=3 essentially reconstructs the Internet AS-and router-level topologies exactly. We hope that a
systematic
method to analyze and synthesize topologies offers a significant improvement to the set of tools available to network topology and protocol researchers.
Minimizing churn in distributed systems
Authors: Godfrey P. Brighten , Shenker Scott , Stoica Ion
Published: October 2006

A pervasive requirement of distributed systems is to deal with churn-change in the set of participating nodes due to joins, graceful leaves, and failures. A high churn rate can increase costs or decrease service quality. This paper studies how to reduce churn by selecting which subset of a set of available nodes to use.First, we provide a comparison of the performance of a range of different node selection strategies in five real-world traces. Among our findings is that the simple strategy of picking a uniform-random replacement whenever a node fails performs surprisingly well. We explain its performance through analysis in a stochastic model.Second, we show that a class of strategies, which we call "Preference List" strategies, arise commonly as a result of optimizing for a metric other than churn, and produce high churn relative to more randomized strategies under realistic node failure patterns. Using this insight, we demonstrate and explain differences in performance for designs that incorporate varying degrees of randomization. We give examples from a variety of protocols, including anycast, over-lay multicast, and distributed hash tables. In many cases, simply adding some randomization can go a long way towards reducing churn.
SybilGuard
Authors: Yu Haifeng , Kaminsky Michael , Gibbons Phillip B. , Flaxman Abraham
Published: October 2006

Peer-to-peer and other decentralized,distributed systems are known to be particularly vulnerable to
sybil attacks
. In a sybil attack,a malicious user obtains multiple fake identities and pretends to be multiple, distinct nodes in the system. By controlling a large fraction of the nodes in the system,the malicious user is able to "out vote" the honest users in collaborative tasks such as Byzantine failure defenses. This paper presents
SybilGuard
, a novel protocol for limiting the corruptive influences of sybil attacks.Our protocol is based on the "social network "among user identities, where an edge between two identities indicates a human-established trust relationship. Malicious users can create many identities but few trust relationships. Thus, there is a disproportionately-small "cut" in the graph between the sybil nodes and the honest nodes. SybilGuard exploits this property to bound the number of identities a malicious user can create.We show the effectiveness of SybilGuard both analytically and experimentally.
Algorithms to accelerate multiple regular expressions matching for deep packet inspection
Authors: Kumar Sailesh , Dharmapurikar Sarang , Yu Fang , Crowley Patrick , Turner Jonathan
Published: October 2006

There is a growing demand for network devices capable of examining the content of data packets in order to improve network security and provide application-specific services. Most high performance systems that perform deep packet inspection implement simple string matching algorithms to match packets against a large, but finite set of strings. owever, there is growing interest in the use of regular expression-based pattern matching, since regular expressions offer superior expressive power and flexibility. Deterministic finite automata (DFA) representations are typically used to implement regular expressions. However, DFA representations of regular expression sets arising in network applications require large amounts of memory, limiting their practical application.In this paper, we introduce a new representation for regular expressions, called the
Delayed Input
DFA (D
2
FA), which substantially reduces space equirements as compared to a DFA. A D
2
FA is constructed by transforming a DFA via incrementally replacing several transitions of the automaton with a single default transition. Our approach dramatically reduces the number of distinct transitions between states. For a collection of regular expressions drawn from current commercial and academic systems, a D2FA representation reduces transitions by more than 95%. Given the substantially reduced space equirements, we describe an efficient architecture that can perform deep packet inspection at multi-gigabit rates. Our architecture uses multiple on-chip memories in such a way that each remains uniformly occupied and accessed over a short duration, thus effectively distributing the load and enabling high throughput. Our architecture can provide ostffective packet content scanning at OC-192 rates with memory requirements that are consistent with current ASIC technology.
DisASTer (distributed algorithms simulation terrain)
Authors: Oechsle Rainer , Gottwald Tim
Published: October 2006

DisASTer (Distributed Algorithms Simulation Terrain) is a platform for the implementation of distributed algorithms. It provides a Java class library that eases the programming of distributed algorithms in Java. Moreover, DisASTer constitutes an execution environment that enables the user to specify interactively a topology at runtime. It allows the user to control the execution of the algorithm (start, stop, suspend, resume, go back and forth). In addition, the execution of a distributed algorithm can be observed through some built-in visualization panels (topology view, sequence view, message queue view). DisASTer supports the implementation of further application-specific views.
Novice Java programmers' conceptions of "object" and "class", and variation theory
Authors: Eckerdal Anna , Thuné Michael
Published: October 2006

Problems with understanding concepts, so called misconceptions, have been investigated and reported in a number of studies regarding object-oriented programming [4], [3]. In a first programming course using an object-oriented language, it is of great importance that students get a good understanding of central concepts like
object
and
class
at an early stage of their education. We have, with a phenomenographic research approach, performed a study with first year university students, investigating what an understanding of the concepts
object
and
class
includes from a student perspective. By applying variation theory [8] to our results we are able to pin-point what the students need to be able to discern in order to gain a "rich" understanding of these concepts.
Do computer science students know what they know?
Authors: Murphy Laurie , Tenenberg Josh
Published: October 2006

This paper describes an empirical study that investigates the knowledge that Computer Science students have about the extent of their own previous learning. The study compares self-generated estimates of performance with actual performance on a data structures quiz taken by undergraduate students in courses requiring data structures as a pre-requisite. The study is contextualized and grounded within a research paradigm in Psychology called
calibration of knowledge
that suggests that self-knowledge across a range of disciplines is highly unreliable. Such self-knowledge is important because of its role in
meta-cognition
, particularly in cognitive self-regulation and monitoring. It is also important because of the credence that faculty give to student self-reports. Our results indicate that Computer Science student self-estimates correlate moderately with their performance on a quiz, more so for estimates provided after they have taken the quiz than before. The pedagogical implications are that students should be provided with regular opportunities for empirical validation of their knowledge as well as being taught the metacognitive skills of regular self-testing in order to overcome validation bias.
A programming languages course for freshmen
Authors: Velázquez-Iturbide J. Ángel
Published: October 2006

Programming languages are a part of the core of computer science. Courses on programming languages are typically offered to junior or senior students, and textbooks are based on this assumption. However, our computer science curriculum offers the programming languages course in the first year. This unusual situation led us to design it from an untypical approach. In this paper, we first analyze and classify proposals for the programming languages course into different pure and hybrid approaches. Then, we describe a course for freshmen based on four pure approaches, and justify the main choices made. Finally, we identify the software used for laboratories and outline our experience after teaching it for seven years.
Student performance in CS1 with distributed pair programming
Authors: Hanks Brian
Published: October 2006

Pair programming has been shown to provide many pedagogical benefits, particularly for students who are learning to program. One drawback with pair programming is its collocation requirement, which makes it difficult for some students to enjoy these benefits. We report on an experiment with a tool that allows students to pair program from separate locations. Our results indicate that students who experience the increased flexibility of distributed pairing perform as well in their introductory programming course as students who have to physically meet in order to pair. These students are also as confident as the collocated students. We also confirm earlier results reported by others that pair programming results in greater student confidence and increased student performance.
Moving from mailing lists to web-based discussion forums
Authors: Dias Artur Miguel
Published: October 2006

We report on some of our experience in using the WEB to promote the communication between students and teachers, focusing on the ongoing migration from mailing lists to Web-based discussion forums in our Department.
Use a little history
Authors: Impagliazzo John
Published: October 2006

This poster describes a work in progress regarding the use of history in computing courses. Its focus revolves around the Computing History Resources and Adaptation (CHRAD) project, partially funded by the National Science Foundation. Elements of the presentation include how history can make computing courses interesting and how it can stimulate greater appreciation between technological and social issues.
A personalized visualization tool for geo-referenced information
Authors: Freitas Sérgio , Carmo Maria Beatriz , Afonso Ana Paula
Published: October 2006

We are developing a prototype for the visualization of geo-referenced information. The data is organized in several topics. The user interactively selects the geographical region and the topics he/she is interest on. The main features of this prototype are: filtering mechanisms to control the amount of data displayed; representations with different levels of detail selected according to the scale of representation. In order to include semantic criteria to reduce the amount of data to display, we use a degree of interest function.
Internet nuggets
Authors: Thorson Mark
Published: October 2006

This column consists of selected traffic from the
comp.arch
newsgroup, a forum for discussion of computer architecture on the Internet---an international computer network.As always, the opinions expressed in this column are the personal views of the authors, and do not necessarily represent the institutions to which they are affiliated.Text which sets the context of a message appears underlined or in italics; this is usually text the author has quoted from earlier messages. The code-like expressions below the authors' names are their addresses on Internet.
Minimizing downtime in seamless migrations of mobile applications
Authors: Zhang Kun , Pande Santosh
Published: October 2006

Application migration is a key enabling technology component of mobile computing that allows rich semantics involving location awareness, trust and timeliness of information processing by moving the application where the data is. Seamlessness is one of the key properties of mobile computing and downtime must be eliminated/minimized during the migration to achieve seamlessness. But migration involves large overheads, dominant of which are the overheads due to serialization and de-serialization [1]. To achieve seamless migration, an application state could be pre-serialized during the program's execution, and upon migration, the serialized data could be transmitted and de-serialized to get the execution started. Previous approach to this problem [1] removed dead state but still suffered from large migration overheads due to serialization on-demand that could lead to an unacceptable downtime.In this work, we develop a static compiler analysis plus runtime assisted framework to decrease the migration overhead to almost zero while minimizing the degradation in the program's performance. We achieve such a goal by deciding which data to be pre-serialized through analysis, and pre-serializing the state in the program. A safe state is kept that would allow immediate migration upon the arrival of an interrupt while minimizing frequent pre-serialization. When the migration interrupt comes in, the serialized data can be transmitted directly to the destination machine. This allows an application to resume its execution at the destination machine with almost no interruption (only a small amount of non-serialized data needs to be serialized during migration). The optimization serializes the data in such a way that a maximal number of functions can execute without interruption after migration. Our experiments with multimedia applications show that the migration latency is significantly reduced leading to a small downtime. Thus, the contribution of the paper is to provide an efficient methodology to perform seamless migration while limiting the overhead.
Effective thread management on network processors with compiler analysis
Authors: Zhuang Xiaotong , Pande Santosh
Published: October 2006

Mapping packet processing tasks on network processor micro-engines involves complex tradeoffs that relating to maximizing parallelism and pipelining. Due to an increase in the size of the code store and complexity of the application requirements, network processors are being programmed with heterogeneous threads that may execute code belonging to different tasks on a given micro-engine. Also, most network applications are streaming applications that are typically processed in a pipelined fashion. Thus, the tasks on different micro-engines are pipelined in such a way as to maximize the throughput. Tasks themselves could have different run time performance demands. Traditionally, runtime management involving processor sharing, real-time scheduling etc. is provided by the runtime environment (typically an operating system) using the hardware support for timers and interrupts that allows time slicing the resource amongst the tasks. However, due to stringent performance requirements on network processors (which process packets from very high speed network traffic), neither OS nor hardware mechanisms are typically feasible/available.In this paper, we show that it is very difficult and inefficient for the programmer to meet the constraints of runtime management by coding them statically. Due to the infeasibility of hardware or OS solution (even in the near future), the only choice left is a compiler approach.We propose a complete compiler solution to automatically insert explicit context switch (ctx) instructions provided on the processors so that the execution of programs is better manipulated at runtime to meet their constraints. We show that such an approach is feasible opening new application domains that would need heterogeneous thread programming. Such approaches would in general become important for multi-core processors.
Compiler-directed thermal management for VLIW functional units
Authors: Mutyam Madhu , Li Feihui , Narayanan Vijaykrishnan , Kandemir Mahmut , Irwin Mary Jane
Published: October 2006

As processors, memories, and other components of today's embedded systems are pushed to higher performance in more enclosed spaces, processor thermal management is quickly becoming a limiting design factor. While previous proposals mostly approached this thermal management problem from circuit and architecture angles, software can also play an important role in identifying and eliminating
thermal hotspots
as it is the main factor that shapes the order and frequency of accesses to different hardware components in the chip. This is particularly true for compiler-scheduled Very Long Instruction Word (VLIW) datapath.In this paper, we focus on a compiler-based approach to make the thermal profile more balanced in the integer functional units of VLIW architectures. For balanced thermal behavior and peak temperature minimization, we propose techniques based on load balancing across the integer functional units with or without rotation of functional unit usage. As leakage power is exponentially dependent on temperature and temperature is dependent on total power (i.e., switching and leakage), in our techniques, we also consider leakage power optimization by IPC tuning (instructions issued per cycle). By taking a code that is already scheduled for maximum performance as input, our scheduling strategies modify this performance-oriented schedule for balanced thermal behavior with negligible performance degradation. We simulate our scheduling strategies using a framework that consists of the
Trimaran
infrastructure, a power model, and the
HotSpot
. Our experimental results using several benchmark programs reveal that the peak temperature can be reduced through compiler scheduling.
The development of Chez Scheme
Authors: Dybvig R. Kent
Published: October 2006

Chez Scheme is now over 20 years old, the first version having been released in 1985. This paper takes a brief look back on the history of Chez Scheme's development to explore how and why it became the system it is today.
Simple unification-based type inference for GADTs
Authors: Peyton Jones Simon , Vytiniotis Dimitrios , Weirich Stephanie , Washburn Geoffrey
Published: October 2006

Generalized algebraic data types (GADTs), sometimes known as "guarded recursive data types" or "first-class phantom types", are a simple but powerful generalization of the data types of Haskell and ML. Recent works have given compelling examples of the utility of GADTs, although type inference is known to be difficult. Our contribution is to show how to exploit programmer-supplied type annotations to make the type inference task almost embarrassingly easy. Our main technical innovation is
wobbly types
, which express in a declarative way the uncertainty caused by the incremental nature of typical type-inference algorithms.
Modelling deterministic concurrent I/O
Authors: Dowse Malcolm , Butterfield Andrew
Published: October 2006

The problem of expressing I/O and side effects in functional languages is a well-established one. This paper addresses this problem from a general semantic viewpoint by giving a unified framework for describing shared state, I/O and deterministic concurrency. We develop a modified state transformer which lets us mathematically model the API, then investigate and machine verify some broad conditions under which confluence holds. This semantics is used as the basis for a small deterministic Haskell language extension called CURIO, which enforces determinism using runtime checks.Our confluence condition is first shown to hold for a variety of small components, such as individual shared variables, 1-to-1 communication channels, and I-structures. We then show how models of substantial APIs (like a modification of Haskell's file I/O API which permits inter-process communication) may be constructed from these smaller components using "combinators" in such a way that determinism is always preserved. We describe combinators for product, name-indexing and dynamic allocation, the last of which requires some small extensions to cater for process locality.
Playing by the Rules
Authors: O'Hanlon Charlene
Published: October 2006

Some of my favorite childhood memories are of playing games with my sister—both structured games such as Monopoly or hopscotch and imagination-fueled games such as cops and robbers or roller derby girls. Regardless of whether the game had established regulations, often our play would devolve into what I call Calvinball, a term coined in the comic strip Calvin and Hobbes referring to the act of making up the rules as you go along.
News 2.0
Authors: Stanik John
Published: October 2006

Open Source Gets Mac Attack
Social influence on technology acceptance behavior
Authors: Lee Younghwa , Lee Jintae , Lee Zoonky
Published: October 2006

Social influence on technology acceptance behavior has been acknowledged but needs to be further articulated. While Subjective Norm (SN) has been dominantly used to capture the essence of social influence, the findings to date has led some researchers to question whether it captures the full extent of social influence. Recently, social psychologists have examined Self-Identity as a construct reflecting social influence on behavior. In particular, Self-Identity has been shown to have significant influence on voluntary behavior and have enduring effects, situations where the Subjective Norm had little effect. This study examines the effect of Self-Identity on technology acceptance decision in the context of a web-based class support system under the Technology Acceptance Model (TAM). The result demonstrates a significant direct and indirect effect of Self-Identity on technology acceptance. The result also confirms that Self-Identity has significant direct effect on the acceptance in voluntary and experienced situations, while Subjective Norm has no significant effect in both situations. Key implications for theory and practice are discussed.
The boss online submission and assessment system
Authors: Joy Mike , Griffiths Nathan , Boyatt Russell
Published: October 2006

Computer programming lends itself to automated assessment. With appropriate software tools, program correctness can be measured, along with an indication of quality according to a set of metrics. Furthermore, the regularity of program code allows plagiarism detection to be an integral part of the tools that support assessment. In this paper, we describe a submission and assessment system, called BOSS, that supports coursework assessment through collecting submissions, performing automatic tests for correctness and quality, checking for plagiarism, and providing an interface for marking and delivering feedback. We describe how automated assessment is incorporated into BOSS such that it supports, rather than constrains, assessment. The pedagogic and administrative issues that are affected by the assessment process are also discussed.
Experiences on automatically assessed algorithm simulation exercises with different resubmission policies
Authors: Malmi Lauri , Karavirta Ville , Korhonen Ari , Nikander Jussi
Published: October 2006

In this paper, we present our experiences in using two automatic assessment tools, TRAKLA and TRAKLA2, in a second course of programming. In this course, 500--700 students have been enrolled annually during the period 1993--2004. The tools are specifically designed for assessing algorithm simulation exercises in which students simulate the working of algorithms at a conceptual level. Both of these tools allow students to resubmit their solutions after getting feedback. However, the resubmission policy has changed considerably during the period. Those changes reflect the students performance in the exercises. We conclude that an encouraging grading policy, i.e., the more exercises they solve the better grades they achive, combined with an option to resubmit the solution is a very important factor promoting students' learning. However, in order to prevent aimless trial-and-error problem solving method, the number of resubmissions allowed per assignment should be carefully controlled.
Principled design of logical fisheye views of functional expressions
Authors: Velázquez-Iturbide J. Ángel
Published: October 2006

We face the problem of simplifying automatically the visualization of expressions in an eager functional language. The problem is relevant for debugging in a programming environment, based on a rewriting model of expression evaluation that displays large intermediate expressions. The simplification technique must filter automatically the parts of an expression which are not interesting for debugging/understanding. We propose the use of logical fisheye views because they provide a balance between showing global context and local information (focus). A straightforward implementation of fisheye views displays too simplified expressions. In the article, we identify five design requirements and describe how they are satisfied. We also include several examples, a discussion and related work.
A preliminary performance comparison of five machine learning algorithms for practical IP traffic flow classification
Authors: Williams Nigel , Zander Sebastian , Armitage Grenville
Published: October 2006

The identification of network applications through observation of associated packet traffic flows is vital to the areas of network management and surveillance. Currently popular methods such as port number and payload-based identification exhibit a number of shortfalls. An alternative is to use machine learning (ML) techniques and identify network applications based on per-flow statistics, derived from payload-independent features such as packet length and inter-arrival time distributions. The performance impact of feature set reduction, using Consistency-based and Correlation-based feature selection, is demonstrated on Naïve Bayes, C4.5, Bayesian Network and Naïve Bayes Tree algorithms. We then show that it is useful to differentiate algorithms based on computational performance rather than classification accuracy alone, as although classification accuracy between the algorithms is similar, computational performance can differ significantly.
The probe gap model can underestimate the available bandwidth of multihop paths
Authors: Lao Li , Dovrolis Constantine , Sanadidi M. Y.
Published: October 2006

The Probe Gap Model (PGM) was proposed as a lightweight and fast available bandwidth estimation method. Measurement tools such as Delphi and Spruce are based on PGM. Compared to estimation methods that require multiple iterations with different probing rates, PGM uses a single probing rate and it infers the available bandwidth from a direct relation between the input and output rates of measurement packet pairs. An important assumption behind the PGM model is that the measured path has a single bottleneck link that determines the available bandwidth of the end-to-end path. In this letter, we show that, even though PGM is accurate in the case of a single queue, it cannot estimate the available bandwidth of multi-hop paths, even if there is a single bottleneck in the path. Whether PGM is accurate or not depends on the routing of cross traffic relative to the measurement traffic. PGM is accurate when the cross traffic follows the same path with the measurement traffic. In the general case, however, PGM can significantly underestimate the available bandwidth of an end-to-end path.
You must be joking...
Authors: Faloutsos Michalis
Published: October 2006

If despite your better judgment you decide to read this article, keep in mind that it was written during the summer, and this has been the hottest summer ever. To avoid such articles in the future, respond to the call below:Request for Contributions: Do you have a news-item of interest? Social gossip? Do you have a pressing question that needs a serious answer? Don't procrastinate: send me an email with "CCR" in the subject.
IBM's pragmatic embrace of open source
Authors: Samuelson Pamela
Published: October 2006

Open source has changed the intellectual property landscape of the software industry.
Aligning word senses using bilingual corpora
Authors: Carpuat Marine , Fung Pascale , Ngai Grace
Published: October 2006

The growing importance of multilingual information retrieval and machine translation has made multilingual ontologies extremely valuable resources. Since the construction of an ontology from scratch is a very expensive and time-consuming undertaking, it is attractive to consider ways of automatically aligning monolingual ontologies, which already exist for many of the world's major languages. Previous research exploited similarity in the structure of the ontologies to align, or manually created bilingual resources. These approaches cannot be used to align ontologies with vastly different structures and can only be applied to much studied language pairs for which expensive resources are already available. In this paper, we propose a novel approach to align the ontologies at the node level: Given a concept represented by a particular word sense in one ontology, our task is to find the best corresponding word sense in the second language ontology. To this end, we present a language-independent, corpus-based method that borrows from techniques used in information retrieval and machine translation. We show its efficiency by applying it to two very different ontologies in very different languages: the Mandarin Chinese HowNet and the American English WordNet. Moreover, we propose a methodology to measure bilingual corpora comparability and show that our method is robust enough to use noisy nonparallel bilingual corpora efficiently, when clean parallel corpora are not available.
Using Japanese honorific expressions
Authors: Shirado Tamotsu , Marumoto Satoko , Murata Masaki , Isahara Hitoshi
Published: October 2006

We investigated, via experiment, knowledge of normative honorific expressions as used in textbooks and in practice by people. Forty subjects divided into four groups according to age (younger/older) and gender (male/female) participated in the experiments. The results show that knowledge about the use of normative honorific expressions in textbooks is similar to that demonstrated by the younger subject groups, but differed from that of the older subject groups. The knowledge of the older subjects was more complex than that shown in textbooks or demonstrated by the younger subjects. A model that can identify misuse of honorific expressions in sentences is the framework for this investigation. The model is minimal, but could represent 76% to 92% of the subjects' knowledge regarding each honorific element. This model will be useful in the development of computer-aided systems to help teach how honorific expressions should be used.
Emotion recognition from text using semantic labels and separable mixture models
Authors: Wu Chung-Hsien , Chuang Ze-Jing , Lin Yu-Chung
Published: October 2006

This study presents a novel approach to automatic emotion recognition from text. First, emotion generation rules (EGRs) are manually deduced from psychology to represent the conditions for generating emotion. Based on the EGRs, the emotional state of each sentence can be represented as a sequence of semantic labels (SLs) and attributes (ATTs); SLs are defined as the domain-independent features, while ATTs are domain-dependent. The emotion association rules (EARs) represented by SLs and ATTs for each emotion are automatically derived from the sentences in an emotional text corpus using the
a priori
algorithm. Finally, a separable mixture model (SMM) is adopted to estimate the similarity between an input sentence and the EARs of each emotional state. Since some features defined in this approach are domain-dependent, a dialog system focusing on the students' daily expressions is constructed, and only three emotional states,
happy, unhappy, and neutral
, are considered for performance evaluation. According to the results of the experiments, given the domain corpus, the proposed approach is promising, and easily ported into other domains.
Backtracking intrusions
Authors: King Samuel T. , Chen Peter M.
Published: October 2006

Analyzing intrusions today is an arduous, largely manual task because system administrators lack the information and tools needed to understand easily the sequence of steps that occurred in an attack. The goal of BackTracker is to identify automatically potential sequences of steps that occurred in an intrusion. Starting with a single detection point (e.g., a suspicious file), BackTracker identifies files and processes that could have affected that detection point and displays chains of events in a dependency graph. We use BackTracker to analyze several real attacks against computers that we set up as honeypots. In each case, BackTracker is able to highlight effectively the entry point used to gain access to the system and the sequence of steps from that entry point to the point at which we noticed the intrusion. The logging required to support BackTracker added 9% overhead in running time and generated 1.2 GB per day of log data for an operating-system intensive workload.
RacerX
Authors: Engler Dawson , Ashcraft Ken
Published: October 2006

This paper describes RacerX, a static tool that uses flow-sensitive, interprocedural analysis to detect both race conditions and deadlocks. It is explicitly designed to find errors in large, complex multithreaded systems. It aggressively infers checking information such as which locks protect which operations, which code contexts are multithreaded, and which shared accesses are dangerous. It tracks a set of code features which it uses to sort errors both from most to least severe. It uses novel techniques to counter the impact of analysis mistakes. The tool is fast, requiring between 2-14 minutes to analyze a 1.8 million line system. We have applied it to Linux, FreeBSD, and a large commercial code base, finding serious errors in all of them. RacerX is a static tool that uses flow-sensitive, interprocedural analysis to detect both race conditions and deadlocks. It uses novel strategies to infer checking information such as which locks protect which operations, which code contexts are multithreaded, and which shared accesses are dangerous. We applied it to FreeBSD, Linux and a large commercial code base and found serious errors in all of them.