Algorithm, local

An algorithm which specifies the attributes of elements of a structured set and uses, at each step, only information about neighbourhoods of the element. Problems of the existence or non-existence of effective algorithms for various discrete optimization problems are naturally formulated in terms of local algorithms.

Let there be given a family $ \{ {\mathfrak M } : {\mathfrak M \in M } \} $ of sets, and let there be assigned to each pair $ ( \mathfrak A, \mathfrak M ) $, where $ \mathfrak A \in \mathfrak M $, a set $ S ( \mathfrak A , \mathfrak M ) $ such that: 1) $ \mathfrak A \in S ( \mathfrak A , \mathfrak M) $; 2) $ S ( \mathfrak A , \mathfrak M ) \subseteq \mathfrak M $; and 3) if $ \mathfrak A \in \mathfrak M _ {1} $, $ \mathfrak A \in \mathfrak M _ {2} $ and $ S ( \mathfrak A , \mathfrak M _ {1} ) \subseteq \mathfrak M _ {2} \subseteq \mathfrak M _ {1} $, then $ S ( \mathfrak A , \mathfrak M _ {1} ) = S ( \mathfrak A , \mathfrak M _ {2} ) $. The set $ S ( \mathfrak A , \mathfrak M ) $ will then be denoted as a neighbourhood of $ \mathfrak A $ in $ \mathfrak M $. Examples of neighbourhoods are conjunction neighbourhoods in a contracted normal form (cf. Boolean functions, minimization of).

Let $ \Gamma $ be a finite undirected graph, $ \Gamma = M _ {1} \cup M _ {2} $, where $ M _ {1} = \{ a _ {1} \dots a _ {q} \} $ is the set of vertices of $ \Gamma $, and let $ M _ {2} = \{ ( a _ {i _ {1} } , a _ {i _ {2} } ) \dots (a _ {r _ {p} } , a _ {r _ {t} } ) \} $ be the set of edges of $ \Gamma $. A neighbourhood $ S _ {1} (R, \Gamma ) $ of an edge $ R = (a _ {i} , a _ {j} ) $ of the graph $ \Gamma $ consists of all vertices of the edges incident with the edge $ R $, and also of all edges whose vertices are included in the neighbourhood $ S _ {1} (R, \Gamma ) $. Let $ S _ {n-1} (R, \Gamma ) $ be a defined neighbourhood; the neighbourhood $ S _ {n} (R, \Gamma ) $ then consists of all vertices of the edges incident with the vertices of the neighbourhood $ S _ {n-1} (R, \Gamma ) $ and all edges, the vertices of which belong to the neighbourhood $ S _ {n} (R, \Gamma ) $. The neighbourhoods $ S _ {1} (a _ {j} , \Gamma ) \dots S _ {n} ( a _ {j} , \Gamma ) $ of an arbitrary vertex $ a _ {j} $ of the graph $ \Gamma $ are introduced in a similar manner.

Let a system of two-place predicates $ P _ {1} ( \mathfrak A , \mathfrak M) \dots P _ {l} ( \mathfrak A , \mathfrak M) $, which is subdivided into two non-intersecting subsets $ \langle P _ {1} \dots P _ {r} \rangle $ and $ \langle P _ {r+1} \dots P _ {l} \rangle $, be defined on pairs $ ( \mathfrak A , \mathfrak M) $, $ \mathfrak A \in \mathfrak M $. The elements of the first subset are called the main predicates, while those of the second are called the auxiliary predicates. A vector $ \widetilde \alpha = ( \alpha _ {1} \dots \alpha _ {l} ) $ is called an information vector if $ \alpha _ {i} \in \{ 0, 1, \Delta \} $, $ i = 1 \dots l $. A vector $ \widetilde \alpha $ is called permissible for $ \mathfrak A $ in $ \mathfrak M $ if for all $ \alpha _ {i} \neq \Delta $ the equality $ \alpha _ {i} = P _ {i} ( \mathfrak A , \mathfrak M ) $ is satisfied. The set $ J ( \mathfrak A , \mathfrak M ) $ of all information vectors permissible for $ \mathfrak A $ in $ \mathfrak M $ is called the information set of $ \mathfrak A $ in $ \mathfrak M $.

