New theory could yield more-reliable Communication Protocols

Communication protocols for digital devices are very efficient but also very brittle: They require information to be specified in a precise order with a precise number of bits. If sender and receiver—say, a computer and a printer—are off by even a single bit relative to each other, communication between them breaks down entirely.

Humans are much more flexible. Two strangers may come to a conversation with wildly differing vocabularies and frames of reference, but they will quickly assess the extent of their mutual understanding and tailor their speech accordingly.

Madhu Sudan, an adjunct professor of electrical engineering and computer science at MIT and a principal researcher at Microsoft Research New England, wants to bring that type of flexibility to computer communication. In a series of recent papers, he and his colleagues have begun to describe theoretical limits on the degree of imprecision that communicating computers can tolerate, with very real implications for the design of communication protocols.

"Our goal is not to understand how human communication works," Sudan says. "Most of the work is really in trying to abstract, 'What is the kind of problem that human communication tends to solve nicely, [and] designed communication doesn't?'—and let's now see if we can come up with designed communication schemes that do the same thing."

One thing that humans do well is gauging the minimum amount of information they need to convey in order to get a point across. Depending on the circumstances, for instance, one co-worker might ask another, "Who was that guy?"; "Who was that guy in your office?"; "Who was that guy in your office this morning?"; or "Who was that guy in your office this morning with the red tie and glasses?"

Similarly, the first topic Sudan and his colleagues began investigating is compression, or the minimum number of bits that one device would need to send another in order to convey all the information in a data file.