  Credit networks rely on decentralized, pairwise trust relationships
(channels) to exchange money or goods. Credit networks arise naturally in many
financial systems, including the recent construct of payment channel networks
in blockchain systems. An important performance metric for these networks is
their transaction throughput. However, predicting the throughput of a credit
network is nontrivial. Unlike traditional communication channels, credit
channels can become imbalanced; they are unable to support more transactions in
a given direction once the credit limit has been reached. This potential for
imbalance creates a complex dependency between a network's throughput and its
topology, path choices, and the credit balances (state) on every channel. Even
worse, certain combinations of these factors can lead the credit network to
deadlocked states where no transactions can make progress. In this paper, we
study the relationship between the throughput of a credit network and its
topology and credit state. We show that the presence of deadlocks completely
characterizes a network's throughput sensitivity to different credit states.
Although we show that identifying deadlocks in an arbitrary topology is
NP-hard, we propose a peeling algorithm inspired by decoding algorithms for
erasure codes that upper bounds the severity of the deadlock. We use the
peeling algorithm as a tool to compare the performance of random topologies as
well as to aid in the synthesis of topologies robust to deadlocks.
