This article studies the zero-error feedback capacity ofcausaldiscrete channels with memory. First, by extending the classical zero-error feedback capacity concept, a new notion ofuniform zero-error feedback capacity$C_{0f} $for such channels is introduced. Using this notion a tight condition for bounded stabilization of unstable noisy linear systems via causal channels is obtained, assuming no channel state information at either end of the channel. Furthermore, the zero-error feedback capacity of a class of additive noise channels is investigated. It is known that for a discrete channel with correlated additive noise, the ordinary capacity with or without feedback is equal$\log q-\mathcal {H}_{ch} $, where$\mathcal {H}_{ch} $is the entropy rate of the noise process and$q $is the input alphabet size. In this paper, for a class of finite-state additive noise channels (FSANCs), it is shown that the zero-error feedback capacity is either zero or$C_{0f} =\log q -h_{ch} $, where$h_{ch} $is thetopological entropyof the noise process. A condition is given to determine when the zero-error capacity with or without feedback is zero. This, in conjunction with the stabilization result, leads to a “Small-Entropy Theorem”, stating that stabilization over FSANCs can be achieved if the sum of the topological entropies of the linear system and the channel is smaller than$\log q$.

Wireless networked control systems (WNCSs) provide a key enabling technique for Industrial Internet of Things (IIoT). However, in the literature of WNCSs, most of the research focuses on the control perspective and has considered oversimplified models of wireless communications that do not capture the key parameters of a practical wireless communication system, such as latency, data rate, and reliability. In this article, we focus on a WNCS, where a controller transmits quantized and encoded control codewords to a remote actuator through a wireless channel, and adopt a detailed model of the wireless communication system, which jointly considers the interrelated communication parameters. We derive the stability region of the WNCS. If and only if the tuple of the communication parameters lies in the region, the average cost function, i.e., a performance metric of the WNCS, is bounded. We further obtain a necessary and sufficient condition under which the stability region is n -bounded, where n is the control codeword blocklength. We also analyze the average cost function of the WNCS. Such analysis is nontrivial because the finite-bit control-signal quantizer introduces a nonlinear and discontinuous quantization function that makes the performance analysis very difficult. We derive tight upper and lower bounds on the average cost function in terms of latency, data rate, and reliability. Our analytical results provide important insights into the design of the optimal parameters to minimize the average cost within the stability region.

It is known that for a discrete channel with correlated additive noise, the ordinary capacity with or without feedback both equal log q-H(Z), where H(Z) is the entropy rate of the noise process Z and q is the alphabet size. In this paper, a class of finite-state additive noise channels is introduced. It is shown that the zero-error feedback capacity of such channels is either zero or C0f= log q - h(Z), where h(Z) is the topological entropy of the noise process. Moreover, the zero-error capacity without feedback is lower-bounded by log q-2h(Z). We explicitly compute the zero-error feedback capacity for several examples, including channels with isolated errors and a Gilbert-Elliot channel.

Although state estimation in networked control systems is a fundamental problem, few efforts have been made to study distributed state estimation via multiple access channels (MAC’s). In this article, we give a characterization of the zero-error capacity region of an M-input, single-output MAC at any finite block-length. To this end, nonstochastic information-theoretic tools are used to derive the converse and achievability proofs. Next, a tight condition to be able to achieve uniformly bounded state estimation errors over such a MAC is provided. The obtained condition establishes a connection between the intrinsic topological entropies of the linear systems and the zero-error capacity region of the MAC.

We consider private function evaluation to provide query responses based on private data of multiple untrusted entities in such a way that each cannot learn something substantially new about the data of others. First, we introduce perfect non-stochastic privacy in a two-party scenario. Perfect privacy amounts to conditional unrelatedness of the query response and the private uncertain variable of other individuals conditioned on the uncertain variable of a given entity. We show that perfect privacy can be achieved for queries that are functions of the common uncertain variable, a generalization of the common random variable. We compute the closest approximation of the queries that do not take this form. To provide a trade-off between privacy and utility, we relax the notion of perfect privacy. We define almost perfect privacy and show that this new definition equates to using conditional disassociation instead of conditional unrelatedness in the definition of perfect privacy. Then, we generalize the definitions to multi-party function evaluation (more than two data entities). We prove that uniform quantization of query responses, where the quantization resolution is a function of privacy budget and sensitivity of the query (cf., differential privacy), achieves function evaluation privacy.

