CST402 — Distributed Computing

Module 1 — Complete Questions & Answers

APJ Abdul Kalam Technological University

PART A — Short Answer Questions (3 Marks Each)

Q1. What do you mean by a distributed system?

[3 Marks]
A distributed system is a collection of independent entities that cooperate to solve a problem that
cannot be individually solved.

Key characteristics:
• A collection of independent computers that do not share common memory or a common physical
clock, and communicate by message passing over a communication network.
• Each computer has its own memory and runs its own operating system.
• Appears to the users as a single coherent computer.
• A single machine crash never prevents the overall system from functioning.

Q2. What are the various features of a distributed system?

[3 Marks]
No common physical clock: Processors do not share a global clock — time synchronization is a
major challenge.
No shared memory: Communication happens only via message passing over the network.
Geographical separation: Nodes can be located at physically different locations.
Autonomy and heterogeneity: Processors are loosely coupled, may have different speeds and
different operating systems, yet cooperate by offering services or solving problems jointly.

Q3. List the characteristics / advantages of a distributed system.

[3 Marks]

Characteristics:
• Crash of a single machine never prevents the entire system from working.
• Computers communicate by message passing — no shared memory or physical clock.
• Appears as a single coherent computer to users.

Advantages / Motivation:
• Inherently distributed computations (e.g., banking, consensus among distant parties).
• Resource sharing.
• Access to geographically remote data and resources.
• Enhanced reliability — availability, integrity, and fault-tolerance.
• Increased performance/cost ratio through resource sharing.
• Scalability and modularity.

Q4. Discuss the transparency requirements of a distributed system.

 [3 Marks]
Transparency hides the implementation policies from the user:
• Access transparency — hides differences in data representation; provides uniform access
operations.
• Location transparency — makes resource locations transparent to users.
• Migration transparency — allows relocating resources without changing names.
• Relocation transparency — ability to relocate resources even while they are being accessed.
• Replication transparency — user is unaware of any replication.
• Concurrency transparency — masks concurrent use of shared resources.
• Failure transparency — system appears reliable and fault-tolerant.

Q5. Define causal precedence relation in distributed executions.

[3 Marks]
The causal precedence relation (→) is a binary relation on the set H of events in a distributed
computation. For events exi and eyj:
• exi → eyj if (i = j) and (x < y) — two events on the same process.
• exi → eyj if exi is the send event and eyj is the corresponding receive event of a message.
• Transitivity: if exi → ezk and ezk → eyj, then exi → eyj.
The causal precedence relation induces an irreflexive partial order on the events — also known as
Lamport's 'happens before' relation.

Q6. Compare logical and physical concurrency.

[3 Marks]
• Two events are logically concurrent if and only if they do not causally affect each other.
• Physical concurrency means the events occur at the same instant in physical time.
• Two events may be logically concurrent even if they do not occur at the same physical time.
• However, if processor speed and message delays were different, logically concurrent events
could coincide physically.
• Whether logically concurrent events coincide physically does not change the outcome of the
computation.
• Therefore, logically concurrent events can be assumed to have occurred at the same physical
instant without loss of generality.

PART B — Long Answer Questions (Module I)

B1. Relate a computer system to a distributed system with neat sketches.

[8 Marks]
A distributed system connects multiple processor-memory units through a shared communication
network (WAN/LAN). Each node consists of a processor (P) and memory bank (M). Nodes do not
share memory; they communicate solely by message passing.

Architectural difference:
• A centralized computer system has a single processor and memory, with tight coupling.
 • A distributed system has multiple independent processor-memory units connected via a network
— loosely coupled.

Software layering at each processor:

• Distributed Application — the user-level application.
• Distributed Software (Middleware) — drives the distributed system while providing
transparency of heterogeneity.
• Operating System — manages local resources.
• Network Protocol Stack — Application, Transport, Network, Data link layers.

Key points:
• The middleware is the distributed software that provides services like naming, communication,
synchronization, and fault-tolerance transparently to the application.
• A distributed execution is the execution of processes across the system to collaboratively
achieve a common goal.
• The layered architecture reduces complexity by separating concerns at each level.
Note: Draw Figure 1.1 (multiple P|M nodes connected via WAN/LAN cloud) and Figure 1.2 (software layer
stack) in your exam answer.

B2. Discuss about various primitives for distributed communication.

