Department of Artificial Intelligence Data Science and Engineering

ASSIGNMENT I

ACADEMIC YEAR: 2025-2026 YEAR/ SEM: III / 05

SUBJECT CODE & NAME - CS3551 - DISTRIBUTED COMPUTING

ASSIGNMENT RUBRICS

Sl.
Criteria Marks Awarded Marks
No
1. Understanding of Concepts 20
2. Accuracy of Calculations/Analysis/PROGRAMS 20
3. Real-world Relevance/Application 20
4. Clarity of Presentation & Diagrams 20
5. Originality and Innovation 20
Total 100

NAME: J. JENIFER

[Link]

SUBMISSION DATE :

Signature of the Staff

1. Design a simple distributed file-sharing application

Problem statement and goals:

Design a distributed file-sharing application where multiple clients can upload and download files.
The system should be simple, fault-tolerant to a modest degree, and illustrate when message-passing
and when shared-memory approaches would be appropriate.

Architectural overview:

We propose a hybrid design with the following components:

- Central Index Server (optional): maintains metadata (file names, owners, chunk locations).
- Storage Nodes (peers): each node stores file chunks and serves upload/download requests.
- Clients: can upload files (chunking + replicate) and download files (retrieve chunks from peers).
- Optional Tracker/Bootstrap node to help new peers join the network.

Data flow (upload):

1. Client splits file into fixed-size chunks (e.g., 4 MB).

2. Client computes chunk hashes and creates metadata.
3. Client sends metadata to Index Server (message-passing) to register the file and receive preferred
storage nodes.
4. Client uploads chunks directly to designated Storage Nodes (message-passing via RPC/HTTP
PUT).
5. Storage Nodes acknowledge; Index Server updates chunk location map.

Data flow (download):

1. Client queries Index Server for file metadata and list of nodes holding chunks.
2. Client downloads chunks in parallel from multiple Storage Nodes (message-passing).
3. Client verifies chunk hashes and reassembles the file.

Role of message-passing vs shared memory:

Message-passing (primary):

In our distributed file-sharing system, message-passing is the dominant communication model.

Clients and storage nodes communicate using network messages (HTTP/REST, gRPC, or custom
RPC). Reasons:
- Physical separation: nodes are on different machines and often on different networks.
- Failure isolation: messages clearly represent actions and allow retry/timeouts.
- Loose coupling: message-passing supports peer-to-peer transfers without shared storage.

Shared memory (limited / conceptual):

True shared memory (memory shared across processes) is not feasible across independent machines.
However, some shared-state semantics can be emulated via distributed shared data stores (e.g., a
replicated key-value store, distributed filesystem, or an in-memory cache like Redis). Use-cases:
- Index Server's metadata can be stored in a distributed replicated database providing a shared view to
all nodes.
- Caching layers that present 'shared' content for performance.

Trade-offs:

- Message-passing is simpler and safer across networks; it enforces explicit coordination and handles
partial failures.
- Emulated shared memory (replicated state) can provide easier programming models but introduces
consistency challenges (consensus, replication lag).
- For availability and partition tolerance, prefer message-passing with eventual consistency for
metadata; for critical metadata you may require strong consistency via consensus (e.g., Raft).
2. Impact of synchronous vs asynchronous execution in a distributed banking system

Scenario and critical requirements:

A distributed banking system receives transactions (deposits, withdrawals, transfers) at multiple

branches. Account balances must be updated correctly despite concurrency, network delays, and
partial failures. Correctness and auditability are paramount; in some cases, low latency is also critical.

Synchronous execution:

Definition: The system waits for an operation to complete (and often for acknowledgments) before
proceeding.
Example pattern: Two-phase commit (2PC) for cross-branch transfers where both branches must
agree before committing.

Pros of synchronous approach:

- Strong consistency: operations can be serialized and atomic.
- Easier reasoning: when an operation returns success, it is committed globally.

Cons:
- Higher latency: waiting for responses from remote branches/databases.
- Tight coupling and blocking: a slow or failed participant stalls the whole transaction.
- Reduced availability under partitions (CAP trade-offs).

Asynchronous execution:

Definition: Operations are initiated and the system proceeds without waiting for remote
acknowledgements; eventual consistency is often used.
Example pattern: Eventual replication using asynchronous logs and conflict-resolution (CRDTs or
last-writer-wins with vector clocks).

Pros:
- Lower latency at the initiating branch; better responsiveness.
- Higher availability; system can accept transactions even when parts are partitioned.

