Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Antoine Guellier
email: antoine.guellier@irisa.fr

Romaric Ludinard
email: romaric.ludinard@imt-atlantique.fr

Bruno Sericola
email: bruno.sericola@inria.fr

Sycomore : a Permissionless Distributed Ledger that self-adapts to Transactions Demand

Keywords: Emmanuelle Anceaume, Antoine Guellier, Romaric Ludinard, Bruno

published or not. The documents may come

I. INTRODUCTION

The goal of decentralized cryptocurrency systems is to offer a medium of exchange secured by cryptography, without the need of a centralized banking authority. An increasing number of distributed cryptocurrencies systems are emerging, and among them Bitcoin, which is often designated as the pioneer of this kind of systems. Bitcoin circumvents the absence of a global trusted third-party by relying on a blockchain, an append-only data-structure, publicly readable and writable, in which all the valid transactions ever issued in the system are progressively appended through the creation of cryptographically linked blocks. Construction of the blockchain is distributed among the nodes of the system (several thousand of nodes), and is secure even if malicious nodes own almost the majority of the computational power of the system. This high resilience relies on the smart orchestration of cryptography primitives, distributed algorithms, and incentive mechanisms.

From a chain of blocks to a balanced directed acyclic graph of blocks. In a chain of blocks, each block references an earlier block by inserting a cryptographic link to this earlier block in its header. This forms a tree of blocks, rooted at the genesis block, in which a branch is a path from a leaf block to the root of the tree. Each branch, taken in isolation, represents a consistent history of the crypto-currency system, that is, does not internally contain any conflicting transactions -doublespending transactions. On the other hand, any two branches of the tree do not need to be consistent with each other. The reason is that, at any time, each node of the system selects a unique branch to represent the history of the crypto-systemthis branch being the longest one of the tree, or equivalently the one that required the most important quantity of work.

Garay and Kiayias [START_REF] Garay | The Bitcoin Backbone Protocol: Analysis and Applications[END_REF] have characterized Bitcoin blockchain via its quality and its common prefix properties. Specifically, they have shown that, by keeping the creation rate of blocks very low with respect to their propagation time in the network (i) if the adversary controls no more than 1/3 of the network hashing power then it provably controls less than a majority of the blocks in the blockchain and, (ii) if the adversary controls no more than 1/2 of the network hashing power then the blockchains maintained by any two honest nodes possess a large common prefix (up to the last k appended blocks), and the probability that they are not mutual prefix of each other decays exponentially in k. Unfortunately, this compels Bitcoin's blockchain to a low transaction confirmation throughput: no more than 7 transactions can be permanently confirmed per second in average, which is by too far very low.

A recent evolution in the structure of blockchains is emerging to deal with the performance issue aforementioned. Eyal et al. [START_REF] Eyal | Bitcoin-NG: A scalable blockchain protocol[END_REF] propose with BITCOIN-NG an off-chain mechanism: blocks refer to a leader in charge of validating transactions batched in micro-blocks out of the chain. LIGHTNING [START_REF] Poon | The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments[END_REF] follows the same principle by publishing results of a set of transactions among two parties. HASHGRAPH [START_REF] Baird | The SWIRLDS Hashgraph Consensus Algorithm: Fair, Fast, Byzantine Fault Tolerance[END_REF], BYTEBALL [START_REF] Churyumov | ByteBall : A Decentralized System for Storage and Transfer of Value[END_REF], and IOTA [START_REF] Popov | The Tangle[END_REF] leverage the presence of well known institutions to get rid of blocks, GHOST [START_REF] Sompolinsky | Accelerating Bitcoin's Transaction Processing[END_REF] and SPECTRE [START_REF] Sompolinsky | SPECTRE: A fast and scalable cryptocurrency protocol[END_REF] protocols family modifies the blockchain data structure from linkedlist of blocks to a directed graph of blocks. In particular, SPECTRE [START_REF] Sompolinsky | SPECTRE: A fast and scalable cryptocurrency protocol[END_REF] organises blocks in a directed (but not acyclic) graph of blocks. Blocks are built so that they acknowledge the state of the directed graph at the time blocks were created which decreases the opportunity for powerful attackers to create blocks in advance. The number of created blocks is increased with respect to classic blockchain-based systems, since all the concurrently created blocks belong to the directed graph. Unfortunately the absence of mechanisms to prevent the presence of conflictual records (i.e., blocks with conflicting transactions) and the cycles in the directed graph require that participants execute a complex algorithm to extract from the graph the set of accepted (i.e., valid) transactions [START_REF] Sompolinsky | SPECTRE: A fast and scalable cryptocurrency protocol[END_REF].

SYC-DAG: A balanced directed acyclic graph of blocks.

The ledger we propose is not a chain of blocks, or a set of transactions extracted from a tree of chains-as achieved in existing solutions, e.g., [START_REF] Decker | Bitcoin Meets Strong Consistency[END_REF], [START_REF] Eyal | Bitcoin-NG: A scalable blockchain protocol[END_REF], [START_REF] Gilad | Algorand: Scaling byzantine agreements for cryptocurrencies[END_REF], [START_REF] Kokoris-Kogias | Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing[END_REF], [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF], [START_REF] Sompolinsky | SPECTRE: A fast and scalable cryptocurrency protocol[END_REF], [START_REF] Sompolinsky | Accelerating Bitcoin's Transaction Processing[END_REF] -but a dedicated balanced directed acyclic graph of blocks, that we call in the following a SYC-DAG. Construction of the SYC-DAG ledger is achieved by the Sycomore protocol, a new distributed protocol run by all the nodes of the system. The Sycomore protocol, that we denote in the following by π syc , resembles in some aspects to Nakamoto's one, denoted by π nak . Briefly, π syc is a distributed protocol allowing each participating node to reach an agreement on a SYC-DAG. Similarly to π nak , at the core of π syc are two effective and simple ingredients: a hashcash proof-of-work (PoW) mechanism to synchronize the construction of blocks and to incentive nodes to correctly behave and a block selection rule to handle block concurrency. On the other hand, the unique features of π syc are the following ones.

1) The structure of the SYC-DAG self-adapts to fluctuations of transactions demand: chains of blocks naturally split into multiple ones to cope with burst of pending transactions, while they merge back together to adapt to a drop of activity; 2) The probability of forks decreases with the increasing number of leaf blocks. Thus the rate at which blocks are mined can be drastically augmented (e.g., one block every 20 seconds) without incurring more forks than in Bitcoin; 3) The frequency at which blocks are mined self-adapts to the number of leaf-blocks in the SYC-DAG; 4) Miners cannot predict the branch in the SYC-DAG to which their blocks will be appended. This prevents malicious miners from devoting their computational work on the growing of specific branches of the SYC-DAG. 5) Transactions are dynamically and evenly partitioned over the SYC-DAG, i.e., there is no transaction that belongs to two different blocks. This makes effective the parallelism brought by the SYC-DAG, which allows us to increase the number of confirmed transactions per second. Altogether, these properties allow us to build a secure, immutable and efficient distributed ledger whose structure selfadapts to transactions demand.

The remaining of the paper is orchestrated as follows. Section II presents the model of the system. Section III introduces the SYC-DAG data structure and describes how π syc builds the SYC-DAG in a permissionless and distributed system. Properties met by π syc are stated in Section IV. Finally Section V concludes.

II. MODEL OF THE SYSTEM

We suppose a permissionless system, that is a system populated by a large, finite yet unbounded set of nodes and whose composition may change over time, which participate to the construction of the distributed ledger. The communication delays between any two nodes, the time to execute a local computation step, and the drift of local clocks are assumed to be upper-bounded, however these upper-bounds are unknown to nodes. These temporal assumptions fit the semi-synchrony model [START_REF] Dwork | Consensus in the Presence of Partial Synchrony[END_REF]. To fit the permissionless model, we assume the computational threshold adversary model, which describes the power of the adversary in terms of computational resources it controls [START_REF] Garay | The Bitcoin Backbone Protocol: Analysis and Applications[END_REF]. Note that in the more classical distributed computing literature, the threshold adversary model describes the power of the adversary in terms of the number of nodes it manipulates. Finally, as we are focusing on a financial cryptosystem, we cannot just consider that nodes are either obedient (i.e., they follow the prescribed algorithm) or malicious. We suppose that most of the nodes are rational, that is, strategically behave to increase their own utility function without violating the prescribed protocols. For example, a rational miner may in priority insert in its block all the current transactions that provide the maximal fees while an obedient one will insert transactions irrespective of the gain they procure. Since rational nodes do not violate the protocol specification, in the following we consider as correct both obedient and rational nodes. We assume that nodes have access to basic and safe cryptographic functions, including a cryptographic hash function h -modeled as a random oracle -and an asymmetric signature scheme -that allows a node r to generate public and secret key pairs (p r , s r ), to compute signatures σ r,h(d) on messages d, and to verify the authenticity of a signature. By these properties, each object o of the system -i.e., transaction and block -is assumed to be uniquely identified. In practice, this is achieved by computing o's cryptographic digest h(o). We assume that correct nodes use their cryptographic keys correctly, i.e. they do not disclose, share or drop their secret keys. Finally, we do not suppose the existence of any trusted public key infrastructure (PKI) to establish nodes identities.

