Categories

Welcome to the Jungle

Before reading this post, you might want to make sure you have read this one, and this one. Just saying.

The purpose of this post is to describe the algorithm known as Jungle and the problem is solves.

Synchronization

Making WaDeD a little bit more abstract that what it actually is–which, conveniently for me, makes all the electronics disappear ;-)–, you can see it as follows: a single device holds a set of messages. When two devices meet, we want them to synchronize their sets, so that when walking away from one another their internal states are the same. Since the interaction might be short, we want this to be as fast as possible. We also want to reduce the energy costs of the whole interaction as much as possible. The energy cost of using the radio, as much in transmitter mode than in receiver mode, is orders of magnitude higher than the cost of CPU cycles or FRAM access over SPI, so we must critically minimize the number of radio packets transmitted. However, once you have started transmitting, the energy cost of adding an extra byte is not really significant, so as much as energy is regarded the size of the packets is of minor importance (it actually is pretty much important, but for reasons of radio transactions efficiency and packets integrity). Furthermore, since any number of devices can be in the same area, the communication should not isolate devices. Instead they should all talk together, so that exchanged messages do not need to be repeated.

Put in other words, we want to compute the symmetric difference of two sets of messages (that is, the elements that they do not have in common) and then exchange those messages, while minimizing the number of times a device communicates with another.

Data storage

In order to do this, we need to be able to quickly compare the state of the memories of two devices. As mentioned in a previous post, hash trees are really convenient data structures to do integrity checks and compare data, provided they are organised precisely in the same way, regardless of the device, their order of arrival and the other data that the device is holding.

This is a very strong constraint: if the messages are stored differently, the trees might have to make more comparisons (consuming energy), or, even worse, they might never completely synchronize, and be stuck in comparing their hashes forever. Can we find a way to organize data so that the same two message will end up being stored in the same place, regardless of what other data is present and the order they were inserted? It appears we can, using a very common structure, namely open hash tables: each leaf of the tree will point to a chained list. Given the 64-bits identifiant of a single message, we determine in which list it should be inserted. The leaf pointing to a list contains a hash of the concatenation of the IDs of the list. The lists are sorted by ID, so the hashes of their leaves differ if and only if the lists differ.

hashtree

That’s it, here is our structure. Messages are stored in small lists, which form the leaves of a hash tree. It is deterministic in its insertion, and comparison can be fast because of the hash tree structure.

The algorithm

Say two devices meet. We want to design a procedure which, at the end, leave the two devices with the same messages in memory, while making them communicate as few as possible, and we can use the augmented hash trees that we have implemented.

In the following description, we need a bit of terminology. The nodes of the tree are divided in two categories: the leaves, which have no sons, and the internal nodes, which have sons. Among those, the penultimate layer (that is, the internal nodes whose sons are leaves) will deserve special treatment. When we talk about broadcasting an internal node, we mean transmitting an information about its position in the tree, and its hash. When we talk about broadcasting a leaf, we mean transmitting an information about its position, and the IDs of all the elements in the list that corresponds to the leaf.

Here are the rules that drive the behaviour of a WaDeD in its communication:

  1. If nothing has happened over a certain period of time, broadcast your root.
  2. If getting a root, compare it with your own. If the hash match, do nothing, otherwise broadcast all the sons of the root.
  3. If getting a node, compare it with the corresponding nodes in your own tree. If they match, do nothing. Otherwise:
    • If the node is not on the penultimate layer, broadcast its sons.
    • If  it is on the penultimate layer, its sons are leaves. For each son, broadcast the leaf.
  4. If getting a leaf, compare it with the matching list in your own tree. For every ID that you hold and is not in the distant list, broadcast the corresponding message. If no message was broadcasted, broadcast your own corresponding leaf.
  5. If getting a message, check whether a message with this ID already exists in memory. If it does, do nothing, otherwise insert it in memory and update the tree.

This algorithm has good properties: when two devices are in a conversation, they are strictly moving down their respective trees, so there can never be any loop in the conversation. A typical exchange will appear as this:

WaDeD A sends a ROOT
root: 1D5DD10E

WaDeD B sends a ROOT
root: B04424B1

WaDeD A sends a NODE N0
sons: 21E5338F 21E5338F 21E5338F 21E5338F 21E5338F 21E5338F 21E5338F 21E5338F

WaDeD B sends a NODE N3
sons: EEDFA82 EEDFA82 3D7B7AC4 EEDFA82 EEDFA82 EEDFA82 EEDFA82 EEDFA82

WaDeD A sends a NODE N11
sons: 0 0 0 0 0 0 0 0

WaDeD B sends a LIST N144
list size: 1
Element 1: 1804A114 

WaDeD A sends a LIST N144
list size: 0

WaDeD B sends a MESSAGE
I'm a WaDeD!

WaDeD A sends a ROOT
root: B04424B1

WaDeD B sends a ROOT
root: B04424B1

This is an actual dump of two WaDeD synchronizing. You can see that the trees have eight sons. The synchronization process is extremely fast if the trees are similar to begin with, and not remarkably longer than a list comparison if the trees are hugely different.

Welcome to the Jungle

But another strong property of this algorithm is that it is stateless: everything is broadcast to everybody, and any device arriving in the middle of a synchronization can benefit from hearing a message. Potentially this leads to conversations dividing and many, many messages being exchanged–hence the name Jungle–, but the WaDeD always act upon messages it gets in a way that leads to increasing its knowledge of the environment. After a few seconds, the jungle calms down: all devices share the same memory state.

In conclusion, we have an algorithm that is extremely efficient when synchronizing two sets that are close and still very good when the sets differ a lot. It deals well when a lot of devices are communicating at the same time, and, since a given device can enter a conversation at any point, missed packets cannot do more harm than having to start the conversation a few messages before.

I think that’s pretty neat.

Commentaires fermés.