Mastering Distributed Systems: Efficient State Serialization and Protocol Design

Introduction to Distributed Systems State Management

In distributed systems, efficient communication between clients and servers is crucial. This tutorial covers key concepts from a problem set on state serialization, protocol comparison, and end-to-end delay analysis. We'll explore these through a game board example and a ChatGPT query pipeline, tying in modern trends like AI and cloud computing.

Part A: Marshalling Game State

Understanding the Code Skeleton

The provided pseudocode serializes a 100x100 game board (squareval) and the round number. We'll fill in the missing parts for a 64-bit system.

(1) total_size = sizeof(int32_t) + 100 * 100 * sizeof(int8_t) + sizeof(int32_t)
Explanation: We need space for the total_size field itself (4 bytes), the board (100*100 bytes), and the round (4 bytes). Note: total_size is a size_t, but we store it as int32_t to match typical packet headers.

(2) memcpy(data_packet, total_size, sizeof(int32_t)
Explanation: Copy the total_size value (as an int32_t) into the first 4 bytes of the packet. The second argument should be a pointer to total_size, but the code snippet uses total_size directly; we assume &total_size is intended.

(3) int offset = sizeof(int32_t)
Explanation: After the total_size field, the board data starts at offset 4.

(4) row_size = 100 * sizeof(int8_t)
Explanation: Each row has 100 squares, each 1 byte.

(5) memcpy(data_packet + offset + (i * row_size), currentstate->squareval + i * 100
Explanation: Copy the i-th row from the source array (which is a flat array of 10000 bytes) to the packet at the correct row offset.

Part B: Total Delay Calculation

Given: marshalling/unmarshalling = 5 ms each (client and server), one-way latency = 10 ms, bandwidth = 240 kbps = 30 KB/s. The serialized state size: 4 bytes (total_size) + 10000 bytes (board) + 4 bytes (round) = 10008 bytes ≈ 9.77 KB. Transmission time = size / bandwidth = 10008 bytes / 30,000 bytes/s ≈ 0.3336 s = 333.6 ms. Total delay = marshalling (client) + transmission + propagation (one-way) + unmarshalling (server) = 5 ms + 333.6 ms + 10 ms + 5 ms = 353.6 ms. However, the question asks from Michael's move completion to Jimmy's start: this includes server processing? The problem says "moment Michael completes his move, to the moment Jimmy can start thinking about his move." Assuming Jimmy is the other client, the server must send the state to Jimmy. So we double: 5 (client marshal) + 333.6 (upload) + 10 (prop up) + 5 (server unmarshal) + server processing (assume 0) + 5 (server marshal) + 333.6 (download) + 10 (prop down) + 5 (client unmarshal) = 707.2 ms. Alternatively, if the server just forwards, we might include only one-way. We'll assume the typical case: total delay = 2 * (marshalling + transmission + propagation) = 2*(5+333.6+10) = 697.2 ms. Since the problem statement is ambiguous, we'll present the reasoning.

Part C: Efficient Move Encoding

Instead of sending the entire board, send only the changed squares. Each move modifies at most 10 squares. We can encode each changed square as (row, col, new_value). Use 2 bytes for row (0-99), 2 bytes for col, and 1 byte for value = 5 bytes per square. Plus a header with number of changed squares (1 byte). So max 1 + 10*5 = 51 bytes per move.

Part D: Average Size and Delay

Original encoding: 10008 bytes. Average changed squares = 5. Efficient encoding: header (1 byte) + 5 * 5 = 26 bytes. Transmission times: original = 10008 / 30000 = 333.6 ms; efficient = 26 / 30000 = 0.867 ms. Total delay (round trip) with marshalling: original = 2*(5 + 333.6 + 10) = 697.2 ms; efficient = 2*(5 + 0.867 + 10) = 31.734 ms. Huge improvement.

Part E: When Many Squares Change

If 5000 squares change, efficient encoding: 1 + 5000*5 = 25001 bytes. Transmission time = 25001/30000 = 833.4 ms. Total delay = 2*(5 + 833.4 + 10) = 1696.8 ms. Original remains 697.2 ms. So original is better.

Part F: Insight

The best strategy depends on the ratio of changed state to total state. For small changes, delta encoding wins; for large changes, full state may be better. Adaptive approaches can switch based on change size.

Part G: Endianness and Hardware Upgrade

Jimmy's new non-Intel chip may use big-endian byte order, while the original Intel chip used little-endian. The serialized data (especially int32_t round and total_size) would be misinterpreted. Fix: use a consistent endianness (e.g., network byte order) by converting with htonl/ntohl before transmission and after reception.

Protocol Comparison: Stop-and-Go vs Blast

Part A: Crowded Cafe (low latency, moderate bandwidth)

Stop-and-go: sends one recipe, waits for ACK. Blast: sends all at once. With low latency (10 ms), stop-and-go has high overhead per recipe due to RTT. Blast is better as it uses bandwidth efficiently, unless packet loss is high.

Part B: Mars (high latency L seconds)

Stop-and-go: each recipe incurs RTT = 2L. Blast: only one RTT for all recipes. Blast is much better for high latency.

Part C: Which is Better?

In both cases, blast is better because it reduces the number of round trips. Stop-and-go is only beneficial when bandwidth is extremely limited and loss is high, but even then, pipelining (like sliding window) is better.

Part D: High Packet Loss

With high loss, blast may waste bandwidth retransmitting all recipes even if only one is lost. Stop-and-go retransmits only the lost one. So stop-and-go is better under high loss, especially if recipes are large.

End-to-End Delay in ChatGPT Pipeline

Part A: Query and Response

Given: Wi-Fi latency 10 ms, bandwidth 10 Mbps; Ethernet latency 1 ms, bandwidth 100 Mbps; Internet latency 500 ms, bandwidth 50 Mbps; server processing 200 ms. Query size 10 KB, response 5 KB. Transmission times: Wi-Fi: 10KB/10Mbps = 8 ms; Ethernet: 10KB/100Mbps = 0.8 ms; Internet: 10KB/50Mbps = 1.6 ms; total upload transmission = 10.4 ms. Response: 5KB/50Mbps = 0.8 ms (Internet), 5KB/100Mbps = 0.4 ms (Ethernet), 5KB/10Mbps = 4 ms (Wi-Fi) = 5.2 ms. Propagation delays: 10+1+500 = 511 ms each way. Total = upload transmission + upload propagation + server processing + download transmission + download propagation = 10.4 + 511 + 200 + 5.2 + 511 = 1237.6 ms.

Part B: File Upload

30 MB file split into 1000 packets of 30 KB each. This is a pipelining scenario. The total delay includes serialization delays at each link. We need to consider the store-and-forward nature. The cloudlet receives the entire file before forwarding. So total delay = time to send file over Wi-Fi + time to send over Ethernet + time to send over Internet + server processing + response time. Wi-Fi: 30MB/10Mbps = 24 s; Ethernet: 30MB/100Mbps = 2.4 s; Internet: 30MB/50Mbps = 4.8 s; propagation: 10+1+500 = 511 ms each way (ignored for simplicity). Server processing 200 ms. Response size? Not given, assume similar. Total ≈ 24+2.4+4.8+0.2 = 31.4 s plus propagation. This shows the impact of bandwidth and store-and-forward delays.

Conclusion

Understanding these concepts helps design efficient distributed systems. Whether optimizing game state transfers or AI query pipelines, always consider the trade-offs between full state and delta encoding, protocol choice based on latency and loss, and the impact of endianness.