1.
Crown
Definition:
A crown is a pattern formed by a group of events (usually 4 or more) that are pairwise
concurrent (not causally related to each other), but when drawn in a space-time diagram,
they form a cycle-like structure that cannot be totally ordered without breaking
concurrency.
Diagram Example:
markdown
CopyEdit
r1 r2
\ /
\ /
m2 m1
/ \
/ \
s2 s1
Here:
• s1 → m1 → r1
• s2 → m2 → r2
• Arrows cross, forming a loop (or crown)
Key Points:
• Events are concurrent (they can happen in any order).
• But due to interleaving, a cyclic dependency is created.
• Such patterns cannot be linearly ordered in a valid way without breaking causality or
concurrency.
2. Linear Extension
Definition:
A linear extension is a total ordering of events that respects the causal order (i.e., every
send event must come before its corresponding receive).
Two Types:
Type Explanation Example
Non- Keeps concurrent events next to each other; respects s1, s2, m1, m2,
Separated causality and concurrency r1, r2
Artificially places concurrent events one after another; s2, m2, r2, s1,
Separated
breaks concurrency (but not causality) m1, r1
Tip:
If two events are concurrent, they can appear in any order. But if one causally depends on
another, it must come later in the list.
3. Causal Order (CO)
Definition:
In causal order, if one event (A) causally affects another event (B), then all processes must
receive A before B.
This is based on the "happened-before" relation (→) by Lamport.
Example:
• P1: sends m1 ("Start Voting")
• P2: after receiving m1 → sends m2 ("I vote Yes")
All processes must receive:
• m1 before m2
Because m2 depends on m1
Diagram:
rust
CopyEdit
P1: ---- m1 ---------->
P2: [receive m1] ---> m2 ------>
→ m1 must be delivered before m2
4. Total Order
Definition:
In total order delivery, all processes must receive all messages in the exact same global
order, even if the messages are unrelated or concurrent.
Example:
• P1 sends m1
• P2 sends m2
All processes receive:
• m1 then m2
or
• m2 then m1
But same for everyone.
Diagram:
sql
CopyEdit
P1: ---- m1 ---->
P2: ---- m2 ---->
Global order: m1 → m2 for all (or) m2 → m1
5. Group Communication
Definition:
Group communication means sending messages to one or more processes at once, instead
of sending them one-by-one.
Types:
Type Description Example
Unicast Message to one process Personal WhatsApp chat
Multicast Message to a group of members WhatsApp group chat
Broadcast Message to all processes Posting a story/status
Diagram:
pgsql
CopyEdit
P1
/| \
P2 P3 P4
→ P1 sends message to all = Broadcast
6. Asynchronous Execution with Synchronous Communication
Definition:
In this case:
• Processes run independently (asynchronous execution)
• But communication happens synchronously (i.e., send and receive must happen
together)
Problem:
If one process is ready to send but the receiver is not ready, the sender gets blocked.
Diagram:
pgsql
CopyEdit
Time →
P1: |---- send(x) ---- waiting ----|
P2: |--- receive(x) ---|
→ P1 is blocked until P2 is ready
Real-Life Example:
Like a phone call — it only works when both people pick up at the same time. If one is not
ready, it doesn’t connect.
7. Synchronous Program on Asynchronous System
Definition:
A program written assuming everything happens in order (synchronously), but it's running
on a real system where delays can occur (asynchronous).
Problem:
• Messages can get delayed
• Results may be inconsistent
• Needs synchronization techniques like:
o Acknowledgment messages
o Delays/timers
o Vector clocks
Diagram:
css
CopyEdit
P1: send(x) ---------------->
Delay
P2: receive(x)
The programmer thought both actions would happen instantly, but in real asynchronous
systems, they don’t.
Final Recap Table (Quick Revision):
Concept Key Idea
Crown Cyclic concurrent pattern
Linear Extension Total order of events
Causal Order Cause before effect
Total Order Same message order for all
Group Communication Send message to one/many/all
Async Exec with Sync Comm System runs freely but message needs sync
Sync Program on Async System Code assumes sync, but real system has delay