From 1a70923f0c82acd77ced5105b9e1097209befdf9 Mon Sep 17 00:00:00 2001 From: rtrimana Date: Fri, 5 Aug 2016 16:40:25 -0700 Subject: [PATCH] Reconciling pseudocode and formal guarantees - part 1 --- doc/iotcloud.tex | 259 +++++++++++++++++++++++++++++++++-------------- 1 file changed, 185 insertions(+), 74 deletions(-) diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex index 0e27bbf..bffd87e 100644 --- a/doc/iotcloud.tex +++ b/doc/iotcloud.tex @@ -836,10 +836,10 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge A message $\mathsf{t}$, is the tuple \begin{center} $\mathsf{t = \tuple{s, E(Dat_s)}}$ \\ -$\mathsf{Dat_s = \tuple{s,id,hmac_p, DE,hmac_c}}$ +$\mathsf{Dat_t = \tuple{s,id,hmac_p, DE,hmac_c}}$ \end{center} -containing $\mathsf{s}$ as sequence number and $\mathsf{Dat_s}$ as its -encrypted contents. $\mathsf{Dat_s}$ consists of $\mathsf{s}$, +containing $\mathsf{s}$ as sequence number and $\mathsf{Dat_t}$ as its +encrypted contents. $\mathsf{Dat_t}$ consists of $\mathsf{s}$, $\mathsf{id}$ as machine ID of the sender, $\mathsf{hmac_p}$ as HMAC from a previous message, $\mathsf{DE}$ as set of data entries, and $\mathsf{hmac_c}$ as HMAC from message $\mathsf{t}$ respectively. @@ -847,20 +847,20 @@ $\mathsf{hmac_c}$ as HMAC from message $\mathsf{t}$ respectively. \begin{defn}[Equality] Two messages $\mathsf{t}$ and $\mathsf{u}$ are equal if their $\mathsf{s}$, -and $\mathsf{Dat_s}$ are exactly the same. +and $\mathsf{Dat_t}$ are exactly the same. \end{defn} \begin{defn}[Parent] -A parent of a message $\mathsf{t}$ is the message $\mathsf{A(t)}$, unique -by the correctness of HMACs in $\mathsf{Dat_s}$, such that -$\mathsf{hmac_p(t) = hmac_c(A(t))}$. +A parent of a message $\mathsf{t}$ is the message $\mathsf{\mathscr{P}_t}$, +unique by the correctness of HMACs in $\mathsf{Dat_t}$, such that +$\mathsf{hmac_p(t) = hmac_c(\mathscr{P}_t)}$. \end{defn} \begin{defn}[Chain] A chain of messages with length $\mathsf{n \ge 1}$ is a message sequence -$\mathsf{R = (r_i, r_{i+1}, ..., r_{i+n-1})}$ such that for every index -$\mathsf{i < k \le i+n-1}$, $\mathsf{r_k}$ has sequence number $\mathsf{k}$ -and is the parent of $\mathsf{r_{k-1}}$. +$\mathsf{R = (r_s, r_{s+1}, ..., r_{s+n-1})}$ such that for every sequence +number $\mathsf{s < k \le s+n-1}$, $\mathsf{r_k}$ has sequence number +$\mathsf{k}$ and is the parent of $\mathsf{r_{k-1}}$. \end{defn} \begin{defn}[Partial sequence] @@ -870,11 +870,11 @@ with the same sequence number, that can be divided into disjoint chains. \begin{defn}[Total sequence] A total sequence $\mathsf{T =}$ $\mathsf{(t_1, t_2, ..., t_n)}$ with -length $\mathsf{n}$ is a chain of messages that starts at $\mathsf{i = 1}$. +length $\mathsf{n}$ is a chain of messages that starts at $\mathsf{s = 1}$. \end{defn} \begin{defn}[Path] -The path of a message $\mathsf{t}$ is the chain that starts at $\mathsf{i = 1}$ +The path of a message $\mathsf{t}$ is the chain that starts at $\mathsf{s = 1}$ and whose last message is $\mathsf{t}$. The uniqueness of a path follows from the uniqueness of a parent. \end{defn} @@ -882,89 +882,163 @@ from the uniqueness of a parent. \begin{defn}[Consistency] A partial sequence $\mathsf{P}$ is consistent with a total sequence $\mathsf{T}$ of length $\mathsf{n}$ if for every message $\mathsf{p \in P}$ -with $\mathsf{i(p) \leq n}$, $\mathsf{t_{i(p)} = p}$. This implies that -$\mathsf{\{p \in P | i(p) \le n\}}$ is a partial sequence of $\mathsf{T}$. +with $\mathsf{s_p \leq n}$, $\mathsf{t_{s_p} = p}$. This implies that +$\mathsf{\{p \in P | s_p \le n\}}$ is a partial sequence of $\mathsf{T}$. \end{defn} \begin{defn}[Transitive closure] -Transitive closure set at index $\mathsf{n}$ is a set $\mathscr{S}$ of -clients comprising a connected component of an undirected graph, where two -clients are connected by an edge if they both received the same message -$\mathsf{t}$ with index $\mathsf{i(t) > n}$. +Transitive closure set at sequence number $\mathsf{s_n}$ is a set +$\mathsf{\mathscr{S}}$ of clients comprising a connected component of an +undirected graph, where two clients are connected by an edge if they both +received the same message $\mathsf{t}$ with sequence number $\mathsf{s_t > n}$. \end{defn} -%\begin{enumerate} -%\item Equality: Two messages $t$ and $u$ are equal if their sequence numbers, senders, and contents are exactly the same. -%\item Message: A message $t$, is the tuple $t = (i(t), s(t), contents(t))$ containing the sequence number, machine ID of the sender, and contents of $t$ respectively. -%\item Parent: A parent of a message $t$ is the message $A(t)$, unique by the correctness of HMACs, such that $HMAC_C(t) = HMAC_P(A(t))$. -%\item Chain: A chain of messages with length $n \ge 1$ is a message sequence $R = (R_i, R_{i+1}, ..., R_{i+n-1})$ such that for every index $i < k \le i+n-1$, $R_k$ has sequence number $k$ and is the parent of $R_{k-1}$. -%\item Partial message sequence: A partial message sequence is a sequence of messages, no two with the same sequence number, that can be divided into disjoint chains. -%\item Total message sequence: A total message sequence $T$ with length $n$ is a chain of messages that starts at $i = 1$. -%\item Path: The path of a message $t$ is the chain that starts at $i = 1$ and whose last message is $t$. The uniqueness of a path follows from the uniqueness of a parent. -%\item Consistency: A partial message sequence $P$ is consistent with a total message sequence $T$ of length $n$ if for every message $p \in P$ with $i(p) < n$, $T_{i(p)} = p$. This implies that $\{p \in P | i(p) \le n\}$ is a subsequence of T. -%\item Transitive closure set at index $n$: A set $\mathscr{S}$ of clients comprising a connected component of an undirected graph, where two clients are connected by an edge if they both received the same message $t$ with index $i(t) > n$. -%\end{enumerate} - \subsubsection{Lemmas and Proofs} -\begin{prop} Every client $J$ who sends a message $t$ has $A(t)$ as its latest stored message, and $i(t) = i(A(t)) + 1$. \end{prop} -\begin{proof} True by definition, because $J$ sets $HMAC_P(t) = HMAC_C(A(t))$ and $i(t) = i(A(t)) + 1$ when a message is sent. \end{proof} +\begin{prop} +Every client $\mathsf{J}$ who sends a message $\mathsf{t}$ +has $\mathsf{\mathscr{P}_t}$ as its latest stored message, and +$\mathsf{s_t = s_{\mathscr{P}_t} + 1}$. +\end{prop} +\begin{proof} True by definition, because $J$ sets +$\mathsf{hmac_p(t) = hmac_c(\mathscr{P}_t)}$ and +$\mathsf{s_t = }$ $\mathsf{s_{\mathscr{P}_t + 1}}$ when a message +is sent. +\end{proof} -\begin{prop} If a rejected message entry is added to the RML at index $i$, the message will remain in the RML until every client has seen it. \end{prop} -\begin{proof} Every RML entry $e$ remains in the queue until it reaches the tail, and is refreshed by the next sender $J$ at that time if $min(MS) > i(e)$; that is, until every client has sent a message with sequence number greater than $i(e)$. Because every client who sends a message with index $i$ has the state of the queue at $i - 1$, this client will have seen the message at $i(e)$. \end{proof} +\begin{prop} If a rejected message entry is added to the set $\mathsf{CR}$ +at sequence number $\mathsf{s}$, the message will remain in $\mathsf{CR}$ +until every client has seen it. +\end{prop} +\begin{proof} Every $\mathsf{CR}$ entry $\mathsf{cr}$ remains in the queue until it +reaches the tail, and is refreshed by the next sender $\mathsf{J}$ at that time if +$\mathsf{min(MS) > s_{cr}}$; that is, until every client has sent a message with +sequence number greater than $\mathsf{s_{cr}}$. Because every client who sends a +message with sequence number $\mathsf{s}$ has the state of the set $\mathsf{SL}$ at +$\mathsf{s - 1}$, this client will have seen the message at $\mathsf{s_{cr}}$. +\end{proof} \begin{figure}[h] \centering - \xymatrix{ & & S \\ -\dots \ar[r] & q \ar[dr]_{J} \ar[r]^{K} & S_1 \ar[r] & S_2 \ar[r] & \dots \ar[r] & p \ar[r] & \dots \ar[r] & S_n = u \\ -& & R_1 \ar[r] & R_2 \ar[r] & \dots \ar[r] & R_m = t \\ + \xymatrix{ & & L \\ +\dots \ar[r] & q \ar[dr]_{J} \ar[r]^{K} & l_1 \ar[r] & l_2 \ar[r] & \dots \ar[r] & p \ar[r] & \dots \ar[r] & l_n = u \\ +& & r_1 \ar[r] & r_2 \ar[r] & \dots \ar[r] & r_m = t \\ & & R \save "2,3"."2,8"*+\frm{^\}} \save "3,3"."3,6"*+\frm{_\}} \restore \restore } -\caption{By Lemma 1, receiving $u$ after $t$ is impossible.} +\caption{By Lemma 1, receiving $t$ after $u$ is impossible.} \end{figure} -\begin{lem} Two messages are received without errors by a client $C$; call them $t$ and $u$ such that $i(t) \le i(u)$. Then $t$ is in the path of $u$. \end{lem} +\begin{lem} Two messages are received without errors by a client $\mathsf{C}$; +call them $\mathsf{t}$ and $\mathsf{u}$ such that $\mathsf{s_t \le s_u}$. +Then $\mathsf{t}$ is in the path of $\mathsf{u}$. +\end{lem} \begin{proof} -Clearly $C$ will throw an error if $i(t) = i(u)$. So $i(t) < i(u)$. Additionally, if $C$ receives $u$ before $t$, this will cause it to throw an error, so $t$ is received before $u$. - -Assume that $t$ is not in the path of $u$. Take $u$ to be the packet of smallest index for which this occurs, and $t$ be the packet with greatest index for this $u$. We will prove that an error occurs upon receipt of $u$. - -Let $R_1$ be the earliest member of the path of $t$ that is not in the path of $u$, and $q$ be its parent. $q$, the last common ancestor of $t$ and $u$, must exist, since all clients and the server were initialized with the same state. Let $S_1$ be the successor of $q$ that is in the path of $u$; we know $S_1 \neq R_1$. Let $R = (R_1, R_2, \dots, R_m = t)$ be the distinct portion of the path of $t$, and similarly let $S$ be the distinct portion of the path of $S_n = u$. - -Let $J$ be the client who sent $R_1$; that is, such that ${id_self}_J = GetMacID(R_1)$, and $K$ be the client who sent $S_1$. +Clearly $\mathsf{C}$ will throw an error if $\mathsf{s_t = s_u}$. So +$\mathsf{s_t < s_u}$. Additionally, if $\mathsf{C}$ receives $\mathsf{u}$ before +$\mathsf{t}$, this will cause it to throw an error, so $\mathsf{t}$ is received +before $\mathsf{u}$. + +Assume that $\mathsf{t}$ is not in the path of $\mathsf{u}$. Take $\mathsf{u}$ +to be the packet of smallest sequence number for which this occurs, and +$\mathsf{t}$ be the packet with greatest sequence number for this $\mathsf{u}$. +We will prove that an error occurs upon receipt of $\mathsf{u}$. + +Let $\mathsf{r_1}$ be the earliest member of the path of $\mathsf{t}$ that is +not in the path of $\mathsf{u}$, and $\mathsf{q}$ be its parent. Message +$\mathsf{q}$, the last common ancestor of $\mathsf{t}$ and $\mathsf{u}$, must exist, +since all clients and the server were initialized with the same state. Let +$\mathsf{l_1}$ be the successor of $\mathsf{q}$ that is in the path of $\mathsf{u}$; +we know $\mathsf{l_1 \neq r_1}$. Let $\mathsf{R = (r_1, r_2, \dots, r_m = t)}$ be +the distinct portion of the path of $\mathsf{t}$, and similarly let $\mathsf{L}$ +be the distinct portion of the path of $\mathsf{l_n = u}$. + +Let $\mathsf{J}$ be the client who sent $\mathsf{r_1}$; that is, such that +$\mathsf{{id_{self}}_J = GetMacID(r_1)}$, and $\mathsf{K}$ be the client who +sent $\mathsf{l_1}$. We know the following three facts: \begin{enumerate} -\item Because no client can send two messages with the same index, and $i(R_1) = i(S_1) = i(q) + 1$, $J \neq K$. +\item Because no client can send two messages with the same sequence number, and +$\mathsf{s_{r_1} = s_{l_1} = s_q + 1}$, $\mathsf{J \neq K}$. -\item To send a message $p$ that is the parent of some other message, one must have the received the parent of $p$. Since $u$ is the message with smallest sequence number received by any client that violate this lemma, no client receives both a message in $R$ and a message in $S$; therefore, no client sends both a message in $(R_2,...,t)$ and a message in $(S_2,...,u)$. +\item To send a message $\mathsf{p}$ that is the parent of some other +message, one must have received the parent of $\mathsf{p}$. Since +$\mathsf{u}$ is the message with smallest sequence number received by any +client that violates this lemma, no client receives both a message in $\mathsf{r}$ +and a message in $\mathsf{l}$; therefore, no client sends both a message in +$\mathsf{(r_2,...,t)}$ and a message in $\mathsf{(l_2,...,u)}$. -\item Since $u$ are the greatest- and least- sequence number messages that violate this lemma, $C$ does not receive any message with sequence number strictly between $i(t)$ and $i(u)$. Because the $s_{last}$ that $C$ stores increases at every message receipt event, $C$ also does not receive any message after $t$ and before $u$ in real time. +\item Since $\mathsf{u}$ is the message with the greatest- and least- sequence +number that violates this lemma, $\mathsf{C}$ does not receive any message with +sequence number strictly between $\mathsf{s_t}$ and $\mathsf{s_u}$. Because the +$\mathsf{s_{last}}$ that $\mathsf{C}$ stores increases at every message receipt +event, $\mathsf{C}$ also does not receive any message after $\mathsf{t}$ and before +$\mathsf{u}$ in real time. \end{enumerate} - There are two cases: - \begin{itemize} -\item Case 1: $J$ did not send a message in $S$. Then $v_J(t) > v_J(q) = v_J(u)$. +\item Case 1: $\mathsf{J}$ did not send a message in $\mathsf{L}$. Then +%$\mathsf{v_J(t) > v_J(q) = v_J(u)}$. +$\mathsf{s_{t_J} > s_{q_J} = s_{u_J}}$. \begin{itemize} -\item Case 1.1: $C$ never updates its slot sequence list between receiving $t$ and receiving $u$; this can only happen if $i(t) = i(u) - 1$. Since $t$ is not the parent of $u$, $HMAC_p(u) \neq HMAC_c(t)$, causing $C$ to error. -\item Case 1.2: Case 1.1 does not occur; therefore, $C$ must update its slot sequence list at some point between receiving $t$ and $u$. The latest index of $J$ decreases during this time, which means it must decrease when some message is received, which means C throws an error in the $CheckLastSeqN$ subroutine. +\item Case 1.1: $\mathsf{C}$ never updates its slot sequence list $\mathsf{SS}$ +between receiving $\mathsf{t}$ and receiving $\mathsf{u}$; this can only happen if +$\mathsf{s_t = s_u - 1}$. Since $\mathsf{t}$ is not the parent of $\mathsf{u}$, +$\mathsf{hmac_p(u) \neq hmac_c(t)}$, causing $\mathsf{C}$ to error. +\item Case 1.2: Case 1.1 does not occur; therefore, $\mathsf{C}$ must update +its slot sequence list $\mathsf{SS}$ at some point between receiving $\mathsf{t}$ +and $\mathsf{u}$. +The latest sequence number of $\mathsf{J}$ decreases during this time, which +means it must decrease when some message is received, which means $\mathsf{C}$ +throws an error in the $\mathsf{CheckLastSeqN}$ subroutine. \end{itemize} -\item Case 2: $J$ sent at least one message in $S$. Call the first one $p$. We know that $i(p) > i(R_1)$, since $J \neq K$ and $p \neq S_1$. $R_1$ must be sent either before or after $p$. +\item Case 2: $\mathsf{J}$ sent at least one message in $\mathsf{L}$. Call the +first one $\mathsf{p}$. We know that $\mathsf{s_p > s_{r_1}}$, since +$\mathsf{J \neq K}$ and $\mathsf{p \neq l_1}$. Message $\mathsf{r_1}$ must be sent +either before or after $\mathsf{p}$. \begin{itemize} -\item Case 2.1: Client $J$ sends $p$, and then $R_1$. Before sending $p$, the greatest sequence number of a message that $J$ has received, ${s_{last}}_j$, must be equal to $i(p) - 1 \ge i(R_1)$. Since ${s_{last}}_j$ never decreases, Client $J$ cannot then send a message with sequence number $i(R_1)$, a contradiction. -\item Case 2.2: Client $J$ sends $R_1$, and then $p$. Let $X = (R_1, \dots )$ be the list of messages $J$ sends starting before $R_1$ and ending before $p$. +\item Case 2.1: Client $\mathsf{J}$ sends $\mathsf{p}$, and then $\mathsf{r_1}$. +Before sending $\mathsf{p}$, the greatest sequence number of a message that +$\mathsf{J}$ has received, $\mathsf{{s_{last}}_J}$, must be equal to +$\mathsf{s_p - 1 \ge s_{r_1}}$. Since $\mathsf{{s_{last}}_J}$ never decreases, +client $\mathsf{J}$ cannot then send a message with sequence number +$\mathsf{s_{r_1}}$, a contradiction. +\item Case 2.2: Client $\mathsf{J}$ sends $\mathsf{r_1}$, and then $\mathsf{p}$. +Let $\mathsf{X = (r_1, \dots )}$ be the list of messages $\mathsf{J}$ sends +starting before $\mathsf{r_1}$ and ending before $p$. \begin{itemize} -\item Case 2.2.1: Some message in $X$ was accepted. Let $v_J(w)$ be the greatest sequence number of the messages that client $J$ sent in the path of message $w$. In this case, before sending $p$, $J$'s value $SM_J[J]$ for its own latest index would be strictly greater than $v_J(q)$. If there is a sequence of messages with contiguous sequence numbers that $J$ receives between $R_1$ and $p$, J throws an error for a similar reason as Case 1.1. Otherwise, when preparing to send $p$, $J$ would have received an update of its own latest index as at most $v_J(q)$. $J$ throws an error before sending $p$, because its own latest index decreases. -\item Case 2.2.2: All messages in $X$ were rejected, making $p$ the first message of $J$ that is accepted after $R_1$. Note that $u$ is the message with least sequence number that violates this lemma, and therefore the first one that $C$ receives after $t$. Therefore, $C$ could not have seen a message after $t$ with index less than $i(p)$. In the $PutDataEntries$ subroutine, $J$ adds every rejected message to $CR(P)$; so for every $i$, $1 \leq i < |X|$, the $i$th element of $X$ will be recorded in the RML of all further elements of $X$; and every element of $X$ will be recorded in $CR_C(p)$. Since every rejected message in $CR(p)$ will be in $CR_C(u)$, $R_1$ will be recorded in $CR_C(p)$. When $C$ receives $u$, $C$ will throw an error from the match $(J, i(q)+1)$ in $CR_C(p)$. +\item Case 2.2.1: Some message in $\mathsf{X}$ was accepted. Let $\mathsf{s_{w_J}}$ +be the greatest sequence number of the messages that client $\mathsf{J}$ sent in +the path of message $\mathsf{w}$. In this case, before sending $\mathsf{p}$, +$\mathsf{J}$'s value in $\mathsf{SM_J}$ for its own latest sequence number would +be strictly greater than $\mathsf{s_{q_J}}$. If there is a sequence of messages with +contiguous sequence numbers that $\mathsf{J}$ receives between $\mathsf{r_1}$ and +$\mathsf{p}$, $\mathsf{J}$ throws an error for a similar reason as Case 1.1. Otherwise, +when preparing to send $\mathsf{p}$, $\mathsf{J}$ would have received an update of its +own latest sequence number as at most $\mathsf{s_{q_J}}$. $J$ throws an error before +sending $\mathsf{p}$, because its own latest sequence number decreases. +\item Case 2.2.2: All messages in $\mathsf{X}$ were rejected, making $\mathsf{p}$ +the first message of $\mathsf{J}$ that is accepted after $\mathsf{r_1}$. Note that +$\mathsf{u}$ is the message with least sequence number that violates this lemma, and +therefore the first one that $\mathsf{C}$ receives after $\mathsf{t}$. Therefore, +$\mathsf{C}$ could not have seen a message after $\mathsf{t}$ with sequence number less +than $\mathsf{s_p}$. In the $\mathsf{PutDataEntries}$ subroutine, $\mathsf{J}$ adds every +%TODO: Check with Thomas about this part +rejected message to $\mathsf{CR(p)}$; so for every $\mathsf{s}$, $\mathsf{1 \leq s < |X|}$, +the $\mathsf{s}$-th element of $\mathsf{X}$ will be recorded in the rejected message list +$\mathsf{CR}$ of all further elements of $\mathsf{X}$; and every element of +$\mathsf{X}$ will be recorded in $\mathsf{CR_C(p)}$. Since every rejected message in +$\mathsf{CR(p)}$ will be in $\mathsf{CR_C(u)}$, ${r_1}$ will be recorded in +$\mathsf{CR_C(p)}$. When $\mathsf{C}$ receives $\mathsf{u}$, $\mathsf{C}$ will throw +an error from the match $\mathsf{\tuple{s_q+1, id_J}}$ in $\mathsf{CR_C(p)}$. \item Case 2.2.2.1: \end{itemize} \end{itemize} @@ -972,30 +1046,67 @@ There are two cases: \end{itemize} \end{proof} -\begin{lem} If there are two packets $t$ and $u$, with $i(t) <= i(u)$, such that $t$ is in the path of $u$, then for any message $p$ with $i(p) <= i(t)$, iff $p$ is in the path of $t$, it is in the path of $u$. \end{lem} +\begin{lem} If there are two packets $\mathsf{t}$ and $\mathsf{u}$, with +$\mathsf{s_t \leq s_u}$, such that $\mathsf{t}$ is in the path of $\mathsf{u}$, +then for any message $\mathsf{p}$ with $\mathsf{s_p \leq s_t}$, iff $\mathsf{p}$ is in +the path of $\mathsf{t}$, it is in the path of $\mathsf{u}$. +\end{lem} \begin{proof} -If $i(t) = i(u)$ or $i(p) = i(t)$, then we are done, because the two relevant messages are the same. - -Reverse direction: The definition of $t$ being in the path of $u$ is the existence of a message sequence $(..., t, ..., u)$ such that each message except $u$ is the parent of the succeeding message. The path of $u$ must contain some message with index $i(p)$; because $p$ is in the path of $u$, this message is $p$ itself. The path of $t$ is then the prefix of this path ending at $t$, which clearly contains $p$. - -Forward direction: The path of $t$ is a substring of the path of $u$, so if the path of $t$ contains $p$, so does the path of $u$. +If $\mathsf{s_t = s_u}$ or $\mathsf{s_p = s_t}$, then we are done, because the two +relevant messages are the same. If they are different messages, then: +\begin{itemize} +\item Reverse direction: The definition of $\mathsf{t}$ being in the path of +$\mathsf{u}$ is the existence of a message sequence $\mathsf{(\dots, t, \dots, u)}$ +such that each message except $\mathsf{u}$ is the parent of the succeeding message. +The path of $\mathsf{u}$ must contain some message with sequence number $\mathsf{s_p}$; +because $\mathsf{p}$ is in the path of $\mathsf{u}$, this message is $\mathsf{p}$ +itself. The path of $\mathsf{t}$ is then the prefix of this path ending at $\mathsf{t}$, +which clearly contains $\mathsf{p}$. + +\item Forward direction: The path of $\mathsf{t}$ is a substring of the path of +$\mathsf{u}$, so if the path of $\mathsf{t}$ contains $\mathsf{p}$, so does the path +of $\mathsf{u}$. +\end{itemize} \end{proof} \begin{theorem} -Suppose that there is a transitive closure set $\mathscr{S}$ of clients, at index $n$. Then there is some total sequence $T$ of length $n$ such that every client $C$ in $\mathscr{S}$ sees a partial sequence $P_C$ consistent with $T$. \end{theorem} +Suppose that there is a transitive closure set $\mathsf{\mathscr{S}}$ of clients, +at sequence number $\mathsf{s_n}$. Then there is some total sequence $\mathsf{T}$ of +length $\mathsf{n}$ such that every client $\mathsf{C}$ in $\mathsf{\mathscr{S}}$ +sees a partial sequence $\mathsf{P_C}$ consistent with $\mathsf{T}$. +\end{theorem} \begin{proof} -The definition of consistency of $P_C$ with $T$ is that every message $p \in P_C$ with index $i(p) \le n$ is equal to the message in that slot in $T$. Let $C_1$ be some client in the transitive closure set, with partial sequence $P_{C_1}$, and let $u$ be some message with $i(u) > n$ that $C_1$ shares with another client. Then let $T$ be the portion of the path of $u$ ending at index $n$ and $t$ be the message at that index. Clearly, by Lemma 1, $P_{C_1}$ is consistent with $T$. We will show that, for every other client $D$ with partial sequence $P_D$, $P_D$ has some message whose path includes $t$. Because $D$ is in the transitive closure, there is a sequence of clients $\mathscr{C} = (C_1, C_2, ..., D)$ from $C_1$ to $D$, where each shares an edge with the next. - -We prove by induction that $P_D$ has a message whose path includes $t$. +The definition of consistency of $\mathsf{P_C}$ with $\mathsf{T}$ is that every message +$\mathsf{p \in P_C}$ with sequence number $\mathsf{s_p \le s_n}$ is equal to the message +in that slot in $\mathsf{T}$. Let $\mathsf{C_1}$ be some client in the transitive closure +set, with partial sequence $\mathsf{P_{C_1}}$, and let $\mathsf{u}$ be some message with +$\mathsf{s_u > s_n}$ that $\mathsf{C_1}$ shares with another client. Then let $\mathsf{T}$ +be the portion of the path of $\mathsf{u}$ ending at sequence number $\mathsf{s_n}$ and +$\mathsf{t}$ be the message at that sequence number. Clearly, by Lemma 1, $\mathsf{P_{C_1}}$ +is consistent with $\mathsf{T}$. We will show that, for every other client $\mathsf{D}$ +with partial sequence $\mathsf{P_D}$, $\mathsf{P_D}$ has some message whose path includes +$\mathsf{t}$. Because $\mathsf{D}$ is in the transitive closure, there is a sequence of +clients $\mathsf{\mathscr{C} = (C_1, C_2, ..., D)}$ from $\mathsf{C_1}$ to $\mathsf{D}$, +where each shares an edge with the next. +We prove by induction that $\mathsf{P_D}$ has a message whose path includes $\mathsf{t}$. \begin{itemize} -\item Base case: $P_{C_1}$ includes $u$, whose path includes $t$. - -\item Inductive step: Each client in $\mathscr{C}$ has a partial sequence with a message that includes $t$ if the previous client does. Suppose $P_{C_k}$ has a message $w$ with a path that includes $t$, and shares message $x$ with $P_{C_{k+1}}$ such that $i(x) > n$. By Lemma 1, $w$ or $x$, whichever has the least sequence number, is in the path of the other, and therefore by Lemma 2, $t$ is in the path of $x$. - -\item Let $z$ be the message of $D$ whose path includes $t$. By Lemma 1, every message in $P_D$ with index smaller than $i(w)$ is in the path of $z$. Since $t$ is in the path of $z$, every message in $P_D$ with smaller index than $i(t)$ is in $T$. Therefore, $P_D$ is consistent with $T$. +\item Base case: $\mathsf{P_{C_1}}$ includes $\mathsf{u}$, whose path includes $\mathsf{t}$. + +\item Inductive step: Each client in $\mathsf{\mathscr{C}}$ has a partial sequence with a message +that includes $\mathsf{t}$ if the previous client does. Suppose $\mathsf{P_{C_k}}$ has +a message $\mathsf{w}$ with a path that includes $\mathsf{t}$, and shares message $\mathsf{x}$ +with $\mathsf{P_{C_{k+1}}}$ such that $\mathsf{s_x > s_n}$. By Lemma 1, $\mathsf{w}$ or +$\mathsf{x}$, whichever has the least sequence number, is in the path of the other, and therefore +by Lemma 2, $\mathsf{t}$ is in the path of $\mathsf{x}$. + +\item Let $\mathsf{z}$ be the message of $\mathsf{D}$ whose path includes $\mathsf{t}$. +By Lemma 1, every message in $\mathsf{P_D}$ with sequence number smaller than $\mathsf{s_w}$ +is in the path of $\mathsf{z}$. Since $\mathsf{t}$ is in the path of $\mathsf{z}$, every +message in $\mathsf{P_D}$ with smaller sequence number than $\mathsf{s_t = s_n}$ is in $\mathsf{T}$. +Therefore, $\mathsf{P_D}$ is consistent with $\mathsf{T}$. \end{itemize} \end{proof} -- 2.34.1