1.1 Key Characteristics of Key-Value Stores

• Data Structure: Maps unique keys to values, similar to dictionaries or hash tables, but on a distributed scale.
• Scalability: Employ distributed systems to handle vast data volumes by spreading data across multiple servers or clusters.
• Flexibility: Allow storage of unstructured or semi-structured data without requiring predefined schemas.

1.2 Advantages Over Relational Databases

Relational databases (RDBMS) like MySQL traditionally store data in structured tables with fixed schemas. However, the evolving needs of applications such as Twitter and Amazon have led to certain challenges:

• Handling Unstructured Data: Many modern applications generate large amounts of unstructured data (e.g., user tweets or shopping cart details) that don’t fit into rigid schemas.
• Write-Heavy Workloads: Modern applications, especially real-time systems, often involve high write frequencies. Key-value stores are optimized for such workloads.
• Performance Needs: Key-value stores support fast operations through techniques like distributed hash tables and caching.

1.3 Key Applications and Use Cases

• Social Media: Storing tweets with tweet IDs as keys and tweet content as values (e.g., Twitter).
• E-commerce: Managing product inventories with item numbers as keys and details as values (e.g., Amazon).
• Video Streaming: Tracking user progress in videos using key-value pairs (e.g., Netflix).

1.4 NoSQL vs. RDBMS: A Paradigm Shift

Key-value stores have emerged due to the CAP theorem, which highlights trade-offs between consistency, availability, and partition tolerance:

• Eventual Consistency: Systems like Cassandra prioritize availability and partition tolerance over immediate consistency.
• Scaling Out: Utilize commodity hardware to add capacity incrementally, unlike traditional "scale-up" approaches.
• BASE Properties: Key-value stores provide Basically Available, Soft state, and Eventual consistency instead of the rigid ACID guarantees of RDBMS.

1.5 Conclusion

Key-value/NoSQL systems address the limitations of traditional databases by offering scalable, flexible, and high-performance solutions for modern, dynamic workloads. They are essential for powering the data-intensive applications of the internet age.

2.1 Log-Structured Storage Mechanism

• Write-Back Caching: Writes are initially stored in memory (in a structure called a memtable) instead of being written directly to disk. This minimizes disk I/O during the write path.
• Commit Logs: Before updating the memtable, Cassandra appends the write operation to a commit log on disk. This ensures durability by allowing recovery in case of failures.
• Flushing to Disk: When the memtable fills up or becomes old, it is flushed to disk as an SSTable (Sorted String Table). SSTables are immutable and store data in a sorted format for efficient lookups.

2.2 Write Path Details

The write path in Cassandra ensures speed and fault tolerance:

1. The client sends the write to a coordinator node.
2. The coordinator determines the replicas for the data using a partitioner (e.g., hash-based partitioning).
3. The write is logged in the commit log for durability.
4. The data is stored in the memtable for fast, in-memory access.
5. When the memtable is full, it is flushed to disk as an SSTable.
6. Indexes and Bloom filters are maintained for efficient read operations from disk.

2.3 Hinted Handoff for Availability

• Temporary Storage: If a replica is down, the coordinator temporarily stores the write as a "hint" and forwards it to the replica when it comes back online.
• Ensures Liveness: This mechanism ensures that writes succeed even in the presence of temporary node failures.

2.4 Optimizations for Disk Access

• SSTables: Immutable SSTables are stored on disk, eliminating the need for locks and enabling efficient compaction of updates.
• Bloom Filters: Used to minimize disk seeks by quickly determining whether a key exists in a particular SSTable.

2.5 Distributed Nature and Tunable Consistency

• Replication: Writes are distributed across multiple replicas, ensuring durability and fault tolerance.
• Consistency Levels: Clients can specify consistency levels (e.g., ONE, QUORUM, ALL), balancing speed and consistency according to application needs.

2.6 Conclusion

By using in-memory caching, log-structured storage, and distributed replication, Cassandra achieves high write throughput. These mechanisms ensure durability, fault tolerance, and low-latency performance, making Cassandra suitable for write-intensive applications.

3.1 Replication for Fault Tolerance

• Replication Factor: Data is replicated across multiple nodes based on a configurable replication factor. This ensures data redundancy and availability during node failures.
• Replication Strategies:
  • SimpleStrategy: Replicates data in a single data center.
  • NetworkTopologyStrategy: Designed for multi-data-center deployments, it replicates data intelligently across racks and regions to ensure fault tolerance.

3.2 Hinted Handoff

• Temporary Storage: If a replica is unavailable, the coordinator temporarily stores the write as a "hint."
• Recovery: Once the replica comes back online, the coordinator forwards the hinted write to ensure data consistency.
• Benefits: Prevents write failures during temporary outages and reduces the need for complex recovery processes.

3.3 Tunable Consistency Levels

Clients can choose a consistency level for each operation, enabling a trade-off between consistency and availability:

• ANY: Ensures availability by allowing writes to any node, even if no replicas are available.
• ONE: Requires acknowledgment from one replica.
• QUORUM: Requires a majority of replicas to acknowledge the operation.
• ALL: Ensures strong consistency but requires all replicas to acknowledge.

3.4 Read Repair

• Consistency Repair: During reads, if replicas return inconsistent data, Cassandra initiates a read repair to synchronize the replicas.
• Background Repair: Ensures eventual consistency by updating replicas in the background.

3.5 Anti-Entropy Repair

• Merkle Trees: Used to compare data across replicas and identify inconsistencies.
• Repair Process: Synchronizes inconsistent replicas using efficient data transfer.

3.6 Gossip Protocol for Node Discovery

• Cluster Membership: Nodes share information about other nodes' status (e.g., up, down, or joining) using a gossip-based protocol.
• Failure Detection: Periodic heartbeats and suspicion scores help detect node failures efficiently.

3.7 Hinted Reads and Repairs

• Downtime Recovery: Cassandra uses hints and repairs to address stale data and ensure replicas converge over time.
• Consistency Enforcement: Stronger consistency levels and quorum reads reduce the risk of stale reads.

3.8 Conclusion

Cassandra's robust mechanisms for replication, hinted handoff, tunable consistency, and repair processes ensure high availability and fault tolerance. Its distributed architecture minimizes downtime and allows seamless operation in failure scenarios, making it a reliable choice for modern applications.

4.1 Key Components of the CAP Theorem

• Consistency (C): Every read receives the most recent write or an error. This ensures all nodes in the system return the same data at any given time.
• Availability (A): Every request (read or write) receives a response, even if some nodes are unavailable. This emphasizes the system's readiness to respond at all times.
• Partition Tolerance (P): The system continues to function despite network partitions, where some nodes cannot communicate with others due to a failure or disconnection.

4.2 Implications of the CAP Theorem

The CAP theorem states that in the presence of a network partition, a distributed system must choose between:

• Consistency: Ensure all nodes return the latest data, even if some nodes are unreachable, potentially sacrificing availability.
• Availability: Allow operations to proceed, potentially sacrificing consistency by returning stale or incomplete data.

Since partitions are inevitable in distributed systems, the CAP theorem effectively reduces the choice to a trade-off between consistency and availability.

4.3 System Classifications Based on CAP

Distributed systems are designed with different CAP trade-offs:

• CP Systems: Prioritize Consistency and Partition Tolerance. Availability may be sacrificed during partitions (e.g., HBase, Spanner).
• AP Systems: Prioritize Availability and Partition Tolerance. Consistency may be relaxed (e.g., Cassandra, DynamoDB).
• CA Systems: Prioritize Consistency and Availability but cannot handle partitions. Typically, these systems operate in single-node or tightly-coupled environments.

4.4 Practical Observations

• Eventual Consistency: Many AP systems use eventual consistency to ensure replicas converge over time, balancing availability with delayed consistency.
• Application-Specific Needs: Different applications require different trade-offs. Financial systems often prioritize consistency (CP), while social media platforms may prioritize availability (AP).

4.5 Conclusion

The CAP theorem provides a framework for understanding trade-offs in distributed systems. By clarifying the limitations and possibilities, it helps designers make informed choices based on their application requirements.

5.1 Key Characteristics

• Convergence: Over time, all replicas in the system will become consistent, assuming no new updates occur.
• Stale Reads: During the convergence process, some replicas may return outdated or inconsistent data.
• Asynchronous Propagation: Updates are propagated asynchronously across replicas, enabling the system to handle high write and read loads.

5.2 How It Works

1. An update is applied to one or more replicas.
2. The update is propagated to other replicas over time through background synchronization mechanisms.
3. Once all replicas have received the update, they reach a consistent state.

5.3 Advantages

