# Max-min Fairness Based Faucet Design for Blockchains

Serdar Metin<EMAIL_ADDRESS>Can Özturan<EMAIL_ADDRESS>Boğaziçi University, Bebek, İstanbul, Turkey

###### Abstract

In order to have transactions executed and recorded on blockchains such as the
Ethereum Mainnet, fees expressed in crypto-currency units of the blockchain
must be paid. One can buy crypto-currency called Ether of the Ethereum
blockchain from exchanges and pay for the transaction fees. In the case of
test networks (such as Rinkeby) or scientific research blockchains (such as
Bloxberg), free crypto-currency, Ether, is distributed to users via faucets.
Since transaction slots on the blocks, storage and smart contract executions
are consuming blockchain resources, Ethers are distributed by fixed small
amounts to users. Users may have different amount of Ether requirements; some
small amounts and some large amounts during different times. As a result,
rather than allowing the user to get a fixed small amount of Ether, a more
general distribution mechanism that allows a user to demand and claim
arbitrary amounts of Ether, while satisfying fairness among users, is needed.
For this end, Max-min Fairness based schemes have been used in centralized
settings. Our work contributes a Max-min Fairness based algorithm and its
Solidity smart contract implementation that requires low transaction costs
independent of the number of users. This is important on the Ethereum
blockchain, since a smart contract execution with transaction costs depending
on the number of users would mean block gas limit exhaustion problem will
eventually be met, making the smart contract ineffective. We report tests
which confirm that the low transaction cost aims have been achieved by our
algorithm.

###### keywords:

Blockhain , Faucet , Max-min Fairness , Resource Allocation

††journal: arXiv.org

##  1 Introduction

Since its conception in 2008 with Bitcoin [1], blockchain technologies have
been the focus of much attention. Although successful at achieving its
initially proposed purpose of providing a peer-to-peer electronic cash system,
Bitcoin was conceived as an autonomous global currency with guaranteed
scarcity, and as such, offered limited programmability and functionality. The
designers of the following generation of blockchain systems mainly
problematised this point and endeavoured on expanding blockchain capabilities.
With the introduction of smart contracts by the Ethereum [2], the blockchain
technology met Turing-complete programming functionalities.

Our work aims to address a recurrent question in computer science, within the
blockchain context: the fair allocation of shared resources. We focus on the
fair allocation of intrinsic resources of blockchains. Since a blockchain is a
distributed ledger, operated in a distributed manner, the ability to operate
on the blockchain (e.g. executing a transaction or a smart contract function,
or deploying a smart contract) is a shared, limited resource. We look at the
fair allocation of this resource.

In the Ethereum blockchain ecosystem that offers smart contract functionality,
the resource usage mentioned above are quoted in terms of gas, which refers to
the cost necessary to perform a transaction on the blockchain. The gas is
priced using the blockchain’s intrinsic crypto-currency, called Ether in the
case of Ethereum. Hence, just like a number of litres of petrol (priced as USD
per litre) is needed in order to have a car travel a number of kilometers, a
number of gas units (priced as Ether per gas unit) is needed to execute a
number of instructions in a blockchain transaction. Thus, the problem
collapses down to the distribution of the system’s intrinsic crypto-currency.
In commercial public networks like Ethereum Mainnet, the distribution process
relies on the competition to create new Ether units of the blockchain
currency, and the trading of the already generated Ethers. However, on test
networks such as Rinkeby or scientific research blockchains such as Bloxberg
[3] alternative Ether distribution mechanisms are used.

A faucet is one such mechanism, which offers free currency to users according
to some predefined policy. In general, faucets offer a fixed amount of
currency for a given time period or block span. For example, Bloxberg
blockchain provides 0.2 Ethers via its web based faucet [4]. However, this
mechanism can be exploited simply by making recurrent requests and
accumulating the obtained currency. For this reason, it cannot be accounted
for as a fair distribution scheme. Max-min Fairness [5, 6] is a distribution
scheme that is widely employed in different contexts where fairness is a
system requirement (e.g. cpu scheduling, bandwidth allocation etc.), and it
can also be considered for the fair distribution of currency in faucet
systems.

On the Ethereum blockchain, the size of each block is bound by a maximum
amount of gas that can be spent per block. This upper bound on the gas amount
is known as the block gas limit. A contract function will not be able to
execute if its gas cost exceeds the block gas limit. We refer to this problem
as the block gas limit exhaustion problem. Hence, smart contract functions
should be designed and implemented in such a way that their execution does not
consume too much gas which may lead to block gas limit exhaustion problem. If
gas limit is reached, it will simply mean the contract function cannot be
executed which in turn may mean the smart contract can no longer operate
properly.

In this work, we first implement Max-min Fairness algorithm in the blockchain
context as a smart contract, as it is originally implemented in centralized
systems. After demonstrating the shortcomings of this implementation in the
blockchain context (i.e. block gas limit exhaustion problem), we contribute an
algorithm that actuates the Max-min Fairness scheme in the blockchain context
without running into the original implementation’s shortcomings. We name our
algorithm Autonomous Max-min Fairness (AMF), since it is operated autonomously
by the users in the system, as opposed to the original algorithm, in which the
distribution operation is done centrally by an authority. Figure 1 illustrates
the operations of centralised and authority driven faucet smart contract
implementation in (a) and autonomous and decentralised implementation driven
by crowds of users in (b). In the former scenario, the distribution is done
with a single call to the distribute function by the authority node in the
beginning of the epoch, whereas in the latter the users make multiple calls to
the claim function throughout the epoch in order to obtain their own share.

Figure 1: The call sequences of the (a) Authority driven faucet, and (b)
Autonomous faucet (driven by crowds of users), in a distribution cycle. Blue
arrows indicate low-cost transactions (demand and claim), and red arrow
indicates a high-cost transaction (distribute).

We further extend the study to a weighted version of Max-min Fairness scheme,
in which case the users are assigned weights for their respective shares,
according to some prioritisation policy. In the tests we run, the weight of
each user’s share is defined to be the reciprocal of the total demand volume
of the user, up to and including the then present demand. By discouraging
unnecessary demands, this policy leads to higher sharing incentives among
users. Moreover, it secures fairness of distribution in the long run, since
latter allocations are mediated with the former demands of a given user. We
name this algorithm Weighted Autonomous Max-min Fairness (WAMF).

The remainder of the article is organised as follows: In the next section, we
review the literature on related work. Having laid out the background on
blockchain studies, in Section 3 we state our problem in the light of the
observations from Section 2. We continue with a section where we justify our
design decisions concerning the experimentation environment. Following that,
in Section 5 the Max-min Fairness scheme and its adaptation to the present
context is explained. In Section 6, the implementation details are laid out.
Once the implementation is explained, the results of the experiments are given
in Section 7. We discuss the results in Section 8, and conclude the article in
Section 9 with the prospects of possible follow-up studies.

##  2 Related Work

Blockchain technologies have been proposed for a number of user applications
(e.g. [7, 8, 9]), and also for background services (e.g. [10, 11]).

By the introduction of tokenised economies, blockchain systems are rendered
capable of governing allocation and trade of resources [12]. A token is a data
structure with certain attributes and operations defined on them, serving for
representing items or value. The first two standards that are developed for
token economies are ERC$20$ and ERC$721$, which define divisible and non-
divisible, or as they are so called, fungible and non-fungible tokens,
respectively. Although compatible with our setting, for reasons of simplicity
we did not use token standards in our implementation.

In many areas in computer science where the problem of distributing shared
resources is encountered, Max-min Fairness [5, 6] has been considered a fair
method [13, 14]. It is also the main method employed in the present study.

The question of fair sharing first arose in the context of operating systems,
where scheduling the resources of a single computer (e.g. processor time)
among processes was the main problem [15]; followed by the problem of
distributing the same resources among users [16], typically at the computer
centres of universities. Similar problems are addressed in the computer
networks literature over the allocation of link bandwidth [17, 13]. Fair
scheduling algorithms have also been the focus of attention in grids [18].

With the advancements in distributed systems, and new paradigms in cluster and
high-performance computing, the problem of fairness evolved yet to larger
scales, and new questions arose. In this context, typically, service providers
charge users for the common resource that is demanded by, and allocated to
them. The same question is now expressed in terms of charging fairness: how
much should each demand cost, for it to be fair among clients [19] ? Should
each type of resource cost the same, and if not how are they traded [20] ?

##  3 Problem Statement

As indicated in Section 2, the criteria for fair allocation is intimately
related with the context the problem is situated in. A number of observations
that stand out to be relevant are as follows:

###  3.1 Abstraction for Demands: The level at which distribution is done

As observed in Section 2, the allocation may be done at process-level [15],
user-level [16], or group-level [21]. The faucet system that we contribute is
designed so as to provide fair distribution of internal currency among users,
with the assumption that the users are identified and registered for making
demands. Therefore, the abstraction for the demands are at the user level.

###  3.2 Abstraction for Resources: The number of resource types and their
relationship with each other

If the resources are abstracted to be homogeneous, the main problem is pricing
a unit resource [19]. On the other hand, if more than one type of resources
abstracted, the problem should be extended as to address how they are traded
among each other [20].

A key factor for determining the price of a cryptocurrency is its by then
present and ultimate total supply [22]. In the system we developed, the growth
of the total supply is predefined by an immutable policy, securing the ground
for a calculable and predictable pricing mechanism. Since the domain we
restricted the present study into is non-commercial blockchain systems,
pricing here does not refer to monetary pricing, but rather the cost of
operations in terms of intrinsic cryptocurrency.

For simplicity, abstraction for the resource is kept at single resource type,
which is the intrinsic currency of the blockchain ecosystem, which in our case
is the Ether cryptocurrency. With Ether, a user can pay for storage as well as
execution cost of smart contract functions on the Ethereum blockchain,
providing the basis for a unified resource type.

###  3.3 Temporal Granularity: The frequency at which the allocation procedure
takes place

For addressing this issue, the blockchain is divided into epochs, which we
define as a constant number of successive blocks. According to the original
Max-min Fairness algorithm, the distribution should be done at the beginning
of each epoch, which we implemented as such. In the algorithms we develop, we
also expand the allocation procedure over the whole span of the epoch, to be
decentrally carried out by users, in the so called claim rounds. The temporal
setting will further be described in Sections 6 and 7.

##  4 Design Decisions on the Experimentation Environment

Although there are a number of design decisions for setting up a blockchain
system to carry out experiments on, one key factor is the proof scheme
employed in the consensus protocol. In the present study, the experiments are
carried out on the Parity implementation of a permissioned Ethereum blockchain
[23]. The main concern for this choice is to decouple two independent, yet
intertwined questions specific to the blockchain environments. Blockchains are
a means both for decentralisation, and for securing digital trust. By
decoupling these two questions and allowing to concentrate on decentralisation
premise, permissioned blockchains are ideal experimentation environments for
blockchain operation analysis. Let us elaborate on that.

Various proof schemes, employed in blockchains’ consensus protocols,
necessitate different trust assumptions, and equivalently, offer different
levels of digital trust to the ecosystems they are embedded in. If one
imagines proof schemes on a scale for their provision of trust, Proof-of-Work
(PoW) blockchains reside on one extreme, since they assume no preliminary
digital trust, and provide all the digital trust needed via their operation.
For this reason they are referred to as trustless computation environments, in
the sense that no prior trust is needed among the users to be involved in the
operation of the ecosystem. Initial blockchains such as Bitcoin [1] and
Ethereum [2] employ PoW based consensus protocols.

Although they can operate stand-alone trust-wise, PoW blockchains expend
enormous physical resources (e.g. electricity, processing power) and their
operation is costly. Other proof schemes were proposed to replace PoW in order
to eliminate these costs. These schemes provided different levels of trust,
compensated by extra-digital measures to different extents, inversely
proportional with the former. Among these are: Proof-of-Space [24], Proof-of-
Stake [25, 26], Proof-of-Prestige [27], Proof-of-Activity [28], Proof-of-
Useful-Work [29], with different utilities and limitations they bear.

Proof-of-Authority (PoA) blockchains, residing on the other extreme, provide
no trust via their operation, and rely solely on extra-digital measures (e.g.
reserve the right to operate on the blockchain only to trusted parties) to
secure trust.

The trust structure described above for PoA is equivalent to the trust
structure of the conventional computation environments, which is referred to
as Pretty Good Privacy (PGP) trust chain [30]. The PGP scheme secures trust
with the assumption of the presence of a trust anchor, a party that can be
unconditionally trusted, and from that point, other parties are trusted either
by the direct reference of, or by a chain of references rooted at the trust
anchor. In the PoA setting, authority nodes act as trust anchors.

We implemented our algorithms in Solidity programming language and run on an
Ethereum Virtual Machine (EVM) environment [31], and more specifically, its
Parity implementation, as mentioned above. The main reason for selecting this
framework is its wide use among blockchain ecosystems. Many blockchain
ecosystems and blockchain based systems utilise either EVM or virtual machines
similar to EVM, and support Solidity programming language for smart contracts
(e.g. [32, 33, 34, 35] etc.), and for this reason there are also studies
available on the performance [36], security [37], and inspection [38] of the
programming language. Not only is it a widespread programming language,
Solidity is also Turing complete [2], which makes it well suited for general
purpose computations. It is a high-level, easy to read, object oriented script
language.

A number of smaller design decisions are taken concerning the parameters of
Parity Ethereum Virtual Machine and the procedure of the experiments, which is
left to be discussed in Section 7, since their explanation relies occasionally
on the implementation of the algorithms we present.

##  5 Max-min Fairness Model

