# State-Dependent Processing in Payment Channel Networks for Throughput
Optimization

Nikolaos Papadis  Electrical Engineering & Institute for Network Science, Yale
UniversityNew HavenConnecticutUSA<EMAIL_ADDRESS>and  Leandros
Tassiulas  Electrical Engineering & Institute for Network Science, Yale
UniversityNew HavenConnecticutUSA<EMAIL_ADDRESS>
(2021)

###### Abstract.

Payment channel networks (PCNs) have emerged as a scalability solution for
blockchains built on the concept of a payment channel: a setting that allows
two nodes to safely transact between themselves in high frequencies based on
pre-committed peer-to-peer balances. Transaction requests in these networks
may be declined because of unavailability of funds due to temporary uneven
distribution of the channel balances. In this paper, we investigate how to
alleviate unnecessary payment blockage via proper prioritization of the
transaction execution order. Specifically, we consider the scheduling problem
in PCNs: as transactions continuously arrive on both sides of a channel, nodes
need to decide which ones to process and when in order to maximize their
objective, which in our case is the channel throughput. We introduce a
stochastic model to capture the dynamics of a payment channel under random
arrivals, and propose that channels can hold incoming transactions in buffers
up to some deadline in order to enable more elaborate processing decisions. We
describe a policy that maximizes the channel success rate/throughput for
uniform transaction requests of fixed amounts, both in the presence and
absence of buffering capabilities, and formally prove its optimality. We also
develop a discrete event simulator of a payment channel, and evaluate
different heuristic scheduling policies in the more general heterogeneous
amounts case, with the results showing superiority of the heuristic extension
of our policy in this case as well. Our work opens the way for more formal
research on improving PCN performance via joint consideration of routing and
scheduling decisions.

††copyright: acmcopyright††journalyear: 2021††doi:
10.1145/1122445.1122456††conference: Woodstock ’18: ACM Symposium on Neural
Gaze Detection; June 03–05, 2018; Woodstock, NY††booktitle: Woodstock ’18: ACM
Symposium on Neural Gaze Detection, June 03–05, 2018, Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Blockchain technology enables trusted collaboration between untrusted parties
that want to reach consensus in a distributed setting. This is achieved with
the help of a distributed ledger, which is maintained by all interested nodes
in the network and functions as the source of truth. The original application
of blockchain, Bitcoin (Nakamoto, 2008), as well as many subsequent ones,
focus on the problem of distributed consensus on a set of financial
transactions and the order in which they were executed. Agreement on the above
provides a way for everyone to be able to prove that they own the amount they
claim to own, without a central entity such as a bank, which is a trusted
institution charged with this role in the traditional economic activity.
Transactions are organized in blocks and blocks are chained to form the
ledger, or the blockchain. In order for a single node to be able to amend
history to its benefit, significant power in the network is required. In Proof
of Work blockchains (including Bitcoin) for example, which rely on nodes
expending computation on solving a hard hash puzzle to include their block in
the chain, the attacking node should own a certain fraction of the
computational power, while in Proof of Stake blockchains, which rely on nodes
staking their wealth in order to publish new blocks, the attacker should own a
certain fraction of the network’s stake. Accountability and transparency are
thus guaranteed as long as each node’s share in the network power is limited.

Despite their success with solving distributed consensus, a major pain point
of blockchains is their scalability (Croman et al., 2016; Papadis et al.,
2018; Bagaria et al., 2019). Compared to a centralized system, where everyone
communicates with a single entity functioning as the source of truth,
decentralizing this operation and assigning this role to the entire network
introduces significant overheads in communication and in complexity. The
frequently cited figures for the transactions per second (throughput) achieved
by the two most prominent cryptocurrencies, 3-7 for Bitcoin and about double
that for Ethereum, are a good indication of the scalability problem,
especially as centralized counterparts such as PayPal or Visa achieve
throughput of thousands of transactions per second. Therefore, for blockchain
to be a long-term viable payment solution, this scalability barrier has to be
overcome.

A promising development in the scalability front is brought by the
introduction of payment channel networks (PCNs). PCNs are a “layer-2” solution
based on the idea that the majority of transactions are only communicated to
the interested parties instead of the entire global network, and the global
network is only consulted in case of disputes. The main building block of a
PCN is the concept of a payment channel: two entities from layer-1 (the
blockchain network itself) that want to transact frequently between themselves
and do not need nor want the entire network confirming and knowing, can form a
payment channel via a smart contract recorded on the blockchain and validated
by the entire network. After the channel is created, the nodes can transact
privately and orders of magnitude faster than done via the main layer-1
network. Payment channels form a network themselves, the PCN, in which
multihop payments are possible, and intermediate nodes relaying payments make
profit from collected fees. The most prominent PCN as of now are the Lightning
Network (Poon and Dryja, 2016) and the Raiden Network (Rai, [n.d.]).

Sending payments via the network formed by the channels requires appropriate
payment routing, scheduling, and congestion control, to guarantee sufficient
success rates and throughput. A multi-hop transaction might fail if it
encounters a channel with insufficient balance to process it on its path.
Several routing approaches have been proposed for proper path selection
(Papadis and Tassiulas, 2020), including source routing (Poon and Dryja,
2016), max-flow-based approaches (Sivaraman et al., 2020; Rohrer et al., 2017;
Yu et al., 2018; Dong et al., 2018; Wang et al., 2019; Varma and Maguluri,
2020), beacon-based routing with proactive aggregation of information
(Prihodko et al., 2016), landmark-based routing (Malavolta et al., 2017),
embedding-based routing (Roos et al., 2018), distance-vector routing (Hoenisch
and Weber, 2018), and ant routing (Grunspan et al., 2020). Scheduling and
congestion control have received little attention, with the notable exception
of (Sivaraman et al., 2020). Most of these schemes employ some heuristic rules
and lack formal optimality guarantees.

In this work, we study the transaction scheduling problem is PCNs from a
formal point of view. As transactions continuously arrive at the two sides of
each channel, the nodes have to make scheduling decisions: which transactions
to process, and when. We introduce a stochastic model for the channel’s
operation and derive an optimal policy that allows the channel to operate at
the maximum possible throughput, which is beneficial both for the nodes
relaying others’ payment to collect fees, and for the network overall. In
addition, we advocate for a modification in how transactions are handled by
nodes: we introduce pending transaction buffers (queues) at the nodes, and
allow the transactions to specify a deadline up to which their sender is
willing to wait in order to increase their success probability. The rationale
behind this modification is that an initially infeasible transaction, in the
extra time it is given in the buffer compared to being rejected immediately,
might become feasible thanks to the updates in the channel balances from
transactions executed from the opposite side. Thus, more elaborate state-
dependent scheduling policies become possible, making decisions based not only
on the instantaneous balances, but also on the buffer contents (the pending
transactions, each with their direction, amount and remaining time to
expiration). In this general setting, we are the first to analytically
describe a throughput-maximizing scheduling policy for a payment channel and
prove its optimality among all dynamic policies. Our theoretical results are
complemented by experiments in a payment channel simulator we implemented, and
on which we test various policies and compare their performance.

In summary, our contributions and insights are the following:

  * •

We develop a stochastic model that captures the dynamics of a payment channel
in an environment with random transaction arrivals from both sides.

  * •

We propose the idea of transaction deadlines and buffering in order to give
nodes more freedom in their scheduling decisions, and formulate the scheduling
problem in our stochastic model, for a channel both without and with buffering
capabilities.

  * •

We describe policies that optimize the throughput, the success rate and the
blockage when transaction amounts are fixed, and present the optimality proofs
for a channel both without and with buffering capabilities. We also introduce
two families of heuristic policies for the arbitrary amounts case.

  * •

We develop a realistic payment channel simulator that accounts for the
simultaneity of payments and implements the node buffering capabilities. We
use the simulator to evaluate the different scheduling policies in both the
fixed and varying transaction amounts cases.

  * •

We discuss the necessity of a joint approach to the fundamental problems of
routing and scheduling, using either formal stochastic modeling techniques, or
learning-based techniques that leverage the network’s operation data.

In summary, our paper is the first to formally treat the optimal scheduling
problem in a PCN with buffering capabilities.

The remainder of the paper is organized as follows. In section 2 we provide an
introduction to the operation of payment channels and introduce the idea of
transaction buffers. In section 3 we describe our stochastic model of a
payment channel, and in section 4 we present the throughput-optimal scheduling
policies, whose optimality we subsequently prove. In section 5 we present
heuristic policies for the more general arbitrary amounts case, and in section
6 we describe the experimental setup and the simulator used for the
evaluation, and present the results of several experiments we conducted. In
section 7 we discuss extensions and generalizations of this work to arbitrary
network structures, and in section 8 we look into related work. Finally,
section 9 concludes the paper.

##  2\. Background

##### Payment channel operation

Figure 1. A payment channel without (top) and with (bottom) pending
transaction buffers.

Blockchain network nodes A and B can form a payment channel between themselves
by signing a common commitment transaction that documents the amounts each of
them commits to the channel. For example, in the channel shown in Figure 1,
node $A$’s balance in the channel is 2 coins, and node $B$’s is 5 coins. After
the initial commitment transaction is confirmed by the blockchain network, A
and B can transact completely off-chain (without broadcasting their
interactions to the blockchain), by transferring the coins from one side to
the other and updating their balances respectively, without the fear of losing
funds thanks to a cryptographic safety mechanism. The total funds in the
channel is its capacity, which remains fixed throughout the channel’s
lifetime.

As nodes create multiple channels with other nodes, a network (the PCN) is
formed. In this network, if a channel does not already exist between a pair of
nodes who want to transact, multihop payments are possible. A cryptographic
construct (the Hashed Time-Lock Contract – HTLC) is again guaranteeing that
the payment will either complete end-to-end, or fail for all intermediate
steps. In Figure 2 for example, node $A$ wants to pay 3 coins to node $C$, and
can achieve this by paying 3 to $B$ and then $B$ paying 3 to $C$. Another
possible payment path is $A\rightarrow E\rightarrow D\rightarrow C$, which
however does not have enough balance (in the $E\rightarrow D$ channel in
particular) to support a payment of 3 coins. This network creates the need for
routing and scheduling of payments to achieve maximum throughput. For more
details on PCN operation, the reader is referred to (Gudgeon et al., 2020;
Papadis and Tassiulas, 2020).

##### Important Metrics in PCNs

The metrics usually used for evaluating the performance of a PCN are the
payment success rate (what percentage of all transactions complete
successfully), the (normalized) throughput (successful amount), and also the
fees a node receives from relaying others’ transactions. A node with a lot of
activity and high transacting amounts (e.g., a payment hub) might focus more
on optimizing throughput, while a node transacting once in a while might care
more for individual transactions succeeding. Since fees are affine in the
payment amount (Papadis and Tassiulas, 2020), for a specific node to maximize
the throughput of its channels is in some sense111Not strictly equivalent
because of the constant term: fee = constant base fee \+ proportional fee rate
$\cdot$ amount equivalent to maximizing the fees it is earning. Therefore, in
this work we are concerned with maximizing the success rate and throughput and
do not deal with fees. Maximizing the throughput is equivalent to minimizing
blockage, i.e. the amount of rejected transactions.

Figure 2. A payment channel network.

##### Payment scheduling policy

The default processing mechanism in a payment channel is the following:
feasible transactions are executed immediately, and infeasible transactions
are rejected immediately. In order to optimize success rates and throughput,
in this work we examine whether the existence of a transaction buffer, where
transactions would be pending before getting processed or rejected, would
actually increase the channel performance. We assume that the sender of every
transaction (or a higher-level application which the transaction serves)
specifies a deadline at most by which they are willing to wait before their
transaction gets processed/rejected. A fine balance when choosing a deadline
would be to push transactions execution to the future as much as possible in
order to allow more profitable decisions within the deadline, but not too much
to the extent that they would be sacrificed. Depending on the criticality of
the transaction for the application or the sender, the deadline in practice
could range from a few milliseconds to a few minutes. Note that this deadline
is different than other deadlines used by the Bitcoin and Lightning protocols
in time-locks (CheckLockTimeVerify – CLTV and CheckSequenceVerify – CSV)
(Aaron van Wirdum, [n.d.]), as the latter are related to when certain coins
can be spent by some node, while the deadline in our case refers to a Quality
of Service requirement of the application.

