There has been a shift towards parallel computing in the computer science field over the past years, which has spurred interest in investigating the parallelization of classic sequential algorithms. Much research has been vested in graphs, particularly the application of breadth-first search. However, a subset of graphs, the tree data structure, has common use in various applications, yet focus tends to remain on graphs. A possible reason is that an effective graph algorithm could easily be applied to a tree, but a tree has a more distinct structure. Therefore, developing algorithms to exploit the specific design of a tree may improve efficiency over the application of a graph algorithm.
We present concurrent breadth first tree traversal algorithm for M-ary trees, where M is an upper bound to the number of child nodes that a given node may have. The algorithm was developed in Java for portability and differs from other approaches in that it shall provide a meaningful ordering of nodes, which is absent in breadth first graph traversals. The approach provides relative fairness in the work done by each thread to aid scalability and eliminates the use of transactional memory, which appears in other concurrent tree traversals that do provide ordering. However, the use of rollback in these methods introduces a higher level of non-determinism to the computation, which we attempt to avoid for a better analysis of the algorithm.