«INFORMATICS AND APPLICATIONS»
Scientific journal
Volume 19, Issue 1, 2025

Content | About  Authors

Abstract and Keywords

UNIVERSAL CONSTRUCTIONS IN ALGEBRAIC SPECIFICATION OF DISTRIBUTED SYSTEMS

• S. P. Kovalyov  V. A. Trapeznikov Institute of Control Sciences of the Russian Academy of Sciences, 65 Profsoyuznaya Str., Moscow 117997, Russian Federation

Abstract: The paper presents recent developments in the previously proposed generalized approach to algebraic specification of distributed systems based on the novel category-theoretic construction called graphalgebra. The graphalgebraic specification is based upon a directed multigraph, the edges of which represent computational operations performed in the nodes of the system and the vertices denote the data exchange ports between the components. Thus, deployment of operations upon the system nodes is specified explicitly. It is also advisable to explicitly describe, in the language of graphalgebras, the procedures for constructing systems towards the target deployment. To this end, the paper defines the constructions of subgraphalgebra, quotient graphalgebra, and bisimulation of graphalgebras and proves their key properties for the first time. The means to construct limits and colimits of suitable diagrams of graphalgebras are proposed. The theoretical results are illustrated by an example of calculating a limit in the category of deep neural networks.

Keywords: algebraic specification; distributed system; universal algebra; category theory; graphalgebra; subalgebara; bisimulation

ON GAME NETWORKS STRUCTURE OPTIMIZATION IN MULTIAGENT SYSTEMS

• N. S. Vasilyev  Bauman Moscow State Technical University, 5-1 Baumanskaya 2nd Str., Moscow 105005, Russian Federation

Abstract: Monoidal category of binary relations is applied to study and optimize large multiagent systems. Agents' communication networks structure choice is essential part of players' strategies. It must be selected to resolve the conflict of interests. Compositionality of the problem in the monoidal category gives possibility to solve it. Notion of the optimal game networks structure is contributed. The definition is based on equilibria and effectiveness principles usage. A method is proposed to find the optimal structure. It uses families of binary relations to compare given agents' preferences relations. Players' optimal communication structure is built by means of the most expedient players' coalitions search. Matrix algebra presentation of binary relations allows computing it. On the ground of the method, a new technology to study and optimize large multiagent systems can be built. Its program realization is supported by computer category algebra.

Keywords: monoidal category; preference relation; communication network; game network structure; expedient coalition; characteristic relation; resulting relation; compositionality

GUARANTEED ESTIMATES OF THE MULTIUSER NETWORK PERFORMANCE INDICATORS IN CASE OF DAMAGE

• Yu. E. Malashenko  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
• I. A. Nazarova  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: Within the framework of computational experiments, the performance indicators of a multiuser communication network are investigated when single node is destroyed. In the simulation, arrays of data on the transmission routes of maximum internodal flows are analyzed. Changes in edge loading and transit flows through undamaged network nodes are being studied. Relative differentiated indicators are calculated that characterize the dependence of transmitted flows on a decrease in network capacity when one node is damaged. Multicriteria guaranteed estimates of the maximum possible deviations from the indicators of functioning of undamaged network in stationary mode are formed. A comparative analysis of the results obtained by using two routing schemes for the transmission of equal interstitial flows is carried out. Summary diagrams for networks with various structural features are provided.

Keywords: streaming model of the communication network; guaranteed estimate in case of node damage

FILTERING OF STATES AND PARAMETERS OF SPECIAL MARKOV JUMP PROCESSES VIA INDIRECT PERFECT OBSERVATIONS

• A. V. Borisov  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The paper investigates the problem of optimal state filtering of a class of stochastic differential observation systems. The state to be estimated consists of two compound components. The first is a finite-state Markov jump process. The second component changes synchronously with the first one and, given a fixed first component, forms a sequence of independent vectors. The available statistical information includes the known functions of the estimated state observed without noise. The problem is to construct the conditional distribution of the system's state given the available observations. In observation systems with degenerate noise, it is impossible to apply standard filtering techniques, which typically involve reducing the observations to a combination of Wiener and Poisson processes using a suitable Girsanov measure transform. The conditional distribution ofthe state can be represented using a recursively linked sequence ofordinary differential and difference equations.

Keywords: Markov jump process; stochastic differential observation system; indirect perfect observations; martingale decomposition; regular version of conditional distribution

