Search

An alternator is a network of concurrent nodes, which satisfies the following conditions: (i) if one node enters its critical section, no neighboring nodes could enter their critical sections at the same computing phase; (ii) along any infinite computing phases, each node enters its critical section infinitely often. An alternator is said to exhibit strong fairness if condition (ii) is changed to: between any two consecutive critical steps of a node, all neighbors enter their critical sections exactly once. In this paper, we propose a state-optimal alternator algorithm for uniform rings with n nodes, where n is any positive integer greater than one. The proposed algorithm operates correctly for synchronous mode. Every node maintains only a two-state variable. The proposed algorithm has the snap property that the system always satisfies condition (i) of the alternator even if some transient fault occurs. The stabilization time of the proposed alternator algorithm is O(n) phases. After stabilization, the system satisfies the strong fairness property and achieves the maximal performance. We say that an alternator achieves the maximal performance if a node is allowed to enter its critical section when both its neighbors do not enter their critical sections. In the worst case, the proposed algorithm allows each node to enter its critical section every three phases. [ABSTRACT FROM AUTHOR]

Distributed storage systems that deploy erasure codes can provide better features such as lower storage overhead and higher data reliability. In this paper, we focus on fractional repetition (FR) codes, which are a class of storage codes characterized by the features of uncoded exact repair and minimum repair bandwidth. We study the duality of FR codes and investigate the relationship between the supported file size of an FR code and its dual code. Based on the established relationship, we derive an improved dual bound on the supported file size of FR codes. We further show that FR codes constructed from t -designs are optimal when the size of the stored file is sufficiently large. Moreover, we present the tensor product technique for combining FR codes and elaborate on the file size hierarchy of resulting codes. [ABSTRACT FROM AUTHOR]

In this paper, the performance of a grid resource is modeled and evaluated using stochastic reward nets (SRNs), wherein the failure–repair behavior of its processors is taken into account. The proposed SRN is used to compute the blocking probability and service time of a resource for two different types of tasks: grid and local tasks. After modeling a grid resource and evaluating the performability measures, an algorithm is presented to find the probability mass function (pmf) of the service time of the grid resource for a program which is composed of grid tasks. The proposed algorithm exploits the universal generating function to find the pmf of service time of a single grid resource for a given program. Therefore, it can be used to compute the pmf of the service time of entire grid environment for a workflow with several dependent programs. Each possible scheduling of programs on grid resources may result in different service times and successful execution probabilities. Due to this fact, a genetic-based scheduling algorithm is proposed to appropriately dispatch programs of a workflow application to the resources distributed within a grid computing environment. Numerical results obtained by applying the proposed SRN model, the algorithm to find the pmf of grid service time, and the genetic-based scheduling algorithm to a comprehensive case study demonstrate the applicability of the proposed approach to real systems. [ABSTRACT FROM AUTHOR]

The analysis of a queue that serves batches of customers with a novel service policy is presented in this paper, showing that a closed steady-state distribution of the number of customers in the queue can be derived for a very general setting of its parameters. Two output processes are flowing out of this queue depending on the fact that single customers are removed from the queue upon completion of a service, or bulks of customers of a fixed size are departing from the queue at the completion of the service's. Based on the expression of the steady-state distribution which assumes a Poisson arrival process, specific parameter configurations are identified that make the queue quasi-reversible, depending on the output process of interest. Since quasi-reversible queues are very important in the context of product form queueing networks, these results have relevant impacts on their own as well as when considered as the basis for possible computationally efficient approximations. Comparisons among the results obtained for different parameter settings are provided using both stochastic order arguments and numerical experiments. Future research directions are proposed considering also the many practical applications of this model ranging from flexible manufacturing, to logistics, to transportation systems. [ABSTRACT FROM PUBLISHER]

Rapid, reliable and energy-efficient programing code dissemination is a challenging issue and offers a programmable and flexible network architecture for software-defined wireless networks (SDWNs). However, many schemes for programing codes in large-scale network incur a longer dissemination convergence time (DCT) and lower energy efficient in loss nature of wireless channels. In this paper, an adaptive broadcast dissemination (ABD) scheme is proposed to achieve low DCT and high network lifetime for SDWNs. An ABD scheme makes full use of energy left of nodes in areas far from the sink. In an ABD scheme, codes are broadcast constantly few times by nodes near the sink to save energy, and many times by nodes in areas far from the sink to rapidly spread software codes. Thus, an ABD scheme can reduce transmission delay for spreading software code while retaining network lifetime. Theoretical analysis and experimental results show that DCT in an ABD scheme is reduced by 28.12-29.86% compared with the hybrid scheme, while retaining network lifetime. [ABSTRACT FROM AUTHOR]