The main objective of the Max-min Fairness scheme is to maximise the minimum
share given to a user, and its mechanism is based on a trivial fairness
scheme, where resources are uniformly distributed among the demanders, each
one of the $n$ demanders obtaining $\frac{1}{n}$ of the resource. Max-min
Fairness improves the trivial scheme on the premise that not every demander
would demand as much as the share that is reserved for them. Accordingly, the
Max-min Fairness allocation algorithm takes recursive iterations over the list
of demanders, reallocating unused shares of the underdemanders among the
overdemanders.

In the first iteration, starting with the smallest demand and proceeding in
the ascending order, the algorithm allocates the demanders the minimum of
$\frac{1}{n}$ of the capacity ($c$) and their demands (i.e.
$\min\\{\frac{c}{n},d_{u}\\}$). At the end of the first iteration, some
demanders are fully supplied, and some capacity is left over. The algorithm,
in turn, proceeds with updated $n^{\prime}$ and $c^{\prime}$, until either all
demands are fully supplied, or the capacity is depleted.

DemandHeap $0$DemandHeap
$1$SuppliedLeftoverDemandLeftoverDemandUserDemandsLeftoverCapacity Figure 2:
The operation of Max-min Fairness Algorithm

The operation of the scheme can be seen in Figure 2, and its pseudo-code in
Algorithm 1. In the pseudo-code the demand heaps are denoted by $D_{0}$ and
$D_{1}$, and individual demands in these heaps are represented by lower case
letters, subscripted with $u$, for user id number (i.e. $d_{u}$).

The balances of users are kept in a vector, and the balance of user $u$ is
represented with $b_{u}$. At each iteration, the maximum available amount to
be allocated to each user is recalculated by dividing the remaining capacity
by the number of remaining demands, and denoted by $s$, representing the unit
share.

To illustrate the operation of the algorithm we may consider the following
example: Suppose that a resource of $30$ units will be shared among three
users, with the demands expressed as $<$$4,11,15$$>$. The algorithm
distributes the resource in $3$ iterations. The rounds and the shares assigned
in each round can be seen in Table 1.

| User $1$ | User $2$ | User $3$ | Share | Capacity
---|---|---|---|---|---
Demands | $4$ | $11$ | $15$ |  | $30$
Iteration $1$ | $4$ | $10$ | $10$ | $10$ | $6$
Iteration $2$ | $0$ | $1$ | $3$ | $3$ | $2$
Iteration $3$ | $0$ | $0$ | $2$ | $2$ | $0$
Total | $4$ | $11$ | $15$ |  |
Table 1: An exemplary distribution according to Max-min Fairness scheme

How the unsatisfied demand, or the leftover capacity will be treated after a
distribution period is a decision of policy. In our current work, we implement
a policy that discards all the unsatisfied demands, in the case of capacity
depletion, and transfers the leftover capacity to the next distribution
period, in the case of satisfying all the demands.

The amount that is reserved for each epoch is denoted by $C$. We call this
amount the epoch capacity, and in the present study, we took it to be
constant. The actual amount that is distributed in an epoch is denoted by $c$,
and it is at least as much as $C$, since it is added to $c$ at the beginning
of each epoch (i.e. Algorithm 1 line $2$).

In Algorithm 1, the lines $4-20$ constitute the main, or outer loop of the
algorithm, which is responsible for repeating the inner loop (lines $10-18$)
until either the demands or the capacity is depleted. It starts with
calculating the share (lines $5-9$), and then starts the inner loop. Once the
proceeding of the inner loop is completed, the demand heaps exchange their
functions (line $19$) and the outer loop takes another iteration.

The inner loop accounts for iterating on and processing the demands in the
active heap. In line $11$ the demand volume and the user id at the root of the
heap is read into a variable and deleted from the heap. After that the minimum
of user demand and unit share (i.e. $\min\\{\frac{c}{n},d_{u}\\}$) is assigned
to the user in lines $12-14$. The control structure in lines $15-17$ checks
whether the demand is fully satisfied. If not, the leftover demand is inserted
to the heap with the user’s id (line $16$) to be processed in further
iterations.

Another version of Max-min Fairness is weighted Max-min Fairness, in which
case the users are weighted over some predefined policy, and the shares are
calculated with the weights assigned to each user, individually. In this
version, instead of the number of demands, the total capacity is divided by
the total weight in order to calculate the unit share ($s$). In turn, the user
share ($s_{u}$ for user $u$) is calculated for each user by multiplying the
unit share with the user’s weight. The users are allocated the minimum of
their demands, and their individually assigned user shares.

Symbol |  Meaning
---|---
$C$ |  Amount of resource that is added to the existing capacity at every epoch, $C\in\mathbb{Z}^{+}$
$D_{i}$ |  Set of demand heaps, $i\in\\{0,1\\}$
$U$ |  Set of users $u\in\\{u_{1},\ldots,u_{n}\\}$
$c$ |  The existing capacity, initialised at $0$, incremented by $C$ at every epoch
$s$ |  Unit share
$u$ |  User $u$, $u\in U$
$d_{ui}$ |  Demand of user $u$ stored on heap $D_{i}$
$b_{u}$ |  Resource balance of user $u$, $b_{u}\in\mathbb{Z}^{\geq 0},u\in U$
Table 2: Symbols used in CMF (Algorithm 1) and their meanings

1 Function: Distribute(_$D,U,c$_)

2 $c\leftarrow c+C$;

3 $i\leftarrow 0$;

4

5while  _$D_{i}.size() >0$ and $c>0$_ do

6 if  _$c <D_{i}.size$_ then

7 $s\leftarrow 1$ ;

8 else

9 $s\leftarrow\left\lfloor\frac{c}{D_{i}.size}\right\rfloor$ ;

10 end if

11

12 while  _$D_{i}.size >0$ and $c>0$_ do

13 $(d_{ui},u)\leftarrow D_{i}.delMin()$;

14 $a\leftarrow\min{(s,d_{ui})}$;

15 $b_{u}\leftarrow b_{u}+a$;

16 $c\leftarrow c-a$;

17 if  _$d_{ui} >s$_ then

18 $D_{1-i}.insert(d_{ui}-s,u)$;

19 end if

20

21 end while

22 $i\leftarrow 1-i$;

23

24 end while

25return;

Algorithm 1 Max-min Fairness (CMF)

Accordingly, the formula for calculating the unit share $s$ is:

$s=\frac{c}{\sum_{j=1}^{n}w_{j}}$

and the user share $s_{u}$ is given by:

$s_{u}=w_{u}\cdot s=w_{u}\cdot\frac{c}{\sum_{j=1}^{n}w_{j}}$

We develop autonomous algorithms called AMF (unweighted version) and WAMF
(weighted version) for actuating the Max-min Fairness scheme. In WAMF, the
weights are defined to be the reciprocals of the total amount of demands users
have made up to the distribution time. This aims at incentivizing users to
make minimal demands suitable to their needs, in order not to be
disadvantageous in the long run. The implementation details of WAMF algorithm,
as well as its pseudo-code is presented in Section 6.

##  6 Implementation

