Unit-03, 04
1.Explain flat naming and structured naming with example.
→ Flat Naming
Definition:
A flat naming system assigns a name to each entity that is a unique, unstructured identifier.
These names do not contain any information about the entity’s location or relationship with
other entities.
Characteristics:
● No Structure: Names are just bit strings or random identifiers (e.g., MAC addresses,
UUIDs).
● Global Uniqueness: Every entity must have a unique name across the system.
● Location Independence: The name does not reveal the physical or network location.
● Direct Matching: Name resolution is usually done by a direct table lookup or hashing.
Advantages:
● Simple to generate and use.
● Good for systems where the number of entities is small or static.
Disadvantages:
● No grouping or hierarchical management.
● Searching is inefficient if exact name is not known.
Example:
● MAC Address: Every network card has a 48-bit unique identifier assigned by the
manufacturer.
● UUID: Universally Unique Identifiers used in databases.
Implementation Approaches:
● Broadcasting: Send a request to all nodes to find the entity (works only for small
LANs).
● Home-Based Approach: Store the mapping in a home node that knows the current
location of the entity.
● Distributed Hash Tables (DHTs): Map names to nodes using hashing for scalability.
Structured Naming
Definition:
In a structured naming system, names are organized into a hierarchical or structured format
where the name components define relationships or containment.
Characteristics:
● Hierarchical Organization: Names are divided into multiple levels (e.g., root,
subdomain, host).
● Delegation: Responsibility for name management can be delegated to different
authorities at different levels.
● Efficient Search: The structure allows partial name resolution step by step.
● Scalability: Can support very large name spaces.
Advantages:
● Easy to manage large numbers of entities.
● Supports location transparency and migration.
● Allows administrative control at different hierarchy levels.
●
Disadvantages:·
● Slightly more complex resolution process.
● Requires maintenance of multiple name servers.
Example:
● Domain Name System (DNS):
● www.example.com
§ .com → top-level domain
§ example → second-level domain
§ www → host name
● The resolution starts at the root name server, then proceeds to .com server, then to
example server.
Implementation:
● Name Resolution: Can be done iteratively (client queries each server) or
recursively (servers forward the request).
● Name Space Structure: May be global (shared by all users), administrative
(restricted to organizations), or local.
2.Write a short note on desirable features of a good naming system.
→ Desirable Features of a Good Naming System
● Location transparency : This feature implies the name of an object should not reveal
any hint as to the physical location of the object, directly or indirectly. An object’s
name should be independent of the physical location or underlying topology of the
system, or the current location of the physical entity.
● Location independency : For performance, reliability, availability, and security
reasons, distributed systems provide the facility of object migration without changing
its name. Location independency means that the name of an object need not be
changed when the object’s location changes.
● Scalability : Distributed systems vary in size ranging from one with a few nodes to
one with many nodes. Distributed systems are normally open systems and their size
changes dynamically.
● Uniform naming convention : In most distributed systems, different naming
conventions are used for naming different types of objects. For example, file names
typically differ from user names and process names. Instead of using such
non-uniform naming conventions, a good naming system should use the same naming
convention for all types of objects in the system.
● Multiple user-defined names for the same object : For a shared object, it is desirable
that different users of the object can use their own convenient names for accessing it.
Therefore, a naming system must provide the flexibility to assign multiple
user-defined names to the same object.
● Group naming : A naming system should allow many different objects to be identified
by the same name. Such a facility is useful to support broadcast facility or to group
objects for conferencing or other applications.
● Meaningful names : A name can be simply any character string identifying some
object. However, for users, meaningful names are preferred to lower-level identifiers
such as memory pointers, disk block numbers or network addresses.
● Performance : The performance measurement of a naming system is the amount of
time needed to map an object’s name to its attributes, such as its location. The naming
system should be efficient so that the number of messages exchanged in a
name-mapping operation is as small as possible.
● Fault tolerance : A naming system should be capable of tolerating, to some extent,
faults that occur due to the failure of a node or a communication link in a distributed
system network. That is, the naming system should continue functioning, perhaps in a
degraded form, in the event of these failures.
● Replication transparency : In a distributed system, replicas of an object are generally
created to improve performance and reliability. A naming system should support the
use of multiple copies of the same object in a user-transparent manner.
○
3.Discuss flat naming, structured naming, and attribute-based naming with
examples.
→ Flat Naming
Definition:
A flat naming system assigns a name to each entity that is a unique, unstructured identifier.
These names do not contain any information about the entity’s location or relationship with
other entities.
Characteristics:
● No Structure: Names are just bit strings or random identifiers (e.g., MAC addresses,
UUIDs).
● Global Uniqueness: Every entity must have a unique name across the system.
● Location Independence: The name does not reveal the physical or network location.
● Direct Matching: Name resolution is usually done by a direct table lookup or hashing.
Advantages:
● Simple to generate and use.
● Good for systems where the number of entities is small or static.
Disadvantages:
● No grouping or hierarchical management.
● Searching is inefficient if exact name is not known.
Example:
● MAC Address: Every network card has a 48-bit unique identifier assigned by the
manufacturer.
● UUID: Universally Unique Identifiers used in databases.
Implementation Approaches:
● Broadcasting: Send a request to all nodes to find the entity (works only for small
LANs).
● Home-Based Approach: Store the mapping in a home node that knows the current
location of the entity.
● Distributed Hash Tables (DHTs): Map names to nodes using hashing for scalability.
Structured Naming
Definition:
In a structured naming system, names are organized into a hierarchical or structured format
where the name components define relationships or containment.
Characteristics:
● Hierarchical Organization: Names are divided into multiple levels (e.g., root,
subdomain, host).
● Delegation: Responsibility for name management can be delegated to different
authorities at different levels.
● Efficient Search: The structure allows partial name resolution step by step.
● Scalability: Can support very large name spaces.
Advantages:
● Easy to manage large numbers of entities.
● Supports location transparency and migration.
● Allows administrative control at different hierarchy levels.
●
Disadvantages:·
● Slightly more complex resolution process.
● Requires maintenance of multiple name servers.
Example:
● Domain Name System (DNS):
● www.example.com
§ .com → top-level domain
§ example → second-level domain
§ www → host name
● The resolution starts at the root name server, then proceeds to .com server, then to
example server.
Implementation:
● Name Resolution: Can be done iteratively (client queries each server) or
recursively (servers forward the request).
● Name Space Structure: May be global (shared by all users), administrative
(restricted to organizations), or local.
Attribute-Based Naming
Definition:
An attribute-based naming system identifies entities using a set of attributes (key–value
pairs) rather than a fixed, unique name. The entity is found by querying based on these
attributes.
Characteristics:
● Descriptive Identification: Entities are described by properties such as type,
owner, date, size, location, etc.
● Flexible Searching: Users can find resources without knowing their exact
name.
● Multiple Matches: Queries may return several entities matching the criteria.
● Dynamic: Works well for dynamic and heterogeneous environments.
Advantages:
● Powerful when exact identifiers are unknown.
● Enables rich and user-friendly search queries.
● Good for resource discovery in large-scale systems.
Disadvantages:
● May result in large search results.
● \Requires efficient indexing for fast search.
Example:
● Directory Services (LDAP): Searching for a printer with {location=Floor3,
type=Color} returns all color printers on the third floor.
● File Search: Searching for {type=pdf, author="John", year=2023} in a
document repository.
Implementation:
● Centralized Directory: All attributes stored in one database (e.g., LDAP
server).
● Hierarchical Directory: Attributes are distributed among servers based on
organizational structure.
● Decentralized: Peer-to-peer attribute lookup using distributed search protocols.
4.What is Clock Synchronization? Explain Lamport’s Logical Clock in
detail.
→ Clock Synchronization:
In a distributed system, each computer or process has its own local clock. These
clocks may not be perfectly synchronized, causing problems in ordering events,
coordinating tasks, or maintaining consistency. Clock synchronization is the process
of coordinating the clocks of all nodes in a distributed system so that the time
difference between any two clocks is within a certain bound.
Need for Clock Synchronization:
● To maintain a consistent ordering of events.
● To schedule tasks accurately.
● To coordinate time-sensitive operations.
● To avoid inconsistencies in logs and transactions.
Lamport’s Logical Clock:
Physical clocks in distributed systems can differ due to drift or delay. To handle this,
Lamport proposed logical clocks, which assign numbers to events to capture the
happens-before (→) relationship rather than the actual physical time.
Happens-Before Relation (→):
● If two events a and b occur in the same process and a occurs before b, then a → b.
● If a is the sending of a message by one process and b is the receipt of the message by
another process, then a → b.
● If a → b and b → c, then a → c (transitivity).
Logical Clock Rules:
1. Each process P maintains a counter LC (logical clock).
2. Increment rule: Before executing an event, P increments LC by 1.
3. Message rule: When P sends a message m, it attaches the current value of LC. On
receiving m, the receiving process Q sets LC = max(LC, timestamp of m) +
1.
Properties:
● If event a → b, then LC(a) < LC(b).
● Provides a partial ordering of events in distributed systems.
Example:
● Process P1: Event e1 → LC=1, send message to P2 with LC=2
● Process P2 receives message, updates LC = max(its LC, 2) +1 = 3
● Events are now partially ordered using logical timestamps.
Fig:- Lamports Logical Check
5.What is mutual exclusion? Explain different categories of mutual exclusion
algorithm in Distributed System.
→ Mutual exclusion: Concurrent access of processes to a shared resource or data is
executed in mutually exclusive manner.Only one process is allowed to execute the
critical section (CS) at any given time. In a distributed system, shared variables
(semaphores) or a local kernel cannot be used to implement mutual exclusion.
Message passing is the sole means for implementing distributed mutual exclusion.
Mutual exclusion algorithms are classified into two categories:
● Permission-based Approaches
A process, which wants to access a shared resource, requests the permission from one
or more coordinators
● Token-based Approaches
● Each shared resource has a token.
● Token is circulated among all the processes
● A process can access the resource if it has the token.
● With a token ring algorithm:
● Each resource is associated with a token
● The token is circulated among the processes
● The process with the token can access the resource
● How is the token circulated among processes?
● All processes form a logical ring where each process knows its next process
● One process is given the token to access the resource
● The process with the token has the right to access the resource
● If the process has finished accessing the resource OR does not want to access
the resource:
● It passes the token to the next process in the ring
There are two types of permission-based mutual exclusion algorithms
Centralized Algorithms: One process is elected as a coordinator (C) for a shared
resource
● Coordinator maintains a Queue of access requests
● Whenever a process wants to access the resource, it sends a request
● message to the coordinator to access the resource
● When the coordinator receives the request:
● If no other process is currently accessing the resource, it grants
● the permission to the process by sending a “grant” message
● If another process is accessing the resource, the coordinator
● queues the request, and does not reply to the request
● The process in action releases the exclusive access after accessing the
● resource
● Afterwards, the coordinator sends the “grant” message to the next
● process in the queue
● Coordinator coordinates entry to critical section.
● Allows only one process to enter critical section.
● Ensures no starvation as uses first come, first served policy.
Decentralized Algorithms:
6.Why mutual exclusion is more complex in distributed systems? Categorize and
compare mutual exclusion algorithms.
→ Mutual exclusion is more complex in a distributed system than in a centralized or
single-processor system due to the lack of shared memory and a global clock, along
with the challenges of communication and failure. Here's a breakdown of the reasons:
Key Reasons for Complexity in Distributed Mutual Exclusion:
● No Shared Memory
○ In centralized systems, mutual exclusion (e.g., with semaphores or locks)
relies on shared memory.
○ In distributed systems, processes are on separate machines with no shared
memory, so coordination must happen through message passing.
● No Global Clock
○ There’s no single clock to timestamp events, making it hard to determine the
order of requests.
○ Logical clocks (e.g., Lamport timestamps) are used, but they add complexity
and can't capture causality perfectly.
● Message Delays & Unreliability
○ Messages can be delayed, lost, duplicated, or arrive out of order.
○ This makes it harder to ensure that all processes have a consistent view of who
should have access to the critical section.
● Failures & Fault Tolerance
○ Processes or nodes might crash or become unreachable.
○ Ensuring mutual exclusion while tolerating failures (e.g., using timeouts or
recovery protocols) is hard.
○ Detecting whether a process is just slow or actually failed is non-trivial (e.g.,
FLP impossibility result).
● Increased Overhead
○ Distributed mutual exclusion algorithms often require many messages to
coordinate access (e.g., Ricart-Agrawala needs 2(n-1) messages).
○ More network traffic and latency are involved compared to local locking.
● Lack of Central Coordinator (in decentralized systems)
○ In a fully distributed system, there's often no central authority to control
access.
○ Coordinating access in a peer-to-peer way requires complex protocols like
token-based or quorum-based approaches.
7.What is mutual exclusion? Categorize and compare mutual exclusion algorithms.
→ Definition:
Mutual exclusion ensures that only one process at a time can execute in its critical
section (CS) in a distributed system.
Categories:
● Centralized Algorithm
a. A coordinator process controls entry into the CS.
b. Steps: request → grant → release.
c. Messages per CS entry: 3.
d. Pros: Simple, low message cost.
e. Cons: Single point of failure, bottleneck risk.
● Distributed Algorithm
f. All processes participate in granting permission.
g. Example: Ricart–Agrawala algorithm (uses timestamps).
h. Messages per CS entry: 2 × (N − 1).
i. Pros: No single point of failure.
j. Cons: High message cost, slower entry.
● Token-Based Algorithm
k. A unique token circulates; possession of the token = CS access.
l. Messages per CS entry: 1 (to pass token).
m. Pros: Low message overhead, fair access.
n. Cons: Token loss requires recovery.
8.Explain bully election algorithms.
→ Purpose:
To elect a coordinator in a distributed system; the highest-ID process becomes the
leader.
Assumptions:
● Each process has a unique ID.
● Processes know IDs of all others.
● Communication is reliable.
Steps:
● A process detecting coordinator failure sends an ELECTION message to all higher-ID
processes.
● If no one responds → it becomes coordinator and sends a COORDINATOR message
to all lower-ID processes.
● If any higher-ID responds, that process takes over the election.
● The process with the highest ID eventually wins and announces itself as coordinator.
Example:
Processes {1, 2, 3, 4, 5}, coordinator 5 fails. Process 2 notices and sends ELECTION to 3, 4,
5 → 3 and 4 reply → 4 sends to 5 (no reply) → 4 becomes coordinator.
Complexity:
● Worst-case messages: O(N²).
● Pros: Simple, ensures highest-ID process wins.
● Cons: Many messages, assumes reliable communication.
9.Define structured naming.
→ Structured naming is a method of naming in distributed systems where names are
organized in a hierarchy or structured format, making it easier to manage, locate, and
reference resources.
Instead of keeping all names in one flat list (like in flat naming), structured naming arranges
them like a tree, with each level providing more specific information.
Key Features
● Hierarchical Structure – Names are divided into multiple levels (like folders
and files in a computer).
● Uniqueness – Names are unique within their scope; combining the hierarchy
ensures global uniqueness.
● Scalability – Can handle large systems because the search for a name can be
narrowed down step-by-step.
● Flexibility – Easier to group related resources and manage them.
● Location Independence – The hierarchy can represent logical organization
rather than physical locations.
Example
Think about how files are stored in a computer:
/home/user/documents/report.txt
· /home – top-level directory
· /user – sub-directory
· /documents – another sub-directory
· report.txt – the actual file name
Here, the path represents a structured name because it follows a hierarchy.
In Distributed Systems
A distributed system might use structured naming to locate resources such as:
● · Servers
● · Printers
● · Data files
● · Applications
Example:
This tells us:
● company → Top-level domain
● department → Specific division
● project → A sub-division
● server1 → The actual resource
Advantages over Flat Naming
● Easier to locate resources
● Avoids naming conflicts
● More efficient searching
● Logical grouping of related items
10. Explain distributed hash table name resolution mechanism.
→ A Distributed Hash Table is a decentralized system that maps a key (like a name)
to a value (like an IP address or data location) using a hash function.
● How it works:
○ The system applies a hash function to the name (key).
○ The hash function outputs an identifier that corresponds to a specific node in
the distributed system.
○ The data is stored at, or retrieved from, the node whose identifier is closest to
the key’s hash value.
○ When resolving a name, the same hash function is applied, and the query is
routed to the responsible node.
● Advantages:
a. Fully decentralized, no single point of failure.
b. Scalable—adding more nodes increases storage and capacity smoothly.
c. Efficient—lookups can be done in O(log n) steps for many DHT designs.
Example:
In a peer-to-peer file-sharing system, if you want the address of “fileX,” you hash
“fileX” to get an ID and then query the DHT, which quickly routes you to the node
storing that file’s location.
11. Define name server.
→ A Name Server is a server that stores and manages mappings between names and
the resources they represent.
● Function: It responds to client queries by translating a human-readable name (like
www.example.com) into the corresponding network address (like 192.168.1.1).
● Types of Name Servers:
○ Authoritative Name Server: Stores the original mapping for a specific domain
and answers queries with definite data.
○ Caching Name Server: Stores previous query results temporarily to speed up
responses.
● Role in Distributed Systems:
Name servers work together to resolve names in hierarchical systems like DNS,
where a query may be passed between multiple servers until the final mapping is
found.
● Example:
When you type www.google.com, your request goes to a name server that translates it
to an IP address, enabling your browser to connect to Google’s server.
