Fwd: [Ripple] Ripple's settlement algorithm, compared to Favorati

FYI


---------- Forwarded message ----------
From: Martin Brock <restonthewind@gmail.com>
Date: 15 January 2012 17:08
Subject: [Ripple] Ripple's settlement algorithm, compared to Favorati
To: Ripple Project <rippleusers@googlegroups.com>


I wish to discuss possible differences between Favorati and Ripple.
The discussion involves technical details that will interest few
people other than Ryan, and Ryan thus far hasn't responded to an
email. He has worked on this project for many years, so it can't
always have his attention. If anyone knows Ryan personally, I'll
appreciate an introduction. This wiki is my only other prospect, so
here goes.

First, I'll introduce some nomenclature that Ripple doesn't use.

At Favorati, "respect" is the inverse of "trust". If you trust me,
then I respect you or owe you respect, i.e. I owe you a favor. I have
trust, and you have respect. When you have respect, you may spend it.

The respect you may spend with me has four forms, 1) respect that I
owe you directly, 2) respect that I owe you indirectly, 3) respect
that others owe you and 4) your self-respect.

1) If you do me a favor, I owe you a favor in return. You have my
direct respect. When you spend this respect by accepting a favor from
me, I return your favor; therefore, my obligation to you decreases,
and you do not owe a favor as a consequence.

2) If I respect someone (who respects someone who respects
someone ...) who respects you, I respect you indirectly. You have my
indirect respect. You may trigger a chain of settlements by asking
your respectors (to ask their respectors ...) to ask me to do you a
favor. You do not owe a favor in return, and everyone in the chain
reduces an obligation to someone in the chain.

3) A mutual friend owes you a favor, and I prefer the friend's respect
to yours. You ask your friend to respect me instead of you, and I do
you a favor. You do not owe me a favor in return. The friend no longer
owes you a favor. The friend owes me a favor instead.

4) You spend your self-respect when I do you a favor and you owe me a
favor in return.


1) and 2) decrease the total respect in the system (the "money
supply"). 3) does not change total respect. 4) increases total
respect.


With this introduction, I can describe Favorati's settlement
algorithm.

Mary wants a $10 favor from Luke.

1) Spend Luke's direct and indirect respect for Mary. Spend less
recent respect before spending more recent respect. The calculation of
indirect respect is recursive. The recursive procedure follows spends
less recent respect first at each level. The procedure potentially
searches the entire network, but if the server caches the network in
RAM, this search is not a problem. The algorithm is O(n) or
thereabouts, so a dedicated server can search millions of
relationships in seconds.

2) If 1) is less than $10, transfer Mary's respect to Luke,
transferring stronger respect before transferring weaker respect.

A friend's respect for Mary is "stronger" (from Luke's perspective) if
Luke's willingness to increase his trust for the friend is greater.
Luke expresses this willingness in a trust policy recorded at
Favorati.net. If Luke is unwilling to accept Mary's respect, no
transfer occurs.

Unlike 1), Favorati does not "ripple" transfers of respect, i.e. if
Paul owes Peter and Peter owes Mary, Favorati does not transfer Paul's
respect for Peter to Luke. Automatic settlement only transfers Peter's
direct respect for Mary.

Indirect transfers could increase Mary's spendable respect and also be
preferable to Luke if Luke trusts Paul more than Peter; however, an
indirect transfer could create a circuit in the trust network, and the
settle algorithm assumes no circuits. I'd like to ripple here, but at
this point, I need an algorithm that cannot create a circuit, and I
haven't thought enough about it. Avoiding circuits when the network is
decentralized is also a problem.

3) If 1) + 2) is less than $10,
Mary owes Luke the balance, i.e. she spends her self-respect and thus
owes Luke a favor in return. Luke's trust policy must permit it.


I can now discuss possible differences between Ripple and Favorati.

In 1), Ripple's order of path traversals could differ. Ripple could
use an order other than least recent first.

In 2), Ripple's order of transfers could differ.

In 2), Ripple could ripple transfers.


I haven't read Ripple's code yet, but the wiki discusses two
transaction algorithms, a naive approach and a more sophisticated
approach.

http://ripple-project.org/Implementation/Transactions

Presumably, the wiki refers to the ripple in 1), since it refers to a
target. A ripple in 2) has no specific target. It seeks Mary's respect
from any member in Luke's trust policy. Both algorithms differ from
the approach in 1).

The naive approach uses the shortest path from Luke to Mary, followed
by the next shortest path and so on. In general, this approach is
computationally intractable. The shortest path problem has an
efficient solution, but finding paths in order by length does not. The
longest path problem is NPC.

http://en.wikipedia.org/wiki/Longest_path_problem

Also, I'm not sure what the wiki means by "shortest". Apparently,
based on the more sophisticated approach, "shortest" refers to
geographical distance between members, and the shortest path algorithm
uses a heuristic, i.e. it orders nodes at each level by distance to
Mary as the crow flies. I'm a GIS guy in my day job, and I've used
this heuristic in an implementation of Dijkstra's shortest path
algorithm in other contexts; however, Favorati's settlement algorithm
does not seek a shortest path.

I don't fully understand the more sophisticated approach; however,
minimizing geographic path length or distance to the target in 1)
confuses me generally. This approach seems to consume more local
respect first, leaving more distant respect. If the wiki refers to a
ripple in 2), minimizing geographic distance makes more sense, since
the algorithm then transfers more local respect to Luke before
transferring more remote respect.

If anyone got this far, you have my respect.

--
You received this message because you are subscribed to the Google
Groups "Ripple Project" group.
To post to this group, send email to rippleusers@googlegroups.com.
To unsubscribe from this group, send email to
rippleusers+unsubscribe@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/rippleusers?hl=en.

Received on Sunday, 15 January 2012 18:36:00 UTC