From lf-lists at mattcorallo.com Wed Sep 1 05:33:23 2021 From: lf-lists at mattcorallo.com (Matt Corallo) Date: Tue, 31 Aug 2021 22:33:23 -0700 Subject: [Lightning-dev] Do we really want users to solve an NP-hard problem when they wish to find a cheap way of paying each other on the Lightning Network? In-Reply-To: References: Message-ID: <05C38A4C-44C7-4A97-A640-5D97A3F6CE42@mattcorallo.com> Please be careful accepting the faulty premise that the proposed algorithm is ?optimal?. It is optimal under a specific heuristic used to approximate what the user wants. In reality, there are a ton of different things to balance, from CLTV to feed to estimated failure probability calculated from node online percentages at-open liquidity, and even fees. There is no such thing as ?optimal?, only heuristics for how to balance these things into a score that you can feed into a routing algorithm. > Do we really want users to solve an NP-hard problem when they wish to find a cheap way of paying each other on the Lightning Network? I find this framing sufficiently insulting to the serious discussion people have had on this topic that I?m not really sure where to go from here aside from ignoring it. > On Aug 31, 2021, at 03:35, Orfeas Stefanos Thyfronitis Litos wrote: > > ?Hi list, > > On 8/31/21 5:01 AM, Anthony Towns wrote: >>> "Do we really want users to solve an NP-hard problem when >>> they wish to find a cheap way of paying each other on the Lightning Network?" >> FWIW, my answer to this is "sure, if that's the way it turns out". >> >> Another program which solves an NP-hard problem every time it runs is >> "apt-get install". >> [I]f it fails too often, >> you re-analyse what's going on manually and add a new heuristic to cope >> with it. > I've been following the conversation with interest and I acknowledge this is a thorny issue. > > I am a bit worried with a path which relies on constantly finding new heuristics to approximate a solution to an NP-hard problem: > * It allows too much room for nonconstructive disagreement between LN developers in the future. > - In a worst case scenario, all implementations end up using different, incompatible heuristics because each group of developers thinks that they have the best one, leading to a suboptimal performance for everyone. Heuristics are less of an exact science after all. > * It makes the job of node operators less predictable, since it would depend more on the decisions of said developers with no guarantee of convergence to a single solution. > - Node operators may perceive this as loss of decentralization to the developers. > > Such an approach is much more suitable to debian, since they have full control and a complete view over their "network" of packages, as opposed to LN, which is decentralized, nodes come and go at will and they can be private (even from developers!). > > Best, > Orfeas > The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th? ann an Oilthigh Dh?n ?ideann, cl?raichte an Alba, ?ireamh cl?raidh SC005336. > _______________________________________________ > Lightning-dev mailing list > Lightning-dev at lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev