The Communication Complexity of Distributed Computing and a Parallel Algorithm for Polynomial Roots

In the first part of the thesis, we begin with a discussion of the minimum communication requirements in some distributed networks. The main result is a general technique for determining lower bounds on the communication complexity of problems on various distributed computer networks. This general technique is derived by simulating the general network by a linear array and then using a lower bound on the communication complexity of the problem on the linear array. Applications of this technique yield nontrivial optimal or near-optimal lower bounds on the communication complexity of distinctness, ranking, uniqueness, merging, and triangle-detection on a ring, a mesh, and a complete binary tree of processors.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Tiwari, Prasoon

• Engineering, Electronics and Electrical

Identifier

(UMI)AAI8701635

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/69350