In a mutual credit network, how would you program an automatic jubilee?

Question

A little explanation might be needed. I mean mutual credit the way that it's defined here:

a type of alternative currency in which the currency used in a transaction can be created at the time of the transaction

Imagine you have a network of accounts. Each starts out at zero and any account can extend a limited line of credit to any other account. My total balance would just be the sum of what others "owe" to me, minus the sum of what I owe to others.

Lines of credit can be represented with a simple table. In pseudo-code for some kind of ORM:

type LineOfCredit struct {
    IOURecipient  string, // Account ID of IOU recipient
    IOUIssuer     string, // Account ID of IOU issuer
    Owed          int,    // Amount owed to IOU recipient
    Limit         int,    // Maximum IOU amount
}

To hopefully make the concept clearer: The "recipient" would generally be the person getting "paid" in a transaction; the "issuer" is the person "paying." For example:

• Persons A requests service from person B
• B agrees and extends a line of credit to A
• A issues IOU to B

These debts may or may not be settled in some real-world currency, at some point, but the idea is that they eventually cancel out one another, either directly or indirectly.

I'll use "$" to represent the currency, though, of course, the units are arbitrary. Imagine that...

• Bob owes $20 to Sally
• Sally owes $20 to Joe
• Joe owes $20 to Bob

It's clear that there's no actual debt here and they don't owe one another anything.

So, how would you detect these kinds of cycles in a balance sheet and then eliminate them? Is this a problem for graph theory? I imagine this can be represented as a directed network graph. My knowledge here is very limited, but I understand it's possible to detect cycles with Tarjan's strongly connected components algorithm, though that doesn't seem to offer much help, especially as those cycles get larger. I also thought that, maybe, shortest-paths could be crunched at the time of a transaction, with the reciprocals of outstanding "debts" represented as edge-weights/distances.

I think Ripple pay possibly did something like this, but I'm having trouble finding a precedent.

Answer 1

The IOU trio you gave as an example, who are balancing each other out, down to zero debt when taken as a whole, evokes the typical counter-example of a (pathological) isolated cycle that defeats reference counting used in memory allocators: the mere existence of a (directed) reference between one node and another prevents those to be deallocated; because each having a use count greater than zero (1).

A classic, common way to garbage-collect such cycles nonetheless (to overcome the limitations of naive reference counting) is by a two-phase "mark-and-sweep" procedure: first, you mark all the nodes as being "dead". Then, from some root node (say, Jack), you recursively follow all the references, using a hop-by-hop from one node to another, and unmark ("revive") the nodes thus-reached after each hop, until all the references have been followed exactly once.

Eventually, some references will have never been followed (because their starting node is unreachable from any other in the first place), and the nodes they point to, will thus still be marked "dead". Just as for your Bob, Joe, Sally trio.

Of course, in your case, we must tweak the notions a bit and define a "reference type" by analogy with the notion of equivalence class:

say, for the equivalence class / reference type "has an IOU of $20 on someone else", each of the three Bob, Sally, and Joe has exactly one such "reference".

So, I believe you can leverage the mark-and-sweep algorithm, at the cost of maintaining, for each node, the set of (distinct) equivalence classes "has an IOU of $X on someone else" that it uses, along with the corresponding markers (1 bit per node and per equivalence class it uses is enough) and running it, mark-and-sweep, as many times over your entire graph as there are (distinct) equivalence classes in use, in total (*)

This may not be a good solution (at all) if there are many possible, distinct amounts of IOUs between any two nodes, though... say, if your graph is already millions of nodes-wide and your distinct IOUs are arbitrarily found in the range $1 to $1,000,000 with a normal distribution, for instance.

'Hope this helps.

(*) E.g.,

Bob owes Joe $20; Jack owes Pete $15; Joe owes Pete $30 and Sally $20; Pete owes Bob $20 and Sally $15; Sally owes Jack $15 and Pete $20:

[IOU...]Bob     Jack    Joe     Pete    Sally
Bob                     (20)

Jack                            (15)

Joe                             (30)    (20)

Pete    (20)                            (15)

Sally           (15)            (20)

After reduction:

[IOU...]Bob     Jack    Joe     Pete    Sally
Bob         

Jack

Joe                             (30)

Pete

Sally

(Only remaining: Joe owes Pete $30)