domain: info math

text:
Philippe Jacquet
email: philippe.jacquet@nokia-bell-labs.com

Bernard Mans
email: bernard.mans@mq.edu.au

Blockchain moderated by empty blocks to reduce the energetic impact of crypto-moneys

While cryptocurrencies and blockchain applications continue to gain popularity, their energy cost is evidently becoming unsustainable. In most instances, the main cost comes from the required amount of energy for the Proof-of-Work, and this cost is inherent to the design. In addition, useless costs from discarded work (e.g., the so-called Forks) and lack of scalability (in number of users and in rapid transactions) limit their practical effectiveness.

In this paper, we present an innovative scheme which eliminates the nonce and thus the burden of the Proof-of-Work which is the main cause of the energy waste in cryptocurrencies such as Bitcoin. We prove that our scheme guarantees a tunable and bounded average number of simultaneous mining whatever the size of the population in competition, thus by making the use of nonce-based techniques unnecessary, achieves scalability without the cost of consuming a large volume of energy. The technique used in the proof of our scheme is based on the analogy of the analysis of a green leader election. The additional difference with Proof-of-Work schemes (beyond the suppression of the nonce field that is triggering most of the waste), is the introduction of (what we denote as) "empty blocks" which aim are to call regular blocks following a staircase set of values. Our scheme reduces the risk of Forks and provides tunable scalability for the number of users and the speed of block generation. We also prove using game theoretical analysis that our scheme is resilient to unfair competitive investments (e.g., "51 percent" attack) and block nursing.

I. INTRODUCTION

Popular cryptocurrencies have now been effectively in use for more than ten years (e.g. Bitcoin [START_REF] Nakamoto | Bitcoin: a peer-to-peer electronic cash system[END_REF]). In addition to the increasing appetite for its key financial aspects (e.g., fast, transparent, secure and private), their potential to facilitate, verify, or enforce the negotiation or performance of various transactions provides an important innovative service that will have a disruptive impact for many applications.

Actual cryptocurrencies are completely decentralized protocols. They are based on the blockchain concept where transactions are regrouped by blocks and confirmed through a common distributed directory connected in peer to peer organization. Its novelty comes from the combination of existing concepts and results from distributed computing, cryptography and game theory. The transactions and the blocks are chained via a chain of hash function which is too expensive to forge and falsify. The blockchain allows that each block and each transaction can be checked back by anyone as if there would be in a gigantic distributed accounting book. The block has also the function of tracing and controling the inflation of the Bitcoin volume and facial value. This is done by giving a reward to the block miner (the action of proposing a block) which is accepted by distributed consensus when the block is "confirmed" (e.g., in Bitcoin, followed by six newer blocks). A block within a forked branch that is not properly confirmed loose its transactions.

One drawback of cryptocurrencies such as Bitcoin is the moderation of block mining rate. With mining reward as a tool in the control of volume of values, there is a fierce competition in block mining. Some individuals may be tempted to mine multiple blocks in order to augment their revenue or bend the system in their favor (e.g., by double spending).

In order to avoid that too many simultaneous blocks are mined and proposed for confirmation, Bitcoin requires a "proof of work" by forcing the block miner to execute a large number of CPU cycles via iterated hash computations before submitting his/her block. The idea of computational puzzle as proof of work is not new, it appears first in the seminal work of Dwork and Noar [START_REF] Dwork | Pricing via processing or combatting junkmail[END_REF] and was later suggested to avoid Sybil attack by Aspnes et al. [START_REF] Aspnes | Exposing computationally challenged Byzantine impostors[END_REF]. The proof of work provides scarcity and uniqueness that help reduce the individual block mining rate.

However the "Proof of Work" (PoW) presently costs 100,000,000,000 CPU cycles (around 10 minutes on a current PC) and if one million miners contend at the same time, then the energy cost of mining one Bitcoin exceeds the value of the Bitcoin itself. Furthermore this cost is expected to quadratically grow or at least linearly grow with the number of contending miners leading to a protocol whose energy cost can absolutely not be sustainable in the near future. Several studies have considered the impact of cost of energy in the mining of Bitcoin (e.g., [START_REF] Bouri | Bitcoin for energy commodities before and after the December 2013 crash: diversifier, hedge or safe haven?[END_REF], [START_REF] Das | Bitcoin's energy consumption: Is it the Achilles heel to miner's revenue?[END_REF], [START_REF] Hayes | Cryptocurrency value formation: An empirical study leading to a cost of production model for valuing bitcoin[END_REF], [START_REF] Ji | Information interdependence among energy, cryptocurrency and major commodity markets[END_REF]).