The conventional setting to utilise Max-min Fairness typically includes a
central unit (either an individual process running on a central processor or a
dedicated administrative host in a computer network) calculating the shares
and carrying out the iterative assignments. This is applicable to the
blockchain context, but not without potential drawbacks. The main bottleneck
in such an adaptation is the block gas limit, which imposes an absolute upper
bound for the number of operations that may take place within the processing
of a single block. For this reason, we implemented two algorithms and compared
them. The implementations are available at [39]

The first algorithm is the Conventional Max-min Fairness (CMF). This algorithm
is implemented as if it operates in the conventional computational setting.
The demands are collected for a given time period or block span, which is
referred to as an epoch in this study. At the beginning of the following epoch
these demands are supplied resources in the Max-min Fairness order by a single
node (typically an authority node) in one step with the distribute function.

In the second algorithm, the demands are collected in a given epoch, and the
demanders claim their reserved share by calling a claim function in the claim
rounds of the following epoch. We call this approach Autonomous Max-min
Fairness (AMF), since there is no need for a central node to carry out the
execution, and the system is operated autonomously by its users. The operation
of AMF emulates the original algorithm identically, except for the last
iteration where the distribution is in the first come first served order among
overdemanders. Originally, the last iteration is in the ascending order of
demand volumes, as are all the preceding iterations.

We implemented both unweighted as well as the weighted versions of Max-min
Fairness for the AMF. The reason for not implementing a weighted version of
CMF is due to its gas cost structure (elaborated on in Section 7.1). In the
following subsections we give the implementation details of the algorithms.

###  6.1 Conventional Max-min Fairness

As it is in the conventional setting, CMF utilizes two min-heaps, exchanging
the demands among each other in each iteration. The operation scheme and the
pseudo-code is the same as it is described in Section 5 (i.e. Figure 2 and
Algorithm 1).

Since Solidity does not offer a built-in data structure for min-heaps, we
implemented it during the development of CMF. We kept the implementation of
the min-heap minimal in order to keep the gas cost at minimal. Only the amount
of demand, and the id (i.e. unique user number given to each user) of the
demanding user is stored and operated on. The remainder of the user attributes
are fetched from other data structures when needed (e.g. while writing to user
balance), by using the user id as the key.

We used an array implementation of heap, a complete binary tree, where the
values are kept in a node array and the insert and delete minimum functions
are implemented so that they index and move the nodes according to the min-
heap organisation. This is also immune to degeneration attacks, in which case
an attacker feeds the tree with selective input to make one branch grow
disproportionately, forcing heap functions run in $\mathcal{O}(n)$ instead of
$\mathcal{O}(log(n))$ time.

We present the performance of CMF, as well as the min-heap, in Section 7.1.

###  6.2 Autonomous Max-min Fairness

In AMF, the epochs are divided into claim rounds. At the end of each round,
the remaining number of demands, the remaining capacity, and the resulting
share is recalculated. The rounds proceed in this manner until either the
capacity is depleted, or all demands are supplied. The rounds are used to
emulate the iterations of the outer loop (lines $4-20$ of Algorithm 1) of the
distribute function.

In order to avoid repetition, we give the pseudo-code only for the weighted
version (WAMF), since it is more general as compared to the unweighted version
(AMF), the latter being the same algorithm with fewer steps. The pseudo-code
of WAMF is presented in Algorithm 2. The symbols for the additional variables,
and their meanings are given in Table 4. The calculation of weights is
obscured from the pseudo-code for the ease of review, and the weights are
simply shown as constant variables. The calculation of weights is described in
detail in the next subsection.

In AMF, instead of a single-handedly operating distribute function, there is a
claim function, which after necessary checks, allows the user assign her
allocated share to herself. Each user is expected to execute the function
individually, to have carried out the iterations of the inner loop of the
distribute function (lines $10-18$ of Algorithm 1), in a decentralized manner.

Any share unclaimed in its due round/epoch is lost. It is included in the
following round/epoch as part of the leftover capacity. In a given epoch,
users may make new demands for the next epoch, while claiming their share for
the previous. The time frame can be traced in Table 3 over the demands and
corresponding claims, and can be seen more explicitly in Figure 3.

| User 1 | User 2 | User 3 | Share | Capacity
---|---|---|---|---|---
| Demand 1 | 4 | 11 | 15 |  |
| Round 1 |  |  |  |  |
Epoch 1 | Claim 0 | Round 2 |  |  |  |  |
|  | Round 3 |  |  |  |  |
| Demand 2 | 11 | 3 | 8 |  | 30
| Round 1 | 4 | 10 | 10 | 10 | 6
Epoch 2 | Claim 1 | Round 2 |  | 1 | 3 | 3 | 2
|  | Round 3 |  |  | 2 | 2 | 0
| Demand 3 | 7 | 8 | 12 | 10 | 30
| Round 1 | 10 | 3 | 8 | 10 | 9
Epoch 3 | Claim 2 | Round 2 | 1 |  |  | 9 | 8
|  | Round 3 |  |  |  |  |
| Demand 4 | 17 | 13 | 5 |  | 38
| Round 1 | 7 | 8 | 12 | 12 | 11
Epoch 4 | Claim 3 | Round 2 |  |  |  |  |
|  | Round 3 |  |  |  |  |
| Demand 5 | .. | .. | .. | .. | 41
| Round 1 | 13 | 13 | 5 | 13 | 10
Epoch 5 | Claim 4 | Round 2 | 4 |  |  | 10 | 6
|  | Round 3 |  |  |  |  |

Table 3: An exemplary distribution carried out with AMF

Epoch-3Demand-1Demand-2Claim-1Epoch-1Epoch-2…Claim-3Demand-4Epoch-4…Claim-4Epoch-5Claim-2Demand-3Time

Figure 3: Time frame for the matching demand and claim function calls

Symbol | Meaning
---|---
$C$ | Amount of resource that is added to the existing capacity at every epoch, $C\in\mathbb{Z}^{+}$
$B$ | Current block number
$O$ | The block number at which the contract was deployed, offset
$E$ | Epoch number
$R$ | Round number
$RE$ | Reset epoch, the epoch at which the total weight was last reset
$ES$ | Number of blocks in an epoch, epoch span
$RS$ | Number of blocks in a round, round span
$U$ | Set of users $u\in\\{u_{1},\ldots,u_{n}\\}$
$W_{i}$ | Total weight for even and odd epochs, $i\in\\{0,1\\}$
$a$ | Demand volume, amount
$u$ | User $u$, $u\in U$
$d_{ui}$ | Demand of user $u$ in list $i$, $i\in\\{0,1\\}$
$de_{ui}$ | The last epoch user $u$ made a demand, $i\in\\{0,1\\}$
$ce_{u}$ | The last epoch user $u$ made a claim
$cr_{u}$ | The last round user $u$ made a claim
$b_{u}$ | Resource balance of user $u$, $b_{u}\in\mathbb{Z^{+}}$
$w_{u}$ | Weight of user $u$
$c$ | The existing capacity, initialised at $0$, incremented by $C$ at every epoch

