bluuebunny/crossref_metadata_2025 huggingface dataset:
Shigella dysenteriaeShuS Promotes Utilization of Heme as an Iron Source and Protects against Heme Toxicity
Authors: Wyckoff Elizabeth E. , Lopreato Gregory F. , Tipton Kimberly A. , Payne Shelley M.
Published: August 2005

Shigella dysenteriaeserotype 1, a major cause of bacillary dysentery in humans, can use heme as a source of iron. Genes for the transport of heme into the bacterial cell have been identified, but little is known about proteins that control the fate of the heme molecule after it has entered the cell. TheshuSgene is located within the heme transport locus, downstream of the heme receptor geneshuA. ShuS is a heme binding protein, but its role in heme utilization is poorly understood. In this work, we report the construction of a chromosomalshuSmutant. TheshuSmutant was defective in utilizing heme as an iron source. At low heme concentrations, theshuSmutant grew slowly and its growth was stimulated by either increasing the heme concentration or by providing extra copies of the heme receptorshuAon a plasmid. At intermediate heme concentrations, the growth of theshuSmutant was moderately impaired, and at high heme concentrations,shuSwas required for growth on heme. TheshuSmutant did not show increased sensitivity to hydrogen peroxide, even at high heme concentrations. ShuS was also required for optimal utilization of heme under microaerobic and anaerobic conditions. These data are consistent with the model in which ShuS binds heme in a soluble, nontoxic form and potentially transfers the heme from the transport proteins in the membrane to either heme-containing or heme-degrading proteins. ShuS did not appear to store heme for future use.
Helicobacter pylori
Flagellar Hook-Filament Transition Is Controlled by a FliK Functional Homolog Encoded by the Gene HP0906
Authors: Ryan Kieran A. , Karim Najma , Worku Mulugeta , Penn Charles W. , O'Toole Paul W.
Published: August 2005

Helicobacter pylori
is a human gastric pathogen which is dependent on motility for infection. The
H. pylori
genome encodes a near-complete complement of flagellar proteins compared to model enteric bacteria. One of the few flagellar genes not annotated in
H. pylori
is that encoding FliK, a hook length control protein whose absence leads to a polyhook phenotype in
Salmonella enterica
. We investigated the role of the
H. pylori
gene HP0906 in flagellar biogenesis because of linkage to other flagellar genes, because of its transcriptional regulation pattern, and because of the properties of an ortholog in
Campylobacter jejuni
(N. Kamal and C. W. Penn, unpublished data). A nonpolar mutation of HP0906 in strain CCUG 17874 was generated by insertion of a chloramphenicol resistance marker. Cells of the mutant were almost completely nonmotile but produced sheathed, undulating polyhook structures at the cell pole. Expression of HP0906 in a
Salmonella fliK
mutant restored motility, confirming that HP0906 is the
H. pylori fliK
gene. Mutation of HP0906 caused a dramatic reduction in
H. pylori
flagellin protein production and a significant increase in production of the hook protein FlgE. The HP0906 mutant showed increased transcription of the
flgE
and
flaB
genes relative to the wild type, down-regulation of
flaA
transcription, and no significant change in transcription of the flagellar intermediate class genes
flgM
,
fliD
, and
flhA
. We conclude that the
H. pylori
HP0906 gene product is the hook length control protein FliK and that its function is required for turning off the σ
54
regulon during progression of the flagellar gene expression cascade.
Role ofBorrelia burgdorferiLinear Plasmid 25 in Infection ofIxodes scapularisTicks
Authors: Strother Keith O. , de Silva Aravinda
Published: August 2005

The tick-borne bacteriumBorrelia burgdorferihas over 20 different circular and linear plasmids. SomeB. burgdorferiplasmids are readily lost during in vitro culture or genetic manipulation. Linear plasmid 25, which is often lost in laboratory strains, is required for the infection of mice. Strains missing linear plasmid 25 (lp25−) are able to infect mice if the BBE22 gene on lp25 is provided on a shuttle vector. In this study, we examined the role of lp25 and BBE22 in tick infections. We tested the hypothesis that complementation with BBE22 in spirochetes lacking lp25 would restore the ability of spirochetes to infect ticks. A natural tick infection cycle was performed by feeding larvae on mice injected with the parental, lp25−, or lp25−BBE22-complemented spirochete strains. In addition, larvae and nymphs were artificially infected with different strains to study tick infections independent of mouse infections.B. burgdorferimissing lp25 was significantly impaired in its ability to infect larval and nymphal ticks. When an lp25−strain was complemented with BBE22, the ability to infect ticks was partially restored. Complementation with BBE22 allowed spirochetes lacking lp25 to establish short-term infections in ticks, but in most cases the infection prevalence was lower than that of the wild-type strain. In addition, the number of infected ticks decreased over time, suggesting that another gene(s) on lp25 is required for long-term persistence in ticks and completion of a natural infection cycle.
Conversion of Methylglyoxal to Acetol by
Escherichia coli
Aldo-Keto Reductases
Authors: Ko Junsang , Kim Insook , Yoo Seokho , Min Bumchan , Kim Kyungmin , Park Chankyu
Published: August 2005