III. THE SYCOMORE PROTOCOL

The objective of the Sycomore protocol π syc is to allow each node u of the system to locally maintain its own local view L u of the ledger, so that at any time u can extract from L u a SYC-DAG (defined in Section III-A) denoted by L u such that for any two nodes u and v either L u L v or L v L u .

We assume a "Bitcoin like crypto-system". That is, similarly to π nak , users create transactions to buy goods with coins. A transaction T is uniquely identified by the hash of its content. Its content is made of two sets, the input set denoted by I and the output one denoted by O. Set I contains a set of references to UTXOs (Unspent Transaction Outputs), credited by previous transactions, together with the proof that the creator of T is allowed to redeem each of those UTXOs. The output set O contains a set of "accounts" (or addresses in the Bitcoin terminology), together with the amount of coins to be credited and the challenges that will allow their owners to redeem these coins. Once created, users submit their transactions to the peerto-peer network. Each node of the network should check the validity of each received transaction prior to propagating it to its neighborhood. Informally, a transaction T = (I, O) is locally valid at node p if p has received all the transactions that have credited all the inputs in I and has never received transactions already using any of those inputs. If there exists some transaction T = (I , O ) and some input i such that i belongs to both I and I , then input i is said to be in a double-spending situation. Transaction T = (I, O) is conflict-free if none of the inputs of T is involved in a doublespending situation and all of the transactions that credited T 's inputs are conflict-free. By construction, the induction is finite because Bitcoin creates money only through coinbase transactions, which are by definition conflict-free [START_REF] Anceaume | Safety Analysis of Bitcoin Improvement Proposals[END_REF]. Similarly to π nak algorithm, blocks are created by successful miners, a subset of the nodes involved in the proof-of-work competition. The incentive to participate to this competition is provided by a reward given to each successful miner. This reward is made of a fixed amount of coins, and a fee associated to each transaction contained in the newly created block. This reward is inserted in the output of a particular transaction, called the coinbase transaction.

To fully take advantage of the SYC-DAG data structure, blocks content is slightly different from the way blocks are built in π nak . Briefly, blocks header contain a commitment for each leaf block of the SYC-DAG (in Bitcoin, the commitment is reduced to a single leaf block), and the choice of the set of transactions embedded in the blocks takes advantage of the presence of several parallel chains in the SYC-DAG. Prior to providing a detailed description of the set of information contained in a block, and how blocks are locally inserted in the local view of the ledger, we first introduce the notion of SYC-DAG.

A. A Sycomore Directed Acyclic Graph (SYC-DAG)

Let us consider graph G = (V, E) defined by a set of vertices V and a set of edges E. Vertices are blocks of transactions and edges represent a predecessor relationship. More precisely and similarly to Bitcoin, a block b j ∈ V "points" to a previous existing block b i ∈ V , that is, edges point back in time. We have (b j , b i ) ∈ E, nevertheless we say that b i is the predecessor of b j and thus b j is the successor of b i . Given two blocks b i and b j ∈ V , we say that b i is reachable from b j if there exists a path in G from b j to b i . We denote b

j b i . By convention, b i is always reachable from itself, i.e., b i b i . A leaf block refers to a block b i ∈ V with no children (i.e., block b i is such that {b j ∈ V | b j b i } = {b i }). Conversely, a genesis block is a block b i ∈ V which is reachable from all the blocks in G, (i.e., we have {b j ∈ V | b j b i } = V ).
In the following, a genesis block is denoted by b 0 .

We define

G = (V , E ) as a prefix of G = (V, E), denoted by G G, if V ⊆ V and E ⊆ E and for any edge (b j , b i ) ∈ E, we have b j ∈ V ⇒ [b i ∈ V ∧ (b j , b i ) ∈ E ]. Note that b 0 belongs to all the prefixes of G.
The notion of chain is central to our construction.

Definition 1 (Chain). A chain C = (b 1 b 2 . . . b c ), with c ≥ 2,
in G is a sequence of blocks starting at block b 1 and ending at block b c such that

• each block b i , with 2 ≤ i ≤ c in the sequence points to a unique block and this block belongs to the sequence and, • each block b i , with 1 ≤ i ≤ c -1 in the sequence is pointed by a unique block and this block belongs to the sequence, and

• the first block b 1 does not point to any block of the sequence and the last block b c is not pointed by any block in the sequence.

The length of a chain is the number of blocks of this chain. Each block in G is assigned a binary string called label. The length of a label is the number of bits of , and is denoted by | |. A genesis block b 0 is labelled with the empty binary string ε. All the blocks of a chain have the label of the first block of the chain they belong to. Thus, all the blocks of the chain starting with the genesis block are labelled with the empty string ε. Henceforth, a block will refer to both the block and its label. We use the following notations in the remaining of the paper: C denotes a chain C whose label is , b denotes a block whose label is , and b i indicates that block b is the i-th block, i ≥ 1, of a chain labelled with . Finally, the binary string of label of length m is noted 0 1 . . . m-1 , and we denote by k , 0 ≤ k < m, the prefix of of length k, i.e., the k first bits of .

The load of a block is the ratio between its number of bytes and its maximal load (for instance, 1 MB in Bitcoin prior to the date of SegWit activation). The load of a block is returned by function LOAD(). We introduce the following three system parameters: integer c min > 0, and thresholds 0 < γ < Γ < 1 under and above which a block is considered respectively under and upper loaded.

Definition 2 (Splittable and Mergeable Block

). Let C = (b 1 b 2 . . . b c ) be a chain with c ≥ c min , then • b c is called a splittable block if 1 c min cmin j=1 LOAD(b c-cmin+j ) > Γ. • b c is called a mergeable block if 1 c min cmin j=1 LOAD(b c-cmin+j ) < γ.
A block which is neither splittable nor mergeable is called a regular block.

We will rely on a distance function D that will allow us to uniquely characterize the closest label to a given bit string. This is obtained by computing the numerical value of the "exclusive or" (XOR) of bit strings. To prevent two bit strings to be at the same distance from a given one, bit strings are suffixed with as many bits "0" as needed to equalize their size to the maximal number s of bits of the longest bit string. Suffixing a bit string with one "0" is denoted by .0.

n ), n ≥ 1, and chain C

(2) = (b

(2) 1 . . . b (2) m ), m ≥ 1 are split chains if b (1)
1 and b

(2) 1 point back to the same splittable block b . We have (1) = .0 and (2) = .1.

Note that by definition of the labels, all the blocks of C

(1)

(resp. C (2)
) have labels (1) (resp. (2) ).

Definition 5 (Merged Chain). Chain C = (b 1 . . . b j ), j ≥ 1, is a merged chain if b 1 points back to two sibling mergeable blocks b (1) and b (2) (i.e., b (1) and b (2) are two mergeable blocks whose respective chains are issued from the same splittable block) such that (1)

= 0 . . . | (1) |-1 , (1) = (2)
and we have = 0 . . .

| (1) |-2 .
By abuse of language, we say that chain C is the predecessor of chain C if the first block of C points back to the last block of C . This is denoted by C = pred(C ).

Based on the above definitions, we are ready to define what is a SYC-DAG.

Definition 6 (SYC-DAG ).

A graph G = (V, E) is a SYC-DAG if G has a unique genesis block b 0 and there exists a partition P = {C1 , . . . , C n } of V such that ∀i s.t. 1 ≤ i ≤ n, C i is a chain with label i (note that several chains in P may be assigned the same label) and the following three properties hold:

∀C i ∈ P, ∀k s.t. 0 ≤ k < | i |, C k i ∈ P (1) ∀C i a merged chain ∈ P, C i.0 , C i.1 ∈ P (2) ∀C i , C j ∈ P, i = j ⇒ [pred(C i ) = pred(C j )] (3)
Note that if G is a SYC-DAG then by Property 1, C ε ∈ P. Figure 1 shows a possible ledger built by π syc , and we will use it to illustrate all introduced notions. Vertices of graph k (i.e., last blocks of respectively C 00 4 ∈ P and C 01 5 ∈ P). Remark that most of the blockchain-like systems build a chain of blocks, which is a restriction of a SYC-DAG to a unique chain.