##  3\. Problem formulation

In this section, we introduce a stochastic model of a payment channel and
define the transaction scheduling problem in a channel with buffers.

Consider an established channel between nodes $A$ and $B$ with capacity
denoted by some positive natural number222All monetary quantities can be
expressed in integer numbers, as in cryptocurrencies and currencies in general
there exists some quantity of the smallest currency denomination, and all
amounts can be expressed as multiples of this quantity. For Bitcoin, this
quantity is 1 satoshi (=$10^{-8}$ bitcoins) or 1 millisatoshi. $C$. Define
$Q^{A}(t)$, $Q^{B}(t)$ to be the balances of nodes $A$ and $B$ in the channel
at time $t$, respectively. The capacity of a channel is constant throughout
its lifetime, so obviously $Q^{A}(t)+Q^{B}(t)=C$ for all times
$t\in\mathbb{R}_{+}$. We consider a continuous time model.

Transactions are characterized by their origin and destination ($A$-to-$B$ or
$B$-to-$A$), their timestamp (time of arrival) $t$ and their amount $v$. These
elements are enough to describe the current channel operation in a PCN like
Lightning, namely without the existence of a buffer. We additionally augment
each transaction with a maximum buffering time, or equivalently, a deadline by
which it has to be processed. We denote the value of a transaction from $A$ to
$B$ arriving at time $t_{n}^{A}$ as $v_{n}^{A}$ and its maximum buffering time
as $d_{n}^{A}$ (and similarly $t_{n}^{B},v_{n}^{B},d_{n}^{B}$ for transactions
from $B$ to $A$). Transactions arrive at the two nodes as marked point
processes: from $A$ to $B$:
$\\{(t_{n}^{A},d_{n}^{A},v_{n}^{A})\\}_{n=1}^{\infty}$, and from $B$ to $A$:
$\\{(t_{n}^{B},d_{n}^{B},v_{n}^{B})\\}_{n=1}^{\infty}$. Denote the deadline
expiration time of the transaction as $\tau_{n}^{A}\triangleq
t_{n}^{A}+d_{n}^{A}$ (similarly for B). Denote the set of all arrival times at
both nodes as
$T_{\text{arrival}}=\\{t_{n}^{A}\\}_{n=1}^{\infty}\cup\\{t_{n}^{B}\\}_{n=1}^{\infty}$,
and the set of all deadline expiration times as
$T_{\text{expiration}}=\\{\tau_{n}^{A}\\}_{n=1}^{\infty}\cup\\{\tau_{n}^{B}\\}_{n=1}^{\infty}$.

The state of the system comprises the instantaneous balances and the contents
of the buffers. The state at time $t$ is

(1) $\displaystyle\begin{split}x(t)=~{}\Bigl{(}&Q^{A}(t),Q^{B}(t),\\\
&D_{1}^{A}(t),...,D_{K^{A}(t)}^{A}(t),v_{1}^{A}(t),...,v_{K^{A}(t)}^{A}(t),\\\
&D_{1}^{B}(t),...,D_{K^{B}(t)}^{B}(t),v_{1}^{B}(t),...,v_{K^{B}(t)}^{B}(t)\Bigr{)}\end{split}$

where $K^{A}(t)$ is the number of pending transactions in node $A$’s buffer at
time $t$ (similarly for $K^{B}(t)$), $D_{k}^{A}(t)$ is the remaining time of
transaction $k$ in node $A$’s buffer before its deadline expiration (similarly
for $D_{k}^{B}(t)$), and $v_{k}^{A}(t)$ is the amount of the $k$-th
transaction in node $A$’s buffer (similarly for $v_{k}^{B}(t)$). For the
channel balances, it holds that
$(Q^{A},Q^{B})\in\\{(a,b)\in[C]\times[C]:a+b=C\\}$, where $[C]=
\\{0,1,\dots,C\\}$. For simplicity, we assume that the pending transactions in
each node’s buffer are ordered in increasing remaining time order. So
$D_{1}^{A}(t)\leq D_{2}^{A}(t)\leq...\leq D_{K^{A}(t)}^{A}(t)$, and similarly
for $B$.

A new arriving transaction causes a transition to a state that includes the
new transaction in the buffer of the node it originated from. The evolution of
the system is controlled, with the controller deciding whether and when to
serve each transaction. At time $t$, the set of possible actions at state
$x(t)$ is a function of the state and is denoted by $U(x(t))$. Specifically, a
control policy at any time $t$ might choose to process (execute) some
transactions and drop some others. When a transaction is processed or dropped,
it is removed from the buffer where it was stored. Additionally, upon
processing a transaction the following balance updates occur:

$\displaystyle(Q^{A},Q^{B})$ $\displaystyle\rightarrow(Q^{A}-v,Q^{B}+v),$ if
the processed transaction is from A to B and of amount $v$
$\displaystyle(Q^{A},Q^{B})$ $\displaystyle\rightarrow(Q^{A}+v,Q^{B}-v),$ if
the processed transaction is from B to A and of amount $v$

At time $t$, the allowable actions $u(t)$ are subsets of the set
$U^{\prime}(t)=\\{(node,k,action):node\in\\{A,B\\},1\leq k\leq
K^{node}(t),action\in\\{EX,DR\\}\\}$ that contain transactions in a specific
order such that executing and dropping them in that order is possible given
the channel state at time $t$. Action $EX$ means “execute the transaction,”
while action $DR$ means “drop the transaction.” Formally,

(2) $\displaystyle\begin{split}u(t)&\in U(x(t))=\\\
\bigl{\\{}&u=\\{(node_{i},k_{i},action_{i})\\}_{i=1}^{l}\in\mathcal{P}(U^{\prime}(t)):\\\
&\forall i=1,\dots,l,action_{i}\text{ on the $k_{i}$-th transaction of
$node_{i}$ is feasible after applying}\\\ &\text{the first $i-1$ actions on
the respective transactions}\bigr{\\}}\end{split}$

where $\mathcal{P}$ denotes the powerset of a set. Note that the empty set is
also an allowable action and means that at that time the control policy idles
(i.e. neither processes nor drops any transaction). An expiring transaction
that is not processed at the time of its expiration is automatically included
in the dropped transactions at that time instant.

Having defined all the possible actions, we should note the following: in the
presence of a buffer, more than one transaction might be executed at the same
time instant, either because two or more transactions expire at that time, or
because the policy decides to process two or more. The total amount processed
(if $action=EX$) or dropped (if $action=DR$) by the channel at time $t$ is:

(3) $\tilde{v}_{action}^{u(t)}(t)=\sum_{(k,node,action)\in
u(t)}v_{k}^{node}(t)$

For example, if $u(t)=\\{(A,2,EX),(B,3,DR),(B,1,EX)\\}$ (meaning that at time
$t$ the chosen action is to execute the second transaction from the buffer of
node $A$, drop the third transaction from the buffer of node $B$, and execute
the first transaction from the buffer of node $B$), then
$\tilde{v}_{EX}^{u(t)}(t)=v_{2}^{A}+v_{1}^{B}$ and
$\tilde{v}_{DR}^{u(t)}(t)=v_{3}^{B}$.

A control policy $\pi=\\{(t,u(t))\\}_{t\in\mathbb{R}_{+}}$ consists of the
times $t$ and the corresponding actions $u(t)$, and belongs to the set of
admissible policies

(4) $\Pi=\bigl{\\{}\\{(t,u(t))\\}_{t\in\mathbb{R}_{+}}\text{ such that
}u(t)\in U(x(t))\text{ for all }t\in\mathbb{R}_{+}\bigr{\\}}$

The total amount of transactions that have arrived until time $t$ is

(5) $\displaystyle
V_{\text{total}}(t)=\sum_{\begin{subarray}{c}n\in\mathbb{N}:~{}t_{n}\leq
t\end{subarray}}v_{n}$

The total throughput (i.e. volume of successful transactions) up to time $t$
under policy $\pi$ is:

(6) $\displaystyle
S^{\pi}(t)=\int_{\tau=0}^{t}\tilde{v}_{EX}^{u(\tau)}(\tau)d\tau$

The total blockage (i.e. volume of rejected transactions) up to time $t$ under
policy $\pi$ is:

(7) $\displaystyle
R^{\pi}(t)=\int_{\tau=0}^{t}\tilde{v}_{DR}^{u(\tau)}(\tau)d\tau$

The amount of pending transactions under policy $\pi$ is then the difference
between the total amount and the sum of the successful and rejected amounts:

(8) $\displaystyle P^{\pi}(t)=V_{\text{total}}(t)-S^{\pi}(t)-R^{\pi}(t)$

The objective is to maximize the total channel throughput (or minimize the
total channel blockage) over all admissible dynamic policies.

A few final notes on the assumptions: We assume that both nodes have access to
the entire system state, namely to the buffer contents not only of themselves,
but also of the other node in the channel. Therefore, in our model, referring
to one buffer per node or to a single shared buffer between the nodes is
equivalent. Moreover, our implicit assumption throughout the paper is that the
buffer sizes are not constrained. This implies that allowing or disallowing a
“Drop” action does not make a difference in terms of the optimality a policy
can achieve. To see this, suppose that node $A$ wants to drop a transaction at
some time before its expiration deadline, including its arrival time. What $A$
can do is wait until the transaction’s expiration without processing it, and
then it will automatically expire and get dropped. This has the same effect as
dropping the transaction earlier. Although a “Drop” action does not give add
or remove any flexibility from an optimal policy, it is helpful for
simplifying the proof of Lemma 2, and so we adopt it. If, however, the buffer
sizes are limited, then the need for nodes to select which transactions to
keep pending in their buffers arises, and dropping a transaction as soon as it
arrives or at some point before its expiration deadline might actually lead to
a better achieved throughput. As this case likely makes the problem
combinatorially difficult, we do not consider it in the present work.

The notation defined so far is summarized in Table 1 in Appendix A.

##  4\. Throughput-optimal scheduling in a payment channel

In this section, we determine a scheduling policy for the channel and prove
its optimality. The policy takes advantage of the buffer contents to avoid
dropping infeasible transactions by compensating for them utilizing
transactions from the opposite side’s buffer.

We first note that buffering does not only apply to transactions that are
infeasible on arrival, as in done for example in (Sivaraman et al., 2020). An
example where buffering even transactions that are feasible at their time of
arrival and not processing them right away can actually improve the success
rate and the throughput is shown in Figure 3. At $t=0$, node $A$ has a balance
of $Q^{A}(0)=7$, and two transactions from A to B in its buffer, with
remaining times and values as follows:
$(D_{1}^{A}(0),v_{1}^{A})=(3,9),(D_{2}^{A}(0),v_{2}^{A})=(5,2)$. At $t=1$, a
transaction of amount 2 from B to A arrives and is processed immediately. At
$t=4$, another transaction of amount 2 from B to A arrives and is processed
immediately. Now consider the two cases:

  * •

If the transaction (5,2) is executed at $t=0$, then the transaction (3,9) will
be rejected. In this case, at $t=5$ the number of successful transactions is 3
out of 4, and the throughput is 6.

  * •

If the transaction (5,2) waits until its deadline (which expires at $t=5$),
then both (5,2) and (3,9) will go through. In this case, at $t=5$ the number
of successful transactions is 4 out of 4, and the throughput is 15.

Therefore, although (5,2) is feasible at the time of its arrival, not
processing it directly and placing it into the buffer for subsequent
processing (as done in the second case) leads to more transactions being
executed and higher throughput eventually.

Figure 3. An example demonstrating that buffering even transactions feasible
at the time of their arrival can increase the success rate and the throughput.

Although the benefit from buffering transactions is intuitive, in the general
case where arriving transaction amounts are allowed to vary, finding an
optimal policy is intractable. Specifically, for a single channel without
buffers and for transactions of varying amounts, finding an optimal policy
that maximizes the number of transactions executed (equivalently, the success
rate) is NP-hard. An offline version of this problem with a finite input is
defined in (Avarikioti et al., 2018): $N$ transactions
$\\{(t_{n}^{A/B},v_{n}^{A/B})\\}_{n=1}^{N}$ of monetary value $v_{n}$ arrive
at times $t_{n}$ from either side, and the goal is to find a subset of the
arriving transactions to be executed in the order of arrival that maximizes
the number of successful executions. (To see how this problem fits in our
case, consider our more general model of section 3 with all buffering times
equal to zero). The decision version of the problem is proven (as Problem 2
with proof in section 3.2 of (Avarikioti et al., 2018)) to be NP-complete.
Therefore, finding an optimal policy in the general online setting of a single
channel with possibly infinite input of transactions is intractable. We expect
that the same is true when the objective is to maximize the total throughput.
For this reason, in the theoretical part of the paper we focus our attention
on the online case of a single channel with equal amounts for all arriving
transactions, for which an optimal policy can be analytically found.

