bluuebunny/crossref_metadata_2025 huggingface dataset:
Review of proof, language, and interaction
Authors: Pucella Riccardo
Published: October 2004

The field of theoretical computer science has had a long tradition of providing wonderful edited books to honor various prominent members of the community. The idea behind such edited works is clear: celebrate the work of a particular researcher by having co-authors and colleagues write papers on subjects related to the researcher's body of work. When successful, such a project provides for a wonderful excursion through the work of a researcher, often highlighting an underlying coherence to that work.On that account, the book
Proof, Language, and Interaction: Essays in the Honor of Robin Milner
(edited by Plotkin, Stirling and Tofte) is a success. In no small part this is due to Milner's span of work from theory to practice. It is hard to both briefly describe Milner's contributions and give an idea of the breadth of his effort. Two major tracks of research emerge. First, after some work with John McCarthy's AI group at Stanford, he developed LCF (specifically, Edinburgh LCF), a system for computer-assisted theorem proving based on Dana Scott's idea on continuous partial functions for denotational semantics. Not only working on the implementation, Milner also worried about the semantic foundations [1]. LCF came with a programming language, Edinburgh ML, which evolved with Milner's help into standard ML, a higher-order language that introduced many features now standard in advanced programming language, features such as polymorphism and type inference [4]. His second track of research involves concurrency. He invented CCS, the calculus of communicating systems [2]. Work on the semantics of CCS went from the traditional domain-theoretic approach to a new operational view of processes equality based on the notion of bisimulation. Subsequent work by Milner led to the development of other calculi, most notably the π-calculus, which included a powerful notion of mobility [3]. His later work in the area attempted to provide a unifying framework for comparing calculi, and unifying sequential and concurent computation.This range of interests is reflected in the table of contents of the book. The book splits across different subjects:
semantic foundations,
where we discover work aimed at understanding computation, both sequential and concurrent,
programming logic,
where we discover work derived from Milner's work on LCF, and aimed at understanding the role of formal mathematics,
programming languages,
where we discover Standard ML, and other languages based on Milner's idea about concurrent calculi,
concurrency,
where we discover work on Milner's early CCS approach and extensions, and
mobility,
where we discover work related to the π-calculus.
SIGACT news complexity theory column 31
Authors: Hemaspaandra Lane A.
Published: October 2004

This issue's guest column, by Art Werschulz, is on information-based computation. Given that this arrived during the first half of December 2000, Art clearly deserves a heroic focus award for making the time to write such a wonderful column while every news cycle was filled with the ups and downs of a presidential post-election adventure the likes of which is not likely to be seen again in any of our lifetimes.Upcoming complexity theory columns include articles by: J. Castro, R. Gavaldà, and D. Guijarro; S. Ravi Kumar and D. Sivakumar; R. Paturi; and M. Holzer and P. McKenzie.
ACM SIGACT news distributed computing column 2
Authors: Rajsbaum Sergio
Published: October 2004

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 two guest contributions: A review of the DISC 2000 Conference by Lisa Higham, and a routing survey by Cyril Gavoille. This survey focuses on routing messages in distributed networks with efficient data structures. After an overview of the various results of the literature, some interestingly open problems are described. Many thanks to Lisa and Cyril!
Itanium's new basic operation of fused multiply-add
Authors: Kreinovich Vladik
Published: October 2004

A new Intel's 64-bit chip
Itanium
has a new instruction set which includes a fused multiply-add instruction
x
1
+
x
2
·
x
3
(see, e.g., [7]). In this short article, we explain the empirical reasons behind the choice of this instruction, give possible theoretical explanation for this choice, and mention a related theoretical challenge.
Review of
Probabilistic Combinatorics and Its Applications
Authors: Krizanc Danny
Published: October 2004

Probablistic arguments have been applied in many areas of combinatorics and theoretical computer science ever since Erdös first used one to prove bounds on Ramsey numbers. Applications range from constructing graphs with properties useful in building communication networks to almost uniform generation of random structures for the purpose of approximately solving intractable counting problems. This book consists of a series of introductory survey articles on topics in probablistic combinatorics and its applications. (The articles are derived from lectures given in one of a series of short courses sponsored by the American Mathematical Society.) The topics covered include random and random-like graphs, discrete isoperimetric inequalities, rapidly mixing Markov chains, and finite Fourier methods. The emphasis throughout the book is on techniques, with sufficient examples to show their usefulness.
Biomolecular computing
Authors: Hemaspaandra Lane A.
Published: October 2004

