Synchronous Byzantine quorum systems

Summary. Quorum systems have been used to implement many coordination problems in distributed systems such as mutual exclusion, data replication, distributed consensus, and commit protocols. Malkhi and Reiter recently proposed quorum systems that can tolerate Byzantine failures; they called these systems Byzantine quorum systems and gave some examples of such quorum systems. In this paper, we propose a new definition of Byzantine quorums that is appropriate for synchronous systems. We show how these quorums can be used for data replication and propose a general construction of synchronous Byzantine quorums using standard quorum systems. We prove tight lower bounds on the load of synchronous Byzantine quorums for various patterns of failures and we present synchronous Byzantine quorums that have optimal loads that match the lower bounds for two failure patterns. Received: June 1998 / Accepted: August 1999     

Designing Decentralized Controllers for Distributed-Air-Jet MEMS-Based Micromanipulators by Reinforcement Learning

Distributed-air-jet MEMS-based systems have been proposed to manipulate small parts with high velocities and without any friction problems. The control of such distributed systems is very challenging and usual approaches for contact arrayed system don’t produce satisfactory results. In this paper, we investigate reinforcement learning control approaches in order to position and convey an object. Reinforcement learning is a popular approach to find controllers that are tailored exactly to the system without any prior model. We show how to apply reinforcement learning in a decentralized perspective and in order to address the global-local trade-off. The simulation results demonstrate that the reinforcement learning method is a promising way to design control laws for such distributed systems.     

Implementing Coloured Petri Nets Using a Functional Programming Language

Coloured Petri Nets (CPNs) are a graphically oriented modelling language for concurrent systems based on Petri Nets and the functional programming language Standard ML. Petri Nets provide the primitives for modelling concurrency and synchronisation. Standard ML provides the primitives for modelling data manipulation and for creating compact and parameterisable CPN models.Functional programming and Standard ML have played a major role in the development of CPNs and the CPN computer tools supporting modelling, simulation, verification, and performance analysis of concurrent systems. At the modelling language level, Standard ML has extended Petri Nets with the practical expressiveness required for modelling systems of the size and complexity found in typical industrial projects. At the implementation level, Standard ML has been used to implement the formal semantics of CPNs that provide the theoretical foundation of the CPN computer tools.This paper provides an overview of how functional programming and Standard ML are applied in the CPN modelling language and the supporting computer tools. We give a detailed presentation of the key algorithms and techniques used for implementing the formal semantics of CPNs, and we survey a number of case studies where CPNs have been used for the design and analysis of systems. We also demonstrate how the use of a Standard ML programming environment has allowed Petri Nets to be used for the implementation of systems.     

An ordinal optimization theory-based algorithm for large distributed power systems

In this paper, we propose an ordinal optimization (OO) theory-based algorithm to solve the yet to be explored distributed state estimation with continuous and discrete variables problems (DSECDP) of large distributed power systems. The proposed algorithm copes with a huge amount of computational complexity problem in large distributed systems and obtains a satisfactory solution with high probability based on the OO theory. There are two contributions made in this paper. First, we have developed an OO theory-based algorithm for DSECDP in a deregulated environment. Second, the proposed algorithm is implemented in a distributed power system to select a good enough discrete variable solution. We have tested the proposed algorithm for numerous examples on the IEEE 118-bus and 244-bus with four subsystems using a 4-PC network and compared the results with other competing approaches: Genetic Algorithm, Tabu Search, Ant Colony System and Simulated Annealing methods. The test results demonstrate the validity, robustness and excellent computational efficiency of the proposed algorithm in obtaining a good enough feasible solution.     

A categorical framework for typing CCS-style process communication