Cons:
- Complexity in ensuring convergence and resolving conflicts.
- Possible temporary inconsistencies (e.g., balance seen at branch A may differ from global state until
sync).

Concrete examples:

1. Synchronous example (fund transfer):

- Alice in Branch A transfers $100 to Bob in Branch B. Branch A uses 2PC to ensure both the debit
and credit commit atomically. If Branch B is unreachable, the transfer is blocked or aborted —
ensuring no lost/double funds but introducing delay.

2. Asynchronous example (local deposit with background replication):

- A deposit at Branch C is applied to the local ledger and an append-only event is sent to the
replication bus. Other replicas apply the event asynchronously; transient reads at remote branches
may not immediately reflect the deposit.

Design recommendations:

- For high-value cross-branch atomic operations, prefer synchronous commit or strong consensus to
avoid inconsistencies.
- For high-throughput local operations (e.g. ATM deposits with low risk), asynchronous replication
with compensating transactions may be acceptable.
- Use hybrid models: synchronous for critical operations, asynchronous for telemetry and reporting.
- Use idempotency, vector clocks or sequence numbers, and rigorous auditing to reconcile state.

3. Design challenges in developing a ride-sharing app as a distributed system

Overview:

A ride-sharing app comprises many distributed components: mobile clients, dispatch servers,
mapping services, pricing engines, notification systems, payment gateways, and analytics. The
system must be responsive (low latency), highly available, and consistent enough to match riders with
drivers correctly.

Key design challenges:

- Real-time matching and location updates (scalability and timeliness).

- Partition tolerance and availability during network failures.
- Consistency vs latency in assigning drivers and handling cancellations.
- Geo-partitioning and dealing with hotspots (e.g., surge areas).
- Security, authentication, and payment processing across distributed services.
Communication between distributed components:

We would use a mix of communication models:

- Synchronous RPC (gRPC/HTTP) for point-to-point requests where immediate response is needed
(e.g., fare estimation, booking confirmation).
- Asynchronous messaging (Kafka, RabbitMQ) for event-driven flows: location streams, trip lifecycle
events, analytics ingestion.
- WebSockets / MQTT for real-time bidirectional channels between mobile clients and gateway
servers for live location updates and notifications.

Example flow (ride request):

1. Rider app sends a ride request to an API Gateway (synchronous REST).

2. Gateway writes a 'ride-request' event to a message bus and returns an ACK to the client.
3. Matching service consumes events, queries available drivers (in-memory geo-index), and initiates
driver notification via push service (async).
4. Driver accepts (message-passing), matching service commits assignment to persistent store and
emits 'ride-assigned' event.

Handling failures and consistency:

- Use optimistic concurrency with reservation tokens to avoid double-assigning drivers.

- Employ timeouts and fallbacks: if driver doesn't confirm within N seconds, cancel and reassign.
- Use distributed tracing and idempotent operations to allow safe retries.

4. Distributed smart home (IoT) model — interactions and global state

System components:

- Edge Devices: sensors (temperature, motion), actuators (lights, locks).

- Home Gateway / Hub: local coordinator, provides local automation and caching.
- Cloud Backend: global control logic, profile storage, remote access.
- Mobile App: user interface for control and monitoring.

Design goals:

- Low-latency local control when possible.

- Secure remote management via cloud when necessary.
- Consistent representation of global state (device statuses, schedules).
Interaction model and global state representation:

We model each device as an actor that publishes events (state updates) and accepts commands. The
global system state is a composition of device states stored in a replicated state store (cloud) and a
local cache in the gateway. Use eventual consistency between gateway and cloud but strong local
consistency for immediate automation.

Sequence example (motion-triggered light):

1. Motion sensor detects motion and sends event to Gateway.

2. Gateway applies local automation rule: send 'turn-on' command to light actuator.
3. Gateway emits event to Cloud for persistent logging and user notification.
4. Cloud updates global state and sends push notification to mobile app.

State model :

- Device State: {device_id, type, last_seen, status, version}

- Global State: aggregation of Device States with metadata and automation rules.
- Synchronization: Gateway increments version and pushes diffs; cloud merges using last-write-wins
with vector clocks for conflict detection.

5. Implementing a simulation of logical clocks (Vector Clocks)

Goal: Provide working Python code to simulate vector clocks among three nodes and determine event
ordering.
Below is an example Python implementation of vector clocks for three nodes. The code supports
internal events, sending, and receiving messages. After running a sequence of events and message
exchanges, compare the vectors to determine causal relationships.

# Vector clock simulation for three nodes

class VectorClock:
def init (self, nodes):
[Link] = nodes
self.v = {n:0 for n in nodes}

def increment(self, node):

self.v[node] += 1

def send(self, from_node, to_node):

# increment before send
[Link](from_node)
return dict(self.v)

def recv(self, to_node, msg_v):

# merge
for n in self.v:
self.v[n] = max(self.v[n], msg_v.get(n,0))
# then increment on receive
[Link](to_node)

# Example usage:
nodes = ['A','B','C']
vcA = VectorClock(nodes)
vcB = VectorClock(nodes)
vcC = VectorClock(nodes)

# A does an internal event

[Link]('A')

# A sends message to B
msg = [Link]('A','B')
[Link]('B', msg)

# B sends to C
msg2 = [Link]('B','C')
[Link]('C', msg2)

print("A:", vcA.v)
print("B:", vcB.v)
print("C:", vcC.v)

Determining event ordering:

Given vectors v and w, v -> w (v happened before w) if for every component i: v[i] <= w[i] and at
least one component strictly less. If neither v <= w nor w <= v, events are concurrent.

6. Causal ordering of messages in a real-time multiplayer game server

Problem:

Multiplayer games rely on ordering of events (player moves, actions). Causal ordering ensures
players see events in an order preserving cause-effect relationships (e.g., a shot fired before hit
confirmation).

Effects on consistency:

- If causal ordering is not preserved, players might see contradictory states (e.g., a character appears
to get hit before the shot is fired).
- In fast-paced games, strict causal ordering increases latency; many games relax ordering for
responsiveness, using client-side prediction and reconciliation.

Improvements using logical clocks:

- Use vector clocks or hybrid logical clocks to tag events with causal metadata.
- Servers can use causal delivery buffers: hold events until their dependencies (as per vector clocks)
arrive or timeout.
- For scalability, use approximate causal ordering with partial vector clocks (sharded by region) or
using logical timestamps plus dependency lists.

7. Evaluation of NTP in synchronizing distributed servers for stock market trading platforms

Context and importance:

Trading platforms require precise and accurate time synchronization for ordering trades, regulatory
compliance, and forensic auditing. Even microsecond-level differences can matter for high-frequency
trading (HFT).
How NTP works (brief):

NTP (Network Time Protocol) synchronizes clocks over packet-switched networks by exchanging
timestamps and estimating network delay and offset. NTP can typically achieve millisecond-level
accuracy over the public internet and microsecond to sub-microsecond on well-configured dedicated
networks with hardware timestamping.

Effectiveness and limitations:

- NTP over commodity networks: millisecond accuracy; insufficient for HFT where sub-microsecond
is desired.
- NTP with hardware timestamping (PTP or NTP with NIC support): better accuracy; still depends on
network topology and asymmetry.
- NTP is susceptible to network asymmetry, variable delay, and malicious time sources; security
extensions (NTS) help.

Recommended approach for trading systems:

- Use dedicated time-distribution infrastructure (GPS / PTP Grandmaster clocks) with hardware
timestamping on NICs.
- Use NTP as a fallback and for general servers where microsecond accuracy is not required.
- Implement strict monitoring and drift detection, and use secure/authenticated time sources.

8. Snapshot algorithm for detecting the global state in a distributed video surveillance system
(FIFO channels)

Problem statement:

We need to capture a consistent global state across distributed camera nodes and storage servers.
Channels between nodes are FIFO (messages arrive in order). The snapshot should allow forensic
reconstruction of what frames and events were present at the snapshot time.

Chandy-Lamport snapshot algorithm (adapted):

Assumptions: FIFO reliable channels; nodes can record local state and channel messages.
Algorithm steps:
1. Initiator (coordinator node) records its local state and sends 'marker' messages on all outgoing
channels.
2. Upon receiving a marker for the first time, a node records its local state, records incoming channel
as empty up to that marker, and forwards markers on its outgoing channels.
3. For subsequent markers on a channel, the node records the sequence of messages that arrived on
that channel after recording local state and before receiving the marker and includes them in the
snapshot for that channel.
4. When all nodes have received markers on all incoming channels, the global snapshot is assembled
at the coordinator.

Handling FIFO channels:

FIFO ensures markers reliably delimit the 'before' and 'after' messages for each channel. Cameras can
tag frame/event messages with sequence numbers so recorded in-transit messages are reproducible.

Adaptations for video surveillance:

- Limit snapshot size by recording only metadata (timestamps, frame IDs) rather than full frames.
- Use consistent snapshot triggers (time-of-day, security event) and concurrency controls to avoid
overwhelming storage.
- Ensure snapshot operation is lightweight—avoid pausing recording.

9. Simulation of Lamport’s distributed mutual exclusion algorithm (three instances)

Simulate Lamport's bakery/timestamp algorithm where three distributed database instances try to
append to a shared log file. We'll provide a Python simulation.

Python simulation (explanation + code):

The code above simulates Lamport's algorithm: nodes issue REQUEST with logical timestamps,
broadcast them, wait for replies, and enter critical section when their request is earliest. The Network
object delivers messages (synchronously here for simplicity) and maintains the set of outstanding
requests.

import heapq
import threading
import time

class Node:
def init (self, name, network):
[Link] = name
[Link] = 0
self.request_queue = []
[Link] = set()
[Link] = network
[Link] = [Link]()
 def timestamp(self):
with [Link]:
[Link] += 1
return ([Link], [Link])

def request_cs(self):
ts = [Link]()
# broadcast request
[Link](("REQUEST", [Link], ts))
[Link] = set()
# wait until replies from all others and our request is earliest
while True:
[Link](0.01)
with [Link]:
if len([Link]) == [Link] - 1:
# check if our request is smallest
smallest = min([Link].global_requests())
if smallest == (ts, [Link]):
break

def receive(self, msg):

typ, sender, ts = msg
with [Link]:
[Link] = max([Link], ts[0]) + 1
if typ == "REQUEST":
[Link].enqueue_request(ts, sender)
# send reply
[Link](sender, ("REPLY", [Link], ([Link], [Link])))
elif typ == "REPLY":
[Link](sender)
elif typ == "RELEASE":
[Link].remove_request(ts, sender)

class Network:
def init (self, nodes):
[Link] = {[Link]:n for n in nodes}
[Link] = [] # list of (ts, name)
[Link] = len(nodes)
 def broadcast(self, msg):
typ, sender, ts = msg
self.enqueue_request(ts, sender)
for n in [Link]():
if [Link] != sender:
[Link](msg)

def send(self, to, msg):

# direct deliver
[Link][to].receive(msg)

def enqueue_request(self, ts, sender):

[Link]((ts, sender))

def remove_request(self, ts, sender):

[Link] = [r for r in [Link] if not (r[0]==ts and r[1]==sender)]

def global_requests(self):
return sorted([Link])

# Example simulation
n1 = Node("A", None)
n2 = Node("B", None)
n3 = Node("C", None)
net = Network([n1,n2,n3])
[Link] = net
[Link] = net
[Link] = net

# Simulate A requesting CS
n1.request_cs()
print("A entered CS")
[Link](("RELEASE","A",([Link],"A")))

10. Token-based vs Permission-based mutual exclusion algorithms

Definitions:

- Token-based: A unique token circulates; the node holding the token can enter the critical section
(e.g., Suzuki-Kasami algorithm).
- Permission-based (permission/request): Nodes request permission from all or a majority and wait
for replies (e.g., Ricart-Agrawala, Lamport's algorithm uses timestamps).
Test case designs in a cloud storage system:

We propose several test cases to compare algorithms under concurrent access:

1. Low contention, low latency: Many nodes occasionally request CS.
2. High contention, low latency: Many nodes frequently request CS.
3. High latency network: artificially delay messages to simulate WAN.
4. Network partitions and temporary failures.

Comparison and recommendation under high network latency:

- Token-based algorithms typically have lower message overhead when contention is high because
only the token needs to be passed. However, latency to obtain the token may be large if the token is
far.
- Permission-based algorithms require O(N) messages per request (request + replies) which can be
costly in high-latency networks.
Recommendation: Under high network latency, token-based approaches often perform better because
they avoid waiting for many replies; however, they are vulnerable to token loss and single-token
bottleneck. A hybrid (multiple tokens per partition or lease-based tokens) may be best for cloud
storage across WANs.

Conclusion and practical considerations:

Choose token-based for high-latency WAN with high contention (and add recovery for token loss).
Choose permission-based where fault-tolerance and simpler recovery from failures are required and
latency is moderate.

Appendix: Code snippets and references

Included code snippets:

- Vector clock simulation (Question 5)
- Simplified Lamport mutual exclusion (Question 9)

Further reading suggestions:

- Chandy & Lamport (1985) — distributed snapshots
- Lamport (1978) — time, clocks, and the ordering of events
- Ricart & Agrawal (1981) — mutual exclusion
- Raft and Paxos papers for consensus