Date: January 19, 2025

Topic: Distributed Systems

Recall

Distributed systems properties:

Communication through LAN/WAN
No physical memory between nodes
$t_m^{a-c}>>t_e^{a-b}$

In a distributed system across nodes, we believe that the processes in a node are totally ordered, and sending across nodes is done before receiving on another node.

Notes

Distributed Systems Definition

Communication through LAN/WAN

Collection of nodes connected by LAN/WAN

No Physical Memory

No physical memory is shared between DS nodes
Only way to communicate is through sending messages on the network

Message Communication >> Event Computation

Event Computation Time $t_e$: Time taken on a single node to do meaningful processing
Message Communication Time $t_m$: Time taken to communicate with other nodes in system
Message communication takes significantly longer than event computation
- Should design algorithms that take much longer to compute than communication time
Even clusters are considered distributed systems as CPUs have become very fast

Beliefs of a Distributed System

Within a Process: Processes are sequential and the events are totally ordered ($h\rightarrow i, f\rightarrow g$, etc)
Across Processes: Sending is done before receiving ( $a \rightarrow b, e \rightarrow f$, etc

“Happened Before” can be from 2 possibilities, either from the same process sequentially, or a sender going before a receiver.

“Happened Before” Relation

If $a$ happened before $b$:

Same Process: In a sequential process, $a$ happened before $b$
Different Process: Communication event connecting $a$ (sender) and $b$ (receiver)

“Happened Before” is also transitive.

Transitivity of “Happened Before”

If $a\rightarrow b$, then $b\rightarrow c$, $a$ and $c$ must follow this relationship $a\rightarrow c$.

Happened Before Quiz

What is the relationship between $a$ and $b$?

$a \rightarrow b$
$b \rightarrow a$
Neither

<aside> 📌 SUMMARY: Distributed systems are connected through WAN/LAN, have no shared memory and the computation time within a node is much shorter than the communication time between nodes. Between events, they can have “happened before” relationships, where for e.g., Event 1 is a sender on Node A and Event 2 is a receiver on Node B. This guarantees that Event 1 happens before Event 2. However concurrent events can also exist for which there are no relations.

</aside>