DHT-related logics

Usage:dht_init(OwnId)

The predicate is intended to perform various initialization functions like finger_table creation, hostname and IP address retrieval. The value supplied in OwnId is treated as value of the hash function used all over the DHT.

• The following properties should hold at call time:
  (basic_props:int/1)OwnId is an integer.

Usage:dht_finger(Idx,Finger)

dht_finger/2 implements the array looking up necessary to retrive information from the finger table, where first argument Idx if acting as array index and Finger as corresponding array value.

• The following properties should hold at call time:
  (basic_props:int/1)Idx is an integer.
  (term_typing:var/1)Finger is a free variable.
• The following properties should hold upon exit:
  (basic_props:int/1)Idx is an integer.
  (basic_props:gnd/1)Finger is ground.

Usage:dht_successor(Successor)

dht_successor/1 a simple wrapper around dht_finger/2, that looks up the first row of so-called finger-table

• The following properties should hold at call time:
  (term_typing:var/1)Successor is a free variable.
• The following properties should hold upon exit:
  (basic_props:gnd/1)Successor is ground.

1. give 'nil' as predecessor if it is stored in database that way, which happens if node is unaware of any other nodes on the ring,
2. otherwise, get current value of predecessor,
3. try calling predecessor with any arbitrary predicate in our case dht_successor/1,
4. if an exception is issued by remote call - reset predecessor to 'nil',
5. get value of predecessor once again and bind this value to the answer. We also check that in case of finger-nodes failure, but this would work out only in poorly populated Chord-ring

Usage 1:dht_check_predecessor(PredecessorId)

Get value of predecessor for current node.

• The following properties should hold at call time:
  (term_typing:var/1)PredecessorId is a free variable.
• The following properties should hold upon exit:
  (basic_props:gnd/1)PredecessorId is ground.

Usage 2:dht_check_predecessor(PredecessorId)

Check whether value supplied is equal to id of predecessor.

• The following properties should hold at call time:
  (basic_props:gnd/1)PredecessorId is ground.
• The following properties should hold upon exit:
  (basic_props:gnd/1)PredecessorId is ground.

  n.closest_preceding_finger(id){
      for i = m downto 1 {
         if (finger[i].node in (n, id)){
            return finger[i].node;
         }
      }
      return n;
  }
            

Usage:dht_closest_preceding_finger(Id,Finger)

dht_closest_preceding_finger/2 is searching local finger-table for the entry which points to a node, that is 'closer' (in terms of DHT distance) to the identifier specified at Id. It should hold that identifier of the node found is greater than identifier of current node and lesser than the identifier supplied in Id. No estimations concerning other nodes in between them are made. Furthermore, a cyclic structure of identifiers is preserved: identifier '0' is lesser then identifier '1' but greater then the highest identifier in DHT.

• The following properties should hold at call time:
  (basic_props:int/1)Id is an integer.
  (term_typing:var/1)Finger is a free variable.
• The following properties should hold upon exit:
  (basic_props:int/1)Id is an integer.
  (basic_props:gnd/1)Finger is ground.

  n.find_predecessor(id){
      n' is n,
      while(id not_in (n', n'.successor] ){
         n' = n'.closest_preceding_finger(id);
      }
      return n';
  }
            

Usage:dht_find_predecessor(Id,Predecessor)

dht_find_predecessor/2 searches all over DHT for a node, which is 'the closest' (in terms of DHT distance) to the index specified as Id. In other words, the searched node must have the index lesser than the identifier specified in Id and there must not be any other nodes between identifier specified in Id and the node found.

• The following properties should hold at call time:
  (basic_props:int/1)Id is an integer.
  (term_typing:var/1)Predecessor is a free variable.
• The following properties should hold upon exit:
  (basic_props:int/1)Id is an integer.
  (basic_props:gnd/1)Predecessor is ground.

Usage:dht_find_successor(Id,Successor)

dht_find_successor/2 has behavior similar to dht_find_predecessor/2 except that it gives a node that directly succeeds the identifier specifies. In other words, the identifier of the node found is greater than the identifier specified in Id and there are no other nodes between the node found and the node specified in Id

• The following properties should hold at call time:
  (basic_props:int/1)Id is an integer.
  (term_typing:var/1)Successor is a free variable.
• The following properties should hold upon exit:
  (basic_props:int/1)Id is an integer.
  (basic_props:gnd/1)Successor is ground.

 n.join(Next){
     predecessor = nil;
     successor = Next.find_successor(n);
 }
            

Usage:dht_join(NodeIP)

dht_join/2 is executed every time some node decides to join some DHT. The only information needed for execution of join is a valid ID / IP combination of any existing node, which must be supplied with NodeId

