Blog

Asserting Priority in a Decentralized Network

July 14, 2022

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](https://microbit.org) 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](https://python.microbit.org/v/beta) 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.
Schema of the presented protocol
Chip State Automaton
# 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](https://github.com/ychalier-rlv/microbit/blob/main/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!