bluuebunny/crossref_metadata_2025 huggingface dataset:
Skiing the embedded systems mountain
Authors: Verbauwhede Ingrid , Schaumont Patrick
Published: November 2005

UCLA teaches students how to master the steep slopes of the embedded systems mountain. The EE201A graduate course connects high-level design specification to embedded implementation. There is a long-standing and wide culture gap between system designers that create those abstract specifications and the system architects that need to implement them. In industry, the culture gap has separated software from hardware teams, and platform creators from platform users. In an embedded context, where these are very tightly connected, this leads to large inefficiencies both in design time and design results. Our course takes students to both sides of the gap and lets them look at this problem from different perspectives. For a given application, it teaches how to select target architectures, tools, and design methods. The course covers a stepwise systematic design process. It includes specification, transformation, and refinement of an application. Specifications enable systematic and structured expression of an application. Transformations rework specifications into ones that are a better match for a given target architecture. Refinements lower the abstraction level toward the target architecture. The embedded systems mountain is traversed in two directions. A vertical refinement axis covers elements such as power-memory-reduction methods or fixed-point refinement. A horizontal exploration axis covers various architecture alternatives including application-specific integrated circuits (ASIC), domain-specific processors, digital signal processors (DSP), embedded cores, programmable processors, and system-on-chip (SOC). During the course, the students also go through an extensive design project to apply the methods learned in this course. A typical embedded application is used to drive the project. In this paper it is illustrated using an embedded version of an image encoder, more specifically a JPEG encoder. Several commercial tools, design environments, and platforms have been used as alternative implementation targets for this application.
A curriculum for embedded system engineering
Authors: Seviora Rudolph E.
Published: November 2005

The paper presents a curriculum for a 4-year undergraduate program in Embedded System Engineering (ESE). The curriculum was developed using a two-step approach. First, a body of education knowledge for Embedded System Engineering was defined. The body consists of sixteen knowledge areas. Each area is composed of several knowledge units, some designated as core and others as electives. The minimum lecture time for the core of each knowledge area is identified. The Body of Knowledge for Computer Engineering, developed by the IEEE-CS/ACM task force for Computing Curricula, was used as a reference. The education knowledge for ESE then served as the base for the development of the program curriculum. The curriculum has a strong mathematics and basic science base, an in-depth exposure to engineering science and design of systems implemented with digital hardware and software, and coverage of two prominent application areas of embedded systems. The curriculum core takes approximately 3 years of the program; the remaining part is elective.
Efficient subtyping tests with PQ-encoding
Authors: Gil Joseph (Yossi) , Zibin Yoav
Published: November 2005

Given a type hierarchy, a
subtyping test
determines whether one type is a direct or indirect descendant of another type. Such tests are a frequent operation during the execution of object-oriented programs. The implementation challenge is in a space-efficient encoding of the type hierarchy that simultaneously permits efficient subtyping tests. We present a new scheme for encoding multiple- and single-inheritance hierarchies, which, in the standard benchmark hierarchies, reduces the footprint of all previously published schemes. Our scheme is called
PQ-encoding
(PQE) after
PQ-trees
, a data structure previously used in graph theory for finding the orderings that satisfy a collection of constraints. In particular, we show that in the traditional object layout model, the extra memory requirements for single-inheritance hierarchies is zero. In the PQE subtyping, tests are constant time, and use only two comparisons. The encoding creation time of PQE also compares favorably with previous results. It is less than 1 s on all standard benchmarks on a contemporary architecture, while the average time for processing a type is less than 1 ms. However, PQE is not an incremental algorithm. Other than PQ-trees, PQE employs several novel optimization techniques. These techniques are applicable also in improving the performance of other, previously published, encoding schemes.
Functional declarative language design and predicate calculus
Authors: Boute Raymond
Published: November 2005

In programming language and software engineering, the main mathematical tool isde factosome form of predicate logic. Yet, as elsewhere in applied mathematics, it is used mostly far below its potential, due to its traditional formulation as just a topic in logic instead of a calculus for everyday practical use.The proposed alternative combines a language of utmost simplicity (four constructs only) that is devoid of the defects of common mathematical conventions, with a set of convenient calculation rules that is sufficiently comprehensive to make it practical for everyday use in most (if not all) domains of interest.Its main elements are a functional predicate calculus and concrete generic functionals. The first supports formal calculation with quantifiers with the same fluency as with derivatives and integrals in classical applied mathematics and engineering. The second achieves the same for calculating with functionals, including smooth transition between pointwise and point-free expression.The extensive collection of examples pertains mainly to software specification, language semantics and its mathematical basis, program calculation etc., but occasionally shows wider applicability throughout applied mathematics and engineering. Often it illustrates how formal reasoning guided by the shape of the expressions is an instrument for discovery and expanding intuition, or highlights design opportunities in declarative and (functional) programming languages.
The Church-Turing thesis and its look-alikes
Authors: Ben-Amram Amir M.
Published: November 2005

