Ensuring fault-tolerant computations in distributed control systems

This paper demonstrates that the fault tolerance of distributed control systems (DCSs) can be improved by scheduling of processes representing functional segments with guaranteed operation of the mechanisms of process reexecution and parallel execution based on checkpoints. Moreover, we suggest the methodological approach to assessing the fault tolerance level of DCSs, which proceeds from the probabilistic modeling of systems having the time triggered architecture (TTA). Finally, we derive numerical formulas for qualitative and quantitative estimation of the fault tolerance level for different modifications of DCSs at the design stage.     

An adaptive fault-tolerant routing algorithm for hypercubemulticomputers

This paper presents a partially adaptive fault-tolerant routing algorithm for hypercube multicomputers. The algorithm is tolerant to n-1 link and/or node faults for an n-cube. It makes routing decisions adaptively based on local failure information only. It is simple to implement and needs a very small message overhead. A comparison between the algorithm and a popular previous work is given     

An adaptive task-level fault-tolerant approach to Grid

A strong failure recovery mechanism handling diverse failures in heterogeneous and dynamic Grid is so important to ensure the complete execution of long-running applications. Although there have been various efforts made to address this issue, existing solutions either focus on employing only one single fault-tolerant technique without considering the diversity of failures, or propose some frameworks which cannot deal with various kinds of failures adaptively in Grid. In this paper, an adaptive task-level, fault-tolerant approach to Grid is proposed. This approach aims at handling quite a complete set of failures arising in Grid environment by integrating basic fault-tolerant approaches. Moreover, this paper puts forward that resource consumption (not received enough attention) is also an important evaluation metric for any fault-tolerant approach. The corresponding evaluation models based on mean execution time and resource consumption are constructed to evaluate any fault-tolerant approach. Based on the models, we also demonstrate the effectiveness of our approach and illustrate the performance gains achieved via simulations. The experiments based on a real Grid have been made and the results show that our approach can achieve better performance and consume less resource.     

Termination detection for distributed computations

A simple derivation of a general solution to the problem of detecting the termination of a distributed computation is presented.     

An immunity-based distributed multiagent-control framework

The human immune system is a complex system of cells, molecules, tissues, and diverse organs that can provide us with primary defense against pathogenic organisms. These components are highly interactive and execute the immune response in a coordinated and specific manner. This paper presents a formal mathematical model of an artificial immune system (AIS)-based control framework. The framework aims to provide an integrated solution to control and coordinate complex distributed systems with a large number of autonomous agents such as automated warehouses, distribution centers, and automated material-handling systems. The control framework consists of a set of AIS agents working in response to the changing environment and the occurrence of tasks. The AIS agents manipulate their capabilities to derive appropriate responses to tackle different problems. A methodology describing the response-manipulation algorithm of the AIS agents and their ability to generate new capabilities is discussed in this paper. Through response manipulation and knowledge building, a self-organized and fully distributed system with agents that are able to adapt and accommodate in a dynamic environment via distributed decision making and interagent communication is achieved.     

An efficient distributed algorithm for detection of knots and cycles in a distributed graph

Knot detection in a distributed graph is an important problem and finds applications in deadlock detection in several areas such as store-and-forward networks, distributed simulation, and distributed database systems. This paper presents an efficient distributed algorithm to detect if a node is part of a knot in a distributed graph. The algorithm requires 2e messages and a delay of 2(d+1) message hops to detect if a node in a distributed graph is in a knot (here, e is the number of edges in the reachable part of the distributed graph and d is its diameter). A significant advantage of this algorithm is that it not only detects if a node is involved in a knot, but also finds exactly which nodes are involved in the knot. Moreover, if the node is not involved in a knot, but is only involved in a cycle, then it finds the nodes that are in a cycle with that node. We illustrate the working of the algorithm with examples. The paper ends with a discussion on how the information about the nodes involved in the knot can be used for deadlock resolution and also on the performance of the algorithm.     

An adaptive framework for monitoring agent organizations

Multiagent technologies are usually considered to be suitable for constructing agent organizations that are capable of running in dynamic and distributed environments and that are able to adapt to changes as the system runs. The necessary condition for this adaptation ability is to make agents aware of significant changes in both the environment and the organization. This paper presents mechanism, which helps agents detecting adaptation requirements dynamically at run time, and an Trace&Trigger, which is an adaptation framework for agent organizations. It consists of an event-tracing-based monitoring mechanism that provides organizational agents with information related to the costs and benefits of carrying out an adaptation process at each moment of the execution. This framework intends to overcome some of the problems that are present in other approaches by allowing the dynamic specification of the information that has to be retrieved by each agent at each moment for adaptation deliberation, avoiding the transference of useless information for adaptation deliberation. This framework has been integrated in the Magentix2 multiagent platform. In order to test its performance benefits for any agent organization, an example based on a market scenario is also presented.     