[6 Marks]
Send() and Receive() primitives are the fundamental mechanisms for message passing:
• Send(destination, buffer) — takes at least two parameters: the destination address and the
user-space buffer holding the data to be sent.
• Receive(source, buffer) — takes at least two parameters: the source address and the buffer
into which data will be received.
Two options for data transfer: buffered (system buffers the data) and unbuffered (direct transfer).

1. Synchronous primitives:
Both Send() and Receive() must handshake. Send completes only after the invoking processor
confirms the Receive has been invoked and completed. Simple to implement but prone to deadlocks
and poor performance due to frequent blocking.

2. Asynchronous primitives:
Control returns to the invoking process as soon as data is copied out of the buffer. The sender can
execute while the message is in transit — higher parallelism. Requires more complex buffer
management. Risk of buffer overflow with burst messages.

3. Blocking primitives:
• Blocking Send — waits until the message is received and acknowledged.
• Blocking Receive — waits until a message arrives before continuing.

4. Non-blocking primitives:
Control returns immediately even if the operation is not complete:
• Non-blocking Send — continues execution after sending without waiting for acknowledgment.
• Non-blocking Receive — continues regardless of whether a message has arrived.
Note: Draw timing diagrams showing Process A and Process B for synchronous vs asynchronous
communication.

B3. Explain the applications of distributed computing.

[7 Marks]
1. Mobile systems: Use wireless communication (electromagnetic waves, shared broadcast
medium). Key challenges: routing, location management, channel allocation, localization, mobility
management. Two architectures: (a) base-station (cellular) approach — geographic regions (cells)
served by a static base station; (b) ad-hoc network — no base station, all responsibility distributed
among mobile nodes.
2. Sensor networks: Processors with electro-mechanical interfaces that sense physical
parameters — temperature, velocity, pressure, humidity, chemicals. May be mobile or static;
communicate wirelessly or via wire.
3. Ubiquitous / pervasive computing: Intelligent homes and smart workplaces. Leverage
wireless communication, sensor, and actuator mechanisms. Essentially distributed systems with
tight environmental integration.
4. Peer-to-peer (P2P) computing: All interactions at a 'peer' level without hierarchy. Shift from
client-server paradigm. Networks are self-organizing. Each peer can be both a client and a server.
5. Publish-subscribe, content distribution & multimedia: Three key needs: (a) efficient
information distribution (publish), (b) mechanism for users to indicate interest (subscribe), (c)
aggregating and filtering large volumes of published information per subscription.
6. Distributed agents: Agents collect, process, and exchange information with other agents.
Challenges: coordination, mobility control, software design.
7. Distributed data mining: Data is distributed and cannot be collected in a single real-time
repository — must be mined in place across nodes.
8. Grid computing: A virtual supercomputer formed from networked machines. Idle CPU cycles
of network machines are shared. Subset of distributed computing.
9. Security in distributed systems: Challenges: confidentiality (authorized access only),
authentication (verifying identity of senders), availability (maintaining access despite malicious
actions).

B4. Explain the design issues and algorithmic challenges of a distributed system.
[8 Marks]

Design Issues (functions to address when building a distributed system):

1. Communication: Appropriate mechanisms for inter-process communication: RPC, remote
object invocation, message-oriented vs stream-oriented communication.
2. Processes: Management of processes and threads at clients/servers; code migration; software
and mobile agents.
3. Naming: Easy-to-use and robust naming schemes for names, identifiers, and addresses to
locate resources and processes transparently and scalably.
4. Synchronization: Mutual exclusion, physical clock synchronization, logical clocks, leader
election, deadlock detection, termination detection.
5. Data storage and access: Schemes for fast, scalable data storage and access across the
network. Redesigning traditional file systems for distributed settings.
6. Consistency and replication: Replication avoids bottlenecks, provides fast access, and
scalability. Managing replica consistency during updates is critical.
7. Fault tolerance: Process resilience, reliable communication, distributed commit, checkpointing,
recovery, consensus, failure detection, self-stabilization.
 8. Security: Cryptography, secure channels, access control, key management (generation and
distribution), authorization, secure group management.
9. API and transparency: Access, location, migration, relocation, replication, concurrency, and
failure transparency.
10. Scalability and modularity: Replication, caching and cache management, asynchronous
processing help achieve scalability.