G = (V, E) are partitionned into P = {C ε 1 , C 0 2 , C 1 3 , C 00 4 , C 01 5 , C 10

B. Construction of a block

We are now ready to describe how blocks are constructed to allow each node of the system to locally maintain its local view of the ledger. As previously said, blocks contain additional information with respect to Bitcoin's blocks so that (i) malicious miners cannot devote their computational power to the growing of a specific chain of the SYC-DAG (Property 1), (ii) transactions are partitioned over the blocks of the SYC-DAG (Property 2), and (iii) the number of leaf blocks self-adapts to transactions demand (Property 3).

Property 1. The predecessor of a block is neither predictable nor choosable.

Let u be any miner, b be the block miner u is currently creating, L u be u's local view of ledger, and b 1 . . . b j be the leaf blocks of L u . The objective of Property 1 is to guarantee that miner u can neither foresee nor chose the chain to which its block will be appended (if it is effectively appended) prior to having irremediably completed the construction of his block's header. The reason is to prevent an adversary from devoting all its computational power to the growing of a specific chain. The solution we propose to achieve this goal is (i) to insert in b u 's header the view on the current state of L u (i.e. hashes of the leaf blocks), and (ii) a commitment on the future state of L u , that is a commitment that must be valid whatever the leaf block to which b u will be appended. As detailed below, this commitment is sealed with a proofof-work. Finally, all these pieces of information allows us to derive the predecessor of b u . Specifically, when u creates block b u , it inserts in b u 's header a set H defined as

H = h(b 1 ), 1 , m 1 , . . . , h(b j ), j , m j , (4)
where h(b 1 ) . . . h(b j ) are the hashes of the leaf blocks b 1 . . . b j of L u , and for each b i , 1 ≤ i ≤ j, label i represents the label of the next block to be appended to b i . That is if b i is a regular block, then by construction of the SYC-DAG, i = i . On the other hand, if b i is a splittable block then by Definition 4, only two split chains can succeed to block b i , and thus two tuples h(b i ), i .0, m i.0 and h(b i ), i .1, m i.1 will appear in H. Finally, if b i is a mergeable block and its sibling leaf block is also mergeable, then by Definition 5, only a merged chain can succeed to block b i , and thus two tuples h(b i ), i , m i and h(b i ), i , m i will appear in H, with i the largest common prefix of i and i . Finally, for each label i , the Merkle root m i of the set of locally pending transactions whose identifier is prefixed by i is inserted in H (Property 2 will detail this point). Hence, if j is the number of leaf blocks in L u (at the time miner u created b u ), then the number of tuples in H is equal to j + j 1 if j 1 leaf blocks of L u are splittable. 1 Now miner u derives from H the leaf block that will be the predecessor of b u without being able to favor one leaf block among all the leaf blocks of L u , while guaranteeing this choice to be verifiable by anyone. This is achieved by relying on the proof-of-work mechanism. Specifically, miner u works to find a nonce ν such that h(H||ν) ≤ T , where T is the target of the proof-of-work, and --is the concatenation operator. The difficulty of obtaining a hash that matches the specific pattern T increases exponentially as the number of the most significant bits in T set to "0" increases. Once nonce ν is found, miner u inserts ν in b u 's header, and derives the unique predecessor of his block b u as the leaf block (let us call it b i ) whose successor will carry the closest label i to b = h(H||ν) mod 2 s , i.e.,

i = arg min k s.t. (-, k ,-)∈H D( k , b),
where s is the number of bits of the longest successor's label, and the distance D is computed as defined in Definition 3.

The label u of b u is set to i . Notice that in case i belongs to two tuples in H, then block b u will have as predecessor the two mergeable blocks b i i and b i i . It is very important to see that no specific reference to the predecessor is added in a block header. The reason is that the header is sealed (thanks to the proof-of-work) prior to having derived such an information. As a consequence, when a node receives a block, it checks the block validity, and derives the block predecessor.

In the following we suppose the absence of temporary forks. Their resolution is detailed in Section III-C.

Property 2. For any transaction T ∈ L u ,

• it exists a unique block b ∈ L u such that T ∈ b , and • it exists a unique path starting from a leaf block b to the genesis block that contains b , and both and share a common prefix.

Property 2 is related to the parallel creation of blocks. It guarantees that a transaction belongs to a unique block, and that looking for that block in the ledger only requires to traverse a single and well identified path whose length is in the best case logarithmic in the number of blocks of the ledger. As briefly aforementioned, the solution we propose to implement Property 2 is to partition pending transactions according to the prefix of their identifier so that only transactions that are prefixed by label u are inserted in block b u (see Property 1). Note that the Merkle root of this set of pending transactions exactly matches the Merkle root that appears in tuple b

i i , i , m i of b u 's H set with u = i .
Note that in addition to b u 's transactions, the miner creates the coinbase transaction that awards him for his block creation work. This is the only transaction of b u whose prefix does not necessarily match label u . Property 3. The number of leaf blocks self-adapts to transactions demand.

Property 3 is implemented by having any miner u locally compute the average load of the last c min blocks of each chain of L u to determine the presence of splittable or mergeable leaf blocks. Any splittable block (which is ascribable to a pick of transactions demand, see Definition 2), can only be the predecessor of two split blocks (more precisely of the first blocks of two split chains), each one in charge of its own partition of transactions. Similarly in presence of a drop of transactions demand (see Definition 2), the successor of two sibling mergeable leaf blocks can only be a block in charge of both partitions of transactions. The fact that a block is splittable or two blocks are mergeable, is observable and verifiable by anyone once these blocks are appended to the ledger.

Let us illustrate the construction of block b u based on the local view L u of the ledger at miner u depicted on Figure 1. Miner u progressively computes H by iterating on all the leaf blocks a, b, c and d of L u . We have H = h(a 00 ), 00, m 00 , h(a 01 ), 010, m 010 , h(a 01 ), 011, m 011 , h(a 10 ), 1, m 1 , h(a 11 ), 1, m 1 , where m 00 , . . . , m 1 are the Merkle roots of the four transactions partitions. Notice the presence of the splittable block b and the two mergeable sibling blocks c and d. Then miner u iterates on h(H||ν) until finding a nonce ν such that h(H||ν) ≤ T with T the current traget of Sycomore. Suppose that the last three bits of h(H||ν) are equal to 101 (three is the maximal length of the blocks labels that will be appended to the actual leaf blocks a,. . . ,d), then b u 's predecessor are the mergeable blocks c and d, and b u 's label is equal to 1. Finally, miner u includes in b u 's body pending transactions of the partition 1.

In Bitcoin, the rate at which blocks are found is regulated by the difficulty parameter D. The difficulty is simply the ratio between the maximal target and the current target T . It is easier to speak in terms of difficulty than in terms of the target. The maximal target is (2 16 -1)2 208 or approximately 2 224 . A random hash has a chance of about 2 -32 to be lower than the maximal target. It follows that if the difficulty is D, it takes on average 2 32 D hashes to find a block, and thus assuming the network hashrate is H, then the block creation rate can be approximated as H/(2 32 D). Every H max = 2016 blocks, the difficulty D is adjusted based on the time it took to mine the last 2016 blocks. In Sycomore, the difficulty is adjusted based on both the network hashrate H and on the number c ≥ 1 of chains in L u (which is an indicator of the current transactions demand). Specifically, adjustment occurs every time all the chains of L u have been extended with H max additional blocks with respect to the last time the difficulty has been adjusted, that is, when their height h satisfies h = 0 mod H max .

To cope with the fact that all the chains do not grow at the same rate, and thus do not reach height h at the same instant, once a chain of L u has reached height h, then miner u does not take this chain into account to determine the predecessor of its block b u , i.e., he only considers all the leaf blocks whose height have not reached the re-adjusting point yet. Note that this does not endanger the security of the algorithm as this is verifiable by anyone. By doing so, the gap between the tallest chain and the smallest one rapidly decreases until all the chains reach height h, instant at which the difficulty can be recomputed. A study of this gap is presented in Section IV.

C. Upon receipt of a block

Once created, blocks are propagated in the system, so that each node v of the system updates its local view L v of the ledger L with the new received block assuming that the block is valid. Block b is valid if 1) the proof-of-work of b is correct, and 2) for each block b referenced in set H of b's header, b belongs to the local view L v , and 3) all non-coinbase transactions embedded in b match the label of b and do not redeem an already spent output. If case 2) does not hold (node v may not have received b yet), b's label cannot be computed and thus case 3) cannot be evaluated yet. Thus b is temporarily stored in v's orphan set, and its validity is postponed until case 2) holds. Note that if case 1) or case 3) is violated, block b is invalid and rejected.

The distributed block creation process may lead to forks, that is the presence of two or more blocks with the same label and pointing back to the same predecessor in L v which violates Property 3 of Definition 6. Notice the difference with split blocks. Two split blocks have the same predecessor but each one inherits the label of their predecessor extended respectively with "0" and "1". Split blocks are created as a response to an increase of transactions demand, while forks are due to concurrency. Since the presence of forks gives rise to several concurrent but valid SYC-DAG (see Definition 6), we introduce a rule, Rule 1, that allows any node v to deterministically extract from its local view L v a single valid SYC-DAG, denoted by L v , that respects Property 3 of Definition 6. Note that Figure 1 does not contain any fork, and thus represents a valid SYC-DAG. Note that by definition of F b , this path necessarily ends at b. Surprisingly enough, the fork rule is exactly the same one as in Bitcoin when the SYC-DAG is reduced to a single chain. This makes sense since it amounts to favor the SYC-DAG that has been acknowledged by the largest proportion of miners. Note that the largest confirmation level of the genesis block can be temporarily reached in two concurrent SYC-DAG. By convention, L v is kept as long as it is not superseded.

Similarly to Bitcoin, Rule 1 may give rise to the pruning of a chain of blocks due to the presence of a fork. However, once a block has been inserted deep enough in the SYC-DAG then, by construction of the blocks and by Rule 1, with high probability such a block will remain forever in L v for any node v. The notion of "deep enough" relates to the confirmation level of a block.

Lemma 1 (Deep confirmation level). For any node v maintaining L v , the probability that a block b with confirmation level k is removed from L v decreases exponentially with k.

Proof: Let b ∈ L v . By Rule 1, and by the computation of F b , we can apply the same argument as the one used by Nakamoto [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] and Rosenfeld [START_REF] Rosenfeld | Analysis of hashrate-based double spending[END_REF]) to show that the probability that block b remains in L v increases exponentially with the length of the longest path of F b .

IV. PROPERTIES OF THE SYCOMORE PROTOCOL

This section is devoted to the study of the properties of the Sycomore protocol, and in particular of L v , for any node v. We show that at any time a single coherent history exists, meaning that at any time a unique SYC-DAG is the valid SYC-DAG. This is achieved by first showing that L v is a prefix of L v and that L v is a SYC-DAG. We conjecture that for any two correct nodes u and v, L u L v or L v L u . Then we study the probability of fork, the confirmation level of transactions, and finally the maximal gap between any two chains at the instant at which the difficulty is readjusted. Proof: We first suppose that c = 1. We model the block creation procedure as a Poisson process. An event represents the creation of a block. Let {N (t), t ≥ 0} be a Poisson process with rate λ representing the number of events in the interval (0, t). We then have, for every n ≥ 0, P{N (t) = n} = e -λt (λt) n n! .

For all t > 0, we denote by p(t) the probability that at least two events of this process occur in an interval of length t. We then have

p(t) = P{N (t) ≥ 2} = 1 -P{N (t) = 0} -P{N (t) = 1} = 1 -e -λt (1 + λt).
We now suppose that c > 1. Let b 1 , . . . , b c be the c leaf blocks of L v . An event of type i represents the creation of a block that has b i as predecessor. The events produced by the Poisson process can be of c different types. We suppose that each event produced is of type i with probability p i , for i = 1, . . . , c. The successive choices for the types are supposed to be independent of each other and also independent of the Poisson process. For every i = 1, . . . , c, we denote by {N i (t), t ≥ 0} the number of events of type i produced by the Poisson process. It is well-known that {N i (t), t ≥ 0} is a also Poisson process with rate λp i and that these c Poisson processes are independent. We denote by p i (t) the probability that at least two events of type i occur in the interval (0, t).

We then have, for every i = 1, . . . , c,

