- From: Melvin Carvalho <melvincarvalho@gmail.com>
- Date: Sun, 15 Jan 2012 19:35:12 +0100
- To: Web Payments <public-webpayments@w3.org>
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