Methylglyoxal (MG) is a toxic metabolite known to accumulate in various cell types. We detected in vivo conversion of MG to acetol in MG-accumulating
Escherichia coli
cells by use of
1
H nuclear magnetic resonance (
1
H-NMR) spectroscopy. A search for homologs of the mammalian aldo-keto reductases (AKRs), which are known to exhibit activity to MG, revealed nine open reading frames from the
E. coli
genome. Based on both sequence similarities and preliminary characterization with
1
H-NMR for crude extracts of the corresponding mutant strains, we chose five genes,
yafB
,
yqhE
,
yeaE
,
yghZ
, and
yajO
, for further study. Quantitative assessment of the metabolites produced in vitro from the crude extracts of these mutants and biochemical study with purified AKRs indicated that the
yafB
,
yqhE
,
yeaE
, and
yghZ
genes are involved in the conversion of MG to acetol in the presence of NADPH. When we assessed their in vivo catalytic activities by creating double mutants, all of these genes except for
yqhE
exhibited further sensitivities to MG in a glyoxalase-deficient strain. The results imply that the glutathione-independent detoxification of MG can occur through multiple pathways, consisting of
yafB
,
yqhE
,
yeaE
, and
yghZ
genes, leading to the generation of acetol.
Proteomic Analysis of Global Changes in Protein Expression during Bile Salt Exposure of
Bifidobacterium longum
NCIMB 8809
Authors: Sánchez Borja , Champomier-Vergès Marie-Christine , Anglade Patricia , Baraige Fabienne , de los Reyes-Gavilán Clara G. , Margolles Abelardo , Zagorec Monique
Published: August 2005

Adaptation to and tolerance of bile stress are among the main limiting factors to ensure survival of bifidobacteria in the intestinal environment of humans. The effect of bile salts on protein expression patterns of
Bifidobacterium longum
was examined. Protein pattern comparison of strains grown with or without bile extract allowed us to identify 34 different proteins whose expression was regulated. The majority of these proteins were induced after both a minor (0.6 g liter
−1
) and a major (1.2 g liter
−1
) exposure to bile. These include general stress response chaperones, proteins involved in transcription and translation and in the metabolism of amino acids and nucleotides, and several enzymes of glycolysis and pyruvate catabolism. Remarkably, xylulose 5-phosphate/fructose 6-phosphate phosphoketolase, the key enzyme of the so-called bifidobacterial shunt, was found to be upregulated, and the activity on fructose 6-phosphate was significantly higher for protein extracts of cells grown in the presence of bile. Changes in the levels of metabolic end products (acetate and lactate) were also detected. These results suggest that bile salts, to which bifidobacteria are naturally exposed, induce a complex physiological response rather than a single event in which proteins from many different functional categories take part. This study has extended our understanding of the molecular mechanism underlying the capacity of intestinal bifidobacteria to tolerate bile.
Expanded Metabolic Reconstruction of
Helicobacter pylori
(
i
IT341 GSM/GPR): an In Silico Genome-Scale Characterization of Single- and Double-Deletion Mutants
Authors: Thiele Ines , Vo Thuy D. , Price Nathan D. , Palsson Bernhard Ø.
Published: August 2005

Helicobacter pylori
is a human gastric pathogen infecting almost half of the world population. Herein, we present an updated version of the metabolic reconstruction of
H. pylori
strain 26695 based on the revised genome annotation and new experimental data. This reconstruction,
i
IT341 GSM/GPR, represents a detailed review of the current literature about
H. pylori
as it integrates biochemical and genomic data in a comprehensive framework. In total, it accounts for 341 metabolic genes, 476 intracellular reactions, 78 exchange reactions, and 485 metabolites. Novel features of
i
IT341 GSM/GPR include (i) gene-protein-reaction associations, (ii) elementally and charge-balanced reactions, (iii) more accurate descriptions of isoprenoid and lipopolysaccharide metabolism, and (iv) quantitative assessments of the supporting data for each reaction. This metabolic reconstruction was used to carry out in silico deletion studies to identify essential and conditionally essential genes in
H. pylori
. A total of 128 essential and 75 conditionally essential metabolic genes were identified. Predicted growth phenotypes of single knockouts were validated using published experimental data. In addition, in silico double-deletion studies identified a total of 47 synthetic lethal mutants involving 67 different metabolic genes in rich medium.
Rv2358 and FurB: Two Transcriptional Regulators from
Mycobacterium tuberculosis
Which Respond to Zinc
Authors: Canneva Fabio , Branzoni Manuela , Riccardi Giovanna , Provvedi Roberta , Milano Anna
Published: August 2005

