Bounded cost algorithms for multivalued consensus using binary consensus instances

In this paper, we present two bounded cost algorithms that solve multivalued consensus using binary consensus instances. Our first algorithm uses log₂n number of binary consensus instances where n is the number of processes, while our second algorithm uses at most binary consensus instances, where is the maximum length of the binary representation of all proposed values in the run. Both algorithms are significant improvements over the previous algorithm in [A. Mostefaoui, M. Raynal, F. Tronel, From binary consensus to multivalued consensus in asynchronous message-passing systems, Information Processing Letters 73 (5–6) (2000) 207–212], where the number of binary consensus instances needed to solve one multivalued consensus is unbounded.     

The k-simultaneous consensus problem

This paper introduces and investigates the k-simultaneous consensus task: each process participates at the same time in k independent consensus instances until it decides in any one of them. It is shown that the k-simultaneous consensus task is equivalent to the k-set agreement task in the wait-free read/write shared memory model, and furthermore k-simultaneous consensus possesses properties that k-set does not. In particular we show that the multivalued version and the binary version of the k-simultaneous consensus task are wait-free equivalent. These equivalences are independent of the number of processes. Interestingly, this provides us with a new characterization of the k-set agreement task that is based on the fundamental binary consensus problem.     

Consensus-based fault-tolerant total order multicast

While total order broadcast (or atomic broadcast) primitives have received a lot of attention, this paper concentrates on total order multicast to multiple groups in the context of asynchronous distributed systems in which processes may suffer crash failures. “Multicast to Multiple Groups” means that each message is sent to a subset of the process groups composing the system, distinct messages possibly having distinct destination groups. “Total Order” means that all message deliveries must be totally ordered. This paper investigates a consensus-based approach to solve this problem and proposes a corresponding protocol to implement this multicast primitive. This protocol is based on two underlying building blocks, namely, uniform reliable multicast and uniform consensus. Its design characteristics lie in the two following properties. The first one is a minimality property, more precisely, only the sender of a message and processes of its destination groups have to participate in the total order multicast of the message. The second property is a locality property: No execution of a consensus has to involve processes belonging to distinct groups (i.e., consensus is executed on a “per group” basis). This locality property is particularly useful when one is interested in using the total order multicast primitive in large-scale distributed systems. In addition to a correctness proof, an improvement that reduces the cost of the protocol is also suggested     

Bandwidth Efficient All-to-All Broadcast on Switched Clusters

Clusters of workstations employ flexible topologies: regular, irregular, and hierarchical topologies have been used in such systems. The flexibility poses challenges for developing efficient collective communication algorithms since the network topology can potentially have a strong impact on the communication performance. In this paper, we consider the all-to-all broadcast operation on clusters with cut-through and store-and-forward switches. We show that near-optimal all-to-all broadcast on a cluster with any topology can be achieved by only using the links in a spanning tree of the topology when the message size is sufficiently large. The result implies that increasing network connectivity beyond the minimum tree connectivity does not improve the performance of the all-to-all broadcast operation when the most efficient topology specific algorithm is used. All-to-all broadcast algorithms that achieve near-optimal performance are developed for clusters with cut-through and clusters with store-and-forward switches. We evaluate the algorithms through experiments and simulations. The empirical results confirm our theoretical finding.     

Open consensus

This paper presents the abstraction of open consensus and argues for its use as an effective component for building reliable agreement protocols in practical asynchronous systems where processes and links can crash and recover. The specification of open consensus has a decoupled, on‐demand and re‐entrant flavour that make its use very efficient, especially in terms of forced logs, which are known to be major sources of overhead in distributed systems. We illustrate the use of open consensus as a basic building block to develop a modular, yet efficient, total‐order broadcast protocol. Finally, we describe our Java implementation of our open‐consensus abstraction and we convey our efficiency claims through some practical performance measures. Copyright © 2001 John Wiley & Sons, Ltd.     

Atomic broadcast in asynchronous crash-recovery distributed systems and its use in quorum-based replication

Atomic broadcast is a fundamental problem of distributed systems: It states that messages must be delivered in the same order to their destination processes. This paper describes a solution to this problem in asynchronous distributed systems in which processes can crash and recover. A consensus-based solution to atomic broadcast problem has been designed by Chandra and Toueg for asynchronous distributed systems where crashed processes do not recover. We extend this approach: it transforms any consensus protocol suited to the crash-recovery model into an atomic broadcast protocol suited to the same model. We show that atomic broadcast can be implemented requiring few additional log operations in excess of those required by the consensus. The paper also discusses how additional log operations can improve the protocol in terms of faster recovery and better throughput. To illustrate the use of the protocol, the paper also describes a solution to the replica management problem in asynchronous distributed systems in which processes can crash and recover. The proposed technique makes a bridge between established results on weighted voting and recent results on the consensus problem.     

