bluuebunny/crossref_metadata_2025 huggingface dataset:
Story driven animation
Authors: Takashima Yosuke , Shimazu Hideo , Tomono Masahiro
Published: January 2007

An animation system has been developed which generates animations from stories written in natural language. The system consists of three modules: story understanding module, stage directing module and action generating module.

The story understanding module extracts actions that are not explicitly described in the story and makes a scenario. The stage directing module adapts the scenario by determining the actors' positions on the stage and setting the stage. Actors are defined as 3-Dimensional articulated figures. Each component of an actor has its primitive motion method. To achieve complicated actions, primitive motions are combined. Referring to these complicated actions, the action generating module produces animated sequences from the adapted scenario. These three modules are tightly coupled with their knowledge bases. As an example, the story of the “Hare and Tortoise” from Aesop's Fables, written for elementary schoolchildren is used. This example proves that it is possible to produce computer animation directly from the story written in natural language, now in Japanese.
A framework for implementing pluggable type systems
Authors: Andreae Chris , Noble James , Markstrum Shane , Millstein Todd
Published: January 2007

Pluggable types have been proposed to support multiple type systems in the same programming language. We have designed and implemented J
ava
COP, a program constraint system for implementing practical pluggable type systems for Java. J
ava
COP enforces user-defined typing constraints written in a declarative and expressive rule language. We have validated our design by (re)implementing a range of type systems and program checkers. By using a program constraint system to implement pluggable types, programmers are able to check that their programs will operate correctly in restricted environments, adhere to strict programming rules, avoid null pointer errors or scoped memory exceptions, and meet style guidelines, while programming language researchers can easily experiment with novel type systems.
Eliminating synchronization-related atomic operations with biased locking and bulk rebiasing
Authors: Russell Kenneth , Detlefs David
Published: January 2007

The Java™ programming language contains built-in synchronization primitives for use in constructing multithreaded programs. Efficient implementation of these synchronization primitives is necessary in order to achieve high performance.Recent research [9, 12, 10, 3, 7] has focused on the run-time elimination of the atomic operations required to implement object monitor synchronization primitives. This paper describes a novel technique called
store-free biased locking
which eliminates all synchronization-related atomic operations on uncontended object monitors. The technique supports the bulk transfer of object ownership from one thread to another, and the selective disabling of the optimization where unprofitable, using epoch-based bulk rebiasing and revocation. It has been implemented in the production version of the Java HotSpot™VM and has yielded significant performance improvements on a range of benchmarks and applications. The technique is applicable to any virtual machine-based programming language implementation with mostly block-structured locking primitives.
Isolating and relating concerns in requirements using latent semantic analysis
Authors: Kit Lo Kwun , Man Chan Kwun , Baniassad Elisa
Published: January 2007

Aspect-oriented requirements analysis involves the identification of concerns that behaviorally influence other concerns. Such concerns are described in requirements called emphaspectual requirements: requirements that detail the influence of one concern over another. The current state of the art for aspect-oriented requirements analysis is Theme/Doc, which allows lexical analysis of requirements based on a set of developer-chosen keywords. It provides a graphical depiction of how concerns relate to requirements, and affords identification of potential aspectual requirements. In addition, clusters of requirements and concerns are identified to arrive at a more useful set of concerns than those initially identified.Because of the lexical nature of the Theme/Doc approach, aspectual requirements are missed, or wrongly identified. Additionally, requirements may be wrongly clustered if they contain ambiguous terms.In this work we explored whether the use of a statistical approach for textual analysis, Latent Semantic Analysis (LSA), would improve upon the lexical approach used by Theme/Doc. We found that LSA helps identify useful concern clusters, and helps reduce the number of falsely identified aspectual requirements.
The paradoxical success of aspect-oriented programming
Authors: Steimann Friedrich
Published: January 2007

Aspect-oriented programming is considered a promising new technology. As object-oriented programming did before, it is beginning to pervade all areas of software engineering. With its growing popularity, practitioners and academics alike are wondering whether they should start looking into it, or otherwise risk having missed an important development. The author of this essay finds that much of aspect-oriented programming's success seems to be based on the conception that it improves both modularity and the structure of code, while in fact, it works against the primary purposes of the two, namely independent development and understandability of programs. Not seeing any way of fixing this situation, he thinks the success of aspect-oriented programming to be paradoxical.
Impact of double blind reviewing on SIGMOD publication
Authors: Tung Anthony K. H.
Published: January 2007

In [1], a set of statistic had been provided with the conclusion that double blind reviewing make no impact on SIGMOD publication. Our studies here will show results contrary to that finding.
Single- versus double-blind reviewing
Authors: Snodgrass Richard
Published: January 2007

