Modified distributed snapshots algorithm for protocol stabilization

This paper assesses the use of Chandy and Lamport's distributed snapshots algorithm (DSA) for stabilizing a communication protocol, a special type of distributed system. We show that when a loss of coordination occurs during the distributed execution of the protocol, DSA is not guaranteed to terminate, and therefore it sometimes fails to obtain a global state or snapshot. We propose some modifications to DSA to solve this problem. Finally, we discuss how, in the case of a loss of coordination, the modified algorithm can be used to stabilize a communication protocol, and we assess the suitability of the global state obtained by DSA as a recovery point to be used later in a backward recovery procedure.     

A modified genetic algorithm for distributed scheduling problems

Genetic algorithms (GAs) have been widely applied to the scheduling and sequencing problems due to its applicability to different domains and the capability in obtaining near-optimal results. Many investigated GAs are mainly concentrated on the traditional single factory or single job-shop scheduling problems. However, with the increasing popularity of distributed, or globalized production, the previously used GAs are required to be further explored in order to deal with the newly emerged distributed scheduling problems. In this paper, a modified GA is presented, which is capable of solving traditional scheduling problems as well as distributed scheduling problems. Various scheduling objectives can be achieved including minimizing makespan, cost and weighted multiple criteria. The proposed algorithm has been evaluated with satisfactory results through several classical scheduling benchmarks. Furthermore, the capability of the modified GA was also tested for handling the distributed scheduling problems.     

Verification of distributed control systems in intelligent manufacturing

This paper presents an application of formal methods for validation of flexible manufacturing systems controlled by distributed controllers. A software tool verification environment for distributed applications (VEDA) is developed for modeling and verification of distributed control systems. The tool provides an integrated environment for formal, model-based verification of the execution control of function blocks following the new international standard IEC61499. The modeling is performed in a closed-loop way using manually developed models of plants and automatically generated models of controllers.     

A full sensing window Random-Access algorithm for messages with strict delay constraints

We consider the Channel Multiple-Access problem for messages with strict delay constraints. The constraints are represented by an upper bound on the transmission delays. For this problem, and for binary collision-noncollision feedback per slot, we present a simple full sensing window Random-Access algorithm. We analyze the algorithm and we compute the fraction of maintained traffic and the expected delay for the successfully transmitted packet, for various input Poisson intensities and various values of the bound on the transmission delays.This work was supported by the U.S. Office of Naval Research, under Contract ONR-N14-86-K-0742.     

A distributed task planning system for computer-integrated manufacturing systems

A formal mathematical framework for a distributed task planning method suitable for computerintegrated manufacturing systems is proposed. All pertinent algorithms are derived. A detailed timing analysis associated with primitive actions and activities (complex tasks) execution is presented. A formal language is designed for event tracking and error specification. Based on the derived language, an error recovery mechanism (automaton) is proposed. A case study demonstrates the applicability of the presented method with and without error occurrences.Dr Kokinaki is currently Science and Engineering Research Centre, De Montfort University, UK.     

A partially distributed deadlock detection algorithm

In this paper, a partially distributed deadlock detection algorithm [PDDDA] with multiple outstanding requests is presented for use in distributed database systems. This algorithm allows a process to request many resources simultaneously and uses a central controller for detecting multisite deadlocks. The detection of local deadlocks and the maintenance of local deadlock information are performed at each of the local sites. This partially distributed algorithm alleviates the problem of congestion at the central controller in a centralized algorithm and needs fewer messages and smaller storage space than a fully decentralized algorithm. A set of criteria for comparing deadlock detection algorithms are also given and then used to compare PDDDA with a fully decentralized algorithm proposed by Isloor and Marsland.Research reported herein was supported by US Army CECOM, Ft. Monmouth, New Jersey, under Contract No. DAAB07-83-K-K542. The views, opinions, and/or findings contained in this paper are those of the authors and should not be construed as an official Deportment of the Army position, policy or decision.     

Integration and control of intelligence in distributed manufacturing

