Attach Lamport and Vector Clocks and Count Lost Updates and Retries

Goal

You will attach Lamport clocks and vector clocks yourself to the event records of four processes, and confirm with the definition where "a smaller number happened earlier" is wrong. Then you will find the conflicts in writes to the same key on three replicas whose wall clocks are skewed, and count which updates disappear without a trace when merged by wall-clock LWW. Finally you will calculate how many times the DB calls multiply if you attach retries at every layer, and write a summary report.

Why it matters

A Lamport clock promises only that the number grows if a → b, and a smaller number does not mean it happened first. If you trust this converse to sort logs or judge conflicts, you get wrong answers with no errors. A vector clock tells you when concurrent events are concurrent, so it lets you count what updates LWW dropped. Retries have the same structure: numbers that look reasonable when viewed layer by layer multiply and pile up on the weakest place. So the grader of this lab does not look only at the numbers you wrote; it runs your functions again on records that are not the materials and compares them with the reference implementation.

Materials

They are under /opt/fixtures/svccs/clocks/. Only read them.

events.csv    프로세스 P·Q·R·S 의 사건 기록. 끝내 도착하지 않은 메시지가 하나 있다
replicas.csv  복제본 A·B·C 의 쓰기와 동기화 메시지. 복제본마다 벽시계가 어긋나 있다
pairs.json    {"pairs": [["R3", "S11"], ...]} — 3단계에서 관계를 판정할 사건 쌍
retry.json    {"layers": [{"name", "retries"}, ...위→아래], "blip_fail_first": 정수}

The columns of both CSVs are proc,seq,kind,msg,key,value,wall_ms. The files are written in order by process and sequence number.

proc     프로세스(복제본) 이름. 사건 id 는 proc + seq, 예) P3
seq      그 프로세스 안의 순번(1부터)
kind     local | send | recv | write        (write 는 로컬 사건의 한 종류)
msg      send/recv 의 메시지 id. 수신은 같은 id 의 송신이 보낸 것이다
key,value write 의 키와 값
wall_ms  그 프로세스의 벽시계 값(밀리초). 프로세스마다 어긋나 있다

Steps

1. Count events.csv and in /root/svccs/clocks/summary.json write events (the total number of events), by_process ({process: number of events}), locals, sends, recvs (the number of distinct messages), and in_flight (the list of message ids that were sent but never received, sorted).
2. In /root/svccs/clocks/clocks.py, create load_events(path) (seq and wall_ms as integers) and lamport(events). lamport returns {event id: value}. The rule: +1 for every event, for a receipt max(자기 앞 사건 값, 그 송신의 값) + 1 (the larger of the value of its own preceding event and the value of the matching send, plus 1), and 0 before the first event of a process. Write the result for all the materials to /root/svccs/clocks/lamport.json as {"clocks": {...}, "max": 가장 큰 값} (max is the largest value).
3. In the same file, create happened_before(events, a, b) (exactly the three conditions of the definition; True if a → b). For each pair in pairs.json, judge relation as "a->b"·"b->a"·"concurrent", and write it to /root/svccs/clocks/hb.json as {"pairs": [{"a", "b", "relation"}, ...], "lamport_misleading": 동시인데 램포트 값이 다른 쌍의 수} (lamport_misleading is the number of pairs that are concurrent but whose Lamport values differ).
4. In the same file, create vector_clocks(events) ({event id: [slots...]}, with the slot order in the alphabetical order of process names) and compare(u, v) ("before"·"after"·"equal"·"concurrent"). Compare every pair of distinct events in events.csv, and in /root/svccs/clocks/vector.json write processes, pairs_total, pairs_ordered, pairs_concurrent, lamport_misleading (the number of concurrent pairs whose Lamport values differ), and agrees_with_definition (true if every pair gets the same answer as the definition in step 3).
5. In the same file, create conflicts(events). Two writes to the same key that are concurrent by vector clock are a conflict. It returns [[쓰기 id, 쓰기 id], ...] (a list of pairs of write ids; the order inside a pair is free). Write the result for replicas.csv to /root/svccs/clocks/conflicts.json as writes (the number of writes), conflict_pairs, and keys (the keys that have conflicts, sorted).
6. In the same file, create lww(events). The rule is exactly the "LWW rule" below. Write the result for replicas.csv to /root/svccs/clocks/lww.json as final ({key: remaining value}), lost (a list), lost_updates (the number of items in lost), and causal_inversions (a list).
7. In the same file, create amplify(retries, fail_first=None). The rule is exactly the "Retry rule" below. With retry.json, compute the case where the DB keeps failing (fail_first=None) and the case where it fails only for the first blip_fail_first calls, and in /root/svccs/clocks/retry.json write layers (a list of names), attempts, and db_down·db_blip (each with invocations·db_calls·success).
8. In /root/svccs/clocks/report.json, write lamport_max, pairs_concurrent, conflicts (the number of conflict pairs), lost_updates, causal_inversions (the count), db_calls_all_layers (the number of DB calls when the DB keeps failing), retry_only_at (the name of one layer where you will keep retries; you choose), db_calls_retry_only_at (the number of calls the DB receives if it keeps failing when only that layer retries and the rest try once each), and order_with (which of "lamport"·"vector"·"wall" you must compare with to tell concurrency apart).

LWW rule

