# Replay Clocks

Ishaan Lagwankar  Michigan State UniversityEast Lansing, Michigan, USA
<EMAIL_ADDRESS>and  Sandeep S Kulkarni  Michigan State UniversityEast
Lansing, Michigan, USA<EMAIL_ADDRESS>
(Date: May 2023)

###### Abstract.

In this work, we focus on the problem of replay clocks ($RepCl$). The need for
replay clocks arises from the observation that analyzing distributed
computation for all desired properties of interest may not be feasible in an
online environment. These properties can be analyzed by replaying the
computation. However, to be beneficial, such replay must account for all the
uncertainty that is possible in a distributed computation. Specifically, if
event $e$ must occur before $f$ then the replay clock must ensure that $e$ is
replayed before $f$. On the other hand, if $e$ and $f$ could occur in any
order then replay should not force an order between them.

After identifying the limitations of existing clocks to provide the replay
primitive, we present $RepCl$ and identify an efficient representation for the
same. We demonstrate that $RepCl$ can be implemented with less than four
integers for 64 processes for various system parameters if clocks are
synchronized within $1ms$. Furthermore, the overhead of $RepCl$ (for
computing/comparing timestamps and message size) is proportional to the size
of the clock. Using simulations, we identify the expected overhead of $RepCl$
based on the given system settings. We also identify how a user can the
identify feasibility region for $RepCl$. Specifically, given the desired
overhead of $RepCl$, it identifies the region where unabridged replay is
possible.

##  1\. Introduction

According to the observer effect, when we try to measure something, we change
it to some extent. Therefore, precise measurement is never truly possible.
Computer programs suffer from this same difficulty. When you try to measure
something in a computation, it changes the underlying computation. In an ideal
world, a program may want to make sure that every step that it is taking is
correct with respect to any environmental changes. However, the time taken for
performing these checks may cause the program to be incorrect. In other words,
it is possible that adding excessive safety checks or checks for guaranteeing
fairness may cause the system to spend substantial time on those checks and
thereby violate system requirements even though those requirements would never
have been violated without those checks in the first place.

This issue is even more complicated in distributed computing where each
process (component, node, etc.) relies on partial information. Hence,
computing the required safety checks (or checking for the satisfaction of
fairness requirements, etc.) would require processes to communicate with each
other. In turn, the time for computing them would be even higher.

As an illustration, consider two drones $A$ and $B$ that are cooperating to
perform a task. Each drone may take independent actions based on some
environment that the other drone cannot see. It is required that the area
covered by the drones remains 50% or above at all times (100% of the time). It
is also preferred that this area remains at 75% most of the time (75% of the
time). Here, we would like to know (1) how frequently a given point $x$ was
covered by one of the drones, (2) how frequently a given point was covered by
both the drones, (3) what was the minimum coverage at any time, etc. (Assume
that they are at two different altitudes so safety measures such as preventing
collision are not necessary). Doing all these checks during the execution
would require that $A$ and $B$ communicate with each other before they make
any move. In turn, it would change the behavior of the drones completely
thereby preventing us to make any conclusion about their behavior in the
absence of these checks. Furthermore, the problem would be even more
complicated if we had a larger number of drones.

One way to address this problem is to log the computation as it is happening
so we can evaluate it later for all properties of interest. These properties
may include non-critical safety properties or desirable performance criteria,
etc. To be beneficial, the amount of storage for the log or the time to create
that log should be small enough so that the underlying computation is affected
minimally. At the same time, the log should capture the non-determinism that
is inherently present in any distributed computation. We also want to make
sure that the creation of the logs is performed independently by each process,
i.e., each process stores its local state whenever it changes along with a
timestamp (discussed next) that identifies when the change was made. We
consider various approaches for storing the timestamps and their implications.

The simplest approach we can consider is to let the timestamp be the physical
time of the relevant process. Here, the storage and computation cost is very
low. However, the physical clocks of processes often differ. Hence, it is
possible that drone $A$ may send a message at time 50 (local time of $A$) but
it is received by $B$ at time $40$ ($B$’s local time). When we try to reply to
this log to evaluate the given properties, it will cause $B$ to receive the
message before $A$ has sent it. This is unacceptable.

The next approach we can consider is vector clocks. Vector clocks introduce
two concerns: Their size of $O(n)$, where $n$ is the number of processes, may
be too high. Another challenge is that vector clocks do not have any reference
to the physical clock and do not account for communication outside the system.
For example, it is possible that drone $A$ activated a green LED at time
$t_{1}$ and $B$ activated a white LED at time $t_{2}$ where $t_{2}>>t_{1}$. In
other words, an external observer will know that the action of $A$ occurred
before $B$. However, if $A$ and $B$ did not communicate then the corresponding
events will be concurrent [6]. Thus, when we replay the log, it is possible
that the white LED event could be replayed before the green LED event. This is
also unacceptable.

Hybrid logical clocks (HLC) [4][5] combine logical clocks and physical clocks.
Specifically, they rely on a system where physical clocks are synchronized
within the acceptable limit of clock skew, $\mathcal{E}$, they guarantee that
$hlc.e<hlc.f$ if $e$ happened before $f$ or $pt.e+\mathcal{E}<pt.f$ ([6]).
Here, $hlc.e$ denotes the Hybrid Logical Clock of process $e$, and $pt.e$
denotes the physical time observed on process $e$. In other words,
$hlc.e<hlc.f$ if $f$ causally depends upon $e$ or $f$ occurred substantially
after $e$. They eliminate the problem associated with physical clocks as HLC
respects causality. They also eliminate the problem caused by vector clocks as
the $HLC$ timestamp of activating the green LED will be less than the $HLC$
timestamp of activating the white LED. $HLC$ does create another problem
though. Consider the case where we have events $e$ and $f$ such that
$|pt.e-pt.f|<\mathcal{E}$ and $e||f$, i.e., the events are causally concurrent
and very close to each other in physical time. Without loss of generality, let
$hlc.e<hlc.f$. In this situation, when we replay the log, $e$ will always
occur before $f$. In other words, the log does not have the necessary
information that could allow it to replay $f$ before $e$ even though they
could have occurred in any order. An extension of HLC, hybrid vector clocks
[12] reduces some of these issues. However, as we highlight in Section 5, this
overhead is still quite high.

Based on these limitations, in this paper, we focus on building a new clock,
RepCl, that combines hybrid logical clocks and vector clocks so as to
eliminate their limitations. Our goal is to investigate scenarios under which
RepCl permits efficient replay of events. To understand why we may need to
limit RepCl to specific scenarios, observe that if the underlying system was
asynchronous (unbounded clock drift) then it is required to have $O(n)$ vector
clocks to enable replay of events. Systems that communicate frequently will
need more information stored to replay events. Thus, we focus on the following
problem: Given the amount of permissible overhead for logging events, what are
the scenarios where perfect replay of events is possible?

Contributions of the paper: We present RepCl, a reply clock that enables the
replay of events in a distributed system. It guarantees that if there is a
causal relation [6] or if $f$ occurred far later than $e$ then
$RepCl.e<RepCl.f$, i.e., the replay will cause $e$ to replayed before $f$. On
the other hand, if $e$ and $f$ are causally concurrent and occurred close in
physical time then they could be replayed in any order. By considering various
system parameters, clock skew ($\mathcal{E}$), message rate $(\alpha)$, and
message delay $(\delta)$, we identify the feasibility region for RepCl.

