Hex Artifact Content
Not logged in

Artifact da00e554ad1ddf188e31d5bdb57150baef145ab6:

Wiki page [Application Example: Distributed Search Engine] by martin_vahi on 2016-09-03 02:25:24.
0000: 44 20 32 30 31 36 2d 30 39 2d 30 33 54 30 32 3a  D 2016-09-03T02:
0010: 32 35 3a 32 34 2e 32 32 36 0a 4c 20 41 70 70 6c  25:24.226.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 37 65 36 61 64 39 35 31 37 63 65 32 30 35 36   7e6ad9517ce2056
0060: 39 35 39 61 30 30 35 65 36 62 63 65 39 63 39 30  959a005e6bce9c90
0070: 34 33 61 66 65 66 36 33 61 0a 55 20 6d 61 72 74  43afef63a.U mart
0080: 69 6e 5f 76 61 68 69 0a 57 20 32 35 36 30 0a 3c  in_vahi.W 2560.<
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 2f 70 3e 0a 0a 3c 70 3e 3c 2f 70 3e 0a 3c  :</p>..<p></p>.<
0380: 75 6c 3e 0a 3c 6c 69 3e 49 20 64 6f 20 6e 6f 74  ul>.<li>I do not
0390: 20 68 61 76 65 20 69 74 2c 20 6e 6f 72 20 77 61   have it, nor wa
03a0: 73 20 49 20 61 62 6c 65 20 74 6f 20 72 65 61 63  s I able to reac
03b0: 68 20 61 6e 79 62 6f 64 79 20 77 69 74 68 69 6e  h anybody within
03c0: 20 4e 20 68 6f 70 73 2c 20 77 68 6f 20 68 61 73   N hops, who has
03d0: 0a 69 74 2e 3c 2f 6c 69 3e 0a 3c 6c 69 3e 49 20  .it.</li>.<li>I 
03e0: 68 61 76 65 20 69 74 2c 20 74 68 65 20 53 69 6c  have it, the Sil
03f0: 6b 74 6f 72 72 65 6e 74 20 70 61 63 6b 65 74 20  ktorrent packet 
0400: 6e 61 6d 65 20 69 73 20 66 6f 6f 20 61 6e 64 20  name is foo and 
0410: 74 68 65 20 64 69 73 74 61 6e 63 65 20 69 73 20  the distance is 
0420: 62 61 72 2e 3c 2f 6c 69 3e 0a 3c 6c 69 3e 49 20  bar.</li>.<li>I 
0430: 64 6f 20 6e 6f 74 20 68 61 76 65 20 69 74 2c 20  do not have it, 
0440: 62 75 74 20 61 73 6b 20 66 72 6f 6d 20 6e 6f 64  but ask from nod
0450: 65 20 4e 5f 78 31 2e 20 45 69 74 68 65 72 20 74  e N_x1. Either t
0460: 68 65 20 4e 5f 78 31 20 68 61 73 20 69 74 20 6f  he N_x1 has it o
0470: 72 20 69 74 20 63 61 6e 0a 72 65 66 65 72 20 74  r it can.refer t
0480: 6f 20 73 6f 6d 65 20 6f 74 68 65 72 20 6e 6f 64  o some other nod
0490: 65 20 74 68 61 74 20 65 69 74 68 65 72 20 68 61  e that either ha
04a0: 73 20 69 74 20 69 74 73 65 6c 66 20 6f 72 20 63  s it itself or c
04b0: 61 6e 20 67 69 76 65 20 61 20 6e 65 77 20 6e 6f  an give a new no
04c0: 64 65 20 6e 61 6d 65 2e 0a 54 68 65 20 53 69 6c  de name..The Sil
04d0: 6b 74 6f 72 72 65 6e 74 20 70 61 63 6b 65 74 20  ktorrent packet 
04e0: 6e 61 6d 65 20 69 73 20 66 6f 6f 20 61 6e 64 20  name is foo and 
04f0: 74 68 65 20 64 69 73 74 61 6e 63 65 20 69 73 20  the distance is 
0500: 62 61 72 2e 3c 2f 6c 69 3e 0a 3c 2f 75 6c 3e 0a  bar.</li>.</ul>.
0510: 0a 3c 70 3e 45 61 63 68 20 6e 6f 64 65 20 6d 61  .<p>Each node ma
0520: 69 6e 74 61 69 6e 73 20 69 74 73 20 6f 77 6e 2c  intains its own,
0530: 20 70 65 72 73 6f 6e 61 6c 2c 20 74 61 62 6c 65   personal, table
0540: 20 6f 66 20 6e 6f 64 65 20 72 65 70 75 74 61 74   of node reputat
0550: 69 6f 6e 73 2e 20 54 68 65 20 71 75 65 72 79 0a  ions. The query.
0560: 69 6e 69 74 69 61 74 6f 72 20 61 73 6b 73 20 74  initiator asks t
0570: 68 65 20 70 61 63 6b 65 74 20 6f 77 6e 65 72 20  he packet owner 
0580: 64 69 72 65 63 74 6c 79 20 66 6f 72 20 74 68 65  directly for the
0590: 20 70 61 63 6b 65 74 20 61 6e 64 20 76 65 72 69   packet and veri
05a0: 66 69 65 73 20 74 68 61 74 20 74 68 65 0a 70 72  fies that the.pr
05b0: 6f 6d 69 73 65 64 20 64 69 73 74 61 6e 63 65 20  omised distance 
05c0: 62 65 74 77 65 65 6e 20 74 68 65 20 71 75 65 72  between the quer
05d0: 79 20 61 6e 64 20 74 68 65 20 70 61 63 6b 65 74  y and the packet
05e0: 20 6d 61 74 63 68 2e 20 49 6e 20 74 65 72 6d 73   match. In terms
05f0: 20 6f 66 20 73 65 61 72 63 68 0a 68 6f 70 73 20   of search.hops 
0600: 74 68 65 20 6e 6f 64 65 73 20 63 6c 6f 73 65 72  the nodes closer
0610: 20 74 6f 20 74 68 65 20 6c 69 61 72 20 67 65 74   to the liar get
0620: 20 68 69 67 68 65 72 20 70 65 6e 61 6c 74 79 20   higher penalty 
0630: 70 6f 69 6e 74 73 20 74 68 61 6e 20 74 68 65 20  points than the 
0640: 6e 6f 64 65 73 0a 66 75 72 74 68 65 72 20 66 72  nodes.further fr
0650: 6f 6d 20 74 68 65 20 6c 69 61 72 2e 20 54 68 65  om the liar. The
0660: 20 72 65 73 74 20 69 73 20 61 20 6d 61 74 74 65   rest is a matte
0670: 72 20 6f 66 20 63 75 73 74 6f 6d 20 68 65 75 72  r of custom heur
0680: 69 73 74 69 63 73 20 74 68 61 74 20 63 61 6e 20  istics that can 
0690: 62 65 0a 76 65 72 79 20 63 72 65 61 74 69 76 65  be.very creative
06a0: 2e 20 54 68 65 20 6c 69 61 72 73 20 6d 69 67 68  . The liars migh
06b0: 74 20 6c 69 65 20 6f 6e 6c 79 20 6f 63 63 61 73  t lie only occas
06c0: 69 6f 6e 61 6c 6c 79 2c 20 61 74 20 72 61 6e 64  ionally, at rand
06d0: 6f 6d 20 6d 6f 6d 65 6e 74 73 20 6f 72 0a 61 63  om moments or.ac
06e0: 63 6f 72 64 69 6e 67 20 74 6f 20 73 6f 6d 65 20  cording to some 
06f0: 68 65 75 72 69 73 74 69 63 20 6f 72 20 73 74 61  heuristic or sta
0700: 74 69 73 74 69 63 61 6c 20 64 69 73 74 72 69 62  tistical distrib
0710: 75 74 69 6f 6e 2c 20 61 63 63 6f 72 64 69 6e 67  ution, according
0720: 20 74 6f 0a 69 6e 73 74 72 75 63 74 69 6f 6e 73   to.instructions
0730: 20 66 72 6f 6d 20 63 65 6e 73 6f 72 73 2c 20 65   from censors, e
0740: 74 63 2e 20 54 68 65 20 73 65 61 72 63 68 20 65  tc. The search e
0750: 6e 67 69 6e 65 20 6d 69 67 68 74 20 62 65 20 64  ngine might be d
0760: 65 73 69 67 6e 65 64 20 74 6f 20 73 65 61 72 63  esigned to searc
0770: 68 0a 66 6f 72 20 74 65 78 74 2c 20 62 75 74 20  h.for text, but 
0780: 74 68 65 20 61 6c 67 6f 72 69 74 68 6d 20 77 6f  the algorithm wo
0790: 72 6b 73 20 61 6c 73 6f 20 6f 6e 20 6f 74 68 65  rks also on othe
07a0: 72 20 64 61 74 61 20 74 79 70 65 73 2c 20 66 6f  r data types, fo
07b0: 72 20 65 78 61 6d 70 6c 65 2c 20 33 44 0a 73 68  r example, 3D.sh
07c0: 61 70 65 73 2c 20 6d 61 70 73 2c 20 69 6d 61 67  apes, maps, imag
07d0: 65 73 2c 20 73 6f 75 6e 64 73 2c 20 65 74 63 2e  es, sounds, etc.
07e0: 3c 2f 70 3e 0a 0a 3c 70 3e 3c 62 72 3e 0a 3c 2f  </p>..<p><br>.</
07f0: 70 3e 0a 0a 3c 68 31 3e 53 6f 75 72 63 65 73 20  p>..<h1>Sources 
0800: 6f 66 20 49 6e 73 70 69 72 61 74 69 6f 6e 3c 2f  of Inspiration</
0810: 68 31 3e 0a 0a 3c 70 3e 3c 2f 70 3e 0a 3c 75 6c  h1>..<p></p>.<ul
0820: 3e 0a 3c 6c 69 3e 3c 61 20 68 72 65 66 3d 22 68  >.<li><a href="h
0830: 74 74 70 73 3a 2f 2f 77 77 77 2e 63 73 2e 63 6f  ttps://www.cs.co
0840: 72 6e 65 6c 6c 2e 65 64 75 2f 7e 62 77 6f 6e 67  rnell.edu/~bwong
0850: 2f 63 75 62 69 74 2f 61 70 70 72 6f 61 63 68 2e  /cubit/approach.
0860: 68 74 6d 6c 22 3e 43 75 62 69 74 3c 2f 61 3e 0a  html">Cubit</a>.
0870: 3c 69 3e 28 3c 61 20 68 72 65 66 3d 22 68 74 74  <i>(<a href="htt
0880: 70 73 3a 2f 2f 61 72 63 68 69 76 65 2e 69 73 2f  ps://archive.is/
0890: 55 73 4f 74 44 22 3e 61 72 63 68 69 76 61 6c 20  UsOtD">archival 
08a0: 63 6f 70 79 3c 2f 61 3e 2c 3c 69 3e 2c 26 6e 62  copy</a>,<i>,&nb
08b0: 73 70 3b 3c 61 20 68 72 65 66 3d 22 68 74 74 70  sp;<a href="http
08c0: 3a 2f 2f 77 77 77 2e 73 6f 66 74 66 31 2e 63 6f  ://www.softf1.co
08d0: 6d 2f 63 67 69 2d 62 69 6e 2f 74 72 65 65 31 2f  m/cgi-bin/tree1/
08e0: 74 65 63 68 6e 6f 6c 6f 67 79 2f 66 6c 61 77 73  technology/flaws
08f0: 2f 73 69 6c 6b 74 6f 72 72 65 6e 74 2e 62 61 73  /silktorrent.bas
0900: 68 2f 61 69 6e 66 6f 2f 37 38 66 36 62 39 38 37  h/ainfo/78f6b987
0910: 33 38 63 39 35 38 38 36 22 3e 6c 6f 63 61 6c 5f  38c95886">local_
0920: 63 6f 70 79 3c 2f 61 3e 2c 26 6e 62 73 70 3b 3c  copy</a>,&nbsp;<
0930: 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f 2f 77  a href="http://w
0940: 77 77 2e 73 6f 66 74 66 31 2e 63 6f 6d 2f 63 67  ww.softf1.com/cg
0950: 69 2d 62 69 6e 2f 74 72 65 65 31 2f 74 65 63 68  i-bin/tree1/tech
0960: 6e 6f 6c 6f 67 79 2f 66 6c 61 77 73 2f 73 69 6c  nology/flaws/sil
0970: 6b 74 6f 72 72 65 6e 74 2e 62 61 73 68 2f 61 69  ktorrent.bash/ai
0980: 6e 66 6f 2f 33 32 62 39 32 31 39 63 39 39 34 66  nfo/32b9219c994f
0990: 63 36 30 66 22 3e 73 6f 75 72 63 65 3c 2f 61 3e  c60f">source</a>
09a0: 3c 2f 69 3e 29 3c 2f 69 3e 3c 2f 6c 69 3e 0a 3c  </i>)</i></li>.<
09b0: 6c 69 3e 43 6f 6f 70 65 72 61 74 69 76 65 20 44  li>Cooperative D
09c0: 6f 6d 61 69 6e 20 4e 61 6d 65 20 53 79 73 74 65  omain Name Syste
09d0: 6d 2c 0a 3c 61 20 68 72 65 66 3d 22 68 74 74 70  m,.<a href="http
09e0: 73 3a 2f 2f 77 77 77 2e 63 73 2e 63 6f 72 6e 65  s://www.cs.corne
09f0: 6c 6c 2e 65 64 75 2f 50 65 6f 70 6c 65 2f 65 67  ll.edu/People/eg
0a00: 73 2f 62 65 65 68 69 76 65 2f 63 6f 64 6f 6e 73  s/beehive/codons
0a10: 2e 70 68 70 22 3e 43 6f 44 6f 4e 53 3c 2f 61 3e  .php">CoDoNS</a>
0a20: 0a 3c 69 3e 28 3c 61 20 68 72 65 66 3d 22 68 74  .<i>(<a href="ht
0a30: 74 70 73 3a 2f 2f 61 72 63 68 69 76 65 2e 69 73  tps://archive.is
0a40: 2f 62 41 42 77 49 22 3e 61 72 63 68 69 76 61 6c  /bABwI">archival
0a50: 20 63 6f 70 79 3c 2f 61 3e 29 3c 2f 69 3e 3c 2f   copy</a>)</i></
0a60: 6c 69 3e 0a 3c 2f 75 6c 3e 0a 0a 3c 70 3e 3c 2f  li>.</ul>..<p></
0a70: 70 3e 0a 0a 3c 70 3e 3c 62 72 3e 0a 3c 2f 70 3e  p>..<p><br>.</p>
0a80: 0a 0a 3c 70 3e 3c 62 72 3e 0a 3c 2f 70 3e 0a 0a  ..<p><br>.</p>..
0a90: 5a 20 66 35 66 35 33 33 61 34 36 39 61 32 65 36  Z f5f533a469a2e6
0aa0: 63 37 38 36 37 62 34 34 63 35 39 63 66 37 32 37  c7867b44c59cf727
0ab0: 62 65 0a                                         be.