Asserting Priority in a Decentralized Network

For the organization of a movie quizz, I challenged myself to create some buzzers for the participants. The objective was to have two teams compete over trivia questions. In this type of game, using buzzers really helps the referee deciding who gets to answer first (which often decides who gets the point), as in many situations, people try to overstep their oponents. Using a machine also relieves the referee from having to make choices that could offend one team: "hey, it's not my fault!"

When presented the challenge, the deadline was already close. I chose to use some micro:bit I had spare, has they are pretty solid and offer a neat feature: wireless communication via radio. That way, there are no cables to plug and hide when setting up the quizz. And teams can be at any distance from each other without issue. I have little experience with those chips, but they seem rather simple, and you can use Python to write the code, so I feel confident.

Priority Assertion

The main feature to implement was priority assertion. If a chip starts buzzing, the other should mute itself for a period of time. If all chips are connected to a central machine, they just have to ask permission to it before buzzing, and things should go smoothly. The first chip to talk to the machine starts a cooldown. During that cooldown, any chip requesting a buzz gets denied.

But in a decentralized setting, things are a bit more complex. Mainly because of one enemy, transmission time. More than being strictly positive, it also varies randomly depending on a myriad of factors. If a chip broadcasts that it is buzzing, the other might do the same before receiving the first message, resulting in both chips buzzing at the same time. Buzzers were supposed to help particularly in those cases!

Also, my first reaction was that those cases would be very rare, especially in a real application where people should only trigger the buzzer when they have the answer. So I did some testing. If I deliberately try to trigger both chips at the same time, about one of three attempts produces a clash. That seemed a bit too much, even if in reality that rate would be much lower. And hey, it is also an opportunity to reflect on a new problem!

Exploring Options

So, what are the options? This is an open question. I searched briefly for an answer online but all I found was for centralized applications. After some reflexion, here is what I came up with:

• use some form of temporal synchronization between chips,
• use a third chip as an authority,
• or just use randomness.

In the first option, the idea was that, before buzzing, chips would wait a bit to see if the other is also going to buzz. If so, use timestamps to know who pressed the button first. But getting timestamps with micro:bit is not an easy task. All we have access to is the running_time() method, which returns the number of milliseconds since the chip was turned on. So, as chips will never start at the same time, users would have to do some trickery, such as pressing a button on each chip at the same time, to synchronize everything, which adds unecessary steps for casual users. It is cumbersome and not precise, but I kept the idea of waiting a bit to check for the other chip before buzzing.

The second option is not so bad. It simply requires another chip to be plugged in. We could also use that third "master" chip to display who won the priority challenge, helping the referee quickly know who pressed the button first. But this solution is just going back to a centralized setting, so it does not answer my question. Actually, in a case with more than two buzzers, I would use this, but here, let's try something else.

Random Tie Breaker

The idea is simple: if players trigger the chips in a time span short enough to outpace radio waves, humans will not be able to accurately tell who pressed the button first. So, if the chips agree together on a random winner, people won't tell. It will be like "oh, this one triggered a little bit earlier". So all we have to do, is coordinate chips for taking a decision when a clash occurs.

To allow for detecting clashes, a chip needs to wait between the button press and the acutal buzz, to make sure its companion is muted. So, here is the plan:

1. First, chips are in READY mode. Whenever a button is pressed, the corresponding chip broadcasts a TRIGGER message, and goes to the ARMED mode.
2. When the other chip receives that TRIGGER message, it mutes itself and sends back a CONCEDE message. It then starts a cooldown and goes into IDLE mode.
3. When the first chip receive the CONCEDE message, it knows that the other is muted for a while. So we can go lights on, music on, into FIRED mode.
4. After some delay, both chips go back into READY mode.

So this is how things go when it's all fine. But, what might happen, is that both chips enter ARMED mode roughly at the same time. So it's not a CONCEDE message they receive from their counterpart, but a TRIGGER one. What to do next? The idea is to use some sort of distributed challenge: a test both chips can perform separately, that yields the same results, from which a decision can be made.

When the user presses the button, the chip generates and stores a random string. When it sends its TRIGGER message, it attaches that string, as a challenge. If a chip in ARMED mode receives a TRIGGER message, it compares its own string with its opponent string. The lower one wins. Then,

• if a chip wins the challenge, it will behave just as if they received a CONCEDE message, and fire,
• if a chip looses the challenge, it gives up and go to IDLE mode.

As long as the two strings are different, the same winner will be picked by both chips, with equal chances. Of course, all chips are considered honest. And even if it is a very rare case, we can make sure generated strings are different by appending to them the unique identifier attached to each micro:bit, with the machine.unique_id() method. In theory, one chip will then have a slight advantage over the other, but I can bet a lot of money it will never be noticed.

Handling Deadlocks

Unfortunately, there are loopholes in the presented protocol. After some testing, it appeared that sometimes, chips would get locked into ARMED mode, sometimes only one, sometimes both. While I'm not sure of why it happens, I believe that sometimes messages can be lost and a chip never gets the answer it was looking for.

To counter that, I made slight modifications:

• When in ARMED mode, the chip continuously sends TRIGGER messages. That way, if the first one did not go through, another will eventually reach the second chip.
• When in IDLE mode, if a chip receives a TRIGGER message (probably from a chip locked into ARMED mode), it sends back a CONCEDE message. This unlocks the armed chip, and changes nothing the idle one that remains in its state (I just reset the cooldown).
• I do the same for a chip in FIRED mode, except the answer is a new TRIGGER message, which will force the other to concede (since the first chip entered FIRED mode, it won the challenge, so we are sure that the other will loose). I could also use a new message like TOOLATE to force other chips to bend the knee.

Now, whatever happens, a chip can always escape from its state, either by pressing a button, waiting for time to pass, or waiting for a message.

Discussion

The final code is available on GitHub: rlv/microbit/buzzer.py.

First, if we ever want to make this more fair, we can use timestamps as challenge strings. This will require precise synchronisation from chips (maybe with an hardware connection during setup), but results will no longer be random.

Second, this way of doing things could get a lot harder if we want to introduce more participants. Like you would have to keep tracks of existing peers, wait for their answer, solve challenges with multiple parties, etc. The solution with one extra master chip would be far easier.

And finally, how on earth isn't there a simpler way of doing this? I feel like I miss something. Problem is that I don't know how to formally express it in a way to find relevant litterature about it. So if you have any idea, please contact me!