"A function is mechanically computable (that is: computable by means of a machine) if and only if it is Turing-computable."
SIGACT news complexity theory column 48
Authors: Hemaspaandra Lane A.
Published: November 2005

Here is a real gift to the field from David Johnson: After a thirteen year intermission, David is restarting his NP-completeness column. His column will now appear about twice yearly in
ACM Transactions on Algorithms.
Welcome back David, and thanks! And for those for whom a diet of two per year wont do, meals past can be found at http://www.research.att.com/~dsj/columns.html.
ACM SIGACT news distributed computing column 19
Authors: Rajsbaum Sergio
Published: November 2005

The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification, Internet, and the Web. This issue consists of:• "A review of the SIROCCO 2005 conference," by Corentin Travers.Many thanks to Corentin for his contribution to this issue.
SIGACT news online algorithms column 8
Authors: Chrobak Marek
Published: November 2005

Pros and cons of the competitive analysis have been discussed in the literature by many authors. Continuing this discussion in this quarter s column, Reza Dorrigiv and Alejandro Lopez-Ortiz review and compare various performance measures for online algorithms, highlighting their differences with respect to the competitive ratio. Many thanks to Reza and Alejandro for contributing this article.
Education forum
Authors: Ross Rocky
Published: November 2005

Every so often I revisit the state of the art with respect to the creation of web pages that include mathematics, and the rendering of those pages in standard browsers. I think that the last full treatment I gave to the topic was in the spring 2003 column. There is some good news to report.
Textbooks
Authors: Ross Rocky
Published: November 2005

Two textbooks are previewed this time. One is
Logic in Computer Science: Modelling and Reasoning about Systems, Second Edition
by
Michael Huth
and
Mark Ryan
of the Imperial College of Science, Technology, and Medicine, London and the University of Birmingham, respectively. Michael helped me get the format right for the
News
, which was greatly appreciated. The other is
A Computational Introduction to Number Theory and Algebra
by
Victor Shoup
of New York University. Enjoy.
The power of collective intelligence
Authors: Weiss Aaron
Published: November 2005

Though the overall health of the tech sector may have looked bleak a few years back---at least in the eyes of financial analysts---a blend of old and new ideas, evolving technologies, and changing cultural values have recently given the online world new vigor. With content derived primarily by community contribution, popular and influential services like Flickr and Wikipedia represent the emergence of "collective intelligence" as the new driving force behind the evolution of the Internet.
Data security in the age of compliance
Authors: Robinson Teri
Published: November 2005

In the post-Enron era, IT departments are under intense pressure not only to keep data safe, but to satisfy a host of new government-imposed security regulations
The Winchester mystery internet
Authors: Schindler Esther
Published: November 2005

Sarah Winchester, the heiress to the Winchester Rifle fortune---the rifle that won the West---was what nowadays we'd call a little unstable. Convinced that she was being haunted by the souls of the Indians killed by the Winchester Rifle, and distraught over the death of her husband and daughter, the heiress consulted a spiritualist. She was given very specific advice: As long as Sarah Winchester continued to build the house she had recently purchased, she would never die.
Once collected, data isn't private
Authors: Treese Win
Published: November 2005

The Three Laws of Data Collection

1. If data is collected, it will be stored.

2. If data is stored, it will be used in a way not expected by the subject of the data.

3. Stored data will leak.
The end of the affair?
Authors: Korman Ken
Published: November 2005

Now entering its third decade, Apple appears to have lost its way
Stackable thread mechanisms
Authors: Loepere Keith
Published: November 2005

A complex system environment such as a Java™ Virtual Machine layered on a series of system (e.g. Unix) services layered on a microkernel foundation requires multiple thread models to be supported simultaneously. The essence of the thread synchronization and manipulation mechanisms in these models can be factored into a small set of supporting thread primitives and mechanisms. These thread mechanisms are stackable, supporting multiple layered environments each with its own complex thread semantics.
Trust and accountability issues in scalable invalidation-based web cache consistency
Authors: Gupta Vijay Shivshanker
Published: November 2005

Web cache consistency is a popular problem in literature. There are a number of web cache consistency schemes, of which the invalidation-based approach is known to be most promising for improving the freshness of cached content. Yu et al. [27] proposed a scalable architecture for invalidation-based web cache consistency but it does not address the issue of trust and accountability for propagation of invalidations across several administrative domains. To address that issue, this article proposes an architecture called FIAT. In designing FIAT, we are concerned with trust and accountability issues that are likely to be encountered in designing a global event notification service. Since invalidation-based web cache consistency is a relatively well-studied problem, the discussion becomes easier if we use web cache consistency as the running theme of this paper.
Multi-agent schema of Mobile IP protocol for mobile environment
Authors: Cheng Chien-Fu , Wang Shu-Ching , Liang Tyne
Published: November 2005