An adaptive middleware framework for context-aware applications

We describe a middleware framework for the adaptive delivery of context information to context-aware applications. The framework abstracts the applications from the sensors that provide context. Further applications define utility functions on the quality of context attributes that describe the context providers. Then, given multiple alternatives for providing the same type of context, the middleware applies the utility function to each alternative and choose the one with maximum utility. By allowing applications to delegate the selection of context source to the middleware, our middleware can implement autonomic properties, such as self-configuration when new context providers appear and resilience to failures of context providers.

---

     

An enhanced active caching strategy for data-intensive computations in distributed GIS

Caching can prepare data for computational tasks in advance by tracking the requirements and behaviors of distributed geographical information systems to reduce network latency and improve computational performance. This paper presents an enhanced method to actively cache data for data-intensive computations that considers both data relationships and the timeliness of those relationships. First, the access correlations, the correlation steps and the times of the correlations are computed based on the behaviors of the computational tasks. Because the influence of historically accessed records will decrease gradually over time, only recently accessed records are used. To track changes in the relationships and prevent cache waste problems, each record is given a different age-based weight. A conditional caching probability can then be computed based on the timeliness relationships, which can be used to find the appropriate data to compute simultaneously. Finally, we present several experiments that compare the proposed method with techniques that use other data placement strategies, active caching strategies and passive caching algorithms. The results show that the proposed model has better performance than other algorithms in all respects. In addition, the proposed model results in a lower cache replacement ratio. The experiments with different data sets on different data scales indicate that the proposed algorithm can also be used in large-scale distributed environments.     

An architectural application framework for evolving distributed systems

In this paper, we present an object-oriented application framework to support the development of evolving distributed systems. The framework combines concepts of the object-oriented paradigm with those of architectural design. The result is a framework which supports extensible and reusable configurations of distributed components. The framework addresses the problem of evolution by allowing the addition, replacement and extension of components of a configuration. Evolution is also possible at run time, where a configuration can change dynamically depending on a particular event. The paper outlines the fundamental aspects of our framework and presents a case study, which illustrates its application.     

An efficient adaptive scheduling scheme for distributed memorymulticomputers

Traditional multiprocessor scheduling schemes have been one of either space-sharing or time-sharing. Space-sharing schemes perform better than time-sharing at low to moderate system loads. However, they have a disadvantage of wasting processing power within partitions at medium to high system loads. Time sharing schemes tend to perform better at medium to high system loads. Almost all the scheduling schemes proposed so far have been tested under ad hoc workload considerations. In light of recent knowledge about workloads, it is imperative to develop an integrated scheduling scheme that combines the advantages of space- and time-sharing while overcoming their individual drawbacks. We propose such a scheduling scheme, called Hierarchical Scheduling Policy, which is efficient as well as general enough to accommodate multiple workloads. Simulation results indicate that our scheme significantly outperforms the best space- and time-sharing mechanisms at medium to high system loads even in the absence knowledge regarding individual job characteristics     

An object-oriented framework for developing distributed manufacturing architectures

Management of complexity, changes and disturbances is one of the key issues of production today. Distributed, agent-based structures represent viable alternatives to hierarchical systems provided with reactive/proactive capabilities. In the paper, approaches to distributed manufacturing architectures are surveyed, and their fundamental features are highlighted, together with the main questions to be answered while designing new structures. Moreover, an object-oriented simulation framework for development and evaluation of multi-agent manufacturing architectures is introduced.     

An architecture framework for an adaptive extensible processor

To improve the performance of embedded processors, an effective technique is collapsing critical computation subgraphs as application-specific instruction set extensions and executing them on custom functional units. The problem with this approach is the immense cost and the long times required to design a new processor for each application. As a solution to this issue, we propose an adaptive extensible processor in which custom instructions (CIs) are generated and added after chip-fabrication. To support this feature, custom functional units are replaced by a reconfigurable matrix of functional units (FUs). A systematic quantitative approach is used for determining the appropriate structure of the reconfigurable functional unit (RFU). We also introduce an integrated framework for generating mappable CIs on the RFU. Using this architecture, performance is improved by up to 1.33, with an average improvement of 1.16, compared to a 4-issue in-order RISC processor. By partitioning the configuration memory, detecting similar/subset CIs and merging small CIs, the size of the configuration memory is reduced by 40%.     

Reconciling fault-tolerant distributed computing and systems-on-chip