And so summer comes around again. What a good time to relax on the beach (with your theorem notebook), to go on that long-planned family vacation (certainly with your theorem notebook, and don't forget to bring the family) and, above all, to catch up on all the papers and progress that have been piling up during the academic year on your "if only I had the time" list.The current column may save you some time on this! In 1997, Mitsunori Ogihara and Animesh Ray, jointly with Kimberly Smith, wrote a guest column on biomolecular computing. Of course, this is an area of intense activity, and in the current issue, they have contributed a delightful column catching us all up on some recent advances in biomolecular computing. (P.S. Coming soon to a future issue will be a guest column by Amnon Ta-Shma on classical versus quantum communication complexity.)
Continuations, functions and jumps
Authors: Thielecke Hayo
Published: October 2004

Practically all programming languages have some form of control structure or jumping. The more advanced forms of control structure tend to resemble function calls, so much so that they are usually not even described as jumps. Consider for example the library function exit in C. Its use is much like a function, in that it may be called with an argument; but the whole point of exit is of course that its behaviour is utterly non-functional, in that it jumps out of arbitrarily many surrounding blocks and pending function calls. Such a "non-returning function" or "jump with arguments" is an example of a
continuation
in the sense which we are interested in here.On the other hand, a simple but fundamental idea in compiling is that a function call is broken down into two jumps: one from the caller to the callee for the call itself, and another jump back from the callee to the caller upon returning. (The return statement in C is in fact listed among the "jump statements" [5].) This is most obvious for void-accepting and -returning functions, but it generalizes to other functions as well, if one is willing to understand "jump" in the broader sense of jump with arguments, i.e. continuation.In this view, then, continuations are everywhere. Continuations have been used in many different settings, in which they appear in different guises, ranging from mathematical functions to machine addresses. Rather than confine ourselves to a definition of what a continuation is, we will focus on continuation-passing style (CPS), as it brings out the commonalities. The CPS transform compresses a great deal of insight into three little equations in λ-calculus. Making sense of it intuitively, however, requires some background knowledge and a certain fluency. The purpose of this article, therefore, is to help the reader uncompress the CPS transform by way of a rational reconstruction from jumps.In the sequel, we will attempt to illustrate the correspondence between continuations and jumps (even in the guise of the abhorred goto). The intent is partly historical, to retrace some of the analysis of jumps that led to the discoveries of continuations. At the same time, the language of choice for many researchers during the (pre)history of continuations, ALGOL 60, is not so different from today's mainstream languages (i.e. C); we hope that occasional snippets of C may be more easily accessible to many readers than a functional language would be. So in each of the four sections (Sections 2-5 below) that make up the body of this paper, some C code will be used to give a naive but concrete example of the issue under consideration, before generalizing to a more abstract setting.
Education forum
Authors: Ross Ricky
Published: October 2004

This is not a column with a particular focus. It's hard after all, to focus during finals week (or the week or two immediately preceding it). These are, in fact, the days when one wonders about the sanity of having chosen a career in education and when one looks forward to a summer's respite from direct involvement in the process, not the days when one is overcome with inspiration and desire to rush out and implement innovations in the curriculum.No, this column is more like campfire stew, a few things new mixed with a few things old, lightly seasoned and warmed up over a fire at twilight.
An enforced inter-admission delay performance-driven connection admission control algorithm
Authors: Belenki Stanislav
Published: October 2004

Connection Admission Control (CAC) is an important function in a computer network that supports Quality of Service (QoS). The function of CAC is to decide whether a new connection can be admitted on the network or a part of the network in such a way that the QoS of the new connection and the already established connections will remain within the requested limits. CAC must also ensure that network resources are used efficiently avoiding unnecessary rejections of candidate connections. Some CAC algorithms attempt to estimate or derive available resources in each hop between the source and the destination. Then they use parameters of the candidate flow and the knowledge about the available resources to make the admission decision. Very often such algorithms use measurements to find out availability of the resources. Hence the name of such algorithms, Measurement-Based CAC (MBCAC). Another class of CAC algorithms assumes that it is the end nodes and not the network that should perform the connection admission. These algorithms use probing packets to probe the path between the end nodes for the requested level of QoS. In this paper a heuristic-based per-hop CAC algorithm is introduced that adapts the average rate of connection admission in response to the measured system performance. In particular, the algorithm decreases the rate of the connection admission when the system is overloaded and increases it when the system is underutilized. The paper uses simulations to show that the algorithm is free from the shortcomings of the current MBCAC algorithms.
A secure multicast protocol with copyright protection
Authors: Chu Hao-hua , Qiao Lintian , Nahrstedt Klara , Wang Hua , Jain Ritesh
Published: October 2004

We present a simple, efficient, and secure multicast protocol with copyright protection in an open and insecure network environment. There is a wide variety of multimedia applications that can benefit from using our secure multicast protocol, e.g., the commercial pay-per-view video multicast, or highly secure military intelligence video conference. Our secure multicast protocol is designed to achieve the following goals. (1) It can run in any open network environment. It does not rely on any security mechanism on intermediate network switches or routers. (2) It can be built on top of any existing multicast architecture. (3) Our key distribution protocol is both secure and robust in the presence of long delay or membership message. (4) It can support dynamic group membership, e.g., JOIN/LEAVE/EXPEL operations, in a network bandwidth efficient manner. (5) It can provide copyright protection for the information provider. (6) It can help to identify insiders in the multicast session who are leaking information to the outside world. We have implemented a prototype system which validates our secure multicast protocol and evaluated it against various performance matrices. The experimental results are very encouraging, but also show where new engineering approaches need to be deployed to conform fully to the design goals.
A case for exceptions
Authors: Vardanega Tullio
Published: October 2004

In this short paper we argue in favour of the value of language support for exceptions. To make our case, we first spell out what we consider exceptions to be about and then discuss reasons for the timid use of them by Ada programmers so far. Finally, we present requirements for an enhanced exception model that, we expect, would increase the confidence and the take up of users.
Enhancing exception support in Ada 95
Authors: Taft S. Tucker
Published: October 2004

This workshop position paper discusses two alternative approaches to enhancing exception support. The first approach is based on a syntax extension, and is very similar to an approach proposed early in the Ada 9X process. The second approach is based on adding a child package to Ada.Exceptions to support raising an exception and associating an Ada object of any type that is an extension of a particular root type.
A side-by-side comparison of exception handling in Ada and Java
Authors: Strohmeier Alfred , Chachkov Stanislav
Published: October 2004

The purpose of this paper is to compare the exception handling mechanisms of Ada and Java. In order to be intelligible and useful to both communities, we have tried not to get into specific technical intricacies of the languages, perhaps sometimes at the cost of precision. Nevertheless, we decided to use the language-specific terminology whenever we write about a given language. We believe that the contrary would often lead to misunderstandings: a) the same term sometimes covers two different concepts, e.g. object, or b) when the concepts are basically the same, the features provided by the language can be largely different, making any unification impossible, e.g. task in Ada and thread in Java.Table 1 "Comparison of Terminology" shows the meanings and correspondences of the most important terms related directly or indirectly to exception handling in the two languages.We did not try to assess the merits of the two languages, not even with regard to exception handling. The issues are too many, and would by far exceed the scope of this paper: How to assess trade-offs between expressive power and performance, if ever a definite evaluation of performance is possible? How to assess language constructs whose "good" intent cannot be enforced? E.g. in Java, the "lazy" programmer can declare Throwable in a method's throws clause, instead of referring to specific exception classes. Where is the borderline between responsibility left to the programmer, and an admittedly error-prone construct in the language?Our goal was therefore to present facts, and facts only, as much as this is possible without any interpretation.
Implementing transactions using Ada exceptions
Authors: Patiño-Martínez M. , Jiménez-Peris R. , Arévalo S.
Published: October 2004

