Digital communication has become a powerful generic tool to deal with any communication problem. Specifically, faced with the problem of transmitting multimedia data across a lossy link (such as the internet), the communications engineer of today will use sophisticated compression techniques to describe the (video, audio, ...) source with the smallest number of bits. In a separate stage, error control coding is used to communicate these bits across the lossy medium without incurring errors.

The theoretical underpinnings of this generic strategy lie in Shannon's separation theorem, asserting that without loss of optimality, the communication strategy can be designed in two separate stages, namely, source coding on the one, and channel coding on the other hand.

From this perspective, bits are the universal currency of information.

Of course, Shannon's theorem comes with a few strings attached. Most importantly, the optimality Shannon refers to excludes computational complexity and delay from view. It only considers the physcial channel resources - number of channel uses per second, transmit power, bandwidth, etc. - and the resulting end-to-end quality of service (that is, the loss between the original video sequence at the sender and its reconstruction at the receiver). As soon as delay and complexity become important, then one may want to jointly design source and channel coding, and a lot of research has gone into this. The problem is that no similarly general design theory is available, and therefore, most code designs remain ad-hoc. Moreover, mathematically, the source and the channel must be stationary and ergodic, though this can be slightly relaxed in some cases.

However, the most spectacular "string attached" to Shannon's theorem concerns general networks. Specifically, Shannon's theorem only applies to point-to-point links. It has long been known that joint source-channel coding can outperform the digital communications approach in some network examples. However, in a certain sense, the folk theorem was that digital communication is "essentially" good enough.

The starting point of our investigations is that this is not correct: In large networks, the "separate design" approach can lead to an exponentially suboptimal performance. This appears to be particularly important for sensor networks.

In other words, Bits cannot be argued to be the universal currency of information in general networks!

The simplest example illustrating the huge gap that can occur between the world of bits and the truly optimal communication systems is perhaps the following:

There is a single underlying source of interest (called X in the figure), and M sensors make independently noisy measurements. We assume that X is real-valued and random, and that all the measurement noises (called W in the figure) are also random and independent of each other. The source produces a new X every time unit, and each sensor makes one noisy observation per time unit. The sensors are allowed to "bunch up" many measurements, and to encode them using as sophistsicated a coding technique as they want. However, whatever they transmit towards the data collection point goes across a multiple-access channel, subject to additive noise. The data collection point wishes to recover the underlying source X to within mean-squared error. How well can this be done?

Denoting the resulting mean-squared error by D, our result shows that any digital strategy can hope to attain a distortion that behaves at best like 1/log(M), which the optimal strategy attains a distortion that behaves like 1/M. In other words, if you fix a target distortion D for which the optimal strategy requires M sensors, then the digital strategy will require exp(M) sensors!

A similar phenomenon can be observed in the problem of computation over multiple-access channels