Networks & distributed systems

Routing chooses the longest matching prefix. Stream reads need not align with writes. A length field itself may arrive in pieces.

The next hops are C, B, A, and D respectively. Prefix specificity, rather than table order, selects the route. TCP presents an ordered byte stream, so receiving HELLOW then ORLD is allowed; two writes do not imply two reads. One framing design uses a fixed-width unsigned length followed by exactly that many payload bytes. Accumulate a partial header, validate length against a configured maximum before allocating, then accumulate the body. Preserve leftover bytes for the next frame. Define byte order and what a truncated connection means.

DNS resolves names using its own records and caching rules. TLS authenticates a peer according to the chosen trust policy and protects channel confidentiality and integrity; it does not establish application authorization or correctness. HTTP defines request/response semantics and its own framing rules. None of these guarantees that a timed-out application request had no effect. A router forwards packets without needing the application's message boundaries.

Check your reasoning

• Apply longest-prefix match to all four addresses.
• Handle partial headers, partial bodies, and size limits.
• Assign guarantees to the correct layer.

Convert bits to bytes and KiB to 1,024 bytes. TCP is constrained by both flow-control and congestion windows.

The bandwidth-delay product is 100,000,000×0.08=8,000,000 bits, or 1,000,000 bytes. A 256 KiB window permits at most 262,144/0.08=3,276,800 bytes/s, about 26.2144 Mbit/s, under the simplified steady-state model. With receive window 128 KiB and congestion window 1 MiB, the smaller window limits outstanding data: 131,072/0.08=1,638,400 bytes/s, about 13.1072 Mbit/s. These are bounds, not guaranteed achieved rates; loss, application stalls, overhead, and changing RTT can lower throughput.

Little's law gives L=λW=200×0.15=30 mean requests in the system, including service and waiting if W measures both. The identity relates long-run averages in a stable population with consistent boundaries. It does not supply a latency distribution, and two services with the same mean can have very different tails. Applying it to a growing backlog without checking stability hides the problem. Measure arrival and departure rates, queue size over time, and latency percentiles separately.

Check your reasoning

• Use the smaller window and consistent units.
• Define the boundary of the queueing system.
• Do not infer tail latency or stability from a mean identity.

The message carries the send event's timestamp. For vectors, merge componentwise and then increment the receiver's own component.

Lamport timestamps are a=1, b=2, c=1, d=max(1,2)+1=3, e=4, f=max(2,4)+1=5. Events b and c are concurrent: neither has a path of local-order and message edges to the other, although their scalar timestamps differ. Happened-before implies increasing Lamport timestamps; the converse is false. A process-ID tie-break can create a deterministic total order, but that added order is not evidence of causation.

With component order (P,Q), vectors are a=(1,0), b=(2,0), c=(0,1), d=(2,2), e=(2,3), f=(3,3). b and c are incomparable componentwise, revealing concurrency in this fixed-membership model. Vectors require space proportional to represented participants and careful treatment of membership and identity. Neither clock reports elapsed physical time or bounds how long a message spent in transit.

Check your reasoning

• Apply receive updates correctly.
• Give a concurrent pair with unequal scalar clocks.
• Distinguish causal order from wall-clock time.

Linearizability preserves real-time order between non-overlapping operations. Sequential consistency preserves each client's program order, not every cross-client real-time edge.

The first history is not linearizable: the completed write must precede the later read, so the register specification requires 1. It can be sequentially consistent under the given one-operation-per-client history by placing B's read before A's write in a global sequential order. That order preserves both clients' trivial program orders but violates real time. If the read overlaps the write, a linearization can place the read first and return zero; overlap allows either relative order consistent with each operation's interval.

A lagging replica can return the old value after another replica acknowledged the write. Read-your-writes normally constrains a client's reads after its own writes, so it need not protect B from missing A's write. Enforcing a stronger global register contract needs an appropriate read/write protocol and failure assumptions. Waiting for a particular replica position may support a session contract without making all clients' operations linearizable.

Check your reasoning

• Use operation intervals rather than timestamp labels alone.
• Construct the sequential-consistency order.
• State the scope of the session guarantee.

Intersection only ensures a shared witness exists. The protocol must require that witness to preserve relevant durable evidence.

A majority is three. Any two three-member subsets of five intersect because 3+3>5. Progress can tolerate two crashes provided the remaining three can communicate, elect a leader, and access required durable state. D,E alone cannot form a majority. To recruit a third voter, a Raft candidate must satisfy the log up-to-date test based on last term and then index; voters also persist term and vote information. These rules, the log-matching checks, and the leader's replication rules connect quorum intersection to safety. Merely storing an entry on three arbitrary machines is not a complete proof of commitment.

Raft directly commits an entry by majority counting only when it is from the leader's current term; committing that entry also commits preceding entries. Old-term entries can have problematic histories during leadership changes, so applying the same counting shortcut to them is unsafe. In a 2–3 partition, the three-side can eventually make progress under the protocol's timing assumptions; the two-side cannot commit new commands. Safety does not imply guaranteed liveness during unlimited delay or repeated failures. This model excludes Byzantine replicas.

Check your reasoning

• Prove majority intersection.
• Name durable voting and log restrictions.
• Separate current-term commitment, old entries, safety, and liveness.

The local ledger change and outbox row must share one commit. Deduplication and the receiver's durable effect must also share an atomic boundary or an equivalent protocol.

Assign a stable operation ID to the intended shipment. In one local transaction, debit the ledger and insert an outbox row containing that ID and payload. A worker repeatedly sends committed rows. The receiver atomically records the ID, validates that retries use the same payload, performs its durable shipment-state transition, and records the result. It returns the stored result for repeats. Physical shipping still requires a fulfillment process whose own retry behavior is designed; a database row alone cannot make a physical action atomic.

Before local commit there is neither debit nor outbox row. After commit but before sending, the worker can recover the durable row. After the receiver acts but before acknowledgment, the repeated ID retrieves the original result instead of creating a second shipment. Marking the outbox delivered must happen after a trustworthy acknowledgment. Deduplication retention must cover all possible delayed retries or use a protocol that safely retires identities; forgetting too soon makes an old request appear new.

Two-phase commit instead asks prepared participants to await a global commit/abort decision. A prepared participant generally cannot unilaterally guess the decision after coordinator failure without risking atomicity, so classic 2PC can block. An outbox gives eventual delivery and explicit intermediate states, not instantaneous cross-service atomicity.

Check your reasoning

• Identify both atomic boundaries.
• Handle the effect-before-acknowledgment crash.
• State retention and physical-effect limits.