The peer review process is generally acknowledged as central to the advancement of scholarly knowledge. It is also vital to the advancement of individual careers.
An automatic construction and organization strategy for ensemble learning on data streams
Authors: Zhang Yi , Jin Xiaoming
Published: January 2007

As data streams are gaining prominence in a growing number of emerging application domains, classification on data streams is becoming an active research area. Currently, the typical approach to this problem is based on ensemble learning, which learns basic classifiers from training data stream and forms the global predictor by organizing these basic ones. While this approach seems successful to some extent, its performance usually suffers from two contradictory elements existing naturally within many application scenarios: firstly, the need for gathering sufficient training data for basic classifiers and engaging enough basic learners in voting for bias-variance reduction; and secondly, the requirement for significant sensitivity to concept-drifts, which places emphasis on using recent training data and up-to-date individual classifiers. It results in such a dilemma that some algorithms are not sensitive enough to concept-drifts while others, although sensitive enough, suffer from unsatisfactory classification accuracy. In this paper, we propose an ensemble learning algorithm, which: (1) furnishes training data for basic classifiers, starting from the up-to-date data chunk and searching for complement from past chunks while ruling out the data inconsistent with current concept; (2) provides effective voting by adaptively distinguishing sensible classifiers from the else and engaging sensible ones as voters. Experimental results justify the superiority of this strategy in terms of both accuracy and sensitivity, especially in severe circumstances where training data is extremely insufficient or concepts are evolving frequently and significantly.
Evaluating caching policies for online auctions
Authors: Menascé Daniel A. , Akula Vasudeva
Published: January 2007

Auction sites have grown rapidly in the last couple of years and recent statistics indicate that eBay carries about 50 million items for sale at any time on its site [2]. Our previous work showed that the workload of online auction sites is substantially different from that of online retailers and uncovered a plethora of interesting findings that can be used, among other things, to improve the performance of online auction sites [1, 3]: i) A very large percentage of auctions have a relatively low number of bids and bidders and a very small percentage of auctions have a high number of bids and bidders. ii) There is some bidding activity at the beginning stages of an auction. This activity slows down in the middle and increases considerably after 90% of an auction's life time has elapsed. iii) Prices rise faster in the first 20% of an auction's life time than in the next 70% of its life time. However, after the age of an auction reaches 90%, prices increase much faster than in the two previous phases.
From switching theory to "queueing" theory
Authors: Chang Cheng-Shang , Chen Yi-Ting , Cheng Jay , Huang Po-Kai , Lee Duan-Shin
Published: January 2007

Queueing theory is generally known as the theory to study the performance of queues. In this extended abstract, we are interested in another aspect of queueing theory, the theory to construct queues. Our interest in constructing queues originates from optical packet switching. Traditionally, queues are relatively cheap to build via electronic memory. However, it is very costly to convert optical packets into electronic packets. As such, building optical queues with minimum complexity has become an important research topic.
Mercury and freon
Authors: Heath Taliver , Centeno Ana Paula , George Pradeep , Ramos Luiz , Jaluria Yogesh , Bianchini Ricardo
Published: January 2007

Power densities have been increasing rapidly at all levels of server systems. To counter the high temperatures resulting from these densities, systems researchers have recently started work on
softwarebased thermal management
. Unfortunately, research in this new area has been hindered by the limitations imposed by simulators and real measurements. In this paper, we introduce Mercury, a software suite that avoids these limitations by accurately emulating temperatures based on simple layout, hardware, and componentutilization data. Most importantly, Mercury runs the entire software stack natively, enables repeatable experiments, and allows the study of thermal emergencies without harming hardware reliability. We validate Mercury using real measurements and a widely used commercial simulator. We use Mercury to develop Freon, a system that manages thermal emergencies in a server cluster without unnecessary performance degradation. Mercury will soon become available from http://www.darklab.rutgers.edu.
Supporting nested transactional memory in logTM
Authors: Moravan Michelle J. , Bobba Jayaram , Moore Kevin E. , Yen Luke , Hill Mark D. , Liblit Ben , Swift Michael M. , Wood David A.
Published: January 2007

Nested transactional memory (TM) facilitates software composition by letting one module invoke another without either knowing whether the other uses transactions.
Closed nested transactions
extend isolation of an inner transaction until the toplevel transaction commits. Implementations may flatten nested transactions into the top-level one, resulting in a complete abort on conflict, or allow partial abort of inner transactions.
Open nested transactions
allow a committing inner transaction to immediately release isolation, which increases parallelism and expressiveness at the cost of both software and hardware complexity.This paper extends the recently-proposed flat Log-based Transactional Memory (LogTM) with nested transactions. Flat LogTM saves pre-transaction values in a log, detects conflicts with read (R) and write (W) bits per cache block, and, on abort, invokes a software handler to unroll the log. Nested LogTM supports nesting by segmenting the log into a stack of activation records and modestly replicating R/W bits. To facilitate composition with nontransactional code, such as language runtime and operating system services, we propose
escape actions
that allow trusted code to run outside the confines of the transactional memory system.
Impact of virtualization on computer architecture and operating systems
Authors: Rosenblum Mendel
Published: January 2007

Abstract This talk describes how virtualization is changing the way computing is done in the industry today and how it is causing users to rethink how they view hardware, operating systems, and application programs. The talk will describe this new view on computing and the benefits driving users to adopt it. The changing roles for hardware and operating systems will be discussed along with what changes will be needed to efficiently and simply support this new computing model. I will conclude with a discussion of areas where industry could use input from the ASPLOS research community.
A comparison of software and hardware techniques for x86 virtualization
Authors: Adams Keith , Agesen Ole
Published: January 2007

Until recently, the x86 architecture has not permitted classical trap-and-emulate virtualization. Virtual Machine Monitors for x86, such as VMware ® Workstation and Virtual PC, have instead used binary translation of the guest kernel code. However, both Intel and AMD have now introduced architectural extensions to support classical virtualization.We compare an existing software VMM with a new VMM designed for the emerging hardware support. Surprisingly, the hardware VMM often suffers lower performance than the pure software VMM. To determine why, we study architecture-level events such as page table updates, context switches and I/O, and find their costs vastly different among native, software VMM and hardware VMM execution.We find that the hardware support fails to provide an unambiguous performance advantage for two primary reasons: first, it offers no support for MMU virtualization; second, it fails to co-exist with existing software techniques for MMU virtualization. We look ahead to emerging techniques for addressing this MMU virtualization problem in the context of hardware-assisted virtualization.
AVIO
Authors: Lu Shan , Tucek Joseph , Qin Feng , Zhou Yuanyuan
Published: January 2007

Concurrency bugs are among the most difficult to test and diagnose of all software bugs. The multicore technology trend worsens this problem. Most previous concurrency bug detection work focuses on one bug subclass, data races, and neglects many other important ones such as
atomicity violations
, which will soon become increasingly important due to the emerging trend of transactional memory models.This paper proposes an innovative, comprehensive, invariantbased approach called AVIO to detect atomicity violations. Our idea is based on a novel observation called
access interleaving invariant
, which is a good indication of programmers' assumptions about the atomicity of certain code regions. By automatically extracting such invariants and detecting violations of these invariants at run time, AVIO can detect a variety of atomicity violations.Based on this idea, we have designed and built
two
implementations of AVIO and evaluated the
trade-offs
between them. The first implementation, AVIO-S, is purely in software, while the second, AVIO-H, requires some simple extensions to the cache coherence hardware. AVIO-S is cheaper and more accurate but incurs much higher overhead and thus more run-time perturbation than AVIOH. Therefore, AVIO-S is more suitable for in-house bug detection and postmortem bug diagnosis, while AVIO-H can be used for bug detection during production runs.We evaluate both implementations of AVIO using large realworld server applications (Apache and MySQL) with six representative real atomicity violation bugs, and SPLASH-2 benchmarks. Our results show that AVIO detects more tested atomicity violations of various types and has 25 times fewer false positives than previous solutions on average.
Comprehensively and efficiently protecting the heap
Authors: Kharbutli Mazen , Jiang Xiaowei , Solihin Yan , Venkataramani Guru , Prvulovic Milos
Published: January 2007

The goal of this paper is to propose a scheme that provides comprehensive security protection for the heap. Heap vulnerabilities are increasingly being exploited for attacks on computer programs. In most implementations, the heap management library keeps the heap meta-data (heap structure information) and the application's heap data in an interleaved fashion and does not protect them against each other. Such implementations are inherently unsafe: vulnerabilities in the application can cause the heap library to perform unintended actions to achieve control-flow and non-control attacks.Unfortunately, current heap protection techniques are limited in that they use too many assumptions on how the attacks will be performed, require new hardware support, or require too many changes to the software developers' toolchain. We propose Heap Server, a new solution that does not have such drawbacks. Through existing virtual memory and inter-process protection mechanisms, Heap Server prevents the heap meta-data from being illegally overwritten, and heap data from being meaningfully overwritten. We show that through aggressive optimizations and parallelism, Heap Server protects the heap with nearly-negligible performance overheads even on heap-intensive applications. We also verify the protection against several real-world exploits and attack kernels.
Unbounded page-based transactional memory
Authors: Chuang Weihaw , Narayanasamy Satish , Venkatesh Ganesh , Sampson Jack , Van Biesbrouck Michael , Pokam Gilles , Calder Brad , Colavin Osvaldo
Published: January 2007

Exploiting thread level parallelism is paramount in the multicore era. Transactions enable programmers to expose such parallelism by greatly simplifying the multi-threaded programming model. Virtualized transactions (unbounded in space and time) are desirable, as they can increase the scope of transactions' use, and thereby further simplify a programmer's job. However, hardware support is essential to support efficient execution of unbounded transactions. In this paper, we introduce
Page-based Transactional Memory
to support unbounded transactions. We combine transaction bookkeeping with the virtual memory system to support fast transaction conflict detection, commit, abort, and to maintain transactions' speculative data.
A probabilistic pointer analysis for speculative optimizations
Authors: Da Silva Jeff , Steffan J. Gregory
Published: January 2007

Pointer analysis is a critical compiler analysis used to disambiguate the indirect memory references that result from the use of pointers and pointer-based data structures. A conventional pointer analysis deduces for every pair of pointers, at any program point, whether a points-to relation between them (i)
definitely
exists, (ii)
definitely does not
exist, or (iii)
maybe
exists. Many compiler optimizations rely on accurate pointer analysis, and to ensure correctness cannot optimize in the
maybe
case. In contrast, recently-proposed
speculative optimizations
can aggressively exploit the
maybe
case, especially if the likelihood that two pointers alias can be quantified. This paper proposes a
Probabilistic Pointer Analysis
(PPA) algorithm that statically predicts the probability of each points-to relation at every program point. Building on simple control-flow edge profiling, our analysis is both one-level context and flow sensitive-yet can still scale to large programs including the SPEC 2000 integer benchmark suite. The key to our approach is to compute points-to probabilities through the use of linear transfer functions that are efficiently encoded as sparse matrices.We demonstrate that our analysis can provide accurate probabilities, even without edge-profile information. We also find that-even without considering probability information-our analysis provides an accurate approach to performing pointer analysis.
Geiger
Authors: Jones Stephen T. , Arpaci-Dusseau Andrea C. , Arpaci-Dusseau Remzi H.
Published: January 2007

Virtualization is increasingly being used to address server management and administration issues like flexible resource allocation, service isolation and workload migration. In a virtualized environment, the virtual machine monitor (VMM) is the primary resource manager and is an attractive target for implementing system features like scheduling, caching, and monitoring. However, the lackof runtime information within the VMM about guest operating systems, sometimes called the semantic gap, is a significant obstacle to efficiently implementing some kinds of services.In this paper we explore techniques that can be used by a VMM to passively infer useful information about a guest operating system's unified buffer cache and virtual memory system. We have created a prototype implementation of these techniques inside the Xen VMM called Geiger and show that it can accurately infer when pages are inserted into and evicted from a system's buffer cache. We explore several nuances involved in passively implementing eviction detection that have not previously been addressed, such as the importance of tracking disk block liveness, the effect of file system journaling, and the importance of accounting for the unified caches found in modern operating systems.Using case studies we show that the information provided by Geiger enables a VMM to implement useful VMM-level services. We implement a novel working set size estimator which allows the VMM to make more informed memory allocation decisions. We also show that a VMM can be used to drastically improve the hit rate in remote storage caches by using eviction-based cache placement without modifying the application or operating system storage interface. Both case studies hint at a future where inference techniques enable a broad new class of VMM-level functionality.
Process and product certification arguments
Authors: Habli Ibrahim , Kelly Tim
Published: January 2007

Many current safety certification standards are process-based, i.e. they prescribe a set of development techniques and methods. This is perhaps best exemplified by the use of Safety Integrity Levels (SILs), e.g. as defined by IEC 61508 and UK Defence Standard 00-55. SILs are defined according to the level of the risk posed by a system, and hence prescribe the tools, techniques and methods that should be adopted by the development and assessment lifecycle. Product-based certification relies on the generation and assurance of product-specific evidence that meets safety requirements derived from hazard analysis. This evidence can be used as the argument basis in a safety case. However, uncertainty about the provenance of evidence in such a safety case can undermine confidence. To address this problem, we argue that process arguments remain an essential element of any safety case. However, unlike the sweeping process-based integrity arguments of the past, we suggest instead that highly directed process arguments should be linked to the items of evidence used in the product case. Such arguments can address issues of tool integrity, competency of personnel, and configuration management. Much as deductive software safety arguments are desirable, there will always be inductive elements. Process-based arguments of the type we suggest address partly this problem by tackling the otherwise implicit assumptions underlying certification evidence.
BASS
Authors: Poe James , Li Tao
Published: January 2007

As software vulnerabilities continue to be exposed on a daily basis and the motivation of cunning adversaries to compromise valuable computer assets grows, novel methods must be developed to ensure security. Recently there has been a growing interest within the computer architecture research community in designing architectural and hardware mechanisms to improve security. Unfortunately, there is currently not a representative set of benchmarks for evaluating the security features of proposed hardware modifications. The frequent result is that great effort is often spent searching for vulnerable programs, and/or evaluations suffer from a lack of diversity. To address this problem, we developed BASS, a benchmark suite to evaluate the security features of proposed architectural solutions under various malicious attack scenarios. BASS v 1.0 currently consists of seven benchmarks chosen to cover a diverse range of architectural attack characteristics. To facilitate the use of these benchmarks in architectural security research, we have developed both vulnerable programs and scripts to automatically generate exploits targeting those vulnerable programs across both 32-bit x86 and 64-bit Alpha Linux platforms. The entire BASS framework including documentation, source code, input data sets, and precompiled binaries for the M5 full system simulator is released under the Gnu GPL and can be freely downloaded at http://www.ideal.ece.ufl.edu/bass.
Fortran resources
Authors: Chivers Ian D , Sleightholme Jane
Published: January 2007

The following is a list of companies and organisations that provide Fortran compilers that conform to the Fortran 90 or 95 standard. Some of these compilers also implement one or more features of the Fortran 2003 standard.
Reflections on being a new female IT professional in the UAE
Authors: Bilal Sara Saeed , Mutawa Habib Al , Amir Fatma Hassan Al , Martin C. Dianne
Published: January 2007

In the June issue of inroads, two students from Zayed University, Sara Saeed Bilal and Fatma Hassan Al Amir, wrote about their ideas on what they thought it would be like to be an IT professional in the United Arab Emirates and what ethical and cultural issues they might have to address. Since that time they have both had the opportunity to do a ten-week internship in a working environment in the UAE. They now reflect on their work experience as female IT professionals in the UAE.
E-voting
Authors: Gotterbarn Don
Published: January 2007

It is generally foolish to predict the future but in this case the odds are with me. This article was written in July 2006 but it will be early December 2006 before it is in print. In the USA a 'mid-term election' was completed in November (three months after this article was written) and I presume most of the recounts from that election should be over by now.
Thoughts on student feedback to help teaching
Authors: Walker Henry M.
Published: January 2007

Most teachers have great interest in improving their courses, their interactions with students, and other components of the teaching and learning process. Although some student feedback can come from school-wide end-of-course evaluations, these typically focus on assessment for contracting, merit pay, and promotion, rather than on improvement. Thus, many school-wide evaluations contain general feedback that may provide little real insight. In some cases, the questions seem remarkably generic:The instructor is breathing:a. all of the time,b. some of the time,c. none of the time.
The open University of Israel
Authors: Gal-Ezer Judith
Published: January 2007

John Impagliazzo, editor of
inroads
, asked me to take over the Distance Learning column. Let me first thank Gordon Davies who was responsible for this column for the past few years. Gordon did a great job and I will have to work hard to follow him and make the column as interesting and appealing as he did.
Further thoughts on backtracking and bounding
Authors: González-Morris Germán
Published: January 2007

This report contains furthers analysis finding more accurate boundaries (pruning) to get a better performance for a specific backtracking algorithm based on the pattern problem. The problem statement is modest-sized to understand the combining criteria implemented reducing substantially the amount of time invested processing, and grows exponentially to the size of the problem making it expensive without applying any constraint.
Partonomy and taxonomy in object-oriented thinking
Authors: Teif Mariana , Hazzan Orit
Published: January 2007

The study presented in this paper explores junior high school students' comprehension of basic OO concepts. It summarizes major (mis)conceptions demonstrated by the students in two main categories: confusion of (1) taxonomic and (2) partonomic hierarchies with classes, objects and their interrelations.
Approaches to recruiting and retaining in computer-science based student organizations
Authors: Thompson Andrew A.
Published: January 2007

Recruitment and retention for a student organization is a very complex task. Faculty members and student leaders must attempt to appeal and relate to an often finicky demographic. This article explores various methods used to attract and retain students into their local ACM student chapter. I will review approaches used during my two year-term as ACM Chapter President at South Carolina State University (SCSU). During this period my executive board and I reactivated our dormant chapter and used various strategies to increase attendance and membership greatly from previous active years.
Research methods in computing
Authors: Holz Hilary J. , Applin Anne , Haberman Bruria , Joyce Donald , Purchase Helen , Reed Catherine
Published: January 2007

Despite a lack of consensus on the nature of Computing Research Methods (CRM), a growing number of programs are exploring models and content for CRM courses. This report is one step in a participatory design process to develop a general framework for thinking about and teaching CRM.We introduce a novel sense-making structure for teaching CRM. That structure consists of a road map to the CRM literature, a framework grounded in questions rather than answers, and two CRM skill sets: core skills and specific skills. We integrate our structure with a model for the process a learner goes through on the way to becoming an expert computing researcher and offer example learning activities that represent a growing repository of course materials meant to aid those wishing to teach research skills to computing students.Our model is designed to ground discussion of teaching CRM and to serve as a roadmap for institutions, faculty, students and research communities addressing the transition from student to fully enfranchised member of a computing research community of practice. To that end, we offer several possible scenarios for using our model.In computing, research methods have traditionally been passed from advisor to student via apprenticeship. Establishing a richer pedagogy for training researchers in computing will benefit all (see Figure 1).
Report on ACM SIGIR 2006 workshop on evaluating exploratory search systems
Authors: White Ryen W. , Muresan Gheorghe , Marchionini Gary
Published: January 2007

Exploratory search systems (ESS) are designed to help users move beyond simply finding information toward using that information to support learning, analysis, and decision-making. The evaluation of the interactive systems designed specifically to help exploratory searchers is a challenging area, worthy of further discussion in the research community. In this article we report on a workshop conducted in conjunction with the ACM SIGIR Conference in Seattle, USA, in August 2006. The workshop involved researchers, academics, and practitioners discussing the formative and summative evaluation of ESS.
SIGIR06 workshop report
Authors: Yee Wai Gen , Beigbeder Michel , Buntine Wray
Published: January 2007

This paper summarizes the activities and discussions of the 2006 Open Source Information Retrieval Workshop, held in conjunction with the 2006 ACM SIGIR Conference. It summarizes the technical program and panelist discussion on the Workshop.
Traffic classification through simple statistical fingerprinting
Authors: Crotti Manuel , Dusi Maurizio , Gringoli Francesco , Salgarelli Luca
Published: January 2007

The classification of IP ows according to the application that generated them is at the basis of any modern network management platform. However, classical techniques such as the ones based on the analysis of transport layer or application layer information are rapidly becoming ineffective. In this paper we present a ow classification mechanism based on three simple properties of the captured IP packets: their size, inter-arrival time and arrival order. Even though these quantities have already been used in the past to define classification techniques, our contribution is based on new structures called protocol fingerprints, which express such quantities in a compact and efficient way, and on a simple classification algorithm based on normalized thresholds. Although at a very early stage of development, the proposed technique is showing promising preliminary results from the classification of a reduced set of protocols.
A critique of recently proposed buffer-sizing strategies
Authors: Vu-Brugier G. , Stanojevic R. S. , Leith D. J. , Shorten R. N.
Published: January 2007

Internet router buffers are used to accommodate packets that arrive in bursts and to maintain high utilization of the egress link. Such buffers can lead to large queueing delays. Recently, several papers have suggested that it may, under general circumstances, be possible to achieve high utilisation with small network buffers. In this paper we review these recommendations. A number of issues are reported that question the utility of these recommendations.
Net neutrality
Authors: Crowcroft Jon
Published: January 2007

Network Neutrality is the subject of much current debate. In this white paper I try to find the signal in the noise by taking a largely technical look at various definitions of network neutrality and the feasibility and complexity of implementing systems that support those ideas.First off, there are a lot of emotional terms used to describe various aspects of what makes the melting pot of the neutrality debate. For example, censorship or black-holing (where route filtering, fire-walling and port blocking might say what is happening in less insightful way); free-riding is often bandied about to describe the business of making money on the net (rather than overlay service provision); monopolistic tendencies, instead of the natural inclination of an organisation that owns a lot of kit that they've sunk capital into, to want to make revenue from it.The paper describes the basic realities of the net, which has never been a level playing field for many accidental and some deliberate reasons, and then looks at the future evolution of IP (and lower level) services; the evolution of overlay services, and the evolution of the structure of the ISP business space (access, core and other); finally, I appeal to simple minded economic and regulatory arguments to ask whether there is any case at all for special pleading for the Internet as a special case, different from other services, or utilities.
Mutatis mutandis
.
How to lease the internet in your spare time
Authors: Feamster Nick , Gao Lixin , Rexford Jennifer
Published: January 2007

Today's Internet Service Providers (ISPs) serve two roles: managing their network infrastructure and providing (arguably limited) services to end users. We argue that coupling these roles impedes the deployment of new protocols and architectures, and that the future Internet should support two separate entities: infrastructure providers (who manage the physical infrastructure) and service providers (who deploy network protocols and offer end-to-end services). We present a high-level design for Cabo, an architecture that enables this separation; we also describe challenges associated with realizing this architecture.
The workshop on internet topology (wit) report
Authors: Krioukov Dmitri , claffy kc , Fomenkov Marina , Chung Fan , Vespignani Alessandro , Willinger Walter
Published: January 2007

Internet topology analysis has recently experienced a surge of interest in computer science, physics, and the mathematical sciences. However, researchers from these different disciplines tend to approach the same problem from different angles. As a result, the field of Internet topology analysis and modeling must untangle sets of inconsistent findings, conflicting claims, and contradicting statements.On May 10-12, 2006, CAIDA hosted the Workshop on Internet topology (WIT). By bringing together a group of researchers spanning the areas of computer science, physics, and the mathematical sciences, the workshop aimed to improve communication across these scientific disciplines, enable interdisciplinary cross-fertilization, identify commonalities in the different approaches, promote synergy where it exists, and utilize the richness that results from exploring similar problems from multiple perspectives.This report describes the findings of the workshop, outlines a set of relevant open research problems identified by participants, and concludes with recommendations that can benefit all scientific communities interested in Internet topology research.
Report from the clean slate network research post-sigcomm 2006 workshop
Authors: Crowcroft Jon , Key Peter
Published: January 2007

Europe has often followed in the footsteps of US research, but here we are trying to lead in Clean Slate networking research, rather than Cleans late networking. This is a report from a recent workshop on this topic.
Book review: Fundamentals of Performance Modeling by M.K. Molloy (Macmillan, 1989)
Authors: Finkel David
Published: January 2007

This book is intended, according to the author's preface, for the undergraduate computer science student without an extensive mathematical background. The book itself provides the mathematical background, through a chapter on probability theory, a chapter on transform theory, and an appendix on mathematical formulas.
An analysis of the Neal Nelson Business Benchmark
Authors: Taheri H. Reza
Published: January 2007

The Neal Nelson Business Benchmark is an industry-standard benchmark which is used to evaluate the performance of UNIX computer systems. The Business Benchmark purports to give the user an idea of the performance of the machine under real business UNIX workloads. In this article we will show that the Business Benchmark stresses few components of the system with very simple tests. As such it is more suited as a component level benchmark or users who want to focus on the performance of a particular aspect of the system, rather then a system-level UNIX benchmark representative of commercial applications.
KRIS
Authors: Baader Franz , Hollunder Bernhard
Published: January 2007

The knowledge representation system KL-ONE first appeared in 1977. Subsequently many systems based on the idea of KL-ONE have been built. The formal model-theoretic semantics which has been introduced for KL-ONE languages [9] provides means for investigating soundness and completeness of inference algorithms. It turned out that almost all implemented KL-ONE systems such as BACK, KL-TWO, LOOM, NIKL, SB-ONE use sound but incomplete algorithms.
Empirical investigation of knowledge representation servers
Authors: Gaines Brain R.
Published: January 2007

The design and application of KRS, a knowledge representation server in the KL-ONE, KRYPTON, CLASSIC family, are described. The server is designed as an open architecture module that can be used as a stand-alone service or embedded in other systems. It accepts the constraints necessary to make subsumption and recognition tractable, and maintains a careful distinction between definitions and assertions. It is implemented as a class library in an object-oriented language using generic, reusable objects. The approach taken to the integration of the server with external knowledge representation servers of similar or dissimilar types is analyzed. The server supports reasoning with exceptions and incomplete data through computation of a three-valued subsumption relation that is able to determine the possibility of further inferences if more assertions are made. KRS demonstrates that it is now possible to develop knowledge representation servers on a par with floating-point arithmetic units and numeric libraries, as modules with well-defined functionality and fast, reliable performance. It is also proving a useful tool for the empirical investigation of some large-scale knowledge representation server applications.
The CLASSIC knowledge representation system
Authors: Patel-Schneider Peter F. , McGuinness Deborah L. , Brachman Ronald J. , Resnick Lori Alperin
Published: January 2007

Our work on the CLASSIC knowledge representation system covers a broad range from theory to practice. While CLASSIC was implemented primarily to provide a simple, easy to learn and use, locally available tool for a relatively limited set of applications, it has a substantial theoretical foundation, based on a formal "terminological" logic. The logical foundation provides the semantics of a term description language, which is used to define structured concepts and make assertions about individuals in a knowledge base. These concepts and individuals are organized into a generalization hierarchy by classification and subsumption algorithms. The CLASSIC system explores the expressiveness vs. tractability tradeoff, driven by concerns of usefulness and usability in several real applications. Within this context, it embodies our views of what a knowledge representation system should
Book Review: Qualitative Process Theory Using Linguistic Variables by Bruce D'Ambrosio (Springer-Verlag New York 1989)
Authors: Akman Varol
Published: January 2007

Probably, most of the readers of this Bulletin are quite familiar with Forbus's [2]
Qualitative process theory
which I'll refer to from now on as QPT. QPT is a popular, satisfactorily sound, and rather complete (do not read the last two words in the logical sense) theory for reasoning about the physical aspects of the daily world, viz, the enterprise of
qualitative reasoning.
(See [5] for an excellent recent review of qualitative reasoning.) The book under review is an attempt to fill in some gaps in QPT and render it more complete. And in this, it succeeds admirably.
Explicit solutions to the
N
-queens problem for all N
Authors: Bernhardsson Bo
Published: January 2007

