Award Date

12-2010

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Ajoy K. Datta, Co-Chair

Second Committee Member

John Minor, Co-Chair

Third Committee Member

Lawrence L. Larmore

Graduate Faculty Representative

Emma E. Regentova

Number of Pages

99

Abstract

In this thesis, we consider the problem of partitioning a network into groups of bounded diameter.

Given a network of processes X and a constant D, the group partition problem is the problem of finding a D-partition of X, that is, a partition of X into disjoint connected subgraphs, which we call groups, each of diameter no greater than D. The minimal group partition problem is to find a D-partition {G1, ... Gm} of X such that no two groups can be combined; that is, for any Gi and Gj, where i ≠ j, either Gi U Gj is disconnected or Gi U Gj has diameter greater than D.

In this thesis, a silent self-stabilizing asynchronous distributed algorithm is given for the minimal group partition problem in a network with unique IDs, using the composite model of computation. The algorithm is correct under the unfair daemon.

It is known that finding a D-partition of minimum cardinality of a network is NP-complete. In the special case that X is the unit disk graph in the plane, the algorithm presented in this thesis is O(D)-competitive, that is, the number of groups in the partition constructed by the algorithm is O(D) times the number of groups in the minimum D-partition.

Our method is to first construct a breadth-first search (BFS) tree for X, then find a maximal independent set (MIS) of X. Using the MIS and the BFS tree, an initialD-partition is constructed, after which groups are merged with adjacent groups until no more mergers are possible. The resulting D-partition is minimal.

Keywords

Clustering; Computer networks; Distributed algorithms; Group membership; Network partitioning; Self-stabilizing algorithm

Disciplines

Computer Sciences | Digital Communications and Networking | Systems and Communications

File Format

pdf

File Size

2200 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS