Award Date

1-1-2002

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Ajoy K. Datta

Number of Pages

46

Abstract

Distributed algorithms are designed for systems consisting of many interconnected processors that communicate with one another by exchanging messages through communication links. Distributed algorithms are used on a wide range of applications, from a VLSI chip to LAN, to the Internet. The advantages of distributed systems include information exchange, resource sharing, replication, parallelization, and modularization; NS (Network Simulator) is an object-oriented, discrete event driven network simulator developed at USC/ISI written in C++ and OTCL. NS is primarily useful for simulating local and wide area networks. It produces one or more text-based output files that contain detailed simulation data. The data can be used for simulation analysis or as an input to a graphical simulation display tool, called Network Animator (NAM); There are two approaches to designing distributed algorithms. In synchronous algorithms, the operation of each process is done in a lock-step behavior, whereas in asynchronous algorithms, the processes take steps in an arbitrary order and at arbitrary relative speeds. Synchronous algorithms are easier to write and prove. However, asynchronous algorithms are easier to implement. Thus, an approach to designing distributed algorithms in asynchronous systems is to start with synchronous algorithms, then transform them into corresponding asynchronous versions by passing them through a special algorithm, called synchronizer. This allows one to use asynchronous systems to run the original synchronous algorithms. The synchronizer itself is an asynchronous algorithm; In this research, we experiment with different types of synchronizers. We implement them by considering two applications: leader election and breadth-first search algorithms. The algorithms are implemented on arbitrary networks. We compare the algorithms in terms of communication complexity. We also discuss the suitability of NS as a platform to implement synchronous and asynchronous algorithms.

Keywords

Distributed; Network Simulator; Software; Synchronizers

Controlled Subject

Computer science

File Format

pdf

File Size

1413.12 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

Rights

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

Download


Share

COinS