Organization of the paper:  The rest of the paper is organized as follows: In
Section 2, we describe the model of computation for distributed systems
including the notion of causality and clock synchronization. In Section 3, we
discuss the problem of replay with clocks. Section 4 presents our algorithm
for RepCl. Properties of RepCl for solving the replay algorithm are discussed
in Section 5. Section 6 identifies the representation of RepCl and its
overhead. We discuss our simulation results in Section 7. Section 8 discusses
related work and Section 9 identifies questions raised by RepCl. Finally, in
Section 10, we conclude and discuss future work.

##  2\. Preliminaries

A distributed system is a set of processes $1..n$. Each process has three
types of events (1) $send$, where it sends a message to another process, (2)
$receive$, where it receives a message from another process, and (3) $local$,
where it performs some local computation.

We define the happened-before (denoted by  hb) relation [6] among the events
in a distributed computation.

  * •

If $e$ and $f$ happened on the same process and $e$ occurred before $f$ then
$e\textsf{ hb}\ f$.

  * •

If $e$ was a send event and $f$ was the corresponding receive event then
$e\textsf{ hb}\ f$.

  * •

The  hb relation is transitive, i.e., if there exist events $e,f$, and $g$
such that $e\textsf{ hb}\ g$ and $g\textsf{ hb}\ f$ then $e\textsf{ hb}\ f$

We say that $e||f$ iff $\neg(e\textsf{ hb}f)\wedge\neg(f\textsf{ hb}\ e)$. In
other words, $e$ is concurrent with $f$ iff $e$ did not happen before $f$ and
$f$ did not happen before $e$.

A timestamping algorithm assigns a timestamp for every event $e$ in the system
as soon as the event is created. Additionally, the timestamping algorithm
defines a $<$ relation that identifies how two timestamps are compared.

As an illustration, Lamport’s logical clock assigns an integer timestamp $l.e$
to every event $e$. The $<$ relation for Lamport’s logical clocks is the
standard $<$ for integers. Likewise, the physical timestamping algorithm
assigns $pt.e$ for every event $e$ where $pt.e$ is the physical time of the
process where event $e$ occurred when it occurred, and the $<$ relation is the
same as that over integers. A vector clock [2][7] assigns event $e$ a
timestamp $vc.e$ where $vc.e$ is a vector that includes an entry $vc.e.j$ for
every process $j$. The $<$ relation on two vector clocks $vc.e$ and $vc.f$
requires that each element in $vc.e$ is less than or equal to the
corresponding element in $f$ and some element in $e$ is less than the
corresponding element in $f$. In other words, $vc.e<vc.f$ iff $(\forall
j::vc.e.j\leq vc.f.j)\wedge(\exists j::vc.e.j<vc.f.j)$.

Note that while the $<$ relation is defined by the timestamping algorithm, the
properties of the $<$ relation vary. For example, logical clocks provide one-
way causality information, i.e., $e\textsf{ hb}f\Rightarrow l.e<l.f$. Vector
clocks provide two-way causality information, i.e., $e\textsf{
hb}f\Leftrightarrow vc.e<vc.f$. By contrast, (unsynchronized) physical clocks
may not provide any guarantees. For example, it is possible that $(e\textsf{
hb}f)$ and $pt.e\not<pt.f$ are simultaneously true.

We assume that each process $j$ in the system is associated with a physical
clock, $pt.j$. Clocks of processes are synchronized with a protocol such as
NTP [9] such that the clock of two processes differ by at most $\mathcal{E}$,
where $\mathcal{E}$ is a parameter, i.e., $\forall
j,k::|pt.j-pt.k|\leq\mathcal{E}$. We also assume that individual clocks are
monotonically increasing. We assume that messages are delivered with a minimum
message delay of $\delta$. We do not assume maximum message delay; it could be
$\infty$ if messages are permitted to be lost. Since our focus is on the
replay of events, if a message is lost, it simply implies that the
corresponding receive message is never replayed.

##  3\. Replay with Clocks

In this section, we focus on how clocks can be used to replay a given
computation. We also discuss some of the limitations of using logical clocks
and vector clocks in the replay process. Note that the goal of this section is
only to illustrate the concept and the goals of the replay; it does not focus
on developing an efficient algorithm for the same.

As discussed in the introduction, the goal of replay is to order the events so
that we can evaluate various properties of interest. To replay a given
computation, we begin with the set where each entry is of the form $\langle
e,ts.e\rangle$, where $e$ is the event (send/receive/local) and $ts.e$ is the
timestamp of $e$. To replay the given set of events, we first find events $e$
such that all events with smaller timestamps than $e$ have already been
replayed. In other words, we find the set $\\{e|\neg(\exists f:ts.f<ts.e)\\}$.
We replay one of these events randomly. Then, we remove event $e$. The process
is continued until all events are replayed. Thus, the algorithm for replay is
shown in algorithm 1.

Algorithm 1 ReplayEvents Operation

1:Input: $S$: Set of Events and timestamp

2:while $S\neq\phi$ do

3: $FrontLine=\\{e|(e,ts.e)\in S\wedge\neg(\exists f:(f,ts.f)\in S\wedge
ts.f<ts.e)\\}$

4: Choose a random event $e$ from FrontLine and replay it

5: $S=S-\\{e\\}$

###  3.1. Limitations of Existing Clocks for Replay

As an example, consider the execution in Figure 1. Here, we have four events
$A,B,C$, and $D$. Their physical timestamps and logical timestamps are shown
in Figure 1. If we replay these events using physical clocks then the possible
outcomes are $CBAD$ or $CBDA$. Note that both these outcomes are undesirable,
as $A$ should occur before $B$ based on the causality (happened-before)
relation.

Figure 1. Sample Execution Sequence and Application of Replay Algorithm.

If we replay them by logical clocks, the possible outcome is $CABD$. However,
there is no option to replay $B$ before $C$ even though $B||C$.

If we replay them with vector clocks, possible orderings are $ABCD$, $ACBD$,
or $CABD$. If the clocks were synchronized to be within 5 time units then
$ABCD$ and $ACBD$ are incorrect.

###  3.2. Requirements of Replay Clock RepCl

In this paper, we focus on a system where the physical clocks are synchronized
to be within $\mathcal{E}$, i.e., for any two processes $j$ and $k$,
$|pt.j-pt.k|\leq\mathcal{E}$. The goal of RepCl is to assign a timestamp
$RepCl.e$ to event $e$ such that

Requirement 1. :

If $e$ happened before $f$ then
$RepCl.e<RepCl.f$, i.e., $e$ will always be replayed before $f$

Requirement 2. :

If $f$ occurred far after $e$, i.e., $e$ and $f$ could not have occurred
simultaneously under clock drift guarantee of $\mathcal{E}_{1}$ where
$\mathcal{E}_{1}\approx\mathcal{E}$ then $e$ will be replayed before $f$,
i.e., $RepCl.e<RepCl.f$

Requirement 3. :

If $e$ and $f$ could have occurred in any order in a system where clocks were
synchronized to be within $\mathcal{E}_{2}$, where
$\mathcal{E}_{2}\approx\mathcal{E}$ then $RepCl.e||RepCl.f$ (i.e.,
$\neg(RepCl.e<RepCl.f)\wedge\neg(RepCl.f<RepCl.e))$

In the last two requirements, we have chosen $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ instead of $\mathcal{E}$ itself as it can permit more
efficient implementation by allowing us to maintain a coarse-grained clock. We
discuss this further in Section 5.

##  4\. Algorithm for Replay Clock (RepCl)

