202402271208
Status: #idea
Tags: DC

Name and Identity Resolution

• Names - Entities in a distributed system
• To operate an entity, there should be an access point
• Access point has an address

Naming types

• Flat naming
  • Simple broadcasting (ARP)
  • Name carries no information about how to locate the access point of the entity
• Structured naming
  • Names that humans can understand (a path)
  • Eg. DNS, Network file server
• Attribute naming
  • Name that can be searched easily
  • Eg. LDAP, Active Directory

Chord-based Distributed Hash Table

• Each node is assigned a unique random $m$-bit identifier (128-160 bit)
• Entity with key $k$ falls under jurisdiction of node with smaller $id\ge k$
  • Called its successor $succ(k)$

Chord Finger Table (FT)

• Each node $p$ maintains FT (array) where $|FT|\le m$
  • $${FT}_p[i]=succ(p+2^{i-1})$$
  • ${FT}_p[i$] stores the successor of node $p$ at certain distance. The links are at exponential distances
  • ${FT}_p[1]$ is the immediate successor of $p$ always
• To lookup a key $k$, node $p$ forwards the request to node $q={FT}_p[j]$ such that:
  • $q={FT}_p[j]{FT}_p[j]\le k<{FT}_p[j+1]$
  • $q={FT}_p[1]TODO$
  • TODO SLIDE 6
• Example: Chord with $m=5$
  • TODO image from slide
  • $succ(26)$ -> Choose a random node, in this case node $1$
  1. Node $1$ searches its FT, since $FT[5]=18<26$, forward the request to node $18$
  2. In node $18$, $FT[2]<26<FT[3]$. Send it to node $20=FT[2]$
  3. In node $20$, $FT[1]<26<FT[2]$. Send it to node $21=FT[1]$
  4. In node $21$, $FT[1]>26$, hence, it has to be in node $28=FT[1]$
  5. In node $28$, search stops and value attached to key $26$ is sent to node $1$
• Order of search space is $O({\log }_{2}N)=O(m)$

Dealing with Failures

• Node joining and leaving at random
• Joining
  • Node $p$ wants to join. It requests a lookup for $succ(p+1)$
• To ensure $FT[1]$ of every node $q$ is not wrong, periodically recompute (TODO)

forever {
	node q requests r = succ(q + 1) to return p = pred(r).
	if (q != p) then q < p <= succ(q+1), hence FT_q[1] = p
	else break
}

• To update finger table, update sucessor of each entry in FT
• Each $q$ pings $pred(q)$ to check if it is alive. If not, mark $pred(q)=\perp$
  • When $p$ requests $q$, to reutrn $pred(q)$ and recieves $\perp$, then notify $q$ to set $pred(q)=p$

Implementing Chord ($m$-bit)

TODO slide 9

# len(node_set) =


def succ(key):
    if key < node_set[0]:
        return node_set[0]
    elif key > node_set[len(node_set) - 1]:
        return node_set[m - 1]
    for node in node_set:
        if key < node:
            return node


def finger(i):
    return succ((ID + 2 ** (i - 1)) % MAXPROC)


def recomputeFingerTable():
    FT[0] = node_set[(ID - 1) % len(node_set)]
    FT[1:] = [finger() for i in range(1, m + 1)]
    FT.append(ID)


def localSuccNode(key):
    if FT[0] < key <= ID:  # self has the key
        return ID
    elif ID < key <= FT[1]:
        pass
    else:
        pass

Exploiting Network Proximity

• Topology-awaare node assigment
  • When assigning an ID to a node, make sure that nodes close in the ID space are also close in the network
  • Very difficult in practice
• Prooximity routing
  • Maintain more than one possible successor, and forward to the closest
  • Store pointers to other nodes in $[p+2^{i-1},p+2^i-1]$
  • $F{T}_p[i]$ points to the first node in this list
• Proximity neighbour selection
  • Whee there is a choice of selecting who your neighbour is, pick the clostest one
  • Pastry system (internet-based DHT) to ensure fault tolerance - Not strictly Chord

Structured Naming

• Naming graph (DAG)
  • A leaf node -> A named entity
  • A director node refers to other nodes
  • Typically has a single root node

References