Byzantine agreement in the presence of mixed faults on processorsand links

In early stage, the Byzantine agreement (BA) problem was studied with single faults on processors in either a fully connected network or a nonfully connected network. Subsequently, the single fault assumption was extended to mixed faults (also referred to as hybrid fault model) on processors. For the case of both processor and link failures, the problem has been examined in a fully connected network with a single faulty type, namely an arbitrary fault. To release the limitations of a fully connected network and a single faulty type, the problem is reconsidered in a general network. The processors and links in such a network can both be subjected to different types of fault simultaneously. The proposed protocol uses the minimum number of message exchanges and can tolerate the maximum number of allowable faulty components to make each fault-free processor reach an agreement     

The anatomy study of consensus agreement in MANETs

Reliability is an important research topic of distributed systems. To achieve fault-tolerance in the distributed systems, healthy processors need to reach a common agreement before performing certain special tasks, even if faults exist in many circumstances. This problem is called as the Byzantine Agreement (BA) problem and it must be addressed. In general, the traditional BA problem is solved in well-defined networks. However, the MANETs (Mobile Ad-hoc Network) are increasing in popularity and its network topology is dynamic in nature. In this paper, the BA problem is re-examined in MANETs. Our protocol uses the minimum number of message exchanges to reach an agreement within the distributed system while tolerating the maximum number of faulty processors in MANETs.     

Byzantine Agreement in a generalized connected network

Traditionally, the Byzantine Agreement (BA) problem is studied either in a fully connected network or in a broadcast network. A generalized network model for BA is proposed in this paper. A fully-connected network or a broadcast network is a special case of the new network architecture. Under the new generalized network model, the BA problem is reexamined with the assumption of malicious faults on both processors and transmission medium (TM), as opposed to previous studies which consider malicious faults on processors only. The proposed algorithm uses the minimum number of message exchanges, and can tolerate the maximum number of allowable faulty components to make each healthy processor reach a common agreement for the cases of processor failures, TM failures, or processor/TM failures. The results can also be used to solve the interactive consistency problem and the consensus problem     

The incremental agreement

To achieve reliable distributed systems, the fault-tolerance must be studied. One of the most important problems of fault-tolerance issues lies in the Byzantine Agreement (BA) problem. The primary issue surrounding BA is that fault-free processors must obtain common agreement even in cases where faults persist. In this field, the fault diagnosis protocol has been proposed so that each fault-free processor detects/locates a common set of faulty processors. However, in this study, the incremental agreement is invoked to make each processor able to agreement upon executing the fault diagnosis protocol using minimal rounds of message exchange in the presence of dual failure characteristics of processors.     

A new solution for the Byzantine agreement problem

Reliability is an important research topic in distributed computing systems consisting of a large number of processors. To achieve reliability, the fault-tolerance scheme of the distributed computing system must be revised. This kind of problem is known as a Byzantine agreement (BA) problem. It requires all fault-free processors to agree on a common value, even if some components are corrupt. Consequently, there have been significant studies of this agreement problem in distributed systems. However, the traditional BA protocols focus on running ⌊(n−1)/3⌋+1 rounds of message exchange continuously to make each fault-free processor reach an agreement. In other words, since having a large number of messages results in a large protocol overhead, those protocols are inefficient and unreasonable, especially for some network environments which have large number of processors. In this study, we propose a novel and efficient protocol to reduce the number of messages. Our protocol can collect, compare and replace the received values to find the reliable processors and replace the values sent by the unreliable processors. Subsequently, each processor can agree on a common value through three rounds of message exchange. Furthermore, the proposed protocol can use the minimum number of messages to tolerate the maximum number of faulty components in a distributed system.     

Reaching Agreement among Virtual Subnets in Hybrid Failure Mode