###  4.1. General case: channel with buffers

We define policy PMDE (Process or Match on Deadline Expiration) for scheduling
transactions in the fixed amounts case. The optimality of PMDE will be shown
in the sequel and is the main result of this paper.

Input: channel state (balances and buffer contents)

1

2on  _arrival of transaction $p_{n}^{A}$ at time $t_{n}^{A}$_ do

3 add $p_{n}^{A}$ to A’s buffer

4

5on  _deadline expiration of transaction $p_{n}^{A}$ at time $\tau_{n}^{A}$_
do

6 if  _$p_{n}^{A}$ is in A’s buffer at time $\tau_{n}^{A-}$_ then

7 if  _$Q^{A}(\tau_{n}^{A-})\geq v_{n}^{A}$_ then

8 execute $p_{n}^{A}$;

9

10 else if  _$Q^{A}(\tau_{n}^{A-}) <v_{n}^{A}$ and $Q^{B}(\tau_{n}^{A-})\geq
v_{n}^{A}$ and $K^{B}(\tau_{n}^{A-})\geq 1$_ then

11 execute the transaction with remaining time $D_{1}^{B}(\tau_{n}^{A-})$ from
$B$ to $A$;

12 execute $p_{n}^{A}$;

13

14 else

15 drop $p_{n}^{A}$;

16

17

18 else

19 idle

20

Algorithm 1 PMDE scheduling policy (Process or Match on Deadline Expiration)

The policy is symmetric with respect to nodes A and B.

In words, PMDE operates as follows: Arriving transactions are buffered until
their deadline expires. On deadline expiration (actually just before, at time
$\tau_{n}^{A-}$), if the expiring transaction is feasible, it is executed. If
it is not feasible and there are pending transactions in the opposite
direction, then the transaction with the shortest deadline from the opposite
direction is executed, followed immediately by the execution of the expiring
transaction. Otherwise, the expiring transaction is dropped.

Note that the only information sharing between the two nodes PMDE requires is
the expiring transaction(s) at the time of expiration, information which would
be revealed anyway at that time. So PMDE is applicable also for nodes not
willing to share their buffer’s contents.

In the general case of non-fixed transaction amounts, the greedy policy PMDE
is not optimal for either objective. This is shown in the following
counterexample. Consider a channel with balance $10$ at node $A$ and one big
transaction of amount $9$ and $5$ small transactions of amounts $2$ arriving
in this order from node $A$ to node $B$. If the big one, which is feasible, is
processed greedily immediately, then the small ones become infeasible. The
total success rate in this case is $1/6$ and the total throughput is $9$.
While if the big one is rejected, then all the small ones are feasible. The
total success rate in this case is $5/6$ and the total throughput is $10$. So
PMDE is not optimal when transaction amounts are unequal, neither with respect
to the success rate, nor with respect to the throughput.

We now proceed to show PMDE’s optimality in the equal transaction amount case.
Note that in this case, the objectives of maximizing the success rate and
maximizing the throughput are equivalent, as they differ only by a scaling
factor (the transaction value divided by the total number of transactions),
and have the same maximizing policy. Note also that combining transactions
from the two sides as PMDE does requires that at least one of the transactions
is individually feasible. This will always happen as long as $Q^{A}(0)\geq v$
or $Q^{B}(0)\geq v$ in the fixed amounts case333Even in the general non-fixed
amounts case though, the chance of two transactions individually infeasible,
that is with amounts larger than the respective balances, occurring in both
sides of the channel simultaneously is very small: usually, the transaction
infeasibility issue is faced at one side of the channel because the side is
depleted and funds have accumulated on the other side..

This optimality of PMDE with respect to blockage is stated in Theorem 1, the
main theorem of this paper. This blockage optimality of PMDE also implies its
expected long-term average throughput optimality.

###### Theorem 1.

For a payment channel with buffers under the assumption of fixed transaction
amounts, let $R$ be the total rejected amount when the initial state is $x(0)$
and transaction are admitted according to a policy $\pi\in\Pi$, and $R^{PMDE}$
the corresponding process when PMDE is applied instead. Then, for any sample
path of the arrival process, it holds

(9) $R^{PMDE}(t)\leq R^{\pi}(t)\text{ a.s. for all }t\in\mathbb{R}_{+}$

We would like PMDE to be maximizing the channel throughput among all dynamic
policies. However, this is not true at every time instant. To see this,
consider another policy that ignores the existence of the buffer and processes
transactions immediately as soon as they arrive if they are feasible and drops
no transactions, and assume the channel balances are big enough that for some
time no transaction is infeasible. Then this policy achieves higher throughput
in the short term compared to PMDE, as PMDE waits until the deadline
expiration to execute a feasible transaction, while the other policy executes
it right away. For example, up to the first deadline expiration, assuming at
least one transaction up to then is feasible, the other policy achieves
nonzero throughput while PMDE achieves zero throughput.

Therefore, the optimality of PMDE does not hold for the throughput at every
time instant. It holds for another quantity though: the total blockage (and
because of (8), it also holds for the sum of the successfully processed
amounts plus the pending ones).

Let $\Pi^{DE}$ be the class of dynamic policies that take actions only at the
times of Deadline Expirations. We will first prove that to minimize blockage
it suffices to restrict our attention to policies in $\Pi^{DE}$. This is shown
in the following lemma.

###### Lemma 0.

For every policy $\pi\in\Pi$, there exists another policy
$\tilde{\pi}\in\Pi^{DE}$ that take actions only at the times of deadline
expirations, and the states and blockage at the times of deadline expirations
under $\tilde{\pi}$ are the same as under $\pi$:

(10) $\tilde{x}(\tau)=x(\tau)~{}\text{ and }~{}\tilde{R}(\tau)=R(\tau)$

for all $\tau\in T_{\text{expiration}}$, and for any sample path of the
arrival process.

###### Proof.

Let $\pi\in\Pi$ be an arbitrary policy that during the interval $[0,\tau_{1}]$
drops certain transactions and processes certain other transactions in some
specific order. We define another policy that takes no action during
$[0,\tau_{1})$ and at $\tau_{1}$ processes and drops the same transactions
that $\pi$ has processed and dropped respectively during $[0,\tau_{1}]$, in
exactly the same order. This is possible, since $\tau_{1}$ is the first
expiration time. Thus, at $\tau_{1}$ we have that the states (balances and
buffer contents) and blockages under $\pi$ and $\tilde{\pi}$ are exactly the
same. Now, defining $\tilde{\pi}$ analogously and applying the same argument
on the intervals $(\tau_{1},\tau_{2}],(\tau_{2},\tau_{3}],\dots$ inductively
proves the lemma. ∎

To prove Theorem 1, we will also need the following lemma.

###### Lemma 0.

For every policy $\pi\in\Pi^{DE}$, there exists a policy
$\tilde{\pi}\in\Pi^{DE}$ that acts similarly to PMDE at $t=\tau_{1}$ and is
such that when the system is in state $x(0)$ at $t=0$ and policies $\pi$ and
$\tilde{\pi}$ act on it, the corresponding total rejected amount processes $R$
and $\tilde{R}$ can be constructed via an appropriate coupling of the arrival
processes so that

(11) $\tilde{R}(t)\leq R(t),t\in\tau_{1},\tau_{2},\dots$

The proof idea is the following: We construct $\tilde{\pi}$ and couple the
blockage processes under $\pi$ and $\tilde{\pi}$ and identical transaction
arrival processes so that (11) holds. First, we consider what policies $\pi$
and $\tilde{\pi}$ might do at time $\tau_{1}$ of the first deadline
expiration. Then, for each possible combination, we couple $\tilde{\pi}$ with
$\pi$ in subsequent times so that at some point the states (balances and
buffer contents) and the total blockages under $\pi$ and $\tilde{\pi}$
coincide, and so that (11) is being satisfied at all these times. From then
on, we let the two policies move together. The full proof is given in Appendix
B.

Next, we present the proof of Theorem 1.

###### Proof.

The proof proceeds as follows: We first use Lemma 1 to say that a blockage-
minimizing policy among all policies in $\Pi$ exists in the class $\Pi^{DE}$.
We then repeatedly use Lemma 2 to construct a sequence of policies converging
to the optimal policy. Each element of the sequence matches the optimal policy
at one more step each time, and is at least as good as any other policy until
that point in time. Having acquired this sequence of policies that gradually
tends to the proposed optimal policy, we can inductively show that the
proposed optimal policy PMDE achieves higher throughput than any other policy.
A similar technique is used in sections IV and V of (Tassiulas and Ephremides,
1993).

From Lemma 1, we have that for any policy $\pi\in\Pi$, we can construct
another policy $\pi^{\prime}\in\Pi^{DE}$ such that for the corresponding total
blockage processes $R^{\pi}$ and $R^{\pi^{\prime}}$ we have
$R^{\pi^{\prime}}(t)\leq R^{\pi}(t)$, $t\in\mathbb{R}_{+}$.

From Lemma 2, we have that given policy $\pi^{\prime}\in\Pi^{DE}$, we can
construct a policy $\pi_{1}\in\Pi^{DE}$ that is similar to PMDE at
$t=\tau_{1}$ and is such that for the corresponding total blockage processes
$R^{\pi^{\prime}}$ and $R^{\pi_{1}}$ we have $R^{\pi_{1}}(t)\leq
R^{\pi^{\prime}}(t)$, $t\in T_{\text{expiration}}$.

By repeating the construction, we can show that there exists a policy
$\pi_{2}$ that agrees with $\pi_{1}$ at $t=\tau_{1}$, agrees with PMDE at
$t=\tau_{2}$, and is such that for the corresponding total blockage processes
we have $R^{\pi_{2}}(t)\leq R^{\pi_{1}}(t)$, $t\in T_{\text{expiration}}$.

If we repeat the argument $k$ times, we obtain policies $\pi_{i}$,
$i=1,\dots,k$, such that policy $\pi_{i}$ agrees with PMDE up to and including
$\tau_{i}$, and for the for the corresponding total blockage processes we have
$R^{\pi_{k}}(t)\leq R^{\pi_{k-1}}(t)\leq\dots\leq R^{\pi_{1}}(t)\leq
R^{\pi^{\prime}}(t)\leq R^{\pi}(t)$, $t\in T_{\text{expiration}}$.

Taking the limit as $k\rightarrow\infty$:

(12) $\displaystyle\lim_{k\rightarrow\infty}R^{\pi_{k}}(t)$
$\displaystyle=R^{PMDE}(t)$

Therefore, $R^{PMDE}(t)\leq R^{\pi}(t)$, $t\in T_{\text{expiration}}$. ∎

Note that the proven optimality results hold independently of the capacity and
initial balances.

###  4.2. Special case: channel without buffers

####  4.2.1. Optimal policy for the channel without buffers

The results of section 4.1 apply also in the special case where either buffers
are nonexistent (and therefore all transactions have to processed or dropped
as soon as they arrive), or when all buffering times of arriving transactions
are zero. In this case, deadline expiration times are the same as arrival
times, and policy PMDE becomes the following policy PFI (= Process Feasible
Immediately):

Input: channel state (balances only)

1

2on  _arrival of transaction $p_{n}^{A}$ at time $t_{n}^{A}$_ do

3 if  _$Q^{A}(t_{n}^{A-})\geq v_{n}^{A}$_ then

4 execute $p_{n}^{A}$;

5

6 else

7 drop $p_{n}^{A}$;

8

9

Algorithm 2 PFI scheduling policy (Process Feasible Immediately)

In words, upon transaction arrival, PFI executes the transaction immediately
if it is feasible, and drops the transaction immediately if it is not
feasible. Formally, PFI takes action $(A,1,EX)$ at all times $t_{n}^{A}$,
$n\in\mathbb{N}$, if $Q^{A}(t_{n})\geq v_{n}^{A}$ and action $(A,1,DR)$
otherwise, action $(B,1,EX)$ at all times $t_{n}^{B}$, $n\in\mathbb{N}$, if
$Q^{B}(t_{n})\geq v_{t_{n}}^{B}$ and action $(B,1,DR)$ otherwise.

