Strong Consensus Problem and Fault Diagnosis Problem in Mobile Ad-Hoc Networks

View Statistics Email Alert RSS Feed

Information

Details

Project title

Code/計畫編號

NSC99-2218-E032-001-MY3

Translated Name/計畫中文名

行動隨意式網路下強勢合議問題以及錯誤診斷問題之研究

Project Coordinator/計畫主持人

Chien-Fu Cheng

Funding Organization/主管機關

National Science and Technology Council

Department/Unit

Tamkang University Department of Computer Science and Information Engineering

Website

https://www.grb.gov.tw/search/planDetail?id=2200320

Year

2011

Start date/計畫起

01-08-2011

Expected Completion/計畫迄

31-07-2012

Bugetid/研究經費

596千元

ResearchField/研究領域

資訊工程--硬體工程

近年來由於無線通訊以及行動計算的蓬勃發展，使得行動隨意式網路的可靠度以及容錯能力成為一個相當重要之課題。為了提供可靠的計算環境，我們需要一個機制讓參與運作的處理器即使在發生損毀或被攻擊時仍能夠達成協議/合議，因此拜占庭協議問題 (Byzantine Agreement Problem, BA problem)、合議問題(Consensus Problem)以及強勢合議問題(Strong Consensus Problem, SC problem)成為許多學者關注的焦點。所謂的強勢合議問題是由Neiger學者於1994年所提出，它是合議問題的變形問題。而強勢合議通訊協定之目的是讓所有運作正常之處理器能夠排除掉其它損毀元件之干擾或攻擊，進而合議出一個共同值(a common value)，以便能接續完成某些特別的工作。在強勢合議問題之中，此共同值必須為這些參與合議過程的處理器們其中之一的初始值。舉例來說，若運作正常之處理器其初始值分別為1到10，那麼最終的合議值將會是1 到10之間的值，不可為1到10以外之任意值，此點正是強勢合議問題與拜占庭協議問題以及合議問題之最大不同點。截至目前為止，尚未有強勢合議通訊協定是針對行動隨意式網路而設計。亦即，在行動隨意式網路上之強勢合議問題尚無法被解決。因此本計畫將在行動隨意式網路上重新探討強勢合議問題，我們所提出的通訊協定能容忍最大數量的損毀元件(包含惡意的攻擊者以及通訊媒介的損毀)，使得所有運作正常之處理器能夠在行動隨意式網路中都能獲得一個共同值來解決強勢合議問題。為了提供更高可靠度的計算環境，我們還必須偵測/定位出網路中的損毀處理器。因此，在本研究之中，我們也將利用強勢合議通訊協定來偵測/定位出損毀的處理器於行動隨意式網路之中。本計畫預計以三年的時間來解決上述之問題，包含如何設計實用可行的行動隨意式網路架構模式。在此模式之下，分別針對處理器損毀情況下、網路環境不穩定的情況下，以及處理器損毀下並且網路環境不穩定的情況下解決強勢合議問題，我們也將進一步將損毀情形區分為惡質性損毀以及非惡質性損毀的情況，藉由分析不同程度之損毀情況以提升整體之容錯能力。此外，我們也將探討如何利用強勢合議通訊協定來找出損毀元件。 Since wireless communication and mobile computing are becoming more and more ubiquitous, the reliability and fault tolerance of mobile ad-hoc networks (MANETs) has become an important topic. In order to provide a reliable environment, a mechanism that allows a set of processors to reach a common agreement, even in the presence of faulty processors, is needed. Therefore, the Byzantine Agreement (BA) problem, Consensus problem and Strong Consensus (SC) problem have drawn attention of more researchers. The SC problem was proposed by Neiger in 1994. The SC problem is a variant of the conventional distributed Consensus problem. The SC problem requires that the agreed value among fault-free processors be one of the fault-free processor’s initial values. Up to now, none of the previous results can solve the SC problem in MANETs. In this study, we shall propose a new protocol to solve the SC problem with dual failure mode on both processors and communication media (both dormant and malicious faults can happen simultaneously to either the processors or the communication media or both) over an unreliable MANET. The proposed protocol is the optimal when the above assumptions are considered. In a highly reliable fault-tolerant environment, to reach a common value is not enough. It is also necessary to detect/locate the faulty components in the network. Therefore, we also propose a new protocol (based on SC) to solve the fault diagnosis problem in MANETs.

Keyword(s)

容錯分散式系統
拜占庭協議問題
合議問題
強勢合議問題
錯誤診斷問題
_x000d_ 惡質性損毀
非惡質性損毀
行動隨意式網路
fault-tolerant distributed system
Byzantine Agreement problem
Consensus_x000d_ problem
Strong Consensus problem
fault diagnosis problem
malicious fault
dormant fault
_x000d_ mobile ad-hoc networks

DSpace CRIS

Strong Consensus Problem and Fault Diagnosis Problem in Mobile Ad-Hoc Networks

Details

Description