The area of intelligent systems has generated a considerable amount of interest—occasionally verging on controversy—within both the research community and the industrial sector. This paper aims to present a unified framework for integrating the methods and techniques related to intelligent systems in the context of design and control of modern manufacturing systems. Particular emphasis is placed on the methodologies relevant to distributed processing over the Internet. Following presentation of a spectrum of intelligent techniques, a framework for integrated analysis of these techniques at different levels in the context of intelligent manufacturing systems is discussed. Integration of methods of artificial intelligence is investigated primarily along two dimensions: the manufacturing product life-cycle dimension, and the organizational complexity dimension. It is shown that at different stages of the product life-cycle, different intelligent and knowledge-oriented techniques are used, mainly because of the varied levels of complexity associated with those stages. Distribution of the system architecture or system control is the most important factor in terms of demanding the use of the most up-to-date distributed intelligence technologies. A tool set for web-enabled design of distributed intelligent systems is presented. Finally, the issue of intelligence control is addressed. It is argued that the dominant criterion according to which the level of intelligence is selected in technological tasks is the required precision of the resulting operation, related to the degree of generalization required by the particular task. The control of knowledge in higher-level tasks has to be executed with a strong involvement of the human component in the feedback loop. In order to facilitate the human intervention, there is a need for readily available, user-transparent computing and telecommunications infrastructure. In its final part, the paper discusses currently emerging ubiquitous systems, which combine this type of infrastructure with new intelligent control systems based on a multi-sensory perception of the state of the controlled process and its environment to give us tools to manage information in a way that would be most natural and easy for the human operator.     

Automated contracting in distributed manufacturing among independent companies

So far, most distributed scheduling systems have been designed for cooperative agents, and are inappropriate for self-interested agents, as for example in inter-firm interactions such as virtual enterprises. This paper discusses issues that arise in extending automated contracting to operate among such self-interested agents. We construct a leveled commitment contracting protocol that allows self-interested agents to efficiently accommodate future events by having the possibility of unilaterally decommitting from a contract based on local reasoning. A decommitment penalty is assigned to both agents in a contract to be freed from the contract, an agent only pays this penalty to the other party. It is formally shown that this leveled commitment feature in a contracting protocol increases Pareto efficiency of deals and can enable contracts by making them individually rational when no full commitment contract can. The analysis is nontrivial because self-interested agents decommit manipulatively a Nash equilibrium analysis of the decommitting game is necessary.     

Divergence control for distributed database systems

This paper presents distributed divergence control algorithms for epsilon serializability for both homogeneous and heterogeneous distributed databases. Epsilon serializability allows for more concurrency by permitting non-serializable interleavings of database operations among epsilon transactions. We first present a strict 2-phase locking divergence control algorithm and an optimistic divergence control algorithm for a homogeneous distributed database system, where the local orderings of all the sub-transactions of a distributed epsilon transaction are the same. In such an environment, the total inconsistency of a distributed epsilon transaction is simply the sum of those of all its sub-transactions. We then describe a divergence control algorithm for a heterogeneous distributed database system, where the local orderings of all the sub-transactions of a distributed epsilon transaction may not be the same and the total inconsistency of a distributed epsilon transaction may be greater than the sum of those of all its sub-transactions. As a result, in addition to executing a local divergence control algorithm in each site to maintain the local inconsistency, a global mechanism is needed to take into account the additional inconsistency Recommended by: Meichum Hsu     

分布式控制系统中多种混合任务的容错调度

分布式控制系统中存在有强实时、软实时和非实时等多种实时性的任务,其中强实时任务必须在其时限前完成,否则会出现灾难性后果,因此必须为分布式控制系统提供一定的容错能力。首先给出了用于调度多种实时性任务的单处理器调度算法——双优先级队列调度算法,并分析算法的可调度性条件。针对分布式控制系统,考虑基版本与副版本的执行时间不同时,结合版本复制技术和单处理器调度算法提出了一种新的容错调度算法。分析了算法的可调度行,给出了可任务集的可调度条件判断方法和基版本任务时限的设置方法。在此基础上,采用启发式静态任务分配算法,保证各处理器的负载均衡。本算法在保证任务容错可调度的条件下,可提高系统中各处理器的利用率,仿真结果表明该算法是有效的。     

A query processing algorithm for a system of heterogeneous distributed databases