• High Availability: The system remains available for read and write operations, even during network partitions or node failures.
• Scalability: Supports distributed architectures with large numbers of nodes by reducing synchronization overhead.
• Performance: Allows faster writes by avoiding immediate synchronization across replicas.

5.4 Trade-Offs

• Temporary Inconsistency: Data may appear inconsistent during the propagation process.
• Application Complexity: Applications need to handle the possibility of stale or conflicting data during the convergence period.
• Conflict Resolution: The system or application must implement strategies (e.g., "last write wins") to resolve conflicts arising from concurrent updates.

5.5 Use Cases

• Social Media: Systems like Twitter or Facebook prioritize availability and responsiveness, tolerating temporary inconsistencies.
• Content Delivery Networks: Distributed caching systems ensure updates propagate across nodes over time while serving content to users.
• E-commerce: Inventory systems allow updates to propagate eventually to handle high traffic scenarios.

5.6 Conclusion

Eventual consistency is a practical choice for distributed systems where high availability and scalability are more critical than immediate consistency. It is especially useful for systems operating under the constraints of the CAP theorem.

6.1 Key Concepts

• Majority Agreement: A quorum typically requires a majority of replicas (more than 50%) to participate in or acknowledge an operation.
• Intersection Property: Any two quorums for the same operation must overlap, ensuring at least one replica shares the most recent update.
• Read/Write Quorums:
  • Read Quorum (R): The minimum number of replicas required to acknowledge a read request.
  • Write Quorum (W): The minimum number of replicas required to acknowledge a write request.
  • Total Replicas (N): The total number of replicas in the system.

6.2 Quorum Formula

For consistency, the following condition must hold:

$$R + W > N$$

This ensures that at least one replica involved in a read operation overlaps with those involved in a write operation, preserving the latest written data.

6.3 Benefits

• Consistency: Quorums help ensure that a sufficient number of replicas agree on data before it is considered valid.
• Fault Tolerance: By involving multiple replicas, the system remains resilient to individual node failures.
• Flexibility: Quorums allow tunable consistency, enabling trade-offs between read and write performance.

6.4 Use Cases

• Distributed Databases: Systems like Cassandra and DynamoDB use quorum-based mechanisms to maintain consistency across replicas.
• Consensus Protocols: Algorithms like Paxos and Raft rely on quorums to achieve agreement in distributed environments.
• Cloud Storage: Systems like Amazon S3 use quorum-based replication to ensure durability and consistency.

6.5 Conclusion

A quorum is a fundamental concept in distributed systems that enables consistency and fault tolerance. By requiring overlapping subsets of nodes for operations, quorums ensure that the most recent data is preserved across replicas.

7.1 Consistency Level Types

• ANY: Ensures the highest availability by allowing the write to succeed as long as at least one replica (including hinted handoff) acknowledges the operation. No guarantee that the data has been written to the required replicas.
• ONE: The operation succeeds when at least one replica responds. Provides fast reads and writes but risks returning stale data during network partitions.
• TWO: Requires acknowledgment from at least two replicas, offering a moderate level of consistency.
• THREE: Requires acknowledgment from at least three replicas, enhancing consistency compared to ONE and TWO.
• QUORUM: Ensures that the majority of replicas (\(\lceil \frac{N}{2} + 1 \rceil\)) acknowledge the operation. Provides strong consistency while balancing availability.
• LOCAL_QUORUM: Similar to QUORUM but restricted to replicas within the local data center. Optimized for multi-data-center setups to reduce inter-region latency.
• EACH_QUORUM: Ensures a QUORUM in each data center, providing strong consistency across all data centers.
• ALL: Requires acknowledgment from all replicas. Provides the strongest consistency but at the cost of high latency and reduced availability during failures.

7.2 Read and Write Consistency

Consistency levels apply to both reads and writes:

• Write Consistency: Specifies how many replicas must acknowledge a write for it to be considered successful.
• Read Consistency: Specifies how many replicas must respond with the latest data for a read to be considered successful.

When the sum of read (\(R\)) and write (\(W\)) consistency levels is greater than the total number of replicas (\(N\)) (\(R + W > N\)), strong consistency is ensured.

7.3 Practical Use Cases

