Please use this identifier to cite or link to this item:
Title: The Communication Complexity of Fault-Tolerant Distributed Computation of Aggregate Functions
Authors: ZHAO YUDA
Keywords: Aggregate functions, communication complexity, fault-tolerance, promise problems
Issue Date: 17-Mar-2014
Citation: ZHAO YUDA (2014-03-17). The Communication Complexity of Fault-Tolerant Distributed Computation of Aggregate Functions. ScholarBank@NUS Repository.
Abstract: Multi-party communication complexity involves distributed computation of a function over inputs held by multiple distributed players. A key focus of distributed computing research, since the very beginning, has been to tolerate failures. It is thus natural to ask ``{\em If we want to compute a certain function while tolerating a certain number of failures, what will the communication complexity be?}'' This thesis centers on the above question. Specifically, we consider a system of $N$ nodes which are connected by edges and then form some topology. Each node holds an input and the goal is for a special {\em root} node to learn some certain function over all inputs. All nodes in the system except the root node may experience {\em crash} failures, with the total number of edges incidental to failed nodes being upper bounded by $f$. This thesis makes the following contributions: 1) We prove that there exists an {\em exponential gap} between the non-fault-tolerant and fault-tolerant communication complexity of {\sc Sum}; 2) We prove near-optimal lower and upper bounds on the fault-tolerant communication complexity of general {\em commutative and associative aggregates} (such as {\sc Sum}); 3) We introduce a new two-party problem {\sc UnionSizeCP} which comes with a novel {\em cycle promise}. Such a problem is the key enabler of our lower bounds on the fault-tolerant communication complexity of {\sc Sum}. We further prove that this cycle promise and {\sc UnionSizeCP} likely play a fundamental role in reasoning about fault-tolerant communication complexity of many functions beyond {\sc Sum}.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
ZhaoYuda.pdf1.1 MBAdobe PDF



Page view(s)

checked on Oct 13, 2018


checked on Oct 13, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.