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

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