Proceedings of ISP RAS

Parallel calculations by automata on direct and back spanning trees of a graph.

Igor Burdonov, Alexander Kossachev, Victor Kuliamin.


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.


parallel computation; directed graphs; group of automata; graph spanning tree


Proceedings of the Institute for System Programming, vol. 26, issue 6, 2014, pp. 63-66

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2014-26(6)-5

Full text of the paper in pdf Back to the contents of the volume