#### 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

#### Language

English

#### Repository Citation

Subedi, Mahesh, "Self-stabilizing group membership protocol" (2010). *UNLV Theses, Dissertations, Professional Papers, and Capstones*. 773.

http://digitalscholarship.unlv.edu/thesesdissertations/773

#### Included in

Computer Sciences Commons, Digital Communications and Networking Commons, Systems and Communications Commons