Graph is an increasingly popular way to model complex data, and the size of single graphs is growing toward massive. Nonetheless, executing graph algorithms efficiently and at scale is surprisingly challenging. As a consequence, distributed programming frameworks have emerged to empower large graph processing. Pregel, as a popular computational model for processing billion-vertex graphs, has been employed to improve the scalability of many algorithms. In this paper, we investigate frequent subgraph mining on single large graphs using Pregel.We present the first distributed algorithm based on Pregel for single massive graphs. In addition, two optimizations are proposed to enhance the algorithm, reducing communication cost and distribution overhead. Extensive experiments conducted on real-life data confirm the effectiveness and efficiency of the proposed algorithm and techniques. [ABSTRACT FROM AUTHOR]

This paper studies the performance characteristics of computational fluid dynamics (CFD) applications on Intel Many Integrated Core (MIC) architecture. Three CFD applications, BT-MZ, LM3D and HOSTA, are evaluated on Intel Knights Corner (KNC) coprocessor, the first public MIC product. The results show that the pure OpenMP scalability of these applications is not sufficient to utilize the potential of a KNC coprocessor. While utilizing the hybrid MPI/OpenMP programming model helps to improve the parallel scalability, the maximum parallel speedup relative to a single thread is still not satisfactory. The OpenCL version of BT-MZ performs better than the OpenMP version but is not comparable to the MPI version and the hybrid MPI/OpenMP version. At the micro-architecture level, while the three CFD applications achieve reasonable instruction execution rates and L1 data cache hit rates, use a large percent of vector instructions, they have low arithmetic density, incur very high branch misprediction rates and do not utilize the Vector Processing Unit efficiently. As a result, they achieve very low single thread floating-point efficiency. For these applications to attain competitive performance on the MIC architecture as on the Xeon processors, both the parallel scalability and the single thread performance should be improved, which is a difficult task. [ABSTRACT FROM AUTHOR]

Dynamic voltage scaling (DVS), which adjusts the clock frequency and supply voltage based on the workload of systems, has been adopted in many computing systems to reduce the energy consumption of the processor. In this paper, we address the problem of minimizing overall energy consumption of a sporadic task in real-time system with a shared set of serially reusable, single unit resources, considering a generalized power model. We first present a static scheduling algorithm, called SSTSASR, which minimizes the system energy consumption of a given set of sporadic tasks and takes the off-chip workload into consideration, assuming that each task releases with the worstcase workload. In addition, we present dynamic slack reclamation techniques, called DSTSASR, which reclaims the slack time from the early completion task to reduce the energy consumption and takes the speed transition overhead into consideration. The simulation results show that the proposed DSTSASR algorithm could achieve a significant amount of energy savings compared with other DVS algorithms. It can reduce the energy consumption by 7.37-31.99% over the DVSSR and by 0.1-5.90% over the SSTSASR. [ABSTRACT FROM AUTHOR]

This paper presents an analysis of the energy consumption of an extensive number of the optimizations a modern compiler can perform. Using GCC as a test case, we evaluate a set of 10 carefully selected benchmarks for 5 different embedded platforms. A fractional factorial design is used to systematically explore the large optimization space (282 possible combinations), while still accurately determining the effects of optimizations and optimization combinations. Hardware power measurements on each platform are taken to ensure all architectural effects on the energy consumption are captured. We show that fractional factorial design can find more optimal combinations than relying on built-in compiler settings. We explore the relationship between run-time and energy consumption, and identify scenarios where they are and are not correlated. A further conclusion of this study is the structure of the benchmark has a larger effect than the hardware architecture on whether the optimization will be effective, and that no single optimization is universally beneficial for execution time or energy consumption. [ABSTRACT FROM PUBLISHER]

This work is primarily inspired by the observation that supervisory control and regulated rewriting have the same nature. Indeed, both of them model a system using some formalism and use a certain formalized control structure to restrict the behavior of the system via some designated control mechanisms. In this paper, we propose the theory of Control Systems (C Systems), which provides a more generic framework to integrate the automaton and grammar representations of control in supervisory control and regulated rewriting. The C system contains two components: the controlled component and the controlling component. The two components are expressed using the same formalism, e.g. automata or grammars. More specifically, we define three types of control systems based on the automaton or grammar representation, namely Automaton Control Systems (AC Systems), Grammar Control Systems (GC Systems) and Leftmost-derivation-based Grammar Control Systems (LGC Systems). We formally study their key theoretical characterizations, such as generative power, equivalence and translation techniques, as well as their connections with supervisory control and regulated rewriting, including the relationships between AC systems and supervisory control, and between GC/LGC systems and regulated rewriting. We also discuss some applications of C systems and finally propose some open questions. [ABSTRACT FROM PUBLISHER]

There are two types of dynamic elements in a pervasive system: the first is where a context varies with shifting environments, and the second is where variables are defined by the dynamic requirements of an application. This makes improving adaptability to dynamic change an important topic in pervasive systems research. Currently, most of the efforts targeting improvements in adaptability focus on context-related issues, other variables being simply encoded in the program directly. This ignores the dynamic complexity of a pervasive system, resulting in poor system adaptability. In this paper, we propose a rule-based method in which the two types of change are separated from the program code. The changes are then stored and processed by means of corresponding rules. In our new method when a change occurs, the system needs only to modify the rules rather than the program code. This makes a pervasive system more robust in its adaptability to dynamic change. Experiments and examples are provided to evaluate the feasibility of the proposed method. [ABSTRACT FROM PUBLISHER]

This paper develops a new theory and model for information and sensor validation. The model represents relationships between variables using Bayesian networks and utilizes probabilistic propagation to estimate the expected values of variables. If the estimated value of a variable differs from the actual value, an apparent fault is detected. The fault is only apparent since it may be that the estimated value is itself based on faulty data. The theory extends our understanding of when it is possible to isolate real faults from potential faults and supports the development of an algorithm that is capable of isolating real faults without deferring the problem to the use of expert provided domain-specific rules. To enable practical adoption for real-time processes, an any time version of the algorithm is developed, that, unlike most other algorithms, is capable of returning improving assessments of the validity of the sensors as it accumulates more evidence with time. The developed model is tested by applying it to the validation of temperature sensors during the start-up phase of a gas turbine when conditions are not stable; a problem that is known to be challenging. The paper concludes with a discussion of the practical applicability and scalability of the model. [ABSTRACT FROM AUTHOR]

This paper examines the limitations of Turing Machines as a complete model of computation, and presents several models that extend Turing Machines. Dynamic interaction of clients and servers on the Internet, an infinite adaptation from evolutionary computation, and robots sensing and acting are some examples of areas that cannot be properly described using Turing Machines and algorithms. They require new models of computation going beyond Turing Machines. We refer to such new models as superTuring models of computation. Three superTuring models of computation, namely Interaction Machines, the π calculus and the $-calculus are presented and explained, focussing on why they are better for the solution of computational problems. We expect that superTuring computation will become the central programming paradigm in the future. [ABSTRACT FROM AUTHOR]

Symbolic transition systems separate data from process behaviour by allowing the data to be uninstantiated. Designing an HML-like modal logic for these transition systems is interesting because of the subtle interplay between the quantifiers for the data and the modal operators (quantifiers on transitions). This paper presents the syntax and semantics of such a logic and discusses the design issues involved in its construction. The logic has been shown to be adequate with respect to strong early bisimulation over symbolic transition systems derived from Full LOTOS. We define what is meant by adequacy and discuss how we can reason about it with the aid of a mechanized theorem prover. [ABSTRACT FROM PUBLISHER]

This paper describes an algorithm and associated tool for checking a network of communicating processes, defined using the algebraic language of CSP, against a set-theoretic specification, expressed in terms of event traces and refusal sets. [ABSTRACT FROM PUBLISHER]

The ability to predict the directions of branches, especially conditional branches, is an important problem in modern computer architecture and advanced compilers. Many static and dynamic techniques have been proposed. Today, all state-of-the-art microprocessors have some form of hardware support for dynamic branch prediction. Static techniques, on the other hand, have not been widely studied because of the belief that they give poorer results. However, good static branch predictions are invaluable information for (static) compiler optimization or performance estimation. In this paper, we propose performing static branch prediction at the source code level. The assumption is that the source code contains information unavailable at the assembly or machine code level that may be used for branch prediction. Empirical studies on 14 integer Spec benchmarks indicate that the simple heuristics proposed can be effective in practice. [ABSTRACT FROM PUBLISHER]

Distributed programs often follow some bounded global predicates, for example, the total number of certain tokens is always the same or bounded in a range. In order to detect bounded global predicates, we can first derive the minimum and maximum global snapshots and then check if the minimum and maximum are out of the range. Recently, Chase and Garg proposed an efficient method to derive the minimum global snapshot by reducing this problem to a maximum network flow problem. A restriction of this method is that all message values (e.g., the token number in messages) must be zero and all process state values (e.g., the token number in processes) must be non-negative. In this paper, we propose an elegant technique, called normalization. By using this technique, we can remove the above restriction and also derive the minimum and maximum global snapshots at the same time. [ABSTRACT FROM AUTHOR]

ALGOL was formulated in Zurich in 1958, and this paper explores some of the reasons why this happened in Zurich and not in the USA. One factor may have been that the first computer on the continent, the Z4, was installed in Zurich in 1950. This computer was built by Zuse during the Second World War. It used relays for its arithmetic and control units, but it had a mechanical memory. Though the machine had limited capabilities, it provided valuable programming experience to a number of researchers, in particular to Stiefel, Rutishauser and Speiser at the ETH Zurich. Already in 1952, Rutishauser formulated a higher programming construct, a counted loop, and he also indicated how to convert mathematical expressions into machine language. We also should mention that Bauer, who was influenced by Rutishauser, also developed a method to implement mathematical expressions, but he used computer hardware for the task. The two started to collaborate, and they formulated a preliminary language in 1957. This language was then formalized at a ACM/GAMM meeting in Zurich under the name International Algebraic Language, or IAL, a language later renamed ALGOL 58. [ABSTRACT FROM PUBLISHER]

