Semi-distributed searching (and maybe fully distributed too)

--===============1082997058==
Content-Type: multipart/signed;
  boundary="nextPart23274658.yc58ipW54A";
  protocol="application/pgp-signature";
  micalg=pgp-sha1
Content-Transfer-Encoding: 7bit

--nextPart23274658.yc58ipW54A
Content-Type: text/plain;
  charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

=46ASD paper:
http://freenetproject.org/papers/kronfol_final_thesis.pdf

The FASD paper enables keyword searching but is spammable. Basically this i=
s really easy (I haven't read it in a while so my terminology may be comple=
tely different to his):
=2D Keywords are hashed, of course, and these hashes translate to routing l=
ocations.
=2D An index element has a list of keywords connected to it.
=2D These are inserted as normal keys, except that they are inserted to the=
 locations of *each* of the keywords.
=2D A search can be routed to all of the keyword locations or to some subse=
t of them. It will include a list of keywords.
=2D The receiving nodes will send back any index elements that match the se=
arch.
=2D Standard algorithms for relevance are used to rank results (based on re=
lative frequency etc). This can easily be extended for arbitrary insert-tim=
e relevance numbers.
=2D I don't recall whether flow control was specified, it could become a pr=
oblem, but the obvious solution is just to limit the number of returned ite=
ms.

The fundamental problem has always been spam: These are effectively KSKs, a=
nd when you fetch them you propagate all the spam that the spammer has inse=
rted.

So solve it the same way we solve this for chat. All we have to do to make =
=46ASD feasible is:
=2D Make the items signed.
=2D Send a compressed list of the inserter identities we are interested in =
along with the request.

Clearly scalability is limited in much the same way as it is for chat. Howe=
ver it should be workable provided there is a certain amount of aggregation=
 and centralisation at the end-user level. And it's a big improvement from =
having to download several huge indexes and intersect them on the client. A=
rguably it may be more efficient to use this mechanism only for popular key=
words; for unpopular keywords the btree indexes should be very efficient. A=
nd it's probably a useful primitive for many applications...

Could it be made fully distributed, without needing a WoT? Yes, but only wi=
th:
1) Some sort of reputation feedback mechanism. This most likely involves no=
t propagating, or de-propagating, content that was fetched and not wanted, =
and
2) A sufficiently high cost for inserts of keywords to deter spamming. E.g.=
 something similar to the Scarce KSKs proposal - limit the number of keywor=
d index items that can be inserted to one per X seconds per link.

These are in principle feasible but may open serious attacks e.g. the first=
 may introduce censorship attacks, links to the wider question of is it saf=
e ever to allow to discover the location of a document without propagating =
it. IMHO the main issue there is path folding, and we can turn path folding=
 off for keyword searches (just like we turn it off for SSKs and inserts). =
Plus, will users give sufficient useful feedback?

KISS: Simplest mechanism: Keep an LRU (random replacement better for data s=
torage but not here). When a fetch happens, generate an unforgeable token f=
or each returned datum. If the user gives positive feedback, this is sent b=
ack to us, we "spend" the token (i.e. commit it to persistent storage, it c=
annot be spent twice, like digicash), and promote the item. This would be a=
n operation similar to an insert, which would promote on those nodes where =
it matched the original fetch. Obviously it will only work for a relatively=
 short period after the original request. We might have recently fetched it=
ems stored in a special cache to be promoted into the main cache if feedbac=
k comes in, and dropped if it doesn't. To prevent abuse, we could perhaps u=
se rate limiting similar to that proposed for inserting? A spammer keeping =
stuff in the cache indefinitely without anyone else fetching it may be poss=
ible by repeatedly requesting (he can't repeatedly insert) - but not if we =
don't promote items that we have already returned from a node that was clos=
e to the originator. Or we just impose rate limiting on search requests as =
well as inserts. Or ignore it - spam is only a problem if it is in volume, =
and inserts are throttled anyway.

Hmmm, what exactly does FASD say about this? My recollection was that FASD =
was spammable. I should really read the paper again! It looks like it *migh=
t* be a tractable problem ...

And can these mechanisms prevent spam on chat too?? Yes, chat is essentiall=
y a search problem.

--nextPart23274658.yc58ipW54A
Content-Type: application/pgp-signature; name=signature.asc 
Content-Description: This is a digitally signed message part.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABEIAAYFAkxEu78ACgkQYUNbc3WUHYiQrgCfcTMtUuz60+W8wPqow0VwpjfF
AHYAoLNNHtHreVA3S+2oiSmcI4GduoQC
=JvGW
-----END PGP SIGNATURE-----

--nextPart23274658.yc58ipW54A--

--===============1082997058==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
Tech mailing list
[email protected]
http://freenetproject.org/cgi-bin/mailman/listinfo/tech
--===============1082997058==--