Distributed algorithms for file sorting and shortest path finding.

Abstract

The thesis consists of four chapters. Chapter one lays out the foundations of distributed computing. Chapter two presents new decentralized algorithms for sorting files of integers stored in a distributed and asynchronous network. An optimal communication complexity O(n log$\sb2$d) is obtained under the assumption that extra memory is available at each site in an almost balanced binary tree network, where n is the file size and d is the number of nodes in the network. When extra memory is removed from the nodes, our algorithm still manages to have a very good complexity of O(n log$\sb2\sp2$d). Chapter three presents a new decentralized algorithm in shortest path finding in a distributed and synchronous network, in particular we focus on the termination detection problem. The analysis of this algorithm shows an improved complexity over previous methods. Moreover, in chapters two and three we discuss some tradeoffs in the design of these two algorithms. Finally in chapter four we summarize our results and present some unsolved problems arising from this work. (Abstract shortened by UMI.)