In a previous work, we demonstrated that the
Mycobacterium tuberculosis Rv2358
-
furB
operon is induced by zinc. In this study, the orthologous genes from
Mycobacterium smegmatis
mc
2
155 were inactivated and mutants analyzed. Rv2358 protein was purified and found to bind upstream of the
Rv2358
gene. Binding was inhibited by Zn
2+
ions.
TheLeptospira interrogans lexAGene Is Not Autoregulated
Authors: Cuñé Jordi , Cullen Paul , Mazon Gerard , Campoy Susana , Adler Ben , Barbe Jordi
Published: August 2005

Footprinting and mutagenesis experiments demonstrated thatLeptospira interrogansLexA binds the palindrome TTTGN5CAAA found in therecApromoter but not in thelexApromoter. In silico analysis revealed that none of the other canonical SOS genes is under direct control of LexA, making the leptospirallexAgene the first described which is not autoregulated.
Approximate distance oracles
Authors: Thorup Mikkel , Zwick Uri
Published: August 2005

Let
G
=
(V,E)
be an undirected
weighted
graph with |
V
| =
n
and |
E
| =
m
. Let
k
≥ 1 be an integer. We show that
G
=
(V,E)
can be preprocessed in
O
(
kmn

1/
k

) expected time, constructing a data structure of size
O
(
kn

1+1/
k

), such that any subsequent
distance query
can be answered, approximately, in
O(k)
time. The approximate distance returned is of stretch at most
2k
−1, that is, the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and
2k
−1. A 1963 girth conjecture of Erdós, implies that Ω(
n

1+1/
k

) space is needed in the worst case for any real stretch strictly smaller than 2
k
+1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its
constant
query time, hence the name "oracle". Previously, data structures that used only
O
(
n

1+1/
k

) space had a query time of Ω(
n

1/
k

).Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse
spanners
of weighted graphs, and improved
tree covers
and
distance labelings
of weighted or unweighted graphs.
Analyzing security protocols with secrecy types and logic programs
Authors: Abadi Martín , Blanchet Bruno
Published: August 2005

We study and further develop two language-based techniques for analyzing security protocols. One is based on a typed process calculus; the other, on untyped logic programs. Both focus on secrecy properties. We contribute to these two techniques, in particular by extending the former with a flexible, generic treatment of many cryptographic operations. We also establish an equivalence between the two techniques.
What’s on Your Hard Drive?
Authors: Grossman Edward
Published: August 2005

Every month we invite you to visit the Queue Web site and tell us: What’s on your hard drive?
Orchestrating an Automated Test Lab
Authors: Donat Michael
Published: August 2005

Networking and the Internet are encouraging increasing levels of interaction and collaboration between people and their software. Whether users are playing games or composing legal documents, their applications need to manage the complex interleaving of actions from multiple machines over potentially unreliable connections. As an example, Silicon Chalk is a distributed application designed to enhance the in-class experience of instructors and students. Its distributed nature requires that we test with multiple machines. Manual testing is too tedious, expensive, and inconsistent to be effective. While automating our testing, however, we have found it very labor intensive to maintain a set of scripts describing each machine’s portion of a given test. Maintainability suffers because the test description is spread over several files.
Review: Network Security Architectures
Authors: State Radu
Published: August 2005

Review: Network Security Architectures
Calendar
Authors: Grossman Edward
Published: August 2005

LinuxWorld Conference and Expo. February 14-17, 2005. Boston, Massachusetts
Traipsing Through the QA Tools Desert
Authors: Coatta Terry
Published: August 2005

The Jeremiahs of the software world are out there lamenting, “Software is buggy and insecure!” Like the biblical prophet who bemoaned the wickedness of his people, these malcontents tell us we must repent and change our ways. But as someone involved in building commercial software, I’m thinking to myself, “I don’t need to repent. I do care about software quality.” Even so, I know that I have transgressed. I have shipped software that has bugs in it. Why did I do it? Why can’t I ship perfect software all the time?
The state of user-centered design practice
Authors: Mao Ji-Ye , Vredenburg Karel , Smith Paul W. , Carey Tom
Published: August 2005

User-Centered Design (UCD) is a multidisciplinary design approach based on the active involvement of users to improve the understanding of user and task requirements, and the iteration of design and evaluation. It is widely considered the key to product usefulness and usability---an effective approach to overcoming the limitations of traditional system-centered design. Much has been written in the research literature about UCD. As further proof of internationally endorsed best practice, UCD processes are also defined in ISO documents, including ISO 13407 and the associated technical report, ISO TR 18529. Increasingly, UCD has become part of the cultural vernacular of the executives and managers who drive technology development in companies of all sizes.
Project portfolios
Authors: Armour Phillip G.
Published: August 2005

Assessing companies' differing attitudes toward identifying and calculating risk-taking endeavors.
The first business application
Authors: Glass Robert L.
Published: August 2005

Celebrating the pivotal role of the first business applications software.
Ad-hoc composition in wearable and mobile computing
Authors: Lalis Spyros , Karypidis Alexandros , Savidis Anthony
Published: August 2005

Changing computing capabilities can be as easy as changing outfits.
Improving the reliability of commodity operating systems
Authors: Swift Michael M. , Bershad Brian N. , Levy Henry M.
Published: August 2005