Table 4: Symbols used in Algorithm 2 and their meanings

In AMF the demands are kept in a map, rather than a min-heap, since it is
necessary for each user to be able to access their own demand entry, while
claiming it. In the present implementation, the demands are kept for one
epoch, and claimed in the following. For this reason, a circular buffer of
size two is kept for each user, in order to prevent an incoming demand in a
given epoch to overwrite the previous epoch’s demand, before it is claimed.
This leads to a two dimensional ($2\text{ x }n$) demand vector, where the
demands for even and odd epochs are kept separately. Additionally, the
variable for keeping the epoch in which the demand was made (for preventing an
obsolete demand to interfere with later demands) is implemented; likewise as a
circular buffer of size two, in order to separate between the even and the odd
epochs.

In addition to the restructured demand, and the newly introduced claim
functions, AMF includes a state update function, which is called at the
beginning of both. The state update function checks the block number, and
calculates the epoch and the round in which the called function will be
executed (lines $3$ and $10$, respectively). The number of blocks for the
duration of an epoch and a round, is also a parameter of the system, which we
experimented on in the present study, and commented on in the results section.

The pseudo-code in Algorithm 2 is organised in three functions, namely, update
state (lines $1-15$), demand (lines $16-24$), and claim (lines $25-45$). At
the beginning of each function (in lines $2$, $18$, and $27$) a local selector
variable ($i$) for the circular buffers is declared and defined. When called
in a given epoch, the state update and the claim functions assume the same
selector values, and demand function assumes its binary complement. That is to
say $i$ values proceed as $<0,1,0,1,...>$ for the state update and claim
functions, and as $<1,0,1,0,...>$ for the demand function.

In line $3$, the epoch number ($E$) is checked for. If the value of $E$ is
found to be obsolete, it is updated. Once the epoch number is updated, the
round number, the capacity, and the unit share are also updated (lines $5-7$),
and the function returns. If epoch number is found to be up-to-date, a similar
check is done for the round number in line $10$. This check, when it returns
positive, leads to the update of the round number and the unit share (lines
$11-12$), and the function returns. If no update is required, the function
returns without making any changes in the state.

After updating the state and setting the selector variable, in line $19$ the
demand function checks whether the user has made a demand in the then present
epoch. If the user has made a demand, the function returns without registering
the newly arrived demand. If not, the demand amount ($a$) is written to the
corresponding slot in the circular demand buffer of the user, and the demand
epoch of the user is updated to be the then current epoch (lines $20-21$). In
the following line the function checks whether any demands have been made by
other users in the then current epoch. If not, the total weight is set to the
user’s weight (line $23$), which resets the total weight variable for the next
epoch. The variable for keeping the last epoch in which the total weight is
reset ($RE$) is updated in line $24$. If demands have been made by other users
prior to the then current call (i.e. $RE=E$) the weight of the user is added
to the total weight, to be accounted for in the next epoch (line $26$).

The claim function, similar to the demand function, starts with updating the
state and initiating the selector variable. It continues with a number of
checks (line $33$). Unless the demand has been done in the previous epoch and
is greater than $0$, or if the capacity is depleted, the function returns
without taking any further action. Following that in line $36$ the function
checks whether the user has made any claims in the then current epoch. If so,
the last round the user made a claim is checked (line $37$). If that also
turns positive, which means the user has claimed her fair share for the round,
the function returns without making any assignments.

If the check in line $36$ turns out negative, meaning this is the user’s first
claim in the then present epoch, the variable for the last epoch the user made
a claim ($ce_{u}$) is updated (line $41$). After that, a similar variable for
the round ($cr_{u}$) is updated in line $41$. Next, the assignment operations
similar to the ones in Algorithm 1 is done in lines $44-46$.

Note that this algorithm differs from the CMF algorithm in that the leftover
demands are not inserted into another heap; they remain in the map. Instead,
the fully satisfied demands are removed from the cumulative weight variable in
lines $42-44$, having the same effect as deleting the minimum in CMF
algorithm. This way, as long as there is an unsatisfied demand, the user’s
weight is included in the total weight, and the unit share is calculated
accordingly. At the end of the epoch, all demands are obsoleted.

1 Function: Update State(_$O,B,E,ES,RS$_)

2 $i\leftarrow E~{}~{}mod~{}~{}2$;

3 if  _$E <\left\lfloor\frac{B-O}{ES}\right\rfloor$_ then

4 $E\leftarrow\left\lfloor\frac{B-O}{ES}\right\rfloor$;

5 $R\leftarrow\left\lfloor\frac{(B-O)\%ES}{RS}\right\rfloor$;

6 $c\leftarrow c+C$;

7 $s\leftarrow\left\lfloor c/W_{i}\right\rfloor$;

8 return

9 end if

10if  _$R <\left\lfloor\frac{(B-O)\%ES}{RS}\right\rfloor$_ then

11 $R\leftarrow\left\lfloor\frac{(B-O)\%ES}{RS}\right\rfloor$;

12 $s\leftarrow c/W_{i}$;

13 return ;

14 end if

15return ;

16 Function: Demand(_$u,\text{a}$_)

17 Update State(_$O,B,E,ES,RS$_);

18 $i\leftarrow(E+1)~{}~{}mod~{}~{}2$;

19 if  _$de_{ui}\neq E$_ then

20 $d_{ui}\leftarrow a$;

21 $de_{ui}\leftarrow E$;

22 if  _$RE <E$_ then

23 $W_{i}\leftarrow w_{u}$;

24 $RE\leftarrow E$;

25 else

26 $W_{i}\leftarrow W_{i}+w_{u}$;

27 end if

28

29 end if

30return ;

31

32Function: Claim(_$u$_)

33 Update State(_$O,B,E,ES,RS$_);

34 $i\leftarrow E~{}~{}mod~{}~{}2$;

35 if  _$de_{ui}\neq E-1$ or $c=0$ or $d_{ui}=0$_ then

36 return ;

37 end if

38if  _$ce_{u}=E$_ then

39 if  _$cr_{u}=R$_ then

40 return ;

41 end if

42

43else

44 $ce_{u}\leftarrow E$;

45 end if

46$cr_{u}\leftarrow R$;

47 $b_{u}\leftarrow b_{u}+\min{(d_{ui},s*w_{u})}$;

48 $d_{ui}\leftarrow d_{ui}-\min{(d_{ui},s*w_{u})}$;

49 $c\leftarrow c-\min{(d_{ui},s*w_{u})}$;

50 if  _$d_{ui}=0$_ then

51 $W_{i}\leftarrow W_{i}-w_{u}$;

52 end if

53return ;

Algorithm 2 Weighted Autonomous Max-min Fairness (WAMF)

###  6.3 Weighted Autonomous Max-min Fairness

As the operation of the algorithm is described in Section 6.2, the only part
that is left to be explained in this subsection is the calculation of weights.