The following corollary states the analog of Theorem 1 and for the case of the
channel without buffers.

###### Corollary 0.

For a single channel without buffers under the assumption of fixed transaction
amounts, policy PFI is optimal with respect to the total blockage: Let $R$ be
the total rejected amount when the initial state is $x(0)$ and transaction are
admitted according to a policy $\pi\in\Pi$, and $R^{PMDE}$ the corresponding
process when PMDE is applied instead. Then, for any sample path of the arrival
process, it holds

(13) $R^{PMDE}(t)\leq R^{\pi}(t)\text{ a.s. for all }t\in\mathbb{R}_{+}$

In addition, in this case the following also holds for any sample path of the
arrival process:

(14) $S^{PFI}(t)\geq S^{\pi}(t)\text{ a.s. for all }t\in\mathbb{R}_{+}$

Equation (14) is a direct consequence of (13) and (8), as in this case the
pending transaction amount is always zero.

####  4.2.2. Analytical calculation of optimal success rate and throughput for
the channel without buffers

For a channel without buffers, if the arrivals follow a Poisson process, we
can calculate the optimal success rate and throughput as the ones we get by
applying the optimal policy PFI.

###### Theorem 4.

For a single channel between nodes $A$ and $B$ with capacity $C$, and Poisson
transaction arrivals with rates $\lambda_{A}\neq\lambda_{B}$ and fixed amounts
equal to $v$, the maximum possible success rate of the channel is

(15)
$SR_{\text{opt}}=\lambda_{A}\left(1-\frac{\lambda_{B}/\lambda_{A}-1}{(\lambda_{B}/\lambda_{A})^{\tilde{C}+1}-1}\right)+\lambda_{B}\left(1-\left(\frac{\lambda_{B}}{\lambda_{A}}\right)^{\tilde{C}}\frac{\lambda_{B}/\lambda_{A}-1}{(\lambda_{B}/\lambda_{A})^{\tilde{C}+1}-1}\right)$

where $\tilde{C}=\lfloor\frac{C}{v}\rfloor$.

When $\lambda_{A}=\lambda_{B}=\lambda$, the maximum possible success rate is

(16) $SR_{\text{opt}}=\frac{2\lambda\tilde{C}}{\tilde{C}+1}$

A proof of this result is given in Appendix C. The maximum possible normalized
throughput is $S\cdot v$.

##  5\. Heuristic policies for general amount distributions

So far, we have described our PMDE policy and proved its optimality for a
channel with or without buffering capabilities in the case of fixed arriving
transaction amounts. PMDE could also serve though the more general case of
arbitrary amounts if payment splitting is used. Indeed, there have been
proposals (e.g., (Sivaraman et al., 2020)) that split payments into small
chunks-packets and route or schedule them separately, possibly along different
paths and at different times, utilizing Atomic Multipath Payments (AMP)
(Osuntokun and Fromknecht, 2018). Recall that it is guaranteed by the PCN’s
cryptographic functionality (the HTLC chaining) that a multihop payment will
either complete or fail along all intermediate steps. The additional
constraint if AMP is employed is that some check should be performed to ensure
that all chunks of a particular transaction are processed until their
destination, or all chunks are dropped. This could for example be checked when
the transaction deadline expires, at which moment every node would cancel all
transactions for which it has not received all chunks. Therefore, this is one
way to be able to apply PMDE to an arbitrary transaction amounts setting.

We also present a modified version of PMDE that does not require payment
splitting and AMP, and is a heuristic extension of the policy that was proved
optimal for fixed transaction amounts. Since now a transaction of exactly the
same amount as the expiring one is unlikely to exist and be the first in the
opposite node’s buffer, the idea is to modify the matching step of PMDE so
that the entire buffer of the opposite side is scanned until enough opposite
transactions are found so as to cover the deficit. The buffer contents are
sorted according to the criterion bufferDiscipline, possible values for which
are: oldest-transaction-first, youngest-transaction-first, closest-deadline-
first, largest-amount-first, smallest-amount-first. The modified policy PMDE
is shown in Algorithm 3, and is symmetric with respect to nodes A and B.

Input: channel state (balances and buffer contents)

Parameters : bufferDiscipline

1

2on  _arrival of transaction $p_{n}^{A}$ at time $t_{n}^{A}$_ do

3 add $p_{n}^{A}$ to A’s buffer

4

5on  _deadline expiration of transaction $p_{n}^{A}$ at time $\tau_{n}^{A}$_
do

6 if  _$p_{n}^{A}$ is in A’s buffer at time $\tau_{n}^{A-}$_ then

7 if  _$Q^{A}(\tau_{n}^{A-})\geq v_{n}^{A}$_ then

8 execute $p_{n}^{A}$;

9

10 else if  _$Q^{A}(\tau_{n}^{A-}) <v_{n}^{A}$ and $Q^{B}(\tau_{n}^{A-})\geq
v_{n}^{A}$ and $K^{B}(\tau_{n}^{A-})\geq 1$_ then

11 deficit $\leftarrow Q^{A}(\tau_{n}^{A-})-v_{n}^{A}$;

12 scan transactions in B’s buffer in order bufferDiscipline and find the
first set with total amount ¿ deficit;

13 if  _such a set exists_ then

14 execute these transactions from $B$ to $A$;

15 execute $p_{n}^{A}$;

16

17 else

18 drop $p_{n}^{A}$;

19

20

21 else

22 drop $p_{n}^{A}$;

23

24

25 else

26 idle

27

Algorithm 3 Generalized PMDE scheduling policy

We also evaluate another family of heuristic policies that sort the
transactions in the buffer according to some criterion and process them in
order, and which is shown in Alg. 4. The buffer might be shared between the
two nodes (thus containing transactions in both directions), or separate. At
regular intervals (every checkInterval seconds – a design parameter), expired
transactions are removed from the buffer. Then, the buffer contents are sorted
according to the criterion bufferDiscipline, and as many of them as possible
are processed by performing a single linear scan of the sorted buffer. The
policies of this family are also parameterized by immediateProcessing. If
immediateProcessing is true, when a new transaction arrives at a node, if it
is feasible, it is processed immediately, and only otherwise added to the
buffer, while if immediateProcessing is false, all arriving transactions are
added to the buffer regardless of feasibility. The rationale behind non-
immediate processing is that delaying processing might facilitate the
execution of other transactions that otherwise would not be possible to
process.

Input: channel state (balances and buffer contents)

Parameters : bufferDiscipline, immediateProcessing, checkInterval

1

2on  _arrival of transaction $p_{n}^{A}$ at time $t_{n}^{A}$_ do

3 if  _immediateProcessing = True and $Q^{A}(t_{n}^{A-})\geq v_{n}^{A}$_ then

4 execute $p_{n}^{A}$

5 else

6 add $p_{n}^{A}$ to A’s buffer

7

8

9every  _checkInterval_ do

10 remove expired transactions from buffer;

11 sortedBuffer $\leftarrow$ sort(buffer, bufferDiscipline);

12 for  _transaction $p\in\text{sortedBuffer}$_ do

13 if  _$p$ is feasible_ then

14 execute $p$;

15

16

17

Algorithm 4 PRI scheduling policy (Process at Regular Intervals)

An underlying assumption applying to all policies is that the time required
for buffer processing is negligible compared to transaction interarrival
times. Thus, buffer processing is assumed effectively instantaneous.

##  6\. Evaluation

###  6.1. Simulator

In order to evaluate the performance of different scheduling policies,
especially in the analytically intractable case of arbitrary transaction
amounts, we built a discrete event simulator of a single payment channel with
buffer support using Python SimPy (Lünsdorf and Scherfke, [n.d.]). Discrete
Event Simulation, as opposed to manual manipulation of time, has the
advantages that transaction arrival and processing occur as events according
to user-defined distributions, and the channel is a shared resource that only
one transaction can access at a time. Therefore, such a discrete event
simulator captures a real system’s concurrency and randomness more
realistically. The simulator allows for parameterization with respect to the
initial channel balances, the transaction generation distributions (frequency,
amount, and maximum buffering time) for both sides of the channel, and the
total transactions to be simulated. The channel has two buffers attached to it
that operate according to the scheduling policy being evaluated. The code of
our simulator will be open-sourced.

###  6.2. Experimental setup

Figure 4. Cumulative Distribution Function of the amounts used from the credit
card transaction dataset (Machine Learning Group - ULB, [n.d.]).

####  6.2.1. Optimal policy for arbitrary amounts

We simulate a payment channel between nodes 0 and 1 with a capacity of 300
with initial balances of 0 and 300 respectively444In practice, Lightning
channels are usually single-funded initially (Pickhardt and Nowostawski,
2020).. Transactions are arriving from both sides according to Poisson
distributions. We evaluate policies PMDE and PRI defined in section 5, with
(PRI-IP) or without immediate processing (PRI-NIP), for all 5 buffer
disciplines (so 15 policies in total), and when both nodes have buffering
capabilities (with and without shared knowledge of the contents), or only one
node, or none. Each experiment is run for around 1500 seconds, and in the
results only the transactions that arrived in the middle 80% of the total
simulation time are accounted for, so that the steady-state behavior of the
channel is captured. Unless otherwise stated, we present our results when
using the oldest-transaction-first buffer discipline, and the checkInterval
parameter used by the PRI policies is set to 3 seconds. For studying the
general amounts case, we use synthetic data from Gaussian and uniform
distributions, as well as an empirical distribution drawn from credit card
transaction data. The dataset we used is (Machine Learning Group - ULB,
[n.d.]) (also used in (Sivaraman et al., 2020)) and contains transactions
labeled as fraudulent and non-fraudulent. We keep only the latter, and from
those we sample uniformly at random among the ones that are of size less than
the capacity. The final distribution we draw from is shown in Figure 4.
Finally, since our simulations involve randomness, we run each experiment for
a certain configuration of the non-random parameters 10 times and average the
results. The error bars in all graphs denote the minimum and maximum result
values across all runs of the experiment.

###  6.3. Results

####  6.3.1. Optimal policy for fixed amounts and symmetric/asymmetric demand

We first simulate a symmetric workload for the channel of 500 transactions on
each side with Poisson parameters equal to 3 (on average 1 transaction every 3
seconds), fixed amounts equal to 50, and a shared buffer between the nodes.
The buffering time for all transactions is drawn from a uniform distribution
between 0 and a maximum value, and we vary this maximum value across
experiments to be 1, 2,…, 10, 20, 30,…, 120 seconds.

(a) Symmetric demand

(b) Asymmetric demand, total throughput

(c) Asymmetric demand, per node throughput

(d) Asymmetric demand, Number of sacrificed transactions

Figure 5. Total channel throughput and number of sacrificed transactions as a
function of maximum buffering time for different scheduling policies, for
oldest-first buffer discipline

We plot the behavior of the total channel throughput (proportional to the
success rate because of fixed amounts) for a single channel for different
experiments with increasing maximum buffering time (Figure 5(a)). The figures
for the other disciplines are very similar. Indeed, PMDE performs better than
the heuristic PRI policies, as expected. We also observe for all policies the
desired behavior of increasing throughput with increasing buffering time.
Moreover, we observe a diminishing returns behavior.

We next consider the effects of asymmetry in the payment demand: we modify the
setup of the previous section so that now 750 transactions arrive at node $A$
every 2 seconds on average (and 500 every 3 seconds at node $B$). The results
are shown in Figure 5(b). In this asymmetric demand case, as expected, the
throughput is overall lower compared to the symmetric case, since many
transactions from the side with the higher demand do not find enough balance
in the channel to become feasible. Figure 5(c) shows separately the throughput
for each of the nodes. We observe again that buffering is helpful for both
nodes, more so for node $B$ though, which was burdened with a smaller load and
achieves higher throughput than node $A$. It is also interesting that the
number of sacrificed transactions (i.e. that were feasible on arrival but
entered the buffer and were eventually dropped) shown in Figure 5(d) is small
for PMDE compared to PRI-NIP (and trivially 0 for PRI-IP).