In this section, we present our approach for RepCl. As discussed earlier, we
assume that the physical clocks are synchronized to be within $\mathcal{E}$.
We discretize the process execution in terms of epochs, where each epoch
corresponds to an increment of the clock by $I$, $0<I\leq\mathcal{E}$ such
that $\mathcal{E}=\epsilon*I$, where $\epsilon$ is an integer. The timeline of
a process is split into epochs where each epoch is of size $I$ (in the local
process clock). In other words, the epoch of process $j$ is obtained by
$\lfloor\frac{pt.j}{I}\rfloor$.

Structure of RepCl timestamp.  With such discretization, the timestamp of
process $j$ (or event $e$) is of the form

(1) $\langle mx.j,\texttt{offset}.j[],\texttt{counter}.j[]\rangle,$

where $mx.j$ is an integer, $\texttt{offset}.j$ and $\texttt{counter}.j$ are
arrays that store at most one entry $\texttt{offset}.j.k$ and
$\texttt{counter}.j.k$ for process $k$

The intuition behind these variables is as follows: $mx.j$ denotes the maximum
epoch process $j$ is aware of (either due to the value of $pt.j$ or the value
of epochs learned from messages it receives). $mx.j-\texttt{offset}.j.k$
denotes the maximum epoch value of $k$ that $j$ has learnt (either via
direct/indirect message from $k$, clock drift assumption, etc). And, counters
are used to deal with the scenario where multiple events happen within the
same epoch.

For example, the timestamp $\langle 50,[0,1,2],[4,5,6]\rangle$ denotes that
this event is aware of epoch 50 of process $0$, 49 of process $1$, and 48 of
process $2$. And, the counter values are $4,5$ and $6$ respectively. For
brevity, we will drop the counter values if they are not relevant to the
current discussion.

