Network Topology And Fault Tolerant Consensus

As the structure of contemporary communication networks grows more complex, practical networked distributed systems become prone to component failures. Fault-tolerant consensus in message-passing systems allows participants in the system to agree on a common value despite the malfunction or misbehavior of some components. It is a task of fundamental importance for distributed computing, due to its numerous applications. We summarize studies on the topological conditions that determine the feasibility of consensus, mainly focusing on directed networks and the case of restricted topology knowledge at each participant. Recently, significant efforts have been devoted to fully characterize the underlying communication networks in which variations of fault-tolerant consensus can be achieved. Although the deduction of analogous topological conditions for undirected networks of known topology had shortly followed the introduction of the problem, their extension to the directed network case has been proven a highly non-trivial task. Moreover, global knowledge restrictions, inherent in modern large-scale networks, require more elaborate arguments concerning the locality of distributed computations. In this work, we present the techniques and ideas used to resolve these issues. Recent studies indicate a number of parameters that affect the topological conditions under which consensus can be achieved, namely, the fault model, the degree of system synchrony (synchronous vs. asynchronous), the type of agreement (exact vs. approximate), the level of topology knowledge, and the algorithm class used (general vs. iterative). We outline the feasibility and impossibility results for various combinations of the above parameters, extensively illustrating the relation between network topology and consensus.

This SpringerBrief presents a survey of data center network designs and topologies and compares several properties in order to highlight their advantages and disadvantages. The brief also explores several routing protocols designed for these topologies and compares the basic algorithms to establish connections, the techniques used to gain better performance, and the mechanisms for fault-tolerance. Readers will be equipped to understand how current research on data center networks enables the design of future architectures that can improve performance and dependability of data centers. This concise brief is designed for researchers and practitioners working on data center networks, comparative topologies, fault tolerance routing, and data center management systems. The context provided and information on future directions will also prove valuable for students interested in these topics.

Real-time computer systems are very often subject to dependability requirements because of their application areas. Fly-by-wire airplane control systems, control of power plants, industrial process control systems and others are required to continue their function despite faults. Fault-tolerance and real-time requirements thus constitute a kind of natural combination in process control applications. Systematic fault-tolerance is based on redundancy, which is used to mask failures of individual components. The problem of replica determinism is thereby to ensure that replicated components show consistent behavior in the absence of faults. It might seem trivial that, given an identical sequence of inputs, replicated computer systems will produce consistent outputs. Unfortunately, this is not the case. The problem of replica non-determinism and the presentation of its possible solutions is the subject of Fault-Tolerant Real-Time Systems: The Problem of Replica Determinism. The field of automotive electronics is an important application area of fault-tolerant real-time systems. Systems like anti-lock braking, engine control, active suspension or vehicle dynamics control have demanding real-time and fault-tolerance requirements. These requirements have to be met even in the presence of very limited resources since cost is extremely important. Because of its interesting properties Fault-Tolerant Real-Time Systems gives an introduction to the application area of automotive electronics. The requirements of automotive electronics are a topic of discussion in the remainder of this work and are used as a benchmark to evaluate solutions to the problem of replica determinism.

The major objective of this book is to introduce advanced design and (online) optimization methods for fault diagnosis and fault-tolerant control from different aspects. Under the aspect of system types, fault diagnosis and fault-tolerant issues are dealt with for linear time-invariant and time-varying systems as well as for nonlinear and distributed (including networked) systems. From the methodological point of view, both model-based and data-driven schemes are investigated.To allow for a self-contained study and enable an easy implementation in real applications, the necessary knowledge as well as tools in mathematics and control theory are included in this book. The main results with the fault diagnosis and fault-tolerant schemes are presented in form of algorithms and demonstrated by means of benchmark case studies. The intended audience of this book are process and control engineers, engineering students and researchers with control engineering background.

Theory is what remains true when technology is changing. So, it is important to know and master the basic concepts and the theoretical tools that underlie the design of the systems we are using today and the systems we will use tomorrow. This means that, given a computing model, we need to know what can be done and what cannot be done in that model. Considering systems built on top of an asynchronous read/write shared memory prone to process crashes, this monograph presents and develops the fundamental notions that are universal constructions, consensus numbers, distributed recursivity, power of the BG simulation, and what can be done when one has to cope with process anonymity and/or memory anonymity. Numerous distributed algorithms are presented, the aim of which is being to help the reader better understand the power and the subtleties of the notions that are presented. In addition, the reader can appreciate the simplicity and beauty of some of these algorithms.

Providing a shared memory abstraction in distributed systems is a powerful tool that can simplify the design and implementation of software systems for networked platforms. This enables the system designers to work with abstract readable and writable objects without the need to deal with the complexity and dynamism of the underlying platform. The key property of shared memory implementations is the consistency guarantee that it provides under concurrent access to the shared objects. The most intuitive memory consistency model is atomicity because of its equivalence with a memory system where accesses occur serially, one at a time. Emulations of shared atomic memory in distributed systems is an active area of research and development. The problem proves to be challenging, and especially so in distributed message passing settings with unreliable components, as is often the case in networked systems. We present several approaches to implementing shared memory services with the help of replication on top of message-passing distributed platforms subject to a variety of perturbations in the computing medium.