In order to avoid these catastrophic consequences, a plethora of alternatives have been suggested and analysed (e.g. [START_REF] Garay | The bitcoin backbone protocol: Analysis and applications[END_REF], [START_REF] Garay | Leonardos The bitcoin backbone protocol with chains of variable difficulty in proceedings of the 36th[END_REF]), including variants of proofs of stake (e.g., [START_REF] Bentov | Proof of activity: Extending bitcoin's proof of work via proof of stake[END_REF], [START_REF] Wood | Ethereum: A secure decentralised generalised transaction ledger[END_REF]) or various proofs of "something" (e.g., proof of Exercise [START_REF] Shoker | Sustainable blockchain through proof of exercise[END_REF]). The later are difficult to implement since they demand external element of proof (fortune, volume and age of coins, etc) and are difficult to extrapolate to blockchain system not related to currencies. Other attempts to tackle the huge waste generated by the Proof of Work as implemented in Bitcoin have been aiming at turning them into work that is actually useful: e.g., solving practical problems have been investigated in [START_REF] Ball | Proofs of useful work[END_REF], extended to present PoWs that are based on the Orthogonal Vectors, 3SUM, and All-Pairs Shortest Path problems in [START_REF] Ball | Average-case fine-grained hardness[END_REF], [START_REF] Ball | Proofs of Work from Worst-Case Assumptions[END_REF], and can be used to allow for much quicker verification and zero-knowledge PoWs. Yet it is unclear how this creates incentives for large amount of transactions, and how it guarantees Liveness (and in particular freedom from starvation if there is no volunteer to solve a practical problem). Also it still remains paramount to reach agreement and to prevent double spending while providing a way to mint the currency.

In this paper, we focus on the unsustainable energy cost and propose a cryptocurrency protocol moderated through a "green" mining protocol in such a way that it will remove the prohibitive energy cost of the proof of work while keeping the blockchain mining input rate between reasonable limits. Those limits can be arbitrarily tuned a priori, while the proof of work CPU parameter must be constantly updated. In fact the system we propose can be applied to blockchain systems not related to cryptocurrencies and which necessitate high frequency updates [START_REF] Kelly | AR will spark the next big tech platform -call it Mirrorworld[END_REF].

Our validation of this scheme is inspired by "green" leader elections [START_REF] Jacquet | A Novel Energy Efficient Broadcast Leader Election[END_REF], [START_REF] Cichon | On Leader Green Election[END_REF]. At its core our model implements a scheme which guarantees a tunable and bounded average number of simultaneous mining whatever the size of the population in competition, like a Leader Election. In addition to public verifiability, our scheme provides liveness and fairness: the unique chain grows and the probability of electing each party is independent to its relative computational power. Our model is "permissionless": there is no explicit membership protocol, anyone can join the system. Our model also offers the safety property (blocks are eventually confirmed). Finally our scheme reduces the risk of Forks (divergent chains of blocks that need to be eventually discarded) and provides tunable scalability for the number of users and the speed of block generation. Interestingly our scheme could be adapted to the aspirational "Proof of Kernel" [START_REF] Lundbaek | Practical Proof of Kernel Work & Distributed Adaptiveness[END_REF] which consists into reducing the population allowed to contend for mining. In this case the PoW is maintained but with a much reduced difficulty just in order to prevent block forgery.

The exact contribution of our work and the structure of the paper are as follows:

• We introduce our green blockchain protocol in Section II.

Our protocol uses a block generation scheme that does not use a nonce in its Proof of Work. The novelty of our protocol comes from a call field that regulates the rate of creation of transaction blocks, in addition to empty blocks. • We prove the performance analysis of our protocol in Section III. The methodology of the proof follows a distributed leader election via collision scheme (that has an interest on its own). The technique garantees a tunable and bounded average number of simultaneous mining, whatever the size of the population in competition for block generation, thus offering full scalability.

• In section IV we present (in two steps) a protocol for implicit empty blocks that renders the scheme completely distributed, tunable and scalable. As the scheme also reduces the chances of forks, it further reduces the energy waste. We provide the performance analysis of the implicit empty block scheme. • In Section V, we prove the resilience of our scheme: as energy wasting PoW farming is no longer possible with our new scheme, we prove that block mining predators that create attack by (what we call) "block nursing", have such a low expectation of success that it renders attacks, such as "51 percent" attack, prohibitive and unworthy. • We give concluding remarks and highlight future works in Section VI.

II. THE GREEN COIN MINING PROTOCOL

A. Parameters and format

Our Green Coin protocol is based on the following parameters:

• an integer k;

• a vector of increasing probabilities of length k + 1: P 0 , P 1 , . . . , P k , with P k = 1; • an upper bound N on the maximum admissible number of contending blocks, that can be set as large as possible. Typical values for these parameters would be k = 8, N = 2 32 are examples. The green coin leader protocol consists in authorizing the mining of an average number of order N 1/k out of n ≤ N contending blocks.

As per Bitcoin, each block of the Green Coin protocol will carry some values obtained by hash function. We denote h the length of the hash value fields in the block. A typical value is h = 256 (32 bytes). But while Bitcoin has only one kind of block, Green Coin relies on two kinds of blocks:

• the regular block containing transactions;

• the empty block which does not contain any transactions. The regular block format is similar to Bitcoin block format but with the difference that it does not contain a nonce field but instead a call field. The call field dictates the required criteria for the next hash value field. The following table gives an abstract format listing the most significant fields:

1 hash of previous block 2 date 3 list of transactions ... ...

call value 5 hash of the block

The empty block looks similar but with no transaction list. 1 hash of previous block 2 date 3 call value 4 hash of the block

B. Mining protocol

Initially, to simplify our presentation, we will assume that empty blocks are mined by a central entity and on a restricted block server. We will discuss later how the protocol can be made distributed or how to face forgery.

A block can be mined only if its hash value is smaller than the call value of the previous block. The call field of a regular block has always the same value which is 2 h+1 P 0 -1. If no regular block is mined, after a certain lapse of time the central entity mines an empty block. Unlike regular block hash values, an empty block hash value does not need to be smaller than the call value of the previous block. The call value of the first empty block should have value 2 h+1 P 1 -1. As long as no new regular block is mined, the central entity mines empty block with successive call values 2 h+1 P 2 -1, . . . , 2 h+1 P k -1. After k mined empty blocks the call values sequence restarts.

There are three facts that are worth noting:

• as there is no nonce field in the regular block there is no proof of work computation required, • instead, the blocks are authorized via the call values which have the effect of regulating the mining rate, • the non-authorized blocks do not need to be submitted and this limits also the traffic generated by the block mining. Liveness. If a call fails, i.e. no regular block is mined, then a new call will be made via a new empty block. Since P k = 1, the last call value is the max-value 2 h+1 -1. Therefore any competition of block mining will result in at least one block mined. Figure 1 displays an example of block sequences in the blockchain. The chain is enforced by the hash values Y 0 , Y 1 , . . . the quantity "Call1" is the default value of the call value in an ordinary block (containing transactions). The value of a regular block hash should always be smaller than the call value of the previous block, regardless the previous block is empty or regular. Empty blocks which follows a block don't need to follow this rule. To illustrate in figure 1 the ordinary block starting with Y 3 mined after the empty block starting with Y 2 must have its hash value (Y 4) smaller than the call value of the previous block: "Call3". Same thing for block starting with Y 4, is hash value Y 5 must be smaller than the Call value of block starting with Y 3, which is "Call1".

III. PERFORMANCE ANALYSIS USING LEADER ELECTION

A. Analogy of a classic leader election via collision

Let us introduce a game of leader election to analyse the performance of our protocol and its scalability. The goal of leader election (e.g., [START_REF] Grabner | Sorting algorithms for broadcast communications: Mathematical analysis[END_REF], [START_REF] Prodinger | The Asymmetric Leader Election Algorithm with swedish stopping: A probabilistic analysis[END_REF]) is to select one among n > 0 players, by proceeding through a number of rounds. Note that using rounds is also commonly accepted that the Blockchain model incorporates some degree of synchrony assumptions: in a network with unbounded delay, the adversary can boost its power just by making the non-faulty parties incur higher delays (e.g., [START_REF] Decker | Information Propagation in the Bitcoin Network[END_REF]). We will show that these assumptions are actually unnecessary for our complete scheme in Section IV.

Informally, the rounds of our leader election are made via coin tossing. We assume that each competitor has a coin whose head probability is p and tail probability q = 1-p. We want to proceed to a leader election among n ≥ 1 competitors. At the beginning all the n competitors transmit. If this results into a collision then each competitor tosses the coin, only those who get a head contend for the second round, we call them the survivors. If the second round results in a collision, then a second coin tossing occurs and a subset of survivors contend, and the protocol continues until none survive. In this case we take as result the last non empty set of survivors.

Usually there is an additional procedure in order to reduce the survivor population to a single leader using a collision algorithm. In our case, this is not necessary as long as the subset of survivor is of reasonable size: we will prove using analytic combinatorics that the average size of the last non empty survivor set is q p log(1/p) with some fluctuations of small amplitude. Note that this value is finite and independent of the initial number contenders (although small fluctuations may enlight some non trivial dependencies). This number can also be tuned to be small or large by tuning the parameter p. This can be done by compromising with the average number of rounds which tends to log 1/p n when n → ∞.

If we wanted to imitate this process for the call values in the empty block, we will need a sequence (P 0 , P 1 , . . .) such that P = p represents an exponential descending staircase but this will create the case that after the first call one would have already n mined blocks.

However we can use our protocol to create the ascending exponential staircase effect when there is a large yet fixed limit N to the number of simultaneous contenders. In this case we suppose that P 0 = 1 N and that P = 1 N p -for ≤ k. In order to have P k = 1 one must have p = 1 N 1/k . If N = 2 32 and k = 8 we will have p = 1 16 and the call sequence will be:

call value rank Probability sequence call value 0 ≤ ≤ k = 8 P = N k -1 2 h+1 .P -1 0 (initial) 2 -32 2 224 -1 1 2 -28 2 228 -1 2 2 -24 2 232 -1 3 2 -20 2 236 -1 4 2 -16 2 240 -1 5 2 -12 2 244 -1 6 2 -8 2 248 -1 7 2 -4 2 232 -1 8 1 2 256 -1
We denote M n the average number of regular mined block when n blocks are in competition after a regular block. Note that an important yet regular assumption in this paper is that successive calls of a hashing function are independent. Of course stricto sensu this is not true since hash value determinations are deterministic computations, but traditionally the better successive hash values imitates independent random variables, the better is a hash function. In fact this argument is the foundation for accepting the resilience of blockchains (made of successive hash computations) against attacks.

Let M n denote the number of blocks mined after the th empty block under the condition that all the previous empty blocks resulted into no regular block mined. We have M n = M 0 n and since P k = 1: M k n = n. Since the fact that the successive calls to hash values are assumed independent, the number of blocks called by the th empty block is a binomial random variable B(n, P ) of probability P . For < k when the binomial variable is B(n, P ) = 0 which occurs with probability (1 -P ) n , no block is mined after the th block and M n = M -1 n . Thus for all integers m, m > 0:

P (M n = m) = n m P m (1 -P ) n-m +(1 -P ) n P (M +1 n = m) (1)
and

P (M n = 0) = δ(n). (2)
where δ(n) = 1 if n = 0 and zero otherwise, also known as Kroenecker symbol.

Let M n (u) = E[u M n ]. Lemma 1: We have for < k M n (u) = (1 + P (u -1)) n -(1 -P ) n +(1 -P ) n M +1 n (u) and M k n (u) = u n
. Proof: This is a direct application of Equation (1). Lemma 2: We have the identity

E[M n ] = nP 0 + =k =1 nP j< (1 -P j ) n (3)
Proof: This is a direct application of previous lemma by using

E[u Mn ] = E[u M 0 n ] and E[u M n ] = ∂ ∂u M n (1)
. Theorem 1: For all n ≤ N , we have the estimate

E[M n ] = O(N 1/k ).
Remark: the optimal value is k = O(log N ) but lower values of integer k are already interesting.

Proof: From Equation 3 we get the inequalities

E[M n ] ≤ nP 0 + k =1 nP (1 -P -1 ) n ≤ nP 0 + 1≤ ≤k nP exp (-P -1 n) .
The quantity 1≤ ≤k nP exp(-P -1 n) is equal to

1≤ ≤k n N p exp(-p -1 n/N ).
This quantity is smaller than f (n/N ) with f (x) = 1 p ∈Z g(p x) with g(x) = xe -x . The function f (e x ) is periodic of period log p and therefore is bounded.

Since p = N -1/k , n/N ≤ 1 and n ≤ N , we get

E[M n ] = O(N 1/k ).
Theorem 2: We have the more precise estimate

E[M n ] ≤ n N + AN 1/k . ( 4
)
with A = 1 log(1/p) k∈Z |Γ (1 + 2ikπ/ log p)|, p denoting N -1/k and where Γ(.) is the Euler "Gamma" function.

Proof: We can give an accurate estimate of the maximum value of function f (x). The function f (e x ) is periodic of period log p and therefore has a Fourier decomposition:

f (e x ) = k∈ g k e 2ikπx/ log p (5)
where g k is the Fourier coefficient. We have

g k = 0 log p f (e x )e 2ikπ/ log p dx = 1 log(1/p) ∞ 0 g(x) 2ikπ/ log p-1 dx = 1 log(1/p) Γ (1 + 2ikπ/ log p)
and then use the upper bound |f (e x )| ≤ k∈Z |g k |.

In passing we get the mean value of f (e x ) to be equal to

g 0 = 1 log(1/p) .
Figure 2 shows the quantity E[M n ] versus n for various parameters. Notice that the sequence of bumps reflects the periodic fluctuations as function of log n analyzed in the upper bound.

Figure 3 shows the same quantities obtained by simulation, each point being simulated 1,000 times.

In fact, we can give a close expression of the distribution of M n .

Lemma 3: For all complex number u:

E[u Mn ] = (1 + P 0 (u -1)) n -(1 -P 0 ) n + 0< <k j< (1 -P j ) n × ((1 + P (u -1)) n -(1 -P ) n ) +u n j<k (1 -P j ) n .
Proof: By application of Lemma 1. Figure 4 displays the various shape of the sequences P (M n > m) versus integer m for various parameters. Notice that the sequence of descending bumps in the plots comes from the mixture of the different binomial distributions.

We can also give an estimate of the exponential tail distribution of M n by the following theorem about large deviations.

Theorem 3: Let p = N -1/k . For all integer m > 0, we have the estimate Proof: We have P = p k-and

P (M n > m) ≤ k + e p (1 + p) m (6)
E[u Mn ] ≤ (1 + p k (u -1)) n -(1 -p k ) n + 0< <k 1 + p (u -1) n -(1 -p ) n (1 -p +1 ) n +u n (1 -p) n Let u = 1 + p, we have 1 + (u -1)p = 1 + p +1
and therefore

(1 + (u -1)p )(1 -p +1 ) = 1 -p 2( +1) ≤ 1. Thus E[u Mn ] ≤ (1 + p k+1 ) n + k. Since (1+p k+1 ) n ≤ exp(np k+1 ) = exp(pn/N ) and n < N we have exp(np/N ) ≤ exp(N -1/k ).
We conclude the proof with the observation that for all integer m: (n, m) indicates the number of times the event M n = m has been obtained during the simulation with the color code: black when more than 64 times, red when between 16 and 64, blue when between 4 and 16, green when between 1 and 4.

u m P (M n > m) ≤ E[u Mn ].

IV. DECENTRALIZED EMPTY BLOCK MINING

For the sake of simplicity, we have initially described our scheme with a requirement to have a central authority to create and mine empty blocks. We now remove this constraint by making the empty block creation fully distributed. For the sake of clarity, we extend our scheme in two steps (with the introduction of two features):

• (A) Time moderated empty blocks mining; • (B) implicit empty blocks mining.

A. Time moderated empty block mining

In this extended scheme, now all entities can mine empty blocks. In this case in order to avoid unfairness between empty miners, a new empty block will be allowed only if its date is above a minimal gap time between the last full and empty block time. For comparison with other existing schemes, the Minimal Gap Time (MGT) can be set to one minute (e.g., in Bitcoin this is called the Block Time, the average time between blocks, and the difficulty of the PoW is adjusted to make the time about 10 minutes; while the block time for Ethereum is set to between 14 and 15 seconds). Note that, in this case, we still need to have at least one entity mining empty blocks to guarantee liveness. Hence for this first variation we assume that possibly several (and at least one) peer-nodes generates empty blocks and thus play the role of a distributed timestamping and block servers.

Time can be captured using Unix universal time (POSIX), a widely used time-stamping system in Unix-like and many other operating systems and file formats, that is commonly used for Blockchain systems. However, one difficulty is that the date given by the clock is not mandatorily accurate (e.g., Unix time is not a true representation of UTC, and leap seconds are not accounted for). However note we are only interested in the time difference in this part. One possibility is that an additional time stamp is added to the block in order to reflect the local time when the timestamping server received the block. Of course, since the timestamping server's time is local, it can only be added at the reception and will be excluded from the hash value computation of the block. An empty block received before the expiration of the minimum time gap with the local time of the timestamping server will be delayed. An empty block with a time stamp which does not show the MGT offset with the original time stamp of a full block will be discarded.

Also the date field of the empty blocks must be excluded from their hash value computation. Otherwise full blocks with very different hash values could be called by different empty blocks on different peers just because the latter show different hash value due to different time stamps. Hence the sequence of hash values of the empty blocks mined after a full block will follow a deterministic sequence. If we ignore the clock drifts, the use of the time stamp does not change the performance analysis of the scheme as we retain the important property that two consecutive calls to hash function generate independent hash values.

B. Implicit empty block mining

We can now extend the previous scheme by exploiting the fact that the sequence of hash values of the empty blocks mined after a full block will follow a deterministic sequence, and thus make them "implicit". In addition, and finally, we remove completely the requirement of any special or centralized entity and make the scheme fully distributed: one does not need a special or central entity to initiate empty blocks since empty blocks will now become implicit, i.e. no empty blocks will be mined. The modification of the protocol is the following:

• Upon reception of a full block within less than one MGT after the mining of the last full block, the block server discards it; • Upon reception of a full block within less than MGT (1 ≤ ≤ k) after the mining of the last full block, with either new block's hash value is larger than 2 h P -1 or the previous block hash value is not the hash value of the last full block, the block server discards it.

Note that another advantage of this scheme is that it also minimises the risk of creating forks as full blocks are discarded earlier.

C. Performance analysis of the implicit empty block scheme

The main difference with the previous scheme analysis is that the hash value of the blocks after each empty block are no longer independent. In fact the hash value of a full block candidate is no longer possibly related to a new empty block. Indeed the previous block hash value field is no longer the hash value of the previous empty block, since it does no longer exists, but the hash value of the last full block. Keeping the previous notations we can state our main theorems and lemmas.

Lemma 4: For m > 0 we have the expression

P (M n = m) = n m P m 0 (1 -P 0 ) n-m + k-1 =1 n m (P -P -1 ) m (1 -P ) n-m +δ(m -n)(1 -P k-1 ) n
Proof: We call slot the time interval of length MGT. Let assume that n full blocks are in competition. Let 0 < < k, the probability that a block has a hash value comprised between 2 h P -1 and 2 h P is P -P -1 . Such a block will be mined on the + 1-th slots after the last full block if and only if all the other full blocks in competition have their hash values greater than or equal to 2 h P . Those which have the hash value greater than 2 h P will not be mined. The hash values of the blocks being assumed independent the binomial expression. The case = 0 corresponds to blocks which have value smaller than or equal to 2 h P 0 . In the case = k we have P k = 1 and occur when all the blocks have hash values greater than or equal to 2 h P k-1 Fig. 6: Average number E[M n ] of mined blocks with explicit (solid) and implicit (dashed) empty blocks mining versus n for k = 16.

Lemma 5: We have the expression:

E[M n ] = nP 0 + k =1 n(P -P -1 )(1 -P -1 ) n-1 . (7)
Proof: This is a direct expression of the previous lemma. We have

E[M n ] = ∂ ∂u E[u Mn ]| u=1 . Indeed for u complex: m u m n m (P -P -1 ) m (1 -P -1 ) n-m = ((P -P -1 )u + 1 -P -1 ) n
and the derivative of the right hand side with respect to variable u is equal to n(P -P -1 )((P -P -1 )u + 1 -P ) n-1 . We notice that when = k we have

n(P -P -1 )(1 -P -1 ) n-1 = n(1 -P k-1 ) n since P k = 1.
The performance of the implicit empty blocks strategy are comparable to the performance of the explicit empty blocks.

In fact we see that the plots of the average number of mined blocks oscillate and cross each other when we compare both strategy (see Figure 6). Theorem 4: For n ≤ N we have the property:

E[M n ] = O(N 1/k ).
Proof: We have

E[M n ] -P 0 n = k =1
n(P -P -1 )(1 -P ) n-1 .

Since P = p k-and p k = 1/N we get

E[M n ] - n N = k =1 n(1/p -1)P (1 -P -1 ) n-1 = k =1 n(1/p -1)P (1 -P -1 ) n (1 -P -1 ) ≤ 1 p k =1 nP (1 -P -1 ) n since (1 -P -1 ) -1 ≤ (1 -p) -1 .
We recognize in the last right hand term an expression which we have already proven to be O(N 1/k ) in the proof of Theorem 1. Using the same reasoning, we obtain a more precise estimate via the use of the "Gamma" function:

E[M n ] ≤ n N + BN 1/k with B = 1 p log(1/p) k∈Z Γ 1 + 2ikπ log p . (8)
V. GAME THEORETIC APPROACH FOR BLOCK NURSING, 51 PERCENT ATTACK

A. The "51 percent" attack

With the nonce disappearing in our scheme (from the internal format of the block that is hashed), any Proof of Work farming is no longer possible in order to achieve a competitive advantage in the mining contest. Indeed to change the hash function of the block, there is a need to change the content of the block, i.e. the Merkel tree representing the transaction confirmed by the block. In order to make the task even more difficult one can enforce the rule that the Merkel tree represents an ordered list of transactions. Under this condition modifying the hash value would need to modify the set of transactions contained in the block. This would make block nursing far less than proof of work farming since transaction identifiers should be distributed in caches while proof of work only require local increments of the nounce integer.

Nevertheless the proof of work farming could be replaced by block nursing. Instead of working on a single block and changing its hash function via the nonce, an institution prepares a set of blocks with different transaction combinations, since it is the only way to modify the block hash function.

Nursing blocks will have a higher cost per hash function than with Proof of Work farming, since one has to access and retrieve transaction IDs. Furthermore not every transaction combination may be permitted, and some may not be interesting, resulting into an unacceptably low income. Also the set of currently available transactions may not be large enough to offer enough combinations. However, in the following we will assume that we have no such limit and assess the risk of nursing blocks.

In this section we analyse the so-called 51 percent attack. It consists to measure the additional means in terms of processing power block nurse must commit in order to gain one term in the probability of prevailing against an adversary nurse.

We will prove the following theorem: Theorem 5: if the adversaries are of equivalent power then one adversary increases of of its probability to win a block mining needs an increase of 1-p 2 2p log(1/p) of the size of block nurse factory.

We notice that if p is small the amplifying factor can be large. for p = 2 -32/k for k = 8, 12, 16 we respectively get an amplification factor of 6.64, 3.95, 3.32.

B. Detailed analysis

Let A be a competitor nursing m blocks and B another competitor B nursing n blocks, let L m,n be the probability L m,n of A losing for a block mining against B. We will show that the quantity L m,n starts to decrease significantly only when m is of the order n/p. Since in the above examples one has 1/p greater than 4 or more, this would require a major investment compared to B. In reciprocity if B wants to balance with A, it would be sufficient that B invests a little more than p times A's investment. Furthermore 1/L m,n is the average length of consecutive mined blocks of miner A against miner B. It estimates the ability of miner A to have confirmed blocks and fork from miner B to take the lead on the currency.

We give the following theorem in the context of explicit empty block mining, where the consecutive hash values are assumed to be independent random variables.

Theorem 6: We have L m,n asymptotically larger than L(x) where x = m/n and

L(x) = log((x + p)p) -log(px + 1) 2 log p (1 + Q(log x))
with Q(.) a periodic function of small amplitude and period log(1/p). Proof: We provide the main steps of the proof. After each non empty mined block there is a potential sequence of k slots, called with empty blocks, to insert the next non empty block. If the calls make that A inserts a block on a slot before the slot of B, A wins the mining. If A and B select the same slot, A and B either win or loose with probability 1/2. (Note that for the sake of the explanation here, and without loss of generality, we assume that A and B mine only one block each.)

If we assume that the all hash function for the blocks nursed by A are independent, the probability that A mines a block on the first slot is 1 -(1 -P 0 ) m , the probability that it mines a block on slot is

(1-P 0 ) m ו • •×(1-P -1 ) m (1-(1-P ) m ).
At the same time the probability that the competitor B mines a block on slot is also (1

-P 0 ) n • • • (1 -P -1 ) n (1 -(1 - P ) n ).
The probability that a competitor mines a block on a further slot is (1

-P 0 ) n • • • (1 -P -1 ) n (1 -P ) n .
Therefore the probability that player A mines a block at slot and wins against B is equal to the sum of half of the first probability plus the second probability, namely 1 2 (1

-P 0 ) n+m • • • (1 - P -1 ) n+m (1 -(1 -P ) n )(1 + (1 -P ) m ): L m,n = 1 2 (1 -(1 -P 0 ) n )(1 + (1 -P 0 ) m ) + 1 2 k =1 (1 -P 0 ) n+m • • • (1 -P -1 ) n+m ×(1 -(1 -P ) n )(1 + (1 -P ) m )
Thus we get

L m,n = 1 2 k =0 (1 -(1 -p ) n )(1 + (1 -p ) m ) × k i> (1 -p i ) n+m ≥ 1 2 k =0 (1 -(1 -p ) n )(1 + (1 -p ) m ) ×(1 - p +1 1 -p ) n+m Since p k = 1/N , we have L n,m ≥ L x (n) + O(n/N ).
with

L x (n) = 1 2 ≥0 (1-(1-p ) n )(1+(1-p ) nx )(1- p +1 1 -p ) (1+x)n .
The Mellin transform of L x (n) with respect to variable n is + O( (s)). The function L * (s) has therefore a pole at a s = 0 and at integer multiples of 2iπ/ log p. The pole at s = 0 gives a contribution to the asymptotic of L x (n), when n → ∞, which is

L * x (s) = Γ(s) 2

VI. CONCLUSION

We have presented a new blockchain scheme which gets rid of the overwhelming waste of energy created by the Proof of Work used in Blockchain protocols such as Bitcoin. The technique used for the proof of our scheme is based on the analysis of a distributed Green Leader Election (which is of interest on its own).

The main difference with Bitcoin-like Proof-of-Work schemes beyond the suppression of the nonce field (triggering most of the waste), is the introduction of empty blocks which aims are to call regular blocks following a controlled staircase set of values. In a simplified approach (that can be relevant for some particular sets of applications or peers), the security of the scheme comes from a secured repository of mined empty blocks by a single authority. Hence we also introduced and analysed a completely distributed block mining protocol that uses an implicit empty block mining which does not need any central authority.

With the disappearance of the nonce in the proof of work, we also consider attacks on the cryptocurrency where it would take other variants of proof of work farming. We analysed the performance of a new strategy, which we name "block nursing" to prove that it will be inherently more complicated than proof of work farming and much less rewarding.

It is also clear that our work supports the case of green alternatives to current Blockchain designs that are wasting huge amount of energy and are unsustainable. This provides valuable input to new applications while it re-enforces an ongoing attention towards relevant policies.

Fig. 1 :

 1 Fig. 1: A sequence of blocks, empty blocks are grayed/yellow.

Fig. 2 :

 2 Fig. 2: The quantity E[M n ] and the upper bound given by (4) in red versus n for N = 2 32 , (top) for k = 8, (middle) k = 12, (bottom) k = 16.

Figure 5 Fig. 3 :

 53 Figure 5 displays the histograms of 1,000 simulations of M n versus n for N = 2 32 and k = 8, 12, 16. The color of the point

Fig. 4 :

 4 Fig. 4: Computed values of P (M n > m) with upperbound given by (6) in red versus m for n = 10, 000, with N = 2 32 , (left) for k = 8, (right) k = 12, (bottom) k = 16.

Fig. 5 :

 5 Fig. 5: various values of M n versus n simulated 1000 times black values appeared more than 64 times, red more than 16 times, blue more than 4 times, green more than once, with N = 2 32 , (top) for k = 8, (middle) k = 12, (bottom) k = 16.

-( 1

 1 + x) log(1 -p +1 1 -p ) -(i + jx) log(1 -p )

1 i=0 1 j=0Fig. 7 :

 117 Fig. 7: Function L(x) (up) for various values of p, (down) function L m,n for n = 10, 000.

ACKNOWLEDGMENT

For the research, B.M. was partially supported by the Australian Research Council Grants DP140100118 and DP170102794. Part of this work was done when BM was visiting LINCS.

We are indebted to Daniel Augot for earlier discussions on Blockchain systems.


From Foraging to… foraging

SPECIAL FEATURE

Wild fruit from the Anona Senegalensis (Combretones)©FAO/Roberto Faidutti From Foraging to....foraging

Edmond Dounias

Only 12000 years ago humankind was still depending exclusively on foraging activities for daily subsistence. Today, the hunter-gatherer societies whose livelihoods still primarily depend on resources that are "taken from the wild" represent only 0,002% of the current world population. We tend to consider these persisting nomadic foragers as the very last depositories of a bygone era when humans were struggling daily to obtain food in very precarious circumstances. This way of apprehending our contemporary hunter-gatherers induces several misconceptions vis-à-vis foraging activities and the potential role they could still play in managing uncultivated resources and in feeding the world.

Read more

Foraging is seen as an improbable way of tracking down resources. There is a strong belief that nature acts as a safety net in which poor and hungry people may occasionally pick something up to eat in periods of drastic food shortage.

Resources in the wild are accordingly perceived as scarce and available only for small groups of people, and requiring long days of hard work to collect them. And according to the optimal foraging theory which was in vogue three decades ago, their caloric return is often seen as too low to compensate the energy mobilized to collect them.

Foraging activities are perceived as belonging to the past: since it is the principal channel of subsistence for small human groups whose ways of life are about to disappear, foraging is in essence understood as an old-fashioned and anachronistic manner to exploit resources. This being said, there is no obvious need to explore foraging as a means to provide insights for the future, especially with regard to the challenging issue of feeding the fast-growing world population, which is going to approach 10 billion by 2050.

It is also commonly believed that only the last nomadic hunter-gatherers forage. Foraging is thus perceived as antithetic to farming. Foraging versus farming has become a mainstream polarity, an inevitable incompatibility. Along this line, humankind had no other evolutionary choice but to shift from the former to the latter. This dichotomist and simplistic way of approaching foraging is primarily enacted by the long persisting belief that nature must be tamed and submissive. It thus ignores a vast continuum of evolutionary, yet contemporary practices which should not necessarily lead to the full domestication of food resources.

In current times, diet diversification has become the motto of a modern agriculture which is nonetheless responsible for the excessive homogenization of food resources produced worldwide and of the related drop in biodiversity in agricultural landscapes; only 12 plant crops and 14 animal species ensure 98% of world's food needs. This is in stark contrast to the approximately 7,000 plants species and several thousand animal species that have commonly been used for human nutrition and health since the Neolithic.

While cohorts of agronomists and nutritionists have mobilized around the challenge of looking for ways to (re)introduce diversity in today's agricultural systems and educate the poor on how to diversify their dietary regimes to meet their nutritional needs, common sense should incline us to look at past diets and take lessons from how these people -commonly described as poor -could maintain such diversified and rich diets that we are now trying to eagerly reinvent. Foraging activities once contributed significantly to these diversified diets and discouragement of foraging activities, often hastened by government incentives and development planners, have been the cause of impoverishment of these traditional dietary systems. Time has come to dispel the common myths on foraging.

First of all, foraging has persisted among many farming societies and was not an exclusive practice of hunter-gatherers alone. Foraging was, and still is, an integrating component of farming systems, rendering the classical dichotomy between eating from the wild versus cultivating crops and herding cattle inaccurate. For instance, the edible-wild food resource (www.ediblewildfood.com) reminds us that modern agriculture considers several hundreds of plants as "weeds" yet they are in fact strategic constituents of agroecosystems and contribute significantly to local recipes as flavourings, herbs, spices, seasonings, condiments and vegetables. Foraging is not anecdotal and remains essential in the daily life of several hundreds of millions of smallholder farmers throughout the tropics. Swidden or fallow fields and gardens are fertile ground for feral forms of plants (and animals), which foster gene flows between domesticated plants and their wild parents. These flows prevent genetic bottlenecks and maintain a high diversity of usable spontaneous resources along a continuum between wild and domesticated.

Agroforestry systems maintained near homestead areas -for instance home gardens and backyards -are also privileged sites for foraging in permanent components of the agroecosystem in which wild, feral and cultivated individuals are tightly intermingled for the sake of diversity.

Many foraging activities among farming societies are carried out by children. Through these activities, children cover alone a significant part of their diet independently of the meals provided by their parents. In periods of food shortage, food collected by children from the wild are eaten as snacks and may ensure up to 35% of daily food consumption. All the food resources that children pick up from the bush -fruits, frogs, fish, small birds, insects and many others generally considered with disgust by adults or taboo -not only provide calories and nutrients: their harvesting is also a pathway towards education. Children are depositories of the sphere of knowledge that they transmit to each other without the intervention of adults. As such, they are not always this high-risk group that we suspect that they are: in many respects, through the control of foraging activities, they contribute to household economy and food security. However, the academic education system rarely acknowledges this "school of nature" and foraging activities.

One of the major drivers for the domestication of food plants was the reduction of the thermostable compounds that they naturally contain to protect themselves from herbivores. Many food plants that are foraged from the wild require neutralization of the phytochemicals they still contain prior to their consumption. The persistence of foraging activities is pending on the preservation of local ecological knowledge and know-how in the field of food technology in order to ensure the palatability of these resources as well as the diversity of the recipes. Reviving foraging practices over resources that have been long neglected is impossible if the related expertise on how to detoxify them has been lost by lack of transmission from generation to generation.

Many foraged resources are "para"-cultivated in the sense that they mobilize perennial harvesting practices aimed at managing the resource production while maintaining it in their original environment. These procedures are accompanied by social rules protecting the rights of ownership over a supposedly "wild" resource, which is cared for, protected, owned, managed, and eventually inherited as a private possession. Beyond their primary function as food, these paracultivated resources occupy the full status of a cultural good. They sometimes appear in matrimonial payments, prestige dishes and the pharmacopoeia, and they may even play a central role as ritual objects. They not only contribute to nutritional security, they also mediate relationships with the invisible world and the spirits who are seen to exert control over "natural" resources. Paracultivation of foraged resources is much more frequent than we think -it has been reported for instance for wild yams, sago and acai palm trees, honeybee and termite nests, and a few oleoproteaginous seed trees. Foraging clearly illustrates how ecological perspectives should not be separated from cultural aspects, or people's perceptions of their resources.

Edmond Dounias works for the French Research Institute for Development (IRD) and is Senior Research Associate to the Center for International Forestry Research (CIFOR). He is based at the Center for Functional and Evolutionary Ecology (CEFE) in Montpellier (France). His research activities focus on the biocultural interactions between forest dwellers and tropical forests in a context of drastic change, with a particular emphasis on hunting and gathering nomadic societies in the Congo Basin and Borneo. For more information, please contact: edounias@cgiar.org


Joel Ortiz Sosa

Hamza Cedric Killian
email: cedric.killian@inria.fr

Ben Ammar

Daniel Chillet
email: daniel.chillet@inria.fr

Hamza Ben Ammar
email: hamza.benammar@univ-lr.fr

Min/max time limits and energy penalty of communication scheduling in ring-based ONoC

I. INTRODUCTION

High-performance computing systems are generally based on multi-core architectures embedding hundreds of cores on a single chip. The design of such Multi-Processor Systemon-Chip (MPSoC) is very challenging, not only for the computation part, but also for the communication media. Indeed, implementing applications on such architectures results in the different tasks being distributed onto the cores and adding more and more data transfers between these cores. To support these data transfers, a large number of classical Network-on-Chips (NoC) were designed and proposed in the literature [START_REF] Benini | Networks on chips: a new soc paradigm[END_REF]. However, these NoCs suffer from some limitations due to the electrical interconnect characteristics: capacitive and inductive coupling [START_REF] Ho | The future of wires[END_REF], interconnect noise and propagation delay. Thus, new on-chip interconnect solutions are highly desirable to overcome these limitations.

In parallel, recent advances in the integration of photonic on silicon allow the conception of optical NoCs [START_REF] Alexoudi | Optics in computing: From photonic network-on-chip to chip-to-chip interconnects and disintegrated architectures[END_REF] making them good candidates for on-chip communications. This technology provides high bandwidth for data transfers and can be a very interesting alternative to bypass the bottleneck induced by classical NoCs.

Among the different ONoC architectures, Multi-Writer Multi-Reader (MWMR) ONoCs offer the most scalable architectures as the communication medium is shared for the data transfers [START_REF] Wu | Suor: Sectioned undirectional optical ring for chip multiprocessor[END_REF]. This scalability is increased with Wavelength Division Multiplexing (WDM) allowing multiple communications in parallel supporting by different wavelengths [START_REF] Chen | Wavelength assignment in optical network-on-chip: Design and performance[END_REF].

However, as for any shared communication medium, the scheduling of communications is a tough part and clearly impacts the application performance. Hence, the communication scheduling in ONoCs has been addressed to solve different purposes like minimizing the number of wavelengths used in the same portion of a waveguide [START_REF] Cerutti | Fast scheduling based on iterative parallel wavelength matching for a multi-wavelength ring network-on-chip[END_REF], or proposing a trade-off between energy and execution time [START_REF] Luo | Performance and energy aware wavelength allocation on ring-based wdm 3d optical noc[END_REF]. The main difficulty is to propose a method to extract the possible communication scenario to evaluate the trade-off between the execution time of an application and the energy consumption overhead needed to counter the crosstalk induced by using WDM technique.

This paper tackles this topic, providing an optimal solution. Besides, to the best our of knowledge, this study is the first to propose a formal model allowing to compute the optimal time extrema of wavelength scheduling in a ring-based WDM MWMR ONoC with an evaluation of crosstalk overhead.

The rest of the paper is organised as follow. Section II presents the communication scheduling impact on the execution time and the crosstalk power penalty. Section III presents the communication allocation and scheduling formalisation developed to find the different global communication solutions. The crosstalk model used for the evaluation of the crosstalk power penalty is also presented in this section. Section IV presents the results provided by the resolution of the problem. Section V describes the state of the art regarding existing methods to handle channel scheduling in ring based ONoCs. Finally, Section VI concludes this paper.

II. COMMUNICATION SCHEDULING

The key concepts investigated in this paper are illustrated in Figure 1 (the legend is presented in Fig. 1.g). Applications are represented as a Directed Acyclic Graph (DAG) as depicted in Fig. 1.a. In this example, we assume that tasks t 0 , t 1 , t 2 and t 3 are respectively mapped onto processors p 0 , p 1 , p 4 , and p 8 , respectively located in clusters c 0 , c 0 , c 1 and c 2 (see Fig. 1.b). Communications Com 0→2 , Com 1→2 and Com 2→3 are implemented using an ONoC which can be configured according to execution performance and energy requirements. Each cluster is associated with an Optical Network Interface (ONI) containing a Transmitter (Tx) and a Receiver (Rx). The Txs integrate lasers to modulate data, and a Micro Ring (MR) resonator for each laser to inject the optical signal into the waveguide (if the MR is 'on'). The Rxs integrate MR to eject the associated optical signal from the waveguide when the MR is 'on'. Finally, photodetectors allow converting an optical signal into an electrical one. From the simple application given in Fig. 1-a and if we consider a waveguide supporting 4 wavelengths, several communication configurations are possible and the following illustrates three of them:

• Low power configuration Cf g1 : in this configuration, illustrated in Fig. 1.c.1, a single wavelength is allocated to each communication. Wavelengths λ 0 (blue) and λ 3 (green) in T x 0 are allocated for Com 0→2 and Com 1→2 , respectively, and λ 0 (blue) is also used in T x 1 for Com 2→3 . We assume a direct OOK modulation, i.e. no modulator is needed. The signals propagate along the waveguide until they reach their destination: signals from T x 0 at wavelength λ 0 and λ 3 are ejected in cluster c 1 , while λ 0 signal from T x 1 is ejected at c 2 . Since λ 0 is used between c 0 to c 1 to support Com 0→2 , it is reused to implement Com 2→3 between clusters c 1 and c 2 , thus maximizing the wavelength occupation in the waveguide. The Fig. 1.c.2 illustrates the task and communication schedule. Processor p 4 in cluster c 1 starts executing t 2 once all the data have been received from p 0 and p 1 and sends the processed data to p 8 in c 2 . The execution of the DAG in this configuration takes 13 clock cycles. In this example, we assume that the targeted BER is reached for all communi-cations. The Fig. 1.c.3 depicts the power spectrum of signals received at Rx 1 and Rx 2 . The NRZ-OOK modulated signals are represented as cardinal sines, while the filter MRs have Lorentzian filter shapes. For the communications between c 0 and c 1 , the two used wavelengths are the most distant, hence the crosstalk between λ 0 and λ 3 is limited, but the associated lasers must increase a bit the emitting power to compensate the signal degradation, named crosstalk power penalty (see Section III-C for more detail on crosstalk). Regarding the communication between c 1 and c 2 , as only one wavelength is received at Rx 2 , no crosstalk penalty has to be compensated. It is worth mention that the power of laser also needs to compensate for propagation losses (not represented here).

• Intermediate configuration

Cf g2 : for this configuration more bandwidth is allocated for each communication. Com 0→2 , Com 1→2 and Com 2→3 are respectively supported by the wavelength pairs (λ 0 , λ 1 ), (λ 2 , λ 3 ) and (λ 0 , λ 3 ). This allocation leads to a reduction of execution time in 8 clock cycles (see Fig. 1.d.2). However, in Rx 1 , as all wavelengths are used, the crosstalk penalty is at maximum, hence the source lasers have to compensate a strong crosstalk power penalty. Regarding the Rx 2 , as the two used wavelengths are the most distant, the crosstalk power penalty is low.

• Fastest configuration

Cf g3 : for this configuration, the band-

width utilization is at maximum. Compared to Cf g2 , Com 2→3
is supported by the 4 available wavelengths. This allocation leads to the fastest execution of the DAG in 7 clock cycles but provides the hugest crosstalk (see Fig. 1.e.2 and Fig. 1.e.3) which needs to be compensated in each T x. The Fig. 1.f plots the execution time versus the crosstalk energy penalty for each configuration. The previously presented configurations belong to a Pareto front. The configurations Cf g1 and Cf g3 are respectively the two bounds: the slowest and the fastest execution configurations. Based on the complexity of the application, the number of solutions on the Pareto front can be difficult to determine, as well as the front itself. As mentioned in the introduction, numerous methods have been developed to optimise the communication scheduling in ONoC. However, no mathematical formulation has been proposed considering MWMR and multiple wavelengths per communication. Hence, the state of the art solutions require a huge effort to explore all the solutions to determine the Pareto front. This paper tackles this problem and allows us to compute the two extrema solutions of this Pareto front. From these information, the designer can evaluate the optimisation opportunity of the wavelength allocation for a specific application using ONoC.

III. FORMALISATION OF COMMUNICATION SCHEDULING

This section presents the wavelength allocation problem, defined with two optimisation functions to extract the bounds in terms of execution time. From this information, and from the crosstalk model (presented in Section III-C), we compute the energy penalty of each bound, which finally gives us the Pareto front of the wavelength allocation design space.

A. Execution time bounds computation

As previously explained, the objective is to compute the two extrema solutions in terms of execution time. The first one, defined by the fastest execution time, is produced by an optimal wavelength allocation, while the second bound is produced by an allocation with only one wavelength for each communication. In this context, the problem addressed includes wavelength allocation and tasks scheduling. Before modelling the optimisation problem, let's define the following variables:

• T asks = {T i } defines the set of tasks T i to schedule. Each T i is defined by the variables {T s i , T d i , T e i } defined below. • N t is an integer defining the tasks number in the set T asks.

• T d i is an integer defining the execution time of the task T i .

• Clusters = {P j } defines the set of clusters P j included in the architecture. A cluster P j is a set of processors which supports the execution of a subset of T asks.

• ON I = {ON I j } defines the set of Optical Network
Interface ON I j included in the architecture. Each cluster P j has its own ON I j . • Op is an integer defining the number of ONIs.

• Com i,j is a boolean variable defining the communication needs between the tasks. If Com i,j = 1, it means that a communication exists from tasks T i to T j . • Data i,j is an integer variable defining the volume of data transferred from the tasks T i to T j .

• M i is an integer variable defining the task mapping. M i = j means that T i is mapped on the cluster P j . • SC k,Comi,j is a boolean variable equal to 1 if a communication Com i,j travels the waveguide segment S k . A waveguide segment S k is the part of waveguide between two ONIs. Typically, S 1 is the segment between ON I 1 and ON I 2 . Note that the static mapping of tasks (M i ) enables to precompute the values SC k,Comi,j . • N W is an integer variable defining the maximum number of wavelengths supported by the waveguide. • B is an integer variable defining the bandwidth for the transfers of data on one wavelength. • t defines the execution cycles.

All the previous variables define the architecture, the mapping and characteristics of tasks. To complete the optimisation problem definition, decision variables must be defined, they are the following:

• Allocλ i,j is the integer variable defining the number of wavelengths allocated for the communication between tasks T i and T j . • T s i and T e i are respectively the start time and the end time of the task T i .

From these variables, we can define the two optimisation functions providing the execution time bounds. The first optimisation function enables to extract the solution with the minimum execution time for an application. This objective function is given by the following equation:

M in ( max{T ei} ) ∀ Ti ∈ T asks (1)
This expression minimises the end of application execution.

Solving this problem provides a solution with the optimal number of wavelengths allocated in order to reduce the communication times.

The second objective function is necessary to find the maximum execution time, obtained when the number of wavelengths for each communication is equal to 1. This objectif function is defined by:

M in N t i=0 N t j Allocλi,j (2)
For both optimisation functions, three constraints are defined.

• The first constraint, as c 1 (Eq.3), is very simple and formalises the links between the start time, end time and the execution time of a task T i .

c1 : T ei = T si + T di (3)
• The second constraint, given as c 2 (Eq.4), verifies that the start time of task T i is greater than the sum between i) the max of the end times of all the predecessor task T j of T i and ii) the time to transfer the data between the tasks T j and T i . This time depends on the number of wavelengths allocated for the communication, more allocated wavelengths leads to smaller communication time.

