Lesson 5

Comparing files over a network

Suppose we want to compare two files over a network at low cost. Two identical copies of a database are stored on two computers. The database is periodically updated—at each step, update requests are sent to both computers. After some number of such changes, you would like to check whether these updates have been applied identically to both copies. Since the copies are stored on different computers, some data must be transmitted from one computer to the other. And since the database may be large, you would like to avoid, if possible, sending the entire database from one computer to the other.

A mathematical model for this problem is the communication complexity model. We will consider only protocols for the string equality problem. Alice has a string \(a \in \{0,1\}^{n}\), and Bob has a string \(b \in \{0,1\}^{n}\). They want to exchange several messages in order to determine whether their strings are equal. The complexity measure of their protocol is the number of bits transmitted. It is assumed that Alice and Bob have unlimited computational power.

Problem. Test your intuition!

A protocol where Alice sends a message to Bob, after which Bob must decide whether their strings are equal, is called one-round. How many bits does Alice need to send to Bob in the worst-case in a deterministic protocol?