Despite decades of research in extensible operating system technology, extensions such as device drivers remain a significant cause of system failures. In Windows XP, for example, drivers account for 85% of recently reported failures.This article describes Nooks, a
reliability subsystem
that seeks to greatly enhance operating system (OS) reliability by isolating the OS from driver failures. The Nooks approach is practical: rather than guaranteeing complete fault tolerance through a new (and incompatible) OS or driver architecture, our goal is to prevent the
vast majority
of driver-caused crashes with
little or no change
to the existing driver and system code. Nooks isolates drivers within lightweight protection domains inside the kernel address space, where hardware and software prevent them from corrupting the kernel. Nooks also tracks a driver's use of kernel resources to facilitate automatic cleanup during recovery.To prove the viability of our approach, we implemented Nooks in the Linux operating system and used it to fault-isolate several device drivers. Our results show that Nooks offers a substantial increase in the reliability of operating systems, catching and quickly recovering from many faults that would otherwise crash the system. Under a wide range and number of fault conditions, we show that Nooks recovers automatically from 99% of the faults that otherwise cause Linux to crash.While Nooks was designed for drivers, our techniques generalize to other kernel extensions. We demonstrate this by isolating a kernel-mode file system and an in-kernel Internet service. Overall, because Nooks supports existing C-language extensions, runs on a commodity operating system and hardware, and enables automated recovery, it represents a substantial step beyond the specialized architectures and type-safe languages required by previous efforts directed at safe extensibility.
Spyware be gone!
Authors: Weiss Aaron
Published: August 2005

The times they are a-changing: White is the new black. Thirty is the new 20. And spyware is the new spam---with a dash of virus mixed in for good measure. (Of course, we still have plenty of original-flavor spam and viruses hanging around, too). What the old-school intruders have going for them is that they are relatively straightforward to define. Spyware, in its broadest sense, is harder to pin down. Yet many feel, as the late Supreme Court Justice Potter Stewart once said, "I know it when I see it."
Sign on the dotted line
Authors: Schindler Esther
Published: August 2005

After renting houses for 25 years, I've just bought my first home. As part of the typical house-closing process, I spent a solid 45 minutes signing my name, over and over. After a while, the pages began to blur, my desire to understand the documents faded, and writer's cramp set in.
Storage and the network
Authors: Treese Win
Published: August 2005

For as long as I can remember---and probably since the invention of the computer---there have been two rules about storage space for computer data: You never have enough of it, and if you have more, it's not connected to the right computer. Somehow this seems to be true even with the incredible increases in the capacity of disk drives, with retail prices in the neighborhood of 50 cents per gigabyte.
What else?
Authors: Tscheligi Manfred
Published: August 2005

Relevance is not always obvious. We have to investigate the unseen and talk about the unknown. Our insights from the outside come from listening to stories within our field. Synergy among the disciplines we think we constitute is always necessary, though hard to achieve. Let us ask questions for which we do not yet have an answer. We have to see what is going on beyond the standard, everywhere, in particular at places we do not consider to be central. Here we will connect to people, places, events, and much more.
Too many cooks
Authors: Beltram Dustin
Published: August 2005

This is the first in a series of articles dedicated to exploring the unique challenges facing designers, customers and users of enterprise software.

 

"Enterprise software?" you say. "What a snooze fest."

 

Well, yes, I might agree with you there. But I'll work hard to make this as interesting and useful as possible. In the months ahead, I'll explore scenarios that illuminate these challenges and, hopefully, shed a little light on how to deal with them. I'll also be talking with practitioners in the field to get their opinions and insights.

 

If you have thoughts you'd like to share on the subject, feel free to send me an email at dbeltramo@acm.org. See you next issue.
Dreaming of robots
Authors: Marcus Aaron
Published: August 2005

Bruce Sterling
is a 50-year-old cyberpunk who is currently "Provocateur-in-Residence" at the Art Center College of Design in Pasadena. His many works of science fiction include a number of robots, especially the novel and short-story cycle Schismatrix Plus.
Learning algorithms for single-instance electronic negotiations using the time-dependent behavioral tactic
Authors: Mok Wilson Wai Ho , Sundarraj R. P.
Published: August 2005

Negotiator often rely on learning an opponent's behavior and on then using the knowledge gained to arrive at a better deal. However, in an electronic negotiation setting in which the parties involved are often unknown to (and therefore lack information about) each other, this learning has to be accomplished with only the bid offers submitted during an ongoing negotiation. In this article, we consider such a scenario and develop learning algorithms for electronic agents that use a common negotiation tactic, namely, the time-dependent tactic (TDT), in which the values of the negotiating issues are dependent on the time elapsed in the negotiation. Learning algorithms for this tactic have not been proposed in the literature. Our approach is based on using the derivatives of the Taylor's series approximation of the TDT function in a three-phase algorithm that enumerates over a partial discretized version of the solution space. Computational results with our algorithms are encouraging.
Knowledge management in China
Authors: Burrows Glen R. , Drummond Damon L. , Martinsons Maris G.
Published: August 2005

China's high-priority effort to become a more knowledge-based economy and society means that knowledge management (KM) is increasingly important. For example, the timely transfer and use of business knowledge can provide a competitive advantage in practically any given industry. Despite its enormous promise in business and science, effective KM also faces formidable obstacles. Here, we explore the most notable ones in the China context.We have used surveys, interviews, focus groups, longitudinal case studies, and anecdotal information for more than a decade to develop an understanding of how knowledge is managed in China and its role in the country's drive for global competitiveness. KM in China is distinctive, constrained somewhat by technological limitations, but influenced more significantly by psychological factors (such as cultural values) among groups and social levels. Here, we describe the distinctive aspects of knowledge generation, documentation, transfer, and use that prevail in China today, highlighting the key factors influencing Chinese KM.
Letters
Authors: Grossman Edward
Published: August 2005

Done imperfectly, however, unfamiliar extended syntax can interfere with readability, creating a Tower of Babel that makes adding resources to a project expensive.
Understanding Software Patching
Authors: Dadzie Joseph
Published: August 2005

Software patching is an increasingly important aspect of today’s computing environment as the volume, complexity, and number of configurations under which a piece of software runs have grown considerably. Software architects and developers do everything they can to build secure, bug-free software products. To ensure quality, development teams leverage all the tools and techniques at their disposal. For example, software architects incorporate security threat models into their designs, and QA engineers develop automated test suites that include sophisticated code-defect analysis tools.
Review: Integration-Ready Architecture and Design: Software Engineering with XML, Java, .NET, Wireless, Speech, and Knowledge Technologies
Authors: Chang R. S.
Published: August 2005

Review: Integration-Ready Architecture and Design: Software Engineering with XML, Java, .NET, Wireless, Speech, and Knowledge Technologies
Review: PHP5 and MySQL Bible by Tim Converse and Joyce Park
Authors: Bellin David
Published: August 2005

Review: PHP5 and MySQL Bible by Tim Converse and Joyce Park
Calendar
Authors: Grossman Edward
Published: August 2005

Embedded Systems Conference
Incorporating contextual information in recommender systems using a multidimensional approach
Authors: Adomavicius Gediminas , Sankaranarayanan Ramesh , Sen Shahana , Tuzhilin Alexander
Published: August 2005

The article presents a multidimensional (MD) approach to recommender systems that can provide recommendations based on additional contextual information besides the typical information on users and items used in most of the current recommender systems. This approach supports multiple dimensions, profiling information, and hierarchical aggregation of recommendations. The article also presents a multidimensional rating estimation method capable of selecting two-dimensional segments of ratings pertinent to the recommendation context and applying standard collaborative filtering or other traditional two-dimensional rating estimation techniques to these segments. A comparison of the multidimensional and two-dimensional rating estimation approaches is made, and the tradeoffs between the two are studied. Moreover, the article introduces a combined rating estimation method, which identifies the situations where the MD approach outperforms the standard two-dimensional approach and uses the MD approach in those situations and the standard two-dimensional approach elsewhere. Finally, the article presents a pilot empirical study of the combined approach, using a multidimensional movie recommender system that was developed for implementing this approach and testing its performance.
Designing mediation for context-aware applications
Authors: Dey Anind K. , Mankoff Jennifer
Published: August 2005

Many context-aware services make the assumption that the context they use is completely accurate. However, in reality, both sensed and interpreted context is often ambiguous. A challenge facing the development of realistic and deployable context-aware services, therefore, is the ability to handle ambiguous context. Although some of this ambiguity may be resolved using automatic techniques, we argue that correct handling of ambiguous context will often need to involve the user. We use the term mediation to refer to the dialogue that ensues between the user and the system. In this article, we describe an architecture that supports the building of context-aware services that assume context is ambiguous and allows for mediation of ambiguity by mobile users in aware environments. We present design guidelines that arise from supporting mediation over space and time, issues not present in the graphical user interface domain where mediation has typically been used in the past. We illustrate the use of our architecture and evaluate it through an example context-aware application, a word predictor system.
Token+constraint systems for tangible interaction with digital information
Authors: Ullmer Brygg , Ishii Hiroshi , Jacob Robert J. K.
Published: August 2005

We identify and present a major interaction approach for tangible user interfaces based upon systems of tokens and constraints. In these interfaces, tokens are discrete physical objects which represent digital information. Constraints are confining regions that are mapped to digital operations. These are frequently embodied as structures that mechanically channel how tokens can be manipulated, often limiting their movement to a single degree of freedom. Placing and manipulating tokens within systems of constraints can be used to invoke and control a variety of computational interpretations.We discuss the properties of the token+constraint approach; consider strengths that distinguish them from other interface approaches; and illustrate the concept with eleven past and recent supporting systems. We present some of the conceptual background supporting these interfaces, and consider them in terms of Bellotti et al.'s [2002] five questions for sensing-based interaction. We believe this discussion supports token+constraint systems as a powerful and promising approach for sensing-based interaction.
Dealing with incomplete knowledge on CLP(
FD
) variable domains
Authors: Gavanelli Marco , Lamma Evelina , Mello Paola , Milano Michela
Published: August 2005