c2 : T si = max T ej * Comj,i + Dataj,i Allocλj,i * B ∀ T e j (4)
Note that if there is no communication between tasks T i and T j , T e j * Com j,i + Dataj,i Allocλj,i * B is equal to 0. • The third constraint, given as c 3 (Eq.5), is the more complex part of the problem. This constraint verifies that, for a waveguide segment S k and for a specific cycle t, the sum of wavelengths allocated to support the communications is not greater than the number of wavelengths available in the waveguide. For that, we compute, for each waveguide segment S k , the sum of wavelengths used by each communication travelling this segment at the same time, and this sum must be smaller or equal than the maximum number of wavelengths.

c3 : ∀{k, t} | k = 0, . . . , Op -1

∧ t = 0, . . . , i T ei + j Datai,j B N t-1 i=0 N t-1 j=0 SC k,Com i,j * Comi,j * (T ei < t) * (T sj > t) * Allocλi,j ≤ N W (5)
To describe these two problems, we use the language OPL (Optimisation Programming Language) and Cplex solver to explore the solutions and to extract the bounds of execution times. The two objective functions concern discrete integer decision variables and the optimisation only concerns one objective. Then the problem can be classified as Integer Linear Program.

B. Computation of crosstalk penalty

As the mapping of a task is statically defined and from the scheduling produced by the above optimisation functions, we can compute the crosstalk penalties which appear at each receiver Rx. We consider each communication Com i,j and we compute the number of wavelengths used from transmitter to receiver ONIs of this communication. For that, we extract all the communications travelling at least on one segment of communication Com i,j and for which a time overlap exists. If Com i,j used n wavelengths to support the communication from tasks T i to T j , then each of the n wavelengths is crosstalked with the n -1 other wavelengths, it defines AutoCrosstalk, AC, given by Eq.6. Furthermore, each of these n wavelengths are crosstalked by all the other wavelengths supporting the other communications using the same part of the waveguide and with a time overlapping, it defines InterCrosstalk, IC, given by Eq.7.