키마다 wall_ms 가 가장 큰 쓰기가 이긴다. wall_ms 가 같으면 proc 이름이 사전순으로 큰 쪽.
final     키 → 이긴 쓰기의 value            winner  키 → 이긴 쓰기의 id
lost      이긴 쓰기가 아니면서, 이긴 쓰기보다 앞서지(→) 않은 쓰기
          (이긴 쓰기가 이미 본 쓰기는 '덮어쓴' 것이지 잃은 것이 아니다)
inversions lost 가운데 이긴 쓰기보다 인과적으로 뒤인(winner → w) 쓰기
돌려줄 것: {"final", "winner", "lost", "inversions"} — 목록은 정렬

Retry rule

retries 는 위 계층부터의 목록이다. 계층 i 는 불리면 아래를 최대 retries[i] + 1 번 부르고,
한 번이라도 성공하면 그만 부른다. 맨 아래 계층이 부르는 것이 DB 다.
DB 는 한 사용자 동작 동안 받은 호출 가운데 처음 fail_first 번은 실패, 그 뒤로는 성공한다
(fail_first 가 None 이면 계속 실패).
돌려줄 것: attempts(계층별 retries+1), invocations(계층별로 불린 횟수, 맨 위는 1),
          db_calls, success(맨 위 계층이 결국 성공했나)

Notes

• The grader imports clocks.py. Put code that reads files and produces results under if __name__ == "__main__": or in a separate script. The functions must use only the event list they receive as an argument: the grader also passes records with different process names and counts.
• The files are written by process, so if you compute line by line from the top, you meet a receipt whose send value does not exist yet. Process the events whose predecessors have all been computed first.
• Common mistakes: a Lamport clock that does only +1 on receipt without max, judging causality by "if L(a) < L(b) then a → b," comparing vectors by the sum or by a single slot and seeing concurrent events as ordered, and adding the per-layer attempt counts instead of multiplying them.
• The outputs disappear when the session ends. Keep them elsewhere if you need them.

Read the event records

Count events.csv and write events, by_process, locals, sends, recvs, and in_flight to /root/svccs/clocks/summary.json.

If you read with csv.DictReader, each line is a dictionary. sends and recvs are the numbers of distinct msg values, and in_flight is the set of send msgs minus the set of receive msgs. A message that was never received cannot be the cause of any later event.

Attach Lamport clocks

Create load_events and lamport in /root/svccs/clocks/clocks.py, and write the result for all the materials to /root/svccs/clocks/lamport.json as clocks and max. The grader also calls lamport with three variant records that have different process names and counts.

A local event or send gets the value of the previous event + 1, and a receive gets max(previous event's value, send's value) + 1. If you scan once in file order, you hit a receive whose send value does not exist yet: process only events whose predecessors have all been computed, and pass the rest to the next round.

Judge happened-before by its definition

Create happened_before(events, a, b) in clocks.py, judge the relation of each pair in pairs.json, and write pairs and lamport_misleading to /root/svccs/clocks/hb.json. The grader compares happened_before on random pairs from variant records.

a → b is whether, following backward from b through "the previous event in the same process" and "the matching send if it is a receive," you reach a. It is easy if you build the set of preceding events for each event. You must not judge by comparing Lamport values: two concurrent events also have different values.

Tell concurrency apart with vector clocks

Create vector_clocks and compare in clocks.py, compare every pair of events in events.csv, and write /root/svccs/clocks/vector.json. The grader compares vector_clocks on variant records and compare on hand-made vectors.

Increment your own slot by 1, and on a receive first merge slot by slot with max. The comparison is slot by slot: if every slot is less than or equal, it is before; if every slot is greater than or equal, it is after; if neither, it is concurrent. If you compare by the sum of slots, even concurrent pairs get an order.

Find concurrent writes to the same key

Create conflicts(events) in clocks.py, and write the result for replicas.csv to /root/svccs/clocks/conflicts.json as writes, conflict_pairs, and keys. The grader also calls conflicts with variant records that have different numbers of replicas and keys.

A conflict is a pair of writes that have "the same key" and are "concurrent by vector." If either one is missing, the list differs. If you decide the order by wall clock, all concurrent writes look like "writes with a before and after."

Count the updates that LWW silently dropped

Create lww(events) in clocks.py following the LWW rule, and write the result for replicas.csv to /root/svccs/clocks/lww.json as final, lost, lost_updates, and causal_inversions. The grader also calls lww with variant records that have different wall-clock skew.

Not every overwritten write is lost. If the winning write had already seen it (→) when it wrote, that is an intended overwrite. The lost ones are writes the winner never saw, and among those, the ones that are causally after the winning write are causal inversions.

How many times does it multiply when every layer retries

Create amplify(retries, fail_first=None) in clocks.py following the retry rule, compute the two scenarios with retry.json, and write them to /root/svccs/clocks/retry.json. The grader also calls amplify with other numbers of layers, retries, and fail_first.

retries is "the number of times to try again," so the number of attempts is retries + 1. The number of times layer i is invoked is the product of the attempt counts of the layers above it, and if the DB keeps failing, the DB calls are the product of the attempt counts of all layers. For the case where the DB comes back partway through, it is safer to actually run it through with recursion.

Summary report

Write lamport_max, pairs_concurrent, conflicts, lost_updates, causal_inversions, db_calls_all_layers, retry_only_at, db_calls_retry_only_at, and order_with to /root/svccs/clocks/report.json.

Most values can simply be copied from the outputs of earlier steps. retry_only_at is a layer name you choose, and if only that layer retries, the DB calls equal that layer's attempt count. order_with must be a method that can give the answer "concurrent."