Nevertheless, in both the symmetric and the asymmetric cases, we generally
observe what we would expect: that the channel equipped with a buffer (denoted
by a non-zero maximum buffering time in the figures) performs at least as good
as the channel without a buffer (i.e. with a maximum buffering time equal to 0
in the figures).

The immediate processing version of PRI leads to slightly better throughput
for large buffering times. The difference between PRI-IP and PRI-NIP is more
pronounced for small maximum buffering time values on the horizontal axis,
because of the checkInterval parameter (set to 3 seconds): for small buffering
times, all or most transactions have an allowed time in the buffer of a few
seconds, so none, one, or very few chances of being considered every 3
seconds. The conclusion is that the benefit PRI can reap from holding feasible
incoming transactions in the buffer instead of processing them right away is
not worth the cost in this case, as processing them immediately leads to
higher overall throughput.

####  6.3.2. Optimal policy for arbitrary amounts

We now evaluate our policies on scenarios with symmetric demand when the
transaction amounts follow some non-constant distribution. Specifically, we
use a Gaussian distribution of mean 100 and variance 50 (truncated at the
channel capacity of 300), a uniform distribution in the interval [0,
capacity], and the empirical distribution from the credit card transaction
dataset.

We first examine the role of the buffer discipline. Figure 6 shows all the
policies for all 5 disciplines for the empirical dataset. The figures when
using the Gaussian or uniform amounts are similar. We observe similar results
for different buffer disciplines, with PMDE performing best for small and
medium maximum buffering times, and PRI-PI performing best for large maximum
buffering times. This is likely due to the fact that PRI-IP offers each
transaction multiple chances to be executed (every checkInterval), unlike PMDE
that offers only one chance. The higher the maximum buffering time, the more
chances transactions get, leading to the higher throughput of PRI. Since the
results are quite similar for different disciplines, in the rest of the
figures we adopt the oldest-first discipline, which additionally incorporates
a notion of First-In-First-Out fairness for transactions.

\͡centering

(a) Oldest first

(b) Youngest first

(c) Closest deadline first

(d) Largest amount first

(e) Smallest amount first

Figure 6. Total channel throughput as a function of maximum buffering time for
different scheduling policies and buffer disciplines

Figure 7 shows the normalized throughput achieved by the three policies under
the oldest-first discipline, for different amount distributions. For Gaussian
amounts (Figure 7(a)), PMDE outperforms PRI-IP and PRI-NIP. For uniformly
distributed amounts in [0, 300], however (Figure 7(b)), we see that for large
buffering times PMDE is not as good as the PRI policies. This is due to the
fact that, unlike the Gaussian amounts that were centered around a small value
(100), amounts now are more frequently very large, close to the capacity. As
PMDE gives only one chance to transactions to be executed (i.e. on their
expiration deadline), while PRI gives them multiple opportunities (i.e. every
time the buffer is scanned), very large transactions have a higher probability
of being dropped under PMDE than under PRI. This justification is confirmed by
the fact that for smaller Uniform[0, 100] amounts (Figure 7(c)), PMDE is
indeed the best. As in practice sending transactions close to the capacity
does not constitute good practice and use of a channel, PMDE proves to be the
best choice for small- and medium-sized transactions.

(a) Gaussian(100, 50)

(b) Uniform(0, 300)

(c) Uniform(0, 100)

(d) Empirical

Figure 7. Total channel throughput as a function of maximum buffering time for
different scheduling policies and transaction amount distributions

####  6.3.3. The importance of privacy and collaboration in scheduling

We now study a different question: how important is it for both nodes to have
a buffer, and if they do, to share the contents with the other node (a node
might have a buffer and not want to share its contents for privacy reasons).
As mentioned earlier, for PMDE in particular this concern is not applicable,
as the only information shared is essentially the expiring transaction(s),
which would be revealed anyway at the time of their execution. For PRI though,
a policy prioritizing the oldest transaction in the entire buffer versus in
one direction only might have better performance, and provide an incentive to
nodes to share their buffers.

(a) PMDE

(b) PMDE

(c) PRI-IP

(d) PRI-IP

(e) PRI-NIP

(f) PRI-NIP

Figure 8. Success rate and normalized throughput for different scheduling
policies and node buffering capabilities

We evaluate a scenario with symmetric demand of 500 transactions from each
side every 3 seconds on average, with Gaussian amounts as before, and
buffering times uniform in [0, 5] seconds. We evaluate all policies with the
oldest-first discipline for all combinations of buffer capabilities at nodes:
none, only one or the other, both but without shared knowledge, and both with
shared knowledge. The results for the success rate and the normalized
throughput are shown in Figure 8.

We observe that all policies perform better when both nodes have buffers as
opposed to one or both of them not having. Non-immediate processing trivially
leads to almost 0 performance when at least one node does not have a buffer
because all transactions of this node are dropped (by being redirected to a
non-existent buffer), and thus neither can the other node execute any but few
transactions because its side gets depleted after executing the first few. In
conclusion, PRI-NIP makes sense only when both nodes have buffers. We also
observe similar performance in PMDE and PRI-IP for separate and shared
buffers, which suggests that nodes can apply these policies while keeping
their buffer contents private without missing out on performance. (In PRI-NIP,
they actually even miss out on performance by sharing).

(a) Buffers: none, Amounts: Gaussian(100, 50)

(b) Buffers: both nodes, Amounts: Gaussian(100, 50)

(c) Buffers: none, Amounts: Empirical

(d) Buffers: both nodes, Amounts: Empirical

Figure 9. Success rate as a function of transaction amount for different
scheduling policies

####  6.3.4. Benefits from buffering as a function of the transaction amount

We now study how the existence of buffers affects the throughput of
transactions of different amounts. We run one experiment with a specific
configuration: initial balances 0 and 300, Gaussian(100, 50) transaction
amounts, and constant deadlines for all transactions equal to 5 seconds. We
repeat the experiment 10 times and average the results. We partition the
transaction amounts in intervals and plot the success rate of transactions in
each interval. We do the same for amounts from the empirical distribution. The
result for oldest-first buffer discipline are shown in Figure 9 (results for
other disciplines are similar).

Figure 10. Success rate as a function of transaction maximum buffering time
for different scheduling policies

By comparing the graphs where the nodes do not have buffers versus when they
both have a shared buffer, we observe that it is the transactions of larger
amounts that are actually benefiting from buffering. The reason is that
smaller transactions are more likely to be feasible and clear on their arrival
even without a buffer, while larger ones are likely infeasible on arrival. The
zero success rates of PRI-NIP when there are no buffers are trivially due to
its design. We observe similar success rates for PMDE and PRI-IP when there
are no buffers, and PMDE being slightly better than PRI-IP when there are
buffers, except for possibly a few very large amounts (the latter is for the
same reason why PRI-IP is better for large amounts in Figure 7(b)). This
insight is important from a user experience perspective: a PCN node, depending
on the sizes of the transactions it serves, can decide whether it is
worthwhile to use PMDE for higher success rates but have to wait longer for
each transaction (till its deadline expiration), or use some more immediate
policy like PRI with potentially lower success rate but faster clearing.

####  6.3.5. Benefits from buffering as a function of the transaction deadline

Similarly as in section 6.3.4, in this section we study whether transactions
with longer versus shorter initial buffering times tend to benefit from the
existence of the buffer the most. We run one experiment with a specific
configuration: initial balances 0 and 300, constant transaction amounts equal
to 50, and uniform deadlines from 0 to 60 seconds. We repeat the experiment 10
times and average the results. We partition the buffering times in intervals
and plot the success rate of transactions in each interval. The result for
oldest-first buffer discipline are shown in Figure 10 (results for other
disciplines are similar). We observe that for PMDE there is no differentiation
among transactions with different buffering times, as PMDE processes all
transactions on their deadline expiration, regardless of when that occurs. For
the PRI policies though, large buffering times (e.g., more than 11 seconds)
are generally better, as they allow for more opportunities for the transaction
to be considered for processing (recall the buffer is scanned every 3
seconds). The user experience insight from this experiment is that if a node
decides to use PMDE for some reason related for example to the transaction
amounts, the deadline values do not matter in terms of the success rate. On
the other hand, if PRI is used, the node should know that this might be
disadvantaging transactions with short buffering times.

##  7\. Extensions to a network setting

In order to extend the PCN throughput maximization problem to an entire
network $G=(V,E)$ with a node set $V$ and an edge set $E$, we need to redefine
our objective and deal with other factors in our decision making that arise
when we have non-direct payments. The objective in a network setting would be
to maximize the total over all pairs of different nodes $S=\sum_{(i,j)\in
E}S_{ij}$, where $S_{ij}$ is the throughput of the channel between nodes $i$
and $j$. The control in a network setting is the policy each node follows in
each of its channels.

###  7.1. The complete graph case

The single channel model we have described so far can be immediately extended
to model a PCN that is a complete graph. In a complete graph, if we assume
that transactions are always routed along the shortest path in hop count, all
transactions will succeed or fail without needing to take a multihop route.
Then, all the channels are independent of each other, and choosing the
policies for each node that maximize the total network throughput can be
decomposed to choosing a policy for each channel separately.

###  7.2. The star graph case

Let us now consider a star graph: all the payments between peripheral nodes
have to pass through the central node. In this case, the shortest path between
a pair of nodes $i$ and $j$ is unique: from $i$ to the central node and from
the central node to $j$. Moreover, the paths between any pairs of nodes
$(i_{1},j_{1})$, $(i_{2},j_{2})$, with $i_{1},j_{1},i_{2},j_{2}$ distinct, are
non-overlapping, so the share of the total throughput that corresponds to
these paths is the sum of the throughput of each path. However, for paths
where for example $j_{1}=j_{2}$, the policy the central node applies might
also depend on whether an arriving payment arrives from $i_{1}$ or arrives
from $i_{2}$. The central node does have this knowledge and may use it to
prioritize transactions of $i_{1}$ vs of $i_{2}$, or to follow an entirely
different policy for transactions arriving from $i_{1}$ than for transactions
arriving from $i_{2}$. This shows one more factor that a scheduling policy has
to consider in a multihop network apart from the amount and deadline of each
transaction: the origin and destination of the transaction. In the single
channel, this information was only used as a binary direction of the payment.

###  7.3. The general case

Unlike the star graph, in a general multihop network there might be multiple
shortest555Shortest can be defined in terms of hops, as the cheapest in terms
of fees, or a combination thereof, as is done in Lightning. paths between a
pair of nodes. Thus, another decision to be made for each transaction is the
routing decision: which of the alternative paths to use. There are two cases:

  1. (1)

nodes use source routing for payments: the origin node determines the entire
path for the payment until it reaches the destination. In this case,
intermediate nodes do not make any routing decision; they just forward the
payment to the next predetermined hop.

  2. (2)

nodes use distributed routing: the node at each hop determines the next one.
In this case, the control decision at each node are both the scheduling and
the routing decisions.

Deadlines are also more complicated to reason about in a network setting: in a
multihop network, there are two possibilities. Transactions either have an
end-to-end deadline by which they have to have been processed or dropped, or
have a per-hop deadline by which they have to have been forwarded to the next
hop or dropped. The per-hop deadlines could be chosen from the original
sender, however choosing them in a “right” way to maximize the throughput is
not straightforward.

In conclusion, when seeking generality, a holistic approach to both routing
and scheduling is needed. We believe that stochastic modeling and optimization
techniques can be a useful tool towards making optimal decisions based on the
details of the network- and channel-level interactions In addition, as the
joint problems become more complex and do not lend themselves to analytical
solutions, reinforcement learning can assist in utilizing the insights given
by the data trail of the network’s operation to empirically derive optimal
operational parameters and policies. We leave the exploration of these
directions to future work.

##  8\. Related work

Most of the research at a network level in PCNs has focused on the routing
problem for multihop transactions. A channel rebalancing technique is studied
in (Pickhardt and Nowostawski, 2020). In (Tang et al., 2020), privacy-utility
tradeoffs in payment channel are explored, in terms of the benefit in success
rates nodes can have by revealing noisy versions of thir channel balances. In
(Wang et al., 2019), payments are categorized into “elephant” and “mice”
payments and a different routing approach is followed for each category.

