Parallel calculations by automata on direct and back spanning trees of a graph.
Parallel calculations by automata on direct and back spanning trees of a graph.
Authors
Abstract
The paper presents a parallel computation algorithm of an arbitrary function value on a multiset of values distributed on directed graph vertices. The computation is performed by message passing executed by automata distributed on the graph vertices. The key idea of the algorithm is to use a structural information on the graph that can be extracted by its parallel exploration and encoded into structures of direct and back spanning trees of the graph, which require only finite number of bits in each graph vertex, and to represent the function calculated as a composition of so called aggregate function and another one. Aggregate functions are characterized by possibility to calculate their value on a union of multisets by aggregating their values on separate multisets, that makes them easy for parallel computation.
Full text of the paper in pdfKeywords
Edition
French-Russian Seminar on Software Verification, Testing, and Quality Estimation, Paris, France, November 24-25, 2014.
Research Group
All publications during 2014
All publications