Constraint Logic Programming languages on Finite Domains, CLP(
FD
), provide a declarative framework for Artificial Intelligence problems. However, in many real life cases, domains are not known and must be acquired or computed. In systems that interact with the outer world, domain elements synthesize information on the environment, they are not all known at the beginning of the computation, and must be retrieved through an expensive acquisition process.In this article, we extend the CLP(
FD
) language by combining it with a new sort (called Incrementally specified Sets,
I-Set
). In the resulting language, CLP(
FD
+
I-Set
), FD variables can be defined on partially or fully unknown domains (
I-Set
). Domains can be linked each other through relations, and constraints can be imposed on them. We describe a propagation algorithm (called
Known Arc Consistency
(KAC)) based on known domain elements, and theoretically compare it with arc-consistency.The language can be implemented on top of different CLP systems, thus letting the user exploit different possible semantics for domains (e.g., lists, sets or streams). We state the specifications that the employed system should provide, and we show that two different CLP systems (Conjunto and {
log
}) can be effectively used.We provide motivating examples and describe promising applications.
Polymorphic predicate abstraction
Authors: Ball Thomas , Millstein Todd , Rajamani Sriram K.
Published: August 2005

Predicate abstraction is a technique for creating abstract models of software that are amenable to model checking algorithms. We show how polymorphism, a well-known concept in programming languages and program analysis, can be incorporated in a predicate abstraction algorithm for C programs. The use of polymorphism in predicates, via the introduction of symbolic names for values, allows us to model the effect of a procedure independent of its calling contexts. Therefore, we can safely and precisely abstract a procedure once and then reuse this abstraction across multiple calls and multiple applications containing the procedure. Polymorphism also enables us to handle programs that need to be analyzed in an open environment, for all possible callers. We have proved that our algorithm is sound and have implemented it in the C2BP tool as part of the SLAM software model checking toolkit.
Optimistic replication
Authors: Saito Yasushi , Shapiro Marc
Published: August 2005

Data replication is a key technology in distributed systems that enables higher availability and performance. This article surveys optimistic replication algorithms. They allow replica contents to diverge in the short term to support concurrent work practices and tolerate failures in low-quality communication links. The importance of such techniques is increasing as collaboration through wide-area and mobile networks becomes popular.Optimistic replication deploys algorithms not seen in traditional “pessimistic” systems. Instead of synchronous replica coordination, an optimistic algorithm propagates changes in the background, discovers conflicts after they happen, and reaches agreement on the final contents incrementally.We explore the solution space for optimistic replication algorithms. This article identifies key challenges facing optimistic replication systems---ordering operations, detecting and resolving conflicts, propagating changes efficiently, and bounding replica divergence---and provides a comprehensive survey of techniques developed for addressing these challenges.
Letters
Authors: Grossman Edward
Published: August 2005

Reading Stuart Feldman’s article, “Quality Assurance: Much More than Testing” (February 2005), I thought, “Oh good, someone who shares my views is writing about this.” Later, however, I found that of the four articles in the QA special report, only Feldman’s was actually about QA. Only he seems to know that QA does not equal testing. You should study his ISO 12207 definition. It says QA is about process. It is about providing confidence. The other three articles were mainly about testing techniques and only superficially about QA. Testing is only one of the possible QA activities.
News 2.0
Authors: Stanik John
Published: August 2005

For years, many of us have donated our spare CPU cycles to the romantic, and thus far fruitless, search for extraterrestrial life in the heavens above. Even without empirical proof, the Seti@home project gives us some sense of contributing to something larger than ourselves—and hope that the cool, 3D graphs being drawn and redrawn across our screens could be just moments away from plotting a new course for intelligent life in the universe.
Review: Exploiting Software: How to Break Code
Authors: Mariën A.
Published: August 2005

Review: Exploiting Software: How to Break Code
Synthesis of skewed logic circuits
Authors: Cao Aiqun , Sirisantana Naran , Koh Cheng-Kok , Roy Kaushik
Published: August 2005

Skewed logic circuits belong to a noise-tolerant high-performance static circuit family. Skewed logic circuits can achieve performance comparable to that of Domino logic circuits but with much lower power consumption. Two factors contribute to the reduction in power. First, by exploiting the static nature of skewed logic circuits, we can alleviate the cost of logic duplication which is typically required to overcome the logic reconvergence problem in both Domino logic and skewed logic circuits. Second, a selective clocking scheme can be applied to a skewed logic circuit to reduce the clock load and hence, clock power. In this article, we propose a two-step synthesis scheme of skewed logic circuits. In the first step, an integer linear programming-based approach is presented to overcome the logic reconvergence problem in skewed logic circuits with minimal logic duplication cost. In the second step, a dynamic programming-based heuristic is applied to achieve an optimal selective clocking scheme. Experimental results show that the average power saving of skewed logic circuits over Domino logic circuits is 41.1%.
Energy-efficient datapath scheduling using multiple voltages and dynamic clocking
Authors: Mohanty Saraju P. , Ranganathan N.
Published: August 2005

