Project Abstract:

Most consensus algorithms for both synchronous and asynchronous distributed systems are based on the notion of round, and achieve consensus by exchanging messages during each round. Time complexity and message complexity are used to evaluate the efficiency of a consensus algorithm. There are various existing results on lower bound for consensus problem. But most of those results achieved by backward induction therefore are complicated and difficult to follow. Thus, the first objective of this project is to provide simpler and more intuitive proofs for some existing results. Traditionally, the consensus problem is considered in a fully connected network. In practice, most of the network topologies may not be fully connected, due to the cost of the fully connected network is huge. Thus, another objective of this project is to study consensus in un-fully connected network, especially in chordal rings.