Implement a Reusable Cyclic Barrier from a Mutex and Condition Variables

Implement a cyclic barrier. The barrier is created for a fixed number of threads, called parties. Each thread calls `wait()` when it reaches a synchronization point; the call blocks until all parties have called it, and then all of them are released together. The barrier then resets by itself, so the same threads can use it again for the next round, and the round after that. The interviewer asked for a low-level implementation: build it from a mutex and condition variables, or your language's monitor primitives, rather than from a library barrier, latch, phaser or semaphore-based helper. ```text CyclicBarrier(parties) wait() -> None # blocks until `parties` threads have called wait() in the current round ``` ```hint Reuse is the hard part Trace what happens when the first thread released from a round immediately calls wait() again while other threads from that same round have not woken up yet. ``` ```hint Who wakes whom Decide which thread detects that a round is complete, and how every sleeping thread learns that it may leave. ``` ### Constraints and Clarifications - `parties >= 1`, fixed at construction. - The barrier must work for any number of consecutive rounds without being recreated. - No busy-waiting in the main version. - No thread may leave a round before all parties of that round have arrived, and no thread may be counted toward the wrong round. ### Clarifying Questions - Which primitives are allowed: a mutex and condition variables, or only atomic operations? - Should an optional action run exactly once per round, in the last thread to arrive, before the others are released? - If a waiting thread times out or is interrupted, should the barrier break for all of that round's waiters, or should only that thread leave? - Should `wait()` return anything, such as the thread's arrival order within the round? ### What a Strong Answer Covers - Arrival counting under a lock, with the last arrival releasing everyone at once - A way for each waiter to tell whether its own round has completed, so that immediate reuse is safe - Waiting in a loop that tolerates spurious wakeups, and broadcast rather than single wakeup - Failure semantics: timeouts, interruption, an exception in the per-round action, and resetting a broken barrier - An atomics-only variant, and when spinning beats sleeping - A test strategy that actually exposes the reuse race ### Follow-up Questions - Implement it again using only atomic operations and spinning. How do you make it reusable without a lock? - Add `wait(timeout)`. What happens to the threads already waiting when one of them times out? - The per-round action throws an exception. What state is the barrier left in, and what do the other threads see? - How would you write a test that reliably exposes a barrier that breaks on reuse?