Recently, dynamic frequency scaling has been explored at the CPU and system levels for power optimization. Low-power datapath scheduling using multiple supply voltages has been well researched. In this work, we develop new datapath scheduling algorithms that use multiple supply voltages and dynamic frequency clocking in a coordinated manner in order to reduce the energy consumption of datapath circuits. In dynamic frequency clocking, the functional units can be operated at different frequencies depending on the computations occurring within the datapath during a given clock cycle. The strategy is to schedule high-energy units, such as multipliers at lower frequencies, so that they can be operated at lower voltages to reduce energy consumption and the low-energy units, such as adders at higher frequencies, to compensate for speed. The proposed time- and resource-constrained algorithms have been applied to various high-level synthesis benchmark circuits under different time and resource constraints. The experimental results show significant reduction in energy for both the algorithms.
Large-scale circuit placement
Authors: Cong Jason , Shinnerl Joseph R. , Xie Min , Kong Tim , Yuan Xin
Published: August 2005

Placement is one of the most important steps in the RTL-to-GDSII synthesis process, as it directly defines the interconnects, which have become the bottleneck in circuit and system performance in deep submicron technologies. The placement problem has been studied extensively in the past 30 years. However, recent studies show that existing placement solutions are surprisingly far from optimal. The first part of this tutorial summarizes results from recent optimality and scalability studies of existing placement tools. These studies show that the results of leading placement tools from both industry and academia may be up to 50% to 150% away from optimal in total wirelength. If such a gap can be closed, the corresponding performance improvement will be equivalent to several technology-generation advancements. The second part of the tutorial highlights the recent progress on large-scale circuit placement, including techniques for wirelength minimization, routability optimization, and performance optimization.
Jef Raskin, pioneer
Authors: Karpinski Richard
Published: August 2005

We note with sadness the passing of Jef Raskin on February 26, 2005. Jef Raskin, a mathematician, orchestral soloist and composer, professor, bicycle racer, model airplane designer, and pioneer in the field of human-computer interactions, died peacefully at home in California surrounded by his family and loved ones. He had recently been diagnosed with pancreatic cancer. Read his obituary at www.raskincenter.org/pressrelease.html.
There once was a whiteboard in verse...
Authors: Buie Elizabeth
Published: August 2005

Your editor of Whiteboard, E. Buie,

Had a notion that sounded like hooey:

"Some poems I'll solicit

From colleagues complicit---

On design, interaction, and GUI!"
A covenant with transparency
Authors: Fleischmann Kenneth R. , Wallace William A.
Published: August 2005

One important ethical aspect of the use of models for decision making is the relative power of the various actors involved in decision support: the modelers, the clients, the users, and those affected by the model. Each has a different stake in the design of decision support models, and the outcome of modeling depends on both the technical attributes of the model and the relationships among the relevant actors. Increasing the transparency of the model can significantly improve these relationships. Here, we explore the importance of transparency in the design and use of decision support models.
Information dissemination via wireless broadcast
Authors: Zheng Baihua , Lee Dik Lun
Published: August 2005

Unrestricted mobility adds a new dimension to data access methodology--- one that must be addressed before true ubiquity can be realized.
TinyDB: an acquisitional query processing system for sensor networks
Authors: Madden Samuel R. , Franklin Michael J. , Hellerstein Joseph M. , Hong Wei
Published: August 2005

We discuss the design of an acquisitional query processor for data collection in sensor networks. Acquisitional issues are those that pertain to where, when, and how often data is physically acquired (
sampled
) and delivered to query processing operators. By focusing on the locations and costs of acquiring data, we are able to significantly reduce power consumption over traditional passive systems that assume the a priori existence of data. We discuss simple extensions to SQL for controlling data acquisition, and show how acquisitional issues influence query optimization, dissemination, and execution. We evaluate these issues in the context of TinyDB, a distributed query processor for smart sensor devices, and show how acquisitional techniques can provide significant reductions in power consumption on our sensor devices.
Statistical geometry representation for efficient transmission and rendering
Authors: Kalaiah Aravind , Varshney Amitabh
Published: August 2005

Traditional geometry representations have focused on representing the details of the geometry in a deterministic fashion. In this article we propose a statistical representation of the geometry that leverages local coherence for very large datasets. We show how the statistical analysis of a densely sampled point model can be used to improve the geometry bandwidth bottleneck, both on the system bus and over the network as well as for randomized rendering, without sacrificing visual realism. Our statistical representation is built using a clustering-based hierarchical principal component analysis (PCA) of the point geometry. It gives us a hierarchical partitioning of the geometry into compact local nodes representing attributes such as spatial coordinates, normal, and color. We pack this information into a few bytes using classification and quantization. This allows our representation to directly render from compressed format for efficient remote as well as local rendering. Our representation supports both view-dependent and on-demand rendering. Our approach renders each node using quasi-random sampling utilizing the probability distribution derived from the PCA analysis. We show many benefits of our approach: (1) several-fold improvement in the storage and transmission complexity of point geometry; (2) direct rendering from compressed data; and (3) support for local and remote rendering on a variety of rendering platforms such as CPUs, GPUs, and PDAs.
IT professionals as organizational citizens
Authors: Moore Jo Ellen , Love Mary Sue
Published: August 2005

