Design of decentralized reliable controllers for large-scale systems

A methodology is developed in this paper for the design of decentralized reliable controllers for large-scale systems. The overall system is decomposed into a group of interconnected subsystems for which local decentralized controllers are designed to ensure the reliability of the overall system, taking into consideration the effect of changes in the system components characteristics and the system structure. The design procedure allows us to find a lower limit for the degree of stability of the subsystems under a wide range of environmental conditions. Finally, the developed methodology is illustrated through a case study.     

不确定关联大系统鲁棒分散可靠H∞控制

针对一类具有不确定性关联大系统,研究其鲁棒分散可靠状态反馈H∞控制器的设计方法.采用线性矩阵不等式的方法,给出了当控制器在规定范围内的一部分失效时控制器存在的充分条件,并能保证闭环系统可靠稳定和具有一定的H∞性能.仿真例子说明了方法的有效性.     

Comments on ‘Design of decentralized reliable controllers for large-scale systems’

It is pointed out that the design algorithm given by Darwish and Soliman (1988) in the title paper is improper.     

Probabilistic flooding for efficient information dissemination in random graph topologies

Probabilistic flooding has been frequently considered as a suitable dissemination information approach for limiting the large message overhead associated with traditional (full) flooding approaches that are used to disseminate globally information in unstructured peer-to-peer and other networks. A key challenge in using probabilistic flooding is the determination of the forwarding probability so that global network outreach is achieved while keeping the message overhead as low as possible. In this paper, by showing that a probabilistic flooding network, generated by applying probabilistic flooding to a connected random graph network, can be (asymptotically) “bounded” by properly parameterized random graph networks and by invoking random graph theory results, asymptotic values of the forwarding probability are derived guaranteeing (probabilistically) successful coverage, while significantly reducing the message overhead with respect to traditional flooding. Asymptotic expressions with respect to the average number of messages and the average time required to complete network coverage are also derived, illustrating the benefits of the properly parameterized probabilistic flooding scheme. Simulation results support the claims and expectations of the analytical results and reveal certain aspects of probabilistic flooding not covered by the analysis.     

Probabilistic multi-knowledge-base systems

This article lays the groundwork for theprobabilistic multi-knowledge-base system (PMKBS), a new decision aid specifically tailored to the needs of a decision-maker faced with the derivation of a consensus diagnosis. In this article, we develop the PMKBS architecture in several ways. First, we define the basic problem that it addresses, and review the fundamental tools upon which it is based. Next, we describe its underlying theory, and explain how some general elicitation and modeling procedures form a viable design paradigm. Finally, we describe a small family of prototype PMKBSs that address problems related to pathologies of the lymph system, and evaluate their performance. Taken together, these discussions and prototypes demonstrate that the PMKBS architecture appears to be flexible, practical, and powerful.     

Epidemic information dissemination in distributed systems

Easy to deploy, robust, and highly resilient to failures, epidemic algorithms are a potentially effective mechanism for propagating information in large peer-to-peer systems deployed on Internet or ad hoc networks. It is possible to adjust the parameters of epidemic algorithm to achieve high reliability despite process crashes and disconnections, packet losses, and a dynamic network topology. Although researchers have used epidemic algorithms in applications such as failure detection, data aggregation, resource discovery and monitoring, and database replication, their general applicability to practical, Internet-wide systems remains open to question. We describe four key problems: membership maintenance, network awareness, buffer management, and message filtering, and suggest some preliminary approaches to address them.     

Probabilistic clock synchronization in distributed systems

Presents and analyzes a new probabilistic clock synchronization algorithm that can guarantee a much smaller bound on the clock skew than most existing algorithms. The algorithm is probabilistic in the sense that the bound on the clock skew that it guarantees has a probability of invalidity associated with it. However, the probability of invalidity may be made extremely small by transmitting a sufficient number of synchronization messages. It is shown that an upper bound on the probability of invalidity decreases exponentially with the number of synchronization messages transmitted. A closed-form expression that relates the probability of invalidity to the clock skew and the number of synchronization messages is also derived     