ACi, j = Allocλi,j * (Allocλi,j -1) (6)

ICi, j = Allocλi,j * k,l|(k,l) =(i,j) (Allocλ k,l * T imeOverlap(Comi,j , Com k,l ) * SegmentOverlap(Comi,j , Com k,l )) (7)
With T imeOverlap, respectively SegmentOverlap, functions returning 1 if the two communications share at least one communication cycle, respectively one segment of the waveguide. The functions return 0 elsewhere. From these two values that count the number of wavelengths which crosstalk together, we compute the power penalty based on the crosstalk model defined in the next section.

C. Crosstalk model

As introduced in Section II, wavelength crosstalk appears when two wavelengths are close to each other and when an MR extracts power from its own resonant wavelength plus power from the neighbour wavelengths. The signals propagating within the waveguide have cardinal sine shape due to the NRZ-OOK modulation used. We use the model of [START_REF] Bahadori | Crosstalk penalty in microring-based silicon photonic interconnect systems[END_REF] to estimate the crosstalk. In this model, we consider especially: the wavelength frequency of each channel, the frequency spacing between channels, FWMR of MR, and the bit-rate of transmission (please refer to [START_REF] Bahadori | Crosstalk penalty in microring-based silicon photonic interconnect systems[END_REF] for more detail on the model). This model allows us to compute the crosstalk power penalty (XP P ) for each signal. This value is the power compensation at the source lasers that is required to maintain the signal quality (Bit Error Rate) due to wavelength crosstalk. Fig. 2 presents the crosstalk power penalty which impacts each wavelength in presence of all the other wavelengths. These power penalties are computed by considering a constant FSR, 0.8 nm in our case, and with an optimal repartition of wavelengths into the FSR interval. It means that when the waveguide includes only two wavelengths, the FWMR is at the maximum value (equal to FSR), and the crosstalk between the two wavelengths is near 0 dB, while the power penalty is near 4 dB for waveguide including 16 wavelengths and an FWMR equal to F SR/15 = 0.053 nm. For the computation of crosstalk penalty, we consider the maximum value of the power penalty XP P max N w given in the Fig. 2. For example, for a waveguide supporting 16 wavelengths (green curve of Fig. 2), XP P max 16 = 5.2 dB. Finally, the global crosstalk energy penalty (GXEP ) of an application is then computed by Eq.8 which takes account of the communication duration (in cycles) which is the time interval when the laser power must be increased.