We defined weights to be the multiplicative inverses of the total demand
volume, up to and including the then present demand. This poses a problem in
the smart contract context, since Solidity does not offer floating point data
types. In other words, since the demand volumes are defined to be positive
integers, it is not possible to keep weights as they are, since the value
needs floating point data type to be stored. Instead, we keep the total demand
volume for each user ($dt_{u}$ for user $u$), introduce an intermediary
variable $p$ (standing for precision) and take the weight equal to:

$w_{u}=\left\lfloor\frac{p}{dt_{u}}\right\rfloor$

We get rid of this intermediary variable while calculating the unit share.
Therefore, instead of

$s=\left\lfloor\frac{c}{\sum_{u=1}^{n}w_{u}}\right\rfloor$

we use:

$s=\left\lfloor\frac{c\cdot p}{\sum_{u=1}^{n}w_{u}}\right\rfloor$

since

$s=\left\lfloor\frac{c\cdot
p}{\sum_{u=1}^{n}\frac{p}{dt_{u}}}\right\rfloor=\left\lfloor\frac{c}{\sum_{u=1}^{n}\frac{1}{dt_{u}}}\right\rfloor$

Similarly, while calculating the user share we use the intermediary variable
$p$:

$s_{u}=\left\lfloor\frac{s\cdot\left\lfloor\frac{p}{dt_{u}}\right\rfloor}{p}\right\rfloor$

As long as the value of $p$ is larger than the total demand volume of the
user, we obtain non-zero weights from
$\left\lfloor\frac{p}{dt_{u}}\right\rfloor$. For
$p=10^{k},k\in\mathcal{Z^{+}}$ is the number of decimal places stored for
weights.

##  7 Results

In this section, we present the results over the gas costs used as the main
performance metric. The tests are run on Parity Ethereum $2.7.2$, and the
contracts are implemented using Solidity $0.5.13$, thus the gas costs are
according to the definitions given thereby.

In our tests, we run Parity in development mode and used its instant seal
consensus algorithm, in which each transaction is placed in an individual
block and inserted instantly to the blockchain. A convenient metric for
measuring time is the block number. In the deployment of the system, this
metric can be used with the block latency to come up with rough temporal
estimations.

Since block latency is a policy parameter for each blockchain ecosystem,
taking block number as the main temporal performance metric is convenient also
in terms of generalizability of the results. As it is presented here, our
results are independent of consensus algorithm, and block latency parameters.

The results for each algorithm are presented in the subsections below. The
data are available at [39]

###  7.1 CMF Results

As indicated in Section 6.1, in the CMF, the demand vector is implemented as
an array of two min-heaps, exchanging the demands among each other at each
iteration. The demands arriving from the users are collected in $D_{0}$ for
the span of an epoch. At the end of the epoch, the distribute function is
called by the authority node, and the distribution is done. The first
iteration is done over $D_{0}$, taking all demands from the smallest to the
largest, granting the available share to the user, and finally either deleting
the minimum demand, if it is completely supplied, or deleting it from $D_{0}$
and inserting it to $D_{1}$, otherwise, to be supplied in the next iterations
if possible. The heaps exchange functions, and the process is repeated until
either all the demands are supplied, or the capacity for the epoch is
exhausted (see Algorithm 1)

Gas usage averages for $n=100$ entry sets are shown in Table 5. For
comparison, the gas performance of a general case heap implementation [40],
called Eth-heap, is provided next to our results:

Function | Present Study | Eth-heap
---|---|---
Insert | 95.459 | 101.261
Delete Minimum | 133.272 | 170.448
Table 5: Average gas costs for Insert and Delete Minimum functions

Considering the $8.000.000$ block gas limit, the heap operations impose an
upper bound of $60$ entries to be processed per block, on average, as seen
with the cost of operations in Table 5. This number is to be further lowered
with the additional cost of assignment operations, needed to record the fair
share of each user to her balance.

The finding immediately implies that an algorithm implemented as a smart
contract and relying on a central node to carry out the distribute function,
cannot support more than $\sim 10$ users, assuming that $3$ iterations are
necessary on average for a distribution process to complete. The exact number
is a function of how disperse the demands are, since the number of
delete/insert operations is dependent on the number of iterations necessary to
answer all the demands, which in turn is dependent on how disperse the demands
are.

This is also the reason why a weighted version of CMF has not been implemented
in the present study. The extra cost of calculating and storing weights will
make the weighted version perform even worse than the unweighted version.

###  7.2 AMF and WAMF Results

The first advantage to be pointed out for AMF is that it virtually has no
limit for the number of users that the system can support. The average gas
costs of demand and claim functions for a system with $10,50,100$ and $500$
users can be seen in Table 6. The tests have been carried over in a setting
where users have made demands, and claimed their demands in the succeeding
epoch. The results indicate that several demand and claim function calls can
be included within a block, without running into the block gas limit
exhaustion problem.

Function | No. of Users | AMF | WAMF
---|---|---|---
Demand | $10$ | $70.245$ | $79.732$
$50$ | $67.351$ | $77.135$
$100$ | $66.989$ | $76.835$
$500$ | $66.700$ | $71.365$
| $10$ | $46.800/140.401$ | $46,643/145.931$
Claim | $50$ | $42.240/126.720$ | $44.852/134.558$
(Avg./Total) | $100$ | $42.114/126.344$ | $44.763/134.289$
| $500$ | $42.047/126.143$ | $45.319/135.959$

Table 6: Average and total gas costs of AMF/WAMF demand and claim functions
for various numbers of users.

The results also indicate that the cost of demand and claim functions do not
grow with the growing number of users. On the contrary, there is a slight
decrease in the average costs, with the growing number of users. The reason
for this is the fact that in each epoch the first call to both functions are
costlier, since state variables are updated in these calls. With large sample
sizes, this difference tends to even out better as compared to the relatively
smaller sample sizes.

It should also be noted that the epochs and rounds should last enough for each
user to be able to make claims and demands. Since the instant seal engine
deployed in the tests place each transaction in an individual block, the epoch
and round spans are so chosen as to allow each user be able to make claims and
demands within an epoch. The parameters of the system that the tests have been
carried on have been shown in Table 7.

According to this, in a setting with $n$ users, in the first epoch, $n$ blocks
are used for user registration function calls and $2n$ blocks are filled with
empty transactions in order to synchronise the process. The following demand
function calls occupied $n$ more blocks, concluding the first epoch. From the
second epoch on, the sequence is $3$ rounds of claim in $3n$ blocks, followed
by $n$ blocks of demand for the next epoch. Three sets are run (adding up to
$4$ epochs), and the averages are collected.

Parameter | Value |  Definition
---|---|---
Number of Users | $n$ |  The number of users in the system
Epoch Capacity | $20n$ |  The amount to be distributed for each epoch
Epoch Span | $4n$ |  The duration of an epoch in number of blocks
Round Span | $n$ |  The duration of a round in number of blocks
Demand Interval | $[10,30)$ |  The interval from which the demands are drawn
Table 7: The values used in the tests for AMF and WAMF.

