Bahir Dar University
Bahir Dar Institute of Technology
Faculty of Computing
Distributed Systems Assignment
Hierarchical Approaches
Group members
1. Adugna Admassu (1603362)
2. Animut Alemeneh (1306126)
3. Ashenafi Alebachew (1306912)
4. Berihun Tessema (1307139)
5. Bezawit Getnet (1603374)
6. Esubalew Sintie (1307570)
7. Yostiena Negash (1603362)
Submitted To፡ Mr. Kokeb
Submission Date: July 18, 2024
What is Naming in Distributed Systems?
Naming in distributed systems is a fundamental concept that involves assigning unique
identifiers to resources, objects, services, and entities within a network. These identifiers, or
names, allow users and programs to locate and interact with these resources across a distributed
environment. The primary goals of naming systems are to ensure:
1. Uniqueness: Each name uniquely identifies a single resource or entity, preventing
conflicts and ensuring that each query returns the correct resource.
2. Scalability: The naming system should handle a large number of names efficiently,
allowing the system to grow without significant performance degradation.
3. Reliability: The system should be robust against failures and changes, ensuring
consistent access to resources even in the face of network issues or node failures.
Flat Naming
Flat naming refers to a type of naming system where identifiers are simple, unstructured bit
strings. These names do not convey any hierarchical or locational information about the entities
they identify. This simplicity makes flat names easy to generate and ensures their uniqueness, but
it also introduces challenges in locating and managing entities.
Hierarchical Approaches
Hierarchical approaches in distributed systems organize the network into a structured, multi-level
hierarchy, enhancing the efficiency of locating and managing entities. This method reduces
complexity and search times, making it easier to resolve names across the network.
Characteristics of Hierarchical Approaches
1. Multi-level Structure:
○ The network is divided into levels, with each level managing a subset of entities.
○ This creates a tree-like structure where higher-level nodes oversee and manage
lower-level nodes.
2. Forwarding Pointers:
○ Entities leave pointers at old locations pointing to their new locations when they
move within the network.
○ These forwarding pointers ensure that queries directed to old locations are
redirected to the entity's current location.
3. Centralized Knowledge:
○ Higher-level nodes possess more comprehensive knowledge of the network
topology and entity locations.
○ They play a crucial role in guiding queries and managing the overall structure of
the hierarchical system.
4. Reduced Search Complexity:
○ Queries are resolved more efficiently by traversing fewer nodes.
○ The hierarchical structure allows for quicker resolution times as queries are
directed from higher-level nodes down to the specific entity.
Hierarchical Approaches in Flat Naming Systems
1. Hierarchy of Nodes:
○ Nodes are organized in a hierarchical tree structure, where each level corresponds
to a different administrative or geographical scope.
○ For instance, in a corporate setting, global offices may represent the highest level,
followed by regional offices, and then local offices at the lowest level.
2. Forwarding Pointers:
○ When an entity relocates, it leaves behind a forwarding pointer at its old location.
○ Mid-level and top-level nodes update their pointers to reflect the entity's new
location, ensuring efficient query redirection.
3. Query Resolution:
○ Queries originate at the top-level nodes and are directed through the hierarchy to
locate the desired entity.
○ This hierarchical navigation reduces the search space and minimizes the chain of
pointer traversals, optimizing query resolution.
Pros of Hierarchical Approaches
1. Efficiency:
○ Reduces the length of forwarding pointer chains, leading to faster query
resolution.
○ Minimizes the number of nodes involved in updating pointers, enhancing overall
system efficiency.
2. Scalability:
○ Handles large networks effectively by breaking them into manageable clusters at
different hierarchical levels.
○ Each level manages a smaller subset of nodes, improving scalability and
performance.
3. Manageability:
○ Easier to maintain and update compared to flat naming structures.
○ Each hierarchical level can independently manage its subset of entities and
administrative tasks, simplifying system administration.
4. Fault Tolerance:
○ Failures at lower levels can often be contained and managed locally without
impacting the entire system.
○ Higher-level nodes can assume additional responsibilities or redistribute tasks in
case of lower-level failures, enhancing system reliability.
Cons of Hierarchical Approaches
1. Complexity:
○ Implementing and maintaining a hierarchical structure requires careful planning
and design.
○ Higher-level nodes may become bottlenecks or single points of failure,
necessitating robust management strategies.
2. Overhead:
○ Additional communication and processing overhead are needed to maintain and
synchronize the hierarchical structure.
○ Updates and queries involve multiple levels, potentially increasing latency and
resource consumption.
3. Resource Intensive:
○ Higher-level nodes require more resources to manage their larger subset of the
network.
○ Balancing the load across nodes at different hierarchical levels can be challenging
and may require sophisticated load-balancing algorithms.
Use Case: Domain Name System (DNS)
The Domain Name System (DNS) is a hierarchical naming system used on the Internet to
translate domain names (e.g., [Link]) into IP addresses (e.g., [Link]) that
computers use to identify each other on the network.
Hierarchical Approach Implementation:
1. Hierarchy of Nodes:
○ Root Level: At the top of the DNS hierarchy is the root domain, represented by a
dot (.), which denotes the root DNS servers. These servers maintain information
about the authoritative name servers for top-level domains (TLDs).
○ Top-Level Domains (TLDs): Below the root are TLDs such as .com, .org, .net,
and country-code TLDs like .us, .uk, etc. Each TLD is managed by a set of
authoritative name servers responsible for domains registered under that TLD.
○ Second-Level Domains: Below the TLDs are the second-level domains (SLDs),
such as [Link] or [Link]. These domains are managed by authoritative
name servers designated by the domain registrants.
○ Subdomains: Further subdivisions of domains can occur, creating a tree-like
structure (e.g., [Link], [Link]), where each level in the
hierarchy represents a different administrative or organizational scope.
2. Forwarding Pointers:
○ DNS uses resource records (like A records for IPv4 addresses and AAAA records
for IPv6 addresses) to store mappings between domain names and IP addresses.
○ When a domain is moved or reconfigured, updated DNS records (including
forwarding pointers) ensure that queries for that domain are correctly redirected to
its current IP address.
3. Query Resolution:
○ When a user or application queries a domain name (e.g., [Link]), the
DNS resolver starts by querying the root DNS servers to determine the
authoritative name servers for the appropriate TLD (.com).
○ It then queries the authoritative name servers for the .com TLD to obtain the
authoritative name servers for [Link].
○ Finally, it queries the authoritative name servers for [Link] to obtain the IP
address associated with [Link].
In summary, naming in distributed systems is crucial for identifying and locating entities. Flat
naming offers simplicity and scalability but lacks locational information, making it harder to
manage and resolve names. Hierarchical approaches address these challenges by organizing the
network into levels, reducing search complexity, and improving efficiency. However, they
introduce additional complexity and overhead, requiring careful implementation and
management.