Category theory has proved a useful tool in the study of type systems for sequential programming languages. Various approaches have been proposed to use categorical models to examine the type structures appropriate to concurrent systems. In this paper, we outline some of these approaches, such as interaction categories, and argue that they are not appropriate to model the handshake communication mechanism as used e.g. in CCS or the π-calculus. We propose an alternative general categorical framework for examining the type structure of such systems, and exhibit its categorical structure, which is similar to that of existing approaches. We then examine in detail an instance of this framework, based on a simple fragment of CCS. We prove that it is isomorphic to a syntactic category constructed from a process algebra similar to CCS, with a fusion operator, as in the fusion calculus. Thus, we make explicit some of the type structure implicitly present in such a process algebra.     

Multirobot systems: a classification focused on coordination

Multirobot systems (MRS) are, nowadays, an important research area within robotics and artificial intelligence and a growing number of systems have recently been presented in the literature. Since application domains and tasks that are faced by MRS are of increasing complexity, the ability of the robots to cooperate can be regarded as a fundamental feature. In this paper, we present a survey of the recent work in the area by specifically examining the forms of cooperation and coordination realized in the MRS. In particular, we propose a new taxonomy for classification of the approaches to coordination in MRS and we describe some systems, which we consider representative in our taxonomy. We finally discuss the outcomes of our analysis and try to highlight future trends of the research on MRS.     

Distributed Partial Order Reduction of State Spaces

State space explosion is a fundamental obstacle in formal verification of concurrent systems. Several techniques for combating this problem have emerged in the past few years, among which the two we are interested in are: partial order reduction and distributed memory state exploration. While the first one tries to reduce the problem to a smaller one, the other one tries to extend the computational power to solve the same problem. In this paper, we consider a combination of these two approaches and propose a distributed memory algorithm for partial order reduction.     

Rule-induction and case-based reasoning: hybrid architecturesappear advantageous

Researchers have embraced a variety of machine learning (ML) techniques in their efforts to improve the quality of learning programs. The recent evolution of hybrid architectures for machine learning systems has resulted in several approaches that combine rule induction methods with case-based reasoning techniques to engender performance improvements over more traditional single-representation architectures. We briefly survey several major rule-induction and case-based reasoning ML systems. We then examine some interesting hybrid combinations of these systems and explain their strengths and weaknesses as learning systems. We present a balanced approach to constructing a hybrid architecture, along with arguments in favor of this balance and mechanisms for achieving a proper balance. Finally, we present some initial empirical results from testing our ideas and draw some conclusions based on those results     

分布式视频点播系统的接入控制研究

Video on Demand(VoD)systems are considered as one of the most valuable services for the next generation broad-bandwidth Internet. To provide high-quality service, the VoD system must employ an admission control module to guarantee QoS, but there are still less research works having been made in this field, especially for distributed VoD systems. In this paper, we mainly focus on distributed admission control for VBR video streams in distributed VoD systems. We firstly discuss different approaches and then two admission control strategies are proposed with experimental comparisons. Our research is also further extended to resource assignment in distributed VoD systems. At the end of this article, we address issues in implementing distributed admission control.     

Sampled-data based distributed convex optimization with event-triggered communication

This paper studies the distributed convex optimization problem for multi-agent systems over undirected and connected networks. Motivated by practical considerations, we propose a new distributed optimization algorithm with event-triggered communication. The proposed event detection is decentralized, sampled-data and not requires periodic communications among agents to calculate the threshold. Based on Lyapunov approaches, we show that the proposed algorithm is asymptotically converge to the unknown optimizer if the design parameters are chosen properly. We also give an upper bound on the convergence rate. Finally, we illustrate the effectiveness of the proposed algorithm by a numerical simulation.     

A decentralized approach for mining event correlations in distributed system monitoring

Nowadays, there is an increasing demand to monitor, analyze, and control large scale distributed systems. Events detected during monitoring are temporally correlated, which is helpful to resource allocation, job scheduling, and failure prediction. To discover the correlations among detected events, many existing approaches concentrate detected events into an event database and perform data mining on it. We argue that these approaches are not scalable to large scale distributed systems as monitored events grow so fast that event correlation discovering can hardly be done with the power of a single computer. In this paper, we present a decentralized approach to efficiently detect events, filter irrelative events, and discover their temporal correlations. We propose a MapReduce-based algorithm, MapReduce-Apriori, to data mining event association rules, which utilizes the computational resource of multiple dedicated nodes of the system. Experimental results show that our decentralized event correlation mining algorithm achieves nearly ideal speedup compared to centralized mining approaches.     