Pilot implementations of reliable systems

This paper describes the pilot implementation of a modifiable reliable system. On the basis of this work, we have been led to conclusions on necessary hardware and software features for supporting a reliable system, techniques for building such systems, and the scope of the results to be expected from a pilot implementation.     

Design of reliable control systems

A methodology for the design of reliable centralized and decentralized control systems is developed. The resulting control systems are reliable in that they provide guaranteed stability and H _∞ performance not only when all control components are operational, but also for sensor or actuator outages in the centralized case, or for control-channel outages in the decentralized case. Reliability is guaranteed provided these outages occur only within a prespecified subset of control components. Strongly stabilizing designs are also developed, for both centralized and decentralized systems     

Probabilistic quorums for dynamic systems

A quorum system is a set of sets such that every two sets in the quorum system intersect. Quorum systems are well known building blocks for maintaining information in a distributed system while providing high availability and good load balance. Probabilistic Quorum Systems (PQS) are variants of quorum systems that relax the strict intersection requirement. They are particularly attractive for large scale systems due to their simplicity and highly efficient availability—load balance tradeoff. We introduce scalable techniques that maintain a PQS in a highly decentralized and highly dynamic setting. We address two challenges. First we show how PQS can be realized efficiently even when each process maintains knowledge of only a constant number of other members. Second, we provide algorithms that adaptively evolve the quorums to adjust to the changes in the system caused by processes leaving and joining the system over time.     

Probabilistic models of computer systems

Summary In this paper we examine certain problems related to the use of diffusion approximations for the approximate modelling of computer systems. In particular we develop a model which allows us to handle waiting times and batch arrivals: these results are a new approach to the use of diffusion approximations. We also examine the effect of the distribution of holding times at boundaries: this question had remained open in earlier studies. We show that the stationary distributions associated with these diffusion models depend only on the average residence time of the process on the boundaries and not on the complete distribution function. This result justifies the use of exponential holding times as had been done in an earlier study.     

Independent recovery in large-scale distributed systems

In large systems, replication can become important means to improve data access times and availability. Existing recovery protocols, on the other hand, were proposed for small-scale distributed systems. Such protocols typically update stale, newly-recovered sites with replicated data and resolve the commit uncertainty of recovering sites. Thus, given that in large systems failures are more frequent and that data access times are costlier, such protocols can potentially introduce large overheads in large systems and must be avoided, if possible. We call these protocols dependent recovery protocols since they require a recovering site to consult with other sites. Independent recovery has been studied in the context of one-copy systems and has been proven unattainable. This paper offers independent recovery protocols for large-scale systems with replicated data. It shows how the protocols can be incorporated into several well-known replication protocols and proves that these protocols continue to ensure data consistency. The paper then addresses the issue of nonblocking atomic commitment. It presents mechanisms which can reduce the overhead of termination protocols and the probability of blocking. Finally, the performance impact of the proposed recovery protocols is studied through the use of simulation and analytical studies. The results of these studies show that the significant benefits of independent recovery can be enjoyed with a very small loss in data availability and a very small increase in the number of transaction abortions     

Decentralized state estimation in large-scale systems

A novel approach to decentralized state estimation in a large-scale interconnected system is proposed. The method assumes a known model for the local subsystem only, and therefore is suitable when the other subsystem models and the interaction matrices are partially or totally unknown. An innovation representation suitable for decentralized subsystem state estimation is derived. The state estimation problem is then solved through the parametric identification of the innovation representation. The identification algorithm is based upon a pseudo-linear regression (PLR) principle that attempts minimization of the innovation variances.     

Load balancing in large-scale RFID systems