• ANY: Use for applications prioritizing availability over immediate consistency, such as logging systems.
• QUORUM: Use for applications requiring a balance between consistency and performance, such as e-commerce systems.
• LOCAL_QUORUM: Ideal for multi-region applications where low-latency reads and writes within a region are essential.
• ALL: Use sparingly for critical data requiring the highest consistency, such as financial transactions.

7.4 Conclusion

Cassandra's tunable consistency levels offer flexibility to adapt to various application needs. By allowing developers to choose the desired level of consistency, Cassandra balances trade-offs between consistency, availability, and latency effectively.

8.1 Purpose of Snitches

• Data Locality: Snitches enable Cassandra to route read and write requests to replicas closest to the client to minimize latency.
• Fault Tolerance: By understanding the topology, snitches prevent data from being replicated across nodes in the same rack, avoiding single points of failure.
• Replication Strategies: Snitches provide the information necessary for replication strategies like NetworkTopologyStrategy.

8.2 Types of Snitches

• SimpleSnitch:
  • Does not consider topology information.
  • Primarily used for single-node clusters or non-production environments.
• RackInferringSnitch:
  • Infers rack and data center information based on the second and third octets of the IP address.
  • Useful when IP addresses are allocated in a way that reflects the network topology.
• GossipingPropertyFileSnitch:
  • Uses a property file (`cassandra-rackdc.properties`) to configure data center and rack information.
  • Shares topology information via gossip, dynamically updating the cluster.
  • Recommended for production environments, especially multi-data-center setups.
• EC2Snitch:
  • Designed for Amazon EC2 environments.
  • Uses EC2 regions as data centers and availability zones as racks.
  • Automatically detects the topology from the EC2 instance metadata.
• EC2MultiRegionSnitch:
  • Similar to EC2Snitch but optimized for multi-region clusters in EC2.
  • Ensures inter-region replication and efficient data access.
• Custom Snitches:
  • Allows users to define their own snitch logic for specialized environments.

8.3 How Snitches Work

1. The snitch determines the data center and rack for each node in the cluster.
2. Replication strategies use this information to place replicas on nodes across different racks and data centers.
3. During reads, the snitch helps choose the closest replica based on topology and latency.
4. Snitches work with dynamic replication strategies like `NetworkTopologyStrategy` to optimize fault tolerance and reduce latency.

8.4 Choosing the Right Snitch

• SimpleSnitch: Best for testing and small-scale clusters.
• GossipingPropertyFileSnitch: Ideal for most production environments, offering flexibility and adaptability.
• EC2Snitch: Recommended for single-region EC2 deployments.
• EC2MultiRegionSnitch: Use for multi-region deployments in EC2.
• Custom Snitch: Use when specialized network configurations or topologies are required.

8.5 Conclusion

Snitches play a critical role in Cassandra's architecture by enabling efficient replication, fault tolerance, and latency optimization. By selecting the appropriate snitch based on the deployment environment, administrators can ensure optimal cluster performance.

9.1 Characteristics of Asynchronous Systems

• Independent Clocks: Each node maintains its own local clock, which may drift from other clocks due to hardware and environmental differences.
• Unbounded Communication Delays: Messages between nodes may take unpredictable amounts of time to arrive, leading to inconsistencies in timestamp-based ordering.
• Unpredictable Processing Times: Nodes process events and messages at varying speeds, making synchronization unreliable.

9.2 Challenges in Synchronization

• Clock Skew: The difference in time values between clocks at two nodes. Over time, this skew can grow due to clock drift.
• Clock Drift: The relative difference in clock speeds, caused by hardware imperfections, leads to gradual divergence in clock values.
• Network Variability: Latencies in message delivery vary due to network congestion, routing differences, and hardware variability.
• No Global Time: Asynchronous systems lack a single, universally accurate clock, making it impossible to rely on a global time standard.
• Partial Order of Events: Without synchronized clocks, determining the absolute sequence of events across nodes is complex.

9.3 Key Problems in Synchronization

Asynchronous systems encounter the following core problems:

• Inaccuracy: A node's local time is often out of sync with real-time or other nodes' clocks.
• Non-Determinism: Message delays and variable processing times lead to inconsistent time interpretations.
• Infeasibility of Perfect Synchronization: Due to unbounded delays, achieving perfect synchronization is theoretically impossible.

9.4 Mitigation Strategies

