Categories

Drops N’ Roses : synchronization protocol

Hey !

Be prepared for the longest post ever…
Today, I would like to explain to you our synchronization protocol. As I said yersterday, for some applications such as KTA (speleology application), we would like to be able to both :
– keep some messages in a specific drop, for example for direction indications.
– spread some messages in our drop-network. It would allow anyone to access these messages everywhere. It would not have been possible without spreadable messages, unless the user goes to that specific drop.

But for having such spreadable messages, we need a synchronization protocol.

When we will have it, we would be able to synchronize a smartphone and a drop, and then, if the smartphone meets another drop or another smartphone, they would synchronize themselves, and so… one by one, every network drops would have the same messages.

 

  • Use Case

In order to explain how we will proceed, I am going to take an example and develop it during all my speech.One of the aims of KTA application is to avoid people to get lost in caves, and to make research easier if someone really get lost.
To do that, we want to store (and spread step by step in all our drop-network) for each user a message, which contains his pseudonym and a list of his last locations (the id of the last drops he met) and a timestamp for each location. Knowing that the size of a message is limited, we would be able to store around 50-60 locations for each user.

  • Problems

This use case raises some problems :
– to be able to spread a message, it needs a unique id in all our network.
– if we want to edit a message, for example to add a pair (position and timestamp), we will have to distinguish different versions of the same message and identify the newest one.
– to avoid that a user A erases user B ‘s messages, or even worst, changes the content of the message with pair of location and timestamp, and replace them with others, we need to protect these informations. the only user that could edit his message should be himself, but other users should be able to spread his messages as well.
– because our memory is quite limited (32Mb is quite big, but… ), we want to forbid someone to flood the memory. We want to allow only one message for the box “location” per person.
– we want also to manage the term date of a message, and to stop its spreading when it is too old. (We want to save some battery !)

  • Our tools

What we are going to use are :
– a web server, with a data base which will contains a limited number N of users. It will also store their public key (RSA), and their pseudonym. This server would be accessible thanks to our mobile-application, out of the caves. Before to go in catacombs, people would have to register on this server if they want to use our system which stores their last locations.
– on our drop, we create different boxes. For this use case, there are two boxes (n°1 and n°2) whose size is N messages, and another box (n°0). Box n°2 contains location messages for each user, certified by each user (with their private key (RSA), corresponding to the public key they have on the server). Box n°1 contains  a set of messages. Each message is certified by the server. Each message contains a server version number, the pseudonym of one user, his rights (I will explain what it is for later) and his public key. These keys will serve to check the certificate of messages in box n°2. Box n°0 contains the public key of the server, to check the certificate of the keys in box n°1.
The advantage of using certified messages is that nobody (except the owner of the message) can change its content, but everybody can store the message, and spread it.

– a very simple synchronization protocol : one for the keys synchronization and another for location messages synchronization.
But before I can explain these protocols, let me explain how the server and its data base works.

  • Server and data base

Each line of this table represents data for a user in the data base : the first item is the server version, the second is the user’s pseudonym, the third his rights, and the last his public key. All this data are certified by the server.

Server data base

1 – User A – Rights – public key

2 – User B – Rights – public key

3 – User C – Rights – public key

50 – User D – Rights – public key

So, imagine N = 50. You can store only 50 users in your data base. And now, it is full. If another user wants to use our system, he can’t. Except if for exemple, user A don’t want to be in the database anymore. He is deleted, and so, another user can register.

Server data base

51 – User E – Rights – public key

2 – User B – Rights – public key

3 – User C – Rights – public key

50 – User D – Rights – public key

The version number is incremented, so it is now 51.

  • Keys synchronization

We want this database to be stored into our box n°1.
Please, consider that each drop has already the public key of the server stored into the box n°0.
Consider that someone (user C) downloads KTA application, and registers as “user C” in our website, and that he is the third person to subscribe. Consider that the drop he would meet has only the first line (corresponding to user A) of the data base stored as a message in its box n°1. The drop will advertise “KTA” and “1”. Thanks to this advertising, the smartphone of user C would know that the drop is not up-to-date. So the smartphone would connect and exchange step by step the (version + pseudonym + rights + user’s public key), all certified by the server. It means that, if the smartphone tries to send something that is not certified by the server, the drop would refuse to store it. In our case, if the smartphone send at first (3 – User C – Rights – public key) certified by the server, the drop would also refuse to store it, because the drop wants the second version, and not the third.

That is because we want to simplify the behaviour of the drop, and make it a bit stupid in order to avoid calculations and save energy. This behaviour is also good, because even if a smartphone has to send 40 versions and get disconnected before it has transmitted all 40 versions, the drop would be on a steady state, and would advertise the last version it has stored. So if another smartphone came, it can get the versions it has not yet without any calcutation required.

But what if now, we take the example of a 51th version again. And the drop is synchronized with the 50th version. If a smartphone with the 51th version meets the drop, it would synchronize : the drop would delete the first version, and replace it with the 51th version.

What if it was not the first version which was replace but the third, because user C want to give up KTA. If someone (user F) registers, the database would change the first version (1 – User A – Rights – public key) into fifty first version (51 – User A -Rights – public key). Same for the second version. And then, for the third, it would create (53 – User F – Rights – public key).
Proceeding like this assures us that we would keep a steady database and synchronization behaviour with the drop.

  • Location messages synchronization

As I explained ahead, the drop would advertise the server version number, so keys would be synchronized.
So now, we would like to synchronize messages which contains the last (locations + timestamps) of this user. These messages are certified, to assure the fact that it is its owner who posts it.

On connection, the drop will send a list of pair with : user ID (for our example, it would be between 1 and 50) and the last timestamp of this user. The last timestamp would be known because it would be the first data of each user message.


The smartphone compares what it receives with the messages it has. It determines which messages it should give to the drop and would message it should ask from the drop.

After these exchanges, the two devices are synchronized !

  • Conclusion

This is the principle of our synchronization protocol.
All smartphones would use this principle to synchronize themselves with drops and other smartphones.
And with this way of doing, we also can send (when someone goes out the caves) these data to the server. Thanks to that, without moving, an administrater could monitor people movements and if someone disappear, he can directly go to the last location where this person has been seen.

Next time, I will complete this protocol with the management of expired messages (too old to be spread in the network).I hope I have been clear. It was quite complicate to explain !
And… congrat’s if you read all this post !

Code must go on

On and on, does anybody know what we are coding for?

Hello World!

In my last post, I described the toughness and the cruelty of the arguments which cheered our last week up. Until Wednesday, the fight kept on, and then we finally managed to start coding again. What a relief!

So on Wednesday we dispatched the work like this: Adele will work on the lowest level by writing the code to communicate with the Flash, Lauriane will be in charge of the DropFS code, and I will personally take care of the BLE layer and the different services. I started to write the code for parsing the Message commands (I will publish an explanation of the architecture very soon).

On Friday, we had our presentation which was appreciated. However we had some remarks about our pricing, so we need to think a bit more about this subject before our final presentation. Then, we had one more big discussion about the DropFS organization, and especially how to handle the synchronization between the drops and the phones in our KTA app. Now we have a very interesting and strong system, with a lot of good properties. I know Adele is preparing some schematics to explain all that, so stay tuned!

This week end, I had no time to work on the project, but tomorrow I will be back again, because code must go on!

May the force be with you!