The problem of taking optimal scheduling decisions for arriving payments in
the channels of a PCN has not been studied extensively in the literature. The
most relevant work to ours is probably (Sivaraman et al., 2020), which
introduces a routing approach for nodes in a PCN that aims to maximize
throughput, via packetization of transactions and a transport protocol for
congestion control in the different nodes of the network. The paper assumes
the existence of queues at the different channels, with transaction units
queued-up whenever the channel lacks the funds to process them immediately,
and a one-bit congestion signal from the routers that helps throttle the
admitted demand so that congestion and channel depletion are avoided. The
paper’s focus is on routing, and the scheduling policies used for the queues
are heuristically chosen. In contrast, we propose that queueing can be
beneficial to the overall throughput even if the transaction is feasible on
its arrival and opt for a more formal to come up with optimal policies.
Another important difference is that (Sivaraman et al., 2020) uses a fluid
model for the incoming transaction demand, while we model the demand as
distinct incoming transactions arriving as a marked point process and base our
policy decisions on the particular characteristics of the specific
transactions.

Another interesting relevant work is (Varma and Maguluri, 2020), which focuses
on throughput-maximizing routing policies: designing a path from the sender to
the recipient of each transaction so that the network throughput is maximized
and the use of on-chain rebalancing is minimized. It proposes dynamic
MaxWeight-based routing policies, uses a discrete time stochastic model and
models the channel as a double-sided queue, like the ones usually used in
ride-hailing systems. Our model in contrast is a continuous time one, focuses
more on scheduling rather than routing, and avoids certain limitations arising
from the double-sided queue assumption by modeling the channel state using two
separate queues, one for each side.

Finally, (Avarikioti et al., 2018) considers a Payment Service Provider (PSP),
a node that can establish multiple channels and wants to profit from relaying
others’ payments in the network. The goal is to define a strategy of the PSP
that will determine which of the incoming transactions to process in order to
maximize profit from fees while minimizing the capital locked in channels. The
paper shows that even a simple variant of the scheduling problem is NP-hard,
and proposes a polynomial approximation algorithm. However, the assumption
throughout the paper is that transactions have to be executed or dropped as
soon as and in the order in which they arrive, and this differentiates the
problem compared to our case.

##  9\. Conclusion

In this paper, we studied the transaction scheduling problem in PCNs. We
defined the PMDE policy and proved its optimality for constant arriving amount
distributions. We also defined a heuristic extension of PMDE as well as
heuristic policies PRI for arbitrary amount distributions, and studied in
detail the policies via experiments in our simulator. This work opens the way
for further rigorous results in problems of networking nature arising in PCNs.
In the future, we hope to see research on joint routing and scheduling
mechanisms that will be able to push the potential of PCNs to their physical
limits and make them a scalable and reliable solution for financial
applications and beyond.

## References

  * (1)
  * Rai ([n.d.]) [n.d.].  Raiden Network.  https://raiden.network/101.html
  * Aaron van Wirdum ([n.d.]) Aaron van Wirdum. [n.d.].  Understanding the Lightning Network, Part 1: Building a Bidirectional Bitcoin Payment Channel.  https://bitcoinmagazine.com/articles/understanding-the-lightning-network-part-building-a-bidirectional-payment-channel-1464710791
  * Avarikioti et al. (2018) Georgia Avarikioti, Yuyi Wang, and Roger Wattenhofer. 2018\.  Algorithmic channel design. In _29th International Symposium on Algorithms and Computation (ISAAC 2018)_ _(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 123)_ , Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao (Eds.). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 16:1–16:12.  https://doi.org/10.4230/LIPIcs.ISAAC.2018.16
  * Bagaria et al. (2019) Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. 2019.  Prism: Deconstructing the Blockchain to Approach Physical Limits. In _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ (London, United Kingdom) _(CCS ’19)_. Association for Computing Machinery, New York, NY, USA, 585–602.  https://doi.org/10.1145/3319535.3363213
  * Croman et al. (2016) Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin Gün Sirer, Dawn Song, and Roger Wattenhofer. 2016\.  On Scaling Decentralized Blockchains. In _Financial Cryptography and Data Security_ , Jeremy Clark, Sarah Meiklejohn, Peter Y.A. Ryan, Dan Wallach, Michael Brenner, and Kurt Rohloff (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 106–125.
  * Dong et al. (2018) Mo Dong, Qingkai Liang, Xiaozhou Li, and Junda Liu. 2018\.  Celer Network: Bring Internet Scale to Every Blockchain.  _CoRR_ abs/1810.00037 (2018).  arXiv:1810.00037 http://arxiv.org/abs/1810.00037
  * Grunspan et al. (2020) Cyril Grunspan, Gabriel Lehéricy, and Ricardo Pérez-Marco. 2020\.  Ant Routing scalability for the Lightning Network.  _CoRR_ abs/2002.01374 (2020).  arXiv:2002.01374 https://arxiv.org/abs/2002.01374
  * Gudgeon et al. (2020) Lewis Gudgeon, Pedro Moreno-Sanchez, Stefanie Roos, Patrick McCorry, and Arthur Gervais. 2020\.  SoK: Layer-Two Blockchain Protocols. In _Financial Cryptography and Data Security_ , Joseph Bonneau and Nadia Heninger (Eds.). Springer International Publishing, Cham, 201–226.
  * Hoenisch and Weber (2018) Philipp Hoenisch and Ingo Weber. 2018.  AODV–Based Routing for Payment Channel Networks. In _Blockchain – ICBC 2018_ , Shiping Chen, Harry Wang, and Liang-Jie Zhang (Eds.). Springer International Publishing, Cham, 107–124.
  * Lünsdorf and Scherfke ([n.d.]) Ontje Lünsdorf and Stefan Scherfke. [n.d.].  SimPy.  https://simpy.readthedocs.io
  * Machine Learning Group - ULB ([n.d.]) Machine Learning Group - ULB. [n.d.].  Credit Card Fraud Detection - Anonymized credit card transactions labeled as fraudulent or genuine.  https://www.kaggle.com/mlg-ulb/creditcardfraud
  * Malavolta et al. (2017) Giulio Malavolta, Pedro Moreno-Sanchez, Aniket Kate, and Matteo Maffei. 2017.  SilentWhispers: Enforcing Security and Privacy in Decentralized Credit Networks. In _24th Annual Network and Distributed System Security Symposium, NDSS 2017, San Diego, California, USA, February 26 - March 1, 2017_. The Internet Society.  https://www.ndss-symposium.org/ndss2017/ndss-2017-programme/silentwhispers-enforcing-security-and-privacy-decentralized-credit-networks/
  * Nakamoto (2008) Satoshi Nakamoto. 2008\.  Bitcoin: A Peer-to-Peer Electronic Cash System.  (2008).  https://bitcoin.org/bitcoin.pdf
  * Osuntokun and Fromknecht (2018) Olaoluwa Osuntokun and Conner Fromknecht. 2018.  Atomic Multipath Payments.  https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-February/000993.html
  * Papadis et al. (2018) Nikolaos Papadis, Sem Borst, Anwar Walid, Mohamed Grissa, and Leandros Tassiulas. 2018.  Stochastic Models and Wide-Area Network Measurements for Blockchain Design and Analysis. In _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications_. IEEE, 2546–2554.  https://doi.org/10.1109/INFOCOM.2018.8485982
  * Papadis and Tassiulas (2020) Nikolaos Papadis and Leandros Tassiulas. 2020.  Blockchain-Based Payment Channel Networks: Challenges and Recent Advances.  _IEEE Access_ 8 (2020), 227596–227609.  https://doi.org/10.1109/ACCESS.2020.3046020
  * Pickhardt and Nowostawski (2020) Rene Pickhardt and Mariusz Nowostawski. 2020.  Imbalance measure and proactive channel rebalancing algorithm for the Lightning Network. In _2020 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)_. 1–5.  https://doi.org/10.1109/ICBC48266.2020.9169456
  * Poon and Dryja (2016) Joseph Poon and Thaddeus Dryja. 2016.  The Bitcoin Lightning Network: scalable off-chain instant payments.  https://lightning.network/lightning-network-paper.pdf
  * Prihodko et al. (2016) Pavel Prihodko, Slava Zhigulin, Mykola Sahno, Aleksei Ostrovskiy, and Olaoluwa Osuntokun. 2016\.  Flare: An approach to routing in Lightning Network.  _Whitepaper_ (2016).
  * Rohrer et al. (2017) Elias Rohrer, Jann-Frederik Laß, and Florian Tschorsch. 2017.  Towards a Concurrent and Distributed Route Selection for Payment Channel Networks. In _Data Privacy Management, Cryptocurrencies and Blockchain Technology_ , Joaquin Garcia-Alfaro, Guillermo Navarro-Arribas, Hannes Hartenstein, and Jordi Herrera-Joancomartí (Eds.). Springer International Publishing, Cham, 411–419.
  * Roos et al. (2018) Stefanie Roos, Pedro Moreno-Sanchez, Aniket Kate, and Ian Goldberg. 2018.  Settling Payments Fast and Private: Efficient Decentralized Routing for Path-Based Transactions. In _25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-21, 2018_. The Internet Society.  http://wp.internetsociety.org/ndss/wp-content/uploads/sites/25/2018/02/ndss2018{_}09-3{_}Roos{_}paper.pdf
  * Sivaraman et al. (2020) Vibhaalakshmi Sivaraman, Shaileshh Bojja Venkatakrishnan, Kathleen Ruan, Parimarjan Negi, Lei Yang, Radhika Mittal, Giulia Fanti, and Mohammad Alizadeh. 2020.  High Throughput Cryptocurrency Routing in Payment Channel Networks. In _17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20)_. USENIX Association, Santa Clara, CA, 777–796.  https://www.usenix.org/conference/nsdi20/presentation/sivaraman
  * Tang et al. (2020) Weizhao Tang, Weina Wang, Giulia Fanti, and Sewoong Oh. 2020\.  Privacy-Utility Tradeoffs in Routing Cryptocurrency over Payment Channel Networks.  _Proc. ACM Meas. Anal. Comput. Syst._ 4, 2, Article 29 (June 2020), 39 pages.  https://doi.org/10.1145/3392147
  * Tassiulas and Ephremides (1993) Leandros Tassiulas and Anthony Ephremides. 1993.  Dynamic server allocation to parallel queues with randomly varying connectivity.  _IEEE Transactions on Information Theory_ 39, 2 (1993), 466–478.  https://doi.org/10.1109/18.212277
  * Varma and Maguluri (2020) Sushil Mahavir Varma and Siva Theja Maguluri. 2020.  Throughput Optimal Routing in Blockchain Based Payment Systems.  _CoRR_ abs/2001.05299 (2020).  arXiv:2001.05299 https://arxiv.org/abs/2001.05299
  * Wang et al. (2019) Peng Wang, Hong Xu, Xin Jin, and Tao Wang. 2019\.  Flash: Efficient Dynamic Routing for Offchain Networks. In _Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies_ (Orlando, Florida) _(CoNEXT ’19)_. Association for Computing Machinery, New York, NY, USA, 370–381.  https://doi.org/10.1145/3359989.3365411
  * Yu et al. (2018) Ruozhou Yu, Guoliang Xue, Vishnu Teja Kilari, Dejun Yang, and Jian Tang. 2018\.  CoinExpress: A Fast Payment Routing Mechanism in Blockchain-Based Payment Channel Networks. In _2018 27th International Conference on Computer Communication and Networks (ICCCN)_. 1–9.  https://doi.org/10.1109/ICCCN.2018.8487351

##  Appendix A Summary of notation