Classic distributed computing abstractions do not match well the reality of digital logic gates, which are the elementary building blocks of Systems-on-Chip (SoCs) and other Very Large Scale Integrated (VLSI) circuits: Massively concurrent, continuous computations undermine the concept of sequential processes executing sequences of atomic zero-time computing steps, and very limited computational resources at gate-level make even simple operations prohibitively costly. In this paper, we introduce a modeling and analysis framework based on continuous computations and zero-bit message channels, and employ this framework for the correctness & performance analysis of a distributed fault-tolerant clocking approach for Systems-on-Chip (SoCs). Starting out from a “classic” distributed Byzantine fault-tolerant tick generation algorithm, we show how to adapt it for direct implementation in clockless digital logic, and rigorously prove its correctness and derive analytic expressions for worst case performance metrics like synchronization precision and clock frequency. Rather than on absolute delay values, both the algorithm’s correctness and the achievable synchronization precision depend solely on the ratio of certain path delays. Since these ratios can be mapped directly to placement & routing constraints, there is typically no need for changing the algorithm when migrating to a faster implementation technology and/or when using a slightly different layout in an SoC.     

An adaptive graph cut algorithm for video moving objects detection

The algorithms based on graph cut have the advantage to detect the moving objects effectively and robustly. The main trouble of the algorithm based on graph cut is that its model parameters will be determined empirically. In this paper, a novel algorithm of adaptive graph cut is proposed to detect video moving objects. Based on Markov random field model, the proposed algorithm uses the numbers of moving objects pixels and objectives-background pixel-pairs to describe the geometric features of the moving objects. And the relationship between the geometric features of the moving objects and the model parameters are set up. In this paper, the model parameters are adaptively optimized through the extraction and prediction of the geometric features of moving objects. Then the detection based on the graph cut is preformed on ROI, which well achieves the balance between the computation and accuracy. Finally, the experimental results show the proposed algorithm can hold the details of moving objects more effectively compared with other algorithms, and improve the detection performance of moving object in the video surveillance.     

An adaptive and QoS-based spectrum awareness framework for CR networks

The Cognitive Radio (CR) networks have the capability to be aware of the licensed spectrum and to solve the inefficient usage of the vacant bands in an opportunistic manner. Thus, a spectrum awareness framework must be designed by considering the spectrum availability, the Primary User (PU) interference avoidance and the heterogeneous Quality of Service (QoS) requirements of CR users (CrUs). Considering these challenges, the main contribution of this paper is to design a complete framework for the spectral awareness in CR networks achieving higher spectrum utilization and fairness. Specifically, a PU Presence Map (PuM) is built for the PU interference avoidance. The QoS requirements of CR users are classified using a Request Map, ReM. An admission control is proposed to stabilize the heterogeneous QoS requirements according to PuM and ReM. Moreover, the adaptiveness of the framework is provided by continuous monitoring of the spectrum against dynamic variations. The simulations demonstrate that the proposed spectrum awareness framework maximizes the available spectrum utilization while maintaining the fairness.     

Causality and atomicity in distributed computations

Summary. In a distributed system, high-level actions can be modeled by nonatomic events. This paper proposes causality relations between distributed nonatomic events and provides efficient testing conditions for the relations. The relations provide a fine-grained granularity to specify causality relations between distributed nonatomic events. The set of relations between nonatomic events is complete in first-order predicate logic, using only the causality relation between atomic events. For a pair of distributed nonatomic events X and Y, the evaluation of any of the causality relations requires integer comparisons, where and , respectively, are the number of nodes on which the two nonatomic events X and Y occur. In this paper, we show that this polynomial complexity of evaluation can by simplified to a linear complexity using properties of partial orders. Specifically, we show that most relations can be evaluated in integer comparisons, some in integer comparisons, and the others in integer comparisons. During the derivation of the efficient testing conditions, we also define special system execution prefixes associated with distributed nonatomic events and examine their knowledge-theoretic significance. Received: July 1997 / Accepted: May 1998     

An adaptive framework for 3D graphics over networks

Access to and transmission of 3D models over networks becomes increasingly popular. However, the performance and quality of access to remote 3D models strongly depends on system load conditions and the capabilities of the various system components, such as clients, servers, and interconnect. The network graphics framework (NGF) integrates various transmission methods for downloading 3D models in a client–server environment. The NGF automatically selects the optimal transmission method for a given pair of client and server, taking into account characteristics of the model to be transmitted, critical environment conditions, user preferences and the capabilities of the client and the server. The NGF aims to provide constant quality of service across different clients and under varying environment conditions.     

一种分布式自治物流信息系统构架

针对物流企业及零售商分散的特点和客户的多样化个性化需求,为了整合分散的物流信息,建立具有弹性的物流对象协同运作模式,解决RFID与该构架的信息集成,提出了一种基于Internet的分布式协调自治物流信息系统构架。详细描述了系统的各关键环节。