Dynamically typed languages are becoming increasingly popular for different software development scenarios such as Web engineering, rapid prototyping or the construction of applications that require runtime adaptiveness. In contrast, statically typed languages have undeniable advantages such as early type error detection and more opportunities for compiler optimizations. Since both approaches offer different benefits, hybrid statically and dynamically typed programming languages have emerged, and some statically typed languages have also incorporated dynamic typing capabilities. In this paper, we present the minimal core of StaDyn, a hybrid typing language that performs static type inference of both statically and dynamically typed references. The type information gathered by the compiler is used to generate efficient .NET code, obtaining a significant runtime performance improvement compared with C# 4.0 and Visual Basic 10. [ABSTRACT FROM AUTHOR]

Wireless sensor networks (WSNs) are emerging as powerful platforms for distributed embedded computing supporting a variety of high-impact applications. However, programming WSN applications is a complex task that requires suitable paradigms and technologies capable of supporting the specific characteristics of such networks which uniquely integrate distributed sensing, computation and communication. Mobile agents are a distributed computing paradigm based on code mobility that has already demonstrated high effectiveness and efficiency in IP-based highly dynamic distributed environments. Due to their intrinsic characteristics, mobile agents may provide more benefits in the context of WSNs than in conventional distributed environments. In this paper we present the design, implementation and experimentation of MAPS (Mobile Agent Platform for Sun SPOT), an innovative Java-based framework for wireless sensor networks based on Sun SPOT technology which enables agent-oriented programming of WSN applications. The MAPS architecture is based on components that interact through events. Each component offers a minimal set of services to mobile agents that are modeled as multi-plane state machines driven by ECA rules. In particular, the offered services include message transmission, agent creation, agent cloning, agent migration, timer handling and easy access to the sensor node resources (sensors, actuators, input switches, flash memory and battery). Agent programming with MAPS is presented through both a simple example related to mobile agent-based monitoring of a sensor node and a more complex case study for real-time human activity monitoring based on wireless body sensor networks. Moreover, a performance evaluation of MAPS carried out by computing micro-benchmarks, related to agent communication, creation and migration, is illustrated. [ABSTRACT FROM AUTHOR]

As network speeds continue to increase, so does the need for scalable pattern matching for deep packet scanning applications such as signature-based network intrusion detection. Multiple-stride deterministic finite automaton (DFA) increases the performance of pattern matching, because they allow multiple bytes of a packet to be scanned simultaneously. However, traditional multiple-stride DFA either rely on specific hardware for parallel comparison or have a huge memory requirements due to state explosion. In this paper, we present a high throughput, multiple-stride pattern-matching architecture that requires a small storage cost and no specific hardware. The basic idea is to group DFA states/transitions into three coarse-grained and variable-size blocks, so that each individual block can employ different-specific methods to optimize storage requirements and performance. The blocks are naturally identified based on basic observations of DFA characteristics: prefix, linear trie and state dependencies. The performance evaluation is done using the Snort pattern sets. We show that multi-byte striding DFA achieves multi Gb/s pure content inspection in software, while utilizing <3 bytes per pattern character. [ABSTRACT FROM AUTHOR]

The paper proposes a simple protocol that ensures sequential consistency. The protocol assumes that the shared memory abstraction is supported by the local memories of nodes that can communicate only by exchanging messages through reliable channels. Unlike other sequential consistency protocols, the one proposed here does not rely on a strong synchronization mechanism, such as an atomic broadcast primitive or a central node managing a copy of every shared object. From a methodological point of view, the protocol is built incrementally starting from the very definition of sequential consistency. It has the noteworthy property that a process that issues a write operation never has to wait for other processes. Depending on the current local state, most read operations issued also have the same property. [ABSTRACT FROM PUBLISHER]

This paper is dedicated to the connection, by a provider, of multiple groups of nodes spread over a network. The role of the provider is to interconnect the members of every group. For this purpose, it must distribute the available links of the network between the groups. The general aim then is to allocate these links in such a way that the communications latencies in the allocated structure are equivalent to the ones in the original (full) network for each group. We study two approaches constructing structures preserving the maximum latency (called the diameter). Unfortunately we show that the associated optimization graph problems are difficult (one cannot be approximated by a constant and the other is NP-complete). Due to these difficulties we relax the constraint on the diameter and propose to construct a unique tree connecting all the groups together. We give a heuristic to treat this problem and we propose several analytical results on its maximum and average latencies performance. [ABSTRACT FROM PUBLISHER]

Data updates have become an important issue in erasure-coded in-memory stores owing to the two-fold reasons: (i) a handful of data-intensive in-memory stores adopt erasure coding for 'hot' data and (ii) small writes in update-intensive in-memory workloads cause expensive updating overheads. After delving into prior updating schemes in erasure-coded storage clusters, we investigate the applicability of these schemes to erasure-coded in-memory stores. We propose a grouped-updating mechanism— GU —to handle small writes in in-memory stores. With GU in place, requests in an updating window are categorized into several updating groups, where multiple small updates in an updating group can be concurrently executed. Two GU updating procedures— GU-stripe and GU-node —are developed to schedule updates according to a stripe and a node holding an updated data block, respectively. Furthermore, we develop two hybrid-updating schemes— H y b r i d − U [ GU - stripe ] and H y b r i d − U [ GU - node ] —to process common writes (i.e. small and large writes) initiated by the GU-stripe- and GU-node-based updating schemes, respectively. Replaying an update-heavy workload generated by YCSB benchmark, we extensively evaluate the four non-GU-based updating schemes, five GU-stripe-based updating schemes, and five GU-node-based updating schemes. Our experiments demonstrate that the GU mechanism boosts updating performance of small writes for RS-coded in-memory stores in terms of updating time and updating traffic. In particular, for a (8, 6) RS-coded in-memory store, the GU-stripe- and GU-node-based updating schemes shortens the updating time of the non-GU-based counterparts by a factor of at least 2.08 and 2.66, respectively. Compared to a single GU-based updating scheme, a GU-based hybrid updating scheme achieves an optimal updating-time and updating-traffic performance. [ABSTRACT FROM AUTHOR]

Recently, TCP SYN flood has been the most common and serious type of Distributed Denial of Service attack that causes outages of server resource of Internet Service Providers. In another aspect, Software Defined Networking (SDN) has emerged as a new networking paradigm to increase network agility and programmability. SDN is also a promising architecture to deal with the network security issue where we can flexibly change security rules and control incoming flows. In this article, we design an Openflow/SDN network remedy to combat specifically TCP SYN flood. We show security threats for the SDN architecture and exploit SDN capabilities and features to design a SDN-based SYN Proxy (SSP) paradigm to mitigate such TCP SYN threats. Our SSP is proved to be a network-based solution to protect application servers in terms of decreasing number of Half-Open Connections at an application server and increasing probability of successful establishment for a TCP flow connection under TCP SYN Flood attack. Using SSP to support application servers is shown to outperform the case where the servers adopt only the protection scheme of Microsoft Windows server reference model without utilizing SSP. SSP also shows that it can reduce the time a flow entry occupies the switch resource by 94% in comparison with the Avant-Guard solution. In addition, SSP improves the successful connection rate and average connection retrieval time in comparison with the standard Openflow solution. [ABSTRACT FROM AUTHOR]

Load-balanced scheduling deals with the uniform allocation of workload to a set of computational resources in order to optimize some characteristic metrics such as makespan, resource utilization and relative load imbalance. As such, the load balancing is an NP-hard problem which becomes more complex when heterogeneity in the workload and the computing resources are introduced. Workload heterogeneity is defined by the types of the workload whereas CPU resources can be heterogeneous in terms of memory/cache hierarchy, clock speed, etc. For load balancing in a truly heterogeneous multicore system, this work proposes a model by incorporating a related heuristic into Genetic Algorithm (GA) to generate the priorities of the workload and the computing resources by exploiting their heterogeneity characteristics. The priorities play a significant role in the effective mapping of the workload on the computing resources. A good number of simulation experiments are carried out to study the performance of the proposed model besides comparing it with some contemporary GA-based models. Results indicate that incorporating the relevant heuristic into GA makes a significant load-balanced scheduling, especially for heavy workload applications. [ABSTRACT FROM AUTHOR]

As an effective means of multi-agent problem solving, autonomous individual programming and interaction that are essential need, are limited in their ability to accommodate the interests of others, and therefore, may unnecessarily constrain the solving ability and negotiability of an agent, particularly in a distributed cooperative environments founded on private and uncertain information. In this paper, a multi-agent group programming model is presented, where each agent executes local programming by evolutionary search. Based on co-evolution idea, agents resolve conflicts and revise their own search direction to optimize local and social objectives in an interactive process by means of clustering and group choice. Finally, the paper presents simulation results that illustrate the operational effectiveness of our agent group programming model. [ABSTRACT FROM PUBLISHER]

Let G(V, E) be an undirected connected graph, where each vertex v is associated with a positive cost C(v) and each edge e = (u, v) is associated with two positive weights, W(u → v) and W(v → u). We consider a new graph problem, called the edge-orientation problem (the EOP). The major issue is to assign each edge e = (u, v) an orientation, either from u to v, denoted as u → v, or from v to u, denoted as v → u, such that maxx∈V{C(x) + Σx→z W(x → z)} is minimized. This paper first shows that the EOP is NP-hard on split graphs and planar graphs. Then, a linear-time algorithm on star graphs is proposed by the prune-and-search strategy. Finally, the algorithmic result on star graphs is extended to trees and simple cactus graphs using the dynamic programming strategy. [ABSTRACT FROM AUTHOR]

