Finger table and routing information

Author(s): Arsen Kostenko.

This module holds the basic operations over the finger table and other routing information. Developed for the sake of simplicity, it should be used only within the dht_logic.pl file. Probably the most important and abstract part of the routing is the finger table. Here is a finger table copy of the node representing identifier 0 (from the Chord paper):

 finger_table(1, 1, finger_interval(1,2), 1).
 finger_table(2, 2, finger_interval(2,4), 3).
 finger_table(3, 4, finger_interval(4,0), 0).

This table reflects the case where there are 8 identifiers in total in the identifier circle and three running nodes with identifiers 0, 1, and 3. In general each entry can be represented as finger_table(idx, start, interval, succ). Here is a brief description of each argument:

idx - Since arrays are not native for Prolog, I put the index as the first argument to the finger_table predicate to achieve indexing.
start - ID that starts the corresponding section of the table.
interval - IDs that fit into the corresponding section of table, represented in the form: finger_interval(interval_start, interval_end)., where:
succ - ID of node responsible for the corresponding section of table, represented in node_id(id, ip). form, where:

Usage and interface

Library usage:
:- use_module(library(dht_routing)).
Exports:
- Predicates:
  dht_finger_table/2, dht_finger_start/2, dht_update_finger/2, dht_set_finger/4, dht_predecessor/1, dht_set_predecessor/1, dht_reset_predecessor/0.
Imports:
- Packages:
  prelude, nonpure, assertions, regtypes, isomodes.

Documentation on exports

PREDICATE

dht_finger_table/2:

It serves as a read-only interface to the finger table information as follows: Idx stands for an index in an array, and Node is the number of the node which is recorded in the entry with that index.

Usage 1:dht_finger_table(Idx,Node)

This case is equal to getting any (possibly random) entry from the finger table.

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

Usage 2:dht_finger_table(Idx,Node)

Get some (one or several if backtracking is exploited) indexes that mention particular node numer, supplied as Node.

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

Usage 3:dht_finger_table(Idx,Node)

Get the identifier of the node, indexed by Idx. Theoretically, there should be no more than on entry for each value of index.

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

Usage 4:dht_finger_table(Idx,Node)

Check whether a particular combination (index and node number) is present in finger table.

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

PREDICATE

dht_finger_start/2:

This predicate may be regarded as a read-only interface to map between the index is a finger table and the beginning of the section of the DHT circle.

Usage 1:dht_finger_start(Idx,NextId)

Get any entry, in other words and entry that has any index and points to any segment in the circle. Common constraints on finger tables, do hold anyway:

result unifies with the content of finger table;
predicate enumerates possible results on backtracking.

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

Usage 2:dht_finger_start(Idx,NextId)

Ask for the index of entry that mentions a particular node as the starting one.

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

Usage 3:dht_finger_start(Idx,NextId)

Get the starting node for a certain entry of finger table.

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

Usage 4:dht_finger_start(Idx,NextId)

Check for the presence of a correspondence between a certain entry and its starting node.

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

PREDICATE

dht_update_finger/2:

dht_update_finger/2 takes care of changing node value to NodeId for entry with index number equal to Idx. This predicate has entirely imperative behavior. Both arguments are to be ground at the moment of call.

Usage:dht_update_finger(Idx,NodeId)

Stores supplied information, previously erasing all old information.

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

PREDICATE

dht_set_finger/4:

This predicate sets the value of finger table entries. If any entry with the same index (Idx) exists, it is erased before new value is asserted.

Usage:dht_set_finger(Idx,Start,End,Node)

All the arguments are to be ground and of type integer.

The following properties should hold at call time:
(basic_props:int/1)Idx is an integer.
(basic_props:int/1)Start is an integer.
(basic_props:int/1)End is an integer.
(basic_props:int/1)Node is an integer.

PREDICATE

dht_predecessor/1:

A common read-only interface to get or check the ID of the predecessor node.

Usage 1:dht_predecessor(PredId)

Get number of predecessor node.

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

Usage 2:dht_predecessor(PredId)

Check whether particular number is associated with current predecessor.

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

PREDICATE

dht_set_predecessor/1:

Write interface for predecessor ID. It checks the type of its argument and saves argument locally.

Usage:dht_set_predecessor(PredId)

Save PredId as the ID of predecessor for current node.

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

PREDICATE

dht_reset_predecessor/0:

Set value of preceding node index to 'nil' whatever it's prior value is.

Finger table and routing information

Usage and interface

Documentation on exports

Module Sections

Global Links

Indices