GXEP = i,j (ACi, j + ICi, j) * XP P max N w * (T sj -T ei) (8)
As we don't include clock frequency in this equation, the unit of GXEP is given in dB * cycles.

IV. RESULTS

We evaluate our contribution with a set of synthetic task graphs generated with our own task generator. This task generator is very similar to TGFF tool, but it includes communication volume between tasks. For this experimental setup, the parameters used to generate the task graphs are the following: number of tasks from 6 to 12 tasks, parallelism between tasks from 1 to 3 tasks executed in parallel, number of communications from 5 to 20 communications, execution times of tasks from 5 to 10 cycles, volume of communication from 5 to 10. These task graphs are mapped on a 16 cluster architecture with a number of wavelengths varying from 1 to 16 (1, 2, 4, 8, and 16) in the ONoC.

For the example presented in this section, we consider a FSR equal to 0.8 nm and, as mentioned before, an optimal repartition of wavelengths onto this interval. The Fig. 3 and Table I highlight the opportunity of wavelength allocation. In particular, the column "gain" of table I shows the reduction of execution time when the number for wavelengths in the waveguide increases. For example, for the Appli 1 and for 16 wavelengths in the waveguide, the possibility to allocate 16 wavelengths for each communication leads to an execution time reduction from 73 to 48, i.e. which corresponds to 34.2% of reduction. For the example "Appli 5", which corresponds to a larger task graphs with more communications between tasks, the possibility to support greater wavelengths allocation leads to an important reduction in terms of the execution time of the application (from 147 to 85, i.e 42% of execution time reduction).