Most microprocessor chips today use an out-of-order instruction execution mechanism. This mechanism allows superscalar processors to extract reasonably high levels of instruction level parallelism (ILP). The most significant problem with this approach is a large instruction window and the logic to support instruction issue from it. This includes generating wake-up signals to waiting instructions and a selection mechanism for issuing them. Wide-issue width also requires a large multi-ported register file, so that each instruction can read and write its operands simultaneously. Neither structure scales well with issue width leading to poor performance relative to the gates used. Furthermore, to obtain this ILP, the execution of instructions must proceed speculatively. An alternative, which avoids this complexity in instruction issue and eliminates speculative execution, is the microthreaded model. This model fragments sequential code at compile time and executes the fragments out of order while maintaining in-order execution within the fragments. The only constraints on the execution of fragments are the dependencies between them, which are managed in a distributed and scalable manner using synchronizing registers. The fragments of code are called microthreads and they capture ILP and loop concurrency. Fragments can be interleaved on a single processor to give tolerance to latency in operands or distributed to many processors to achieve speedup. The implementation of this model is fully scalable. It supports distributed instruction issue and a fully scalable register file, which implements a distributed, shared-register model of communication and synchronization between multiple processors on a single chip. This paper introduces the model, compares it with current approaches and presents an analysis of some of the implementation issues. It also presents results showing scalable performance with issue width over several orders of magnitude, from the same binary code. [ABSTRACT FROM AUTHOR]

Event-based middleware is currently being applied for application component integration in a range of application domains. As a result, a variety of event services has been proposed to address different requirements. In order to aid the understanding of the relationships between these systems, this paper presents a taxonomy of distributed event-based programming systems. The taxonomy is structured as a hierarchy of the properties of a distributed event system and may be used as a framework to describe such a system according to its properties. The taxonomy identifies a set of fundamental properties of event systems and categorizes them according to the event model supported and the structure of the event service. Event services are further classified according to their organization and their interaction models, as well as other functional and non-functional features. [ABSTRACT FROM PUBLISHER]

Grid middleware development has advanced rapidly over the past few years to support component-based programming models and service-oriented architectures. This is most evident with the forthcoming release of the Globus toolkit (GT4), which represents a convergence of concepts (and standards) from both the grid and web-services communities. Grid applications are increasingly modular, composed of workflow descriptions that feature both resource and application dynamism. Understanding the performance implications of scheduling grid workflows is critical in providing effective resource management and reliable service quality to users. This paper describes a series of extensions to an existing performance-aware grid management system (TITAN). These extensions provide additional support for workflow prediction and scheduling using a multi-domain performance management infrastructure. [ABSTRACT FROM PUBLISHER]

This paper introduces a new programming model for distributed systems, distributed composite objects (DCOs), to meet efficient implementation, transparency and performance demands of distributed applications with cooperating users connected through the Internet. The DCO model incorporates two basic concepts. The first is composition, by which an object is partitioned into sub-objects that together constitute a single composite object. The second is replication, which extends the object concept to the distributed environment. The DCO model allows the representation of an object as a collection of sub-objects and enhances the object distribution concept by implementing replication at the sub-object level and only when demanded. DCOBE, a DCO-based programming environment, conceals implementation details of the DCO model behind its interface and provides basic mechanisms for object composition, distribution and replication of object state, consistency management, concurrency control and dynamic deployment of restructured objects. It facilitates the design of distributed applications, significantly reducing the overall time for development by taking care of distributed system issues. DCOBE, being implemented on JVM, provides an environment that works on heterogeneous platforms. A distributed application is developed using the Java language in a centralized manner and is then made available on the Internet. The Objects are dynamically deployed to requesting client nodes. This allows users to deal with various environments that exist in a wide area network and to separate applications from the implementation of shared objects. [ABSTRACT FROM PUBLISHER]

Reversible variable length codes (RVLCs) have been extensively studied. In recent years, many new coding standards such as H.263 MPEG-4 and JPEG-2000 have adopted RVLCs to enhance their error resilient capability. This paper presents a novel algorithm that can construct efficient RVLCs. Distinct from previous Huffman-based schemes, the proposed algorithm employs the branch-and-bound strategy to generate RVLCs. This strategy not only improvesthe coding efficiency but also provides a flexible codeword selection. The experimental results show that the RVLCs obtained by our algorithm outperform all existing RVLCs. [ABSTRACT FROM AUTHOR]

An evidence theoretic classification method is proposed in this paper. In order to classify a pattern we consider its neighbours, which are taken as parts of a single source of evidence to support the class membership of the pattern. A single mass function or basic belief assignment is then derived, and the belief function and the pignistic (‘betting rates’) probability function can be calculated. Then the (posterior) conditional pignistic probability function is calculated and used to decide the class label for the pattern. It is shown that such a classifier extends the standard majority voting based k-nearest neighbour classifier, and it is an approximation to the optimal Bayes classifier. In experiments this classifier performed as well as or better than the voting and distance weighted k-nearest neighbours classifiers with best k, and its performance became stable when the number of neighbours considered was >4. [ABSTRACT FROM AUTHOR]

