Hex Artifact Content
Not logged in

Artifact 92bffe4cf24960dd6071b6c32b55975ae6de8d4e:

Wiki page [Application Example: Distributed Search Engine] by martin_vahi on 2016-09-03 02:19:26.
0000: 44 20 32 30 31 36 2d 30 39 2d 30 33 54 30 32 3a  D 2016-09-03T02:
0010: 31 39 3a 32 36 2e 39 36 39 0a 4c 20 41 70 70 6c  19:26.969.L Appl
0020: 69 63 61 74 69 6f 6e 5c 73 45 78 61 6d 70 6c 65  ication\sExample
0030: 3a 5c 73 44 69 73 74 72 69 62 75 74 65 64 5c 73  :\sDistributed\s
0040: 53 65 61 72 63 68 5c 73 45 6e 67 69 6e 65 0a 50  Search\sEngine.P
0050: 20 65 62 31 63 34 64 31 31 65 33 63 66 61 31 66   eb1c4d11e3cfa1f
0060: 34 30 65 37 30 63 32 63 63 36 64 33 62 66 30 39  40e70c2cc6d3bf09
0070: 64 33 37 37 62 30 39 63 32 0a 55 20 6d 61 72 74  d377b09c2.U mart
0080: 69 6e 5f 76 61 68 69 0a 57 20 32 34 31 38 0a 3c  in_vahi.W 2418.<
0090: 70 3e 3c 66 6f 6e 74 20 63 6f 6c 6f 72 3d 22 23  p><font color="#
00a0: 66 66 30 30 30 30 22 3e 54 68 65 20 69 64 65 61  ff0000">The idea
00b0: 20 69 6e 20 74 68 69 73 20 63 68 61 70 74 65 72   in this chapter
00c0: 20 68 61 73 20 6e 6f 74 20 62 65 65 6e 20 74 65   has not been te
00d0: 73 74 65 64 20 69 6e 0a 70 72 61 63 74 69 63 65  sted in.practice
00e0: 20 79 65 74 2e 20 49 74 27 73 20 6a 75 73 74 20   yet. It's just 
00f0: 61 20 74 68 6f 75 67 68 74 2c 20 61 20 73 74 61  a thought, a sta
0100: 72 74 69 6e 67 20 70 6f 69 6e 74 20 66 6f 72 20  rting point for 
0110: 61 6e 20 65 78 70 65 72 69 6d 65 6e 74 2e 3c 2f  an experiment.</
0120: 66 6f 6e 74 3e 3c 2f 70 3e 0a 0a 3c 70 3e 3c 62  font></p>..<p><b
0130: 72 3e 0a 3c 2f 70 3e 0a 0a 3c 68 31 3e 54 68 65  r>.</p>..<h1>The
0140: 20 47 69 73 74 20 6f 66 20 74 68 65 20 49 64 65   Gist of the Ide
0150: 61 3c 2f 68 31 3e 0a 0a 3c 70 3e 41 20 64 6f 63  a</h1>..<p>A doc
0160: 75 6d 65 6e 74 20 6f 72 20 70 61 72 74 20 6f 66  ument or part of
0170: 20 61 20 64 6f 63 75 6d 65 6e 74 20 72 65 73 69   a document resi
0180: 64 65 73 20 61 74 20 61 20 53 69 6c 6b 74 6f 72  des at a Silktor
0190: 72 65 6e 74 20 70 61 63 6b 65 74 2e 20 41 20 73  rent packet. A s
01a0: 65 61 72 63 68 0a 71 75 65 72 79 20 63 61 6c 63  earch.query calc
01b0: 75 6c 61 74 65 73 20 61 20 72 61 74 69 6f 6e 61  ulates a rationa
01c0: 6c 20 6e 75 6d 62 65 72 2c 20 61 20 64 69 73 74  l number, a dist
01d0: 61 6e 63 65 2c 20 62 65 74 77 65 65 6e 20 74 68  ance, between th
01e0: 65 20 71 75 65 72 79 20 61 6e 64 20 74 68 65 0a  e query and the.
01f0: 53 69 6c 6b 74 6f 72 72 65 6e 74 20 70 61 63 6b  Silktorrent pack
0200: 65 74 2e 20 54 68 65 20 71 75 65 73 74 69 6f 6e  et. The question
0210: 20 74 6f 20 74 68 65 20 6e 65 74 77 6f 72 6b 20   to the network 
0220: 6f 66 20 6e 6f 64 65 73 20 69 73 3a 20 3c 62 3e  of nodes is: <b>
0230: 22 44 6f 20 59 6f 75 20 68 61 76 65 20 61 0a 53  "Do You have a.S
0240: 69 6c 6b 74 6f 72 72 65 6e 74 20 70 61 63 6b 65  ilktorrent packe
0250: 74 20 74 68 61 74 20 68 61 73 20 61 20 4d 41 58  t that has a MAX
0260: 49 4d 55 4d 20 64 69 73 74 61 6e 63 65 20 6f 66  IMUM distance of
0270: 20 4c 20 66 72 6f 6d 20 74 68 65 20 70 6f 69 6e   L from the poin
0280: 74 20 74 68 61 74 20 69 73 0a 64 65 74 65 72 6d  t that is.determ
0290: 69 6e 65 64 20 62 79 20 61 20 73 65 61 72 63 68  ined by a search
02a0: 2d 65 6e 67 69 6e 65 20 73 70 65 63 69 66 69 63  -engine specific
02b0: 2c 20 70 72 65 2d 64 65 66 69 6e 65 64 2c 20 66  , pre-defined, f
02c0: 75 6e 63 74 69 6f 6e 20 77 69 74 68 20 74 68 65  unction with the
02d0: 0a 66 6f 6c 6c 6f 77 69 6e 67 20 69 6e 70 75 74  .following input
02e0: 20 70 61 72 61 6d 65 74 65 72 73 2c 20 70 61 72   parameters, par
02f0: 61 6d 5f 31 2c 2e 2e 2e 2c 70 61 72 61 6d 5f 4e  am_1,...,param_N
0300: 3f 22 20 3c 2f 62 3e 53 6f 6d 65 20 6f 66 20 74  ?" </b>Some of t
0310: 68 65 20 6e 6f 64 65 73 20 6f 6e 20 74 68 65 0a  he nodes on the.
0320: 6e 65 74 77 6f 72 6b 20 77 69 6c 6c 20 6c 69 65  network will lie
0330: 2c 20 62 75 74 20 74 68 65 20 6f 6e 6c 79 20 70  , but the only p
0340: 6f 73 73 69 62 6c 65 2c 20 73 70 65 63 69 66 69  ossible, specifi
0350: 65 64 2c 20 61 6e 73 77 65 72 73 20 74 6f 20 74  ed, answers to t
0360: 68 61 74 20 71 75 65 73 74 69 6f 6e 0a 61 72 65  hat question.are
0370: 3a 3c 62 72 3e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 3c  :<br>.</p>..<p><
0380: 62 72 3e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 3c 2f 70  br>.</p>..<p></p
0390: 3e 0a 3c 75 6c 3e 0a 3c 6c 69 3e 49 20 64 6f 20  >.<ul>.<li>I do 
03a0: 6e 6f 74 20 68 61 76 65 20 69 74 2c 20 6e 6f 72  not have it, nor
03b0: 20 77 61 73 20 49 20 61 62 6c 65 20 74 6f 20 72   was I able to r
03c0: 65 61 63 68 20 61 6e 79 62 6f 64 79 20 77 69 74  each anybody wit
03d0: 68 69 6e 20 4e 20 68 6f 70 73 2c 20 77 68 6f 20  hin N hops, who 
03e0: 68 61 73 0a 69 74 2e 3c 2f 6c 69 3e 0a 3c 6c 69  has.it.</li>.<li
03f0: 3e 49 20 68 61 76 65 20 69 74 2c 20 74 68 65 20  >I have it, the 
0400: 53 69 6c 6b 74 6f 72 72 65 6e 74 20 70 61 63 6b  Silktorrent pack
0410: 65 74 20 6e 61 6d 65 20 69 73 20 66 6f 6f 20 61  et name is foo a
0420: 6e 64 20 74 68 65 20 64 69 73 74 61 6e 63 65 20  nd the distance 
0430: 69 73 20 62 61 72 2e 3c 2f 6c 69 3e 0a 3c 6c 69  is bar.</li>.<li
0440: 3e 49 20 64 6f 20 6e 6f 74 20 68 61 76 65 20 69  >I do not have i
0450: 74 2c 20 62 75 74 20 61 73 6b 20 66 72 6f 6d 20  t, but ask from 
0460: 6e 6f 64 65 20 4e 5f 78 31 2e 20 45 69 74 68 65  node N_x1. Eithe
0470: 72 20 74 68 65 20 4e 5f 78 31 20 68 61 73 20 69  r the N_x1 has i
0480: 74 20 6f 72 20 69 74 20 63 61 6e 0a 72 65 66 65  t or it can.refe
0490: 72 20 74 6f 20 73 6f 6d 65 20 6f 74 68 65 72 20  r to some other 
04a0: 6e 6f 64 65 20 74 68 61 74 20 65 69 74 68 65 72  node that either
04b0: 20 68 61 73 20 69 74 20 69 74 73 65 6c 66 20 6f   has it itself o
04c0: 72 20 63 61 6e 20 67 69 76 65 20 61 20 6e 65 77  r can give a new
04d0: 20 6e 6f 64 65 20 6e 61 6d 65 2e 0a 54 68 65 20   node name..The 
04e0: 53 69 6c 6b 74 6f 72 72 65 6e 74 20 70 61 63 6b  Silktorrent pack
04f0: 65 74 20 6e 61 6d 65 20 69 73 20 66 6f 6f 20 61  et name is foo a
0500: 6e 64 20 74 68 65 20 64 69 73 74 61 6e 63 65 20  nd the distance 
0510: 69 73 20 62 61 72 2e 3c 2f 6c 69 3e 0a 3c 2f 75  is bar.</li>.</u
0520: 6c 3e 0a 0a 3c 70 3e 3c 2f 70 3e 0a 0a 3c 70 3e  l>..<p></p>..<p>
0530: 45 61 63 68 20 6e 6f 64 65 20 6d 61 69 6e 74 61  Each node mainta
0540: 69 6e 73 20 69 74 73 20 6f 77 6e 2c 20 70 65 72  ins its own, per
0550: 73 6f 6e 61 6c 2c 20 74 61 62 6c 65 20 6f 66 20  sonal, table of 
0560: 6e 6f 64 65 20 72 65 70 75 74 61 74 69 6f 6e 73  node reputations
0570: 2e 20 54 68 65 20 71 75 65 72 79 0a 69 6e 69 74  . The query.init
0580: 69 61 74 6f 72 20 61 73 6b 73 20 74 68 65 20 70  iator asks the p
0590: 61 63 6b 65 74 20 6f 77 6e 65 72 20 64 69 72 65  acket owner dire
05a0: 63 74 6c 79 20 66 6f 72 20 74 68 65 20 70 61 63  ctly for the pac
05b0: 6b 65 74 20 61 6e 64 20 76 65 72 69 66 69 65 73  ket and verifies
05c0: 20 74 68 61 74 20 74 68 65 0a 70 72 6f 6d 69 73   that the.promis
05d0: 65 64 20 64 69 73 74 61 6e 63 65 20 62 65 74 77  ed distance betw
05e0: 65 65 6e 20 74 68 65 20 71 75 65 72 79 20 61 6e  een the query an
05f0: 64 20 74 68 65 20 70 61 63 6b 65 74 20 6d 61 74  d the packet mat
0600: 63 68 2e 20 49 6e 20 74 65 72 6d 73 20 6f 66 20  ch. In terms of 
0610: 73 65 61 72 63 68 0a 68 6f 70 73 20 74 68 65 20  search.hops the 
0620: 6e 6f 64 65 73 20 63 6c 6f 73 65 72 20 74 6f 20  nodes closer to 
0630: 74 68 65 20 6c 69 61 72 20 67 65 74 20 68 69 67  the liar get hig
0640: 68 65 72 20 70 65 6e 61 6c 74 79 20 70 6f 69 6e  her penalty poin
0650: 74 73 20 74 68 61 6e 20 74 68 65 20 6e 6f 64 65  ts than the node
0660: 73 0a 66 75 72 74 68 65 72 20 66 72 6f 6d 20 74  s.further from t
0670: 68 65 20 6c 69 61 72 2e 20 54 68 65 20 72 65 73  he liar. The res
0680: 74 20 69 73 20 61 20 6d 61 74 74 65 72 20 6f 66  t is a matter of
0690: 20 63 75 73 74 6f 6d 20 68 65 75 72 69 73 74 69   custom heuristi
06a0: 63 73 20 74 68 61 74 20 63 61 6e 20 62 65 0a 76  cs that can be.v
06b0: 65 72 79 20 63 72 65 61 74 69 76 65 2e 20 54 68  ery creative. Th
06c0: 65 20 6c 69 61 72 73 20 6d 69 67 68 74 20 6c 69  e liars might li
06d0: 65 20 6f 6e 6c 79 20 6f 63 63 61 73 69 6f 6e 61  e only occasiona
06e0: 6c 6c 79 2c 20 61 74 20 72 61 6e 64 6f 6d 20 6d  lly, at random m
06f0: 6f 6d 65 6e 74 73 20 6f 72 0a 61 63 63 6f 72 64  oments or.accord
0700: 69 6e 67 20 74 6f 20 73 6f 6d 65 20 68 65 75 72  ing to some heur
0710: 69 73 74 69 63 20 6f 72 20 73 74 61 74 69 73 74  istic or statist
0720: 69 63 61 6c 20 64 69 73 74 72 69 62 75 74 69 6f  ical distributio
0730: 6e 2c 20 69 6e 73 74 72 75 63 74 69 6f 6e 73 20  n, instructions 
0740: 66 72 6f 6d 0a 63 65 6e 73 6f 72 73 2c 20 65 74  from.censors, et
0750: 63 2e 3c 2f 70 3e 0a 0a 3c 70 3e 3c 62 72 3e 0a  c.</p>..<p><br>.
0760: 3c 2f 70 3e 0a 0a 3c 68 31 3e 53 6f 75 72 63 65  </p>..<h1>Source
0770: 73 20 6f 66 20 49 6e 73 70 69 72 61 74 69 6f 6e  s of Inspiration
0780: 3c 2f 68 31 3e 0a 0a 3c 70 3e 3c 2f 70 3e 0a 3c  </h1>..<p></p>.<
0790: 75 6c 3e 0a 3c 6c 69 3e 3c 61 20 68 72 65 66 3d  ul>.<li><a href=
07a0: 22 68 74 74 70 73 3a 2f 2f 77 77 77 2e 63 73 2e  "https://www.cs.
07b0: 63 6f 72 6e 65 6c 6c 2e 65 64 75 2f 7e 62 77 6f  cornell.edu/~bwo
07c0: 6e 67 2f 63 75 62 69 74 2f 61 70 70 72 6f 61 63  ng/cubit/approac
07d0: 68 2e 68 74 6d 6c 22 3e 43 75 62 69 74 3c 2f 61  h.html">Cubit</a
07e0: 3e 0a 3c 69 3e 28 3c 61 20 68 72 65 66 3d 22 68  >.<i>(<a href="h
07f0: 74 74 70 73 3a 2f 2f 61 72 63 68 69 76 65 2e 69  ttps://archive.i
0800: 73 2f 55 73 4f 74 44 22 3e 61 72 63 68 69 76 61  s/UsOtD">archiva
0810: 6c 20 63 6f 70 79 3c 2f 61 3e 2c 3c 69 3e 2c 26  l copy</a>,<i>,&
0820: 6e 62 73 70 3b 3c 61 20 68 72 65 66 3d 22 68 74  nbsp;<a href="ht
0830: 74 70 3a 2f 2f 77 77 77 2e 73 6f 66 74 66 31 2e  tp://www.softf1.
0840: 63 6f 6d 2f 63 67 69 2d 62 69 6e 2f 74 72 65 65  com/cgi-bin/tree
0850: 31 2f 74 65 63 68 6e 6f 6c 6f 67 79 2f 66 6c 61  1/technology/fla
0860: 77 73 2f 73 69 6c 6b 74 6f 72 72 65 6e 74 2e 62  ws/silktorrent.b
0870: 61 73 68 2f 61 69 6e 66 6f 2f 37 38 66 36 62 39  ash/ainfo/78f6b9
0880: 38 37 33 38 63 39 35 38 38 36 22 3e 6c 6f 63 61  8738c95886">loca
0890: 6c 5f 63 6f 70 79 3c 2f 61 3e 2c 26 6e 62 73 70  l_copy</a>,&nbsp
08a0: 3b 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f  ;<a href="http:/
08b0: 2f 77 77 77 2e 73 6f 66 74 66 31 2e 63 6f 6d 2f  /www.softf1.com/
08c0: 63 67 69 2d 62 69 6e 2f 74 72 65 65 31 2f 74 65  cgi-bin/tree1/te
08d0: 63 68 6e 6f 6c 6f 67 79 2f 66 6c 61 77 73 2f 73  chnology/flaws/s
08e0: 69 6c 6b 74 6f 72 72 65 6e 74 2e 62 61 73 68 2f  ilktorrent.bash/
08f0: 61 69 6e 66 6f 2f 33 32 62 39 32 31 39 63 39 39  ainfo/32b9219c99
0900: 34 66 63 36 30 66 22 3e 73 6f 75 72 63 65 3c 2f  4fc60f">source</
0910: 61 3e 3c 2f 69 3e 29 3c 2f 69 3e 3c 2f 6c 69 3e  a></i>)</i></li>
0920: 0a 3c 6c 69 3e 43 6f 6f 70 65 72 61 74 69 76 65  .<li>Cooperative
0930: 20 44 6f 6d 61 69 6e 20 4e 61 6d 65 20 53 79 73   Domain Name Sys
0940: 74 65 6d 2c 0a 3c 61 20 68 72 65 66 3d 22 68 74  tem,.<a href="ht
0950: 74 70 73 3a 2f 2f 77 77 77 2e 63 73 2e 63 6f 72  tps://www.cs.cor
0960: 6e 65 6c 6c 2e 65 64 75 2f 50 65 6f 70 6c 65 2f  nell.edu/People/
0970: 65 67 73 2f 62 65 65 68 69 76 65 2f 63 6f 64 6f  egs/beehive/codo
0980: 6e 73 2e 70 68 70 22 3e 43 6f 44 6f 4e 53 3c 2f  ns.php">CoDoNS</
0990: 61 3e 0a 3c 69 3e 28 3c 61 20 68 72 65 66 3d 22  a>.<i>(<a href="
09a0: 68 74 74 70 73 3a 2f 2f 61 72 63 68 69 76 65 2e  https://archive.
09b0: 69 73 2f 62 41 42 77 49 22 3e 61 72 63 68 69 76  is/bABwI">archiv
09c0: 61 6c 20 63 6f 70 79 3c 2f 61 3e 29 3c 2f 69 3e  al copy</a>)</i>
09d0: 3c 2f 6c 69 3e 0a 3c 2f 75 6c 3e 0a 0a 3c 70 3e  </li>.</ul>..<p>
09e0: 3c 2f 70 3e 0a 0a 3c 70 3e 3c 62 72 3e 0a 3c 2f  </p>..<p><br>.</
09f0: 70 3e 0a 0a 3c 70 3e 3c 62 72 3e 0a 3c 2f 70 3e  p>..<p><br>.</p>
0a00: 0a 0a 5a 20 64 66 33 61 31 65 31 39 64 30 30 35  ..Z df3a1e19d005
0a10: 33 34 38 65 62 33 33 36 32 36 65 61 33 62 63 64  348eb33626ea3bcd
0a20: 39 35 66 32 0a                                   95f2.