Quentin Bramas

Quentin Bramas

The Tangle is the data structure used to store transactions in the IOTA cryptocurrency. In the Tangle, each block has two parents. As a result, the blocks do not form a chain, but a directed acyclic graph. In traditional Blockchain, a new block is appended to the heaviest chain in case of fork. In the Tangle, the parent selection is done by the Tip Selection Algorithm (TSA). In this paper, we make some important observations about the security of existing TSAs. We then propose a new TSA that has low complexity and is more secure than previous TSAs.

François Bonnet, Quentin Bramas, Xavier Défago

In public distributed ledger technologies (DLTs), such as Blockchains, nodes can join and leave the network at any time. A major challenge occurs when a new node joining the network wants to retrieve the current state of the ledger. Indeed, that node may receive conflicting information from honest and Byzantine nodes, making it difficult to identify the current state. In this paper, we are interested in protocols that are stateless, i.e., a new joining node should be able to retrieve the current state of the ledger just using a fixed amount of data that characterizes the ledger (such as the genesis block in Bitcoin). We define three variants of stateless DLTs: weak, strong, and probabilistic. Then, we analyze this property for DLTs using different types of consensus.

Jean-Philippe Abegg, Quentin Bramas, Thomas Noel

This paper we define a new Puzzle called Proof-of-Interaction and we show how it can replace, in the Bitcoin protocol, the Proof-of-Work algorithm.

Quentin Bramas, Stephane Devismes, Pascal Lafourcade

We deal with a set of autonomous robots moving on an infinite grid. Those robots are opaque, have limited visibility capabilities, and run using synchronous Look-Compute-Move cycles. They all agree on a common chirality, but have no global compass. Finally, they may use lights of different colors, but except from that, robots have neither persistent memories, nor communication mean. We consider the infinite grid exploration (IGE) problem. For this problem we give two impossibility results and three algorithms, including one which is optimal in terms of number of robots. In more detail, we first show that two robots are not sufficient in our settings to solve the problem, even when robots have a common coordinate system. We then show that if the robots' coordinate systems are not self-consistent, three or four robots are not sufficient to solve the problem. Finally, we present three algorithms that solve the IGE problem in various settings. The first algorithm uses six robots with constant colors and a visibility range of one. The second one uses the minimum number of robots, i.e., five, as well as five modifiable colors, still under visibility one. The last algorithm requires seven oblivious anonymous robots, yet assuming visibility two. Notice that the two last algorithms also satisfy achieve exclusiveness.

Quentin Bramas, Sébastien Tixeuil

We propose a new probabilistic pattern formation algorithm for oblivious mobile robots that operates inthe ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinatesystems of robots (the robots do not share a common "North" nor a common "Right"), yet it preserves theability from any initial configuration that contains at least 5 robots to form any general pattern (and not justpatterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in thesame model) that robots do not pause while moving (so, our robots really are fully asynchronous), and theamount of randomness is kept low -- a single random bit per robot per Look-Compute-Move cycle is used.Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministicpattern formation one. As the deterministic phase does not use chirality, it may be of independentinterest in the deterministic context. A noteworthy feature of our algorithm is the ability to form patternswith multiplicity points (except the gathering case due to impossibility results), a new feature in the contextof pattern formation that we believe is an important asset of our approach.

Quentin Bramas, Sébastien Tixeuil

We consider the problem of scattering $n$ robots in a two dimensional continuous space. As this problem is impossible to solve in a deterministic manner, all solutions must be probabilistic. We investigate the amount of randomness (that is, the number of random bits used by the robots) that is required to achieve scattering. We first prove that $n \log n$ random bits are necessary to scatter $n$ robots in any setting. Also, we give a sufficient condition for a scattering algorithm to be random bit optimal. As it turns out that previous solutions for scattering satisfy our condition, they are hence proved random bit optimal for the scattering problem. Then, we investigate the time complexity of scattering when strong multiplicity detection is not available. We prove that such algorithms cannot converge in constant time in the general case and in $o(\log \log n)$ rounds for random bits optimal scattering algorithms. However, we present a family of scattering algorithms that converge as fast as needed without using multiplicity detection. Also, we put forward a specific protocol of this family that is random bit optimal ($n \log n$ random bits are used) and time optimal ($\log \log n$ rounds are used). This improves the time complexity of previous results in the same setting by a $\log n$ factor. Aside from characterizing the random bit complexity of mobile robot scattering, our study also closes its time complexity gap with and without strong multiplicity detection (that is, $O(1)$ time complexity is only achievable when strong multiplicity detection is available, and it is possible to approach it as needed otherwise).