PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Pairs of Words with Nonmaterializable Mutual Information
A. E. Romashchenko
pp. 1–18

Abstract—Let there be a pair of words $\langle a,b\rangle $ with sufficiently large mutual information. Can we always “materialize” this information, i.e., point out a word $c$ that can be computed from $a$ and $b$ simply and whose Kolmogorov complexity equals the mutual information between $a$ and $b$? In this paper, we propose a better estimate for the amount of mutual information which may be materialized for words from the construction of Gács and Körner, and also give a new method for constructing pairs of words with nonmaterializable mutual information.

Note on “On the Asymptotic Capacity of a Multiple-Access Channel” by L. Wilhelmsson and K. Sh. Zigangirov
P. Gober and A. J. Han Vinck
pp. 19–22

Abstract—This note refers to the paper [Probl. Inf. Trans., 1997, vol. 33, no. 1, pp. 9–16], in which the capacity of a $T$-user $q$-ary multiple-access channel is studied for both the coordinated and uncoordinated cases. We give bounds for the capacities as $T \to \infty$ and discuss results of numerical calculations for various values of $T$.

Nonergodicity of a Queueing Network under Nonstability of Its Fluid Model
A. A. Puhalskii and A. N. Rybko
pp. 23–41

Abstract—We study ergodicity properties of open queueing networks for which the associated fluid models have trajectories that go to infinity. It is proved that if a trajectory is stable in a certain sense and grows to infinity linearly, then the underlying stochastic process is nonergodic. The result applies to the basic nontrivial examples of nonergodic networks found by Bramson, and Rybko and Stolyar. The proof employs some general results from the large deviation theory.

Large Deviations in Some Queueing Systems
N. D. Vvedenskaya, E. A. Pechersky, and Yu. M. Suhov
pp. 42–53

Abstract—Logarithmic asymptotics of probabilities of large delays are derived for the “last come–first served” system and system with priorities. Trajectories that determine the mean dynamics of arrival flow under the condition of large delay are described.

Global Stability of Infinite Systems of Nonlinear Differential Equations and Nonhomogeneous Countable Markov Chains
V. I. Oseledets and D. V. Khmelev
pp. 54–70

Abstract—Countable systems of differential equations $\dot x=f(x)$ in $X\subset l_1$ with bounded Jacobi operators $J(x)=\partial f/\partial x$ are studied. Sufficient conditions of global stability and global asymptotic stability are obtained, where for any $x\in X$ the matrix $J^{\rm T}(x)$ is the transition-rate matrix for a countable Markov chain and $X$ is a subset of a linear affine variety. Results are applied to two infinite systems arising from the modern queueing theory.

Study of Controlled Asynchronous Multiple Access in Satellite Communication Networks with Conflict Warning
A. A. Nazarov and S. L. Shokhor
pp. 71–84

Abstract—Communication networks with a dynamical random-multiple-access protocol with conflict warning free of corrupted message losses are examined. A non-Markovian network model is constructed. Using the method of generating functions, main probability parameters are found. Results obtained are compared with those found in [Izv. Vuzov, Ser.: Fiz., 1992, no. 9, pp. 120–129] by asymptotic methods. The domain of validity of asymptotic results is found.

A Simply Realizable Ideal Cryptographic System
B. Ya. Ryabko
pp. 85–89

Abstract—We suggest a construction for an ideal cryptographic system, whose enciphering and deciphering complexity is exponentially less than that of known systems.