The paper addresses the method of processing and recognizing sequences of false and non-false signals from a distributed system with an output. It is proposed to adapt existing algorithms for non-distributed systems. The aim of the research is to obtain new approaches to detect and synthesize signal patterns from a distributed system. It allows us to identify more false signals than are initially known, and thus recognize more possible errors during the operation of a distributed system. The developed algorithm must meet certain criteria, such as the number of states, the percentage of false assumptions, etc. The relevance of the work lies in the need to recognize erroneous behavior in distributed systems, where the theoretical number of error patterns is proportional to the number of system elements, and it is not always possible to list all erroneous states, but it is possible to specify certain patterns of such states and allow the system to determine specific erroneous states based on known patterns. The paper uses many well-known approaches, including a similar solution for non-distributed systems, the combination and adaptation of which gives the required result.
In the evolving landscape of technology, distributed systems have become a cornerstone in a
myriad of applications ranging from industrial automation to cyber-physical systems like modern
transportation and smart cities [
The need for robust error detection in distributed systems is not just a matter of operational
efficiency but safety and reliability [
The advent of advanced technologies in distributed systems has further complicated the
landscape of error detection [
Recognizing this gap, our research pivots to developing an algorithm tailored for distributed systems, focusing on synthesizing false signal sequences. This algorithm adapts and extends existing methodologies originally designed for non-distributed systems to suit the complex requirements of distributed architectures. Our primary objective is to facilitate more accurate, efficient, and reliable monitoring of these systems by honing the detection of erroneous states through an innovative approach to signal synthesis.
This work aims to develop a language for representing regular constraints in distributed systems by available finite sets of events, detecting patterns, and directly recognizing these events in a given distributed system. In the context of this paper, a pattern is a template for the state of a distributed system.
Based on the goal, the following tasks were defined: developing a language that would allow describing patterns of sequences of events and a system for recognizing these patterns. Taken together, the solution of these tasks allows us to control the state of a distributed system by declaring the required system states and analyzing the current state.
During the study, it was proposed to adapt existing mechanisms for pattern recognition in non-distributed systems and a new way of declaring patterns.
The relevance of the work is due to the need to control distributed systems, namely to identify sequences of events that may indicate a malfunction in the system, an attack, etc. To summarize, there is a need to recognize false system states. Currently, some approaches can recognize a false state but cannot make assumptions about states that are not defined as false. It is not always possible to list all such system states, so searching for patterns in known false states and recognizing them is necessary.
This paper presents the study's results: a language for specifying event patterns and a system for recognizing them. The algorithm presented in this paper solves the problem of supplementing a known set of patterns.
Distributed systems are very common in many areas of human activity, such as cyber-physical
systems (e.g., a modern car, airplane, industrial machine) [
Very often, to make a global decision about the further behavior of the system, it is necessary
to have up-to-date information about the states of all nodes or some subset of them. For example,
if we consider an airplane as a cyber-physical system, in order to enable landing mode, the
airplane control system must collect data on the landing gear, flap angle, elevator angle, engine
speed, etc. [
Because of this, the problem of parallel information processing arises, i.e., recognizing a set of signals coming from different system nodes that can be interpreted as a sequence of states, where each element of the sequence is the current state of a particular system node. It is important that the system is able to recognize such states that are a system malfunction (hereinafter referred to as an error in the system). Given that there are many events in such systems, we can summarize the concept of an error to an error pattern, i.e. certain sequences of events in certain nodes, the occurrence of which indicates a malfunction of the system.
The problem is also complicated by the fact that each node of the system can be in many states, and also has its own sequences of states that should be considered a malfunction. To summarize, the task is to recognize disturbances in the distributed system as a whole, which means that it is necessary to build an algorithm for recognizing errors in a two-dimensional vector of system states.
Currently, an algorithm for recognizing and completing error patterns exists and was described
in [
This paper uses and develops the ideas proposed in the article, so here are the main definitions used in the paper.
Definition 1. A regular pattern detector is a tuple
R = 〈Σ, , 0, Π, 〉, where is the alphabet of input signals; Q is a finite set of states; q0 Q is a fixed state called the initial state; is a finite alphabet whose elements denote the corresponding recognized patterns; : Q → + Q is a decision function.
An alphabet is a finite set of characters. A finite sequence of characters is called a word and is denoted by +.
Definition 2. A partial mapping from a set X to a set Y is a subset f X Y such that: if (x, y’) f, where x X and y’, y’’ Y means that y’ = y’’.
f (x) = y means that (x, y) f f (x) = means that (x, y) f y Y f(x) means that y Y: (x, y) f
To determine the -indexed family += { +| Π} of sequence sets recognized by a regular pattern detector R, we need to supplement the decision function with a partial mapping +: Q → + Q which is defined recursively as follows: + (q, a) = (q, a) for any q Q and a + (q, ua) = if + (q, u) = s or + (q, u) + (q, ua) = (q’, a) or + (q, ua) = (q’, a) where q’ Q
Definition 3. The word u + is recognized by a regular pattern detector R as a pattern s (denoted as u R+s) if + (q0, u) = s.
In other words,
R+ = { Σ+| +( 0, ) ↓= }, for any s .
Thus, the indexed family of + = { +| Π} a subset + is associated with any regular pattern detector R. The properties of this family are defined in the following statement.
Statement 1. For any regular pattern detector R, the indexed family R+ has the following properties: 1. Sets with R+ are non-overlapping sets. 2. Each set in R+ is regular.
3. The common plural prefix ⋃ + is an empty word.
The proof of this statement is given in [
Algorithm 1. Synthesis algorithm for regular pattern detectors.
The idea of the algorithm is as follows:
Having any finite alphabet of signals and a finite alphabet of recognizable patterns, we fix as indexed family of mutually non-overlapping sets {Es | x } from finite subsets, which do not have + of the common prefix; a finite subset C + of events that are considered unrecognizable and moreover, = ⋃ Π , where E C = .
The output of the algorithm is a regular pattern detector 〈Σ, , 0, Π, 〉 so that: 1. ⊂ + for all s .
2. ⋂ Π + ∩ = . 3. The number of elements in Q is less or equal to the number of states for any detector satisfying conditions 1 and 2.
Data: is an indexed family of E finite subsets + that do not share a common prefix and a finite subset C +.
Results: regular pattern detector R for all q Q and a : if (q, a) = ⊥ then: choose randomly X from (Q + ) \ {q, ⊥}; redefine (q, a) = x; if u R+s for any s and u C cancel the override; continue; minimize the resulting detector by the Hopcroft method.
The symbol ⊥ is used to indicate a trash state that is not a member of Q. Also, the state that the detector takes after successful pattern recognition is called the terminal state.
Tree-shaped detector 〈Σ, , 0, Π, 〉 is determined by the following way:
Q = { ∈ Σ∗| ∈ ⋃ , ∈ Σ∗} ∪ {⊥},
Π q0 = ; (⊥, a) = ⊥ for all a ; (u, a) = ua if ua Q; (u, a) = ⊥ or else.
The aim of this paper is to develop a recognizer for certain sequences of events in a distributed system, as well as a language that could be used to describe false and non-false sequences. The recognizer should also supplement the set of false sequences by identifying patterns in known sequences.
In the context of this work, these sequences are called regular constraints because they are the language of the detector. This language is also called the syntax of regular constraints on the behavior of a distributed system with an output. Thus, it is necessary to develop an algorithm that, given a finite set of constraints and words that are not constraints, will synthesize a syntax to represent the regular constraints of a certain system with an output.
The constructed detector should have the following properties: 1. Parallel recognition of signals from nodes of a distributed system 2. Minimum number of states of the resulting detector
The main difference, and the reason why it is impossible to use the existing synthesis algorithm to solve the problem, is that the system is divided, and at one moment of time signals can come from many channels. If we assume that there are channels, and the 3d channel receives messages constructed over the alphabet, then if we collect data from all channels at a certain point in time, we get a vector of length, which will represent the current state of the system.
Theoretically, such a word could be considered a regular constraint, but constraints in a system exist not only globally (for the entire system), but also for its individual nodes. If you declare constraints in this way, it will be difficult to distinguish and understand, looking at the constraints in this form, how the system as a whole should actually behave, and how its individual elements should behave.
In this case, it is possible to use the principle of "divide and conquer" [
Since the global state of the system is completely dependent on its parts, and the parts of the system are ordinary message generators, we can set constraints for each part of the system separately and check the state of a particular element of the distributed system. The state of each individual element of the system can be generalized to the state of normal operation or to the state of error, which can be represented by an alphabet of only two letters, for example, 0 and 1, accordingly.
It is worth mentioning that the survey of system elements on their condition occurs with a certain periodicity, so we will consider time as discrete.
Thus, the task comes down to first recognizing the signals from each element of the system
separately, and for this purpose, there is already a detector algorithm described in [
If a detector is created for each of the system elements, then the trash state, or any nonterminal state, can be considered as 0, and the terminal state as 1. In this context, the existence of a terminal state indicates the recognition of an error pattern in a system element.
After implementing detectors for individual elements of a distributed system, the output vector obtained from the elements is simply a sequence of 0s or 1s. This sequence can be further simplified by considering it as a binary representation of a non-negative integer. Since we need to recognize a word again (though now only over a two-character alphabet), we can use the idea of a detector again. We will call this detector a coordinating detector because it recognizes the word obtained from the current recognition results of the detectors on each node of the system.
Now the main problem is the number of states in such a recognizer - that is, the number of possible transitions equal to because from each state it is possible to transfer to any other state. This number of states is not satisfactory, because the number of states grows very quickly with the number of elements of the distributed system.
This means that it is not necessary to generate all theoretically possible states, but only those that can appear with a high probability. It is also necessary to determine the total number of generated states, or the steps that the state generation algorithm will take because the algorithm must stop at some point.
To optimize the number of states, it is worth considering the following concepts the intensity of each signal source (system element). Based on the information about the frequency of receiving messages, the next state can be predicted from a given state, and then there is no need to create transitions from this state to unlikely states, which can save both the number of states and the number of transitions. Additionally, there is a limit to the length of each word of the coordinating detector. In fact, given that there are a total of channels, the length of the coordinating detector word is always equal to , since the i-th character of this word corresponds to the current state of the i-th channel.
Therefore, it is recommended to use: 1. Alphabet for the coordinating detector. Restriction - words are built over this alphabet. 2. Any alphabet is necessary for an element of the system to describe its states (in the context of this work, this is not important, because we only need the result of the node detector) 3. An algorithm for synthesizing new states based on the frequency of messages (other approaches for synthesizing states will also be considered in the work).
First, let us explain some notations that will be used in the following algorithms.
D is a set of words to be recognized by the detector. Hereinafter, the words consist of the alphabet = {0, 1}; N is a set of words that should not be recognized by the detector; n is number of channels (system elements); |D| is the number of words to be recognized by the detector; |N| is the number of words to be recognized by the detector.
Algorithm 2: Calculating the intensity of each channel.
Data: channels Ch = {S1, …, Sn} limitations | ℎ| = , | | = ∀ = 1 … Result: Tuple 〈 1, … , 〉 of frequencies of each channel.
For each Ch from
| | ℎ = ∑ ,
=1 ℎ = | ℎ|.
The graph below shows the expected number of signals from each element of the system at each moment of time, the number of channels = 5. Values received per channel: {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 0}, {0, 0, 1, 1, 1}, {0, 1, 0, 1, 0}
The vertical line divides the chart into two halves: the left half shows the actual number of signals (cumulative), and the right half shows the expected number of signals.
Initialize the current state cur For each r with D: (cur, r) = cur + r cur = cur + r For each sequence sd D For each state q in Sd
Initialize the current state cur = q
Initialize the current transition oldNext = (q)
Generate |D| of new states G using algorithm (3)
For each state g with G:
(cur, g) = cur + g
cur = cur + g
If recognized s N
Remove new states (q) = oldNext
Minimize the detector with the Hopcroft algorithm [
When generating new states, it is important not to significantly change the theoretical frequency of each channel. That's why a sequence of random states is generated, because the initial frequency is measured by the characteristic of the states. Also, the algorithm needs to be stopped, although theoretically it can be generated until the states satisfy the frequency characteristics. Of course, the generation of states does not guarantee that the resulting sequences will have a frequency close to the initial one.
However, it is possible to filter out sequences whose frequency characteristics differ from the initial ones, and the degree of difference can be adjusted using the parameter, which can be used to set the maximum frequency deviation from the initial frequency characteristic. Next, we propose an algorithm for removing generated sequences whose frequency differs from the initial one by more than.
Algorithm 5. Removing sequences that do not meet the frequency characteristics.
Data: a tree-like detector R with states Q + Qg, frequency characteristics = 〈 1, … , 〉, parameter of absolute frequency difference .
For each sequence s R Determine the expected frequency fe of each channel for s Remove the last states |D| from s, if i 1…n: |fi - fe| < .
The algorithm removes only the last |D| states of sequences whose frequency characteristics do not meet the requirements. It is obvious that since algorithm (4) generated exactly |D| new states, if the frequency response has changed, it is due to the new states, not the existing ones, on the basis of which the initial frequency was calculated. Moreover, deleting the entire sequence reduces the number of initial sequences.
As a result of algorithms (4) and (5), we have a system of states with transitions (in fact, a deterministic automaton) that recognizes error patterns and does not recognize patterns of normal system behavior, which is what we needed to do. The set of error patterns is supplemented by generating new states and transitions based on information about the frequency of events in each element of the system. Each generated sequence corresponds to the given sequences in terms of frequency characteristics; at best, the number of completed transitions is |D|2; at worst, 0 if all generated states and transitions differ from the specified characteristics.
Additionally, it should be noted that for elements of a distributed system, it is assumed that the transition to the terminal state does not mean the transition to the terminal state of the entire system, and when such a state appears, the system element signals it and transitions to the initial state.
Figures 2, 3 shows states and transitions before and after running the synthesis algorithm (4). Figure 3: Graph of the enumerations of the algorithm (4)
As mentioned in the previous section, the algorithm for generating new states and sequences should preserve the frequency characteristics of the channels. We also proposed a sequence filtering algorithm based on the absolute frequency difference parameter. The optimal value of the parameter remains an open question є. It is worth noting that the value of this parameter does not affect the accuracy of the detector, but only affects the number of states of the resulting automaton. At any value of the parameter, the algorithm does not recognize normal (not false) sequences, but only changes the number of probable false sequences.
Below is a graph of the dependence of the number of states of the resulting detector on the value of the parameter є. The sequence of initial false states:
{0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 0}, {0, 0, 1, 1, 1}, {0, 1, 0, 1, 0}
Sequence of normal states {0, 1, 1, 1, 0}, {0, 1, 0, 1, 0}. The parameter є changes from 0 to 0.5 in increments of 0.1. The horizontal line indicates the total number of states generated by the synthesis algorithm (4), but before the filtering algorithm (5) is run. The algorithms were implemented using the Python program language
The graph shows that the frequency deviation does not exceed 0.4 for any of the generated sequences. From the graph, we can conclude that the number of states depends on the parameter є almost linearly.
Another important information for understanding the behavior of the algorithm depending on
the parameter є is the value of the average deviation of the actual channel frequency from the
expected one. To get the average deviation, we find the average difference between the expected
frequency of each channel and the actual one. Below is a graph of the average deviation versus
from є.
The average deviation correlates with the number of states, but does not exceed 0.1.
Next, it is necessary to compare the obtained results with the conventional synthesis
method for the detector described in [
We also use the same constraints as for the coordinating detector: the sequence of initial false states:
{0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 0}, {0, 0, 1, 1, 1}, {0, 1, 0, 1, 0}
A sequence of normal states: {0, 1, 1, 1, 0}, {0, 1, 0, 1, 0}. It is important to know the number of states in the generated detector, as well as the average frequency deviation.
The algorithm must be run many times in a row to obtain a reliable average because the algorithm depends on a random number generator.
After running the algorithm on the test dataset twenty times in a row, the average frequency deviation was 0.1895. The number of states does not depend on random numbers and is equal to 26. Below is a graph of frequency deviations depending on the algorithm execution. The minimum average deviation was 0.15, the maximum was 0.2.
Based on the results of both algorithms, we can conclude that with the same number of states in both algorithms, the accuracy of the algorithm proposed in this paper is exactly twice as high, as evidenced by the difference in the average frequency difference - 0.9 at є = 0.25 for the proposed algorithm, and 0.19 for the existing algorithm. Thus, 0.25 can be considered the optimal value. However, the flexibility of the algorithm allows it to be adapted to different use cases.
To increase the generation accuracy, you need to reduce the value of є, but get fewer generated sequences. If you need as many generated sequences as possible, you can increase the parameter, neglecting the possible error.
The result of the study is a developed and analyzed algorithm for synthesizing false signal
sequences based on finite sets of false and non-false sequences. This algorithm is an adapted
version of an existing algorithm for a non-distributed system with an output [
As a result of our work, we have achieved: 1.A language of constraints for a distributed system with an output has been developed 2.The optimal number of detector states was achieved, which is less than the maximum theoretically possible number.
3.A mechanism for adjusting the accuracy of transition detection has been developed The results of this work may allow researchers to develop new automated systems for monitoring the operation of distributed systems, or improve the efficiency of existing solutions. This could allow for greater automation in the operation and monitoring of distributed systems, potentially meaning more reliable systems.
As an intermediate conclusion, this algorithm can be used for experimental purposes, on test samples to investigate the very effectiveness of synthesis algorithms and the approach to processing parallel events in general. Further development of the idea can be carried out in several directions: increasing the probability of guessing a false state, further reducing the total number of states, and further simplifying the constraint language.