On Friday, April 29, 2016 10:31:19 AM Bert Massop wrote: > Hi xor, > > Awesome! Thanks for sharing your work, I've been looking forward to that > for quite some time ☺. I hope to dedicate some time to reading it in a > month or so, once I finish my master's thesis.
That'd be great, I would be really thankful for a full read :) > Now to answer your question: > > > Besides getting to know how WoT works, it would be of scientific benefit > > for the project if you do read it: > > The end of the thesis describes how the algorithm might be further > > improved by > > investigating what can be considered as a whole class of algorithms. I > > have > > not heard about such a class of algorithms being identified and named by > > science yet. But this might be merely due to lack of my knowledge. > > I assume that this question relates to section 4.3.4 of your thesis. Yes! I had named the problem as "Single-Source Variable Shortest-Paths" (SSVSP) there. > You're looking at the class of dynamic shortest-paths problems, more > specifically the dynamic single-source shortest-paths problem. Note that in > general, DSSSP is at least as hard as (static) all-pairs shortest paths > [0]. However, WoT likely introduces a couple of constraints on the graph > that allow for improved complexity bounds. You might find [0] an > interesting read nonetheless. This is a perfect answer, just what I had hoped for! Thanks :) Also the idea with the constraints on the graph is promising. I shall think about such constraints for development of the WoT release next+2 or next+3, as next is in feature-freeze, and the other two releases are planned to ship very significant improvements already (see [1]). Meanwhile, I'm looking forward to you or other people reading the chapters 2 and 3 of the thesis. As they describe in great detail how the current WoT algorithm works, I hope this finally "opens up" WoT development enough so other people also have the opportunity to get ideas on whether such constraints do exist. I shall of course do my duty of dealing with this myself if nobody else does. But I'm really happy to finally have some peer review and hence this very promising algorithmic suggestion of yours! :) > [0] Roditty, L., & Zwick, U. (2011). On dynamic shortest paths problems. > *Algorithmica*, *61*(2), 389-401. Interesting that this is from only 2011. So we're still a vanguard research project :) This might open up fundraising possibilities from research institutions such as universities? I acquired a PDF with sha256sum of: > 09642b1e4681f1205da31ccaa829f93e62c4d071d67b93476c89437edbdde0b7 Is this what you had at hand? Further, thanks to your identification of what the problem is called, I was able to find a stackexchange question thread which asks for a similar thing. I.e. the first part of the question sounds just the same, the rest of it sounds like a smaller part of the problem, so do read the whole of it: http://cs.stackexchange.com/questions/7250/retrieving-the-shortest-path-of-a-dynamic-graph The answers cite further publications. I today don't have time to dig through them. If you do, please tell me which ones seem relevant so I can add them to the bugtracker. Huge major thanks again !! :) [1] - next+1: Is planned to ship a O(N^2) to O(N) reduction of USK subscriptions at the scale of the whole network, so that is enough already to decide to do it first. - next+2: Plans to reduce lock granularity of the "import new trust list" transaction by a factor of O(512), which could greatly improve UI latency. So we might do DSSSP in next+3. However O(512) is still a fixed constant, so if someone meanwhile shows how easily we can apply the DSSSP algorithms, I shall postpone the O(512) thing and do the DSSSP stuff in next+2 already instead of next+3.
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list [email protected] https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