The
n
-queens problem is often used as a benchmark problem for AI research and in combinatorial optimization. An example is the recent article [1] in this magazine that presented a polynomial time algorithm for finding a solution. Several CPU-hours were spent finding solutions for some
n
up to 500,000.
Correspondence: Response to "Explicit Solutions to the N-Queens Problem for all N"
Authors: Valtorta Marco
Published: January 2007

Dear Dr. Johnson:I read with interest the correspondence regarding the
N
-Queen problem in the April 1991 issue of the
SIGART
Bulletin, including your comments in the "Letter from the Editor." I would like to contribute some additional considerations.
A decision-theoretic approach to robotic control systems
Authors: Basye Kenneth
Published: January 2007

We present an approach to building high-level control systems for robotics based on Bayesian decision theory. We show how this approach provides a natural and modular way of integrating sensing and planning. We develop a simple solution for a particular problem as an illustration. We examine the cost of using such a model and consider the areas in which abstraction can reduce this cost. We focus on one area, spatial abstraction, and discuss the design issues that arise in choosing an abstraction that we have used to solve problems involving robot navigation, and give a detailed account of the mapping from raw sensor data to the abstraction.
Integrating perception with problem solving
Authors: Benjamin Paul , Cameron Alec , Dorst Leo , Rosar Madeleine , Wu Hsiang-Lung
Published: January 2007

Problem solving is a process to convert the world from an initial state to a goal state. This paper describes an approach that interleaves perception with action in problem solving. We presume that an intelligent agent starts this process with uncertain knowledge about the initial state of the world, a specified goal state, a given set of permissible actions to alter the world state, and a given set of sensors to observe the partially understood world state. The task is to generate and execute a plan to reach a state in which the agent knows that it has reached the goal.Given a problem described by all feasible sequences of actions and perceptions applicable to coverting any given state to the goal state, we demonstrate how to construct plans that can guide both action and perception by achieving a sequence of subgoals and show it is equivalent to decomposing the representation of the problem into components corresponding to achieving subgoals. We first show that feasible sequences of actions can be decomposed into components, independent of perception, for instance through a principal series (in the case of a group, a subnormal series). This leads to subgoals with which certain observables can be associated. On the other hand, the perceptive problem can be decomposed by switching on sensors in series and performing actions that make the perceived state indistinguishable from the goal state. Finally, we show how perception can be intergrated with problem solving; we use perception to guide actions; hence, to reduce the overall cost of problem solving. The ideas are illustrated with problems taken from subgroups of Rubik's Cube; we are currently extending them to arbitrary semi-groups.
Integrated systems based on behaviors
Authors: Brooks Rodney A.
Published: January 2007

Behavior based systems require an orthogonal view of integration issues. In this paper we highlight those issues, discuss what is easy, what is hard, and where the research frontiers lie.
Integrating reaction and planning in a heterogeneous asynchronous architecture for mobile robot navigation
Authors: Gat Erann
Published: January 2007

We present an architecture for controlling autonomous mobile robots based on control of continuous activities (processes) rather than discrete actions. We define a hierarchy of activity, and argue that different levels of activities require different sorts of computational mechanisms to control them. Many controversial issues concerning the use of persistent internal state and higher levels of abstraction can be better understood in terms of this hierarchy. Two experiments using the architecture to control mobile robots performing complex navigation tasks are described.
MAX
Authors: Kuokka Daniel R.
Published: January 2007

This article summarizes the MAX system, a meta-reasoning architecture designed to integrate the reasoning, execution, and learning required of intelligent agents. MAX is based on the idea of specifying all the reasoning and learning capabilities of a system as explicit, declarative knowledge. The mechanisms that support this, as well as the benefits and drawbacks are outlined. An example of the integrated behavior implemented in MAX is given, along with comparisons to related architectures.
Behavioral synergy without explicit integration
Authors: Mataric Maja J.
Published: January 2007

We address the problem of integrating a number of capabilities into a situated system without introducing a hybrid solution consisting of a reactive low-level, and a deliberative high-level. We demonstrate a fully intergrated physical system (a mobile robot) performing navigation, landmark detection, map learning, and planning, without explicit integration. Inspired by biology and the subsumption architecture, our approach proceeds bottom-up and is fully reactive. It maximizes the use of direct information from the world, and minimizes communication within the system. The control is fully distributed over all of the components, and does not use any manipulable data structures or symbolic representations. Instead, the representation of the entire system is homogeneous; it consists of simple reactive rules which encode both the control strategy and the knowledge of the system. The exchange of knowledge within the system is mostly done implicitly, by observing, and relying on, the effects of the other components. Integration is accomplished through the components' interaction with the environment. The homogeneous, behavior-based nature of the representation does not make a distinction between the reactive and deliberating parts of the system, making them all active and interactive.