| dc.description.abstract | The Full Reversal Algorithm of Gafni and Bertsekas has been traditionally used to solve problems in distributed computing, such as leader election, resource allocation, and routing problems [1]. Full reversal generally works in a decentralized manner, only taking advantage of locality by reorienting edges that are incident on a node and surrounding neighbors, depending on the distributed problem being solved. The fact that Full Reversal looks at edges that are surrounding isn't troublesome; what is that is that it looks at all of these edges, no matter the cost of reversing that edge. This can lead to sub-optimal resolutions that do not minimize the cost of link reversal in a distributed problem. This thesis explores the case where: (1) there are differing costs on edges; (2) these costs are derived naturally from a hierarchical organization of the network. To minimize the cost in link reversals, in such cases, we propose an algorithm, called Hierarchical Full Reversal that takes advantage of information that may arise in neighboring nodes in the form of hierarchical cliques. The algorithm is then analyzed and compared to the traditional Full Reversal Algorithm via cases of routing problems to a leader within a graph. For hierarchical graphs, the algorithm does achieve a reduction. The experiments we conducted over a set of different graph structures show that there can be a reduction in cost, sometimes as much as by 48%, but with a reduction of 30% for general examples we tried. | en |
