https://paper.wf/binarycat/a-protocol-for-reliable-notifications-over-a-1-bit-fallible-connection

binarycat

Software I Wrote and Use

a protocol for reliable notifications over a 1 bit fallible
connection.

October 4, 2024

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?

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.

---------------------------------------------------------------------

#networking #programming

---------------------------------------------------------------------

published with writefreely