Ivannikov Institute for System Programming of the RAS


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

Authors

Burdonov, A. Kossachev, V. Kuliamin.

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 pdf

Keywords

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

Edition

French-Russian Seminar on Software Verification, Testing, and Quality Estimation, Paris, France, November 24-25, 2014.

Research Group

Software Engineering

All publications during 2014 All publications