Table 1. Notation used throughout the paper Symbol | Meaning
---|---
$A$, $B$ | Nodes of the channel
$C$ | Capacity of the channel
$Q^{A}(t)$ | Balance of node $A$ on the channel at time $t$
$t_{n}^{A}$ | Arrival time of $n$-th transaction of node $A$
$v_{n}^{A}$ | Value (amount) of $n$-th transaction of node $A$
$d_{n}^{A}$ | Maximum buffering time of $n$-th transaction of node $A$
$\tau_{n}^{A}$ | Deadline expiration time of $n$-th transaction of node $A$
$D_{k}^{A}(t)$ | Remaining time until expiration of $k$-th transaction in node $A$’s buffer at time $t$
$v_{k}^{A}(t)$ | Value (amount) $k$-th transaction in node $A$’s buffer at time $t$
$K^{A}(t)$ | Number of pending transactions in node $A$’s buffer at time $t$
$T_{\text{arrival}}$ | Sequence of all transaction arrival times on both sides of the channel
$T_{\text{expiration}}$ | Sequence of all deadline expiration times on both sides of the channel
$x(t)$ | System state at time $t$ (channel balances and buffer contents)
$u(t)$ | Action taken at time $t$
$U(x(t))$ | Action space at time $t$
$\tilde{v}_{EX}^{u(t)}(t)$ | Total amount processed by the channel at time $t$
$\tilde{v}_{DR}^{u(t)}(t)$ | Total amount rejected by the channel at time $t$
$\pi$ | Control policy
$\Pi$ | Set of admissible control policies
$V_{\text{total}}(t)$ | total amount of arrivals until time $t$
$S^{\pi}(t)$ | Total channel throughput up to time $t$ under policy $\pi$
$R^{\pi}(t)$ | Total channel blockage (rejected amount) up to time $t$ under policy $\pi$
$P^{\pi}(t)$ | Amount of pending transactions at time $t$ under policy $\pi$

##  Appendix B Proof of Lemma 2

We restate Lemma 2 here for the reader’s convenience.

###### Lemma 2 0.

For every policy $\pi\in\Pi^{DE}$, there exists a policy
$\tilde{\pi}\in\Pi^{DE}$ that acts similarly to PMDE at $t=\tau_{1}$ and is
such that when the system is in state $x(0)$ at $t=0$ and policies $\pi$ and
$\tilde{\pi}$ act on it, the corresponding total rejected amount processes $R$
and $\tilde{R}$ can be constructed via an appropriate coupling of the arrival
processes so that

(17) $\tilde{R}(t)\leq R(t),t\in\tau_{1},\tau_{2},\dots$

###### Proof.

We construct $\tilde{\pi}$ and couple the blockage processes under $\pi$ and
$\tilde{\pi}$ so that (11) holds. Let the first transaction arrivals be
identical (same arrival times, values and deadlines) under both policies.
Denote the time instant when the first deadline expiration occurs by
$\tau_{1}$. Without loss of generality, let $p_{1}^{A}$ be from node $A$ to
node $B$ be one of the transactions expiring at $\tau_{1}$. We distinguish the
following cases based on the actions policy $\tilde{\pi}$ might take at
$\tau_{1}$:

  1. (1)

$\tilde{\pi}$ drops $p_{1}^{A}$ at $\tau_{1}$. The only reason why this would
happen, since $\tilde{\pi}$ mimics PMDE at $\tau_{1}$, is if $p_{1}^{A}$ is
infeasible and there is no pending feasible transaction on the opposite side.

The fact that $p_{1}^{A}$ is infeasible, since all transaction amounts are of
the same fixed value, means that all transactions in the same direction are
individually infeasible for $\pi$ as well.

The fact that there is no pending feasible transaction on the opposite side
means that $\pi$ cannot process any individual transaction in the opposite
direction.

Therefore, $\pi$ has no choice but to drop $p_{1}^{A}$, and possibly drop some
other transactions. Denote the set of these other transactions dropped by
$\pi$ at $\tau_{1}$ by $P_{1}^{d}$.

At the next expiration time $\tau_{2}$, we let $\tilde{\pi}$ operate in two
phases: in the first phase, we let $\tilde{\pi}$ drop all transactions in
$P_{1}^{d}$. So now both the states and the blockages under both $\pi$ and
$\tilde{\pi}$ are the same. In the second phase at $\tau_{2}$, let
$\tilde{\pi}$ match the action of that $\pi$ takes at $\tau_{2}$. For all
future expiration times, we let $\tilde{\pi}$ be identical to $\pi$. Then the
blockage processes under $\pi$ and $\tilde{\pi}$ are identical, and therefore
(11) holds.

  2. (2)

$p_{1}$ is individually feasible at $\tau_{1}$, and $\tilde{\pi}$ processes it
at $t=\tau_{1}$

We distinguish cases based on what policy $\pi$ does at $\tau_{1}$.

    1. (a)

At $\tau_{1}$, $\pi$ processes $p_{1}^{A}$, drops some transactions from
possibly both sides (set $P_{1}^{d}$) and processes some other transactions
from possibly both sides (set $P_{1}^{p}$). Then $R(\tau_{1})=|P_{1}^{d}|v$
and $\tilde{R}(\tau_{1})=0$.

Let $\tau_{2}$ be the next time of deadline expiration. At $\tau_{2}$, we let
$\tilde{\pi}$ operate in two phases. In the first phase, we let $\tilde{\pi}$
drop all transactions in $P_{1}^{d}$ and process all transactions in
$P_{1}^{p}$ at $\tau_{2}$, just like $\pi$ did at $\tau_{1}$. Now the states
under $\pi$ and $\tilde{\pi}$ are the same, and the same is true for the
blockages: $\tilde{R}=R=|P_{1}^{d}|v$. In the second phase, we let
$\tilde{\pi}$ be identical to $\pi$ at $\tau_{2}$. For all future expiration
times, we also let $\tilde{\pi}$ be identical to $\pi$, and both the states
and the blockages under $\pi$ and $\tilde{\pi}$ match.

    2. (b)

At $\tau_{1}$, $\pi$ drops $p_{1}^{A}$, drops some transactions (set
$P_{1}^{d}$) and processes some other transactions (set $P_{1}^{p}$). Then
$R(\tau_{1})=(|P_{1}^{d}|+1)v$ and $\tilde{R}(\tau_{1})=0$.

Let $\tau_{2}$ be the next time of deadline expiration. At $\tau_{2}$, we let
$\tilde{\pi}$ operate in two phases. In the first phase, we let $\tilde{\pi}$
drop all transactions in $P_{1}^{d}$ and attempt to process all transactions
in $P_{1}^{p}$ at $\tau_{2}$, just like $\pi$ did at $\tau_{1}$. Depending on
whether the latter is possible, we distinguish the following cases:

      1. (i)

If this is possible, then now the states under $\pi$ and $\tilde{\pi}$ are
almost the same, with the only difference being that node $A$ has processed
one more transaction from A to B under $\tilde{\pi}$. So, at that moment, for
the balances under the two policies we have
$\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A}-v,Q^{B}+v)$, and for the
blockages we have $\tilde{R}=R+v$. In the second phase at $\tau_{2}$, and at
subsequent deadline expiration times, we let $\tilde{\pi}$ match $\pi$ (and
thus the relationships between the balances and the blockages under the two
policies remain the same). This will be always possible except if at some
point $\pi$ executes some transaction from A to B and since A’s balance under
$\tilde{\pi}$ is less than under $\pi$, $\tilde{\pi}$ is not able to process
it. At that moment, we let $\tilde{\pi}$ drop that infeasible transaction and
match $\pi$ in the rest of $\pi$’s actions. Then we have
$\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A},Q^{B})$ and $\tilde{R}=R$.
For all future expiration times, we also let $\tilde{\pi}$ be identical to
$\pi$, and both the states and the blockages under $\pi$ and $\tilde{\pi}$
match.

      2. (ii)

If this is not possible, the only transaction feasible under $\pi$ but not
under $\tilde{\pi}$ must be from A to B. We let $\tilde{\pi}$ drop that
transaction and follow $\pi$ in all other transactions $\pi$ processes or
drops. So now, $\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A},Q^{B})$ and
$\tilde{R}=R$. For all future expiration times, we let $\tilde{\pi}$ be
identical to $\pi$, and both the states and the blockages under $\pi$ and
$\tilde{\pi}$ match.

  3. (3)

$p_{1}^{A}$ is individually infeasible at $\tau_{1}$, but $\tilde{\pi}$
processes $p_{1}^{A}$ at $t=\tau_{1}$ by matching it with a transaction
$\tilde{p}_{1}^{B}$ from B to A

We distinguish cases based on what policy $\pi$ does at $\tau_{1}$.

    1. (a)

At $\tau_{1}$, $\pi$ processes $p_{1}^{A}$, drops some transactions from
possibly both sides (set $P_{1}^{d}$) and processes some other transactions
from possibly both sides (set $P_{1}^{p}$). Then $R(\tau_{1})=|P_{1}^{d}|v$
and $\tilde{R}(\tau_{1})=0$. Since $p_{1}^{A}$ is individually infeasible at
$\tau_{1}$ (for both policies), the only way $\pi$ can process $p_{1}^{A}$ at
$\tau_{1}$ is if it matches it with another transaction from the opposite
direction; call the matched transaction $p_{1}^{B}\in P_{1}^{p}$.

Let $\tau_{2}$ be the next time of deadline expiration. At $\tau_{2}$, we let
$\tilde{\pi}$ operate in two phases. We distinguish cases based on what policy
$\pi$ does with transaction $\tilde{p}_{1}^{B}$ at $\tau_{1}$.

      1. (i)

$\tilde{p}_{1}^{B}\in P_{1}^{p}$ (i.e. $\tilde{p}_{1}^{B}$ is processed by
$\pi$ at $\tau_{1}$)

In this case, in the first phase at $\tau_{2}$ we let $\tilde{\pi}$ drop all
transactions in $P_{1}^{d}\setminus\\{p_{1}^{B}\\}$ and process all
transactions in $P_{1}^{p}$ at $\tau_{2}$, just like $\pi$ did at $\tau_{1}$.
Now the states under $\pi$ and $\tilde{\pi}$ are the same, and the same is
true for the blockages: $\tilde{R}=R=|P_{1}^{d}|v$. In the second phase, we
let $\tilde{\pi}$ be identical to $\pi$ at $\tau_{2}$. For all future
expiration times, we also let $\tilde{\pi}$ be identical to $\pi$, and both
the states and the blockages under $\pi$ and $\tilde{\pi}$ match.

      2. (ii)

$\tilde{p}_{1}^{B}\notin P_{1}^{p}$ and $\tilde{p}_{1}^{B}\in P_{1}^{d}$ (i.e.
$\tilde{p}_{1}^{B}$ is dropped by $\pi$ at $\tau_{1}$, so it is not in B’s
buffer anymore under $\pi$ at $\tau_{2}$)

In this case, in the first phase at $\tau_{2}$ we let $\tilde{\pi}$ drop all
transactions in $P_{1}^{d}$, drop also $p_{1}^{B}$ from $P_{1}^{p}$, and
process all transactions in $P_{1}^{p}\setminus\\{p_{1}^{B}\\}$ at $\tau_{2}$.
Now the states under $\pi$ and $\tilde{\pi}$ are the same, and the same is
true for the blockages: $\tilde{R}=R=(|P_{1}^{d}|+1)v$. In the second phase,
we let $\tilde{\pi}$ be identical to $\pi$ at $\tau_{2}$. For all future
expiration times, we also let $\tilde{\pi}$ be identical to $\pi$, and both
the states and the blockages under $\pi$ and $\tilde{\pi}$ match.

      3. (iii)

$\tilde{p}_{1}^{B}\notin P_{1}^{p}$ and $\tilde{p}_{1}^{B}\notin P_{1}^{d}$
(i.e. $\tilde{p}_{1}^{B}$ is neither processed nor dropped by $\pi$ at
$\tau_{1}$, so it is still in B’s buffer under $\pi$ at $\tau_{2}$)

In this case, in the first phase at $\tau_{2}$ we let $\tilde{\pi}$ drop all
transactions in $P_{1}^{d}$ and attempt to process all transactions in
$P_{1}^{p}$ at $\tau_{2}$, just like $\pi$ did at $\tau_{1}$.

Depending on whether the latter is possible, we distinguish the following
cases:

        1. (A)

If this is possible, then now the states under $\pi$ and $\tilde{\pi}$ are
almost the same, with the only difference being that node $A$ has processed
one more transaction ($\tilde{p}_{1}^{B}$) from B to A under $\tilde{\pi}$.
So, at that moment, we have
$\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A}+v,Q^{B}-v)$ and
$\tilde{R}=R-v$. In the second phase at $\tau_{2}$, and at subsequent deadline
expiration times, we let $\tilde{\pi}$ match $\pi$ (and thus the relationships
between the balances and the blockages under the two policies remain the
same). This will be always possible except if at some point $\pi$ executes
some transaction from B to A and since B’s balance under $\tilde{\pi}$ is less
than under $\pi$, $\tilde{\pi}$ is not able to process it. At that moment, we
let $\tilde{\pi}$ drop that infeasible transaction and match $\pi$ in the rest
of $\pi$’s actions. Then we have
$\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A},Q^{B})$ and $\tilde{R}=R$.
For all future expiration times, we let $\tilde{\pi}$ be identical to $\pi$,
and both the states and the blockages under $\pi$ and $\tilde{\pi}$ match.

        2. (B)

