Award Date

8-1-2012

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Ajoy K Datta

Second Committee Member

Lawrence Larmore

Third Committee Member

Juyeon Jo

Fourth Committee Member

Emma Regentova

Number of Pages

127

Abstract

In this thesis, we give message passing algorithms in distributed environment for five different problems of a rooted tree having n nodes. In the first algorithm, every node has a value; the root calculates the sum of those values, and sends it to all the nodes in the network. In the second algorithm, the root computes the value of mean of values of all the nodes, and sends it to all nodes of the network. The third algorithm calculates the guide pairs. Guide pair of a node x is an ordered pair (pre_index(x), post_index(x)), where pre_index(x) and post_index(x) are the rank of x in the preorder and reverse postorder traversal of T. In the fourth algorithm, we compute the rank of all the nodes in the tree by considering the weight (value) present at every node. Finally, in the fifth algorithm, values present in the nodes are sorted in level order.

Keywords

Computer algorithms; Message passing; Parallel computers; Routing (Computer network management)

Disciplines

Computer Sciences | OS and Networks | Theory and Algorithms

Language

English


Share

COinS