Algorithmic Challenges:
1. Execution models and frameworks: Interleaving model and partial order model — widely
used for reasoning about distributed executions.
2. Distributed graph algorithms and routing: Graph algorithms form building blocks for
communication, data dissemination, object location. Algorithms must handle dynamically
changing graph characteristics.
3. Time and global state: Providing accurate physical time and logical time (relative, eliminates
overhead of physical time where unnecessary).
4. Synchronization/coordination: Problems: physical clock sync, leader election, mutual
exclusion, deadlock detection, termination detection, garbage collection.
5. Group communication and multicast: Efficient group communication with ordered message
delivery. Processes can join/leave/fail. Different processes may receive concurrent messages in
different orders — formal ordering semantics needed.
6. Monitoring distributed events and predicates: Predicates on distributed variables specify
global state conditions — used in debugging, sensing, and industrial process control.
7. Distributed program design and verification: Methodically designed, verifiably correct
programs reduce software engineering overhead.
8. Debugging distributed programs: Much harder than sequential programs due to concurrency
and non-determinism from large numbers of possible execution interleavings.
9. Data replication, consistency, and caching: Replicas must be consistent during updates.
Replica placement across the system is also a challenge.

B5. Discuss about the global state of a distributed system.

[6-7 Marks]
The global state of a distributed system is a collection of the local states of its components — the
processes and the communication channels.

Process state:
Defined by the contents of processor registers, stacks, local memory, etc. — depends on the local
context of the distributed application.

Channel state:
Given by the set of messages currently in transit in the channel. Channel state SCx,yij = { mij |
send(mij) ≤ exi AND rec(mij) is not ≤ eyj } — all messages pi sent up to event exi that pj had not yet
received up to eyj.

Event effects on state:

• An internal event changes the state of the process at which it occurs only.
• A send event changes the state of the sending process and the channel state.
• A receive event changes the state of the receiving process and the channel state.

Global state notation:

GS = { Union(LSxii), Union(SCyj,zkjk) } — union of all local process states and all channel states.

Cuts in space-time diagram:

• A cut is a zigzag line joining one arbitrary point on each process line in the space-time diagram.
• A cut divides events into PAST (to the left) and FUTURE (to the right).
• Every cut corresponds to a global state; every global state can be represented as a cut.
• A consistent cut is one where if event eyj is in the PAST of the cut, then every event exi that
causally precedes it is also in the PAST.

B6. Explain the models of communication networks.

[6 Marks]
There are three models of service provided by communication networks:

1. FIFO model:
Each channel acts as a first-in first-out message queue. Message ordering sent between two
processes is preserved. If process pi sends messages m1 then m2 to pj, then pj receives m1 before
m2.

2. Non-FIFO model:
A channel acts like a set. The sender adds messages and the receiver removes them in a random
order. No ordering guarantee is maintained.

3. Causal ordering model:

Based on Lamport's 'happens before' relation. Property (CO): For any two messages mij and mkj, if
send(mij) → send(mkj), then rec(mij) → rec(mkj).
• Causally related messages destined to the same destination are delivered in causal order.
• Causally ordered delivery implies FIFO message delivery: CO ⊂ FIFO ⊂ Non-FIFO.
• Causal ordering considerably simplifies the design of distributed algorithms as it provides built-in
synchronization.

B7. Explain in detail about the past and future cones of an event.
[6 Marks]
In the space-time diagram of a distributed computation, a cut is a zigzag line joining one arbitrary
point on each process line, dividing events into PAST and FUTURE.

Past cone of event ej:

• Event ej could have been affected only by all events ei such that ei → ej.
• All information available at ei could have been made accessible at ej.
• All such events ei belong to the PAST of ej: PAST(ej) = { ei | ei → ej }.

Future cone of event ej:

• The future of ej, Future(ej), contains all events ei that are causally affected by ej.
• Future(ej) = { ei | for all ei in H, ej → ei }.

Concurrent events:
Events that are neither in the past nor the future of ej are logically concurrent with ej. They neither
causally precede nor follow ej.

Graphical representation:
In the space-time diagram, the past and future form two cone/triangle shapes meeting at the event
point. The left cone is the past; the right cone is the future. The region outside both cones represents
concurrent events.
Note: Draw Figure 2.4 showing the two cone shapes (past triangle on left, future triangle on right) meeting at
event ej in the space-time diagram.

End of Module 1 — CST402 Distributed Computing