p i (t) = P{N i (t) ≥ 2} = 1 -e -λpit (1 + λp i t). If p i = 1/c, we get p i (t) = P{N i (t) ≥ 2} = 1 -e -λt/c (1 + λt/c).
This completes the proof of the lemma. Note that case c = 1 corresponds to the fork probability in Bitcoin. Figure 2 shows the probability of fork when blocks are created every 10 mn in average (i.e. λ 0 = 1/600 in Bitcoin's setup). The interval of time that we consider (i.e. 30 seconds) corresponds to the time it takes for a block to be received by a large proportion of the nodes in the peer-to-peer system [START_REF] Decker | Information propagation in the bitcoin in the bitcoin network[END_REF]. This graph shows that the probability of fork in Bitcoin is small (i.e. equal to p(t) = 0.0012 in the time interval of 30 seconds) which was confirmed by Decker's observations [START_REF] Decker | Information propagation in the bitcoin in the bitcoin network[END_REF], while in Sycomore this probability of fork is even smaller and decreases as a function of the number of leaf blocks c. For instance the probability that in the time interval of 30 seconds a fork occurs is equal to p(30) = 4.9 × 10 -5 when c = 5, p(30) = 1.2 × 10 -5 when c = 10 and p(30) = 3.1 × 10 -6 when c = 20. This clearly means the capability of Sycomore to sustain a higher rate at which blocks are mined without exceeding Bitcoin's probability of fork. This is shown in Figure 3. In this figure, the relationship between c and the rate at which block are mined to guarantee a probability of fork equal to the one of Bitcoin is depicted. For instance, in presence of c = 30 leaf blocks, blocks can be mined every 20 seconds in average while guaranteeing a probability of fork not greater than the one of Bitcoin. This adaptiveness is a remarkable feature of Sycomore, which to the best of our knowledge, is not present in any other ledger design. Finally, we focus on the maximal gap that exists between any two leaf blocks at the time the difficulty must be readjusted, that is when the first leaf block reaches height h = 0 mod H max . We model the update of the ledger as a ball and urn problem where each produced event is of type i with probability p i , for i = 1, . . . , c, with c the number of leaf blocks of the ledger. If the events of type i are placed in an urn numbered i, then N i (t) can be seen as the number of events in urn i at time t. We denote by M (t) and by m(t) respectively the maximun and minimun levels among the c urns at time t. We thus have We would like to evaluate the instants t at which the level of all the c urns is between a and H max . More precisely we want to determine, for every integer a, H max and for every ε ∈ (0, 1), the instants t such that P{M (t) ≤ H max , m(t) ≥ a} ≥ 1 -ε. For all t ≥ 0, H max ≥ 0 and 0 ≤ a ≤ H max , we have when . Indeed, introducing the notation v j (t) = e -λt/c (λt/c) j j! and u r (t) = r j=0 e -λt/c (λt/c) j j! , we have f (t) = u Hmax(t) -u a-1 (t) c and since u r (t) = -λv r (t)/c, then derivative of f is given by f (t) = c u Hmax(t) -u a-1 (t) c-1 -λv Hmax(t) c + λv a-1 (t) c .

M (t) = max
We then have

f (t) = 0 ⇔ v Hmax(t) = v a-1 (t) ⇔ t = c λ H max ! (a -1)! 1 Hmax-a+1
.

Since f (0) = 0 and lim t-→∞ f (t) = 0, if f (t * ) ≥ 1 -ε then there exist two values of t called t 1 and t 2 such that for all t ∈ [t 1 , t 2 ] we gave f (t) ≥ 1 -ε.

Numerical application. To illustrate these results, we fix ε = 0.01 and for different values of H max , we compute the greatest value a * of a such that f (t * ) ≥ 1 -ε. We also give for some values of a and H max the intervals of time [t 1 , t 2 ] in which we have f (t) ≥ 1 -ε. We obtain the results shown in Table I where the time is expressed in minutes.

V. CONCLUSION

In this paper, we have proposed Sycomore, a dedicated balanced directed acyclic graph of blocks. Sycomore aims at addressing performance issues of permissionless ledgers. We show that Sycomore allows us to keep all the remarkable properties of the Bitcoin blockchain in terms of security, immutability, and transparency, while enjoying higher throughput and self-adaptivity to transactions demand. We are currently investigating a formal evaluation of Sycomore behavior while working on implementation to bring this solution to a real world usage.

Definition 3 (

 3 Distance D). Let a = a 0 . . . a d-1 and b = b 0 . . . b d -1 be any two bit strings (note that the bit numbering starts at zero for the most significant bit), and s = max(d, d ). D(a, b) = D(a 0 . . . a d-1 .0 s-d , b 0 . . . b d -1 .0 s-d ) = s-1 i=0 2 s-1-i 1 {ai =bi} , where notation 1 {A} denotes the indicator function which is equal to 1 if the set A is not empty and 0 otherwise. Hence, bit strings that have longer prefix in common are closer to each other. For instance, let = 0001, = 0000, and = 111 be any three bit string labels, then D( , ) = 1, D( , ) = 8 + 4 + 2 + 1 = 15 and D( , ) = 8 + 4 + 2 = 14. Two binary strings at distance 1 are called siblings, e.g. bit strings and are sibling, which is denoted by = . Note that by abuse of notation, two sibling blocks b and b will be denoted by b and b . Definition 4 (Split Chains). Chain C (1) = (b

6 , C 11 7 ,

 67 C 0 8 , C 00 9 , C 01 10 }. For any chain C ∈ P we have ∀k s.t. 0 ≤ k < | |, C k ∈ P. In particular, we have C ε ∈ P. For any chains C i , C j (e.g. C 0 2 and C 0 8 ), we have pred(C i ) = pred(C j ). Finally, for any merged chain C i ∈ P (e.g. C 0 8 ), we have b 1 points back to two sibling mergeable blocks b .0 j and b .1

Fig. 1 .

 1 Fig. 1. A possible ledger built with πsyc

Rule 1 .

 1 [Fork Rule] At any time, keep the SYC-DAG for which the confirmation level of the genesis block is the largest. The confirmation level of some block b in L v is computed by determining the longest path of blocks that commit the presence of b in L v . Specifically let F b rooted at b be the directed acyclic graph that contains all the blocks in L v that commit the presence of b in L v . F b = (V b , E b ) where V b ⊆ V and, for any two blocks (b j , b i ) ∈ V 2 , we have (b j , b i ) ∈ E b if (h(b i ), -, -) belongs to H bj , with H bj the header of block b j as defined in Equation (4). The set V b is defined by V b = {b j ∈ V | b j b} ∪ {b}. Recall that relation refers to the existence of a path from b j to b. The confirmation level of b is equal to the length of the longest path of F b .

Fig. 2 .

 2 Fig.2. Probability of fork as a function of time (seconds). The block creation rate is Bitcoin's one, i.e., λ = 1/600 (one block every 10 mns in average).

Fig. 3 .Lemma 2 .Conjecture 1 .

 321 Fig. 3. Mean inter-block time as a function of the number of leaf blocks c to meet Bitcoin's probability of fork (i.e., p(t) = 0.0012 which is obtained with λ 0 = 1/600)

  i=1,...,c {N i (t)} and m(t) = min i=1,...,c {N i (t)}.

.

  p i = 1/c, P{M (t) ≤ H max , m(t) ≥ a} = c i=1 P{a ≤ N i (t) ≤ H max }We denote by f this function when p i = 1/c. Then we can show that f has a unique maximum at point t = t * given by t * = c λ H max ! (a -1)! 1/(Hmax-a+1)

TABLE I VALUES

 I OF t * , t 1 , t 2 FOR DIFFERENT VALUES OF Hmax AND a * .

	(Hmax, a * )	a	t 1	t *	t 2
	(2016, 1732)	1732	18700	18722	18743
		1500	16225	17516	18811
	(10080, 9431)	9431	97507	97537	97567
		7500	77704	87583	97737
	(20160, 19237)	19237	196911	196967	197023
		15000	153812	175166	153812

Note that as long as a splittable block has not been appended by two split blocks then that splittable block is still considered as a leaf block.


Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Yann Busnel
email: yann.busnel@imt-atlantique.fr

Vasile Cazacu
email: vasile.cazacu@irisa.fr

On the Fly Detection of the Top-k Items in the Distributed Sliding Window Model

This paper presents a new algorithm that detects on the fly the k most frequent items in the sliding window model. This algorithm is distributed among the nodes of the system. It is inspired by a recent and innovative approach, which consists in associating a stochastic value correlated with the item's frequency instead of trying to estimate its number of occurrences. This stochastic value corresponds to the number of consecutive heads in coin flipping until the first tail occurs. The original approach was to retain just the maximum of consecutive heads obtained by an item, since an item that often occurs will have a higher probability of having a high value. While effective for very skewed data distributions, the correlation is not tight enough to robustly distinguish items with comparable frequencies. To address this important issue, we propose to combine the stochastic approach together with a deterministic counting of items. Specifically, in place of keeping the maximum number of consecutive heads obtained by an item, we count the number of times the coin flipping process of an item has exceeded a given threshold. This threshold is defined by combining theoretical results in leader election and coupon collector problems. Results on simulated data show how impressive is the detection of the top-k items in a large range of distributions.

I. INTRODUCTION

The need to analyze in real time large-scale and distributed data streams has recently became tremendous to detect attacks, anomalies or performance issues. In particular the identification of recent heavy-hitters (or hot items) is essential but highly challenging. This problem has been heavily studied during the last decades with both exact and probabilistic solutions [START_REF] Demaine | Frequency Estimation of Internet Packet Streams with Limited Space[END_REF], [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF]. A great survey and empirical comparisons of available and most used techniques were done by Cormode and Hadjieleftheriou [START_REF] Cormode | Methods for finding frequent items in data streams[END_REF]. While simple to state and fundamental for advanced analysis, answering this issue over a time sliding window [START_REF] Wei | Persistent Data Sketching[END_REF], [START_REF] Homem | Finding top-k elements in a time-sliding window[END_REF] and among distributed nodes [START_REF] Papapetrou | Sketching distributed sliding-window data streams[END_REF] is still an active research field. The distributed detection of frequent items over a sliding window presents two extra challenging aspects with respect to the centralized detection of frequent items since the inception of the stream:

• Treat time decaying items as they enter and exit the sliding window; • Produce mergeable local stream summaries in order to obtain a system-wide summary. Very recently, Song, Liu and Ge [START_REF] Song | Top-k Frequent Items and Item Frequency Tracking over Sliding Windows of Any Sizes[END_REF] formalized this problem as the windowed top-k frequent items (WTK) problem and proposed an efficient and very elegant solution, named the floating top-k (FTK) method, to solve WTK. In a nutshell, instead of counting items or estimate their frequency, FTK associates a stochastic value correlated with the item's frequency in order to identify the most frequent ones.

Our contributions. We improve upon their solution by providing a new algorithm called FTK CE . It is based on a deterministic counting of the most over-represented items in the data streams, which are themselves probabilistically identified using a dynamically defined threshold. Performance of our new algorithm are astonishingly good, despite any items order manipulation or distributed execution 1 .

Paper roadmap. The remaining of our paper is organized as follows. Works related to our problem are presented in Section II. Section III provides a specification of the problem addressed in this paper. Section IV is dedicated to our algorithm description, and Section V details the construction of the algorithm's threshold. Performance evaluation is presented in Section VI. Finally, Section VII concludes this paper and presents some future works.

II. RELATED WORKS

A lot of research works have been dedicated to the detection of top-k items in continuous and massive streams since the seminal work of Misra and Gries [START_REF] Misra | Finding repeated elements[END_REF] in 1982. As detailed shortly, lines of work particularly focus on the space and time complexity of the detection algorithms in order to cope with the continuously increasing rates of data generation. Some works also address orthogonal features related to the semantic of the streams by providing the possibility to answer queries on the recent past of a particular stream or on distributed ones [START_REF] Cormode | Methods for finding frequent items in data streams[END_REF]. Research in the detection of top-k items can be classified in two groups: counter-and sketch-based algorithms.

A. Sketch-based techniques

The two most known, versatile and general purpose sketch summaries are COUNTSKETCH (also known as AMS sketch) due to Alon, Matias and Szegedy [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF] and COUNTMIN sketch due to Cormode and Muthukrishnan [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF]. Actually, both techniques are used to extract the number of times (also called the frequency) each item occurs in a stream. Such an estimation is done by relying on the properties of the linear projection (using universal hash functions) of the initial data space onto a smaller space of counters. In order to mitigate inevitable collision of items, several pairwise-independent hash functions are used in parallel. The top-k items are then extracted from the sketch data structure.

B. Counter-based techniques

One of the most famous counter based technique is undeniably the SPACESAVING algorithm by Metwally, Agrawal et El Abbadi [START_REF] Metwally | Efficient Computation of Frequent and Top-k Elements in Data Streams[END_REF]. The underlying idea of SPACESAVING is just to store a limited number of counters. The associated counter is incremented when an already seen item arrives, and all counters are decremented when a new item arrives and all counters are already taken. While initially thought to answer the frequent and the top-k items problems, SPACESAVING can be extended to answer the frequency estimation problem too.

C. Mixed techniques

Recent works have mostly been focused on improving, extending or mixing precedent works as achieved for example in [START_REF] Homem | Finding top-k elements in a time-sliding window[END_REF], [START_REF] Wei | Persistent Data Sketching[END_REF], [START_REF] Papapetrou | Sketching distributed sliding-window data streams[END_REF], [START_REF] Anceaume | Identifying Global Icebergs in Distributed Streams[END_REF], [START_REF] Cafaro | Mining frequent items in the time fading model[END_REF], [START_REF] Tang | Efficient Identification of TOP-K Heavy Hitters over Sliding Windows[END_REF]. A common idea of both [START_REF] Homem | Finding top-k elements in a time-sliding window[END_REF] and [START_REF] Tang | Efficient Identification of TOP-K Heavy Hitters over Sliding Windows[END_REF] to enhance the performance of SPACESAVING consists in filtering out some of the items (i.e., the ones supposed to have low frequencies) before applying SPACESAVING by adding a hashed bitmap counter for [START_REF] Homem | Finding top-k elements in a time-sliding window[END_REF] and two COUNTMIN sketches for [START_REF] Tang | Efficient Identification of TOP-K Heavy Hitters over Sliding Windows[END_REF].

D. Probabilistic counting technique

Almost all of the previous works are based on improvements and/or combinations of counting methods and hashing techniques. Differently, in 2017, Song et al. [START_REF] Song | Top-k Frequent Items and Item Frequency Tracking over Sliding Windows of Any Sizes[END_REF] presented a new type of algorithm to directly identify the top-k most frequent items without counting or estimating their frequencies. The core idea of their proposal is to generate a stochastic value every time an item arrives and just to keep the maximum value obtained by different items. The logic behind this technique is that more often an item occurs, more numerous are its chances to get a higher value. The estimated top-k most frequent items are given by the items with the k highest values. Finally, this innovative approach presents two very interesting properties:

• The algorithm is resilient to the permutation of items within the data stream, and • A distributed sliding window schema can be derived straightforwardly. These points will be discussed in Section IV.

III. PROBLEM STATEMENT

In this section we discuss some important features of the sliding window and distributed version of the top-k most frequent items problem.

A. Terminology

Sliding window. There are mainly two ways to define a sliding window when treating a data stream. A sliding window is either defined by the last n W received items or by the items received during the last W units of time. We adopt the second definition, since it matches a larger range of applications. Specifically, the time domain is partitioned into time units (e.g., seconds, hours, days, etc.), which define the time granularity of the sliding window over the data stream. Indeed, the time unit acts like a micro batch for the windowed top-k most frequent items problem: the top-k most frequent items are extracted at each time unit, after what the top-k most frequent items over the whole past time window is returned. The choice of the time unit is completely arbitrary and has to be defined by the user and depends on the problem at hand. Thresholded counts, heavy hitters, top-k. The thresholded counts problem (e.g., [START_REF] Keralapura | Communicationefficient distributed monitoring of thresholded counts[END_REF]) aims to identify all the items that crossed a previously defined threshold. Since this threshold is independent of the stream length, this can lead to a potentially unbounded number of different items crossing this threshold. On the other hand, heavy-hitters are items whose frequency exceeds a given proportion φ of the stream size (e.g., [START_REF] Ben-Basat | Heavy hitters in streams and sliding windows[END_REF]). There can be at most 1/φ heavy hitters at any time or during one sliding window. The motivation behind the top-k most frequent items problem is to avoid when possible the use of a statically defined threshold, which in highly dynamic and large data streams can produce a very fluctuating number of heavy hitters since φ is likely to be relatively low. In addition, there are many use cases (e.g., social networks hot topics, marketing applications, etc.), where we are only interested in the top-k most frequent items whatever the relative frequency of each item. Section III-B formally defines the top-k most frequent items.

B. System Model

We consider a set of N nodes S 1 , . . . , S N such that each node S i receives a large sequence σ Si of data items. In the following we use the generic term "item" to represent any received element or symbol. We assume that streams σ S1 , . . . , σ S N do not necessarily have the same size, i.e., some of the items present in one stream do not necessarily appear in others or their number of occurrences may differ from one stream to another one. We also suppose that node S i (1 ≤ i ≤ N ) does not know the length of its input stream. Items arrive at high rates and due to memory/resource constraints, they need to be processed sequentially and in an online manner. Indeed, nodes can locally store only a small amount (i.e., a fraction) of the information with respect to the size of their input data streams and only perform simple operations on them (e.g., elementary arithmetic operations).

Moreover, we suppose that nodes S 1 , . . . , S N cannot communicate among each other. Thus we suppose the existence of a specific node, called the coordinator in the following, with which each node is allowed to communicate (see Figure 1). A coordinator is there to avoid naive centralization of all data and to significantly reduce communication cost over the network. We assume that the communication is instantaneous.

Let σ = a 1 , a 2 , a 3 , . . . , a n be a data stream of items that arrive regularly and sequentially. Each data item i is drawn from the universe Ω = {1, 2, . . . , N }, where N is very large. A natural approach to study a data stream σ of length n is to model it as a fingerprint vector over the universe Ω, given by F = (f 1 , f 2 , . . . , f N ) where f i represents the number of occurrences of item i in σ and 0 ≤ f i ≤ n. Note that in the following by abusing the notation, we denote this "|Ω|-point distribution" by "Ω-point distribution", also known as the item frequency vector of σ.

C. Problem statement

We now formalize the top-k frequent items problem, the windowed top-k frequent items one, and the distributed version of the windowed top-k frequent items problem.

Definition 1 (Top-k Frequent Items). Given a data stream σ of n items a 1 , a 2 , a 3 , . . . , a n , the top-k most frequent items over σ is the set {i ∈ Ω | f i ≥ f (k) } where f (k) is the k-th greatest value in F .
Definition 2 (Windowed Top-k Frequent Items (WTK) [START_REF] Song | Top-k Frequent Items and Item Frequency Tracking over Sliding Windows of Any Sizes[END_REF]). For any time t and any number of time units W , the windowed top-k frequent items problem consists in returning the top-k most frequent items received from time t -W to time t.

Definition 3 (Distributed Windowed Top-k Frequent Items).

For any time t, any number of time units W and N nodes, S 1 , . . . , S N , the distributed windowed top-k frequent items problem consists in returning the top-k most frequent items received among all N nodes from time t -W to time t. In the following we denote our algorithm by FTK CE and the one proposed by Song et al. [START_REF] Song | Top-k Frequent Items and Item Frequency Tracking over Sliding Windows of Any Sizes[END_REF] by FTK.

IV. ALGORITHMS DESCRIPTION A. Preliminaries

At the core of FTK and FTK CE algorithms lies a very simple yet powerful mechanism: coin flipping. Tossing a coin can be viewed as a Bernoulli process or a sequence of independent and identically distributed Bernoulli trials. Each trial has exactly two outcomes (e.g., 0 and 1 or tail and head) and the same probability p to obtain 1 or head (H).

Definition 4 (Bernoulli process).

A Bernoulli process is a finite or infinite sequence of independent random variables X 1 , X 2 , X 3 , . . ., such that:

• For each integer i, the value of X i is either 0 or 1;

• For all values of i, the probability that X i = 1 is the same number p.

Frequency correlated stochastic value. The Bernoulli process we consider here is the number of trials needed to obtain 0 (i.e., first hit time), which precisely corresponds to tossing a coin until the first tail occurs (see Figure 2). Clearly, more attempts implies longer hitting times. Thus the first hit time is a stochastic value statistically correlated to the number of attempts.

To get an insight on the correlation between the maximum hitting time and the number of trials, consider the experiment of obtaining two consecutive heads (until the first tail) with respectively one and two trials of a fair coin (i.e., p = 1/2). As shown in Figure 3, there is only one way to obtain "HHT" with one trial, while there are three possibilities with two trials.

Overview. The left heatmap in Figure 4 presents the global pattern of the hitting time probability evolution as a function of the number of trials. As can be seen, there is a logarithmic relationship between the number of trials and the maximum expected number of consecutive heads. For more empirical and theoretical evidence of this logarithmic behaviour, one can consult for example [START_REF] Kinney | Tossing Coins Until All Are Heads[END_REF], [START_REF] Schilling | The Longest Run of Heads[END_REF], [START_REF] Túri | Limit theorems for the longest run[END_REF]. A logarithmic relationship implies that for a high number of trials, the correlation with the maximum hitting time is less significant than for a small number of trials. On the other hand, there is a linear relationship between the number of trials and the number of times the hitting time exceeds a given threshold (see right heatmap in Figure 4).

B. Original approach -FTK

The original approach to identify the top-k most frequent items is to retain for each item in the stream the maximum number of consecutive heads obtained over all the occurrences of this item at each time unit. For each time unit, only the k items with the highest maximum number of consecutive heads are retained. Finally, the top-k most frequent items over a sliding window of W time units are the items with the highest maximum number of consecutive heads among all the items retained during the W time units.

It turns out that this technique is efficient for very skewed data distributions, but it is no more the case in presence of more homogeneous data distributions where items have comparable frequencies. This is in part due to the logarithmic relationship between the number of trials and the expected maximum number of consecutive heads as observed in Figure [START_REF] Wei | Persistent Data Sketching[END_REF]. In other words, the condition for FTK to correctly detect the k most frequent items is a large frequency gap between the top-k most frequent items and the other ones. Moreover, this gap should increase as a function of the stream length.

C. Our approach -FTK CE

To address this important limitation, we propose another stochastic value, which is robustly correlated to the item's frequency, while keeping as much as possible the properties of the initial approach as detailed in the following.

Instead of keeping only the maximum number of consecutive heads, our algorithm counts the number of times the Bernoulli process (i.e., number of consecutive heads) of an item has exceeded a dynamically defined threshold θ. Relying on a threshold, can be viewed as filtering out items with low frequencies, which resembles in some aspects to the mixed techniques presented in Section II-C. As will be shown in the sequel, the value of this threshold has an impact on both the precision of the returned top-k items and on the space complexity of the algorithm.

As previously described, our algorithm FTK CE is locally run at nodes S 1 , . . . , S N , and at the specific coordinator node. The pseudo-code run at a given node S i , associated with its stream σ, is presented in Algorithm 1. The main data structure maintained by Algorithm 1 is a list denoted by Γ. Each element Send Γ to the coordinator of Γ is a tuple (u, c u ), where c u represents the number of times the Bernoulli process of an item u has exceeded a given threshold θ. Once all items received during a time unit t have been processed, node S i sends to the coordinator its list Γ.

The pseudo-code run by the coordinator node is described in Algorithm 2. The coordinator maintains a first-in firstout linked list denoted by Γ coord . At each time unit, the coordinator merges the information sent by S 1 , . . . , S N to extract the top-k most frequent items received during the last W time units over the N distributed data streams. Technically, at each time unit and for each item u in (u, -) of Γ i , the coordinator sums the total number of times item u has exceeded threshold θ across all the nodes S i and stores this information in Γ coord [0]. Upon query the coordinator sums all c coord u of each item u in (u, -) of Γ coord over the last w time units. Let c Q u be this sum. The coordinator returns then the top-κ items u with the highest c Q u values (see Section IV-D, flexibility of parameters).

D. Properties of FTK and FTK CE

In this section we present the four main properties common to both approaches, which are essential to answer the distributed and windowed top-k most frequent items problem. These properties are a direct consequence of the independence of the Bernoulli processes.

Sliding window. The first and most useful property of these algorithms is their memoryless feature, i.e., every time an item is received both algorithms attribute a stochastic value to this item which is independent from what happened in the past. This is the feature which allows us to deal with sliding windows.

Distributed monitoring. The above feature is also the one which allows us to deal with distributed streams. Thus, a distributed execution of both algorithms produce exactly the same result at the coordinator node as if all N data streams were directly received by a single node (e.g., the coordinator). Γ coord [0] ← empty list

5 for i ← 1 to N do 6 foreach (u, c u ) ∈ Γ i do 7 if u ∈ Γ coord [0] then 8 (u, c coord u ) ← (u, c coord u + c u ) 9 else 10 Γ coord [0] ← Γ coord [0] ∪ (u, c u ) 11 Q ← empty list 12 for j ← 0 to w -1 do 13 foreach (u, c coord u ) ∈ Γ coord [j] do 14 if u ∈ Q then 15 (u, c Q u ) ← (u, c Q u + c coord u ) 16 else 17 Q ← Q ∪ (u, c coord u ) 18 Sort Q in descending order by c Q u 19 T opItems ← first κ items of Q 20 return T opItems
Flexibility of parameters. An important property of both algorithms is to return the top-k most frequent items ordered according to their frequency. This allows both algorithms to dynamically answer any top-κ most frequent items query, with κ ≤ k. In addition, the size of the sliding window can also be dynamically adjusted to any w, with w ≤ W .

Permutation independence. Another important property of both approaches, is their resilience to any ordering manipulation of the items within any sliding window of the data streams.

All this properties shared by FTK and FTK CE are illustrated in Figure 5. V. THRESHOLD DEFINITION Even though both FTK and FTK CE algorithms use a Bernoulli process, they differentiate from each other by the way they aggregate the stochastic values. In the following of this section we detail the computation of the threshold θ used by our algorithm FTK CE .

A. Rationale of the threshold θ in FTK CE

Although the initial approach FTK is interesting when applied on skewed data distributions, simulations on homogeneous data distributions reveal its weakness. This is due to the choice of the aggregated value over the Bernoulli process. Indeed, the maximum number of heads is not a robust metric and it does not efficiently discriminate items based on their frequencies. Example. As an illustrative example, think about identifying the top-1 most frequent item with FTK. Unless the most frequent item occurs more than 50% of times in the sliding window, the algorithm fails in average to correctly identify it as the top-1. Indeed, the top-1 expected precision corresponds to the proportion of its frequency it the sliding window, as the longest number of consecutive heads can be obtained by any other item due to the independence of the Bernoulli processes.

As previously said, what needs to be done is to compute an aggregated value which is more correlated to the item's frequency. Instead of keeping only the maximum number of consecutive heads, our algorithm counts the number of times the Bernoulli process of an item has exceeded a given threshold θ.

Such a threshold should be finely chosen to act like a filter. Indeed, a too restrictive filter (i.e., high θ) would only retain a subset of the true top-k items, while a too permissive one (i.e., low θ) would retain too many extra items. To fix a proper threshold, we combine two known theoretical results issued from the coupon collector and the leader election problems. Briefly the coupon collector allows us to determine how many items should exceed the threshold to ensure that the true top-k most frequent items are among them. Then a result from the leader election problem allows us to derive which threshold enables this quantity of items to be retained.

B. Coupon collector problem

Suppose we have a set of N coupons (corresponding to the N different items in the universe) and we denote by p u the probability of the coupon u to be drawn (according to the frequency distribution of items) such as

p 1 +p 2 +• • •+p N = 1.
For the sake of clarity and without any loss of generality, we suppose that coupons (and items) are ordered decreasingly according to their frequency, such as

p 1 ≥ p 2 ≥ • • • ≥ p N .
The coupon collector problem consists in determining the distribution of the number T N of coupons that need to be drawn with replacement from the set {1, 2, . . . , N } in order to obtain the full collection of N different coupons.

The generalized version of the coupon collector problem allows us to consider a collection of coupons {1, 2, . . . , x} where p = (p 1 , p 2 , . . . , p x ) is not necessarily a probability distribution, i.e., p 1 + p 2 + • • • + p x ≤ 1. This models the presence of a null coupon 0, which is drawn with probability

p 0 = 1 -(p 1 + • • • + p x )
and which is not allowed to belong to the considered collection.

In our case, we consider the collection formed by the k most frequent coupons {1, 2, . . . , k} and the null coupon 0 is formed by all other coupons {k + 1, k + 2, . . . , N } which is drawn with probability

p 0 = 1 -(p 1 + • • • + p k ).
From [START_REF] Anceaume | Identifying Global Icebergs in Distributed Streams[END_REF] we have:

E[T k (p)] = k-1 i=0 (-1) k-1-i |J|=i 1 1 -(p 0 + P j ) , (1)
where P j = j∈J p j and J is a subset of {1, 2, . . . , k} of size i. E[T k (p)] represents the minimum expected number of coupons to be drawn in order to obtain the collection formed by the k most frequent coupons. And once we have the number of all coupons (null and from the collection) to be drawn, we can use the next result from the leader election problem to compute the θ threshold.

C. Leader election problem

The leader election problem is fundamental in distributed systems. A common use case is the selection of a coordinator during the initialization of a service or after the failure of an existing one. The most studied issues in the leader election problems are their time and communication complexities which are essential to adapt to large scale systems. In this paper we are interested in the behaviour of the number of contestants during the election rounds. This is related to space complexity, since knowing in advance the distribution of survivors throughout the election process can lead to a better management of resources. We consider here a randomized election algorithm with the binomial splitting protocol and we adopt the definition of survivors from [START_REF] Kalpathy | Survivors in leader election algorithms[END_REF].

Assume there are n contestants (corresponding to the n items in the data stream) and every one flips a coin, not necessarily fair, but common to all contestants. We note p the probability of obtaining head and 1 -p the one of obtaining tail. Contestants who obtain head are allowed to compete for the next round, while those who obtain tail are eliminated from the election. The set of contestants allowed to compete for the next round is called the advancing set and is denoted by K n . In the coin flipping case, K n ∼ Bin(n, p), hence the name of binomial splitting protocol. K n can be seen as the sum of n Bernoulli random variables, with probability p to get 1 and 1 -p to get 0. The number of contestants remaining after t rounds are called survivors and are designated by Sn,t . Note that as we are not directly interested in electing a winner, we consider the winnerless process where the algorithm continues even if there remains only one contestant. We are precisely interested in the number of survivors after a given number of election rounds. The distribution of the random variable Sn,t is given by Kalpathy, Mahmoud and Rosenkrantz [START_REF] Kalpathy | Survivors in leader election algorithms[END_REF].

Theorem 1 (Survivors distribution [START_REF] Kalpathy | Survivors in leader election algorithms[END_REF]). Suppose we conduct a leader election among n contestants, in which a fair selection of a subset of contestants of a random size K n = Bin(n, p) advance to the next round, and the algorithm is applied recursively on that subset, till all contestants are eliminated (exactly as in the elimination by the coin flipping process). The number of survivors, Sn,t , has the binomial distribution of Bin(n, p t ).

Proof. For self-contained reasons, we include the proof of Kalpathy et al [START_REF] Kalpathy | Survivors in leader election algorithms[END_REF]. The proof is done by induction on t that φ Sn,t (x), the moment generating function of Sn,t , is (1 -p t + p t e x ) n , which is that of Bin(n, p t ). At t = 0, Sn,0 = n = Bin(n, p 0 ), providing a basis for the induction. Suppose now that, for t ≥ 1, Sn,t-1 is distributed like Bin(n, p t-1 ). If exactly k contestants survive till round t -1, of these Bin(k, p) will advance to compete in round t. Thus, letting q = 1 -p, we have the conditional expectation E e x Sn,t | Sn,t-1 = k = k j=0 k j p j q k-j e xj = (q + pe x ) k .

So, we have the unconditional expectation

φ Sn,t (x) = n k=0 (q + pe x ) k Pr[ Sn,t-1 = k],
which gives (by the induction hypothesis)

φ Sn,t (x) = n k=0 (q + pe x ) k n k (p t-1 ) k (1 -p t-1 ) n-k = ((q + pe x )p t-1 + 1 -p t-1 ) n = (1 -p t + p t e x ) n ,
completing the induction.

D. Threshold θ computation

Technically, threshold θ is computed as follows. We use Formula (1) to determine the expected minimum number of items E[T k (p)] to be drawn with replacement and according to their frequency distribution in the data stream in order to ensure that in expectation the true top-k most frequent items are among them. Then we determine the number of election rounds t to be performed in order to elect in expectation the number of items previously defined. This number of rounds corresponds to the value of t when E[ Sn,t ] = E[T k (p)], i.e., when the number of survivors Sn,t equals in expectation to the minimum number of items to be drawn containing the true top-k T k (p).

In the case of a binomial splitting protocol, Sn,t ∼ Bin(n, p t ) (cf. Theorem 1). Thus, t must be such that

E[Bin(n, p t )] = E[T k (p)]
and since E[Bin(n, p t )] = np t , we have:

t = log(E[T k (p)]) -log(n) log(p)
Finally, threshold θ is defined as θ = t.

In practice, as the data stream length and the frequencies of the top-k most frequent items are unknown, the computation of t is impossible. Nevertheless, the threshold θ can be heuristically initialized and dynamically maintained during the execution of FTK CE . In Section VI we consider θ = t , since the ceil value of t maximizes the error of FTK CE .

VI. PERFORMANCE EVALUATION

The present section contains results on simulated data and the main aspect covered here is the precision/recall of our approach (FTK CE ) compared to the original one (FTK) proposed by Song et al. in [START_REF] Song | Top-k Frequent Items and Item Frequency Tracking over Sliding Windows of Any Sizes[END_REF], which is so far, and to the best of our knowledge, the most impressive solution to solve the (distributed) windowed top-k problem.

By precision, we mean the number of top-x items, with 1 ≤ x ≤ k, correctly detected by the algorithms divided by the total number of detected items, i.e., k by design. A particularity of the top-k problem is that precision and recall are equivalent in this case. Indeed, the number of false positives in the returned top-k set corresponds exactly to the number of false negatives not returned by the algorithm.

A. Simulation protocol

To analyze the performance of our approach, we consider simulated data following zipfian distributions, as the family of power law distributions are widely observed in real word data sets and natural phenomena [START_REF] Adamic | Zipf's law and the Internet[END_REF], [START_REF] Newman | Power laws, Pareto distributions and Zipf's law[END_REF].

Furthermore, all of the following experiments have been realized during an unique sliding window on a single node. Since in accordance with the proprieties described in Section IV-D, both algorithms will output the same precision for any sliding window over multiple nodes as long as the data streams keep the same distribution shape.

Concretely, we generate n = 10 6 items containing up to N = 10 4 distinct items and whose frequencies follow a Zipfα distribution with 0 ≤ α ≤ 4.5. Note that Zipf-0 corresponds to the uniform data distribution and Zipf-4.5 corresponds to a extremely skewed data distribution (see Figure 6b). Moreover, the results presented below are an average of 10 3 algorithms executions and we also fix by default k = 15 for clarity and readability of graphs.

B. Items frequency distribution

Figure 6a compares the precision of both FTK CE and FTK algorithms as a function of different Zipf-α items frequency distributions, when queried to answer the top-15 most frequent items problem. FTK CE is capable to detect frequent items even for relatively flat Zipf-1 distributions (see Figure 6b). FTK starts to perform equivalently only from the Zipf-2 items frequency distribution, in which case just the top-1 most frequent item occurs more than 60% of times.

C. Number of top items

Both solutions perform consistently when employed to answer top-k frequent items queries for different values of k (see Figure 7). Moreover, the precision of FTK CE is improving when k is increasing for both frequency distributions of items, while for FTK it is only the case for the Zipf-1 distribution. As seen in Section IV-D, a common property of both FTK CE and FTK algorithms are their ability to answer any top-κ query as long as κ ≤ k. Figure 8 compares their precision when asked for all possible top-κ queries, i.e., 1 ≤ κ ≤ k = 15, which confirms the impressive behavior of our algorithm for all intermediate top-κ queries.

D. Space complexity

In order to obtain an empirical overview of the memory cost, Figure 9 presents the number of counters that is necessary for the FTK CE algorithm in order to answer different topk queries, for 1 ≤ k ≤ 25. Simulation results show that the good precision of the FTK CE algorithm for a relatively homogeneous Zipf-1 distribution comes at a cost in terms of required memory. Nevertheless, in order to answer the top-25 most frequent items query, FTK CE uses less than 300 counters, i.e., less than 3 % compared to the total possible number of different items N = 10000.

Note that the different "steps" are due to the different values of threshold θ. For information, we plot the theoretical number of counters that would be required if the thresholds were directly defined as θ = t, i.e., a float value (cf. Section V-D).

VII. CONCLUSION In this paper we have presented a new approach derived

the state-of-the-art solution provided by Song et al. [START_REF] Song | Top-k Frequent Items and Item Frequency Tracking over Sliding Windows of Any Sizes[END_REF] in order to answer the distributed sliding window top-k most frequent items problem. We have shown some important improvements of the precision of the returned top-k items by our method, especially for homogeneous frequency distributions of data items.

In order to mitigate the necessity to estimate the probability distribution vector p of the true top-k most frequent items, we are currently investigating the means to incorporate or bypass this limitation, although, it can already be done using techniques presented in Section II. We plan to analyze more in depth the theoretical behavior of our algorithm, such as ( , δ)-error approximation or memory and communication cost bounds.

Fig. 1 .

 1 Fig. 1. System model

Fig. 2 .

 2 Fig. 2. Coin tossing until first tail.

Fig. 3 .

 3 Fig. 3. Obtaining exactly two consecutive heads with one or two trials.

Fig. 4 .

 4 Fig. 4. Heatmap of probabilities to obtain a given number of consecutive heads (left) or a given number of threshold exceeds (right) as a function of the number of trials.

Algorithm 1 : 2 Γ ← empty list 3 foreach item u that arrives at t do 4 l 5 if l ≥ θ then 6 if u ∈ Γ then 7 ( 8 else 9 Γ

 123456789 MAINTAINFTK CE (σ, θ) Input : σ: data stream, θ: hitting time threshold Output: continuously evolving data structure Γ 1 foreach time unit t do ← BERNOULLIPROCESS(p) u, c u ) ← (u, c u + 1) ← Γ ∪ (u, 1) 10

Algorithm 2 :foreach time unit t do 2 3

 223 RETRIEVETOPK (Γ 1 , . . . , Γ N , w = W , κ = k) Input : Γ 1 , . . . , Γ N : local nodes updates, w: query size of the sliding window (default w = W ), κ: query number of top items (default κ = k) Output: the top-κ most frequent items during the last w time units 1 Remove last element Γ coord [W -1]Append a new element at the beginning of Γ coord 4

Fig. 5 .

 5 Fig. 5. Windowed and/or distributed FTK algorithm execution.

Fig. 6 .

 6 Fig. 6. FTK CE and FTK top-15 precision (a) and probability mass function of the first 15 most frequent items (b) for different Zipf distributions.

2 Fig. 7 .

 27 Fig. 7. Top-k precision, with k ∈ {5, 10, 15, 20, 25}.

Fig. 8 .

 8 Fig. 8. Intermediate top-κ query precision, with 1 ≤ κ ≤ k = 15.

2 Fig. 9 .

 29 Fig. 9. Number of counters used by the FTK CE algorithm to answer the top-k most frequent items problem, for 1 ≤ k ≤ 25.

Both algorithms, FTK CE and FTK, share these two properties (cf. Section IV-D).