Broadcast protocols for distributed systems

An innovative approach is presented to the design of fault-tolerant distributed systems that avoids the several rounds of message exchange required by current protocols for consensus agreement. The approach is based on broadcast communication over a local area network, such as an Ethernet or a token ring, and on two novel protocols, the Trans protocol, which provides efficient reliable broadcast communication, and the Total protocol, which with high probability promptly places a total order on messages and achieves distributed agreement even in the presence of fail-stop, omission, timing, and communication faults. Reliable distributed operations, such as locking, update, and commitment, typically require only a single broadcast message rather than the several tens of messages required by current algorithms     

Logic Minimization as an Efficient Means of Fuzzy Structure Discovery

Established methods of Boolean minimization have previously unseen potential as an efficient and unrestricted means of fuzzy structure discovery, becoming particularly useful within a design methodology for the automatic development of fuzzy models. Traditionally used in digital systems design, logic minimization tools allow us to exploit the fundamental links between binary (two-valued) and fuzzy (multivalued) logic. In this paper, we show how logic optimization plays an integral role in a two-phase fuzzy model design process. Adaptive logic processing is realized as the discovered Boolean structures are augmented with fuzzy granules and then refined by adjusting connections of fuzzy neurons, helping to further capture the numeric details of the target systems behavior. Accurate and highly interpretable fuzzy models are the result of the entire development process.     

Interleaved all-to-all reliable broadcast on meshes and hypercubes

All-to-all (ATA) reliable broadcast is the problem of reliably distributing information from every node to every other node in point-to-point interconnection networks. A good solution to this problem is essential for clock synchronization, distributed agreement, etc. We propose a novel solution in which the reliable broadcasts from individual nodes are interleaved in such a manner that no two packets contend for the same link at any given time-this type of method is particularly suited for systems which use virtual cut-through or wormhole routing for fast communication between nodes. Our solution, called the IHC Algorithm, can be used on a large class of regular interconnection networks including regular meshes and hypercubes. By adjusting a parameter η referred to as the interleaving distance, we can flexibly decrease the link utilization of the IHC algorithm (for normal traffic) at the expense of an increase in the time required for ATA reliable broadcast. We compare the IHC algorithm to several other possible virtual cut-through solutions and a store-and-forward solution. The IHC algorithm with the minimum value of η is shown to be optimal in minimizing the execution time of ATA reliable broadcast when used in a dedicated mode (with no other network traffic)     

Boolean vector algebraic structures: properties and applications to digital logic simulation

Boolean algebra is the basic mathematic used in the analysis and synthesis of binary systems. Technological advances have led to an increasing interest in multivalued logic systems where more than two logical values are used.In the application of multivalued logic, each logical value could often be represented by a Boolean vector, ie a vector with binary components (0 or 1). Therefore, it is quite important to have a thorough understanding of properties embedded in the algebraic structures using Boolean vectors as basic operands. This gives the motivation for this study.Boolean vector operations are introduced and two major modes associated with the complement are characterized. Then we define a Boolean vector E-algebra and its major features are given. Finally, some applications are discussed and illustrated.     

Streets of Byzantium: Network Architectures for Fast Reliable Broadcasts

A site broadcasting its local value to all other sites ina fault-prone environment is a fundamental paradigm in constructing reliable distributed systems. Time complexity lower bounds and network connectivity requirements for reliable broadcast protocols in point-to-point communication networks are well known. In this paper, we consider the reliable broadcast problem in distributed systems with broadcast networks (for example, Ethernets) as the basic communication architecture. We show how properties of such network architectures can be used to effectively restrict the externally visible behavior of faulty processors. We use these techniques to derive simple protocols that implement reliable broadcast in only two rounds, independent of the failure upper bounds.     

Chasing the Weakest System Model for Implementing Ω and Consensus

Aguilera et al. and Malkhi et al. presented two system models, which are weaker than all previously proposed models where the eventual leader election oracle Ω can be implemented, and thus, consensus can also be solved. The former model assumes unicast steps and at least one correct process with f outgoing eventually timely links, whereas the latter assumes broadcast steps and at least one correct process with f bidirectional but moving eventually timely links. Consequently, those models are incomparable. In this paper, we show that Ω can also be implemented in a system with at least one process with f outgoing moving eventually timely links, assuming either unicast or broadcast steps. It seems to be the weakest system model that allows to solve consensus via Ω-based algorithms known so far. We also provide matching lower bounds for the communication complexity of Ω in this model, which are based on an interesting “stabilization property” of infinite runs. Those results reveal a fairly high price to be paid for this further relaxation of synchrony properties.     