Mobile communication has been more and more popular not only because it supports convenient wireless communication within networks but also due to the powerful roaming function among networks without disconnection. In conventional mobile communication designs, there is usually only one single Mobile Agent (MA) in one network, which means the whole network would go out of control once MA fails in the network Another drawback is that each MA and node in the network should maintain the binding information in its own cache. However, ask every node to store and maintain the binding information in its cache is a heavy burden. In this study, the proposed Fault-tolerant Multi-agent based Mobile IP (FMIP) schema, which can solve the above drawbacks of single MA in one network by using the multi-agent based model to provide fault-tolerant capability. In addition, we also solve the drawback of each node should maintain the binding information in its own cache by maintaining the Mobile Agent Table (MAT) and Binding Update Table (BUT) in the MA only. Finally, we shall also provide the Smooth Handoff mechanism, Take Over mechanism, and Recovery mechanism for the mobile environment to provide the powerful fault-tolerant capability.
An efficient contract signing protocol using the aggregate signature scheme to protect signers' privacy and promote reliability
Authors: Wang Chih-Hung , Kuo Yan-Sheng
Published: November 2005

Contract signing conducted over the Internet arouses concerns of fairness. Two signing parties exchange their signatures in a fair manner, so that no party can gain an advantage over the other. This paper will discuss the security issues of signers' privacy and reliability of the system for the contract signing protocol. The trusted third party (TTP), responsible for maintaining the fairness in the protocol, cannot get useful information about the exchanged signatures by solving the dispute between two parties. The concept of semi-trusted third party (STTP) adopted from Franklin and Reiter's paper (in 1997) can be used to reach our goal. However, Franklin and Reiter's protocol uses an on-line third party and is inapplicable to the exchange of signatures. Hence, we propose an efficient contract signing protocol with off-line STTP using the aggregate signature proposed by Boneh and Gentry. Furthermore, the use of aggregate signature and bilinear pairings will effectually promote system reliability.
Streets of consensus under unknown unreliable network
Authors: Wang S. C. , Chiang M. L. , Yan K. Q. , Jea K. F.
Published: November 2005

Generally, tasks in a distributed system, such as two-phase commitment in database system, the location of a replicated file, and a landing task controlled by a flight path finding system, must reach an agreement. This type of unanimity problems is called the agreement problem and one of the most fundamental problems in the field of distributed environment. It requires a set of the processors to agree on a common value even if some components of the system are corrupted. There are many significant studies about these problems in a regularized network environment such as Fully Connected Network, BroadCast Network, and MultiCast Network. Nevertheless, it is computationally infeasible to ignore the network structure in a real environment. In general, the network topology varies with time. Thus, this kind of uncertain network will generate unknown network environment and affect the system to reach a common value. In this paper, the agreement problem will be revisited in an Unknown Network. Simultaneously, Back Propagation Network (BPN) is used to help system to recognize the network structure. Subsequently, the proposed protocol, Unknown Network Protocol (UNP) can reach an agreement that uses the minimum rounds of message exchange and can tolerate the maximum number of faulty components.
Exploring the limits of leakage power reduction in caches
Authors: Meng Yan , Sherwood Timothy , Kastner Ryan
Published: November 2005

If current technology scaling trends hold, leakage power dissipation will soon become the dominant source of power consumption. Caches, because of the fact that they account for the largest fraction of on-chip transistors in most modern processors, are a primary candidate for attacking the leakage problem. While there has been a flurry of research in this area over the last several years, a major question remains unanswered---What is the total potential of existing architectural and circuit techniques to address this important design concern? In this paper, we explore the limits in which existing circuit and architecture technologies may address this growing problem. We first formally propose a parameterized model that can determine the optimal leakage savings based on the perfect knowledge of the address trace. By carefully applying the sleep and drowsy modes, we find that the total leakage power from the L1 instruction cache, data cache, and a unified L2 cache may be reduced to mere 3.6, 0.9, and 2.3%, respectively, of the unoptimized case. We further study how such a model can be extended to obtain the optimal leakage power savings for different cache configurations.
Whole execution traces and their applications
Authors: Zhang Xiangyu , Gupta Rajiv
Published: November 2005