If this is not possible, the only transaction feasible under $\pi$ but not
under $\tilde{\pi}$ must be from B to A (so in the same direction as
$p_{1}^{B}$, or $p_{1}^{B}$ itself). We let $\tilde{\pi}$ drop $p_{1}^{B}$. So
now, $\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A},Q^{B})$ and
$\tilde{R}=R$.

In the second phase, we let $\tilde{\pi}$ follow $\pi$ in all other
transactions $\pi$ processes or drops at $\tau_{2}$. For all future expiration
times, we let $\tilde{\pi}$ be identical to $\pi$, and both the states and the
blockages under $\pi$ and $\tilde{\pi}$ match.

    2. (b)

At $\tau_{1}$, $\pi$ drops $p_{1}^{A}$, drops some transactions from possibly
both sides (set $P_{1}^{d}$) and processes some other transactions from
possibly both sides (set $P_{1}^{p}$). Then $R(\tau_{1})=(|P_{1}^{d}|+1)v$ and
$\tilde{R}(\tau_{1})=0$.

Let $\tau_{2}$ be the next time of deadline expiration. At $\tau_{2}$, we let
$\tilde{\pi}$ operate in two phases. We distinguish cases based on what policy
$\pi$ does with transaction $\tilde{p}_{1}^{B}$ at $\tau_{1}$.

      1. (i)

$\tilde{p}_{1}^{B}\in P_{1}^{p}$ (i.e. $\tilde{p}_{1}^{B}$ is processed by
$\pi$ at $\tau_{1}$)

In this case, in the first phase at $\tau_{2}$ we let $\tilde{\pi}$ drop all
transactions in $P_{1}^{d}$ and process all transactions in
$P_{1}^{p}\setminus\\{\tilde{p}_{1}^{B}\\}$, just like $\pi$ did at
$\tau_{1}$. Depending on whether the latter is possible, we distinguish the
following cases:

        1. (A)

If this is possible, then now the states under $\pi$ and $\tilde{\pi}$ are
almost the same, with the only difference being that node $A$ has processed
one more transaction ($p_{1}^{A}$) from A to B under $\tilde{\pi}$. So, at
that moment, we have
$\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A}-v,Q^{B}+v)$ and
$\tilde{R}=R+v$. In the second phase at $\tau_{2}$, and at subsequent deadline
expiration times, we let $\tilde{\pi}$ match $\pi$ (and thus the relationships
between the balances and the blockages under the two policies remain the
same). This will be always possible except if at some point $\pi$ executes
some transaction from A to B and since A’s balance under $\tilde{\pi}$ is less
than under $\pi$, $\tilde{\pi}$ is not able to process it. At that moment, we
let $\tilde{\pi}$ drop that infeasible transaction and match $\pi$ in the rest
of $\pi$’s actions. Then we have
$\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A},Q^{B})$ and $\tilde{R}=R$.
For all future expiration times, we let $\tilde{\pi}$ be identical to $\pi$,
and both the states and the blockages under $\pi$ and $\tilde{\pi}$ match.

        2. (B)

If this is not possible, the only transaction feasible under $\pi$ but not
under $\tilde{\pi}$ must be from A to B (so in the same direction as
$p_{1}^{A}$, or $p_{1}^{A}$ itself). We let $\tilde{\pi}$ drop that
transaction. So now, $\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A},Q^{B})$
and $\tilde{R}=R$.

In the second phase, we let $\tilde{\pi}$ follow $\pi$ in all other
transactions $\pi$ processes or drops at $\tau_{2}$. For all future expiration
times, we let $\tilde{\pi}$ be identical to $\pi$, and both the states and the
blockages under $\pi$ and $\tilde{\pi}$ match.

      2. (ii)

$\tilde{p}_{1}^{B}\notin P_{1}^{p}$ and $\tilde{p}_{1}^{B}\in P_{1}^{d}$ (i.e.
$\tilde{p}_{1}^{B}$ is dropped by $\pi$ at $\tau_{1}$, so it is not in B’s
buffer anymore under $\pi$ at $\tau_{2}$)

In this case, in the first phase at $\tau_{2}$ we let $\tilde{\pi}$ drop all
transactions in $P_{1}^{d}$, and process all transactions in $P_{1}^{p}$. Now
the states (balances and buffer contents) under $\pi$ and $\tilde{\pi}$ are
the same. For the blockages, we have: $\tilde{R}=R-2v\leq R$. In the second
phase, we let $\tilde{\pi}$ be identical to $\pi$ at $\tau_{2}$. For all
future expiration times, we also let $\tilde{\pi}$ be identical to $\pi$, and
both the states and the blockages under $\pi$ and $\tilde{\pi}$ match. So (11)
holds for all expiration times.

      3. (iii)

$\tilde{p}_{1}^{B}\notin P_{1}^{p}$ and $\tilde{p}_{1}^{B}\notin P_{1}^{d}$
(i.e. $\tilde{p}_{1}^{B}$ is neither processed nor dropped by $\pi$ at
$\tau_{1}$, so it is still in B’s buffer under $\pi$ at $\tau_{2}$)

In this case, in the first phase at $\tau_{2}$ we let $\tilde{\pi}$ drop all
transactions in $P_{1}^{d}$ and attempt to process all transactions in
$P_{1}^{p}$ at $\tau_{2}$, just like $\pi$ did at $\tau_{1}$. This will be
always possible, as the only difference in the states under $\pi$ and
$\tilde{\pi}$ is that B’s buffer contains $\tilde{p}_{1}^{B}$ under $\pi$ but
not under $\tilde{\pi}$. In terms of executed transactions, $\tilde{\pi}$
compared to $\pi$ has additionally processed the pair
$\left(p_{1}^{A},\tilde{p}_{1}^{B}\right)$ and pairs have no net effect on the
balances. So $\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A},Q^{B})$ and
$\tilde{R}=R-v\leq R$.

In the second phase at $\tau_{2}$, and at subsequent deadline expiration
times, we let $\tilde{\pi}$ match $\pi$ (and thus the relationships between
the balances and the blockages under the two policies remain the same). This
will be always possible except if at some point $\pi$ decides to execute or
drop $\tilde{p}_{1}^{B}$ that is still in B’s buffer under $\pi$ but not under
$\tilde{\pi}$.

        1. (A)

If $\pi$ drops $\tilde{p}_{1}^{B}$, then the states under $\pi$ and
$\tilde{\pi}$ completely match (balances and buffer contents), and we have
$\tilde{R}=R-v\leq R$. At that moment, and for all future expiration times, we
let $\tilde{\pi}$ be identical to $\pi$, and thus both the states and the
blockages under $\pi$ and $\tilde{\pi}$ match.

        2. (B)

If $\pi$ processes $\tilde{p}_{1}^{B}$, then $\tilde{\pi}$ cannot do the same,
and thus $\pi$ has processed one more transaction from B to A than
$\tilde{\pi}$. So we have
$\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A}-v,Q^{B}+v)$, same buffer
contents, and $\tilde{R}=R-v\leq R$.

From then on, we let $\tilde{\pi}$ match $\pi$ for as long as this is possible
(and thus the relationships between the balances and the blockages under the
two policies remain the same). The only reason why $\tilde{\pi}$ at some point
might not be able to match $\pi$ is if it $\pi$ executes a transaction from B
to A that $\tilde{\pi}$ cannot because B’s balance under $\tilde{\pi}$ is less
than under $\pi$. At that time, we let $\tilde{\pi}$ drop that transaction and
match $\pi$ in all its other actions. So now
$\left(\tilde{Q}^{A},\tilde{Q}^{B}\right)=(Q^{A},Q^{B})$, the buffer contents
are the same, and $\tilde{R}=R$. For all future expiration times, we let
$\tilde{\pi}$ be identical to $\pi$, and both the states and the blockages
under $\pi$ and $\tilde{\pi}$ match.

Thus, in all possible cases, it is possible to couple $\tilde{\pi}$ with $\pi$
so that (2) is satisfied. This concludes the proof of the lemma. ∎

##  Appendix C Proof of Theorem 4

We restate Theorem 4 here for the reader’s convenience.

###### Theorem 4 0.

For a single channel between nodes $A$ and $B$ with capacity $C$, and Poisson
transaction arrivals with rates $\lambda_{A}\neq\lambda_{B}$ and fixed amounts
equal to $v$, the maximum possible success rate of the channel is

(18)
$SR_{\text{opt}}=\lambda_{A}\left(1-\frac{\lambda_{B}/\lambda_{A}-1}{(\lambda_{B}/\lambda_{A})^{\tilde{C}+1}-1}\right)+\lambda_{B}\left(1-\left(\frac{\lambda_{B}}{\lambda_{A}}\right)^{\tilde{C}}\frac{\lambda_{B}/\lambda_{A}-1}{(\lambda_{B}/\lambda_{A})^{\tilde{C}+1}-1}\right)$

where $\tilde{C}=\lfloor\frac{C}{v}\rfloor$.

When $\lambda_{A}=\lambda_{B}=\lambda$, the maximum possible success rate is

(19) $SR_{\text{opt}}=\frac{2\lambda\tilde{C}}{\tilde{C}+1}$

###### Proof.

The maximum possible success rate of the channel is the success rate under the
optimal policy PFI.

We focus on the balance of node $A$, which has an initial value of $b_{A}$.
Over time, it forms a continuous-time, time-homogeneous Markov chain that is a
birth-death process with states $\\{0,1,\dots,C\\}$. Since all transactions
are of amount $v$, only the states that are a multiple of $v$ away from
$b_{A}$ are reachable. Therefore, we reduce this Markov chain to another one
with fewer states: $\\{0,1,\dots,\tilde{C}\\}$, where $\tilde{C}=\lfloor
C/v\rfloor$ and state $k$ in the new Markov chain corresponds to state
$\bmod(b_{A},v)+kv$ in the initial Markov chain, $k=1,\dots,\tilde{C}-1$.

The state transition diagram of the new Markov chain is the following:

Let $\pi=(\pi_{1},\dots,\pi_{\tilde{C}})$ be the stationary distribution.

The long-term rejection rate $RR_{\text{opt}}$ (fraction of rejected
transactions) and success rate $SR_{\text{opt}}$ of the channel can be
calculated as follows:

(20) $RR_{\text{opt}}=\lambda_{A}\pi_{0}+\lambda_{B}\pi_{C}$

(21) $\displaystyle SR_{\text{opt}}$
$\displaystyle=\lambda_{A}+\lambda_{B}-RR_{\text{opt}}$ (22)
$\displaystyle=\lambda_{A}(1-\pi_{0})+\lambda_{B}(1-\pi_{\tilde{C}})$

Therefore, we need to calculate the stationary distribution. The local balance
equations are:

(23) $\lambda_{B}\pi_{k}=\lambda_{A}\pi_{k+1}$

So
$\pi_{k+1}=\frac{\lambda_{B}}{\lambda_{A}}\pi_{k}=\left(\frac{\lambda_{B}}{\lambda_{A}}\right)^{k}\pi_{0},~{}k=0,\dots,\tilde{C}-1$.

The normalization constraint hence yields

(24)
$\sum_{k=0}^{\tilde{C}}\pi_{k}=1\implies\pi_{0}\sum_{k=0}^{\tilde{C}}\left(\frac{\lambda_{B}}{\lambda_{A}}\right)^{k}=1$

We now distinguish between the two cases:
If $\lambda_{A}\neq\lambda_{B}$, then:

(25)
$\pi_{0}=\frac{\lambda_{B}/\lambda_{A}-1}{(\lambda_{B}/\lambda_{A})^{\tilde{C}+1}-1}$

and

(26)
$\pi_{k}=\left(\frac{\lambda_{B}}{\lambda_{A}}\right)^{k}\pi_{0},~{}k=1,\dots,\tilde{C}$

If $\lambda_{A}=\lambda_{B}=\lambda$, then

(27) $\pi_{k}=\frac{1}{\tilde{C}+1},~{}k=0,1,\dots,\tilde{C}$

Plugging the stationary distribution into the success rate formula completes
the proof. ∎