Transactional Drago
programming language is an
Ada
extension that provides transaction processing capabilities. Exceptions have been integrated with transactions in
Transactional Drago;
exceptions are used to notify transaction aborts and any unhandled exception aborts a transaction. Transactions can be multithreaded in
Transactional Drago,
and therefore, concurrent exceptions can be raised. In that case a single exception must be chosen to notify the transaction abort.
Transactional Drago
provides exception resolution within transactions to tackle such a situation. In this paper we describe the transaction model of
Transactional Drago
focusing on how the
Ada
exception model can be used to implement
Transactional Drago
semantics. In the paper we identify which features of
Ada
were useful, as well as some weaknesses we have found in the language. We point out some missing basic mechanisms for the
Ada
standard that can be of great help for developing applications with strong exception handling requirements like transactional frameworks and many other applications.
DROOPI
Authors: Quinot Thomas , Kordon Fabrice , Pautet Laurent
Published: October 2004

This paper presents our work to bridge the Ada 95 Distributed Systems Annex (DSA) and CORBA to take advantages of both environments facilities. Our project consists in two successive steps. The first one is CIAO, a DSA to CORBA translator. The second one aims at the definition of a generic middleware to be customized to DSA and CORBA. We propose a definition and an architecture of services for a generic middleware,

D
ROOPI
,

and explain how it can be customized according various criteria. This generic middleware takes advantage of the lessons learned in the design and the development of several projects: GLADE [24], AdaBroker [1], and CIAO [25]. Therefore, in its motivation and its targetting, we believe