Exception systems have become popular because they uncouple error detection and handling thus allowing us to produce better software. However, the exception handling systems of many object-oriented languages benefit very little from object-oriented programming. The catch clauses following a try block are isolated pieces of code: they do not belong to classes and cannot be reused. This paper presents the object-oriented exception system of the Green language, which fully uses the object-oriented programming features. These include the use of classes, types and subtyping, objects and inheritance. The result is a powerful exception system completely integrated with the language. [ABSTRACT FROM AUTHOR]

This paper presents a loopless algorithm to generate all permutations of a multiset. Each is obtained from its predecessor by making one transposition. It differs from previous such algorithms by using an array for the permutations but requiring storage only linear in its length. [ABSTRACT FROM AUTHOR]

Many data compression techniques are essentially variable length codes. Such codes suffer from a vulnerability to error propagation. This occurs when an error causes the correspondence between the data stream and the stream of encoded symbols to be lost and continues until synchronization between the two is re-established. This paper compares a number of strategies for synchronization in which redundant synchronizing words are used with a mechanism for labelling or counting them. In each case the strategy is investigated for the prevention of error propagation, ensuring the re-establishment of the correspondence with the correct point in the data stream. Three classes of potential synchronization error are explored: the false recognition of spurious words, the loss of synchronizing words and synchronization misinterpretation, when one synchronizing word is confused with another. The probabilities of synchronization error are analysed. It is shown that the strategies are successful against random errors when they incorporate some mechanism for consistency checking. The relative merits of different schemes are demonstrated. The schemes are also compared with the technique known as bitstuffing. This is considered on its own and in combination with the other schemes. [ABSTRACT FROM AUTHOR]

In this paper we present a polynomial time algorithm for finding the shortest sequence of rotations that converts one binary tree into another when both binary trees are of a restricted form. The initial tree must be a degenerate tree, where every node has exactly one child, and the destination binary tree must also be degenerate, of a more restricted nature. Previous work on rotation distance has focused on approximation algorithms. Our algorithm is the only known non-trivial polynomial time algorithm for exact rotation distance between special cases of binary trees. [ABSTRACT FROM AUTHOR]

This paper presents an approach to analyze stack-based assembly code with respect to leakages of private information. We consider systems implementing a multilevel security policy, where the security levels form a lattice. The approach is based on abstract interpretation of the operational semantics. We consider a representative subset of instructions of conventional stack-based assembly languages. We define a collecting small-step semantics of the language, enhanced to convey the level of the information flow during execution: this is accomplished by annotating each value with the level of the information on which it depends. Then we define an abstract semantics of the language that abstracts from actual data and maintains only the annotations on the security level. We give sufficient conditions the abstract semantics must satisfy to ensure secure information flow. The use of abstract interpretation allows, on one side, being semantics based, to accept as secure a wide class of programs, and on the other side, being rule based, to be automated fully. In fact we show how it may be combined with a model checking technique, where the conditions for security are described by temporal logic formulae that can be automatically checked on the abstract representation of the program. [ABSTRACT FROM AUTHOR]

Students often have difficulty with the minutiae of program construction. We introduce the idea of ‘Programming by Numbers’, which breaks some of the programming process down into smaller steps, giving such students a way into the process of Programming in the Small. Programming by Numbers doesnot add intellectual difficulty to learning programming, as it does not require the student to learn additional tools or theory. In fact it can be done with pencil and paper or the normal editor, and only requires the student to remember (and understand) seven simple steps. Programming by Numbers works best with languages that offer pattern matching, such as ML, or data-directed dispatching, such as Java. [ABSTRACT FROM PUBLISHER]

In this paper we introduce a typed λ-calculus in which computer networks can be formalized and directed at situations where the services available on the network are stationary, while the information can flow freely. For this calculus, an analogue of the ‘propositions-as-types ’interpretation of constructive type theory holds with respect to information push and pull in computer networks: in the calculus a type represents a task that the user wants to carry out, while a term inhabiting this type represents a procedure that will yield the desired result. Under this interpretation, techniques for theorem proving can be used for finding a procedure to achieve a certain task on the network. Techniques for type checking can be used for checking a complex network program before running it. Reductions on terms can be used for finding alternative procedures to achieve a certain task. Terms constructed in this abstract calculus can be ‘compiled ’to procedures which are executable on the actual network. We show this for a simple Unix network. [ABSTRACT FROM PUBLISHER]

A recursive algorithm GenWordsR and a non-recursive algorithm GenWordsNR are presented in this paper to generate sequences for regular k-ary trees efficiently. They are compared with some of the previous recursive and non-recursive algorithms for this problem that were found in the literature. When the average number of recursive calls is used as a measure of the time complexity of recursive algorithms for generating k-ary trees, O(k) calls for a k-ary tree is the bestresult in the previous recursive algorithms, while O(1/k) calls for a k-ary tree is needed by GenWordsR. When the average number of comparisons is used as a measure of the time complexity of non-recursive algorithms for generating k-ary trees, GenWordsNR outperforms the previous non-recursive algorithms. As k increases, the number (and the average number) of comparisons performed by GenWordsNR tends to 66% that of the best previous non-recursive algorithms. [ABSTRACT FROM PUBLISHER]