Different types of program profiles (control flow, value, address, and dependence) have been collected and extensively studied by researchers to identify program characteristics that can then be exploited to develop more effective compilers and architectures. Because of the large amounts of profile data produced by realistic program runs, most work has focused on separately collecting and compressing different types of profiles. In this paper, we present a unified representation of profiles called Whole Execution Trace (WET), which includes the complete information contained in each of the above types of traces. Thus, WETs provide a basis for a next-generation software tool that will enable mining of program profiles to identify program characteristics that require understanding of relationships among various types of profiles. The key features of our WET representation are: WET is constructed by labeling a static program representation with profile information such that relevant and related profile information can be directly accessed by analysis algorithms as they traverse the representation; a highly effective two-tier strategy is used to significantly compress the WET; and compression techniques are designed such that they minimally affect the ability to rapidly traverse WET for extracting subsets of information corresponding to individual profile types as well as a combination of profile types. Our experimentation shows that on, an average, execution traces resulting from execution of 647 million statements can be stored in 331 megabytes of storage after compression. The compression factors range from 16 to 83. Moreover the rates at which different types of profiles can be individually or simultaneously extracted are high. We present two applications of WETs, dynamic program slicing and dynamic version matching, which make effective use of multiple kinds of profile information contained in WETs.
An overview of the Advanced CompuTational Software (ACTS) collection
Authors: Drummond L. A. , Marques O. A.
Published: November 2005

The ACTS Collection brings together a number of general-purpose computational tools that were developed by independent research projects mostly funded and supported by the U.S. Department of Energy. These tools tackle a number of common computational issues found in many applications, mainly implementation of numerical algorithms, and support for code development, execution, and optimization. In this article, we introduce the numerical tools in the collection and their functionalities, present a model for developing more complex computational applications on top of ACTS tools, and summarize applications that use these tools. Last, we present a vision of the ACTS project for deployment of the ACTS Collection by the computational sciences community.
An overview of SuperLU
Authors: Li Xiaoye S.
Published: November 2005

We give an overview of the algorithms, design philosophy, and implementation techniques in the software SuperLU, for solving sparse unsymmetric linear systems. In particular, we highlight the differences between the sequential SuperLU (including its multithreaded extension) and parallel SuperLU_DIST. These include the numerical pivoting strategy, the ordering strategy for preserving sparsity, the ordering in which the updating tasks are performed, the numerical kernel, and the parallelization strategy. Because of the scalability concern, the parallel code is drastically different from the sequential one. We describe the user interfaces of the libraries, and illustrate how to use the libraries most efficiently depending on some matrix characteristics. Finally, we give some examples of how the solver has been used in large-scale scientific applications, and the performance.
SLEPc
Authors: Hernandez Vicente , Roman Jose E. , Vidal Vicente
Published: November 2005

The Scalable Library for Eigenvalue Problem Computations (SLEPc) is a software library for computing a few eigenvalues and associated eigenvectors of a large sparse matrix or matrix pencil. It has been developed on top of PETSc and enforces the same programming paradigm.The emphasis of the software is on methods and techniques appropriate for problems in which the associated matrices are sparse, for example, those arising after the discretization of partial differential equations. Therefore, most of the methods offered by the library are projection methods such as Arnoldi or Lanczos, or other methods with similar properties. SLEPc provides basic methods as well as more sophisticated algorithms. It also provides built-in support for spectral transformations such as the shift-and-invert technique. SLEPc is a general library in the sense that it covers standard and generalized eigenvalue problems, both Hermitian and non-Hermitian, with either real or complex arithmetic.SLEPc can be easily applied to real world problems. To illustrate this, several case studies arising from real applications are presented and solved with SLEPc with little programming effort. The addressed problems include a matrix-free standard problem, a complex generalized problem, and a singular value decomposition. The implemented codes exhibit good properties regarding flexibility as well as parallel performance.
SUNDIALS
Authors: Hindmarsh Alan C. , Brown Peter N. , Grant Keith E. , Lee Steven L. , Serban Radu , Shumaker Dan E. , Woodward Carol S.
Published: November 2005

SUNDIALS is a suite of advanced computational codes for solving large-scale problems that can be modeled as a system of nonlinear algebraic equations, or as initial-value problems in ordinary differential or differential-algebraic equations. The basic versions of these codes are called KINSOL, CVODE, and IDA, respectively. The codes are written in ANSI standard C and are suitable for either serial or parallel machine environments. Common and notable features of these codes include inexact Newton-Krylov methods for solving large-scale nonlinear systems; linear multistep methods for time-dependent problems; a highly modular structure to allow incorporation of different preconditioning and/or linear solver methods; and clear interfaces allowing for users to provide their own data structures underneath the solvers. We describe the current capabilities of the codes, along with some of the algorithms and heuristics used to achieve efficiency and robustness. We also describe how the codes stem from previous and widely used Fortran 77 solvers, and how the codes have been augmented with forward and adjoint methods for carrying out first-order sensitivity analysis with respect to model parameters or initial conditions.
An overview of the Trilinos project
Authors: Heroux Michael A. , Bartlett Roscoe A. , Howle Vicki E. , Hoekstra Robert J. , Hu Jonathan J. , Kolda Tamara G. , Lehoucq Richard B. , Long Kevin R. , Pawlowski Roger P. , Phipps Eric T. , Salinger Andrew G. , Thornquist Heidi K. , Tuminaro Ray S. , Willenbring James M. , Williams Alan , Stanley Kendall S.
Published: November 2005