D
ROOPI

is an original project.
An IDL to Ada95 mapping to support propagation modeling
Authors: Needham D. , Demurjian S. , Peters T.
Published: October 2004

Representing dynamic interdependencies between design objects is an essential part of modeling the critical software communications found in complex software systems. This paper investigates the modeling of propagations (our term for dynamic interdependencies), which are captured using design-level triggers for specifying dynamic behavior across object types. We focus on the CORBA-compliant utilization of our propagation model to support distributed, propagation-focused applications. We develop a propagation-specific interface in IDL, and examine Ada 95 source code that meets the requirements specified by the IDL design. An example of the CORBA-compliant propagations involved in the maintenance of topological invariance in the industrial domain is examined.
Agent oriented programming with Ada'95
Authors: Hait Férial Benachour
Published: October 2004

This paper shows the suitability of Object Oriented Programming language Ada'95 for Agent Oriented Programming. Agent oriented programming relies on the assumption, that a complex distributed software system can be programmed as a set of communicating, interacting, knowledge base entities called (software) agents. In this work we study the financial market case by introducing new modeling and implementation tools in order to simulate and understand some properties of the market evolution process. Object -Oriented modeling of social systems requires the integration of new concepts related to mental processes such as learning, planning, knowledge representation and communication. If one defines an agent as an object combination of mental state to perceive its environment and achieve some goals, a knowledge base to hold its
memory
and an interfacing communication with other entities then all the above properties could be fulfilled. In this paper we describe a method for the use of Ada object Oriented Programming language for the implementation of a MAS plate-form. The results obtained in the experimental part lead to some parameters of the model validation, like the agent's performance in increasing their own wealth and their adapted behavior throughout the evolving market.
Ethics and information systems
Authors: Smith H. Jeff
Published: October 2004