Fig. 4 presents the limits of the Pareto fronts for the application 2 (the same type of curves can be observed for the other task graphs), and for a number of wavelengths available in the waveguide varying from 1 to 16. This figure clearly shows that increasing the number of wavelengths in a waveguide has a great impact in terms of energy penalty, due to wavelengths crosstalks between communications.

Furthermore, this figure also shows that increasing the number of wavelengths in a waveguide as no real impact in terms of execution time if WDM is used only between communications (see the line "Allocation of 1 wavelength per communication"). It means that WDM must be considered not only to parallelise communications with each other, but also to parallelise each communication.

Finally, from the design space exploration point of view, our proposal enables to extract the bounds in terms of execution times and also enables to evaluate the energy penalty induced by crosstalk between wavelengths when using WDM technique. As discussed in the introduction section, these results give a global overview of the wavelengths allocation design space, and can help the designer to select the appropriate wavelength allocation for the ONoC.

V. RELATED WORKS

The wavelength allocation has been first considered as an optimisation problem where each communication message is assigned to only one wavelength [START_REF] Cerutti | Fast scheduling based on iterative parallel wavelength matching for a multi-wavelength ring network-on-chip[END_REF]. The objective function and the set of constraints ensure the maximum throughput by spatially sharing the wavelengths between different communications. However, this work does not benefit from multiple wavelengths per communication to speed up applications. In [START_REF] Gu | Mronoc: A low latency and energy efficient on chip optical interconnect architecture[END_REF], the authors propose a Multiple Ring-based Optical NoC and a wavelengths assignation based on WDM is used to reduce the contention during communication and to simplify the control of the NoC. In [START_REF] Koohi | All-optical wavelength-routed architecture for a power-efficient network on chip[END_REF], the authors propose to use WDM technique through deterministic routing algorithm to eliminate the need for resource reservation. The ONoC is then shared for different communications, but a pair of sender and receiver uses only one wavelength for the data transmission. In the paper [START_REF] Uscumlic | The impact of network design on packet scheduling in slotted wdm packet rings[END_REF], the authors compare the complexity of For specific communication needs, i.e. broadband communications, the authors of [START_REF] Biberman | Broadband operation of nanophotonic router for silicon photonic networks-on-chip[END_REF] take advantage of WDM to support data channels on multiple parallel wavelengths, in order to distribute the information to several receivers.

