In this thesis, we look into the problem of forming and maintaining good committees that can represent a distributed network. The solution to this problem can be used as a sub-routine for Byzantine Agreement that only costs sub-quadratic message complexity. Most importantly, we make no cryptographic assumptions such as the Random Oracle assumption and the existence of private channels. However, we do assume the network to be peer-to-peer, where a message receiver knows who the message sender is. Under the synchronous full information model, our solution is to utilize an approximating disperser for selecting a good next committee with high probability, repeatedly. We consider several existing theoretical constructions (randomized and deterministic) for approximating dispersers, and examine the practical applicability of them, while improving constants for some constructions. This algorithm is robust against a semi-adaptive adversary who can decide the set of nodes to corrupt periodically. Thus, a new committee should be selected before the current committee gets corrupted. We also prove some constructions that do not work practically for our scenario. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/11728 |
| Date | 05 May 2020 |
| Creators | Zheng, Zehui |
| Contributors | Pan, Jianping, King, Valerie D. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.002 seconds