One thing that should be accounted for is that the average cost of demand
function declines throughout the rounds. The reason for this is, some demands
have been fully supplied in the previous epoch, thus, fewer calls to claim
function lead to the full execution of the function (i.e. calls from users
whose demands have already been satisfied return without making any
assignments). The average claim costs of rounds for Max-min and Weighted Max-
min Fairness schemes can be seen in Table 8.

Round | AMF | WAMF
---|---|---
$1$ | $64.677$ | $67.211$
$2$ | $32.717$ | $36.158$
$3$ | $28.749$ | $32.589$
Average | $42.047$ | $45.319$
Total | $126.143$ | $135.959$
Table 8: The costs of the claim functions over rounds, in a setting with
$n=500$ users.

The number of rounds, as indicated in Section 7.1 is a function of the initial
distribution of the demands. In our tests, we drew random demands from an
approximately uniform distribution offered by Javascript Math.random()
function, in the range $[10,30)$, and the epoch capacity is set to $20n$, so
that on average the overdemands and underdemands could balance each other out.

In all the simulations with a Python script, the distribution is completed in
$3$ iterations. Therefore, in the tests presented here, we run the system for
$3$ rounds of claims. The results are cross-checked with the Python
simulations and proved identical. We suspect that with the parameters used in
this study, $3$ iterations might be an upper bound, but we do not have a
proof. Further investigation needs to be carried out to in order to come up
with a theoretical bound.

Another variable that can be parameterized according to the policy and that
would effect gas costs is the size of the variables used to represent amounts.
The size of the variables can be chosen smaller to save from the extra cost of
unused space. The necessary sizes for the variables is dependent on the total
amount that is planned to be distributed in the long run, maximum available
allocation in an epoch and the maximum number of epochs to distribute all the
resource etc. In the present study, all the variables are implemented as their
$256$ bit defaults, in order not to lose generality.

##  8 Discussion

The main bottleneck, and the main performance metric of the present study is
the gas consumption, and this is arguably a natural approach for studies on
blockchain systems. However, the results presented in this study are not to be
taken for their absolute values. Low level improvements may be introduced in
coding or compilation, leading to lower transaction costs. The aim of this
approach is to demonstrate the availability, and the cost structure of the
Max-min Fairness algorithm, and its different implementations.

Accordingly, the present study demonstrates, over the failure of CMF to
support more than 10 users, that it is not feasible for Max-min Fairness
scheme to be implemented in the blockchain context as it is implemented in the
conventional computational settings. In principle, because of the block gas
limit, blockchain systems are not well suited for algorithms, which cannot be
efficiently distributed to be processed by multiple computing parties, with
partial data, and asynchronously. A single transaction to carry out a function
with heavy computational burden is not a working strategy while developing
software for blockchain systems.

This is in accordance with the distributed nature and the philosophy of the
blockchain systems. In contrast with the centralized systems, blockchains aim
to distribute both the work and the control among its users. For this reason,
they are incentive driven, as opposed to centralized systems, which are
authority driven. That is to say, centralized systems rely on an authorized
component (e.g. operating system kernels, load balancers, web servers etc.) to
carry out the computation; whereas blockchain systems rely on incentivising
its users to operate the system in a way that the outcome will turn out to be
the desired computation. Both AMF and WAMF are designed taking those points
into consideration. Consequently, they offer scalable solutions for blockchain
systems.

Another possibility to consider is changing the capacity replenishment policy.
In the present study, the capacity is replenished by a constant quantity $C$
at the beginning of each epoch. Instead, the tests can be run with varying
quantities of replenishment over time, possibly according to some function of
epoch number (i.e. $C=f(E)$). This may serve as a distribution mechanism for
systems that run on donations, like election rallies or other types of fund
raising projects, where public transparency, responsibility, incentivisation,
and participation are matters of consideration. This kind of a distribution
mechanism lends these projects the opportunity to be publicly transparent, and
make commitments (e.g. declaring the weights for the expenditure items) prior
to raising funds, since the system assures the enforcement of declared
commitments, by the virtue of its immutability.

##  9 Conclusion

In the present study we addressed the problem of fair distribution of shared
resources within the blockchain systems context. We worked on the intrinsic
resources of blockchains, and developed faucets as smart contracts, running
different implementations of Max-min Fairness Algorithm, which is
traditionally accepted realizing fairness in the literature.

It has been demonstrated that the Max-min Fairness algorithm, as it is
implemented in the conventional programming contexts, cannot support a public
system because of the scaling of its gas cost structure. Two autonomous
implementations of the algorithm are offered as a solution, and the tests have
shown that these implementations can support wide public use of the system
without running into block gas limit exhaustion problem.

Although, in the present, the faucets are mainly utilised as tools for
distributing the native currency of the test networks, the operation of faucet
systems need not be limited to this use case. These systems have the ability
to represent any resource type, and accordingly, to fairly allocate them, as
briefly discussed in the preceding section.

The faucet algorithms presented in this study are designed for single resource
planning. For the prospective studies we might propose focusing on multi-
resource planning problems. One way would be keeping each resource type
separate and distribute them in parallel, with the algorithms developed in the
present study. This will assume an independence of the supply and the value of
the resources. If the resources are dependent on each other, alternative
solutions must be proposed and evaluated.

## References

  * Nakamoto et al. [2008] S. Nakamoto, et al., Bitcoin: A peer-to-peer electronic cash system, 2008.
  * Wood et al. [2014] G. Wood, et al.,  Ethereum: A secure decentralised generalised transaction ledger,  Ethereum project yellow paper 151 (2014) 1–32.
  * Friederike Kleinfercher [2020] J. L. Friederike Kleinfercher, Sandra Vengadasalam, Bloxberg whitepaper, the trusted research infrastructure, v1.1, https://bloxberg.org/wp-content/uploads/2020/02/bl
