On Wednesday 13 January 2010 00:33:21 xor wrote: > > Currenty, the WoT IdentityFetcher permanently subscribes to the trust list > USK > of EVERY known identity, resulting in a total load of n*n USK subscriptions > on > the network - each identity subscribes to the USK of every other identity. > > (Even though it does O(n?), we will soon release the current code as WoT 0.4 > on the plugins page labeled as testing because it is guaranteed to fetch all > identities, i.e. guraanteed to "just work" and has proven to be very stable > in > all other means. And WoT 0.4 in general is optimized for new features & > stability, not for performance. 0.5 is planned to fix usability and > performance issues and bugs of course. - First implement all functions to > work > properly, then optimize and see if it still works the same as the previous > version, that's my plan)
IMHO O(n) per node is not as big a problem as you might think on Freenet, because much of the work ends up being shared between different nodes. It is definitely not the same as O(n^2). However, we do need to deal with it, as n will eventually get rather large, and we have to track multiple keys for each of these identities. > > I propose the following change for WoT 0.5 to get rid of the permanent O(N*N): > > - Permanent USK subscriptions should only be done to rank1 identities: The > identities to which an OwnIdentity has assigned a (positive of course) trust > value (= the users trustees). This should give us "small world > network"-effects > already. And if I'm right it changes everything from n? to some logarithmic > function of n. That is to be proved :) > > - The trust lists which are fetched of the rank1 identities will give us new > edition hints for new trust lists of other identities. Its called "hints" > because we cannot tell the USK manager that those editions REALLY exist, they > might be spoofed, i.e. too high. The USK manager supports specifying an > edition as hint-only. > > - So for rank 2 identities (Y is rank 2 <=> an own identity trusts X and X > trusts Y): If we receive a new edition hint for a rank2 identity, immediately > start a fetch for the hinted edition. Give the fetch a certain amount of time > to succeed, abort it if it doesn't. I propose 1 hour as the time limit. Tell > the USK manager NOT to attempt to search for any newer editions than the > hinted one: We want to use the information gathered from our rank1 identities > instead. But do not disable the fetching attempts of older editions than the > hinted one - to detect bogus hints. All you need to do is fetch that one slot. Give it say 3 attempts. That won't take an hour and you don't need a time limit, it's a simple request. > > - For rank3 and above identities, do the same as for rank2 but only allow a > hint-fetch-attempt every N days. N is to be carefully tweaked, I propose we > start with 3. > > - If any identity has not had a fetch attempt for >= M days, try to fetch > them > once. In other words, each identity is fetched at max every M days so that > identities which are not "hit" by the random heuristic above still get > fetched > every now and then. Reasonable. > DO allow the USK manager to search for editions higher > than the current hinted one. Do this to catch bugs in the other heuristics. > Log if an edition was fetched which was higher than the latest received hint. > I propose M to be 7 days. Fetching many slots ahead by doing a full USK retrieval uses much more resources, is it worth it? > > Now the question is: Who can calculate the maximal, minimal and average > complexity of my algorithm? :) > > I'm aware of the fact that the last point (fetch all identities every 7 days) > introduces some O(n?) again but IMHO its necessary for preventing bugs which > could cause some identities to be NEVER fetched. We can disable it after > we're > sure that it's not needed. Is it? Won't hints suffice to quickly deal with any such problem? > > And if anyone has suggestions for improvements, feel free to give them. I > consider my proposed rank1 and rank2 behavior as quite natural, but for rank3 > and above we might for example use an exponential function of rank, score and > whatever for the minimal delay between fetches. -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 835 bytes Desc: This is a digitally signed message part. URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20100119/4bdc2c6a/attachment.pgp>
