Browse wiki

From Navigators

Jump to: navigation, search
Abstract The thesis investigates the problem of fau The thesis investigates the problem of fault- and intrusion-tolerant consensus in resource-constrained wireless ad hoc networks. This is a fundamental problem in distributed computing because it abstracts the need to coordinate activities among various nodes. It has been shown to be a building block for several other important distributed computing problems like state-machine replication and atomic broadcast. The thesis begins by making a thorough performance assessment of existing intrusion-tolerant consensus protocols, which shows that the performance bottlenecks of current solutions are in part related to their system modeling assumptions. Based on these results, the communication failure model is identified as a model that simultaneously captures the reality of wireless ad hoc networks and allows the design of efficient protocols. Unfortunately, the model is subject to an impossibility result stating that there is no deterministic algorithm that allows n nodes to reach agreement if more than n􀀀2 omission transmission failures can occur in a communication step. This result is valid even under strict timing assumptions (i.e., a synchronous system). The thesis applies randomization techniques in increasingly weaker variants of this model, until an efficient intrusion-tolerant consensus protocol is achieved. The first variant simplifies the problem by restricting the number of nodes that may be at the source of a transmission failure at each communication step. An algorithm is designed that tolerates f dynamic nodes at the source of faulty transmissions in a system with a total of n � 3f + 1 nodes. The second variant imposes no restrictions on the pattern of transmission failures. The proposed algorithm effectively circumvents the Santoro- Widmayer impossibility result for the first time. It allows k out of n nodes to decide despite � � dn 2 e(n􀀀k)+k􀀀2 omission failures per communication step. This algorithm also has the interesting property of guaranteeing safety during arbitrary periods of unrestricted message loss. The final variant shares the same properties of the previous one, but relaxes the model in the sense that the system is asynchronous and that a static subset of nodes may be malicious. The obtained algorithm, called Turquois, admits f < n 3 malicious nodes, and ensures progress in communication steps where � � dn􀀀f 2 e(n 􀀀 k 􀀀 f) + k 􀀀 2. The algorithm is subject to a comparative performance evaluation against other intrusion tolerant protocols. The results show that, as the system scales, Turquois outperforms the other protocols by more than an order of magnitude. tocols by more than an order of magnitude.
Advisor Nuno Ferreira Neves + , Miguel Correia +
Author Henrique Moniz +
Key HMonizPhD10  +
Month nov  +
NumPubDate 2,010.11  +
ResearchLine Fault and Intrusion Tolerance in Open Distributed Systems (FIT) +
School Departamento de Informática, Faculdade de Ciências, Universidade de Lisboa  +
Title Byzantine Fault-Tolerant Agreement Protocols for Wireless Ad hoc Networks  +
Type phdthesis  +
Year 2010  +
Has improper value forThis property is a special property in this wiki. Url  +
Categories Publication  +
Modification dateThis property is a special property in this wiki. 2 October 2018 16:36:39  +
hide properties that link here 
  No properties link to this page.


Enter the name of the page to start browsing from.
Personal tools
Navigators toolbox