Let $ \mathfrak M = \{ \mathfrak A _ {1} \dots \mathfrak A _ {q} \} $ and $ ( \alpha _ {i1} \dots \alpha _ {il} ) \in J ( \mathfrak A _ {i} , \mathfrak M ) $, $ i = 1 \dots q $. The set $ \mathfrak M ^ {*} = \{ \mathfrak A _ {1} ^ {\alpha _ {11} \dots \alpha _ {1l} } \dots \mathfrak A _ {q} ^ {\alpha _ {q1} \dots \alpha _ {ql} } \} $ is called permissible for $ \mathfrak M $. The class $ J ( \mathfrak M ) $ of all sets $ \mathfrak M ^ {*} $ permissible for $ \mathfrak M $ is called the information class of the set $ \mathfrak M $ over the system of predicates $ P _ {1} \dots P _ {l} $. Clearly, a neighbourhood $ S ( \mathfrak A , \mathfrak M) $ defines a neighbourhood $ S ( \mathfrak A ^ { {\alpha _ {1} } \dots {\alpha _ {l} } } , \mathfrak M ^ {*} ) $.

Introduce a system of functions $ \phi _ {1} \dots \phi _ {l} $ such that

$$ \phi _ {i} ( \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } , S ( \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } , \mathfrak M ^ {*} )) = ( \beta _ {1} \dots \beta _ {l} ). $$

The functions $ \phi _ {i} $ will be defined over all pairs $ ( \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } , S ( \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } , \mathfrak M ^ {*} )) $ such that $ \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } \in \mathfrak M ^ {*} $, $ \mathfrak M ^ {*} \in J ( \mathfrak M ) $, and satisfies the following conditions: 1) $ \alpha _ {i} = \beta _ {j} $ if $ j \neq i $; and 2) the set $ {\widetilde{\mathfrak M} } ^ {*} $, which is obtained from $ \mathfrak M ^ {*} $ by replacing the element $ \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } $ by $ \mathfrak A ^ {\beta _ {1} \dots \beta _ {l} } $, is permissible for $ \mathfrak M $, i.e. $ {\widetilde{\mathfrak M} } ^ {*} \in J ( \mathfrak M ) $. For the sake of brevity, the pairs $ ( \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } , S ( \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } , \mathfrak M ^ {*} )) $ are denoted by $ ( \mathfrak A , a _ {1} \dots a _ {l} , S, \mathfrak M ^ {*} ) $.

A partial order is introduced on some of the above sets: 1) on the set $ M _ {1} = \{ 0, 1, \Delta \} $ one takes $ \Delta < 0 $, $ \Delta < 1 $; 2) on the set $ M _ {2} $ of information vectors of length $ l $ one takes $ ( \alpha _ {1} \dots \alpha _ {l} ) \leq ( \beta _ {1} \dots \beta _ {l} ) $ if $ \alpha _ {i} \leq \beta _ {i} $, $ i = 1 \dots l $; 3) on the set of elements with marks one takes $ \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } \leq \mathfrak A ^ {\beta _ {1} \dots \beta _ {l} } $ if $ ( \alpha _ {1} \dots \alpha _ {l} ) \leq ( \beta _ {1} \dots \beta _ {l} ) $; 4) on the set $ M ^ {*} = \cup _ {\mathfrak M \in M } J ( \mathfrak M ) $ one takes $ \mathfrak M _ {1} ^ {*} \leq \mathfrak M _ {2} ^ {*} $ if, first, $ \mathfrak M _ {1} ^ {*} $ and $ \mathfrak M _ {2} ^ {*} $ belong to the same information class $ J ( \mathfrak M ) $ and, secondly, if $ ( \alpha _ {1} \dots \alpha _ {l} ) \leq ( \beta _ {1} \dots \beta _ {l} ) $ follows from $ \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } \in \mathfrak M _ {1} ^ {*} $ and $ \mathfrak A ^ {\beta _ {1} \dots \beta _ {l} } \in \mathfrak M _ {2} ^ {*} $; 5) on the set of neighbourhoods of the form $ S ( \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } , \mathfrak M ^ {*} ) $ one takes $ S _ {1} \leq S _ {2} $, where $ S _ {1} = S ( \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } , \mathfrak M _ {1} ^ {*} ) $ and $ S _ {2} = S ( \mathfrak A ^ {\beta _ {1} \dots \beta _ {l} } , \mathfrak M _ {2} ^ {*} ) $ if and only if $ S ( \mathfrak A , \mathfrak M _ {1} ) = S ( \mathfrak A , \mathfrak M _ {2} ) $ and if it follows from $ \mathfrak B ^ {\gamma _ {1} \dots \gamma _ {l} } \in S _ {1} $ and $ \mathfrak B ^ {\delta _ {1} \dots \delta _ {l} } \in S _ {2} $ that $ ( \gamma _ {1} \dots \gamma _ {l} ) \leq ( \delta _ {1} \dots \delta _ {l} ) $.