oxberg$_$whitepaper$_$1.1.pdf, 2020\. [Online; accessed 1-March-2020].

  * Bloxberg [2020] Bloxberg, Bloxberg Faucet, https://faucet.bloxberg.org/, 2020\. [Online; accessed 17-September-2020].
  * Bertsekas et al. [1992] D. P. Bertsekas, R. G. Gallager, P. Humblet, Data networks, volume 2, Prentice-Hall International New Jersey, 1992.
  * Keshav and Kesahv [1997] S. Keshav, S. Kesahv, An engineering approach to computer networking: ATM networks, the Internet, and the telephone network, volume 116, Addison-Wesley Reading, 1997.
  * Crosby et al. [2016] M. Crosby, P. Pattanayak, S. Verma, V. Kalyanaraman, et al.,  Blockchain technology: Beyond bitcoin,  Applied Innovation 2 (2016) 71.
  * Foroglou and Tsilidou [2015] G. Foroglou, A.-L. Tsilidou,  Further applications of the blockchain,  in: 12th student conference on managerial science and technology, 2015, pp. 1–8.
  * Kuo et al. [2017] T.-T. Kuo, H.-E. Kim, L. Ohno-Machado,  Blockchain distributed ledger technologies for biomedical and health care applications,  Journal of the American Medical Informatics Association 24 (2017) 1211–1220.
  * Maesa et al. [2017] D. D. F. Maesa, P. Mori, L. Ricci,  Blockchain based access control,  in: IFIP international conference on distributed applications and interoperable systems, Springer, 2017, pp. 206–220.
  * Samaniego and Deters [2018] M. Samaniego, R. Deters,  Virtual resources & blockchain for configuration management in iot.,  J. Ubiquitous Syst. Pervasive Networks 9 (2018) 1–13.
  * Shirole et al. [2020] M. Shirole, M. Darisi, S. Bhirud,  Cryptocurrency token: An overview,  in: IC-BCT 2019: Proceedings of the International Conference on Blockchain Technology, Springer Nature, 2020, p. 133.
  * Hahne [1991] E. L. Hahne,  Round-robin scheduling for max-min fairness in data networks,  IEEE Journal on Selected Areas in communications 9 (1991) 1024–1039.
  * Gogulan et al. [2012] R. Gogulan, A. Kavitha, U. K. Kumar,  Max min fair scheduling algorithm using in grid scheduling with load balancing,  International Journal of Research in Computer Science 2 (2012) 41.
  * Waldspurger [1995] C. A. Waldspurger, Lottery and stride scheduling: Flexible proportional-share resource management, Ph.D. thesis, Massachusetts Institute of Technology, 1995.
  * Kay and Lauder [1988] J. Kay, P. Lauder,  A fair share scheduler,  Communications of the ACM 31 (1988) 44–55.
  * Nace and Pióro [2008] D. Nace, M. Pióro,  Max-min fairness and its applications to routing and load-balancing in communication networks: a tutorial,  IEEE Communications Surveys & Tutorials 10 (2008) 5–17.
  * Doulamis et al. [2007] N. D. Doulamis, A. D. Doulamis, E. A. Varvarigos, T. A. Varvarigou,  Fair scheduling algorithms in grids,  IEEE Transactions on Parallel and Distributed Systems 18 (2007) 1630–1648.
  * Marbach [2002] P. Marbach,  Priority service and max-min fairness,  in: Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, volume 1, IEEE, 2002, pp. 266–275.
  * Ghodsi et al. [2011] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, I. Stoica,  Dominant resource fairness: Fair allocation of multiple resource types.,  in: Nsdi, volume 11, 2011, pp. 24–24.
  * Mohanty et al. [2020] S. Mohanty, S. C. Moharana, H. Das, S. C. Satpathy,  Qos aware group-based workload scheduling in cloud environment,  in: Data Engineering and Communication Technology, Springer, 2020, pp. 953–960.
  * Hayes [2015] A. Hayes,  What factors give cryptocurrencies their value: An empirical analysis,  Available at SSRN 2579445 (2015).
  * Paritytech [2019] Paritytech, parity ethereum, https://github.com/paritytech/pa-rity-ethereum, 2019. [Online; accessed 19-November-2019].
  * Ren and Devadas [2016] L. Ren, S. Devadas,  Proof of space from stacked expanders,  in: Theory of Cryptography Conference, Springer, 2016, pp. 262–285.
  * Kiayias et al. [2017] A. Kiayias, A. Russell, B. David, R. Oliynykov,  Ouroboros: A provably secure proof-of-stake blockchain protocol,  in: Annual International Cryptology Conference, Springer, 2017, pp. 357–388.
  * King and Nadal [2012] S. King, S. Nadal,  Ppcoin: Peer-to-peer crypto-currency with proof-of-stake,  self-published paper, August 19 (2012) 1.
  * Król et al. [2019] M. Król, A. Sonnino, M. Al-Bassam, A. Tasiopoulos, I. Psaras,  Proof-of-prestige: A useful work reward system for unverifiable tasks,  in: 2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), IEEE, 2019, pp. 293–301.
  * Bentov et al. [2014] I. Bentov, C. Lee, A. Mizrahi, M. Rosenfeld,  Proof of activity: Extending bitcoin’s proof of work via proof of stake [extended abstract] y,  ACM SIGMETRICS Performance Evaluation Review 42 (2014) 34–37.
  * Ball et al. [2017] M. Ball, A. Rosen, M. Sabin, P. N. Vasudevan,  Proofs of useful work.,  IACR Cryptol. ePrint Arch. 2017 (2017) 203.
  * Abdul-Rahman [1997] A. Abdul-Rahman,  The pgp trust model,  in: EDI-Forum: the Journal of Electronic Commerce, volume 10, 1997, pp. 27–31.
  * Dannen [2017] C. Dannen, Introducing Ethereum and Solidity, Springer, 2017.
  * Baird et al. [2018] L. Baird, M. Harmon, P. Madsen,  Hedera: A governing council & public hashgraph network,  The trust layer of the internet, whitepaper 1 (2018) 1–97.
  * Foundation [2018] T. Foundation, Tron: Advanced decentralized blockchain platform, 2018.
  * Cheng et al. [2019] R. Cheng, F. Zhang, J. Kos, W. He, N. Hynes, N. Johnson, A. Juels, A. Miller, D. Song,  Ekiden: A platform for confidentiality-preserving, trustworthy, and performant smart contracts,  in: 2019 IEEE European Symposium on Security and Privacy (EuroS&P), IEEE, 2019, pp. 185–200.
  * Niloy et al. [2021] F. A. Niloy, M. A. Nayeem, M. M. Rahman, M. N. U. Dowla,  Blockchain-based peer-to-peer sustainable energy trading in microgrid using smart contracts,  in: 2021 2nd International Conference on Robotics, Electrical and Signal Processing Techniques (ICREST), IEEE, 2021, pp. 61–66.
  * Wöhrer and Zdun [2018] M. Wöhrer, U. Zdun,  Design patterns for smart contracts in the ethereum ecosystem,  in: 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), IEEE, 2018, pp. 1513–1520.
  * Wohrer and Zdun [2018] M. Wohrer, U. Zdun,  Smart contracts: security patterns in the ethereum ecosystem and solidity,  in: 2018 International Workshop on Blockchain Oriented Software Engineering (IWBOSE), IEEE, 2018, pp. 2–8.
  * Bragagnolo et al. [2018] S. Bragagnolo, H. Rocha, M. Denker, S. Ducasse,  Smartinspect: solidity smart contract inspector,  in: 2018 International Workshop on Blockchain Oriented Software Engineering (IWBOSE), IEEE, 2018, pp. 9–18.
  * Metin [2020] S. Metin, blockchainfaucet, 2020\. URL: https://github.com/serdarmetin/blockchainFaucet.
  * Mitton [2018] Z. Mitton, Priority Queue on Ethereum: eth-heap, 2018. URL: https://github.com/zmitton/eth-heap.