Efficient distributed solutions for classical network problems

Makki, S. A. M. (1997). Efficient distributed solutions for classical network problems PhD Thesis, School of Information Technology and Electrical Engineering, The University of Queensland. doi:10.14264/uql.2014.571

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
THE12345.pdf Thesis full text application/pdf 4.49MB 0
Author Makki, S. A. M.
Thesis Title Efficient distributed solutions for classical network problems
School, Centre or Institute School of Information Technology and Electrical Engineering
Institution The University of Queensland
DOI 10.14264/uql.2014.571
Publication date 1997-01-01
Thesis type PhD Thesis
Supervisor George Havas
Total pages 175
Language eng
Subjects 010303 Optimisation
Formatted abstract
Recent advances in computer hardware and communication technologies have made it cost effective to develop large systems from collections of many interconnected computers. Such large systems are called distributed computing systems or distributed systems for short. Distributed systems offer tremendous processing capabilities and have cost and performance advantages over the traditional centralised systems. Distributed systems may be preferred over centralised systems, or their use may simply be unavoidable for many reasons, including providing efficient resource sharing, information exchange, computation speed-up and increased performance through parallelisation, and increased reliability and availability through replication.

We take distributed systems to mean a collection of separate autonomous sites (computers), which may communicate with each other only by sending messages. Sites do not share a common memory or clock. A site usually consists of a computing unit, a storage unit, an interface to local users and a communication network interface. There is currently a wide variety of ways in which computer systems are connected together to form distributed systems.

In order to take full advantage of distributed systems’ computing power we need to develop and design efficient distributed algorithms. Distributed algorithms are algorithms designed to run on a system consisting of many interconnected computers. Pieces of a distributed algorithm may run concurrently and independently, each with only a limited amount of information. The term distributed algorithms covers a large variety of concurrent algorithms used for a wide range of applications. Distributed algorithms arise in many real-world applications, including distributed information processing, telecommunications, scientific computing and automatic teller machines. An important part of the job of building such a system is to develop, design and analyse efficient distributed algorithms. However, due to the lack of global information and absence of global control mechanisms the design of a distributed algorithm is much more difficult than its corresponding centralised/sequential algorithm. These algorithms also have different complexity measures due to the priorities important in these systems compared with their centralised counterparts.

This thesis presents new and efficient distributed algorithms for three fundamental network problems: depth-first search; breadth-first search; and Eulerian tour construction in a static distributed environment. It also investigates the construction of a depth-first search tree in a dynamic distributed environment (i.e. the topology of the network may change during the execution of the algorithm). We show that the best message and time complexities can be achieved for a range of network topologies. Furthermore, we show that the proposed distributed algorithms are very practical and easy to implement. These algorithms have a range of applications, because the solution to many important problems in a distributed environment requires the examination (visit) of all sites of distributed systems.
Keyword Electronic data processing -- Distributed processing
Computer algorithms

Document type: Thesis
Collection: UQ Theses (RHD) - UQ staff and students only
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 12 Dec 2014, 19:09:00 EST by Mary-Anne Marrington on behalf of Scholarly Communication and Digitisation Service