Let $ A $ and $ B $ be elements of one of the sets 1)–5). If $ A \leq B $ and $ A \geq B $, then the elements $ A $ and $ B $ are called equi-informative, which is denoted by $ A \widehat\widehat{ {{}}} B $. A function $ \phi ( \mathfrak A , \alpha _ {1} \dots \alpha _ {l,\ } S, \mathfrak M ^ {*} ) $ is called monotone if it follows from $ S _ {1} \leq S _ {2} $ that, for $ i = 1 \dots l $,

$$ \phi _ {i} ( \mathfrak A, \alpha _ {1} \dots \alpha _ {1} , S _ {1} ,\ \mathfrak M _ {1} ^ {*} ) \leq \phi _ {i} ( \mathfrak A , \beta _ {1} \dots \beta _ {1} , S _ {2} , \mathfrak M _ {2} ). $$

The determination of a local algorithm also necessitates the introduction of an ordering algorithm $ A _ \pi $. Let $ M $ be an arbitrary set of elements with information vectors, and let $ N = \{ 1 \dots l \} $. Consider the set $ M {\widetilde \times } N $ of all pairs $ ( \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } , j ) $ such that $ \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } \in M $, $ j \in N $, $ \alpha _ {j} = \Delta $. The algorithm $ A _ \pi $ orders the set $ M {\widetilde \times } N $. The local algortihm $ A $ is completely defined by the system of predicates $ P _ {1} \dots P _ {l} $, by the subdivision of this system into main predicates $ P _ {1} \dots P _ {r} $ and auxiliary predicates $ P _ {r+1} \dots P _ {l} $, by the system of monotone functions $ \phi _ {1} \dots \phi _ {l} $, $ \phi _ {i} = \phi _ {i} ( \mathfrak A , \alpha _ {1} \dots \alpha _ {l} , S, \mathfrak M ^ {*} ) $, and by the algorithm $ A _ \pi $.

Let $ \mathfrak M ^ {*} = \cup _ {i = 1 } ^ {m} \mathfrak A ^ {\alpha _ {i _ {1} } \dots \alpha _ {i _ {l} } } $, $ \mathfrak M ^ {*} \in J ( \mathfrak M ) $. The first step of the local algorithm may be described as follows. Algorithm $ A _ \pi $ is applied to the set $ M {\widetilde \times } N $, where $ M = \mathfrak M ^ {*} $; for the first pair $ ( \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } , j ) $ of the ordered sequence one computes $ \phi _ {j} ( \mathfrak A, \alpha _ {1} \dots \alpha _ {l} , S, \mathfrak M ^ {*} ) = ( \beta _ {1} \dots \beta _ {l} ) $ and the element $ \mathfrak A ^ {\alpha _ {1} \dots \alpha _ {l} } $ is then replaced by $ \mathfrak A ^ {\beta _ {1} \dots \beta _ {l} } $; if $ ( \alpha _ {1} \dots \alpha _ {l} ) = ( \beta _ {1} \dots \beta _ {l} ) $, then one takes the second pair, etc.; if for all elements $ ( \mathfrak B ^ {\gamma _ {1} \dots \gamma _ {l} } , i ) $ the equality $ \phi ( \mathfrak B, \gamma _ {1} \dots \gamma _ {l} , S, \mathfrak M ^ {*} ) = ( \gamma _ {1} \dots \gamma _ {l} ) $ is true, then the local algorithm $ A $ is terminated after reviewing all the pairs from $ M {\widetilde \times } N $. Otherwise, after replacement of the vector $ ( \alpha _ {1} \dots \alpha _ {l} ) $ by the new vector $ ( \beta _ {1} \dots \beta _ {l} ) $, algorithm $ A $ is terminated if there are no more elements with at least one symbol $ \Delta $ in the first $ r $ places of the information vectors; if there are such elements, the first step of the local algorithm terminates. Let the number of steps of the local algorithm $ A $ which have been performed be $ n $. The $ (n + 1) $- st step is carried out exactly as the first step, except that instead of the set $ \mathfrak M ^ {*} $ one now considers the set $ \mathfrak M _ {n} ^ {*} $ into which the set $ \mathfrak M ^ {*} $ has been converted after the first $ n $ steps of the local algorithm $ A $. Owing to the monotone nature of the functions $ \phi _ {i} $, $ i = 1 \dots l $, the local algorithm $ A $ will be terminated after a finite number of steps.

The starting theorems for local algorithms are the uniqueness theorem and the theorem on the existence of a best algorithm. The first theorem states that the result of the calculation of the main predicates is independent of the algorithm $ A _ \pi $( the order in which the elements of the set $ \mathfrak M ^ {*} $ are taken). The second theorem stipulates the existence, under very general conditions, of a best local algorithm, i.e. of a local algorithm which uses a given system of neighbourhoods to compute given main predicates with fixed auxiliary predicates, whenever this is done by any other local algorithm with an identical system of neighbourhoods, and main and auxiliary predicates.

The problem of finding a best local algorithm in explicit form has been solved for algorithms of synthesis of minimal coverings. Let there be given a tuple $ \langle \mathfrak A _ {1} \dots \mathfrak A _ {q} , \mu _ {1} \dots \mu _ {q} , M \rangle $, where $ \mathfrak A _ {i} $ is a set, $ \mu _ {i} $ is the complexity of $ \mathfrak A _ {i} $, $ \mu _ {i} > 0 $, $ i = 1 \dots q $, $ M \subseteq \cup _ {i=1} ^ {q} \mathfrak A _ {i} $. The complexity of the tuple $ ( \mathfrak A _ {i _ {1} } \dots \mathfrak A _ {i _ {p} } ) $ is $ \sum _ {j=1} ^ {p} \mu _ {i _ {j} } $. The problem is how to construct a covering of $ M $ by sets from a number of $ \mathfrak A _ {1} \dots \mathfrak A _ {q} $ with minimum complexity. A system of neighbourhoods $ S _ {1} \dots S _ {n} \dots $ for each $ \mathfrak A _ {i} $ is introduced in a manner similar to the introduction of a system of neighbourhoods for conjunctions. A best local algorithm is constructed for a system of neighbourhoods $ S _ {k} $ at fixed predicates: the set of auxiliary predicates is empty; the main predicates are considered to be the predicates $ P _ {1} ( \mathfrak A , M) $( $ \mathfrak A $ is not included in any minimal covering of $ \mathfrak M $) and $ P _ {2} ( \mathfrak A , M) $( $ \mathfrak A $ is included in all the minimal coverings of $ \mathfrak M $). Best local algorithms have also been constructed to calculate simple properties of edges of a graph. Various local algorithms have been proposed to solve problems of minimization of Boolean functions, of discrete linear programming, etc.

