Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/77721
 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 Source: 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}. URI: http://scholarbank.nus.edu.sg/handle/10635/77721 Appears in Collections: Ph.D Theses (Open)

###### Files in This Item:
File Description SizeFormatAccess SettingsVersion

OPEN

None

#### Page view(s)

318
checked on Feb 23, 2018