• The following properties should hold at call time:
  (basic_props:atm/1)NodeIP is an atom.

 n.notify(NewNodeId){
     if (predecessor is nil ||
           NewNodeId in (predecessor, n)){
         predecessor = NewNodeId;
     }
 }
            

Usage:dht_notify(NewNode)

dht_notify/1 is called on current node, once any other DHT node specified by NewNode regards current node at it's successor.

• The following properties should hold at call time:
  (basic_props:gnd/1)NewNode is ground.

Perform stabilization on the successor node by asking successor's predecessor value. If the value returned is equal to current node, just stay calm, otherwise try to adopt the newly returned result as new successor. Most of the 'dirty' work is performed by stabilize_successor/2 predicate. The corresponding Chord-paper quote is given below:

 n.stabilize(){
     x = successor.predecessor;
     if (x in (n, successor)){
         successor = x;
     }
     successor.notify(n);
 }
            

Usage:

dht_stabilize/0 is a eternally repeated predicate, which aims at stabilizing first-level references of the finger-table, while multiple concurrent joins and failures can happen. Its main goal is to ask its own successor to report its predecessor. If the reported node is different from the one that is calling dht_stabilize/0, there should be someone in between current node and its the successor. So a newly reported node should be registered as the successor instead of an old one. Technically, once an inconsistency between actual state of DHT and finger-table is found a newly found node is asked to perform dht_notify/1, with current node as an argument.

This predicate takes care of maintaining the finger table entries (except the first one) up to date. The first entry is taken care of by a specialized predicate dht_stabilize/0, since there is much more responsibility on first entry (a direct successor). Rest of the same task is performed here, by dht_fix_fingers/0. In the Chord paper notation this part look like:

 n.fix_fingers(){
     i = random index > 1 into finger[];
     finger[i].node = find_successor(finger[i].start);
 }  
            

Usage:

dht_fix_fingers/0 is yet another randomly repeated predicate, which aims at stabilizing high-level references of finger-table, while multiple concurrent joins and failures happen. Once started, dht_fix_fingers/0 picks a random (but not first) entry of finger table, and searches for a node responsible for the identifiers specified in the entry. In case, node that was found is different from the one currently specified, current node is replaced by a new one.

Usage:dht_id_by_node(Node,NodeID)

Get node identity by node number.

• The following properties should hold at call time:
  (basic_props:int/1)Node is an integer.
  (term_typing:var/1)NodeID is a free variable.
• The following properties should hold upon exit:
  (basic_props:int/1)Node is an integer.
  (basic_props:gnd/1)NodeID is ground.

• search for the node responsible for value supplied as a Key;
• perform dht_consult_server_b/3 on a node found.

Usage 1:dht_find_and_consult_b(Key,Value)

An invocation of this type would bind all free variables in Value to the values present in the local database of the node responsible for Key.

• The following properties should hold at call time:
  (basic_props:int/1)Key is an integer.
  (term_typing:var/1)Value is a free variable.
• The following properties should hold upon exit:
  (basic_props:int/1)Key is an integer.
  (basic_props:gnd/1)Value is ground.

Usage 2:dht_find_and_consult_b(Key,Value)

Invocation with two ground arguments is equal to checking the presence of the term specified by Value inside the DHT.

• The following properties should hold at call time:
  (basic_props:int/1)Key is an integer.
  (basic_props:gnd/1)Value is ground.

Usage 1:dht_consult_server_b(NodeId,Key,Value)

First variant deals with real consulting, when the value is unknown. Therefore, after predicate is successfully executed, a real value, that is stored under Key is associated with third argument (Value)

• The following properties should hold at call time:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (term_typing:var/1)Value is a free variable.
• The following properties should hold upon exit:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.

Usage 2:dht_consult_server_b(NodeId,Key,Value)

Second variant is more similar to check for existence, All arguments are ground by the time predicate is called, so the only use is success/failure of predicate itself.

• The following properties should hold at call time:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.
• The following properties should hold upon exit:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.

• search for the node responsible for value supplied as a Key;
• perform dht_consult_server_nb/3 on a node found.

Usage 1:dht_find_and_consult_nb(Key,Value)

An invocation of this type would bind all free variables in Value to the values present in the local database of the node responsible for Key.

• The following properties should hold at call time:
  (basic_props:int/1)Key is an integer.
  (term_typing:var/1)Value is a free variable.
• The following properties should hold upon exit:
  (basic_props:int/1)Key is an integer.
  (basic_props:gnd/1)Value is ground.

Usage 2:dht_find_and_consult_nb(Key,Value)

