brian

Tarry’s &Awerbuch’sAlgorithms
byBrianBartman
Outline
AlgorithmsTarry’s AlgorithmTime and Message complexityAwerbuch’sDepth First Search AlgorithmTime and Message complexityExperimentDescriptionExperiment VariablesTest CasesExpected ResultsActual Results
Tarry’s Algorithm
varusedp[q] :booleanInitfalse for eachq∈Neighp;fatherp: process initundef;For the initiator only execute once:beginfatherp:=p; chooseq∈Neighp;usedp[q] :=true; send <tok> toqendFor each process upon receipt of <tok>fromq0:begin iffatherp=undefthenfatherp:=q0;If∀q∈Neighp:usedp[q]thendecideelse if∃q∈Neighp(q≠Neighp∧ ¬usedp[q])then beginchooseq∈Neighp\ {fatherp}with ¬usedp[q];usedp[q] :=true; send <tok> toqendelse beginusedp[fatherp] :=true;send <tok>tofatherpendend
Tarry’s Time And Message Complexity
Because Tarry’s algorithm is a traversal algorithm both the time complexity and message complexity are the same.Time Complexity = Message Complexity2E
varusedp[q] :booleanInitfalse for eachq∈Neighp;fatherp: process initundef;For the initiator only, execute once:beginfatherp:=p; chooseq∈Neighp;forallr∈Neighpdo send <vis> tor;forallr∈Neighpdo receive <ack> fromr;usedp[q] :=true;send <tok> toqendFor all processes upon receive of <tok>fromq0:begin iffatherp=undefthenbeginfatherp:=q0;forallr∈Neighp\ {fatherp}dosend <vis> tor;forallr∈Neighp\ {fatherp}doreceive<ack> fromr;end ;if∀q∈Neighp:usedp[q]thenifpis the initiatorthendecideelsesend <tok> tofatherpendelsechooseq∈Neighpwith ¬usedp[q];usedp[q] :=true;send <tok> toqendendFor all processes upon receive of <viz>fromq0:beginusedp[q0] :=true; send <ack> toq0;
Awerbuchs
Awerbuch’sTime And Message Complexity
Time Complexity4N - 2Time Complexity = Message Complexity4E
Experiment
Description:The goal of the experiment is to measure time and message complexities of Tarry’s andAwerbuch’salgorithms and compare them over various topologies with increasing numbers of nodes. The time complexities measured accounting for both parallel and sequential executions of both algorithms, however this only effects the execution time ofAwerbuch’salgorithm. The different topologies tested were: star, chain ring and clique. Each topology was tested with 2 to 25 nodes comprising the topology. Each of the different number of nodes between 2 and 25 was each tested 5 times and the averages taken.
Experiment Variables
Independent VariablesNumber of nodesDependent VariablesNumber of messages sentNumber of guarded commands executedParallel time (recorded forAwerbuch’s).
Test Cases
TopologiesChainCliqueRingStarFor each topology graphs were constructed for 2 to 25 nodes.Each of the configurations between 2 and 25 were each tested 5 times.
Expected Results
ChainTarry’s will out performAwerbuch’sbecause Tarry’s time complexity is 2E and the topology of the graph preventsAwerbuch’sfrom taking advantage of parallel execution of <ack> and <vis> sends and receives.CliqueAwerbuch’swill have a lower time complexity (linear) in parallel because the number of nodes is whatAwerbuch’sdepends upon, while Tarry’s depends upon the number of edges which is increasing exponentially.StarAwerbuch’swill take longer than Tarry’s algorithm, because it is unable to exploit parallelism.RingAwerbuch’swill take longer to complete because it is still unable to exploit the ability to send messages inparallel.
Chain Results
Clique Results
Ring Results
Star Results
Future Work
What I would like to do is to develop an idea of what type of density is necessary for Tarry’s algorithm to be faster thanAwerbuch’son arbitrary topologies, and possibly develop some sort of rating system which could rate the density of a network and see exactly how sparse or dense a network would need to be in order forAwerbuch’salgorithm to be either faster or slower than Tarry’s.
References
A. Baruch, “A New Distributed Depth-First-Search Algorithm,”Information Processing Letters 20, pp. 147-150, 1985.G.Tarry, “LeProblemDes Labyrinthes,”Nouvelles Annales deMathematique14, 1895.