Before we describe the algorithm, we discuss two helper functions, Shift and
MergeSameEpoch. The Shift function allows us to change the value of $mx$.
Since $mx.j-\texttt{offset}.j.k$ denotes the knowledge of $j$ has about the
epoch of $k$, if $mx$ is changed to newmx without providing $j$ any additional
knowledge of the clock of $k$ then $newmx-\texttt{newoffset}.j.k$ should
remain the same as $mx.j-\texttt{offset}.j.k$. Hence, Shift operation changes
offset$.j.k$ to be $\texttt{offset}.j.k+(newmx-mx)$. Furthermore, if this
value is more than $\epsilon$ then we reset it to $\epsilon$, as guaranteed by
the clock drift assumption. (Note that process $j$ can learn about the clock
of $k$ via clock synchronization assumption even if $j$ and $k$ do not
communicate. For example, shifting the timestamp $\langle 12,[0,2,10]\rangle$
so that $mx$ is changed to 20 will result in $\langle 20,[8,10,18]\rangle$. If
$\epsilon=15$, this will change to $\langle 20,[8,10,\epsilon]\rangle$ (cf.
Figure 2).

The MergeSameEpoch function takes two timestamps $t1$ and $t2$ with the same
$mx$ value and combines their offsets by setting to be $\texttt{offset}.j.k$
to be the $min(t1.\texttt{offset}.j.k,t2.\texttt{offset}.j.k)$. For example,
merging $\langle 50,[0,1,2]\rangle$ and $\langle 50,[2,0,1]\rangle$ results in
$\langle 50,[0,0,1]\rangle$.

Description of the Algorithm.  The algorithm works as follows:

Local/Send event.  Here, we describe how $RepCl.j$ is updated when $j$ sends a
message. Let the current timestamp of $j$ be

$\langle mx.j,\texttt{offset}.j[],\texttt{counter}.j[]\rangle$

First, $mx.j$ needs to be increased if the clock of $j$ has advanced beyond
epoch $mx.j$. Hence, we first compute $newmx.j$ which is equal to
$max(mx.j,\texttt{epoch}.j)$. When $j$ sends a message, it does not learn any
new information about the clock of process $k$.

We consider two cases: The first case is for the scenario where the newly
created event $f$ is in a new epoch as the previous event, $e$. This will
happen if $mx$ remains unchanged and $\texttt{offset}.j.j$ is unchanged. In
this case, we increase $\texttt{counter}.j.j$. The second case deals with the
scenario where $f$ is in a new interval. Thus, the offset associated with $k$
is changed using the Shift operation. Note that the Shift operation computes
the shift of all processes except $j$. $\texttt{offset}.j.j$ should be based
on the value of $\texttt{epoch}.j$. Hence, we set it equal to
$newmx-\texttt{epoch}.j$. The Shift operation is illustrated in Algorithm 2.

Figure 2. Working of Shift() on Process 0. Here, $\epsilon$=15, and the shift
is issued to advance to epoch 20. Algorithm 2 Shift Operation

1:Define Shift operation.

2:Shift(${ts},newmx$)

3:for each $k$ do

4: $ts.\texttt{offset}.k\leftarrow{\texttt{offset}.k}+(newmx-{ts.mx})$

5: if $ts.\texttt{offset}.k>\epsilon$ then

6: $ts.\texttt{offset}.k\leftarrow\epsilon$

7:Output: ${ts}$

Algorithm 3 Send Message

1:$newmx\leftarrow\max({mx.j},{\texttt{epoch}.j})$

2:${\texttt{new\\_offset}}\leftarrow{newmx}-{\texttt{epoch}.j}$

3:if $({mx.j}={newmx}\land{\texttt{offset}.j.j}={\texttt{new\\_offset}})$ then

4: ${\texttt{counter}.j.j}\leftarrow{\texttt{counter}.j.j}+1$

5:else

6: ${ts.j}\leftarrow{Shift}({ts.j},{newmx})$

7: ${\texttt{offset}.j.j}\leftarrow\min({newmx}-{\texttt{epoch}.j},\epsilon)$

8: ${\texttt{counter}.j}\leftarrow[0,0,\ldots,0]$

Receive event.  Next, we describe how RepCl is updated when $j$ (with
timestamp $\langle mx.j,\texttt{offset}.j[],\texttt{counter}.j[]\rangle$
receives a message $m$ with timestamp $\langle
mx.m,\texttt{offset}.m[],\texttt{counter}.m[]\rangle$.

First, we compute $newmx$ which is the maximum of $mx.j$, $mx.m$ and
$\texttt{epoch}.j$. Timestamps of $j$ and $m$ are then shifted to $newmx$
using the Shift operation. These timestamps are then merged to obtain the $mx$
and offset values of the new event, say $f$.

Now, we check if the knowledge that $f$ has about epochs is the same as that
of $e$ (the previous event on $j$) or $m$. If all three are in the same epoch
then $\texttt{counter}.j.j$ is set to one more than the maximum of
$\texttt{counter}.j.k$ and $\texttt{counter}.m.k$. If only $e$ and $f$ are in
the same epoch, $\texttt{counter}.j.j$ is incremented by $1$. If only $m$ and
$f$ are in the same epoch, $\texttt{counter}.j$ is set to $\texttt{counter}.m$
and the value of $\texttt{counter}.j.j$ is incremented by $1$. If none of
these conditions apply then counters are reset to $0$.

Algorithm 4 Receive Message

1:Input: Message $m$

2:Let $m$ be the message that was received

3:$newmx\leftarrow\max(mx.j,mx.m,\texttt{epoch}.j)$

4:${ts.a}\leftarrow{\texttt{Shift}}({ts.j},newmx)$

5:${ts.b}\leftarrow{\texttt{Shift}}({ts.m},newmx)$

6:${ts.c}\leftarrow{\texttt{MergeSameEpoch}}({ts.a},{ts.b})$

7:if EqualOffset$(ts.j,{ts.c})\land$ EqualOffset$(ts.m,{ts.c})$ then

8: for each $k$ do

9:
$\texttt{counter}.j.k\leftarrow\max(\texttt{counter}.j.k,\texttt{counter}.m.k)$

10: $\texttt{counter}.j.j\leftarrow\texttt{counter}.j.j+1$

11:if $\texttt{EqualOffset}(ts.j,{ts.c})\land\neg$
$\texttt{EqualOffset}(ts.m,{ts.c})$ then

12: $\texttt{counter}.j.j\leftarrow\texttt{counter}.j.j+1$

13:if $\neg$ $\texttt{EqualOffset}(ts.j,{ts.c})\land$
$\texttt{EqualOffset}(ts.m,{ts.c})$ then

14: $\texttt{counter}.j\leftarrow{\texttt{counter}.m}$

15: $\texttt{counter}.j.j\leftarrow\texttt{counter}.j.j+1$

16:if $\neg$ $\texttt{EqualOffset}(ts.j,{ts.c})\land\neg$
$\texttt{EqualOffset}(ts.m,{ts.c})$ then

17: $\texttt{counter}.j\leftarrow[0,0,\ldots,0]$

As an illustration, consider the execution of the program in Figure 1.
Assuming that $\epsilon=5,I=1,$ and $\mathcal{E}=5$, the RepCl timestamps will
be as shown in Figure 3. Here, event $A$ has physical time of $50$. Since
process P1 has not heard from anyone else so far, the offsets for P2 and P3
will be $\epsilon$. The offset for process P1 will be $0$. Regarding event
$C$, the situation is similar except that the offset for process P3 is $0$.
When event $B$ is created upon receiving message $m_{1}$, process P2 is aware
of times $50$ from $P1$. And, it is the maximum epoch it is aware of. Hence,
offsets are $[0,2,\epsilon]$ respectively. When event $D$ is created, process
P2 is aware of epoch 52 (from P2) and epoch 50 (from P1). It is aware of
timestamp $40$ from P3. However, this information is overridden by the clock
synchronization guarantee that says that the clock of P3 is at least $47$.
Thus, the offsets are set to $[3,e,\epsilon]$ Here, the permissible ordering
is $CABD$.

In this figure, if $\epsilon$ were $20$ then the timestamp of $D$ would be
changed to $[3,2,12]$. Furthermore, $B$ and $C$ could be replayed in any
order. Thus, the permissible replays would be $CABD$ or $ABCD$ or $ACBD$.

Figure 3. Replay of the Execution in Figure 1 with RepCl. Algorithm 5
MergeSameEpoch Operation

1:Input: Timestamp $t1$, Timestamp $t2$

2:Timestamp $ts$ = new Timestamp

3:for each $k$ do

4: $ts.\texttt{offset}.j.k=min(t1.\texttt{offset}.j.k,t2.\texttt{offset}.j.k)$

5:return $ts$

Algorithm 6 EqualOffset Operation

1:Input: Timestamp $t1$, Timestamp $t2$

2:if $t1.{mx}\neq t2.{mx}\vee(\exists j\ t1.{\texttt{offset}.j}\neq
t2.{\texttt{offset}.j})$ then

3: return false

4:else

5: return true

##  5\. Properties of RepCl

In this section, first, we define the $<$ relation on two timestamps $RepCl.e$
and $RepCl.f$. Then, we identify the properties of this $<$ relation and the
happened-before relation.

Definition 1: Given timestamp $RepCl.e=\\\ \langle
mx.e,\texttt{offset}.e[],\texttt{counter}.e[]\rangle$ and
$RepCl.f=\langle mx.f,\texttt{offset}.f[],\texttt{counter}.f[]\rangle$, we say
that
$RepCl.e<RepCl.f$ iff

$\displaystyle mx.f$ $\displaystyle>mx.e+\epsilon$ $\displaystyle\vee$
$\displaystyle\Big{(}|mx.f-mx.e|\leq\epsilon$
$\displaystyle\quad\land\Big{(}\Big{(}\forall
l(mx.e-\texttt{offset}.e.l)\leq(mx.f-\texttt{offset}.f.l)\Big{)}$
$\displaystyle\quad\land\Big{(}\exists
l(mx.e-\texttt{offset}.e.l)<(mx.f-\texttt{offset}.f.l)\Big{)}\Big{)}$
$\displaystyle\quad\vee\Big{(}\forall
l(mx.e-\texttt{offset}.e.l)=(mx.f-\texttt{offset}.f.l)$
$\displaystyle\quad\land\Big{(}\forall
l(\texttt{counter}.e.l)\leq(mx.f-\texttt{counter}.f.l)$
$\displaystyle\quad\land\exists
l(\texttt{counter}.e.l)<(\texttt{counter}.f.l)\Big{)}\Big{)}\Big{)}$

The above $<$ relation first compares if $mx.f$ and $mx.e$ are far apart. If
that is the case, we define $RepCl.e<RepCl.f$. If they are close, i.e.,
$|mx.f-mx.e|\leq\epsilon$, then, we compare the offsets. Since
$mx.e-$offset$.e.k$ identifies the knowledge $e$ had about the epoch of
process $k$, we use a comparison that is similar to vector clocks to determine
if $<$ relation holds between $RepCl.e$ and $RepCl.f$. Finally, if the offsets
are also equal then we use the comparison of counters (again in the same
fashion as vector clocks).

We overload the $||$ relation for comparing timestamps as well. Specifically,

Definition 2 Given timestamps $RepCl.e$ and $RepCl.f$, we say that
$RepCl.e||RepCl.f$ iff $\neg(RepCl.e<RepCl.f)\wedge\neg(RepCl.f<RepCl.e)$

From the construction of the timestamp algorithm, we have the following two
lemmas:

Lemma 1: (e happened before f) $\Rightarrow RepCl.e<RepCl.f$

Lemma 2: $|mx.e-maxt.f|\leq\epsilon\wedge(e||f)\ \ \ \Rightarrow\ \ \
RepCl.e||RepCl.f$

Requirement 1 of RepCl: Observe that Lemma 1 satisfies the first requirement
of $RepCl$; if $e$ happened before $f$ then $e$ must be replayed before $f$.

Requirement 2 of RepCl:  Now, we focus on the second requirement.
Specifically, we show that by letting $\mathcal{E}_{1}=\mathcal{E}+I$, the
second requirement is satisfied.

Observe that in the $RepCl$ algorithm, messages carry the epoch values of
multiple processes. This allows a process to learn epoch information about
other processes. For the subsequent discussion, imagine that the messages also
carried the actual physical time as well. In this case, $j$ will learn about
the clock of a process $k$ via such messages. Additionally, $j$ will also
learn about the clock of a process $k$ based on the assumption of clock
synchronization. Likewise, when event $e$ is created, it will have some
information about the clock of each process. Let $mpt.e$ and $mpt.f$ be the
maximum clock (of any process) that $e$ and $f$ are aware of when they
occurred. If $mpt.f>mpt.e+\mathcal{E}_{1}$ then $f$ cannot occur before $e$
under the clock synchronization guarantee of $\mathcal{E}_{1}$. Now, we show
that in this situation, it is guaranteed that $RepCl.e<RepCl.f$.

By definition of $mx$, $mx.f=\lfloor\frac{mpt.f}{I}\rfloor$ and
$mx.e=\lfloor\frac{mpt.e}{I}\rfloor$. Additionally, we have

| $-1<(x-\lfloor x\rfloor)-(y-\lfloor y\rfloor)<1$
---|---
$\therefore$ | $-1<(\frac{mpt.f}{I}-\lfloor\frac{mpt.f}{I}\rfloor)-(\frac{mpt.e}{I}-\lfloor\frac{mpt.e}{I}\rfloor)<1$
$\therefore$ | $-1<(\frac{mpt.f}{I}-mx.f)-(\frac{mpt.e}{I}-\lfloor\frac{mpt.e}{I}\rfloor)<1$
$\therefore$ | $-1<(\frac{mpt.f-mpt.e}{I})-(mx.f-mx.e)<1$

Now, if $mpt.f-mpt.e>\mathcal{E}+I$ then we can rewrite the second inequality
as $(\frac{\mathcal{E}+I}{I}-(mx.f-mx.e)\leq 1$. Using the fact that
$\mathcal{E}=\epsilon*I$, we have $\epsilon<(mx.f-mx.e)$. In other words,
$mpt.f-mpt.e>\mathcal{E}+I\Rightarrow(mx.f>mx.e+\epsilon)$. By Definition 1,
we have $RepCl.e<RepCl.f$. In other words, we have

Lemma 3: If $f$ occurred far after $e$, i.e., $f$ could not have occurred
before $e$ in a system that guarantees that clocks are synchronized within
$\mathcal{E}_{1}=\mathcal{E}+I$ then $e$ will be replayed before $f$, i.e.,
$RepCl.e<RepCl.f$.

Requirement 3 of RepCl.  Next, we consider the case where $e$ and $f$ could
have occurred in any order if the underlying system guaranteed that clocks
were synchronized to be within $\mathcal{E}_{2}=\mathcal{E}-I$. Letting the
maximum clock that event $e$ (respectively, $f$) was aware of to be $mpt.e$
(respectively, $mpt.f$), we observe that $|mpt.e-mpt.f|\leq\mathcal{E}_{2}$.
Furthermore, $e$ and $f$ must be causally concurrent. Under this scenario, we
show that $RepCl.e||RepCl.f$.

If $|mpt.e-mpt.f|\leq\mathcal{E}-I$, we have

$\therefore$ |  ${|\frac{mpt.e}{I}-\frac{mpt.f}{I}|\leq\ \epsilon-1}$ | // since $\mathcal{E}=\epsilon*I$
---|---|---
$\therefore$ |  ${|\lfloor\frac{mpt.e}{I}\rfloor-\lfloor\frac{mpt.f}{I}\rfloor|\leq\ \epsilon}$ | since $|(x-\lfloor x\rfloor)-(y-\lfloor y\rfloor)|<1$
$\therefore$ |  $|mx.e-mx.f|\leq\epsilon$ | by definition of $mx$

Now, from Lemma 2, $RepCl.e||RepCl.f$. In other words,

Lemma 4 If $e$ and $f$ could have occurred in any order in a system where
clocks were synchronized to be within $\mathcal{E}-I$ then $RepCl.e||RepCl.f$.

Effect of discretization and comparison with hybrid vector clocks [12]: We
note that the discretization of the clock via $I$ has caused the bounds used
for clock synchronization in Lemmas 1 and 2 to be different. We could have
eliminated this if we had not discretized the clocks. (Discretization with $I$
was not done in [12].) However, without discretization, the values of offsets
will be very large. Without discretization, we will need to rely on just the
physical clocks which have a granularity of under 1 nanosecond. Now, if
$\mathcal{E}=1ms$ then the value of the offset could be as large as $10^{6}$.
By discretizing the clock, it would be possible to keep offsets to be very
small (about 4 bits). We expect that the discretization will not seriously
impact the replay. For example, if $\mathcal{E}=1ms$ and $I=0.1ms$ then our
algorithm will guarantee that causally concurrent events within $0.9ms$ can be
replayed in any order. And, events that could not occur simultaneously under a
clock synchronization guarantee of $1.1ms$ will be replayed only in one order.
Additionally, if $e$ happened before $f$ then $e$ will always be replayed
before $f$.

##  6\. Representation of RepCl and its Overhead

In this section, we identify how $RepCl$ can be stored for permitting
efficient computation. As written, $RepCl$ will require $2n+1$ integers.
However, a more compact representation will be possible when we account for
the fact that it is being used in a system where the clocks are synchronized
to be within $\mathcal{E}$. Thus, if $j$ does not hear from $k$ (directly or
indirectly) for a long time then the knowledge $j$ would have about the clock
of $k$ is the same that is provided by the clock synchronization assumption.
In this case, offset$.j.k=\epsilon$. It follows that there is no need to store
this value if we interpret no information about the offset of $k$ to mean that
offset$.j.k=\epsilon$.

With this intuition, we represent $RepCl.j$ as shown in Figure 4. Here, the
value of $mx.j$ (represented by the first word) is 50. The next word
identifies the bitmap. Since the bit corresponding to process 1 is $0$, it
implies that offset$.j.0=\epsilon$. The offset for process 2 is $10$ (first 4
bits of the offset) and $counter.j.2$ is $2$ (first 2 bits of the counter). We
note that the bits for each offset and counter is hard-coded based on the
system parameters (cf. Section 7). The second word is a bitmap that identifies
whether offset$.j.k$ is stored for process $k$. Each offset is stored with a
fixed number of bits in the subsequent word(s).

Figure 4. Sample $RepCl$ representation.

Next, we show that this representation allows us to reduce the cost of storage
as well as the cost of computing timestamps or comparing them (using $<$
relation). Specifically, all these costs are proportional to the number of
processes that have communicated with $j$ recently.

With representation in Figure 4, first, we note that finding the location of
the $1$s in the given bitmap can be done in time that is proportional to the
number of $1$s in the bitmap. ($(n-(n\&(n-1)$ will return the number with only
the rightmost $1$). Thus, we have

Observation 1: Shift and MergeSameEpoch can be implemented using $O(x)$ time
where $x$ is the number of bits set to $1$ in the bitmap.

Note that this means that the time to compute the timestamp for send/receive
at process $j$ is not dependent upon the number of processes in the system.
But only processes that have recently communicated with process $j$. In turn,
this means that

Observation 2: Send and Receive can be implemented using $O(x)$ time where $x$
is the number of bits set to $1$ in the bitmap.

Observation 3: Given two timestamps, $RepCl.e$ and $RepCl.f$, we can determine
if $RepCl.e<RepCl.f$ in $O(x)$ time where $x$ is the number of bits set to $1$
in $e$ and $f$.

It follows that the number of bits that are $1$ in a given timestamp
identifies not only the storage cost of the timestamps but also the time to
compute these timestamps at run time. Effectively, this also identifies the
overhead of the timestamps that enable the replay of the computation. Hence,
in Section 7, we focus on identifying scenarios where the cost of storing
these offsets is within the limits identified by the user.

We note that the above approach will work as long as the number of processes
is less than the number of bits in a word (typically, 64 in today’s systems).
We expect that this will be more than sufficient for many systems in practice.
If there are more than 64 processes, we expect that process $j$ is
communicating with only a subset of these processes. And, if process $j$ does
not communicate with someone there is no need to store offsets for them. Thus,
this approach can be extended for the case where the number of processes is
larger. However, the details are out of the scope of the paper.

##  7\. Simulation Results

As demonstrated in Section 5, the overhead of $RepCl$ depends upon the number
of offsets/counters that need to be stored. And, this value depends upon the
number of processes that communicate with a given process in the $\mathcal{E}$
time. In other words, the system parameters will determine the size of
$RepCl$. In this section, we evaluate the overhead of $RepCl$ via simulation.

(a) $\alpha$ = 20 messages/s, $n$ = 32.

(b) $\alpha$ = 40 messages/s, $n$ = 32.

(c) $\alpha$ = 160 messages/s, $n$ = 32.

(d) $\alpha$ = 20 messages/s, $n$ = 64.

(e) $\alpha$ = 40 messages/s, $n$= 64.

(f) $\alpha$ = 160 messages/s, $n$ = 64.

Figure 5. $\tau$ vs $\mathcal{E}$ when varying $I$, $\delta=8\mu s$.

Specifically, we simulate a distributed environment with five key parameters -
the number of processes ($n$), the maximum allowed clock skew ($\mathcal{E}$),
the interval size ($I$), the message rate ($\alpha$), and the message delay in
microseconds ($\delta$). The message delay is modeled as the average delay
experienced in the simulated network, and can vary by some nonzero $\Delta$ in
production. In the simulation, at every clock tick, a process delivers any
messages it is expected to deliver at that clock tick. It also sends a message
to other processes based on the message rate $\alpha$. When a message is sent,
the corresponding receive event is added to the receiver’s queue based on the
value of $\delta$. Clock skew of $\mathcal{E}$ is enforced by ensuring that a
process advances its clock only if it will keep the clocks to be within
$\mathcal{E}$ interval. We also compute the actual value of the maximum clock
skew observed in the simulation to ensure that if $\mathcal{E}=1ms$ then the
worst-case clock skew is indeed $1ms$. For the purposes of the results, we
denote the offset array size as $\tau$ and the counter array size as $\sigma$.

Next, we describe our observations from these simulations.
Specifically, we identify how $\tau$ and $\sigma$ change based on varying
$\alpha,\delta,\mathcal{E}$ and $I$.

###  7.1. Effect of Clock Skew ($\mathcal{E}$)

In this section, we measure the trends in $\mathcal{E}$ while varying the
other parameters to see how the $\tau$ and $\sigma$ are affected. We compare
each parameter pair-wise with $\mathcal{E}$ to see the effect of the parameter
on the clock skew trend with $\tau$.

Varying $I$:  Here, we keep the $\delta$ and $\alpha$ constant to see how
$\tau$ and $\sigma$ change with $\mathcal{E}$. (1) In case of $\tau$ vs
$\mathcal{E}$ curve, we notice that the value of $I$ has little bearing on
$\tau$. As expected, as the value of $\mathcal{E}$ increases, $\tau$ increases
with it. This is true for all values of $\alpha$, and we consistently store
more offsets as $\alpha$ increases. For any given value of $\alpha$, however,
the value of $I$ can be chosen to set the granularity of the user’s choice and
would allow more flexibility in the clock information. Regardless of the
choice of $I$ by the user, the offset sizes increase with roughly the same
trend. These trends are illustrated in Figure 5. (2) In the case of $\sigma$
vs $\mathcal{E}$ curve, we see not too much of a variation in $\sigma$, as
most events reach a different epoch. On average, we do not see many events
storing counters; roughly $0.78\%$ of events store counters, and the values of
such counters do not exceed 5 in most cases. Hence, we would need very little
space to store these counters. These trends are illustrated in Figure 6. Since
this observation is true for all simulations in this paper, we do not discuss
the analysis for $\sigma$ in the subsequent sections.

Since the total size of $RepCl$ depends upon the number of bits for each
offset and the total number of offsets, we consider a specific example here.
For Figure 4, the number of offsets is 2 and the size of each offset is 4
bits. Therefore, one word is sufficient to store offsets. Likewise, one word
is enough for counters. Thus, we need a total of 4 words to store this
timestamp. (Note that the counters can be stored in the same amount of memory
as we have a number of extraneous bits in this representation, specifically in
the max epoch word if we elect to store the sum of all these counters here. By
doing this, we would lose some information, but considering that the number of
events that record meaningful counters is low, this may be an acceptable
trade-off.) It is straightforward to observe that the size of $RepCl$ grows
linearly with the number of offsets in it. And, the total size of $RepCl$ will
require the use of the floor function to identify the number of words
necessary to store it. Since the floor operation loses some of the relevant
data, we present the value of $\tau$ in this section. Graphs that compute the
total size of $RepCl$ are presented in the Appendix.

(a) $n$ = 32.

(b) $n$ = 64.

Figure 6. $\sigma$ vs $\mathcal{E}$ when varying $I$, $\delta$ = 8 $\mu s$,
$\alpha$ = 160 messages/s.

Varying $\delta$:  Here, we fix the $I$ and $\alpha$, and for different
$\delta$ values, and we identify how $\tau$ changes with $\mathcal{E}$. As
$\mathcal{E}$ increases, we see higher values of $\tau$, implying a higher
number of offsets stored on average. We observe that higher values of $\delta$
produce a lower number of offsets in each case, barring some noise. This is
expected as an increase in $\delta$ implies messages would reach in a delayed
fashion, and would lead to processes setting other process offsets to
$\epsilon$ due to non-receipt of messages. As the $\mathcal{E}$ increases, a
process hears from more processes (directly or indirectly) within time
$\mathcal{E}$. Hence, the number of offsets increases. This is illustrated in
Figure 7.

(a) $n$ = 32.

(b) $n$ = 64.

Figure 7. $\tau$ vs $\mathcal{E}$ when varying $\delta$, $I$ = 8 $\mu s$,
$\alpha$ = 40 messages/second.

Varying $\alpha$: Here, we fix the $I$ and $\delta$, and for different
$\alpha$ values, we identify how $\tau$ changes with $\mathcal{E}$. As
expected, for lower values of $\alpha$, we consistently store lower offsets,
as communication between processes is sporadic. As the $\mathcal{E}$
increases, $\tau$ increases linearly until the bound of $n$ is reached. This
is due to the same reason mentioned earlier, as the bound lengths on epochs
are larger, even sporadic messages tend to store more offsets on other
processes, causing the overall value of $\tau$ to increase. This is
illustrated in Figure 8.

(a) $n$ = 32.

(b) $n$ = 64.

Figure 8. $\tau$ vs $\mathcal{E}$ when varying $\alpha$, $I$ = 4 $\mu s$,
$\delta$ = 8 $\mu s$.

###  7.2. Effect of Interval Size ($I$)

In this section, we observe the trends in $I$ with respect to $\delta$ and
$\alpha$.

Varying $\delta$:  Here, we fix the $\mathcal{E}$ and $\alpha$ and check how
$\tau$ changes with $I$. From Figure 9, we observe that the value of $I$ does
not really have a significant effect on $\tau$ (Note that the $Y$ axis of this
figure varies only from $1.2$ to $1.5$.) This means that the selection of $I$
does not affect the number of offsets maintained by a process. However, it
affects the size of each offset. Specifically, the max value of the offset is
$\epsilon=\frac{\mathcal{E}}{I}$ and the number of bits required for each
offset is $\log_{2}\epsilon$. Hence, a larger value of $I$ is better for
reducing the size of the $RepCl$. However, with larger $I$, the guarantees
provided by $RepCl$ are lower. Specifically, Lemma 3 shows that some unforced
reordering may occur when events $e$ and $f$ differ by time $\mathcal{E}+I$.
Users should therefore choose the value of $I$ based on the desired guarantees
of $RepCl$ or the maximum desirable offset.

(a) $n$ = 32.

(b) $n$ = 64.

Figure 9. $\tau$ vs $I$ when varying $\delta$, $\mathcal{E}$ = 2 ms, $\alpha$
= 20 messages/s.

Varying $\alpha$: For every point in the $I-\tau$ trend, lower $\alpha$ values
produce lower $\tau$. This is consistent with our observations so far as
communication is infrequent and processes tend to not hear from other
processes, subsequently not storing their offsets. As $I$ increases, we see
this property respected, and $\tau$ increasing consistently. This is
illustrated in Figure 10.

(a) $n$ = 32.

(b) $n$ = 64.

Figure 10. $\tau$ vs $I$ when varying $\alpha$, $\mathcal{E}$ = 2 ms, $\delta$
= 8 $\mu s$.

###  7.3. Effect of Message Delay ($\delta$)

In this section, we observe the effect of $\delta$ on $\tau$ while fixing
$\mathcal{E}$ and $I$. Here, we observe that the value of $\delta$ has minimal
effect on $\tau$. Specifically, as shown in Figure 11, we observe that the
value of $\tau$ increases as the value of $\alpha$ increases. However, for a
fixed value of $\alpha$, the offset size remains the same. This is illustrated
in Figure 11.

(a) $n$ = 32.

(b) $n$ = 64.

Figure 11. $\tau$ vs $\delta$ when varying $\alpha$, $\mathcal{E}$ = 4 ms, $I$
= 16 $\mu s$.

###  7.4. Feasibility Regions

In this section, we review the simulations to define the notion of feasible
regions. As discussed earlier, the goal of $RepCl$ is to enable the replay of
a distributed computation with a small overhead. Here, we consider the case
where the user identifies the expected overhead of $RepCl$ to identify
scenarios under which $RepCl$ can be used to provide a perfect-replay that
meets all the requirements from Section 5. Since the overhead of the counters
remains virtually unchanged, we only focus on the overhead of the number of
offsets, i.e., the value of $\tau$.

For $\tau=8$, the feasibility regions are shown in Figure 12(a). Here, the
blue dots identify the data points where $\tau=8$ is feasible and the red dots
represent the data points where $\tau=8$ is not feasible. The green line
identifies the bounds where $\tau=8$ is feasible. We find that the size of the
feasible region remains fairly unchanged with the value of $n$. However, it
shrinks when the value of $\mathcal{E}$ is increased. This is expected based
on how $\tau$ changes with $\mathcal{E}$.

We note that the feasibility region only identifies the case where perfect-
replay meets all the requirements from Section 3. If the user needs to utilize
$RepCl$ in an infeasible region, the user can obtain partial-replay. To
understand this, consider the case where the actual value of $\mathcal{E}$ is
$4ms$ but the user specifies it to be $2ms$ while constructing $RepCl$. In
this case, if $e$ and $f$ are within $2ms$ then $RepCl$ will allow them to be
replayed in any order. However, if $f$ occurred $3ms$ after $e$ then $e$ will
always be replayed before $f$. We anticipate that even in a system where the
clock skew is $4ms$, the actual clock skew at a given moment is likely to be
smaller than $4ms$. This implies that the forced order between $e$ and $f$
will be quite infrequent. Hence, we anticipate that $RepCl$ will be applicable
even in domains where the system parameters cause it to fall in an infeasible
region.

(a) $\mathcal{E}$ = 1 ms, $n$ = 32, and $\tau$ = 8.

(b) $\mathcal{E}$ = 2 ms, $n$ = 32, and $\tau$ = 8.

(c) $\mathcal{E}$ = 1 ms, $n$ = 64, and $\tau$ = 8.

(d) $\mathcal{E}$ = 2 ms, $n$ = 64, and $\tau$ = 8.

Figure 12. Feasibility regions for alpha and delta settings.

##  8\. Related Work

The notion of a Logical clock (LC) was proposed in 1978 by Leslie Lamport [6]
to trace the ordering of events in a distributed system. LCs do not use
physical time (NTP [8]) and define a causal relation of $hb$ (happens-before),
based on the communication between nodes (logical events). Vector time was
designed independently by multiple researchers [7][2][11], and they proposed
the idea of representing time in a distributed system as a set of
n-dimensional non-negative integer vectors. Vector clock algorithms suggest
that if two events $x$ and $y$ have timestamps $vh$ and $vk$, respectively,
then $x$ happened before $y$then $vh<vk$.

While vector clocks are upper bounded by $O(n)$ complexity in terms of both
time and memory complexity, the different implementations of the past have
tried to reduce this complexity and generate more efficient representations,
with some success. Singhal-Kshemkalyani’s differential technique [11], relied
on piggybacking using the last sent and last update, without updating every
vector clock. This method relies on the assumption that even though the number
of processes is large, only a few key processes in a system would interact
frequently by passing messages. A benefit of this method is that it cuts down
storage overhead at each process to $O(n)$. However, this method doesn’t make
a substantial contribution to reducing the time complexity incurred when
updating the vector clock, as it relies on piggybacking to work. Fowler-
Zwaenepoel’s[3] direct-dependency technique cuts down storage complexity again
by reducing the message size during transmission by transmitting only a scalar
value in the messages. The downside of this method is that it has a high
computational overhead as it has to trace dependencies and update the vector
clock, especially in systems where a few key processes may have a large number
of events. Since all these approaches provide the same functionality as that
of a vector clock, they will all have undesirable replays as identified in
Section 3.

One existing limitation between vector clocks representing logical time and
physical clock synchronization is the difficulty in reconciling one with the
other. To overcome this challenge, Hybrid Logical clocks were introduced by
Kulkarni et al. [5] to capture the causality relationship of a logical clock
with the characteristics of a physical clock embedded into it. Another variant
of the hybrid clock is the Hybrid Vector Clock [12], which, unlike the Hybrid
Logical Clock, is able to provide all possible/potential consistent snapshots
for a given time. However, the HVC suffers from large overheads in execution,
while updating all timestamps in the event of a send or receive. Our work with
Replay Clocks expands on the idea of the Hybrid Vector Clock and provides an
efficient implementation to counteract the large overheads of the HVC.

There has been some work in trace generation using event ordering, but most of
these use the traditional logical/vector clock infrastructure. Dapper [10] is
Google’s tracing software for distributed systems using logical event
ordering. However, the authors mention that Dapper cannot correctly point to
causal history, as it uses annotations in non-standard control primitives,
that may mislead the causality calculations. ShiViz [1] uses VCs in generating
distributed system traces using happens-before relationships. However, since
it uses traditional vector clocks, it uses a higher complexity than our
proposed model.

##  9\. Discussion

In Section 7, we identified feasible regions for the given permissible
overhead for $RepCl$. Thus, the natural question is: what can a user do if the
given system parameters fall into the infeasible region? Here, observe that
$\mathcal{E}$ provides one way to reduce the overhead if we accept some
imperfect replay. To explain this, consider the case where we are using a
system with clock skew to be $\mathcal{E}_{a}$. If the user implements $RepCl$
with $\mathcal{E}<\mathcal{E}_{a}$ then the resulting replay will still
satisfy requirements 1 and 2 (cf. Section 3.2). Requirement 3 will be
satisfied with $\mathcal{E}_{2}=\mathcal{E}-I$.

Figure 13. Effect of using $\mathcal{E}$ instead of $\mathcal{E}_{a}$ in
$RepCl$.

Looking at this situation closely, we observe that the clock skew between two
processes follows a structure shown in Figure 13. Specifically, at a given
instance, the clocks of two processes $j$ and $k$ differ by some amount that
is less than $\mathcal{E}_{a}$. However, the actual clock difference at a
fixed point in time (that is not visible to either $j$ and $k$) is often less
than $\mathcal{E}_{a}$. Hence, if $e$ and $f$ occurred at the same global
time, the probability that the respective clocks differed by $\mathcal{E}$
depends upon the area of the shaded part (cf. Figure 13). In this case, $e$
and $f$ would still be replayed in arbitrary order. Only if the clocks fall in
the non-shaded area then the replay will force an order between $e$ and $f$.
In other words, even if the system parameters fall in the infeasible region,
it would be possible to use $RepCl$ that provides a valid replay. It is just
that it will not be able to reproduce all possible replays.

##  10\. Conclusion and Future Work

In this paper, we focused on the problem of replay clocks in systems where
clocks are synchronized to be within $\mathcal{E}$. The purpose of these
clocks is to reproduce a distributed computation with all its certainties and
uncertainties. By certainty, we mean that if event $e$ must have happened
before $f$ then the replay must ensure that $e$ is replayed before $f$.
Specifically, this required that if $e$ happened before $f$ (as defined in
[6]) or $f$ occurred $\mathcal{E}_{1}\approx\mathcal{E}$ time after $e$ then
$e$ must occur before $f$. And, by uncertainty, we mean that if $e$ and $f$
could occur in any order then the replay should not force an order between
them. Specifically, if $e||f$ (as defined in [6]) and $e$ and $f$ occurred
within time $\mathcal{E}_{2}\approx\mathcal{E}$ then the replay permits them
to be replayed in any order.

We presented $RepCl$ to solve the replay problem with
$\mathcal{E}_{1}=\mathcal{E}+I$ and $\mathcal{E}_{2}=\mathcal{E}-I$, where $I$
is a parameter to $RepCl$. We analyzed $RepCl$ for various system parameters
(clock skew ($\mathcal{E}$), message rate ($\alpha$), message delay
($\delta$)). We find that for various system parameters, the size of $RepCl$
and the overhead to create timestamps and/or compare them is small.

For the purpose of replay, $RepCl$ provides several advantages over existing
approaches. For example, unlike logical clocks, they do not force certain
unneeded event ordering. They have a significantly lower overhead compared to
vector clocks. Also, they do not generate illegitimate replays that can occur
with the user of vector clocks.

The overhead of $RepCl.j$ depends upon the number of processes that
communicate with $j$ (directly or indirectly) in $\mathcal{E}$ window. This is
different from the case in vector clocks where the overhead is always
proportional to the number of processes in the system.

We have utilized $RepCl$ to enable users to visualize a distributed
computation (cf. Appendix). The goal of the visualization is to allow the user
to identify an event $f$ where a failure occurred. Then, they can use a replay
of events just preceding $f$ to determine whether the error would go away. If
it does, it would imply that it is a synchronization error. Likewise, a user
can replay some portion of the computation. Since the replay of events may
occur in a different order, it will help identify potential synchronization
errors.

$RepCl$ is designed mainly for offline analysis, where the event data is
stored during execution and analyzed at a later time. However, $RepCl$ can be
used for run-time monitoring/analysis as well if the data related to the
timestamps is sent to a monitor, that monitor could analyze it for potential
properties of interest if the analysis can be done quickly. However, a key
challenge in this context will be whether the run-time monitors can keep up
with the execution of the system.

There are several future directions for $RepCl$. If the size of $RepCl$ needed
for perfect replay is too large, the user can reduce the size of $RepCl$ by
choosing a lower value of $\mathcal{E}$. In this case, the resulting replay
will force some ordering between concurrent events. One of the future works is
to identify the effect of reducing $\mathcal{E}$ in this manner. Another
future work is to build a robust API for $RepCl$ that will simplify its use in
practice.

## References

  * [1] Ivan Beschastnikh, Patty Wang, Yuriy Brun, and Michael D Ernst.  Debugging distributed systems.  Communications of the ACM, 59(8):32–37, 2016.
  * [2] Colin J Fidge.  Timestamps in message-passing systems that preserve the partial ordering.  In Kerry Raymond, editor, Proceedings of the 11th Australian Computer Science Conference (ACSC), pages 56–66, 1988.
  * [3] Jerry Fowler and Willy Zwaenepoel.  Causal distributed breakpoints.  Proceedings.,10th International Conference on Distributed Computing Systems, pages 134–141, 1990.
  * [4] Sandeep S Kulkarni, Gabe Appleton, and Duong Nguyen.  Achieving causality with physical clocks.  In Proceedings of the 23rd International Conference on Distributed Computing and Networking, ICDCN ’22, page 97–106, New York, NY, USA, 2022. Association for Computing Machinery.
  * [5] Sandeep S Kulkarni, Murat Demirbas, Deepak Madappa, Bharadwaj Avva, and Marcelo Leone.  Logical physical clocks.  In Principles of Distributed Systems: 18th International Conference, OPODIS 2014, Cortina d’Ampezzo, Italy, December 16-19, 2014. Proceedings 18, pages 17–32. Springer, 2014.
  * [6] Leslie Lamport.  Time, clocks, and the ordering of events in a distributed system.  Commun. ACM, 21(7):558–565, July 1978.
  * [7] Friedemann Mattern et al.  Virtual time and global states of distributed systems.  Univ., Department of Computer Science, 1988.
  * [8] D. L. Mills.  Network time protocol (ntp).  RFC 958, RFC Editor, September 1985.
  * [9] David L Mills.  Internet time synchronization: the network time protocol.  IEEE Transactions on communications, 39(10):1482–1493, 1991.
  * [10] Benjamin H Sigelman, Luiz André Barroso, Mike Burrows, Pat Stephenson, Manoj Plakal, Donald Beaver, Saul Jaspan, and Chandan Shanbhag.  Dapper, a large-scale distributed systems tracing infrastructure.  2010\.
  * [11] Mukesh Singhal and Ajay D. Kshemkalyani.  An efficient implementation of vector clocks.  Inf. Process. Lett., 43(1):47–52, 1992.
  * [12] Sorrachai Yingchareonthawornchai, Duong N Nguyen, Sandeep S Kulkarni, and Murat Demirbas.  Analysis of bounds on hybrid vector clocks.  IEEE Transactions on Parallel and Distributed Systems, 29(9):1947–1960, 2018.

##  Appendix A Application of RepCl

In this section, we discuss an application of $RepCl$ so as to visualize a
given computation. This visualization is intended for the case where the user
observes that there is an error in the program. Let $f$ denote the event where
the error was observed. Now, the user can utilize $RepCl$ and visualize the
events in the immediate past of $f$. The user can also replay the events in
the recent past of $f$ to determine if the error goes away. If the error is
caused by a lack of synchronization, it will allow the user to identify the
missing synchronization either via visualization or via identifying all
possible replays that are possible in the given computation. A sample
visualization trace is shown in Figure 14 in Appendix. It can also be replayed
using the Algorithm in Section 3. This algorithm chooses one of the FrontLine
events at random. Allowing the user to select these events provides the
ability to the user to evaluate ‘what-if’ scenarios to reduce the number of
replays.

Figure 14. Sample API example of output traces with swimlanes in
visualization.

##  Appendix B Clock Size

Following from Section 7, we present Figure 15 as an extension to Figure 5.
Here, we replace the $Y$-axis of $\tau$ with the actual size of the clock in
words. This relation is a linear transformation and produces the same trends
observed in Figure 5. Following our discussion about the size of the clock in
Section 6, the clock size for most cases is between 2 to 4 words for our most
efficient configurations. This would reduce even further with choices to
represent the sum of counters in the extraneous bits of the epoch store, as we
do not lose as much information in most cases.

(a) $\alpha$ = 20 messages/s, $n$ = 32.

(b) $\alpha$ = 40 messages/s, $n$ = 32.

(c) $\alpha$ = 160 messages/s, $n$ = 32.

(d) $\alpha$ = 20 messages/s, $n$ = 64.

(e) $\alpha$ = 40 messages/s, $n$= 64.

(f) $\alpha$ = 160 messages/s, $n$ = 64.

Figure 15. Clock Size vs $\mathcal{E}$ when varying $I$, $\delta=8\mu s$.