Semester

Fall

Date of Graduation

2006

Document Type

Dissertation

Degree Type

PhD

College

Statler College of Engineering and Mineral Resources

Department

Lane Department of Computer Science and Electrical Engineering

Committee Chair

Frances L. Van Scoy.

Abstract

This research investigates the problems of gossiping and multiple message broadcasting in dynamically orientable graphs of different network topologies. These are new problems never attempted before. Dynamically orientable graphs and six different network topologies are considered: paths, cycles, stars, binary trees, complete trees and two-dimensional grids. Information dissemination in graphs that are dynamically orientable requires that number of messages sent in each direction along an edge be balanced and therefore necessitates a different approach in gossiping and multiple message broadcasting.;The obvious upper bound for gossiping and multiple message broadcasting in dynamically orientable graphs is twice the best known time for gossiping and multiple message broadcasting in classical graphs. This is obtained by inserting an additional time step t' after each time step t in the classical graph algorithm in which all calls of time step t are repeated with messages moving along the same edges but in the opposite direction to reset the bias of these edges. Finding better bounds for gossiping and multiple message broadcasting in dynamically orientable graphs is the goal of this research.;For each network topology an algorithm is proposed to perform gossiping and multiple message broadcasting. For some network topologies proposed algorithms for dynamically orientable graphs achieved the same upper bound as it is known for classical graphs, for example, gossiping in dynamically orientable grid graphs. In some cases the best time is the twice the best known time for gossiping and multiple message broadcasting in classical graphs, for example, gossiping in dynamically orientable star graphs. In other cases, good time bounds are achieved that are very close to the upper bounds in classical graphs, for example, multiple message broadcasting in dynamically orientable grid graphs. Multiple message broadcasting in dynamically orientable cycle graphs is also a good example of close upper bounds. As number of messages increases bounds become very close to each other.

Share

COinS