Size of Vector Clocks, Matrix Clocks, Virtual Time and Physical Clock Synchronization

Flashcards covering vector clocks, matrix clocks, virtual time, physical clock synchronization (NTP), global state recording (Chandy-Lamport), and distributed mutual exclusion (Lamport, Ricart-Agrawala, Maekawa, Agarwal-El Abbadi).

Is a vector clock of size $n$ necessary for a computation with $n$ processes if the goal is to explicitly track progress at every other process?

Yes, a size of $n$ is necessary in that scenario.

In terms of causality, what is the necessary size of a vector clock?

The size must be equal to the dimension of the partial order $(E, \text{≻})$.

What is defined as a linear ordering of events $E$ that is consistent with the partial order $(E, \text{≻})$?

A linear extension.

What is the dimension of a partial order?

The minimum number of linear extensions whose intersection gives exactly the partial order.

What is the dimension of the partial order in a client-server interaction where queries and responses alternate strictly?

One ($1$).

What is a "crown" in the context of concurrent send-receive executions?

A graphical property where messages are such that $Send(m_i) \text{≻} Receive(m_{i + 1 \text{ mod } (n - 1)})$ for all $i$ from $0$ to $n - 1$.

What is the dimension of a crown of $n$ messages?

$$n$$

In a matrix clock system maintained by process $p_i$, what does $mt_i[i, i]$ represent?

The local logical clock of $p_i$.

In a matrix clock $mt_i[1..n, 1..n]$, what does the entry $mt_i[i, j]$ denote?

The latest knowledge process $p_i$ has about the local logical clock of process $p_j$, which is $mt_j[j, j]$.

What does $mt_i[j, k]$ represent in a matrix clock?

The knowledge $p_i$ has about the latest knowledge that $p_j$ has about the local logical clock of $p_k$.

According to Rule R1 for Matrix Time, how does process $p_i$ update its local logical time before an event?

$mt_i[i, i] := mt_i[i, i] + d$ (where $d > 0$).

What information is piggybacked with every message $m$ in a matrix clock system?

The matrix time $mt$.

What is the significance of the property $\text{min}_k(mt_i[k, l]) \text{≥} t$ in matrix clocks?

Process $p_i$ knows that every other process knows that $p_l$'s local time has progressed until $t$, allowing for the disposal of obsolete information.

Which mechanism does the implementation of virtual time use for organizing and synchronizing distributed systems?

The Time Warp mechanism.

On what optimistic assumption does the Time Warp mechanism rely?

That synchronization conflicts and rollbacks generally occur rarely.

How is Virtual Time defined as a coordinate system?

It is a global, one-dimensional, temporal coordinate system on a distributed computation used to measure computational progress and define synchronization.

What are the four components that characterize every message in a virtual time system?

The name of the sender, the virtual send time, the name of the receiver, and the virtual receive time.

State Semantic Rule 1 for virtual time systems.

$\text{Virtual send time of each message} < \text{Virtual receive time of that message}$.

State Semantic Rule 2 for virtual time systems.

$\text{Virtual time of each event in a process} < \text{Virtual time of next event in that process}$.

What happens in a Virtual Time system if a message's virtual receive time is less than the local virtual time at the receiver?

A conflict is discovered and offending processes are rolled back.

What is the relationship between the Time Warp mechanism and Lamport's logical clock scheme?

Time Warp is an inverse of Lamport's scheme.

What is the role of the global control mechanism in the Time Warp implementation of virtual time?

It handles global issues such as global progress, termination detection, I/O error handling, and flow control.

Why do physical clocks in distributed systems require periodic synchronization?

Because clocks tick at different rates and can drift seconds per day, accumulating errors over time.

To what accurate real-time standard are physical clocks typically synchronized?

$UTC$ (Universal Coordinated Time).

What is the formula representing the specification for a physical timer working correctly with a maximum skew rate $\rho$?

$$1 - \rho \text{≤} \frac{dC}{dt} \text{≤} 1 + \rho$$

Which protocol is widely used for clock synchronization on the Internet and employs the Offset Delay Estimation method?

$NTP$ (Network Time Protocol).

In the hierarchy of NTP time servers, what is the role of the primary server?

The primary server at the root synchronizes directly with $UTC$.

How are the clock offset $\theta$ and roundtrip delay $\rho$ estimated in NTP if the differential delay is small?

$\theta = \frac{a + b}{2}$ and $\rho = \frac{a - b}{2}$, where $a = T_1 - T_3$ and $b = T_2 - T_4$.

What is the estimated offset $O_i$ between A's clock and B's clock in NTP?

$$O_i = \frac{T_{i - 2} - T_{i - 3} + T_{i - 1} - T_i}{2}$$

What is the estimated round-trip delay $D_i$ in NTP symmetric mode?

$$D_i = (T_i - T_{i - 3}) - (T_{i - 1} - T_{i - 2})$$

Why are logical clocks preferred over physical clocks for capturing causality in distributed systems?

Because the rate of event occurrence is much higher than physical clock precision, and physical clocks are only loosely synchronized.

How is the global state $GS$ of a distributed system defined notationally?

$GS = \text{∪}_i LS_i, \text{∪}_{i, j} SC_{ij}$, where $LS_i$ is the local state of process $i$ and $SC_{ij}$ is the state of the channel from $i$ to $j$.

What defines a strongly consistent global state?

A global state that is both consistent and transitless.

What is a "cut" in a space-time diagram?

A zigzag line joining one arbitrary point on each process line that slices the diagram into a PAST and a FUTURE.

What characterizes a consistent cut in a space-time diagram?

Every message received in the PAST of the cut was also sent in the PAST of that cut.

State the consistency condition C2 for a global state recording.

$$\text{send}(m_{ij}) \text{∈} LS_i \text{⇐} m_{ij} \text{∈} SC_{ij} \text{∧} \text{rec}(m_{ij}) \text{∈} LS_j$$

What control message is used by the Chandy-Lamport algorithm for FIFO channels to separate messages?

A marker.

When does the Chandy-Lamport algorithm terminate for a process?

After the process has received a marker on all of its incoming channels.

What is the message complexity for a single instance of the Chandy-Lamport snapshot algorithm?

$O(e)$ messages, where $e$ is the number of edges in the network.

What are the three basic approaches for distributed mutual exclusion?

Non-token based, Quorum based, and Token based.

Define the safety property of a mutual exclusion algorithm.

Only one process can execute the critical section at any given instant.

What is the formula for system throughput in mutual exclusion?

$\text{system throughput} = \frac{1}{SD + E}$, where $SD$ is synchronization delay and $E$ is average critical section execution time.

In Lamport’s mutual exclusion algorithm, when is a process allowed to enter the critical section?

When it has received messages with higher timestamps from all other sites ($L1$) and its request is at the top of its own request queue ($L2$).

What is the message complexity per critical section execution for the Ricart-Agrawala algorithm?

$2(N - 1)$ messages.

In Maekawa’s algorithm, what is the required size of a request set (quorum) for $N$ sites?

$$K \text{≈} \text{√}N$$

Which message types does Maekawa’s algorithm use to handle deadlocks?

$FAILED$, $INQUIRE$, and $YIELD$.

In the Agarwal-El Abbadi algorithm, how are sites logically organized?

Into a complete binary tree.

What is the best-case scenario size for a tree-structured quorum in the Agarwal-El Abbadi algorithm?

$O(\text{log } n)$ sites.

What property is exhibited by the tree quorum algorithm when it can still form a quorum despite site failures less than $\text{log } n$?

Graceful degradation.

In a token-based mutual exclusion algorithm, how is mutual exclusion fundamentally ensured?

By the uniqueness of the token (PRIVILEGE message).