Computability of best local algorithms in a class of local algorithms is an important problem in the theory of local algorithms. If a system of imbedded neighbourhoods $ S _ {1} ( \mathfrak A, \mathfrak M ) \subseteq \dots \subseteq S _ {n} ( \mathfrak A, \mathfrak M ) \subseteq \dots $ is given on the pairs $ ( \mathfrak A, \mathfrak M ) $, $ \mathfrak A \in \mathfrak M $, $ \mathfrak M \in M $, and if the local algorithm operates with respect to the system $ S ( \mathfrak A, \mathfrak M ) $ of neighbourhoods where $ S _ {k-1} ( \mathfrak A, \mathfrak M ) \subseteq S ( \mathfrak A, \mathfrak M ) \subseteq S _ {k} ( \mathfrak A, \mathfrak M ) $, then one says that the local algorithm has index $ k $. It is natural to consider the number of predicates $ P _ {1} \dots P _ {l} $ in the definition of a local algorithm as the quantity of memory of the local algorithm. Let there be given a set $ {\mathcal P} $ of predicates $ P ( \mathfrak A , \mathfrak M ) $. It is considered that all the predicates participating in the definition of the local algorithm belong to $ {\mathcal P} $. Let $ A ( \mathfrak M ^ {*} ) $ be the result of applying the local algorithm $ A $ to $ \mathfrak M ^ {*} $, $ \mathfrak M ^ {*} \in J ( \mathfrak M ) $, $ \mathfrak M \in M $. One says that the predicate $ P _ {1} ( \mathfrak A , \mathfrak M ) $ is not $ (k, l) $- computable if for any local algorithm of index $ k $ with memory quantity $ l $ for the main predicate $ P _ {1} $ and for the auxiliary predicates $ P _ {2} \dots P _ {l} $ from $ {\mathcal P} $ there exists a set $ \mathfrak M ^ {*} $ such that in $ A ( \mathfrak M ^ {*} ) $ the predicate $ P _ {1} $ will not be computable for all elements.

Let $ f (x _ {1} \dots x _ {n} ) $ be the set of all Boolean functions (cf. Boolean function) in the variables $ x _ {1} \dots x _ {n} $ and let $ P _ {1} ( \mathfrak A , f( x _ {1} \dots x _ {n} )) $ be the predicate ( "the conjunction A is included in at least one minimal disjunctive normal form" ). With natural limitations imposed on the class of predicates $ {\mathcal P} $ it was found that the predicate $ P _ {1} ( \mathfrak A , f( x _ {1} \dots x _ {n} )) $ is not $ (k, l) $- computable if $ kl < \textrm{ const } \cdot 2 ^ {n} $. It is interesting to note that the predicate $ P ( \mathfrak A , f ( x _ {1} \dots x _ {n} )) $( "the conjunction A is included in at least one dead-end disjunctive normal form of f" ) (cf. Boolean functions, normal forms of) is $ (2, 1) $- computable, but is not $ (1, 1) $- computable. Similar results were obtained for predicates describing the entry of an edge into a shortest path between given vertices of a graph.

See also the references to Boolean functions, minimization of.

References

[1a]	Yu.I. Zhuravlev, "Local algorithms for the calculation of information Part I" Cybernetics , 1 : 1 (1965) pp. 10–16 Kibernetika (Kiev) , 1 : 1 (1965) pp. 12–19
[1b]	Yu.I. Zhuravlev, "Local algorithms for the calculation of information Part II" Cybernetics , 2 : 2 (1966) pp. 1–8 Kibernetika (Kiev) , 2 : 2 (1966) pp. 1–11
[2]	I.V. Khutoryanskaya, "Aspects of the theory of local algorithms on graphs" Cybernetics , 7 : 1 (1971) pp. 37–44 Kibernetika (Kiev) : 1 (1971) pp. 29–33
[3]	Yu.I. Zhuravlev, "Set-theoretical methods in the algebra of logic" Problemy Kibernet. , 8 (1962) pp. 5–44 (In Russian)

Comments

As a specific area (or in this form), the subject seems not to have been studied in the Western literature. It may be related to the study of Systolic Array algorithms [a1], Chapt. 8.

References

[a1]	C. Mead, L. Conway, "Introduction to VLSI systems" , Addison-Wesley (1980) pp. 263–330