Uniform and self-stabilizing token rings allowing unfair daemon

A distributed system consists of a set of processes and a set of communication links, each connecting a pair of processes. A distributed system is said to be self-stabilizing if it converges to a correct system state no matter which system state it starts with. A self-stabilizing system is considered to be an ideal fault tolerant system, since it tolerates any kind and any finite number of transient failures. In this paper, we investigate uniform randomized self-stabilizing mutual exclusion systems on unidirectional rings. As far as deterministic systems are concerned, it is well-known that there is no such system when the number 6 of processes (i.e., ring size) is composite, even if a fair central-daemon (c-daemon) is assumed. A fair daemon guarantees that every process will be selected for activation infinitely many times. As for randomized systems, regardless of the ring size, we can design a self-stabilizing system even for a distributed-daemon (d-daemon). However, every system proposed so far assumes a daemon to be fair, and effectively replies on this assumption. This paper tackles the problem of designing a self-stabilizing system, without assuming the fairness of a daemon. As a result, we present a randomized self-stabilizing mutual exclusion system for any size n (including composite size) of a unidirectional ring. The number of process states of the system is 2(n-1)     

Achieving reliable system performance by fast recovery of branch miss prediction

Today's technology evolution provides users inexpensive and powerful computer systems. However, there are argues that system reliability and fault tolerance is necessary in the systems as well. A proper design for the reliable and fault-tolerant computer system requires a trade-off among cost, reliability, and availability. In this paper, we propose a low-cost recovery scheme for reliable system performance. With this approach, it completely eliminates the roll-back overhead on branch misprediction. Thus, the instruction fetcher does not stop and it fetches instructions from the correct path immediately after the misprediction detected. So, this approach prevents a processor from flushing the pipeline, even under branch misprediction by allowing the instruction fetcher to work continuously. Our approach reduces the branch misprediction penalty for achieving reliable system performance. It instantly reconstructs the map table to any mispredicted branch and it outperforms the conventional RMT by an average of 10.93%.     

Consensus of linear multi‐agent systems with stochastic noises and binary‐valued communications

This article studies consensus problems of discrete‐time linear multi‐agent systems with stochastic noises and binary‐valued communications. Different from quantized consensus of first‐order systems with binary‐valued observations, the quantized consensus of linear multi‐agent systems requires that each agent observes its neighbors' states dynamically. Unlike the existing quantized consensus of linear multi‐agent systems, the information that each agent in this article gets from its neighbors is only binary‐valued. To estimate its neighbors' states dynamically by using the binary‐valued observations, we construct a two‐step estimation algorithm. Based on the estimates, a stochastic approximation‐based distributed control is proposed. The estimation and control are analyzed together in the closed‐loop system, since they are strongly coupled. Finally, it is proved that the estimates can converge to the true states in mean square sense and the states can achieve consensus at the same time by properly selecting the coefficient in the estimation algorithm. Moreover, the convergence rate of the estimation and the consensus speed are both given by O(1/t). The theoretical results are illustrated by simulations.     

欺骗攻击下具备隐私保护的多智能体系统均值趋同控制

针对通信网络遭受欺骗攻击的离散时间多智能体系统,研究其均值趋同和隐私保护问题.首先,考虑链路信道存在窃听者的情形,提出一种基于状态分解思想的分布式网络节点值重构方法,以阻止系统初始信息的泄露.其次,针对所构建的欺骗攻击模型,利用重构后节点状态信息并结合现有的安全接受广播算法,提出一种适用于无向通信网络的多智能体系统均值趋同控制方法.理论分析表明,该方法能够有效保护节点初始状态信息的隐私,并能消除链路中欺骗攻击的影响,实现分布式系统中所有节点以初始值均值趋同.最后,通过数值仿真实验验证了该方法的有效性.     

Cover2