In [START_REF] Xie | Crosstalk noise analysis and optimization in 5x5 hitless silicon-based optical router for optical networks-on-chip (onoc)[END_REF], the impact of crosstalk in ONoC is studied and a generic approach is defined to model crossing angles equals to 60°and 120°rather than conventional 90°crossing.

In [START_REF] Luo | Performance and energy aware wavelength allocation on ring-based wdm 3d optical noc[END_REF], the authors have developed a genetic algorithm to explore the design space of communication management in the context of WDM technique. The technique is an evolution of the ORNoC proposed in [START_REF] Beux | Optical ring network-on-chip (ornoc): Architecture and design methodology[END_REF]. The algorithm provides a set of large number of solutions and a Pareto Front can be extracted from this set, but due to the genetic algorithm progress, bounds of the design space can be missed. Furthermore, the time to extract the set of solutions can be very high even if the design space is small.

VI. CONCLUSION

Due to its intrinsic features, Wavelength Division Multiplexing in the ONoC domain is an interesting opportunity to offer very high bandwidth for the data transfers between cores and/or clusters of cores. While this technique is generally used to ensure several communications in parallel on the same waveguide, WDM also enables to use several wavelengths for the same communication. However, this technique induces crosstalk between wavelengths when they are used at the same time on the same part of waveguide. Then exploring the design space of wavelength allocation is a difficult task for the designer. To tackle this problem, this article presents a mathematical formulation to extract the limits of Pareto front in terms of execution time versus crosstalk energy penalty.