This paper presents a query processing algorithm, formulated and developed in support of the prototype architecture of the Distributed Access View Integrated Database (DAVID) which is a heterogeneous distributed database management system. The objective of the proposed query processing algorithm is to produce an inexpensive strategy for a given query. The inexpensive query strategy is obtained primarily by computing the most profitable semi-joins and by determining the best sequence of join operations per processing site. The latter is obtained by applying a zero-one integer linear program that uses a non-parametric statistical estimation technique to compute the sizes of the temporary clusters. A cluster is a subset of the cartesian product of a list of atomic and non-atomic domains and is the structure that can represent in a uniform way data stored in relational, hierarchical and network databases.Following some background information on the development of the DAVID prototype, this paper introduces the schema architecture. The schema architecture describes the mechanism by which the component heterogeneous database schemata are mapped into the uniform global schema. This is followed by the formulation of the query processing algorithm, its implementation and an illustration of its use in the context of NASA's Astrophysics Data System.Recommended by: Y. Breitbart     

支持构件迁移的分布式系统容错算法

随着分布式应用技术的发展,构件的静态性限制了分布式系统在运行期间适应其可用资源变化的要求.为了动态适应系统可用资源,提高系统性能,支持构件可迁移的分布式应用研究受到广泛关注.针对提高构件可迁移分布式应用的可靠性,提出一种分布式系统容错算法.在准同步检查点算法的基础上,通过引入shadow-chain和通讯录机制,实现了构件间通信的可靠性和构件重定位的透明性,从而使得系统能够在较低代价下设置检查点,并能将出错后的系统回卷到一致性状态.     

A software architecture for distributed computer control systems

Distributed computer control systems have a number of potential advantages over centralized systems, especially where the application is itself physically distributed. A computer station can be placed close to the plant being controlled, and a communications network used to enable the stations to communicate to coordinate their actions. However, the software must be carefully designed to exploit the potential advantages of distribution. This paper describes the software architecture of CONIC, a system to support distributed computer control applications. This architecture emphasizes the distinction between the writing of individual software components and the construction and configuration of a system from a set of components. A modular structure is used to separate programming from configuration. Typed entry and exit ports are used to clearly define module interfaces. Ports, analagous to the plugs and sockets of hardware components, permit modules to be interconnected in different ways. On-line modification and extension of the system is supported by permitting the dynamic creation and interconnection of modules. Message passing primitives are provided to permit modules to coordinate and synchronize control actions.     

Internet-based manufacturing: A review and a new infrastructure for distributed intelligent manufacturing

Global competition and rapidly changing customer requirements are forcing major changes in the production styles and configuration of manufacturing enterprises. Traditional centralized manufacturing systems are not able to meet these requirements. In recent years, the internet has become the worldwide information platform for the sharing of information and data. Information processing is an important challenge in an internet-based manufacturing environment, and must facilitate distribution, heterogeneity, autonomy and cooperation. This paper reviews recent trends and major developments in internet-based manufacturing. Broad categories of distributed information management are identified, based upon the development of computer integrated manufacturing, and the possible direction of future research is indicated.     

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.     

Reliable performance prediction for multigrid software on distributed memory systems

We propose a model for describing and predicting the parallel performance of a broad class of parallel numerical software on distributed memory architectures. The purpose of this model is to allow reliable predictions to be made for the performance of the software on large numbers of processors of a given parallel system, by only benchmarking the code on small numbers of processors. Having described the methods used, and emphasized the simplicity of their implementation, the approach is tested on a range of engineering software applications that are built upon the use of multigrid algorithms. Despite their simplicity, the models are demonstrated to provide both accurate and robust predictions across a range of different parallel architectures, partitioning strategies and multigrid codes. In particular, the effectiveness of the predictive methodology is shown for a practical engineering software implementation of an elastohydrodynamic lubrication solver.     

A two-phase hybrid heuristic algorithm for the capacitated location-routing problem

In this paper, we propose a two-phase hybrid heuristic algorithm to solve the capacitated location-routing problem (CLRP). The CLRP combines depot location and routing decisions. We are given on input a set of identical vehicles (each having a capacity and a fixed cost), a set of depots with restricted capacities and opening costs, and a set of customers with deterministic demands. The problem consists of determining the depots to be opened, the customers and the vehicles to be assigned to each open depot, and the routes to be performed to fulfill the demand of the customers. The objective is to minimize the sum of the costs of the open depots, of the fixed cost associated with the used vehicles, and of the variable traveling costs related to the performed routes. In the proposed hybrid heuristic algorithm, after a Construction phase (first phase), a modified granular tabu search, with different diversification strategies, is applied during the Improvement phase (second phase). In addition, a random perturbation procedure is considered to avoid that the algorithm remains in a local optimum for a given number of iterations. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several solutions obtained by the previously published methods and new best known solutions.