• Logical Time: Use logical clocks, such as Lamport timestamps or vector clocks, to order events based on causality rather than absolute time.
• Clock Synchronization Protocols: Algorithms like Network Time Protocol (NTP) or Cristian's Algorithm attempt to synchronize clocks to an external time source, though with bounded error.
• Eventual Consistency: Systems often rely on eventual synchronization, ensuring that clocks align within acceptable bounds over time.

9.5 Conclusion

Time synchronization in asynchronous systems is inherently challenging due to the absence of shared clocks, unpredictable communication delays, and clock drift. While perfect synchronization is unattainable, practical approaches like logical clocks and synchronization protocols help mitigate the impact of these challenges.

10.1 Key Techniques to Reduce Error

• Measure Round-Trip Time (RTT):
  • Compute the RTT for a message exchange between the two machines.
  • Estimate one-way delay as half the RTT, assuming symmetric delays.
  • Use this to adjust the synchronized time more accurately.
• Use Multiple Synchronization Samples:
  • Take several measurements of RTT to account for variability in network delays.
  • Average the results to reduce the impact of outliers and transient congestion.
• Filter Noise in Network Delays:
  • Discard RTT samples significantly higher than the median to eliminate outliers caused by network congestion.
  • Use statistical techniques like median or weighted averages for better delay estimates.
• Estimate and Adjust Clock Drift:
  • Monitor the drift between clocks and adjust synchronization intervals accordingly.
  • If drift rates are known, incorporate them into clock adjustments to maintain better alignment over time.
• Apply Cristian’s Algorithm:
  • Use the minimum RTT observed as a basis to reduce error, assuming the actual delay cannot be shorter than this.
  • Set the time to the midpoint of the earliest possible time window during synchronization.
• Use Network Time Protocol (NTP):
  • Employ NTP, which uses hierarchical clock synchronization across multiple levels (stratum levels).
  • Synchronize with lower-latency, higher-accuracy servers within the NTP hierarchy.

10.2 Practical Steps to Minimize Error

1. Ensure both machines use reliable clocks with minimal drift.
2. Connect the machines through low-latency, stable network paths.
3. Prefer local time servers or synchronization sources to reduce latency.
4. Set up periodic synchronization to adjust for ongoing drift.
5. Implement clock skew correction mechanisms to smooth discrepancies.

10.3 Advanced Methods

• Use Precision Time Protocol (PTP):
  • PTP provides higher accuracy by timestamping messages at the hardware level, reducing software-induced delays.
• Deploy GPS-Based Synchronization:
  • Synchronize clocks using GPS, which provides high-precision time signals, bypassing network delay variability.
• Implement Stratum-Specific Configuration:
  • In NTP setups, configure clients to synchronize with high-precision, low-stratum servers for reduced errors.

10.4 Conclusion

Reducing synchronization error between machines involves careful measurement of delays, statistical filtering, and the use of advanced protocols like NTP and PTP. Combining these methods ensures improved precision and reliability for time-sensitive applications.

11.1 Key Mechanisms for Consistency

• Write-Ahead Log (WAL):
  • All updates are written to the WAL before being applied to in-memory structures (MemStores).
  • This ensures durability and allows recovery in case of node failure.
• Atomic Writes:
  • All updates to a single row are atomic. Multiple columns in the same row can be updated in a single operation without risking partial updates.
• Region-Based Data Management:
  • HBase tables are divided into regions, each managed by a single region server.
  • This eliminates the need for distributed consensus for a single row, simplifying consistency management.

11.2 Data Replication and Strong Consistency

• Region Ownership:
  • Each region is served by one active region server, ensuring a single authoritative source for reads and writes.
• Replication Across Data Centers:
  • For multi-data-center setups, asynchronous replication is used to propagate updates, ensuring eventual consistency across data centers while maintaining strong consistency locally.
• Zookeeper Coordination:
  • Zookeeper ensures that only one region server is active for a given region, preventing split-brain scenarios.

11.3 Recovery and Failover

• Automatic Failover:
  • If a region server fails, Zookeeper reassigns its regions to other servers.
• Log Replay:
  • When a new region server takes over, it replays the WAL entries to ensure no data is lost.

11.4 Client-Side Consistency Guarantees

• Strictly Consistent Reads:
  • Clients always read from the latest version of data in HBase, ensuring that they see the most recent updates.
• Read Isolation:
  • Reads are isolated from ongoing writes, ensuring that partial or inconsistent states are never exposed.

11.5 Advantages and Trade-offs