Unreliable failure detectors are abstract devices that, when added to asynchronous distributed systems, enable solving distributed computing problems (e.g., consensus) that otherwise would be impossible to solve in these systems. This paper focuses on two classes of failure detectors defined by Chandra and Toueg, namely, the classes denoted diamP (eventually perfect) and diamS (eventually strong). Both classes include failure detectors that eventually detect permanently all process crashes, but while the failure detectors of diamP eventually make no erroneous suspicions, the failure detectors of diamS are only required to eventually not suspect a single correct process. Informally, in a one-shot agreement problem, a new problem instance is created each time the processes propose new values to be decided on (e.g., consensus is one-shot). In such a context, this paper addresses the following question related to the comparative power of these classes, namely: "Are there one-shot agreement problems that can be solved in asynchronous distributed systems with reliable links but prone to process crash failures augmented with op, but cannot be solved when those systems are augmented with diamS?" Surprisingly, the paper shows that the answer to this question is "no." An important consequence of this result is that diamP cannot be the weakest class of failure detectors that enables solving one-shot agreement problems in unreliable asynchronous distributed systems     

A simple and fast asynchronous consensus protocol based on a weak failure detector

Summary. The Consensus problem is a fundamental paradigm for fault-tolerant asynchronous systems. It abstracts a family of problems known as Agreement (or Coordination) problems. Any solution to consensus can serve as a basic building block for solving such problems (e.g., atomic commitment or atomic broadcast). Solving consensus in an asynchronous system is not a trivial task: it has been proven (1985) by Fischer, Lynch and Paterson that there is no deterministic solution in asynchronous systems which are subject to even a single crash failure. To circumvent this impossibility result, Chandra and Toueg have introduced the concept of unreliable failure detectors (1991), and have studied how these failure detectors can be used to solve consensus in asynchronous systems with crash failures. This paper presents a new consensus protocol that uses a failure detector of the class . Like previous protocols, it is based on the rotating coordinator paradigm and proceeds in asynchronous rounds. Simplicity and efficiency are the main characteristics of this protocol. From a performance point of view, the protocol is particularly efficient when, whether failures occur or not, the underlying failure detector makes no mistake (a common case in practice). From a design point of view, the protocol is based on the combination of three simple mechanisms: a voting mechanism, a small finite state automaton which manages the behavior of each process, and the possibility for a process to change its mind during a round. Received: August 1997 / Accepted: March 1999     

Techniques for Classifying Executions of Deployed Software to Support Software Engineering Tasks

There is an increasing interest in techniques that support analysis and measurement of fielded software systems. These techniques typically deploy numerous instrumented instances of a software system, collect execution data when the instances run in the field, and analyze the remotely collected data to better understand the system's in-the-field behavior. One common need for these techniques is the ability to distinguish execution outcomes (e.g., to collect only data corresponding to some behavior or to determine how often and under which condition a specific behavior occurs). Most current approaches, however, do not perform any kind of classification of remote executions and either focus on easily observable behaviors (e.g., crashes) or assume that outcomes' classifications are externally provided (e.g., by the users). To address the limitations of existing approaches, we have developed three techniques for automatically classifying execution data as belonging to one of several classes. In this paper, we introduce our techniques and apply them to the binary classification of passing and failing behaviors. Our three techniques impose different overheads on program instances and, thus, each is appropriate for different application scenarios. We performed several empirical studies to evaluate and refine our techniques and to investigate the trade-offs among them. Our results show that 1) the first technique can build very accurate models, but requires a complete set of execution data; 2) the second technique produces slightly less accurate models, but needs only a small fraction of the total execution data; and 3) the third technique allows for even further cost reductions by building the models incrementally, but requires some sequential ordering of the software instances' instrumentation.     

A survey of inter-flow network coding in wireless mesh networks with unicast traffic

Wireless network performance is much restricted by the unreliability of the wireless channel and the competition among different flows for the shared network resources such as the bandwidth. Network coding is a technique that exploits the broadcast of the wireless channel and can effectively address these two restrictions to improve network performance. For example, with network coding, an intermediate node of multiple flows can encode packets from these flows into one mixed packet and serve these flows using only one transmission instead of multiple transmissions in the traditional way, thus mitigating the competition among flows. Inter-flow network coding (XNC), as a form of network coding, considers encoding packets from different flows, and it can benefit wireless mesh networks (WMNs) with either reliable or lossy links. In this paper, we present a survey on XNC in WMNs for unicast traffic, with various design factors related to XNC being covered. Specifically, our survey considers two types of WMNs, one with reliable links and the other with lossy links, and we study how XNC can be effectively utilized in both two types of WMNs. In addition to the benefits of XNC, we also present in this survey some drawbacks of applying XNC in WMNs. With this paper, we believe that readers will have a more thorough understanding of XNC on how it effectively mitigates the resource competition among flows and the channel unreliability problem in WMNs.