Abstract

The problem of parallel computation of the value of a function of multiset of values recorded at the vertices of a directed graph is considered. Computation is performed by automata that are located at the vertices of the directed graph and exchange messages with each other that are transmitted along the arcs of the graph (in the direction of their orientation). It is assumed that the arc capacity, that is, the number of messages that can be simultaneously transmitted through an arc, is limited. Computation is initiated by a message coming from outside to the automaton located at the initial vertex of the graph. At the end of work, the same automaton sends outside the calculated value of the function. Two algorithms are proposed to solve this problem. The first algorithm carries out an analysis of the graph based on its traversal. Its purpose is to mark the graph by a change of the states of the automata at the vertices. Direct and back spanning trees of a graph are constructed. The direct spanning tree is oriented from the root, which is the initial vertex of the graph. The back spanning tree is oriented to the root. In addition, at each vertex, a value of the counter of incoming arcs of the back spanning tree is set. Such marking is used by the second algorithm, which calculates the value of one or other function. This calculation is based on a pulsation algorithm: first, request messages are distributed from the automaton of the initial vertex over the graph, which should reach each vertex, and then response messages are sent from each vertex back to the initial vertex. In fact, the pulsation algorithm calculates aggregate functions for which the value of a function of a union of multisets is calculated by the values of the function of these multisets. However, it is shown that any function f(x) has an aggregate extension; that is, an aggregate function can be calculated as h(f′(x)), where f′ is an aggregate function. Note that the marking of a graph does not depend on a function that will be calculated. This means that the marking of a graph is carried out once; after that, it can be reused for calculating various functions.