The Trilinos Project is an effort to facilitate the design, development, integration, and ongoing support of mathematical software libraries within an object-oriented framework for the solution of large-scale, complex multiphysics engineering and scientific problems. Trilinos addresses two fundamental issues of developing software for these problems: (i) providing a streamlined process and set of tools for development of new algorithmic implementations and (ii) promoting interoperability of independently developed software.Trilinos uses a two-level software structure designed around collections of
packages
. A Trilinos package is an integral unit usually developed by a small team of experts in a particular algorithms area such as algebraic preconditioners, nonlinear solvers, etc. Packages exist underneath the Trilinos top level, which provides a common look-and-feel, including configuration, documentation, licensing, and bug-tracking.Here we present the overall Trilinos design, describing our use of abstract interfaces and default concrete implementations. We discuss the services that Trilinos provides to a prospective package and how these services are used by various packages. We also illustrate how packages can be combined to rapidly develop new algorithms. Finally, we discuss how Trilinos facilitates high-quality software engineering practices that are increasingly required from simulation software.
Frontier search
Authors: Korf Richard E. , Zhang Weixiong , Thayer Ignacio , Hohwald Heath
Published: November 2005

The critical resource that limits the application of best-first search is memory. We present a new class of best-first search algorithms that reduce the space complexity. The key idea is to store only the Open list of generated nodes, but not the Closed list of expanded nodes. The solution path can be recovered by a divide-and-conquer technique, either as a bidirectional or unidirectional search. For many problems, frontier search dramatically reduces the memory required by best-first search. We apply frontier search to breadth-first search of sliding-tile puzzles and the 4-peg Towers of Hanoi problem, Dijkstra's algorithm on a grid with random edge costs, and the A* algorithm on the Fifteen Puzzle, the four-peg Towers of Hanoi Problem, and optimal sequence alignment in computational biology.
Lattice problems in NP ∩ coNP
Authors: Aharonov Dorit , Regev Oded
Published: November 2005

We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of √n lie in NP intersect coNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice problems: Banaszczyk [1993], Goldreich and Goldwasser [2000], and Aharonov and Regev [2003]. Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier series over the lattice. This technique might be useful elsewhere---we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP) improving on a previous result of Regev[2003]. An interesting fact is that our result emerged from a “dequantization” of our previous quantum result in Aharonov and Regev [2003]. This route to proving purely classical results might be beneficial elsewhere.
On the impossibility of dimension reduction in l
1
Authors: Brinkman Bo , Charikar Moses
Published: November 2005

The Johnson--Lindenstrauss lemma shows that any
n
points in Euclidean space (i.e., ℝ

n

with distances measured under the ℓ
2
norm) may be mapped down to
O
((log
n
)/ϵ
2
) dimensions such that no pairwise distance is distorted by more than a (1 + ϵ) factor. Determining whether such dimension reduction is possible in ℓ
1
has been an intriguing open question. We show strong lower bounds for general dimension reduction in ℓ
1
. We give an explicit family of
n
points in ℓ
1
such that any embedding with constant distortion
D
requires
n

Ω(1/
D
2
)

dimensions. This proves that there is no analog of the Johnson--Lindenstrauss lemma for ℓ
1
; in fact, embedding with any constant distortion requires
n
Ω(1)
dimensions. Further, embedding the points into ℓ
1
with (1+ϵ) distortion requires
n

½−
O
(ϵ log(1/ϵ))

dimensions. Our proof establishes this lower bound for shortest path metrics of series-parallel graphs. We make extensive use of linear programming and duality in devising our bounds. We expect that the tools and techniques we develop will be useful for future investigations of embeddings into ℓ
1
.
Hardness of approximating the shortest vector problem in lattices
Authors: Khot Subhash
Published: November 2005

Let
p
> 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in ℓ

p

norm within a constant factor. Under the stronger assumption NP ⊈ RTIME(2

poly
(log
n
)

), we show that there is no polynomial-time algorithm with approximation ratio 2

(log
n
)
1/2−ϵ

where
n
is the dimension of the lattice and ϵ > 0 is an arbitrarily small constant.We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves
some
constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction
behave well
under the
augmented tensor product
, a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2

(log
n
)
1/2-ϵ

.
Scheduling over a time-varying user-dependent channel with applications to high-speed wireless data
Authors: Andrews Matthew , Zhang Lisa
Published: November 2005

