Skip to main content
CSEP 552: Distributed Systems

Problem Set 4: Logical Clocks and Sharding

Due: Tuesday, November 24, 6:30pm. Individual work. Submit a PDF of your answers on Gradescope.

Part 1: Virtual Time

Problems 1 through 3 refer to the figure below. Events are labelled A-N. Messages are labelled u-z (each of which has a send and receive event).

Space-time diagram with three servers, S1, S2 and S3, drawn as vertical lines with time flowing down. Each event is a dot labelled with a letter. From top to bottom, S1 has events A (a local event), B (receives u), C (sends v), D (receives w) and E (receives z). S2 has events F (sends u), G (sends x), H (receives v), I (sends y) and J (sends w). S3 has events K (a local event), L (receives x), M (receives y) and N (sends z). So the six messages are: u from F to B, v from C to H, w from J to D, x from G to L, y from I to M, and z from N to E.

  1. Recall the definition of "happens before".

    e1 happens before e2 if:

    • they happen on the same node and e1 is first, or
    • e1 sends a message and e2 receives that message, or
    • there is some e3 with e1 HB e3 and e3 HB e2 (transitivity).

    Now answer the following questions about happens before.

    1. How many events (labelled A-N) "happen before" event M?

    2. For how many events (labelled A-N) does G "happen before" the event?

  2. Recall Lamport's algorithm for computing logical clocks.

    The algorithm assigns a positive integer timestamp to each event.

    • First event on each node gets timestamp 1.
    • For a local event, add 1 to the previous timestamp.
    • Message send: timestamp the send event like a local event (add 1 to the previous timestamp), and attach that timestamp to the message.
    • Message receive: max(receiver's timestamp, message timestamp) + 1.

    Now answer the following questions about Lamport clocks.

    1. What timestamp is computed for event M?

    2. What timestamp is attached to message w?

    3. What timestamps are computed for events L and J? What does that tell you about their happens-before relationship?

  3. Recall the vector clock algorithm.

    A vector clock is a list of non-negative integers of length \(n\), where \(n\) is the number of nodes.

    Each event gets a vector clock as its timestamp. Component i is the timestamp of the latest event of node i that this event has heard about.

    • First event on each node gets 1 in its own component and 0 elsewhere.
    • For a local event, add 1 to the node's own component of the previous vector.
    • Message send: timestamp the send event like a local event (add 1 to the node's own component of the previous vector), and attach that vector to the message.
    • Message receive: componentwise max(receiver's vector, message vector), then add 1 to the receiver's own component.

    In the problems below, we use [S1, S2, S3] as the vector clock components.

    1. What vector clock is computed for event M?

    2. What vector clock is attached to message w?

    3. What vector clocks are computed for events L and J? What does that tell you about their happens-before relationship?

  4. Explain what it means if two different events have the same logical timestamp in Lamport's algorithm. Justify your answer.

  5. Explain why two different events can never have equal vector clocks.

Part 2: Impossibility

Recall the coordinated attack problem from lecture. Two generals, \(B_1\) and \(B_2\), each start with a boolean input saying whether they think they should attack. The generals then run a deterministic protocol by exchanging messages, and at some point each general may decide true (attack) or false (do not attack). A protocol solves the coordinated attack problem if every execution satisfies the following three requirements.

  • Agreement: if \(B_1\) decides \(v\) and \(B_2\) decides \(w\), then \(v = w\).
  • Validity:
    • if both inputs are false, then neither general decides true;
    • if both inputs are true and no messages are lost in this execution, then both generals decide true.
  • Termination: each general eventually decides some value.

The fault model is an asynchronous network with message drops but not node failures. Assume that if a message is not dropped, then it is eventually delivered.

In lecture we proved that no protocol solves this problem.

Problems 6 to 8 below are variants of the coordinated attack problem. For each variant, say whether the problem is solvable in the asynchronous network model with message drops, or whether it is impossible. If the problem is solvable, describe (at a high level) a protocol to solve the problem. If it is impossible, say (at a high level) how to adapt the proof from lecture to show it is impossible.

  1. Suppose we add a third node \(C\) to the system, which can exchange messages with \(B_1\) and \(B_2\) over a lossy network. Further suppose that \(C\) magically has access to \(B_1\) and \(B_2\)'s input booleans. \(C\) is allowed to assist \(B_1\) and \(B_2\) by exchanging messages, but \(C\) does not have to make a decision. The agreement, validity, and termination conditions apply only to \(B_1\) and \(B_2\), not \(C\).

  2. Suppose messages from \(B_1\) to \(B_2\) may be dropped, but that messages from \(B_2\) to \(B_1\) are always eventually delivered. Adjust the second validity requirement so that it reads "... if no messages from \(B_1\) to \(B_2\) are lost...".

  3. Suppose the network is "bounded lossy" instead of lossy, i.e., in any single execution, at most \(k\) messages are lost by the network, and \(k\) is fixed and known by the protocol.

Future parts of this problem set will be released later.