Compatibility among diversity Foundations, lessons, and directions of semantic communication

We give an overview of a theory of semantic communication proposed by Goldreich, Juba, and Sudan. The theory is intended to capture the obstacles that arise when a diverse population of independently designed devices must communicate with one another. The aim of the theory is to provide conceptual foundations for the design and evaluation of devices that are compatible with such a diverse population. Conclusions drawn from the theory (i) identify a kind of information-sensing that is inherently necessary for compatibility whenever the population is sufficiently diverse and (ii) identify tensions between the richness of diversity and the computational cost of coping with such diversity in a population. We will review how these considerations are reflected in the formulation and design of an example application, a self-patching packet network stack. In particular, this application will illustrate the utility of explicit consideration of various computational complexity measures in addressing both (i) and (ii). We will also review work aimed at identifying kinds of populations across which compatibility can be achieved efficiently.