A radio frequency identifier (RFID) system consists of inexpensive, uniquely-identifiable tags that are mounted on physical objects, and readers that track these tags (and hence these physical objects) through RF communication. For many performance measures in large-scale RFID systems, the set of tags to be monitored needs to be properly balanced among all readers. In this paper we, therefore, address this load balancing problem for readers — how should a given set of tags be assigned to readers such that the cost for monitoring tags across the different readers is balanced, while guaranteeing that each tag is monitored by at least one reader. We first present centralized solutions to two different variants of this load balancing problem: (i) min–max cost assignment (MCA), and (ii) min–max tag count assignment (MTA). We show that MCA, the generalized variant of the load balancing problem, is NP-hard and hence present a 2-approximation algorithm for it. We next present an optimal centralized solution for MTA, an important specialized variant of the problem. Subsequently, we present a localized distributed algorithm that is probabilistic in nature and closely matches the performance of the centralized algorithms. Finally we present detailed simulation results that illustrate the performance of the localized distributed approach, how it compares with the centralized optimal and near-optimal solutions, and how it adapts the solution with changes in tag distribution and reader topology. Our results demonstrate that our schemes achieve very good performance even in highly dynamic large-scale RFID systems.     

Probabilistic system opacity in discrete event systems

In many emerging security applications, a system designer frequently needs to ensure that a certain property of a given system (that may reveal important details about the system’s operation) be kept secret (opaque) to outside observers (eavesdroppers). Motivated by such applications, several researchers have formalized, analyzed, and described methods to verify notions of opacity in discrete event systems of interest. This paper introduces and analyzes a notion of opacity in systems that can be modeled as probabilistic finite automata or hidden Markov models. We consider a setting where a user needs to choose a specific hidden Markov model (HMM) out of m possible (different) HMMs, but would like to “hide” the true system from eavesdroppers, by not allowing them to have an arbitrary level of confidence as to which system has been chosen. We describe necessary and sufficient conditions (that can be checked with polynomial complexity), under which the intruder cannot distinguish the true HMM, namely, the intruder cannot achieve a level of certainty about its decision, which is above a certain threshold that we can a priori compute.     

Software development for reliable software systems

The process of software development has a major influence on the reliability of a software system. The reliability of a software system can be improved by eliminating all the errors that occur during its development. This paper presents, from a tutorial point of view, a methodology of software development that can minimize the number of errors in a system when the system is being developed. The three phases of software development viz. requirements analysis, design, and implementation are examined to find out what needs to be done in each phase, how the end result of each phase can be verified for correctness, and how the form in which information is passed between each phase can be improved. This discussion is directly applicable to the development of small software systems and programs.     

广义系统H∞可靠性控制

通过对更一般形式的执行器和传感器故障模型分析,研究了广义系统基于观测器的H∞可靠性控制器设计问题.利用带有约束的广义代数Riccati不等式(GARI),给出执行器故障情况下,广义系统H∞可靠性控制器存在的充要条件和设计方法,以及传感器故障情况下,广义系统H∞可靠性控制器存在的充分条件和设计方法.所设计的H∞可靠性控制器使得闭环广义系统容许且传递函数的H∞范数有界.同时,还将带广义约束的GARI转化成了线性矩阵不等式(LMI),进而简化了广义系统H∞可靠性控制器设计方法.     

Designing reliable systems with unreliable components

Many electronics experts predicted that component failures (in particular, tube failures) in the pioneering ENIAC machine would be so frequent that the machine would never be useful. But the engineers (system architects) and component manufacturers improved their art over time to improve the system’s availability. Their achievement of remarkably low failure rates should serve as an inspiration to chip- and system-level designers today. Three articles in this general issue of IEEE Micro address the challenge of reliable designs of the future.     

On built-in test techniques in reliable computer systems

Reliability is a primary criterion in the design of computer systems both from the points of view of fault tolerance and of repair, but the major difference lies in the relative cost constraints. Built-in test (BIT) techniques exploit hardware redundancy to provide continuous on-line monitoring of computer performance. Hardware's declining cost makes these techniques attractive, especially for modular computers. For both users and designers, it is important to understand the potential effectiveness of BIT approaches in terms of cost and performance. To assure BIT effectiveness, a computer BIT approach that supports the applicable system maintenance concepts must be selected, and required integral testing resources must be identified. This paper summarises present BIT approaches, discusses systematic ways to incorporate BIT into new computer designs and describes techniques for assessing BIT effectiveness in modular digital computers.