Two mathematical formulations are defined, one for each limit of the Pareto front, and a set of constraints ensuring the temporal scheduling of tasks and the spatial and temporal distribution of communications onto the ONoC. From this mathematical formulation, we demonstrate that our proposal can help the designer during the design space exploration by highlighting the optimisation opportunity in terms of execution time of his application, but it also gives information about the energy overhead needed to improve the performance.

VII. ACKNOWLEDGEMENT

Fig. 1 .

 1 Fig. 1. Global concept of communication scheduling for Optical Network on Chip.

Fig. 2 .

 2 Fig. 2. Crosstalk power penalty repartition for each signal of a Nw wavelengths receiver.

Fig. 3 .

 3 Fig. 3. Execution times comparison for min vs max wavelength allocation.

Fig. 4 .

 4 Fig. 4. Limits of Pareto fronts for application 2 (task graph 2).

Cfg 2 Cfg 3 Cfg 1

		t 0	p 0	ONI 0 p 1	t 1	t 0 t 1	t 2 Com 0à2 Com 2à3 Com 1à2 t 3 ONI 1 p 4 p 5 t 2	t 3	p 8	ONI 2 p 9																	Crosstalk Energy Penalty
			p 2	p 3	c 0		p 6	p 7	c 1			p 10	p 11	c 2																t 1 … t 6 t 7 t 8 t 9 t 10 t 11 t 12 t 13 Execution time
	c 0	Tx 0				Rx 1	c 1	Tx 1						Rx 2	c 2	c 0	Tx 0			Rx 1	c 1	Tx 1			Rx 2	c 2	c 0	Tx 0			Rx 1	c 1	Tx 1	Rx 2	c 2
																														t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10 t 11 t 12
	Rx 1						Rx 2									Rx 1					Rx 2						Rx 1				Rx 2
			λ 0	λ 1	λ 2	λ 3	λ signal		λ 0	λ 1		λ 2		λ 3	λ signal		λ 0	λ 1	λ 2	λ 3	λ signal	λ 0	λ 1	λ 2	λ 3	λ signal		λ 0	λ 1	λ 2	λ 3	λ signal	λ 0	λ 1	λ 2	λ 3	λ signal
		Low crosstalk power penalty	No crosstalk power penalty			Strong crosstalk power penalty		Low crosstalk power penalty			Strong crosstalk power penalty	Strong crosstalk power penalty

978-1-7281-9151-5/20/$31.00 2020 European Union

Com 1à2 t 1 Com 0à2 t 0 t 13

	Com 2à3	t 2	t 4
	t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10 t 11 t 12

Com 1à2 t 1 Com 0à2 t 0 t 13

	Com 2à3	t 2	t 4
			t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10 t 11 t 12

Com 1à2 t 1 Com 0à2 t 0 t 13 Com 2à3 t 2 t 4 Cfg2 Cfg3 Cfg1 On-chip laser with direct modulation for λ x ON

	OFF	Crosstalk power compensation
		Low	Medium	High

Photodetector ON Add-Drop filter for λ x OFF ON OFF Power Spectrum of NRZ-OOK modulation on λ x

	λ 0	λ signal	λ 0	λ signal

Drop lorentzian filter shape for λ x ONI m t i Task i Com iàj Com. i to j p n Proc. n c k Cluster k Optical Network Interface m Optical waveguide

	a)	g)	f)
	b)
	c.1)	d.1)	e.1)
	c.2)	d.2)	e.2)
	c.3)	d.3)	e.3)

TABLE I EXECUTION

 I TIME COMPARISONS BETWEEN MONO WAVELENGTH ALLOCATION AND MULTI WAVELENGTHS FOR EACH COMMUNICATION.

	Applications	(# tasks, # comm)	1 WL		2 WL			4 WL			8 WL			16 WL
			1 wl	1 wl	1..2 wl	gain %	1 wl	1..4 wl	gain %	1 wl	1..6 wl	gain %	1 wl	1..8 wl	gain %
	Appli 1	(6, 5)	82	73	63	13.7	73	55	24.7	73	50	31.5	73	48	34.2
	Appli 2	(8, 11)	160	111	101	9.0	98	76	22.4	98	66	32.6	98	63	35.7
	Appli 3	(10, 18)	196	128	121	5.5	112	86	23.2	112	80	28.5	112	73	34.8
	Appli 4	(12, 18)	219	161	143	11.2	153	114	25.5	153	99	35.2	153	90	41.2
	Appli 5	(12, 20)	225	158	139	12.0	147	105	28.6	147	89	39.4	147	85	42.2
	Average gain		-			10.2			24.9			30.8			34.2
	Waveguide configuration:		# WL: Nb of wavelengths available on the waveguide
				#..# wl: range of possible wavelengths allocated for each communication
	different solutions for the schedule of packets on WDM ring
	topology. The solution considers time-slotted allocation for the
	wavelengths, and different policies are considered This work
	proposes to split the message to reduce the design cost.

This work benefited from the support of the projects SHNoC ANR-18-CE25-0006, Opticall2 ANR-18-CE24-0027 and COMIN Labs excellence laboratory ANR-10-LABX-07-01 of the French National Research Agency (ANR).