University of Illinois Urbana-Champaign

Fault-tolerant consensus in directed graphs and convex hull consensus

Tseng, Lewis

Content Files
TSENG-DISSERTATION-2016.pdf

Permalink

https://hdl.handle.net/2142/90567

Description

Title
Fault-tolerant consensus in directed graphs and convex hull consensus
Author(s)
Tseng, Lewis
Issue Date
2016-04-20
Director of Research (if dissertation) or Advisor (if thesis)
Vaidya, Nitin H.
Doctoral Committee Chair(s)
Vaidya, Nitin H.
Committee Member(s)
  • Chekuri, Chandra
  • Gupta, Indranil
  • Welch, Jennifer L
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2016-07-07T19:54:10Z
Keyword(s)
  • Consensus
  • Byzantine fault
  • Crash fault
  • Directed network
  • fault-tolerance
  • convex hull consensus
Abstract
As distributed systems nowadays scale to thousands or more of nodes, fault-tolerance becomes one of the most important topics. This dissertation studies the fault-tolerance aspect of the consensus algorithm, which is a fundamental building block for the distributed systems. Particularly, the dissertation has the following two main contributions on fault-tolerant consensus in message-passing networks: • We explore various fault-tolerant consensus problems under different fault models in communication networks that are modeled as arbitrary directed graphs, i.e., two pairs of nodes may not share a bi- directional communication channel, and not every pair of nodes may be able to communicate with each other directly or indirectly. We prove the tight condition of the underlying communication graphs for solving each of the consensus problem, i.e., the necessary condition is equal to the sufficient condition. • We propose a new consensus problem – convex hull consensus – in which the input is a vector of reals in the d-dimensional space, and the output is a convex polytope contained within the convex hull of all inputs at fault-free nodes. For asynchronous systems, we present an approximate convex hull consensus algorithm with optimal fault tolerance that reaches consensus on optimal output polytope under crash fault model. Convex hull consensus may be used to solve related problems, such as vector consensus and function optimization with the initial convex hull as the domain.
Graduation Semester
2016-05
Type of Resource
text
Permalink
http://hdl.handle.net/2142/90567
Copyright and License Information
Copyright 2016 Lewis Tseng

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois