Speaker Queue Protocol: Half duplex messaging as a base layer

[michielbdejong]

If we can create a layer that guarantees that probes and traces only ever cross inside a node and never in-flight in-between two nodes, that would help avoid quite a few unnecessary problems around undetected loops and possibly (in simpler node types) even message storms.

One option I came up with is a sort of randomize backoff or Rock-Scissors-Stone game that decides who is allowed to talk:

Version 1: Random backoff

Try to take the lock at any time, if there is a clash, wait for a random time before retrying.

Version 2: Random numbers game

Each player chooses a number between 0 and 99. If the difference between the two numbers is 50 or smaller, the smallest number wins. Otherwise the bigger number wins. If the two numbers are the same, the game is undecided. An improvement on this is to let one player add .5 to their number, so they can never be the same.

Version 3: Water/Hammer vs Fire/Glass.

Equivalent to version 2 with one player playing 0 or 1, and the other playing .5 or 1.5.
One player plays wither Water or Hammer, the other plays either Fire or Glass.
The verbs 'extinguish', 'burn', 'contain', and 'break' all mean 'WIN'.
For the Water/Hammer player, it's a 50/50 choice, and chances of winning depend entirely on what the Fire/Glass player plays:

• Water extinguishes Fire but is contained by Glass
• Hammer smashes Glass but is burnt by Fire
  For the Fire/Glass player, the dilemma is similar:
• Fire burns Hammer but is extinguished by Water
• Glass contains Water but is broken by Hammer.

Version 4: Whackamole

A different way to describe what is essentially a same game of two booleans:
The 'mole', or 'difference' player tries to escape by putting their mole in a different location than the hammer.
The 'hammer', or 'equality' player tries to whack the mole by putting their hammer in the same location as the mole.

[michielbdejong]

Another options is to remove the 'nobody is talking state', then you only need a 'switch' signal.

A B
\
\  S
\/
S
 \
  /
  /
  /
  /

[michielbdejong]

I can use the Pauze messages that I already implemented in the Jackal, so send Pauze(true) before talking and Pauze(false) as immediate response to that.

[michielbdejong]

When node B is paused but has a reason to want to send node A a message, it queues the message but sends a Pauze message to signal they have their hand up. As soon as A finishes its current batch, if B has their hand up, A unpauses B.

[michielbdejong]

The Bilateral Speaker Queue Protocol aims to help two participants speak one at a time.
It is better than naively taking turns, because it does not needlessly keep passing turns when neither of the participants have anything to say. It works as follows.

Setting

• 2 nodes participate in a conversation
• each node may send a message to the other node at any time
• each message that is sent, is eventually received intact by other participant, although there may be delays
• messages from one sender node always arrive in the order in which they were sent
• there is no guarantee that an earlier message from A to B arrives at B before a later message from B to A arrives at A.

Message types

There are three message types:

• information messages
• raise-hand to indicate intention to send information messages
• over-to-you to indicate a change of current speaker

Rules

• node A starts in 'speaker' mode, node B starts in 'listener' mode (state A)
• the speaker may send information messages, the listener may not.
• when node B desires to become speaker, they send node A a 'raise-hand' message (state A+)
• node A may send several more information messages, but will eventually receive the raise-hand message (state A++)
• node A may now send several more information messages, but will eventually send an over-to-you message (state A+++)
• node B will eventually receive the over-to-you message (state B)
• Etc for states B+, B++, B+++ and back to state A.

State transitions	A info	A raise-hand	A over-to-you	B info	B raise-hand	B over-to-you
A	A				A+
A+	A+ / A++
A++	A++		A+++
A+++				B
B		B+		B
B+				B+ / B++
B++				B++		B+++
B+++	A

[michielbdejong]

Implemented this now in abstract class Polite which extends abstract class Node and is the basis for class Butterfly.