In a wireless network, a basestation transmits data to mobiles at
time-varying, mobile-dependent
rates due to the ever changing nature of the communication channels. In this article, we consider a wireless system in which the channel conditions and data arrival processes are governed by an
adversary
. We first consider a single server and a set of users. At each time step
t
, the server can only transmit data to one user. If user
i
is chosen, the transmission rate is

r
i

(
t
). We say that the system is (
w
, ε)-
admissible
if in any window of
w
time steps the adversary can schedule the users so that the total data arriving to each user is at most 1−ε times the total service it receives.Our objective is to design online scheduling algorithms to ensure stability in an admissible system. We first show, somewhat surprisingly, that the admissibility condition alone does not guarantee the existence of a stable online algorithm, even in a subcritical system (i.e., ε > 0). For example, if the nonzero rates in an infinite rate set can be arbitrarily small, then a subcritical system can be unstable for any deterministic online algorithm.On a positive note, we present a tracking algorithm that attempts to mimic the behavior of the adversary. This algorithm ensures stability for all (
w
, ε)-admissible systems that are not excluded by our instability results. As a special case, if the rate set is finite, then the tracking algorithm is stable even for a critical system (i.e., ε = 0). Moreover, the queue sizes are independent of ε. For subcritical systems, we also show that a simpler max weight algorithm is stable as long as the user rates are bounded away from zero.The offline version of our problem resembles the problem of scheduling unrelated machines and can be modeled by an integer program. We present a rounding algorithm for its linear relaxation and prove that the rounding technique cannot be substantially improved.
IT skills in a tough job market
Authors: Prabhakar Bipin , Litecky Charles R. , Arnett Kirk
Published: November 2005

IT professionals know they must keep their skills up to date. But doing so requires knowing what skills are in demand.
NewsInEssence
Authors: Radev Dragomir , Otterbacher Jahna , Winkel Adam , Blair-Goldensohn Sasha
Published: November 2005

A news delivery and summarization system, acting as a user's agent, gathers and recaps news items based on specifications and interests.
Current practices of leading e-government countries
Authors: Lee Sang M. , Tan Xin , Trimi Silvana
Published: November 2005

IT is transforming the way governments function and valuable lessons can be learned from the pioneering e-government programs that have led the charge.
Investigating wireless web adoption patterns in the U.S.
Authors: Malhotra Arvind , Segars Albert H.
Published: November 2005

Wireless Web providers should roll out new services on an
evolutionary
rather than
revolutionary
track.
The
new
Professional Development Centre boasts 1,000 courses, O'Reilly Books, and CS classics
Authors: Patterson David A.
Published: November 2005

ACM is expanding the PDC along three axes: Doubling the number of online courses, adding 500 books from Safari (including O'Reilly's library), and classic computer science books that you can help select.
Introduction
Authors: Mowshowitz Abbe , Turoff Murray
Published: November 2005

This special section presents views of a society changing under the influence of advanced information technology. Computers have been around for about half a century and their social effects have been described under many headings. The title "Digital Society" chosen for this collection of articles is intended to call attention to fundamental IT-based transformations in social organization and structure.
The growth of information workers in the U.S. economy
Authors: Wolff Edward N.
Published: November 2005

Using decennial census data to trace the increase in U.S. information workers from 1950--2000 and examining the role of subtitutional and compositional effects.
Digital aids for an aging society
Authors: Czaja Sara J. , Hiltz Starr Roxanne
Published: November 2005

As a result of 20th-century advances in medicine and standard of living there is a dramatic increase in the number of older people in the U.S. and most developed countries of world. Currently, people aged 65 years and older represent approximately 13% of the population and this number is expected to increase to 22% by 2030. Moreover, the fastest-growing subgroup within the older cohort is the "oldest old" (85 years and older) [4].
Why the Internet is bad for democracy
Authors: Noam Eli M.
Published: November 2005

The Internet is not simply a set of interconnected links and protocols---it is also a construct of the imagination, an inkblot test into which everyone projects their desires, fears, and fantasies. Some see enlightenment and education. Others see pornography and gambling. Some see sharing and collaboration. Others see spam and viruses. Yet when it comes to the impact on the democratic process, the answer seems unanimous. The Internet is good for democracy. It creates digital citizens active in the teledemocracy [1] of the Electronic Republic [2] in the e-nation [3]. But this bubble, too, needs to be pricked.
Universal access to information
Authors: Varian Hal R.
Published: November 2005

In 2003, the world produced about 800MB of information for each man, woman, and child on earth [2]. Much of this information, such as supermarket scanner data and the like, is pretty dull. But some of it, such as the material contained in books, magazines, newspapers, movies, music, and family photos, is potentially of great interest to people.
HIT and MIS
Authors: Goldschmidt Peter G.
Published: November 2005