Approaches for semantic interoperability between domain ontologies

Abstract: Domain ontologies and knowledge-based systems have become very important in the agent and semantic web communities. As their use has increased, providing means of resolving semantic differences has also become very important. In this paper we survey the approaches that have been proposed for providing interoperability among domain ontologies. We also discuss some key issues that still need to be addressed if we are to move from semi-automated to fully automated approaches to providing consensus among heterogeneous ontologies.     

On the Expressive Power of Schedulers in Distributed Probabilistic Systems

In this paper, we consider several subclasses of distributed schedulers and we investigate the ability of these subclasses to attain worst-case probabilities.Based on previous work, we consider the class of distributed schedulers, and we prove that randomization adds no extra power to distributed schedulers when trying to attain the supremum probability of any measurable set, thus showing that the subclass of deterministic schedulers suffices to attain the worst-case probability. Traditional schedulers are a particular case of distributed schedulers. So, since our result holds for any measurable set, our proof generalizes the well-known result that randomization adds no extra power to schedulers when trying to maximize the probability of an ω-regular language. However, non-Markovian schedulers are needed to attain supremum probabilities in distributed systems.We develop another class of schedulers (the strongly distributed schedulers) that restricts the nondeterminism concerning the order in which components execute. We compare this class against previous approaches in the same direction, showing that our definition is an important contribution. For this class, we show that randomized and non-Markovian schedulers are needed to attain worst-case probabilities.We also discuss the subclass of finite-memory schedulers, showing the intractability of the model checking problem for these schedulers.     

Automated constraint-based addition of nonmasking and stabilizing fault-tolerance

We focus on the constraint-based automated addition of nonmasking and stabilizing fault-tolerance to hierarchical programs. We specify legitimate states of the program in terms of constraints that should be satisfied in those states. To deal with faults that may violate these constraints, we add recovery actions while ensuring interference freedom among the recovery actions added for satisfying different constraints. Since the constraint-based manual design of fault-tolerance is well known, we expect our approach to have a significant benefit in automating the addition of fault-tolerance. We illustrate our algorithm with four case studies: stabilizing mutual exclusion, stabilizing diffusing computation, a data dissemination problem in sensor networks, and tree maintenance. With experimental results, we show that the complexity of our algorithm is reasonable and that it can be reduced using the structure of the hierarchical systems.We also reduced the time complexity of the synthesis using parallelism. We consider two approaches to speedup the synthesis algorithm: first, the use of the multiple constraints that have to be satisfied during synthesis; second, the use of the distributed nature of the programs being synthesized. We show that our approaches provide significant reduction in the synthesis time.To our knowledge, this is the first instance where automated synthesis has been successfully used in synthesizing programs that are correct under fairness assumptions. Moreover, in three of the case studies considered in this paper, the structure of the recovery paths is too complex to permit existing heuristic-based approaches for adding recovery.     

分布式数据库中一致性与可用性的关系

随着各类应用在数据量和业务量上的扩展,单机数据库系统越发难以应对现实需求。分布式数据库能够根据业务的需求动态地扩容,因此逐步开始受到应用的青睐。近年来,分布式数据库产品层出不穷,并在互联网应用中被大量投入使用。然而,分布式数据库的系统复杂度前所未有。为了让系统可用,设计者需要在多种属性中作合理选择和折中。这造成现有的数据库产品形态各异、优缺点对比分明。至今为止,尚未有人对分布式数据库的设计空间和折中方案进行过深入分析和整理。本文作者在对多个分布式数据库产品进行深入理解之后认识到：分布式数据库系统的设计方案可以通过三个属性进行基本刻画–操作一致性、事务一致性和系统可用性。虽然这三个属性并不新颖,但它们在数据库语境下的含义在文献中尚未得到充分澄清。本文对这三个属性进行澄清,并通过它们对典型数据库产品的格局进行概括、对现有的分布式数据库技术进行综述。此外,本文还对这三个属性之间的相互关系进行深入分析,以期帮助未来的开发者在分布式数据库的设计过程中作出合理选择。     