Invocation with two ground arguments is equal to checking the presence of the term specified by Value inside the DHT.

• The following properties should hold at call time:
  (basic_props:int/1)Key is an integer.
  (basic_props:gnd/1)Value is ground.

Usage 1:dht_consult_server_nb(NodeId,Key,Value)

First variant deals with real consulting, when the value is unknown. Therefore, after predicate is successfully executed, a real value, that is stored under Key is associated with third argument (Value)

• The following properties should hold at call time:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (term_typing:var/1)Value is a free variable.
• The following properties should hold upon exit:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.

Usage 2:dht_consult_server_nb(NodeId,Key,Value)

Second variant is more similar to check for existence, All arguments are ground by the time predicate is called, so the only use is success/failure of predicate itself.

• The following properties should hold at call time:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.
• The following properties should hold upon exit:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.

• search for node responsible for value supplied as a Key;
• perform dht_extract_from_server_b/3 on a node found.

Usage 1:dht_find_and_extract_b(Key,Value)

An invocation of this type would bind all free variables in Value to values present in the local database of the corresponding node, and the values against which the matching was performed are erased.

• The following properties should hold at call time:
  (basic_props:int/1)Key is an integer.
  (term_typing:var/1)Value is a free variable.
• The following properties should hold upon exit:
  (basic_props:int/1)Key is an integer.
  (basic_props:gnd/1)Value is ground.

Usage 2:dht_find_and_extract_b(Key,Value)

Invocation with two ground arguments is equal to checking presence of term specified by Value inside the DHT, and removing it in case of successful search.

• The following properties should hold at call time:
  (basic_props:int/1)Key is an integer.
  (basic_props:gnd/1)Value is ground.

Usage 1:dht_extract_from_server_b(NodeId,Key,Value)

First variant deals with blind 'extraction', when the value is unknown. Therefore, after predicate is successfully executed, a real value, that is stored under Key is associated with third argument (Value)

• The following properties should hold at call time:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (term_typing:var/1)Value is a free variable.
• The following properties should hold upon exit:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.

Usage 2:dht_extract_from_server_b(NodeId,Key,Value)

Second variant is more similar to pointed elimination. All arguments are ground by the time predicate is called, so the only use is success and elimination of predicate itself or general failure on contrary.

• The following properties should hold at call time:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.
• The following properties should hold upon exit:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.

• search for node responsible for value supplied as a Key;
• perform dht_extract_from_server_nb/3 on a node found.

Usage 1:dht_find_and_extract_nb(Key,Value)

An invocation of this type would bind all free variables in Value to values present in the local database of the corresponding node, and the values against which the matching was performed are erased.

• The following properties should hold at call time:
  (basic_props:int/1)Key is an integer.
  (term_typing:var/1)Value is a free variable.
• The following properties should hold upon exit:
  (basic_props:int/1)Key is an integer.
  (basic_props:gnd/1)Value is ground.

Usage 2:dht_find_and_extract_nb(Key,Value)

Invocation with two ground arguments is equal to checking presence of term specified by Value inside the DHT, and removing it in case of successful search.

• The following properties should hold at call time:
  (basic_props:int/1)Key is an integer.
  (basic_props:gnd/1)Value is ground.

Usage 1:dht_extract_from_server_nb(NodeId,Key,Value)

First variant deals with blind 'extraction', when the value is unknown. Therefore, after predicate is successfully executed, a real value, that is stored under Key is associated with third argument (Value)

• The following properties should hold at call time:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (term_typing:var/1)Value is a free variable.
• The following properties should hold upon exit:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.

Usage 2:dht_extract_from_server_nb(NodeId,Key,Value)

Second variant is more similar to pointed elimination. All arguments are ground by the time predicate is called, so the only use is success and elimination of predicate itself or general failure on contrary.

• The following properties should hold at call time:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.
• The following properties should hold upon exit:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)Value is ground.

Usage:dht_find_and_store(Key,Value)

dht_find_and_store/2 is meant to perform two actions:

• search for a node responsible for the value supplied as Key;
• perform dht_store_to_server/4 on node found.

• The following properties should hold at call time:
  (basic_props:int/1)Key is an integer.
  (basic_props:gnd/1)Value is ground.

Usage:dht_store_to_server(NodeId,Key,KeyHash,Value)

Store Value under given Key and also record relation between Key and KeyHash.

• The following properties should hold at call time:
  (basic_props:gnd/1)NodeId is ground.
  (basic_props:gnd/1)Key is ground.
  (basic_props:gnd/1)KeyHash is ground.
  (basic_props:gnd/1)Value is ground.