Evaluating the potential advantages and considering the risks associated with electronic health care records.
The educational productivity paradox
Authors: Peslak Alan R.
Published: November 2005

Studying the effects of increased IT expenditures in educational institutions.
Lowering the barriers to programming
Authors: Kelleher Caitlin , Pausch Randy
Published: November 2005

Since the early 1960's, researchers have built a number of programming languages and environments with the intention of making programming accessible to a larger number of people. This article presents a taxonomy of languages and environments designed to make programming more accessible to novice programmers of all ages. The systems are organized by their primary goal, either to teach programming or to use programming to empower their users, and then, by each system's authors' approach, to making learning to program easier for novice programmers. The article explains all categories in the taxonomy, provides a brief description of the systems in each category, and suggests some avenues for future work in novice programming environments and languages.
Topology control in wireless ad hoc and sensor networks
Authors: Santi Paolo
Published: November 2005

Topology Control (TC) is one of the most important techniques used in wireless ad hoc and sensor networks to reduce energy consumption (which is essential to extend the network operational time) and radio interference (with a positive effect on the network traffic carrying capacity). The goal of this technique is to control the topology of the graph representing the communication links between network nodes with the purpose of maintaining some global graph property (e.g., connectivity), while reducing energy consumption and/or interference that are strictly related to the nodes' transmitting range. In this article, we state several problems related to topology control in wireless ad hoc and sensor networks, and we survey state-of-the-art solutions which have been proposed to tackle them. We also outline several directions for further research which we hope will motivate researchers to undertake additional studies in this field.
The internet and identifiers
Authors: Mockapetris Paul
Published: November 2005

One factor driving growth in the Internet is an increase in the number of objects involved in the Internet, whether "real" objects in the physical world such as RFID tags, toasters with IP addresses, or 'virtual' objects such as phone numbers, email addresses, or web pages. A second factor is the growth in bandwidth due to fiber optics, new wireless technologies, and the like. The "push" effect of more objects and the "pull" effect of more capability creates powerful reinforcement. Since the first step in any network activity is identifying the parties to the activity, there's a corresponding need for more and better technologies for creating identifiers, as well as technologies for search, management, etc.We rely on a variety of techniques, services, and layers of identity in today's Internet. But we need to be certain that today's services can scale and that we learn from past efforts such as ENUM, and develop effective methodologies for future problems. This talk takes a look at the technologies in use, their interdependencies, and some outstanding issues and problems.
Metarouting
Authors: Griffin Timothy G. , Sobrinho Joäo Luís
Published: November 2005

There is a shortage of routing protocols that meet the needs of network engineers. This has led to BGP being pressed into service as an IGP, despite its lack of convergence guarantees. The development, standardization, and deployment of routing protocols, or even minor changes to existing protocols, are very difficult tasks. We present an approach called Metarouting that defines routing protocols using a high-level and declarative language. Once an interpreter for a metarouting language is implemented on a router, a network operator would have the freedom to implement and use any routing protocol definable in the language. We enforce a clean separation of protocol mechanisms (link-state, path-vector, adjacency maintenance, and so on) from routing policy (how routes are described and compared). The Routing Algebra framework of Sobrinho [25] is used as the theoretical basis for routing policy languages. We define the Routing Algebra Meta-Language (RAML) that allows for the construction of a large family of routing algebras and has the key property that correctness conditions --- guarantees of convergence with respect to the chosen mechanisms --- can be derived automatically for each expression defining a new routing algebra.
HLP
Authors: Subramanian Lakshminarayanan , Caesar Matthew , Ee Cheng Tien , Handley Mark , Mao Morley , Shenker Scott , Stoica Ion
Published: November 2005

It is well-known that BGP, the current inter-domain routing protocol, has many deficiencies. This paper describes a hybrid link-state and path-vector protocol called HLP as an alternative to BGP that has vastly better scalability, isolation and convergence properties. Using current BGP routing information, we show that HLP, in comparison to BGP, can reduce the churn-rate of route updates by a factor
400
as well as isolate the effect of routing events to a region
100
times smaller than that of BGP. For a majority of Internet routes, HLP guarantees worst-case linear-time convergence. We also describe a prototype implementation of HLP on top of the XORP router platform. HLP is not intended to be a finished and final proposal for a replacement for BGP, but is instead offered as a starting point for debates about the nature of the next-generation inter-domain routing protocol.
Implications of autonomy for the expressiveness of policy routing
Authors: Feamster Nick , Johari Ramesh , Balakrishnan Hari
Published: November 2005