DOPPLER MEASUREMENTS APPLICATION ANALYSIS TO IDENTIFY MOTION PARAMETERS FROM OBSERVATIONS WITH RANDOM DELAYS

• A. V. Bosov  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The moving object positioning problem statement uses a model of a stochastic dynamic observation system with random time delays between the subsequent observation and the actual state of the object and the presence of unknown motion parameters. For such a model, using the example of an underwater vehicle (UV), the variants of the observation formation are analyzed. The first uses only stationary acoustic sensors which allow measuring only angular coordinates. In the second variant, the measurements are supplemented by velocity measurements performed both on board the moving object and by external observers. Each model is used in two ways: assuming that there is complete a priori information about the parameters of the UV movement and in the absence of data on the values of some of the parameters. In the latter variant, the positioning problem is solved in conjunction with the task of unknown motion parameters identification. The models and the results of their experimental application are compared in order to qualitatively assess the effectiveness of using velocity measurements. To do this, a conditionally minimax nonlinear filter is applied to the problem. A comparative analysis of the models of the observation system was performed as a part of a large-scale computational experiment.

Keywords: nonlinear stochastic observation system; Bayesian parameter identification; observations with random time delays; conditionally minimax nonlinear filter; positioning; acoustic sensors; Doppler effect

NORMAL CONDITIONALLY-OPTIMAL FILTERING METHODS FOR IMPLICIT STOCHASTIC SYSTEMS

• I. N. Sinitsyn  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The paper is dedicated to nonlinear synthesis of normal conditionally-optimal (in Pugachev sense) filters (NCOF) for information processing in interconnected observable implicit object stochastic systems (StS) reducible to explicit. Differential and difference equations of observable non-Gaussian StS are presented and methods of its reduction are considered. Special attention is paid to nonsmooth implicit StS. Differential NCOF equations are derived by methods of normal approximation (NAM) of the set of differential equations for object, observation system, and Pugachev conditionally-optimal filters. Difference NCOF equations based on NAM are given for nonlinear regression and autoregression StS models. Some generalizations for complex implicit StS and control StS are formulated.

Keywords: conditionally-optimal (in Pugachev sense) filter; implicit stochastic system; normal approximation method (NAM); normal suboptimal filter (NSOF); stochastic process (StP)

ONE QUEUING SYSTEM WITH CORRELATED INPUT FLOW

• A. K. Bergovin  Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation
• A. M. Ryazanov  Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation
• V. G. Ushakov  Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: A single-line queuing system with an infinite number of waiting places, an arbitrary distribution of service time, and a Poisson incoming flow with random intensity is considered. The intensities are subordinated to the autoregressive dependence of the first order. The j oint distribution of the number of total customers in the system is obtained as well as the sojourn time of a customer in the system in a nonstationary regime. Expressions for stationary distributions and their probabilistic characteristics are also presented. The average sojourn time in the system in the stationary regime is numerically studied and illustrated under different assumptions on the distribution of service time and on the characteristics of the incoming flow. Comparison is made with the classical M |G| 1 queue.

Keywords: random intensity; queue length; waiting time; passive traffic analysis; quality of service

COMPARATIVE ANALYSIS OF QUEUING SYSTEM STABILITY TESTS

• M. P. Krivenko  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The article discusses two types of procedures for statistical control of the stability of the queuing system: comparison of the intensities of input and output flows and detection of nonstationarity of the sequence of sojourn times. In the first case, we are talking about methods for processing matched pairs and in the second case, we are talking about single-root tests for first-order autoregression models. The procedure for collecting and fixing initial data is specified, since in one case, it is tied to moments in time and in the second - to event numbers. The two types of stability tests used refer to weak significance tests, for which the basic null hypotheses are different and complement each other. This is immediately evident when they are compared: the results are better when the assumptions of the corresponding null hypotheses are satisfied. To take into account such features, a composite criterion is built on the basis of consensus and randomization, which leads to an increase in the number of error-free solutions. Further improvement in the quality of decisions can be achieved in the procedure for comparing the critical levels of significance of individual criteria. The results were obtained by the Monte-Carlo method for a specific type of queuing system operating with a simple Poisson input flow. Violation of this assumption can become a destabilizing factor, for the description of which the model of the batch Poisson process was introduced. For it, by varying the intensity of batch arrival and the batch size mean, it is possible to form input streams of different structures with the same intensity. It was found that as the batch increases, the number of implementations generated by the queuing system that demonstrate instability increases; the size of the batch can be a source of a significant increase in the time spent in the system in comparison with the option of single batches; and the use of single root tests can lead to erroneous conclusions about instability.

