DHT-related logics

Author(s): Arsen Kostenko.

This module implements a core DHT functionality, like finger-table manipulation and lookup search. Keep in mind that remote calls (known as remote predicate calls in Prolog) are extracted to a separate module as well as low-lever database handling. In turn, the logic module is utilized by higher-lever modules, like the server-2-server and server-2-client communication modules.

Id is treated as the value of the hash function used all over the DHT.

Documentation on exports

PREDICATE
Predicated performs the initialization of a single-node DHT.

Usage: dht_init(OwnId)

  • Description: 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.

PREDICATE
Get the node identifier (composition of identifier and IP-address) by using index in the finger table. Prolog synonym for finger[k].node.

Usage: dht_finger(Idx,Finger)

  • Description: 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.

PREDICATE
Wrapper around dht_finger/1, where first argument is defaulted to '1'

Usage: dht_successor(Successor)

  • Description: 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.

PREDICATE
dht_check_predecessor/1 predicate is called by external nodes when they run dht_stabilize/0. Since there is no other way to learn about a predecessor's failure, but checking explicitly once predecessor is required. that is why behavior of dht_check_predecessor is following:
  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)

  • Description: 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)

  • Description: 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.

PREDICATE
Perform search over current finger table, in order to find entry pointing to node that is more closely located to value supplied via Id. Here is original part of code from Chord paper.
  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)

  • Description: 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.

PREDICATE
Perform search over existing DHT structure. The resulting node is expected to precede the one identified by Id. Again, a small quote from Chord-paper source code.
  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)

  • Description: 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.

PREDICATE

Usage: dht_find_successor(Id,Successor)

  • Description: 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.

PREDICATE
It performs the join procedure on the node pointed by the argument. Here is the corresponding quote:
 n.join(Next){
     predecessor = nil;
     successor = Next.find_successor(n);
 }
            

Usage: dht_join(NodeIP)

  • Description: 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.

PREDICATE
This predicate performs 'notification'. Notification is part of adaptation process launched by dht_stabilize/0. A quote from Chord paper that refers to this section is given below:
 n.notify(NewNodeId){
     if (predecessor is nil ||
           NewNodeId in (predecessor, n)){
         predecessor = NewNodeId;
     }
 }
            

Usage: dht_notify(NewNode)

  • Description: 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.

PREDICATE
dht_stabilize

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);
 }
            
There is also a small simplification scheme, since before calling dht_join/1 each node assumes itself as the only member of the circle, the very first case of dht_stabilize/0 does nothing if successor is actually equal to current node.

Usage:

  • Description: 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.

PREDICATE
dht_fix_fingers

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:

  • Description: 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.

PREDICATE
This predicate is entirely used by remote calls. Since there is dht_rpr_id_by_node/2 for current module. This is an effort to avoid module-re-exportation (dht_routing.pl and dht_rpr.pl).

Usage: dht_id_by_node(Node,NodeID)

  • Description: 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.

PREDICATE
dht_find_and_consult_b/2 is meant to perform two actions:
  • search for the node responsible for value supplied as a Key;
  • perform dht_consult_server_b/3 on a node found.
This is the first predicate of the whole dht_find_and_*/2 family of predicates. Name of each member of the family gives a hint on implementation. And as it is presented by the name of the family, they share some part of implementation - all the members of the family perform search for particular DHT-node, which is achieved by find_server/3 predicate.

Usage 1: dht_find_and_consult_b(Key,Value)

  • Description: 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)

  • Description: 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.

PREDICATE
Basically forms the second half of dht_find_and_consult/2 predicate. This predicate takes no care about search of corresponding server. The only thing it does - given a server try to locate a predicate under given Key there. Of course there two possible variants of application:

Usage 1: dht_consult_server_b(NodeId,Key,Value)

  • Description: 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)

  • Description: 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.

PREDICATE
dht_find_and_consult_nb/2 is meant to perform two actions: This is the first predicate of the whole dht_find_and_*/2 family of predicates. Name of each member of the family gives a hint on implementation. And as it is presented by the name of the family, they share some part of implementation - all the members of the family perform search for particular DHT-node, which is achieved by find_server/3 predicate.

Usage 1: dht_find_and_consult_nb(Key,Value)

  • Description: 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)

  • Description: 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.

PREDICATE
Basically forms the second half of dht_find_and_consult/2 predicate. This predicate takes no care about search of corresponding server. The only thing it does - given a server try to locate a predicate under given Key there. Of course there two possible variants of application:

Usage 1: dht_consult_server_nb(NodeId,Key,Value)

  • Description: 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)

  • Description: 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.

PREDICATE
dht_find_and_extract_b/2 is meant to perform two actions: Unlike dht_find_and_consult/2, this predicate removes matching records form the local databases of the corresponding nodes.

Usage 1: dht_find_and_extract_b(Key,Value)

  • Description: 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)

  • Description: 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.

PREDICATE
This predicate is also used entirely as a second part of dht_find_and_extract/2 predicate. It's behavior differs from similar dht_consult_server_b/3 predicate, only in action that is performed over DHT. In this case 'extraction' of predicates, instead of simple 'consultation'

Usage 1: dht_extract_from_server_b(NodeId,Key,Value)

  • Description: 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)

  • Description: 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.

PREDICATE
dht_find_and_extract_nb/2 is meant to perform two actions: Unlike dht_find_and_consult/2, this predicate removes matching records form the local databases of the corresponding nodes.

Usage 1: dht_find_and_extract_nb(Key,Value)

  • Description: 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)

  • Description: 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.

PREDICATE
This predicate is also used entirely as a second part of dht_find_and_extract/2 predicate. It's behavior differs from similar dht_consult_server_b/3 predicate, only in action that is performed over DHT. In this case 'extraction' of predicates, instead of simple 'consultation'

Usage 1: dht_extract_from_server_nb(NodeId,Key,Value)

  • Description: 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)

  • Description: 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.

PREDICATE
First part of this predicate is similar to rest of dht_find_and_*/2 family - perform search over existing DHT structure. After search - storage operation is performed.

Usage: dht_find_and_store(Key,Value)

  • Description: 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.
    Since the arguments of dht_store_to_server/4 must be ground both arguments of dht_find_and_store are ground too.
  • The following properties should hold at call time:
    (basic_props:int/1)Key is an integer.
    (basic_props:gnd/1)Value is ground.

PREDICATE
Second part of dht_find_and_store/2 predicate.

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

  • Description: 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.