We address two problems dealing with fault-tolerant communication in networks.
The first one is designing a distributed storage protocol tolerant to Byzantine failure of
servers. The protocol implements a multi-writer multi-reader register which satisfies
a weaker consistency condition called MWReg. Most of the earlier work gives multiwriter
implementations by simulating m copies of a single-writer protocol where m
is the number of writers. Our solution gives a direct multi-writer implementation
and thus has bounded message and time complexity independent of the number of
writers. We have simulated the complete protocol to test its performance and also
proved its correctness theoretically.
The second problem we address is of providing a reliable communication link
between two nodes in a network. We present a capacity reservation algorithm in the
case for upper bounds on edge capacities and costs associated with using per unit
capacity on any edge. We give a flow based approximation algorithm with cost at
most four times optimal.
To conclude, we design a distributed storage protocol and a capacity reservation
algorithm which are tolerant to network failures.
Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-3118 |
Date | 15 May 2009 |
Creators | Kanjani, Khushboo |
Contributors | Sprintson, Alex, Welch, Jennifer |
Source Sets | Texas A and M University |
Language | en_US |
Detected Language | English |
Type | Book, Thesis, Electronic Thesis, text |
Format | electronic, application/pdf, born digital |
Page generated in 0.0172 seconds