In una rete di mutuo, come programmeresti un giubileo automatico?

5

Potrebbe essere necessaria una piccola spiegazione. Intendo il mutuo credito come è definito qui :

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

Immagina di avere una rete di account. Ognuno inizia a zero e qualsiasi account può estendere una linea di credito limitata a qualsiasi altro account. Il mio saldo totale sarebbe solo la somma di ciò che gli altri "devono" a me, meno la somma di ciò che devo agli altri.

Le linee di credito possono essere rappresentate con una semplice tabella. In pseudo-codice per un qualche tipo di 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
}

Spero di rendere il concetto più chiaro: il "destinatario" sarebbe in genere la persona che sta ricevendo "pagato" in una transazione; "emittente" è la persona "pagante". Ad esempio:

  • Persone A richiede un servizio dalla persona B
  • B accetta ed estende una linea di credito ad A
  • Un errore da IOU a B

A un certo punto questi debiti possono o non possono essere regolati in alcune valute del mondo reale, ma l'idea è che alla fine si annullino a vicenda, direttamente o indirettamente.

Userò "$" per rappresentare la valuta, sebbene, ovviamente, le unità siano arbitrarie. Immagina che ...

  • Bob deve $ 20 a Sally
  • Sally deve $ 20 a Joe
  • Joe deve $ 20 a Bob

È chiaro che qui non c'è alcun debito reale e loro non devono nulla a nessuno.

Quindi, come potresti rilevare questi tipi di cicli in un bilancio e poi eliminarli? Questo è un problema per la teoria dei grafi? Immagino che questo possa essere rappresentato come un grafico di rete diretto. La mia conoscenza qui è molto limitata, ma capisco che è possibile rilevare cicli con l'algoritmo di componenti strongmente connessi di Tarjan , sebbene ciò non sembra offrire molto aiuto, specialmente quando questi cicli diventano più grandi. Ho anche pensato che, forse, i percorsi più brevi potevano essere scricchiolanti al momento di una transazione, con i reciproci di "debiti" in sospeso rappresentati come ponderazioni / distanze.

Penso che Ripple pay abbia fatto qualcosa del genere, ma ho difficoltà a trovare un precedente.

    
posta Greg 29.11.2014 - 11:15
fonte

1 risposta

1

Il trio di IOU che hai dato come esempio, che si bilanciano a vicenda, fino a zero debito se preso nel suo insieme, evoca il tipico contro-esempio di un ciclo (patologico) isolato che sconfigge il conteggio dei riferimenti usato negli allocatori di memoria : la semplice esistenza di un riferimento (diretto) tra un nodo e l'altro impedisce che questi vengano deallocati; perché ognuno con un conteggio di usi maggiore di zero (1).

Un modo classico e comune di raccolta di tali cicli (tuttavia, per superare i limiti del conteggio dei riferimenti ingenui) è una procedura "mark-and-sweep" a due fasi: in primo luogo, si contrassegnano tutti i nodi come " morto". Quindi, da qualche nodo radice (ad esempio, Jack), segui tutti i riferimenti in modo ricorsivo, usando un hop-by-hop da un nodo a un altro e deselezionando ("rivivi") i nodi così raggiunti dopo ogni hop, fino a quando tutti i riferimenti sono stati seguiti esattamente una volta.

Alla fine, alcuni riferimenti non saranno mai stati seguiti (perché il loro nodo di partenza non è raggiungibile da nessun altro in primo luogo), e i nodi a cui puntano, saranno quindi contrassegnati come "morti". Proprio come per il tuo Bob, Joe, Sally trio.

Naturalmente, nel tuo caso, dobbiamo modificare leggermente le nozioni e definire un "tipo di riferimento" per analogia con la nozione di classe di equivalenza :

per esempio, per la classe di equivalenza / tipo di riferimento "ha un IOU di $ 20 su qualcun altro", ciascuno dei tre Bob, Sally e Joe ha esattamente uno di questi "riferimenti".

Quindi, credo che tu possa sfruttare l'algoritmo mark-and-sweep, al costo di mantenere, per ogni nodo, l'insieme di classi di equivalenza (distinte) "ha un IOU di $ X su qualcun altro" che usa , insieme ai marker corrispondenti (1 bit per nodo e per classe di equivalenza che utilizza è sufficiente) e eseguendolo, mark-and-sweep, tante volte sull'intero grafico in quanto ci sono (equivalenti) classi di equivalenza in uso, in totale (*)

Questa potrebbe non essere una buona soluzione (del tutto) se ci sono molte quantità possibili e distinte di IOU tra due nodi qualsiasi, anche se ... diciamo, se il tuo grafico è già di milioni di nodi e i tuoi IOU distinti sono per esempio, trovate arbitrariamente tra $ 1 e $ 1.000.000 con una distribuzione normale , per esempio.

'Spero che questo aiuti.

(*) E.g.,

Bob deve a Joe $ 20; Jack deve Pete $ 15; Joe deve Pete $ 30 e Sally $ 20; Pete deve Bob $ 20 e Sally $ 15; Sally deve Jack $ 15 e Pete $ 20:

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

Jack                            (15)

Joe                             (30)    (20)

Pete    (20)                            (15)

Sally           (15)            (20)

Dopo la riduzione:

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

Jack

Joe                             (30)

Pete

Sally

(Restante solo: Joe deve Pete $ 30)

    
risposta data 11.09.2015 - 11:15
fonte

Leggi altre domande sui tag