Distributed Systems – Assignment 3 Answers
Part A: Conceptual Understanding
1. Define a Distributed System
A distributed system is a collection of independent computers that appear to users as a single
coherent system. The computers communicate with each other through a network and coordinate
their actions by passing messages. Key characteristics include resource sharing, scalability,
concurrency, and fault tolerance.
2. Why the Internet is considered a distributed system
The Internet connects millions of computers across the world that work together to provide services
such as web browsing, email, and cloud storage. These systems communicate using standard
protocols. For example, when a user accesses a website, the request travels through multiple
servers and networks before reaching the destination server and returning a response.
3. Transparency in distributed systems
Transparency means hiding the complexity of the distributed system from users so that it appears
as a single system.
Access transparency: Users access resources in the same way regardless of where they are
located.
Location transparency: Users do not need to know the physical location of resources.
Replication transparency: Multiple copies of resources exist but appear as a single resource.
Failure transparency: The system continues functioning even if some components fail.
4. Openness in Internet systems
Openness refers to the ability of a system to interoperate with other systems using publicly
available standards. It allows different hardware and software platforms to communicate and work
together easily.
5. Role of RFCs
RFC (Request for Comments) documents describe standards, protocols, and technical guidelines
used in the Internet. They help maintain consistency and interoperability between systems
developed by different organizations.
6. Examples of RFC-based protocols
Examples include HTTP (HyperText Transfer Protocol), TCP (Transmission Control Protocol), and
IP (Internet Protocol).
Part B: Analytical Questions
1. Model of Distributed Computation
In distributed computation, multiple processes run on different machines and communicate by
exchanging messages through a network. Each process performs computation locally and sends
messages to coordinate with others.
2. Comparison of Network Models
3. Anonymous Networks
Anonymous networks are networks where nodes do not have unique identifiers. A major challenge
in designing algorithms for such networks is symmetry breaking, because processes cannot easily
distinguish themselves from others.
Part C: Concurrent Algorithms and Complexity
1. Concurrent Algorithms
Concurrent algorithms allow multiple processes to execute simultaneously while coordinating their
operations through communication mechanisms.
2. Message Passing
Message passing is a communication model where processes exchange information by sending
and receiving messages over the network instead of sharing memory.
3. Message Complexity
Message complexity refers to the total number of messages exchanged between processes during
the execution of a distributed algorithm.
4. Message Complexity Derivation
If there are n nodes and each node sends a message to every other node exactly once, then each
node sends (n-1) messages. Therefore the total messages are n(n-1). In Big-O notation the
complexity is O(n²).
Part D: Application-Based Question
1–2. Ring Communication
In a ring topology with 5 processes, each process sends one message to its neighbor. Therefore
the total number of messages transmitted is 5. If all processes send messages at the same time
with a global clock assumption, the execution can be considered synchronous.
3. Real-world Example
A common real-world example is token ring networks where a token circulates between devices to
control access to the network.
Feature Synchronous Network Asynchronous Network
Time assumptions Known upper bound on processing and communication time No fixed assumptions on timing
Message delivery Messages delivered within known time Delivery time unpredictable
Algorithm difficulty Relatively easier More complex
Ring Topology Diagram (5 Processes)
P1
P5 P2
P4 P3