Em uma rede de crédito mútuo, como você programaria um jubileu automático?

5

Uma pequena explicação pode ser necessária. Quero dizer, crédito mútuo da maneira como é definido aqui :

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

Imagine que você tenha uma rede de contas. Cada um começa com zero e qualquer conta pode estender uma linha limitada de crédito para qualquer outra conta. Meu saldo total seria apenas a soma do que os outros "devem" a mim, menos a soma do que devo aos outros.

Linhas de crédito podem ser representadas com uma tabela simples. Em pseudo-código para algum tipo de 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
}

Espero que torne o conceito mais claro: o "destinatário" geralmente seria a pessoa que recebe "pagamento" em uma transação; o "emissor" é a pessoa "pagando". Por exemplo:

  • Pessoas A solicita serviço da pessoa B
  • B concorda e estende uma linha de crédito para A
  • Um problema sai para B

Essas dívidas podem ou não ser liquidadas em alguma moeda do mundo real, em algum momento, mas a ideia é que elas eventualmente se anulem umas às outras, direta ou indiretamente.

Usarei "$" para representar a moeda, embora, é claro, as unidades sejam arbitrárias. Imagine isso ...

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

É claro que não há dívida real aqui e eles não devem nada um ao outro.

Então, como você detectaria esses tipos de ciclos em um balanço e depois os eliminaria? Isso é um problema para a teoria dos grafos? Eu imagino que isso pode ser representado como um gráfico de rede direcionado. Meu conhecimento aqui é muito limitado, mas eu entendo que é possível detectar ciclos com algoritmo de componentes strongmente conectados do Tarjan , apesar de que não parece oferecer muita ajuda, especialmente à medida que esses ciclos aumentam. Eu também pensei que, talvez, os caminhos mais curtos pudessem ser triturados no momento de uma transação, com os recíprocos de "dívidas" pendentes representados como pesos de borda / distâncias.

Eu acho que pagamento do Ripple possivelmente fez algo assim, mas estou com dificuldades para encontrar um precedente.

    
por Greg 29.11.2014 / 11:15
fonte

1 resposta

1

O trio IOU que você deu como exemplo, que está equilibrando um ao outro, até zero dívida quando tomado como um todo, evoca o típico contra-exemplo de um ciclo isolado (patológico) que derrota a contagem de referência usada em alocadores de memória : a mera existência de uma referência (dirigida) entre um nó e outro impede que estes sejam desalocados; porque cada um tendo uma contagem de uso maior que zero (1).

Uma maneira clássica e comum de coletar esses ciclos de maneira incorreta (superar as limitações da contagem ingênua de referências) é por um procedimento de "marcar e varrer" em duas fases: primeiro, marcar todos os nós como " morto". Então, de algum nó raiz (digamos, Jack), você recursivamente segue todas as referências, usando um salto a salto de um nó para outro, e desmarca ("revive") os nós assim alcançados após cada salto, até que todos as referências foram seguidas exatamente uma vez.

Eventualmente, algumas referências nunca terão sido seguidas (porque o nó inicial é inacessível de qualquer outro em primeiro lugar), e os nós para os quais eles apontam continuarão marcados como "mortos". Assim como para o seu Bob, Joe, Sally trio.

É claro que, no seu caso, precisamos ajustar um pouco as noções e definir um "tipo de referência" por analogia com a noção de classe de equivalência :

digamos, para a classe de equivalência / tipo de referência "tem um IOU de $ 20 em outra pessoa", cada um dos três Bob, Sally e Joe tem exatamente uma "referência".

Então, acredito que você pode aproveitar o algoritmo de marca e varredura, com o custo de manter, para cada nó, o conjunto de classes de equivalência (distintas) "tem um IOU de $ X em outra pessoa" que ele usa , juntamente com os marcadores correspondentes (1 bit por nó e por classe de equivalência que usa é suficiente) e executá-lo, marcar e varrer, tantas vezes em todo o gráfico quanto houver classes de equivalência (distintas) em uso, no total (*)

Isso pode não ser uma boa solução (se possível) se houver muitas quantidades possíveis de IOUs entre dois nós, embora ... digamos, se seu gráfico já tiver milhões de nós e suas IOUs distintas forem arbitrariamente encontrado no intervalo de US $ 1 a US $ 1.000.000 com uma distribuição normal , por exemplo.

'Espero que isso ajude.

(*) Por exemplo,

Bob deve a Joe $ 20; Jack deve Pete $ 15; Joe deve Pete $ 30 e Sally $ 20; Pete deve a Bob $ 20 e a 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)

Após a redução:

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

Jack

Joe                             (30)

Pete

Sally

(apenas o restante: Joe deve Pete $ 30)

    
por 11.09.2015 / 11:15
fonte