Are managers discouraging IT professionals from exhibiting behaviors the organization desperately needs?
Knowledge management mechanisms of financial service sites
Authors: Nah Fiona Fui-Hoon , Siau Keng , Tian Yuhong
Published: August 2005

How can we effectively acquire, use, and manage knowledge via the Web?
The Supreme Court revisits the
Sony
safe harbor
Authors: Samuelson Pamela
Published: August 2005

What will the Supreme Court do in
MGM v. Grokster
? How will this decision affect you?
Layered manufacturing technologies
Authors: McMains Sara
Published: August 2005

From the holodeck in "Star Trek" to the slice-by-slice reconstruction of the alien Leeloo played by actress Milla Jovovich in the movie
The Fifth Element
, science fiction has long predicted the possibility of automated one-off construction of the most complex objects from a stream of digital information. While we are still a long way from being able to build living beings in this manner, digitally controlled layered manufacturing (LM) technologies are transforming prototyping and mass customization of mechanical and biomedical parts of extraordinary geometric complexity.
The race for space
Authors: Robinson Teri
Published: August 2005

Holographic storage records and reads millions of bits simultaneously, offering instant access to vast quantities of data
Virtualization virtually everywhere
Authors: Treese Win
Published: August 2005

I'm writing this column in April. Like many people, I'm using Intuit's TurboTax to prepare my income-tax forms. But I'm using TurboTax in a somewhat unusual way: running it on a virtual machine. TurboTax normally runs on Microsoft Windows, but the computer I want to use runs Linux. To make this all work, I'm using a program called VMware that provides the illusion of an entire separate computer on which Windows can run. From the point of view of the Linux system, VMware is just another application with just another window on the screen. The Windows software sees a full computer, and it can't really tell the difference between the virtual environment and the real one.
A pairwise key predistribution scheme for wireless sensor networks
Authors: Du Wenliang , Deng Jing , Han Yunghsiang S. , Varshney Pramod K. , Katz Jonathan , Khalili Aram
Published: August 2005

To achieve security in wireless sensor networks, it is important to be able to encrypt and authenticate messages sent between sensor nodes. Before doing so, keys for performing encryption and authentication must be agreed upon by the communicating parties. Due to resource constraints, however, achieving key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and other public-key based schemes, are not suitable for wireless sensor networks due to the limited computational abilities of the sensor nodes. Predistribution of secret keys for all pairs of nodes is not viable due to the large amount of memory this requires when the network size is large.In this paper, we provide a framework in which to study the security of key predistribution schemes, propose a new key predistribution scheme which substantially improves the resilience of the network compared to previous schemes, and give an in-depth analysis of our scheme in terms of network resilience and associated overhead. Our scheme exhibits a nice threshold property: when the number of compromised nodes is less than the threshold, the probability that communications between any additional nodes are compromised is close to zero. This desirable property lowers the initial payoff of smaller-scale network breaches to an adversary, and makes it necessary for the adversary to attack a large fraction of the network before it can achieve any significant gain.
Letters
Authors: Grossman Edward
Published: August 2005

Jef Raskin’s article, “Comments Are More Important than Code” (March 2005), made my day! Ideally the comments should outline (in a form clarified by hindsight) the intellectual process that led to the code.
What’s on Your Hard Drive?
Authors: Grossman Edward
Published: August 2005

Combine this storage surplus with gigabytes of RAM, and we have a breeding ground for that most conspicuous of “wares”: bloatware. We’ve all seen it, and many of us use it every day. We may have even become comfortable with these overweight tools and now barely recognize them as such. Indeed, they can simultaneously be our greatest enemies and our most familiar friends.
A Conversation with Tim Marsland
Authors: McKusick Kirk
Published: August 2005

Delivering software to customers, especially in increments to existing systems, has been a difficult challenge since the days of floppies and shrink-wrap. But with guys like Tim Marsland working on the problem, the process could be improving.
Implementation of hierarchical bases in FEMLAB for simplicial elements
Authors: Xin Jianguo , Pinchedez Katia , Flaherty Joseph E.
Published: August 2005

We present the implementation of well-conditioned hierarchical bases for one-dimensional, triangular and tetrahedral elements in finite element FEMLAB software. Using the domain mesh information provided by FEMLAB, we found an easy way to maintain the continuity of solution across the interelement boundaries. The conditionings of the global stiffness matrices of several standard problems are compared with the Lagrange bases and are smaller for all cases.
Does spell-checking software need a warning label?
Authors: Galletta Dennis F. , Durcikova Alexandra , Everard Andrea , Jones Brian M.
Published: August 2005

Users---ironically, often those most verbally armed---put too much trust and little effort in questioning spell- and grammar-checking programs.