This report presents a weighted version of the Byzantine Agreement Problem
and its solution under various conditions.
In this version, each machine is assigned a weight depending on the application.
Instead of assuming that at most $f$ out of $N$ machines fail, the algorithm assumes
that the total weight of the machines that fail is at most $\rho < 1/3.$
When each machine has weight $1/N,$ this problem reduces to the standard Byzantine Generals
Agreement Problem.
By choosing weights appropriately, the weighted Byzantine Agreement
Problem can be applied to situations where a subset of processes are more trusted.
By using weights,
the system can reach consensus in the presence of Byzantine failures, even when more than $N/3$
processes fail, so long as the total weight of the failed processes is less than $1/3.$
Some properties of the Weighted Byzantine Agreement algorithms when the weight vectors are not
the same at every process are discussed.
Also, a method to update the weights of the processes after execution of the weighted Byzantine Agreement
is given.
The update method guarantees
that the weight of any correct process is never reduced and the weight of
any faulty process, suspected by correct processes whose total weight is at least $1/4,$
is reduced to $0$ for future instances.
A short discussion of some weight assignment strategies is also given. / text
| Identifer | oai:union.ndltd.org:UTEXAS/oai:repositories.lib.utexas.edu:2152/ETD-UT-2012-05-5616 |
| Date | 13 August 2012 |
| Creators | Bridgman, John Francis |
| Source Sets | University of Texas |
| Language | English |
| Detected Language | English |
| Type | thesis |
| Format | application/pdf |
Page generated in 0.0018 seconds