The information systems (I/S) community is becoming concerned with questions of ethical behavior in many realms. But those who attempt to resolve the quandaries may find themselves confused by differing approaches and theoretical assumptions that are often proffered. This paper provides a meta-framework that identifies the areas of convergence and divergence in these approaches and assumptions. An illustrative example (America Online's plans to share subscriber information with telemarketers) is examined through several sets of lenses. Special attention is paid to the linkages between the theories, with fertile areas for future research identified.
Reflections on the dimensions of trust and trustworthiness among online consumers
Authors: Gefen David
Published: October 2004

Trust is emerging as a potentially central aspect leading to IT acceptance. It is especially needed in the case of gaining and later retaining consumers of online vendors. This has been shown by previous research using single dimensional constructs. But trust can also be viewed as a multi-dimensional construct combining specific beliefs (sometimes labeled as trustworthiness) that either directly or through an overall assessment of trust influence relevant behavioral intentions. To show the need to examine trust in a multi-dimensional perspective, this study proposes a three-dimensional scale of trustworthiness dealing with integrity, benevolence, and ability in the unique case of online consumer trust, and then shows the importance of examining the effects of each dimension individually. The data show that trustworthiness and trust should not be regarded as a single construct with a single effect. Rather, different beliefs influence different consumer activity intentions. Window-shopping intentions was affected by the ability-trustworthiness of the vendor, while overall trust in the vendor and its integrity-trustworthiness affected purchase intentions. The importance of differentiating among online customer activities and what dimensions of trustworthiness affect each is discussed.
CODASYS
Authors: Antony Solomon R. , Batra Dinesh
Published: October 2004

The paper describes the main features of a prototype tool CODASYS (COnceptual modeling tool for DAtabase SYStems), which purports to help novice designers engaged in conceptual data modeling. It is well known that conceptual data modeling is an error-prone process for novice database designers. The tool assists a designer in developing an entity-relationship diagram that can be translated to a normalized relational representation, free of derived dependencies. We first discuss a set of requirements for the tool that is based on achieving normal forms, on preventing data modeling errors, and on a theoretical foundation. We then discuss how the tool achieves the four normal forms and prevents common database errors such as incorrect degree, incorrect connectivity, and derived relationships. Further, we provide a cognitive framework for understanding novice error behavior and elaborate on how CODASYS addresses cognitive strain in database design. Next, we present the features of the tool and, with the help of flowcharts, discuss how these features have been implemented using a rule-based approach. It may be noted that empirical studies have been conducted to test the efficacy of the tool and have indicated significant improvement in novice designer performance.
Counting the number of active flows on a high speed link
Authors: Estan Cristian , Varghese George , Fisk Mike
Published: October 2004

Internet links operate at high speeds, and past trends predict that these speeds will continue to increase rapidly. Routers and Intrusion Detection Systems that operate at up to OC-768 speeds (40 Gigabits/second) are currently being developed. In this paper we address a basic function common to several security and measurement applications running at line speeds:
counting the number of distinct header patterns (flows) seen on a high speed link in a specified time period.
For example one can detect port scans by counting the number of connections opened by the suspected port scanner and one can ascertain that a denial of service attack is in progress by counting the number of distinct (fake) source addresses that send packets to the suspected victim. We provide algorithms solving the flow counting problem using extremely small amounts of memory. This can translate into savings of scarce fast memory (SRAM) for hardware implementations. It can also help systems that use cheaper DRAM to allow them to scale to larger instances of the problem. The reduction in memory is particularly important for network security applications such as detecting port scans and DoS attacks that need to run a separate instance of the algorithm for each suspected attacker or victim. Our algorithms can be implemented in hardware at wire speeds (8 nsec per packet for OC-768) using simple CRC based hash functions, multiplexers and SRAM. They access at most one or two memory locations per packet. We expose the behavior of simple building blocks and provide a family of
customizable
counting algorithms that can be adapted to the requirements of various applications. This allows our algorithms to use less memory than the best known counting algorithm, probabilistic counting, to provide the same accuracy.• Virtual bitmap is well suited for triggers (which need only be accurate around a threshold value) such as detecting DoS attacks, and uses 292 bytes to achieve an error of 2.619% compared to 5,200 bytes for probabilistic counting.• Our "no assumptions" counting algorithm,
multiresolution bitmap
algorithms uses only 2143 bytes to count up to 100 million flows with an average error of 3%. Its accuracy is slightly better when the number of flows is small, while the accuracy of probabilistic counting using the same memory is much worse.• Our
adaptive bitmap
that exploits stationarity in the number of flows can count the number of distinct flows on a link that contains anywhere from 0 to 100 million flows with an average error of less than 1 % using only 2 Kbytes of memory. Probabilistic counting needs eight times more memory to achieve the same accuracy.• We used our
triggered bitmap
to replace the port scan detection component of the popular intrusion detection system Snort. Doing so reduced the memory usage from 89 Mbytes to 6.4 Mbytes (with an average error of 13.5%) as measured on a 10 minute trace. Probabilistic counting uses 23 Mbytes.This work was made possible by a grant from NIST for the Sensilla Project.
STAR
Authors: Lui King-Shan , Lee Whay Chiou , Nahrstedt Klara
Published: October 2004

With increasing demand for multimedia applications, local area network (LAN) technologies are rapidly being upgraded to provide support for quality of service (QoS). In a network that consists of an interconnection of multiple LANs via bridges, the QoS of a flow depends on the length of an end-to-end forwarding path. In the IEEE 802.1D standard for bridges, a spanning tree is built among the bridges for loop-free frame forwarding. Albeit simple, this approach does not support all-pair shortest paths. In this paper, we present a novel bridge protocol, the Spanning Tree Alternate Routing (STAR) Bridge Protocol, that attempts to find and forward frames over alternate paths that are provably shorter than their corresponding tree paths. Being backward compatible to IEEE 802.1D, our bridge protocol allows cost-effective performance enhancement of an existing extended LAN by incrementally replacing a few bridges in the extended LAN by the new STAR bridges. We develop a strategy to ascertain bridge locations for maximum performance gain. Our study shows that we can significantly improve the end-to-end performance when deploying our bridge protocol.
Controlling high bandwidth aggregates in the network
Authors: Mahajan Ratul , Bellovin Steven M. , Floyd Sally , Ioannidis John , Paxson Vern , Shenker Scott
Published: October 2004

The current Internet infrastructure has very few built-in protection mechanisms, and is therefore vulnerable to attacks and failures. In particular, recent events have illustrated the Internet's vulnerability to both denial of service (DoS) attacks and flash crowds in which one or more links in the network (or servers at the edge of the network) become severely congested. In both DoS attacks and flash crowds the congestion is due neither to a single flow, nor to a general increase in traffic, but to a well-defined subset of the traffic --- an
aggregate
. This paper proposes mechanisms for detecting and controlling such high bandwidth aggregates. Our design involves both a local mechanism for detecting and controlling an aggregate at a single router, and a cooperative
pushback
mechanism in which a router can ask upstream routers to control an aggregate. While certainly not a panacea, these mechanisms could provide some needed relief from flash crowds and flooding-style DoS attacks. The presentation in this paper is a first step towards a more rigorous evaluation of these mechanisms.
Passive estimation of TCP round-trip times
Authors: Jiang Hao , Dovrolis Constantinos
Published: October 2004

We propose and evaluate a passive measurement methodology that estimates the distribution of Round-Trip Times (RTTs) for the TCP connections that flow through a network link. Such an RTT distribution is important in buffer provisioning, configuration of active queue management, and detection of congestion unresponsive traffic. The proposed methodology is based on two techniques. The first technique is applicable to TCP caller-to-callee flows, and it is based on the 3-way handshake messages. The second technique is applicable to callee-to-caller flows, when the callee transfers a number of MSS segments to the caller, and it is based on the slow-start phase of TCP. The complete estimation algorithm reports an RTT for 55-85% of the TCP workload, in terms of bytes, in the traces that we examined. Verification experiments show that about 90% of the passive measurements are within 10% or 5ms, whichever is larger, of the RTT that
ping
would measure. Also, measurements on several NLANR traces show that the two estimation techniques agree within 25ms for 70-80% of the processed TCP connections. We also apply the estimation methodology on a number of NLANR traces and examine the variability of the measured RTT distributions in both short and long timescales.
Distributed computing research issues in grid computing
Authors: Casanova Henri
Published: October 2004

Ensembles of distributed, heterogeneous resources, or
Computational Grids,
have emerged as popular platforms for deploying large-scale and resource-intensive applications. Large collaborative efforts are currently underway to provide the necessary software infrastructure.
Grid computing
raises challenging issues in many areas of computer science, and especially in the area of
distributed computing,
as Computational Grids cover increasingly large networks and span many organizations. In this paper we briefly motivate Grid computing and introduce its basic concepts. We then highlight a number of distributed computing research questions, and discuss both the relevance and the short-comings of previous research results when applied to Grid computing. We choose to focus on issues concerning the dissemination and retrieval of information and data on Computational Grid platforms. We feel that these issues are particularly critical at this time, and as we can point to preliminary ideas, work, and results in the Grid community and the distributed computing community. This paper is of interest to distributing computing researchers because Grid computing provides new challenges that need to be addressed, as well as actual platforms for experimentation and research.
Data mining aided signature discovery in network-based intrusion detection system
Authors: Han Hong , Lu Xian Liang , Lu Jun , Bo Chen , Yong Ren Li
Published: October 2004

In Network-based Intrusion Detection, signatures discovery is an important issue, since the performance of an intrusion detection system heavily depends on accuracy and abundance of signatures. In most cases, we have to find these signatures manually. This is a time-consuming and error-prone work. Some papers introduce data mining into Intrusion Detection System. However, there are some drawbacks in these schemes. We present a data mining based approach to supporting signature discovery in network-based Intrusion Detection System. It has people find signatures of an intrusion easily. The main idea is that: First, Signature Discovery System (SDS) tries to find the most possible signatures that occur very frequently in the communication monitored. Second, SDS will find the relationships between these candidate signatures and construct rules based on these relationships found. Finally, SDS gives two kinds of hints: one is the signatures whose frequency of occurrence is greater than a threshold; the other is a set of rules composed of a set of signatures that are created by SDS in the second step. An experimental system called SigSniffer has been implemented to test the feasibility of the proposed approach.
A distributed persistent object store for scalable service
Authors: Jin Chao , Zheng Weimin , Zhou Feng , Wu Yinghui
Published: October 2004

This paper presents a distributed persistent object store designed to simplify scalable service in cluster environment. This distributed object store, called TODS (Tsinghua Object Data Store), presents a single-imaged, transparent persistent and object-oriented view of the storage devices of the whole cluster. TODS is designed to be incremental scalable and efficient, and also has the properties of the high concurrency, high throughput and availability which are necessary for scalable service. TODS supports distributed ACID transactions within the cluster, which qualifies its use in the building of complex transactional services. And the user interface of TODS is fitter for building service than that of file system, and significantly easier to use than that of RDBMS. TODS is a reusable platform for scalable service in cluster by forming many general data management functions into one independent layer. This paper gives the motivation, principle and architecture of TODS. Some technique details are also discussed. In our performance experiments, the system scales smoothly to a 36-node server cluster and achieves 11,160 In-memory reads/sec and 396 transactions/sec.
User experiences with the Aonix ObjectAda RAVEN
Authors: Brach David , Eng P.
Published: October 2004

CMC Electronics Inc. has gained experience using the Ravenscar Profile by developing avionics software using the Aonix ObjectAda RAVEN toolset. The Aonix toolset was selected by CMC Electronics for several reasons including familiarity with the product family, the well-known IDE, the small kernel footprint, the claimed Ravenscar Profile compatibility (at the time of evaluation the only claimant) and the certifiability option. The Aonix toolset met all our criteria for an avionics software development toolset. From our development experience certain conclusions with respect to the Ravenscar Profile and Aonix toolset have been reached, which will be expressed herein.
Precise response time analysis for Ravenscar kernels
Authors: Zamorano Juan , de la Puente Juan Antonio
Published: October 2004

The Ravenscar Profile defines a subset of the Ada95 tasking constructs which can be implemented using a small, reliable kernel. One of the benefits of this approach is to improve the timing analysis because non-deterministic and non-analyzable features are excluded. But to perform a precise schedulability analysis of a Ravenscar compliant application, the kernel overheads must be taken into account. Therefore, a set of metrics and documentation requirements has to be defined in order to model the kernel influence in response time analysis. In this paper the main components of the response time of periodic and sporadic tasks running on a Ravenscar kernel are identified, and the set of kernel metrics which are required to perform a precise timing analysis is identified.
Application-defined scheduling in Ada
Authors: Rivas Mario Aldea , Harbour Michael González
Published: October 2004

This paper presents an application program interface (API) that enables Ada applications to use application-defined scheduling algorithms in a way compatible with the scheduling model of the Ada 95 Real-Time Systems Annex. Several application-defined schedulers, implemented as special user tasks, can coexist in the system in a predictable way. This API is currently implemented on our operating system MaRTE OS.
Developing e-commerce in internetworked organizations
Authors: Henfridsson Ola , Holmström Helena
Published: October 2004

Many computer game developers have adopted network technologies for value-adding purposes at several stages of the corporate value chain. In this paper, we suggest that this adoption extends the current notion of developing e-commerce by including ongoing interaction with the consumers concerning what is being produced. On the basis of an interpretive case study, this paper outlines the process by which a Swedish computer game developer involved its customers in producing, testing, distributing, and marketing its online computer game Clusterball. Using Orlikowski's (1999) notion of "internetworked organizations", the paper explores how this customer involvement was supported by the use of network technologies at every stage of the value chain, and it illustrates how this involvement can be understood as an important feature of future development of e-commerce in organizations.
Interrupts and Ada
Authors: Hunt J. R.
Published: October 2004

This paper discusses the issues involved in servicing interrupts in Ada, with reference to the mechanisms in (Refs. 1 and 2), and concludes that it can be done efficiently and reliably, but that some form of asynchronous communication is needed, and that this is best done explicitly using an additional run time system interface.
Asynchronous transfer of control in Ada
Authors: Toetenel W. J. , van Katwijk J.
Published: October 2004

Rapid event driven mode shifts and certain kinds of error recovery require a task asynchronously to affect the flow of control of another task in ways that cannot be conveniently achieved by abort alone….
Communication between Ada programs in DIADEM
Authors: Atkinson C. , Goldsack S. J.
Published: October 2004

It has been recognized for some time that Ada is not well designed for the purpose of programming networks of loosely-coupled processors, and numerous projects have been set up to find a solution. The DIADEM project had the particular goal of constructing flexible Ada programs that could be executed in a range of distributed systems, including, as a limiting case, a centralized uniprocessor. To this end a technique was developed by which the Ada rendezvous could be used as a remote communication mechanism, supported in a highly portable way on a range of different network architectures and communication systems. This was achieved by the definition of a special package providing a “standard interface” to the transport layer services of the host communication system. After outlining the basic principles of the DIADEM approach, and describing the first prototype implementation of the communication mechanism, this paper discusses how a standard interface similar to that used in DIADEM could provide an efficient, yet portable, technique for supporting remote communication in time-critical (hard) real-time, distributed systems.
Supporting Ada in a distributed environment
Authors: Hutcheon A. D. , Wellings A. J.
Published: October 2004

This paper describes a set of tools which support a pre-partitioning approach to programming distributed systems in Ada. It also considers how these tools can be modified to support fault-tolerant applications.
Efficient encoding of application layer PDU's for fieldbus networks
Authors: Pimentel J. R.
Published: October 2004

A new and efficient encoder suitable for encoding application layer PDU's is suggested. Because of its good efficiency, it is particularly useful for fieldbus networks where real time behaviour is a major requirement. The encoder is able to work with ASN. 1 syntax rules and produces a new transfer syntax which can be negotiated with the ISO presentation layer. The overhead length required by the new encoder is at least half of that required by ASN. 1 encoding. Several examples using MMS protocol data units demonstrate the enhanced features of the new encoder.
The IC model of parallel computation and programming environment
Authors: Cameron E. J. , Cohen D. M. , Gopinath B. , Keese W. M. , Ness L. , Uppaluru P. , Vollaro J. R.
Published: October 2004

The IC* project is an effort to create an environment for the design, specification and development of complex systems such as communication protocols, parallel machines and distributed systems. The basis of this work is the IC* model of parallel computation. In this model a system is specified by a set of invariant expressions which describe its behavior in time. The novel features of the model include: temporal and structural constraints, inherent parallelism, explicit modeling of time, nondeterministic evolution and dynamic activation. The project also includes the construction of a parallel computer specifically designed to support the model of computation. The model of computation, the status of the project and the user environment is the content of this paper.
Transactional lock-free execution of lock-based programs
Authors: Rajwar Ravi , Goodman James R.
Published: October 2004

This paper is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multi-threaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access to shared data. To ensure correctness programmers often rely on conservative locking at the expense of performance. The resulting serialization of threads is a performance bottleneck. Locks also interact poorly with thread scheduling and faults, resulting in poor system performance.We seek to improve multithreaded programming trade-offs by providing architectural support for optimistic lock-free execution. In a lock-free execution, shared objects are never locked when accessed by various threads. We propose
Transactional Lock Removal
(TLR) and show how a program that uses lock-based synchronization can be executed by the hardware in a lock-free manner, even in the presence of conflicts, without programmer support or software changes. TLR uses timestamps for conflict resolution, modest hardware, and features already present in many modern computer systems.TLR's benefits include improved programmability, stability, and performance. Programmers can obtain benefits of lock-free data structures, such as non-blocking behavior and wait-freedom, while using lock-protected critical sections for writing programs.
Temporally silent stores
Authors: Lepak Kevin M. , Lipasti Mikko H.
Published: October 2004

Recent work has shown that silent stores--stores which write a value matching the one already stored at the memory location--occur quite frequently and can be exploited to reduce memory traffic and improve performance. This paper extends the definition of silent stores to encompass sets of stores that change the value stored at a memory location, but only temporarily, and subsequently return a previous value of interest to the memory location. The stores that cause the value to revert are called temporally silent stores. We redefine multiprocessor sharing to account for temporal silence and show that in the limit, up to 45% of communication misses in scientific and commercial applications can be eliminated by exploiting values that change only temporarily. We describe a practical mechanism that detects temporally silent stores and removes the coherence traffic they cause in conventional multiprocessors. We find that up to 42% of communication misses can be eliminated with a simple extension to the MESI protocol. Further, we examine application and operating system code to provide insight into the temporal silence phenomenon and characterize temporal silence by examining value frequencies and dynamic instruction distances between temporally silent pairs. These studies indicate that the operating system is involved heavily in temporal silence, in both commercial and scientific workloads, and that while detectable synchronization primitives provide substantial contributions, significant opportunity exists outside these references.
Cool-Mem
Authors: Ashok Raksit , Chheda Saurabh , Moritz Csaba Andras
Published: October 2004

This paper presents Cool-Mem, a family of memory system architectures that integrate conventional memory system mechanisms, energy-aware address translation, and compiler-enabled cache disambiguation techniques, to reduce energy consumption in general purpose architectures. It combines statically speculative cache access modes, a dynamic CAM based Tag-Cache used as backup for statically mispredicted accesses, various conventional multi-level associative cache organizations, embedded protection checking along all cache access mechanisms, as well as architectural organizations to reduce the power consumed by address translation in virtual memory. Because it is based on speculative static information, the approach removes the burden of provable correctness in compiler analysis passes that extract static information. This makes Cool-Mem applicable for large and complex applications, without having any limitations due to complexity issues in the compiler passes or the presence of precompiled static libraries. Based on extensive evaluation, for both SPEC2000 and Mediabench applications, 12% to 20% total energy savings are obtained in the processor, with performance ranging from 1.2% degradation to 8% improvement, for the applications studied.
Compiler optimization of scalar value communication between speculative threads
Authors: Zhai Antonia , Colohan Christopher B. , Steffan J. Gregory , Mowry Todd C.
Published: October 2004

While there have been many recent proposals for hardware that supports
Thread-Level Speculation
(TLS), there has been relatively little work on compiler optimizations to fully exploit this potential for parallelizing programs optimistically. In this paper, we focus on one important limitation of program performance under TLS, which is stalls due to forwarding scalar values between threads that would otherwise cause frequent data dependences. We present and evaluate dataflow algorithms for three increasingly-aggressive instruction scheduling techniques that reduce the
critical forwarding path
introduced by the synchronization associated with this data forwarding. In addition, we contrast our compiler techniques with related hardware-only approaches. With our most aggressive compiler and hardware techniques, we improve performance under TLS by 6.2-28.5% for 6 of 14 applications, and by at least 2.7% for half of the other applications.