[Gzz] Some initial answers to a)...c)

[hemppah]

Here are some initial answers (and proposals) to my research questions from a)
to c). Please feel free give comments:

a)
-the most efficient algorithm: O(log n)
-DHTs requires O(log n) hops, log n neighbors, except Viceroy (however,
robustness suffers)
-SWNs requires O(log^2 n) hops, much less neighbors (constant, is not depedent 
of n)
-in DHTs and SWNs, it is possible to locate data in constant time, BUT it
requires knowing all n neighbors!!!
-in basic scenario, DHTs and SWTs assume that we have to know value's key 
beforehand
-in this case, DHTs and SWNs require little bandwidth, because "network knows
where the block resides"
-in this case, FBNs, Hybrids, Social Discovery require much bandwidth, since
there is no benefit from the block's ID at all (they have to ask constantly)
-SWNs require less memory than DHTs, since there are less connections to other 
nodes
-SWNs relies less to neighbor nodes than DHTs
-proposol: most efficient approaches for this research problem are DHTs and
SWNs, since they are based on key-value pairs (Storm has a key as block ID)


b)

-compared to previous research problem, the "obvious"/"first seen" benefits of
DHTs and SWNs in this research problem are smaller
-we don't beforehand know which block is the most recent associated with a
specfic urn-5 name
-in theory, though, the most efficient algorithm is O(log n), *assuming* that we
already know the most recent block's ID (see previous research problem)
-the most important question is, how we can efficiently associate urn-5 names
with the most recent block / to all blocks which are associated with it
-for DHTs and SWNs:

Req. 1:
-each node maintains a local stack based data structure (urn-5 name -> most
recent local block ID) for every urn-5 names which node hosts. The most recent
block is topmost --> we don't have to check all blocks and their urn-5
associations to get the most recent

Req. 2:
-all urn-5 name mappings are stored as <key, value[ ]>, where the key is urn-5
name's hash and value is a record containing block ID and timestamp of that
block. So, when we store a block in our system first time, we have to create a
new key-value:  <hash_of_urn_5_name, [block id, block timestamp]> and route this
mapping to node which is "closest" to a hash value. Now when we want to find the
most recent block associated with a specific urn-5 name, we do:
        
1. locally compute a hash for given urn-5 string
2. route the query to a node which hosts the given hash of urn-5 ("closest" 
node)
3. get most recent block's ID using the idea from previuos idea
4. use ID to get the specific block using normal DHT/SWN operation
                
In this approach, we don't have to perform additional searching and sorting of
mappings. And of course, we know that for given urn-5, only one node hosts *all*
the block information ("block history") for the urn-5, since mappings are mapped
to a single node, closest to urn-5 hash value.  Again, this should work fine 
under
existing DHTs (and SWTs ?).
        
Some simple analysis: 
-there are more key-value pairs in the system for additional urn-5 --> block
associations
-however, I don't think this is an issue, since data's size is small
-efficiency: find node which hosts urn-5 names + find node which hosts blocks
associated with urn-5 name: logn + logn = 2logn (logarithmical)
        
-for FBS and others:
-there is no very efficient (simple) methods for finding urn-5 name associated
with the most recent block
-one simple proposal is that when we visit to each node (first idea above), get
only the most recent one and compare them (or greedy approach: dismiss 
currently 
most recent block as we visit to nodes, if newer block have been found)


c)

This is quite similar to previous research problem's answer. There are slight
differences, though.

-for DHTs and SWNs:

Req. 1:
-each node maintains a local stack based data structure (urn-5 name -> most
recent local block ID) for every urn-5 names which node hosts. The most recent
block is topmost --> we don't have to check all blocks and their urn-5
associations to get the most recent
Req. 2:
-all urn-5 name mappings are stored as <key, value[ ]>, where the key is urn-5
name's hash and value is a record containing block ID and timestamp of that
block. So, when we store a block in our system first time, we have to create a
new key-value:  <hash_of_urn_5_name, [block id, block timestamp]> and route this
mapping to node which is "closest" to a hash value. Now when we want to find the
most recent block associated with a specific urn-5 name, we do: 
        
1. locally compute a hash for given urn-5 string
2. route the query to a node which hosts the given hash of urn-5 ("closest" 
node)
3. get the specific block(s) data (block ID) from the stack which matches to
given date&time properties (we compare to block header data)
4. use IDs to get the specific blocks using normal DHT/SWN operation            
        
Some simple analysis: 
-there are more key-value pairs in the system for additional urn-5 --> block
associations
-however, I don't think this is an issue, since data's size is small
-efficiency: find node which hosts urn-5 names + find node which hosts blocks
associated with urn-5 name: logn + logn = 2logn (logarithmical)
        
-for FBS and others:
-there is no very efficient (simple) methods for finding urn-5 name associated
with the most recent block
-one simple proposal is that when we be that we visit to each node (first idea
above), get all blocks which matches to given properties


For any additional information, please see my research problems document (CVS).

Thanks,
-Hermanni



-------------------------------------------------
This mail sent through IMP: http://horde.org/imp/