In this paper, some interesting issues related to vertical partitioning in object oriented database systems are presented. A review of existing research is given with an identification of some open problems. A taxonomy of various possible partitioning schemes and a unified view of the vertical partitioning problem are also presented. Existing vertical partitioning algorithms have been studied for their use in both parallel and distributed object-oriented databases. [ABSTRACT FROM PUBLISHER]

The reliability of a distributed computing system depends on the reliability of its communication links and nodes and on the distribution of its resources, such as programs and data files. Many algorithms have been proposed for computing the reliability of distributed computing systems, but they have been applied mostly to distributed computing systems with perfect nodes. However, in real problems, nodes as well as links may fail. This paper proposes two new algorithms for computing the reliability of a distributed computing system with imperfect nodes. Algorithm I is based on a symbolic approach that includes two passes of computation. Algorithm II employs a general factoring technique on both nodes and edges. Comparisons with existing methods show the usefulness of the proposed algorithms for computing the reliability of large distributed computing systems. [ABSTRACT FROM PUBLISHER]

Due to the widespread distribution and the nature of hyperlinks on the WWW system, interactive temporal behaviours that exist in the WWW environment are different from those used in traditionally distributed multimedia presentation environments. Therefore, the control scheme and model of a new temporal synchronization that can guarantee the presentation continuity within the multimedia WWW environment is required. In this paper we will: (i) classify interactive temporal behaviours that are associated with user interactions, i.e. `replay', `freeze-restart', `skip&go-to', `hold&go-to' and `end&go-to', into two classes, intrapage user and interpage interactive temporal behaviours; (ii) identify the link control with some temporal constraints; (iii) derive temporal interactive synchronization control schemes to resolve the permitted interactive temporal behaviours and the system's link behaviour; and (iv) propose the extended finite state machine (EFSM) approach that is able to formally model the corresponding interactive temporal and link control architecture and schemes. [ABSTRACT FROM PUBLISHER]

Flexible network management requires explicit control of the exact paths taken by different network flows. Whatever the way this endeavour is achieved (e.g. Multiprotocol Label Switching, Virtual Local Area Networks and OpenFlow), this need may lead to an explosion of entries in the forwarding tables of network equipment. In this article, we present an algorithm that aggregates many network paths in a reduced number of trees, thus allowing shrinking the forwarding state in switching devices. Path aggregation algorithms are often deployed to reduce data-plane state with different routing approaches and the presented algorithm achieves better results than existent algorithms with similar goals. Additionally, we show that most types of popular routing and switching equipment, even using off-the-shelf routing software, may be used to implement multi-path routing with trees. This highlights the applicability of the proposed algorithm and its significance in light of the current trend of separating the data- and the control-planes in modern networks. [ABSTRACT FROM AUTHOR]

This paper presents a new specification language called ARC. The language ARC is designed for specifying systems where communication plays a pivotal role. ARC takes simple message sequence charts as a starting point and extends them to allow the precise specification of complex communication behaviour. ARC includes the language COLD-K for specifying data and operations on data. The goal in designing the ARC language was to retain the intuitive nature of simple sequence charts while allowing more complex behaviour to be described. [ABSTRACT FROM AUTHOR]

Substitution errors, where individual characters are altered, and transposition errors, where two consecutive characters are interchanged, are commonly caused by human operators. In this paper, codes that detect a single substitution error or a single transposition error are studied. In particular, it is shown that such codes of length n over an alphabet of q characters have at most qn−1 codewords if q ≤ 3 and at most [2n/3] codewords if q = 2. Codes which have that many codewords are called optimal codes. We present optimal codes for all values of n and q. Simple encoding techniques for these codes are also described. [ABSTRACT FROM AUTHOR]

As use of object orientation for application development has increased, many researchers have investigated the design of object-based programming languages for distributed and persistent programming. This paper concentrates on reviewing a number of such languages for distributed or persistent programming. In each case, the focus is on the object model supported and the mechanisms and policies employed in the implementation of distributed or persistent objects. In particular, each language reviewed has been chosen to illustrate a particular object model or implementation strategy. [ABSTRACT FROM AUTHOR]

This paper presents a generalization of Robinson and Staple's window inference system of hierarchical reasoning. The generalization enhances window inference so that it is capable of supporting transformational proofs. In addition, while Robinson and Staples proposed window inference as an alternative to existing styles of reasoning, this paper describes window inference in terms of sequent formulation of natural deduction. Expressing window inference in terms of natural deduction, a style of reasoning already known to be sound, demonstrates the soundness of window inference itself. It also illustrates how mechanized support for window inference can be implemented using existing sequent-based theorem provers. The paper also examines the use of contextual assumptions with window inference. Two definitions of what may be assumed in a context are presented. The first is a general definition; while the second has a simpler form. These definitions are shown to be equivalent for contexts that do not bind variables. [ABSTRACT FROM AUTHOR]