• Advantages:
  • Strong row-level consistency.
  • Reliable recovery from failures.
  • Durability through WAL.
• Trade-offs:
  • Higher write latency due to WAL and atomicity guarantees.
  • Reduced flexibility in write operations compared to eventual consistency systems.

11.6 Conclusion

HBase achieves consistency through mechanisms like the Write-Ahead Log, atomic updates, and strict region management. Its design ensures reliable, up-to-date data access, making it ideal for systems requiring strong consistency guarantees.

12.1 Core Idea of Lamport Causality

• Causal Dependency: If an event \(A\) influences event \(B\), then \(A\) causally precedes \(B\).
• Logical Timestamps: Lamport introduces logical clocks to assign timestamps to events, ensuring that causally related events are properly ordered.

12.2 Happens-Before Relation

The "Happens-Before" relation (\(\rightarrow\)) is a partial ordering of events that defines causality:

• \(A \rightarrow B\): Event \(A\) happens before \(B\) if:
  • Both occur in the same process, and \(A\) happens earlier in the process timeline.
  • Process \(A\) sends a message that is received by process \(B\).
  • \(A \rightarrow B\) and \(B \rightarrow C\) imply \(A \rightarrow C\) (transitivity).
• If no causal relationship exists between two events, they are considered concurrent.

12.3 Logical Clock Mechanism

• Each process maintains a counter (logical clock).
• The clock is incremented whenever an event occurs.
• When a process sends a message, it includes its current clock value in the message.
• Upon receiving a message, the recipient updates its clock to the maximum of its current clock and the received timestamp, then increments it.

This ensures that causally dependent events have consistent timestamps.

12.4 Practical Uses

• Event Ordering: Ensures events are processed in a causally consistent manner in distributed systems.
• Debugging: Helps trace the sequence of events to identify issues in distributed applications.
• Concurrency Control: Used in distributed databases to manage transaction dependencies.

12.5 Advantages and Limitations

• Advantages:
  • Enables causally consistent event ordering without synchronized clocks.
  • Simple to implement with minimal computational overhead.
• Limitations:
  • Does not capture the total order of events; only a partial order is established.
  • Concurrent events cannot be distinguished causally.

12.6 Conclusion

Lamport causality provides a logical framework for ordering events in distributed systems based on their causal relationships. It is a critical building block for understanding and designing systems that require consistency and coordination across distributed processes.

13.1 Steps to Assign Lamport Timestamps

1. Initialize Logical Clocks:
   • Each process starts with a logical clock set to \(0\).
2. Local Events:
   • When a process executes an event, it increments its logical clock by \(1\).
3. Message Sending:
   • When a process sends a message, it increments its logical clock by \(1\) and attaches the updated clock value to the message.
4. Message Receiving:
   • Upon receiving a message, a process updates its logical clock to the maximum of its current clock and the received timestamp, then increments it by \(1\).

13.2 Example

Consider three processes \(P_1\), \(P_2\), and \(P_3\) with the following events:

• \(P_1\): \(A \rightarrow C \rightarrow E\)
• \(P_2\): \(B \rightarrow D \rightarrow G\)
• \(P_3\): \(F \rightarrow H\)

Messages:

• \(C\) at \(P_1\) sends a message to \(D\) at \(P_2\).
• \(E\) at \(P_1\) sends a message to \(F\) at \(P_3\).

14.1 Steps to Assign Vector Timestamps

1. Initialize Vector Clocks:
   • Each process maintains a vector of size \(N\) (number of processes), initialized to all zeros.
   • The \(i\)-th element of a process’s vector clock reflects the progress of process \(i\).
2. Update Local Clock:
   • When a process performs an internal event, it increments its own entry in the vector clock.
3. Send a Message:
   • When a process sends a message, it attaches its current vector clock to the message.
4. Receive a Message:
   • When a process receives a message, it updates its vector clock by taking the element-wise maximum of its own clock and the received clock, then increments its own entry.

14.2 Example

Consider three processes \(P_1\), \(P_2\), and \(P_3\) with the following events:

• \(P_1\): \(A \rightarrow C \rightarrow E\)
• \(P_2\): \(B \rightarrow D \rightarrow G\)
• \(P_3\): \(F \rightarrow H\)

Messages:

• \(C\) at \(P_1\) sends a message to \(D\) at \(P_2\).
• \(E\) at \(P_1\) sends a message to \(F\) at \(P_3\).