What

imagine you have two devices, a client and a server, connected in a peculiar way:

1. the server cannot send messages to the client without the client asking for them
2. there are two channels, a request on one channel can only be responded to on the same channel
3. the first channel has infinite bandwith and is perfectly reliable, but each message is obscenely expensive.
4. the second channel is free, but can only send messages with a single payload bit, and the message has a 50% chance of being dropped

You've just been tasked with building a layer on top of this so that the server can send messages to the client, what do you do?

[DISCLAIMER: read the errata section before you go out and implement this]

How

Informal

the client sends 1-bit tokens. when the server receives that token, if it has generated new messages since it last sent that token, it responds with the boolean negation of that token.

the client always sends the last token it received. when it receives a token that is different from the one it sent, it retrieves a message from the side channel.

Formal

When the system start up, the devices initialize themselves to the following state: 1. the client sets it's client_token variable to false. 2. the server has an empty message queue 3. the server sets its server_token to false, and new_messages to false.

the client periodically sends its client_token value along the unreliable channel.

when the server receives client_token, it performs the following operation:

if client_token = server_token then
  set new_messages false
end if

it then responds with server_token.

whenever the server generates a new message, it performs the following operation:

if not new_messages then
  set server_token (not server_token)
  set new_messages true
end if

when the client receives server_token, it performs the following operation:

if server_token ≠ client_token then
  pull messages
  set client_token server_token

Why

turns out this absurd hypothetical isn't actually that far off of how TCP+TLS and UDP behave, especially in the context of mobile and embedded devices.

this system also has the nice property that the 1-bit messages don't depend on the side-channel messages, useful if there are actually multiple clients, and perhaps multiple secure servers the client wants to be able to receive messages from, and the presence of new messages is multiplexed through a single unsecured server.

Errata 2024-10-25: one bit isn't enough, but two is

as shown here, using a single bit means the server can't tell the difference between a client sending the previous token and the next token.

however, if you replace the 1-bit bools with 2-bit unsigned integers, and replace the negation with a wrapping increment, the protocol works as intended.

additionally, i should have added a timing requirement to the infallible channel, otherwise long polling is a simpler and equally valid solution to the posed problem.

---

#networking #programming