ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 1, с. 134-142
СЛОЖНЫЕ ТЕХНИЧЕСКИЕ СИСТЕМЫ УПРАВЛЕНИЯ, ^^^^ И ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ КОМПЛЕКСЫ
УДК 62-40
VISITING BYZANTINE AGREEMENT UNDERLYING AD HOC ENVIRONMENT
© 2007 r. Kuq-Qin Yan, Shu-Ching Wang*
Taiwan, Chaoyang University of Technology Received January 26.05
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.
Introduction. In recent years, the Mobile Ad Hoc Network (MANET) has enjoyed an amazing rise in popularity. The MANET features are infrastructure less (no access point or base stations, no dedicated routers), automatic adaptation to changes in topology (nodes enter and leave the network freely, and are instantly mobile within the network), and quick deployment. For these reasons, potential MANET applications include military use (infrastructure could become a target, point of failure), search and rescue (prior establishment of the required networking infrastructure is impossible) and meetings or conferences (network lifetime does not merit the cost or time required to setup a network) [1].
There are three kinds of routing algorithms in a MANET, table-driven, on-demand, and hybrid routing [2]. The table-driven routing algorithm [2-4] involves all nodes trying to have complete knowledge of all paths to all other nodes in the MANET. The on-demand routing algorithm [4, 5] involves paths being discovered only when they are required. The hybrid routing algorithm [2, 6] involves a combination of the table-driven routing algorithm and on-demand routing algorithm. Any
(Agreement): (Validity):
Numerous achievements have been using the BA problem [9]. Unfortunately, all of the current protocols are used in static networks. These protocols cannot perform in a dynamically changing network. The classic BA problem is
*Responsible for correspondece: Prof.Shu-Ching Wang Email: scwang@mail.cyut.edu.tw
of the above strategies can help each node transmit a message to the other nodes in the MANET. Under many circumstances, a fault-free processor in a distributed system can reach a common agreement before performing some special tasks. Examples include the two-phase commitment in a distributed database system, the whereabouts of a replicated file in a distributed environment, and a landing task controlled by a flight path finding system [7].
To achieve perfect reliability in the MANET, a mechanism that allows a set of nodes to reach a common agreement, even in the presence of faulty nodes, is needed. Such a unanimity problem was studied by Lamport [8], called the Byzantine Agreement problem (BA). The solution of this problem involves making all fault-free nodes in an n-node distributed system reach a common agreement. One node, called the source node, chooses an initial value to start with. The nodes communicate with each other by message exchanges. The desired protocol solves the BA problem if it satisfies the following constraints:
considered for a synchronous fixed network in which the boundaries on the processing and communication delays for the fault-free components are fine, and each node does not have mobility in a static network [10].
However, in the MANET, each node has mobility. The nodes may move away from or back to the MANET at any time. Therefore, some of the fault-free nodes (nodes that
All fault-free nodes agree on the same value;
If the source node is fault-free, then all fault-free nodes should agree on
the initial value vs from the source node.
move away from the network in the message exchange phase and move back to the network in the decision-making phase) would not receive enough messages to reach a common agreement. This situation violates the BA problem requirement in which "each fault-free node" must reach a common agreement value. In this study, we will re-examine the BA problem in a MANET to provide fault-tolerance capability and reliable distributed computing. The protocol designed to reach Byzantine agreement in a MANET is called MAHAP (Mobile Ad Hoc Agreement Protocol). MAHAP makes fault-free nodes reach a common agreement using the minimum number of message exchanges and can tolerate a maximum number of faulty nodes.
1. The Conditions for BA problem. To solve the BA problem, the fallible node failure types, the system model, the number of required message exchange rounds, and the constraints must be considered first.
1.1. Thc Failure Type of a Fallible Node. During protocol execution, a node is said to be fault-free if it follows the protocol specifications; otherwise, the node said to be faulty. There are two failure categories; the dormant fault and the malicious fault (also called the Byzantine fault or the arbitrary fault) [8]. The dormant node faults include crashes and omission. A crash fault occurs when a node is broken. An omission fault takes place when a node fails to transmit or receive a message on time or at all. The malicious fault is the most damaging failure because the behavior of a malicious faulty node is unpredictable and arbitrary. In short, a malicious faulty node may work in coordination with other faulty nodes to prevent other fault-free nodes from reaching a common agreement value. Therefore, the malicious fault is the most damaging failure type and causes the worst problem. If the BA problem can be solved under malicious fault conditions, the BA problem can be solved under other failure conditions. Hence, in this study, the proposed protocol will solve the B A problem with malicious faulty nodes.
1.2. System Model. Because MANET nodes are mobile, the nodes may move away from the MANET or return at any time. In our system, model a node that moves away from the MANET in the message-exchange phase is called an "away node." A node that returns to the MANET before the decision-making phase is called a "return node."
The BA problem is considered in a MANET with fallible nodes and the fallible node type is the malicious fault. A MANET example is shown in Fig. 1. The assumptions and parameters of the MAHAP protocols are listed as follows.
Each node in the MANET can be identified as unique.
Let N be the set of all nodes in the network and N1 = n, where n is the number of nodes in the underlying MANET, and n ^ 4.
The nodes in the underlying MANET are assumed fallible.
A node that transmits messages is called the sender node.
There is only one source node that transmits a message in the first message exchange round in the BA problem.
Let fm be the maximum number of malicious faulty nodes.
Let fa be the maximum number of away nodes.
Each node can detect any node that moves away from the MANET.
A node does not know the fault status of other nodes.
Let vs be the initial value of the source.
Let t be the maximum number of allowed faulty nodes.
Let 8f be the absent value in the i-th round of a message exchange.
1.3. The Number of Message Exchange Rounds Required by MAHAP. In the BA problem, each node exchanges messages with all other nodes during the message exchange phase. Hence, the message-exchange phase is a time consuming phase. Therefore, reducing the number of required rounds is the major concern in designing an optimal protocol. The term "round" denotes the message exchange interval [7, 8, 10-15]. Fischer and Lynch pointed out that t + 1 (t ^ [(n - 1)/3]) rounds are the minimum number of rounds to get enough messages to achieve BA [10]. The number of rounds required in the MANET is also t + 1. A detailed description of the message-exchange phase will be presented in Section 2.1.
1.4. Constraints. The number of faulty nodes allowed in the network depends on the total number of nodes in the network and the node failure types. For example, in Lamport et al. [8], the assumption of node failure type was malicious in a fixed network. An additional constraint in Lamport et al. was n > 3fm, wherefm. is the number of malicious faulty nodes [8].
In this paper, the MAHAP is designed for a MANET with malicious faulty nodes. Because MANET nodes are mobile and the away nodes can be detected by each node in the MANET, the constraint of MAHAP
is n > 3fm + fa.
)Node f
Node e
Node b
Node g
Node d
''Node i
Node h
Node ^ Q - fault-free node,
^ - malicious faulty node
Fig. 1. An example of MANET.
2. The Proposed Mobile Ad Hoc Agreement Protocol (MAHAP). The MA-HAP protocol makes fault-free nodes agree on the value initiated by the source node. There are three phases in the MAHAP: the message-exchange phase, decision-making phase and the extension-agreement phase. In addition, the number of rounds required for executing MAHAP is t + 1 (t ^ [(n - 1)/3]). MAHAP can tolerate fm malicious faulty nodes, and fa away nodes, where n > 3fm + fa. The MAHAP is shown in Fig. 2. To make it more easily be understood, a flow chart is given in Appendix I.
2.1. Message-Exchange Phase. The goal of the message-exchange phase is to collect
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.