In this paper, we investigate zero-error communication over M-user multiple access channels with correlated transmitters. The correlation among the users is modeled by means of both a common message seen by all encoders as well as pairwise shared messages. Motivated by networked control systems, we use tools from nonstochastic information theory to characterize the zero-error capacity region of the investigated channel. To this end, both converse and achievability proofs are provided.

This paper studies the complexity of solving two classes of non-cooperative games in a distributed manner, in which the players communicate with a set of system nodes over noisy communication channels. The complexity of solving each game class is defined as the minimum number of iterations required to find a Nash equilibrium (NE) of any game in that class with ∈ accuracy. First, we consider the class G of all N-player non-cooperative games with a continuous action space that admit at least one NE. Using information-theoretic inequalities, a lower bound on the complexity of solving G is derived which depends on the Kolmogorov 2∈-capacity of the constraint set and the total capacity of the communication channels. Our results indicate that the game class G can be solved at most exponentially fast. We next consider the class of all N-player non-cooperative games with at least one NE such that the players' utility functions satisfy a certain (differential) constraint. We derive lower bounds on the complexity of solving this game class under both Gaussian and non-Gaussian noise models. Finally, we derive upper and lower bounds on the sample complexity of a class of quadratic games. It is shown that the complexity of solving this game class scales according to Θ (1/∈2) where € is the accuracy parameter.

Worst-case models of erasure and symmetric channels are investigated, in which the number of channel errors occurring in each sliding window of a given length is bounded. Upper and lower bounds on their zero-error capacities are derived, with the lower bounds revealing a connection with the topological entropy of the channel dynamics. Necessary and sufficient conditions for linear state estimation with bounded estimation errors via such channels are then obtained, by extending previous results for non-stochastic memoryless channels to those with finite memory. These estimation conditions involve the topological entropies of the linear system and the channel.

The problem of characterising the zero-error capacity region for multiple access channels even in the noiseless case has remained an open problem for over three decades. Motivated by this challenging question, a recently developed theory of nonstochastic information is applied to characterise the zero-error capacity region for the case of two correlated transmitters. Unlike previous contributions, this analysis does not assume that the blocklength is asymptotically large. Finally, a new notion of nonstochastic information is proposed for a non-cooperative problem involving three agents. These results are preliminary steps towards understanding information flows in worst-case distributed estimation and control problems.

As the size of robots decreases in multirobot systems, collisions cease to be catastrophic events that need to be avoided at all costs. This implies that less conservative, coordinated control strategies can be employed, where collisions are not only tolerated, but can potentially be harnessed as an information source. In this paper, we follow this line of inquiry by employing collisions as a sensing modality that provides information about the robots' surroundings. We envision a collection of robots moving around with no sensors other than binary, tactile sensors that can determine if a collision occurred, and let the robots use this information to determine their locations. We apply a probabilistic localization technique based on mean-field approximations that allows each robot to maintain and update a probability distribution over all possible locations. Simulations and real multirobot experiments illustrate the feasibility of the proposed approach.

Information does not generally behave like a flow in communication networks with multiple sources and sinks. However, it is often conceptually and practically useful to be able to associate separate data streams with each source-sink pair, with only routing and no coding performed at the network nodes. This raises the question of whether there is a nontrivial class of network topologies for which achievability is always equivalent to “routability”, for any combination of source signals and positive channel capacities. This paper considers a possibly cyclic, directed, errorless network with n source-sink pairs, mutually independent source signals, and a relaxed communication objective in terms of demanded information rates at sinks. The concept of triangularizability is introduced and it is shown that, if the network topology is triangularizable, then a given combination of source signals, demand rates and channel capacities is achievable if and only if the digraph supports a feasible multicommodity flow.

The emerging area of control with limited data rates incorporates ideas from both control and information theory. The data rate constraint introduces quantization into the feedback loop and gives the interconnected system a two-fold nature, continuous and symbolic. In this paper, we review the results available in the literature on data-rate-limited control. For linear systems, we show how fundamental tradeoffs between the data rate and control goals, such as stability, mean entry times, and asymptotic state norms, emerge naturally. While many classical tools from both control and information theory can still be used in this context, it turns out that the deepest results necessitate a novel, integrated view of both disciplines.