Naming systems are used inside Distributed Systems to provide location transparency, and also fragmentation and replication transparency.

  • Address: contains the entities current location (e.g. IP address)
  • Name: identifies entity independent of location (e.g. domain name / file path), prerequisite for distribution transparency
    • Flat names: have no structure, often random bit strings, good for machines but difficult for humans
    • Structured names: have a hierarchically structured name space e.g. URLs, directories, easy to read for humanss
  • Name space: set of all possible names

Name system is responsible for resolving addresses based on names. The name space can be partitioned and replicated over nodes inside the system.

Flat names #

Broadcast #

An entity is located by sending a broadcast to all nodes. Every node checks whether it has the address and replies if it has. This results in al partitioned name space where every node only knows its local entities.

Distributed Hash Table (DHT): chord system #

  • Name space partitioned according to a hash function
  • Hash identifier has $m$ bits, keys are in range $[0, 2^{m}-1]$
  • Entity falls under successor node with smallest $id \geq k$ denoted as $succ(k)$
  • Each node has a finger table: $FT_p[i] = succ(p + 2^{i-1})$
  • Lookup key $k$ forward to node $q = FT_p[j] \leq k < FT_p[j+1]$

Structured names #

Hierarchical name spaces #

  • Are represented as a directed graph in which the leaf nodes are entities.
  • Typically partitioned where each name server stores one partition
  • Highly scalable: DNS

Name resolution #

  • Iterative: send message to each name server to resolve each part
  • Recursive: message is send to root server which forward requests recursively
    • Higher demand on each server
    • Caching becomes more effective
    • Communication cost may be recuded when distance to client is big and name servers are close to each other

Attribute-based naming #

  • Example is X.500 / LDAP, a standardized protocol that allows naming things by attributes.
  • Much more powerful than DNS by allowing search on entities based on attributes.