Distributed Bayesian diagnosis for modular assembly systems—A case study

The growing interest in modular and distributed approaches for the design and control of intelligent manufacturing systems gives rise to new challenges. One of the major challenges that have not yet been well addressed is monitoring and diagnosis in distributed manufacturing systems. In this paper we propose the use of a multi-agent Bayesian framework known as Multiply Sectioned Bayesian Networks (MSBNs) as the basis for multi-agent distributed diagnosis in modular assembly systems. We use a close-to-industry case study to demonstrate how MSBNs can be used to build component-based Bayesian sub-models, how to verify the resultant models, and how to compile the multi-agent models into runtime structures to allow consistent multi-agent belief update and inference.     

Modeling of distributed parameter systems for applications—A synthesized review from time–space separation

Many industrial processes belong to distributed parameter systems (DPS) that have strong spatial–temporal dynamics. Modeling of DPS is difficult but essential to simulation, control and optimization. The first-principle modeling for known DPS often leads to the partial differential equation (PDE). Because it is an infinite-dimensional system, the model reduction (MR) is very necessary for real implementation. The model reduction often works with selection of basis functions (BF). Combination of different BF and MR results in different approaches. For unknown DPS, system identification is usually used to figure out unknown structure and parameters. Using various methods, different approaches are developed. Finally, a novel kernel-based approach is proposed for the complex DPS. This paper provides a brief review of different DPS modeling methods and categorizes them from the view of time–space separation.     

Modeling parallel and distributed systems with finite workloads

In studying or designing parallel and distributed systems one should have available a robust analytical model that includes the major parameters that determine the system performance. Jackson networks have been very successful in modeling computer systems. However, the ability of Jackson networks to predict performance with system changes remains an open question, since they do not apply to systems where there are population size constraints. Also, the product-form solution of Jackson networks assumes steady-state and exponential service centers or certain specialized queueing discipline. In this paper, we present a transient model for Jackson networks that is applicable to any population size and any finite workload (no new arrivals). Using several non-exponential distributions we show to what extent the exponential distribution can be used to approximate other distributions and transient systems with finite workloads. When the number of tasks to be executed is large enough, the model approaches the product-form solution (steady-state solution). We also, study the case where the non-exponential servers have queueing (Jackson networks cannot be applied). Finally, we show how to use the model to analyze the performance of parallel and distributed systems.     

Semi-supervised machine learning approach for DDoS detection

Even though advanced Machine Learning (ML) techniques have been adopted for DDoS detection, the attack remains a major threat of the Internet. Most of the existing ML-based DDoS detection approaches are under two categories: supervised and unsupervised. Supervised ML approaches for DDoS detection rely on availability of labeled network traffic datasets. Whereas, unsupervised ML approaches detect attacks by analyzing the incoming network traffic. Both approaches are challenged by large amount of network traffic data, low detection accuracy and high false positive rates. In this paper we present an online sequential semi-supervised ML approach for DDoS detection based on network Entropy estimation, Co-clustering, Information Gain Ratio and Exra-Trees algorithm. The unsupervised part of the approach allows to reduce the irrelevant normal traffic data for DDoS detection which allows to reduce false positive rates and increase accuracy. Whereas, the supervised part allows to reduce the false positive rates of the unsupervised part and to accurately classify the DDoS traffic. Various experiments were performed to evaluate the proposed approach using three public datasets namely NSL-KDD, UNB ISCX 12 and UNSW-NB15. An accuracy of 98.23%, 99.88% and 93.71% is achieved for respectively NSL-KDD, UNB ISCX 12 and UNSW-NB15 datasets, with respectively the false positive rates 0.33%, 0.35% and 0.46%.