Keywords: queueing system; sample-path stability; matched pairs tests; unit root tests; Dickey-Fuller tests; omnibus test of stability; batch Poisson process; size of batch as a destabilizing factor

PERTURBATION AND TRUNCATION BOUNDS FOR ONE CLASS OF MARKOV PROCESSES OF BIRTH-AND-DEATH TYPE WITH CATASTROPHES

• I. A. Usov  Department of Applied Mathematics, Vologda State University, 15 Lenin Str., Vologda 160000, Russian Federation
• Y. A. Satin  Department of Applied Mathematics, Vologda State University, 15 Lenin Str., Vologda 160000, Russian Federation, Moscow Center for Fundamental and Applied Mathematics, M.V. Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation
• A. I. Zeifman  Department of Applied Mathematics, Vologda State University, 15 Lenin Str., Vologda 160000, Russian Federation, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
• V. Yu. Korolev  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation, Moscow Center for Fundamental and Applied Mathematics, M.V. Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation, Faculty of Computational Mathematics and Cybernetics, M.V. Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation

Abstract: A class of inhomogeneous continuous-time Markov chains of birth-and-death type with a countable state space is considered. Two types of additional transitions are allowed in the chain, which bring it either to the boundary state or to the state adjacent to it. It is assumed that with an increase in the state number, the birth (death) intensities monotonically decrease (increase). Perturbation bounds are obtained using special weighted norms associated with the total variation. An estimate of the approximation error, when one replaces the original chain by a process with a finite number of states, is constructed. For the case when all the intensities are state-dependent, conditions are provided (using the logarithmic norm method), which guarantee (weak) ergodicity in the norm of total variation. Results are accompanied by illustrative examples.

Keywords: queuing system; birth-and-death process; catastrophes; truncation bounds; perturbation bounds

SOLVING INVERSE STATISTICAL PROBLEMS USING THRESHOLD PROCESSING METHODS THAT ALLOW THE CONSTRUCTION OF AN UNBIASED ESTIMATE OF THE MEAN-SQUARE RISK

• O. V Shestakov  Department of Mathematical Statistics, Faculty of Computational Mathematics and Cybernetics, M. V Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation, Moscow Center for Fundamental and Applied Mathematics, M.V. Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation

Abstract: The methods of wavelet analysis in combination with threshold processing procedures are widely used in the tasks of estimating the signal function from noisy data. Their popularity is explained by their adaptability to the local features of the studied functions and the high speed of processing algorithms. This approach has also proved fruitful for the inversion of linear homogeneous operators that arise in some signal and image processing tasks. The most common types of threshold processing are hard and soft threshold processing. However, when using hard threshold processing, estimates with large variance are obtained and soft threshold processing leads to an additional bias. In an attempt to get rid of these disadvantages, various alternative types of threshold processing have been proposed in recent years. In this paper, the author considers a class of threshold functions that allow the construction of an unbiased estimate of the mean-square risk. This estimate makes it possible to analyze the error of noise reduction methods. The study of the properties of unbiased risk estimate is an important practical task, since it allows one to assess the quality of both the methods themselves and the equipment used. The paper discusses strategies for choosing threshold values and provides statements about the asymptotic normality and strong consistency of the risk estimate.

Keywords: wavelets; threshold processing; linear homogeneous operator; unbiased risk estimate

METRIZATION OF DISCRETE TOPOLOGICAL SPACES IN THE CONTEXT OF LATTICE THEORY. PART 1. ON THE NORMALITY OF SPACES

• I. Yu. Torshin  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: A fundamental problem in machine learning and other modern methods of data analysis is the solution to the issue of generating metric distance functions (metrics) that would be adequate to the applied problems under study. The paper presents the results of a systematic analysis of the possibilities of metrization of discrete topological spaces using the concepts of lattice theory. A theorem on the regularity and normality of topological spaces arising in problems of recognition, classification, and numerical forecasting is proved. The regularity (according to Zhuravlev) of a set of precedents guarantees the normality of a topological space (separability axiom T4) and, consequently, the metrizability of this space. The author plans to put practical applications of the consequences of the theorem on regularity and normality presented in a separate paper that will make it possible to systematize the search forproblem-oriented metrics which are most suitable for a particular applied problem.

Keywords: topological data analysis; lattice theory; algebraic approach of Yu. I. Zhuravlev and K. V. Rudakov; separation axioms