2
$\begingroup$

Recently it occurred to me that one could potentially design an interactive "compression" scheme which seems to allow for arbitrarily high compression ratios, at the sole expense of time. This already sounds pretty cranky, I realize that, but here is a formal description of the protocol which I hope makes sense:

Define a data store as a tuple $(\mathcal{O}, n, \delta)$ with $\mathcal{O} : \mathbb{N} \to \{ 0, 1\}^n$ a random oracle. We say that the data store "contains" the value $x$ at a (real) time $t \geq 0$ if $\mathcal{O}(\lfloor t \delta^{-1} \rfloor) = x$, such that the contents of the data store randomly change every $\delta$ units of time. A data store could be realized in software using the current time in some agreed-upon representation and any cryptographic hash function.

Alice wants to sends a message to Bob encoded as a bit string as part of an interactive protocol (Alice and Bob are both present and active during the transmission). First they both agree on a suitable $\delta$ such that they can both resolve the current time to within $\delta$ units of time. Then, Alice chooses an integer $n \geq 2$, instantiates a data store $(\mathcal{O}, n, \delta)$, and sends these parameters to Bob, and then breaks up the message into $n$-bit blocks. For each block, Alice then monitors the data store until its contents equal the block, at which point Alice sends a single bit "1" to Bob. When Bob receives this signal, he looks up the contents of the data store and retrieves the corresponding $n$-bit block (possibly rewinding as needed to account for any transmission delay, this is feasible as long as the transmission delay is fairly constant and known to within $\delta$ units of time). When the last block is sent, Alice sends the bit "0", Bob computes a checksum of the message and sends it to Alice for verification.

If the message contained $m$ $n$-bit blocks, the total amount of data actually sent (outside of protocol overhead) was $m$ bits, achieving a compression ratio of $1 - 1/n$, and it would take an expected $m \delta 2^{n}$ time to successfully send it (that is, $\delta 2^{n} / n$ time per bit). Also note that since this scheme doesn't actually use any structure in the message, it can be given already compressed data to compound any already attained compression ratios: the two are not mutually exclusive.

Clearly this doesn't allow for amazingly high transmission rates in general. A realistic usecase could be communication with a space probe, where the light-time transmission delay may be accurately computed allowing for a very low $\delta$, say, $\delta = 10 ~ \text{ns}$. Then we can achieve decent compression ratio/transmission rate tradeoffs, e.g. 94% at 3 KB/s ($n = 16$) or 90% at 122 KB/s ($n = 10$).

It gets exponentially more time-consuming to send data as $n$ increases, so 95% compression ratio is probably about the best one can practically achieve in reasonable time in the general case.

Obviously this only works as an interactive protocol, not as an offline protocol. Also, it doesn't really work "as-is" in real life because you can't just send 1 bit on most channels, as each communication entails a nontrivial amount of overhead (TCP/IP packet, etc..) but in principle I don't see why it couldn't work.

So, does anyone know if this kind of "temporal communication" has been studied before, and can point out any fundamental or practical problems or errors I overlooked that might explain why it isn't used?

$\endgroup$
  • $\begingroup$ It's worth noting that while this is terrible for transmission time, you may be able to save on energy, or monetary costs if you get charged by the bit. $\endgroup$ – immibis Jan 14 '18 at 22:46
2
$\begingroup$

There are two flaws in your idea.

First, compression ratio is not the right metric. The right metric for evaluating your scheme is the transmission rate: how long does it take to send a $n$-bit message? The answer is that your scheme fares very poorly under that metric: it takes $\Theta(2^n)$ units of time to send a $n$-bit message. Therefore, your scheme has very poor performance, both theoretically and practically.

Transmission rate is the right metric for a scheme that sends data over a communication channel. Compression ratio would be suitable for a compression scheme of the form $C:\{0,1\}^n \to \{0,1\}^*$, but crucially, this requires that the output of the compression scheme can be expressed in bits. Your protocol doesn't have that property: the output is actually trits.

This leads me to the second flaw in your idea. Your protocol requires a communication channel that has three states (i.e., can convey one of three symbols at any point in time): "1", "0", or "I have nothing to send right now". In other words, you need a communication channel that can send trits (0, 1, or 2), not just bits (0 or 1). But if we had a communication channel like that, we could already achieve higher transmission rate than your scheme. So, you're not comparing to the right baseline.

For these reasons, your scheme does not beat any information-theoretic bound and does not contradict any theoretical barrier. It also probably won't be effective or useful in practice.

$\endgroup$
  • $\begingroup$ That makes sense, so the main problem is that I am misrepresenting the notion of "waiting for a signal", that explains it. However I don't really follow your first point: why should transmission time always be the primary metric? Aren't there situations where the cost of transmitting is very high but the transmission can be done over long periods of time? $\endgroup$ – Thomas Jan 5 '15 at 6:28
  • $\begingroup$ Also, it is obvious that the scheme is absolutely awful for $n$ greater than 20 or so. I am more interested in its versions for small $n$, say, $n \leq 16$, not so much its asymptotics as $n \to \infty$. $\endgroup$ – Thomas Jan 5 '15 at 6:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.