+1 Recommend
1 collections
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      A Breadth-First, Ordered Parallel Tree Traversal


      1 , 1 , 1 ,   , 1

      ScienceOpen Preprints


      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.


          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.

          Related collections

          Most cited references 1

          • Record: found
          • Abstract: not found
          • Article: not found

          An Efficient Wait-Free Vector


            Author and article information

            [1 ] UCF
            ScienceOpen Preprints
            26 August 2019

            This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at .

            Software engineering


            Comment on this article