Thousands of competing autonomous systems must cooperate with each other to provide global Internet connectivity. Each autonomous system (AS) encodes various economic, business, and performance decisions in its routing policy. The current interdomain routing system enables each AS to express policy using
rankings
that determine how each router inthe AS chooses among different routes to a destination, and
filters
that determine which routes are hidden from each neighboring AS. Because the Internet is composed of many independent, competing networks, the interdomain routing system should provide
autonomy
, allowing network operators to set their rankings independently, and to have no constraints on allowed filters. This paper studies routing protocol stability under these conditions. We first demonstrate that certain rankings that are commonly used in practice may not ensure routing stability. We then prove that, when providers can set rankings and filters autonomously, guaranteeing that the routing system will converge to a stable path assignment essentially requires ASes to rank routes based on AS-path lengths. We discuss the implications of these results for the future of interdomain routing.
One more bit is enough
Authors: Xia Yong , Subramanian Lakshminarayanan , Stoica Ion , Kalyanaraman Shivkumar
Published: November 2005

Achieving efficient and fair bandwidth allocation while minimizing packet loss in high bandwidth-delay product networks has long been a daunting challenge. Existing end-to-end congestion control (
eg
TCP) and traditional congestion notification schemes (
eg
TCP+AQM/ECN) have significant limitations in achieving this goal. While the recently proposed XCP protocol addresses this challenge, XCP requires multiple bits to encode the congestion-related information exchanged between routers and end-hosts. Unfortunately, there is no space in the IP header for these bits, and solving this problem involves a non-trivial and time-consuming standardization process.In this paper, we design and implement a simple, low-complexity protocol, called Variable-structure congestion Control Protocol (VCP), that leverages only the existing two ECN bits for network congestion feedback, and yet achieves comparable performance to XCP,
ie
high utilization, low persistent queue length, negligible packet loss rate, and reasonable fairness. On the downside, VCP converges significantly slower to a fair allocation than XCP. We evaluate the performance of VCP using extensive ns2 simulations over a wide range of network scenarios. To gain insight into the behavior of VCP, we analyze a simple fluid model, and prove a global stability result for the case of a single bottleneck link shared by flows with identical round-trip times.
Limitations of equation-based congestion control
Authors: Rhee Injong , Xu Lisong
Published: November 2005

We study limitations of an equation-based congestion control protocol, called TFRC (TCP Friendly Rate Control). It examines how the three main factors that determine TFRC throughput, namely, the TCP friendly equation, loss event rate estimation and delay estimation, can influence the long-term throughput imbalance between TFRC and TCP. Especially, we show that different sending rates of competing flows cause these flows to experience different loss event rates. There are several fundamental reasons why TFRC and TCP flows have different average sending rates, from the first place. Earlier work shows that the convexity of the TCP friendly equation used in TFRC causes the sending rate difference. We report two additional reasons in this paper: (1) the convexity of 1/
x
where
x
is a loss event period and (2) different RTO (retransmission timeout period) estimations of TCP and TFRC. These factors can be the reasons for TCP and TFRC to experience initially different sending rates. But we find that the loss event rate difference due to the differing sending rates greatly amplifies the initial throughput difference; in some extreme cases, TFRC uses around 20 times more, or sometimes 10 times less, bandwidth than TCP.
OpenDHT
Authors: Rhea Sean , Godfrey Brighten , Karp Brad , Kubiatowicz John , Ratnasamy Sylvia , Shenker Scott , Stoica Ion , Yu Harlan
Published: November 2005

Large-scale distributed systems are hard to deploy, and distributed hash tables (DHTs) are no exception. To lower the barriers facing DHT-based applications, we have created a public DHT service called OpenDHT. Designing a DHT that can be widely shared, both among mutually untrusting clients and among a variety of applications, poses two distinct challenges. First, there must be adequate control over storage allocation so that greedy or malicious clients do not use more than their fair share. Second, the interface to the DHT should make it easy to write simple clients, yet be sufficiently general to meet a broad spectrum of application requirements. In this paper we describe our solutions to these design challenges. We also report our early deployment experience with OpenDHT and describe the variety of applications already using the system.
Meridian
Authors: Wong Bernard , Slivkins Aleksandrs , Sirer Emin Gün
Published: November 2005

This paper introduces a lightweight, scalable and accurate framework, called Meridian, for performing node selection based on network location. The framework consists of an overlay network structured around multi-resolution rings, query routing with direct measurements, and gossip protocols for dissemination. We show how this framework can be used to address three commonly encountered problems, namely, closest node discovery, central leader election, and locating nodes that satisfy target latency constraints in large-scale distributed systems without having to compute absolute coordinates. We show analytically that the framework is scalable with logarithmic convergence when Internet latencies are modeled as a growth-constrained metric, a low-dimensional Euclidean metric, or a metric of low doubling dimension. Large scale simulations, based on latency measurements from 6.25 million node-pairs as well as an implementation deployed on PlanetLab show that the framework is accurate and effective.