Fault-tolerance is an important research topic in the study of distributed systems. To cope with the influence of faulty components, reaching a common agreement in the presence of faults before performing certain tasks is essential. However, the Byzantine Agreement (BA) problem is a fundamental problem in fault-tolerant distributed systems. In previous studies, protocols dealing with the BA problem focused on static networks; however, these do not perform well in dynamically changing mobile networks. The most well known mobile network is the Mobile Ad-hoc Network (MANET). To enhance fault-tolerance and MANET reliability, the BA problem in virtual subnets of MANET is revisited in this paper. The proposed protocol is called the Hybrid Agreement Protocol (HAP). It achieves agreement on a common value among all functional mobile processors in a minimal number of message exchange rounds, and can tolerate a maximal number of allowable faulty components in the virtual subnet of MANET.     

Byzantine Agreement under dual failure mobile network

Networks are trending towards wireless systems that provide support for mobile computing. The Byzantine Agreement (BA) protocols used in static networks do not perform well in a dynamically changing mobile environment. Mobile commerce and related applications are necessary for wireless networks. There are numerous properties in a wireless network that play important roles. For example, the processors in a wireless network have highly mobile capabilities. Processors can immigrate into or move away from the network at any time. Although mobile technology has brought greater convenience, it is comparatively more dangerous. Wireless systems are susceptible to security flaws such as attacks by hackers. The number of allowable faulty components within the system is also decreased. To increase the number of allowable faulty components and ensure network security, a simple, secure and efficient protocol, BAM, is proposed to handle the BA problem. The fault symptoms include malicious and dormant faults. Furthermore, the proposed protocol uses the minimum number of message exchange rounds to make all healthy processors agree on a common value and can tolerate the maximum number of allowable faulty components. The proposed method will also ensure message security and increase the system's fault tolerant capability.     

A FIFO-based multicast network and its use in multicomputers

We present an implementation of a multicast network of processors. The processors are connected in a fully connected network and it is possible to broadcast data in a single instruction. The network works at the processor-memory speed and therefore provides a fast communication link among processors. A number of interesting architectures are possible using such a network. We show some of these architectures which have been implemented and are functional. We also show the system software calls which allow programming of these machines in parallel mode.     

Reaching fault diagnosis agreement on an unreliable general network

Recently, Siu et al. failed in their attempt to use the FDAMIX protocol to eliminate the fault diagnosis agreement (FDA) problem with mixed faults on the processors in a general network. Therefore, in this study, a new protocol, the FDAL protocol, is introduced to solve the FDA problem with mixed faults on the links. The FDAL is capable of detecting/locating faulty links to reconfigure the unreliable general network into a reliable network, and is able to increase the system performance and strengthen network integrity.     

Efficient task migration algorithm for distributed systems

The objective of the study was to achieve balanced load among processors, reduce the communication overhead of the load balancing algorithm, and improve respource utilization, which results in better average resonse time. A communication protocol and a fully distributed algorithm for dynamic load balancing through task migration in a connected N-processor network are presented. Each processor communicates its load directly with only a subset (of the size √ N) of processors, reducing communication traffic and average response time. It is proved that the given algorithm will perform task migration even if there is only one light load processor and one heavy load processor in the system. Simulation results show that the proposed scheme can save up to 60% of the protocol messages used by the broadcast algorithms and can reduce the average response time     

From immediate agreement to eventual agreement: early stopping agreement protocol for dynamic networks with malicious faulty processors

With the rapid advancement of wireless networking technology, networks have evolved from static to dynamic. Reliability of dynamic networks has virtually become an important issue. Fortunately, a solution to the above issue can be derived from solutions to the Byzantine Agreement (BA) problem. BA problem can be solved by protocols that make processors reach an agreement through message exchange. Protocols used to solve the problem can be divided into Immediate Byzantine Agreement (IBA) protocols and Eventual Byzantine Agreement (EBA) protocols. In IBA protocols, the number of rounds of message exchange is determined by the total number of processors in the network. Even if no faulty processor is present in the network, IBA protocols still require a fixed number of rounds of message exchange, causing a waste of time. In contrast, EBA protocols dynamically adjust the number of rounds of message exchange according to the interference of faulty processors. In terms of efficiency, EBA protocols certainly outperform IBA protocols. Due to the fact that the existing EBA protocols have been designed for static networks, they cannot work on dynamic networks. In this paper, we revisit the EBA problem in dynamic networks to increase the reliability of dynamic networks. Simulations will be conducted to validate that the proposed protocol requires the minimum rounds of message exchange and can tolerate the maximum number of malicious faulty processors compared to other existing protocols.     

Optimal task assignment in homogeneous networks

This paper considers the problem of assigning the tasks of a distributed application to the processors of a distributed system such that the sum of execution and communication costs is minimized. Previous work has shown this problem to be tractable for a system of two processors or a linear array of N processors, and for distributed programs of serial parallel structures. Here we focus on the assignment problem on a homogeneous network, which is composed of N functionally-identical processors, each with its own memory. Some processors in the network may have unique resources, such as data files or certain peripheral devices. Certain tasks may have to use these unique resources; they are called attached tasks. The tasks of a distributed program should therefore be assigned so as to make use of specific resources located at certain processors in the network while minimizing the amount of interprocessor communication. The assignment problem in such a homogeneous network is known to be NP-hard even for N=3, thus making it intractable for a network with a medium to large number of processors. We therefore focus on task assignment in general array networks, such as linear arrays, meshes, hypercubes, and trees. We first develop a modeling technique that transforms the assignment problem in an array or tree into a minimum-cut maximum-flow problem. The assignment problem is then solved for a general array or tree network in polynomial time     

Uniform dynamic self-stabilizing leader election

A distributed system is self-stabilizing if it can be started in any possible global state. Once started the system regains its consistency by itself, without any kind of outside intervention. The self-stabilization property makes the system tolerant to faults in which processors exhibit a faulty behavior for a while and then recover spontaneously in an arbitrary state. When the intermediate period in between one recovery and the next faulty period is long enough, the system stabilizes. A distributed system is uniform if all processors with the same number of neighbors are identical. A distributed system is dynamic if it can tolerate addition or deletion of processors and links without reinitialization. In this work, we study uniform dynamic self-stabilizing protocols for leader election under readwrite atomicity. Our protocols use randomization to break symmetry. The leader election protocol stabilizes in O(ΔD log n) time when the number of the processors is unknown and O(ΔD), otherwise. Here Δ denotes the maximal degree of a node, D denotes the diameter of the graph and n denotes the number of processors in the graph. We introduce self-stabilizing protocols for synchronization that are used as building blocks by the leader-election algorithm. We conclude this work by presenting a simple, uniform, self-stabilizing ranking protocol     

Lower bounds for the broadcast problem in mobile radio networks

Summary.  In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol Π, for any n and for any D≦n/2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by Π for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors. Received: August 1994 / Accepted: August 1996     

Termination detection protocols for mobile distributed systems

This paper studies a fundamental problem, the termination detection problem, in distributed systems. Under a wireless network environment, we show how to handle the host mobility and disconnection problems. In particular, when some distributed processes are temporarily disconnected, we show how to capture a weakly terminated state where silence has been reached only by those currently connected processes. A user may desire to know such a state to tell whether the mobile distributed system is still running or is silent because some processes are disconnected. Our protocol tries to exploit the network hierarchy by combining two existing protocols together. It employs the weight-throwing scheme on the wired network side, and the diffusion-based scheme on each wireless cell. Such a hybrid protocol can better pave the gaps of computation and communication capability between static and mobile hosts, thus more scalable to larger distributed systems. Analysis and simulation results are also presented     

The optimal generalized Byzantine Agreement in Cluster-based Wireless Sensor Networks

A Wireless Sensor Network (WSN) is a wireless network consisting of spatially distributed autonomous devices using sensor nodes in a wide range of applications in various domains. In the future, WSNs are expected to be integrated into the “Internet of Things” (IoT), where sensor nodes join the Internet dynamically, and use them to collaborate and accomplish their tasks. Because of the communications of WSN will produce a broadcast storm, the Cluster-based Wireless Sensor Network (CWSN) was proposed to ameliorate the broadcast storm. However, the capability of the fault-tolerance and reliability of CWSNs must be carefully investigated and analyzed. To cope with the influence of faulty components, reaching a common agreement in the presence of faults before performing certain tasks is essential. Byzantine Agreement (BA) problem is a fundamental problem in fault-tolerant distributed systems. To enhance fault-tolerance and reliability of CWSN, the BA problem in CWSN is revisited in this paper. In this paper, a new BA protocol is proposed that adapts to the CWSN and derives its limit of allowable faulty components, while maintaining the minimum number of message exchanges.     

Visiting Byzantine Agreement underlying Ad Hoc environment

The Mobile Ad Hoc Network (MANET) has become more popular because the MANET is a self-organizing, self-configuring, and an instantly deployable multi-hop wireless network that responds to application needs without any fixed infrastructure. Moreover, the MANET is fault-tolerant and reliable. A mechanism is needed in the MANET that allows a set of nodes to agree on a common value. The distributed Byzantine Agreement (BA) problem is one of the most important issues in designing a fault-tolerant system. In many cases, reaching a common agreement among fault-free nodes in coping with the influence from faulty components is crucial in a fault-tolerant system. When a common agreement is achieved, all fault-free nodes in the system can produce stable results without any influence from the faulty components. In this study, the BA problem is visited in a MANET, in which the components are subject to a malicious fault. The proposed protocol can tolerate the maximum number of allowable faulty nodes using a minimum number of message exchange rounds. Each fault-free node can reach a common agreement value for the BA problem in a MANET. The text was submitted by the authors in English.     

The anatomy study of server-initial agreement for general hierarchy wired/wireless networks

The Byzantine Agreement (BA) plays a key role in fault-tolerant distributed system design. A number of solutions to the BA problem based on various network model assumptions have been proposed. However, most existing BA protocols are designed for pure wired or pure wireless networks. In practice, most current networks are combined wired and wireless environments. In this paper, we extend the BA problem over a combined wired/wireless network, consisting of both powerful computing stationary processor and low-power mobile processor. The communication overhead of BA protocol is inherently large and secure group communications are important. The protocols proposed in this paper use the hierarchical model concept to reduce the communication overhead and provide secure group communications well suited for combined wired/wireless networks.     

Distributed computing on oriented anonymous hypercubes with faulty components

We give efficient algorithms for distributed computation on oriented, anonymous, asynchronous hypercubes with possible faulty components (i.e. processors and links) and deterministic processors. Initially, the processors know only the size of the network and that they are inter-connected in a hypercube topology. Faults may occur only before the start of the computation (and that despite this the hypercube remains a connected network). However, the processors do not know where these faults are located. As a measure of complexity we use the total number of bits transmitted during the execution of the algorithm and we concentrate on giving algorithms that will minimize this number of bits. The main result of this paper is an algorithm for computing Boolean functions on anonymous hypercubes with bit cost , where is the number of faulty components (i.e. links plus processors), is the number of links which are either faulty, or non-faulty but adjacent to faulty processors, and is the diameter of the hypercube with faulty components. Received: October 1992 / Accepted: April 2001     

A note on consensus on dual failure modes

F.J. Meyer and D.K. Pradhan (1991) proposed the MS (for “mixed-sum”) algorithm to solve the Byzantine Agreement (BA) problem with dual failure modes: arbitrary faults (Byzantine faults) and dormant faults (essentially omission faults and timing faults). Our study indicates that this algorithm uses an inappropriate method to eliminate the effects of dormant faults and that the bound on the number of allowable faulty processors is overestimated. This paper corrects the algorithm and gives a new bound for the allowable faulty processors