\usepackage{graphicx}\r
\usepackage{mathrsfs}\r
\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx\r
+\usepackage[all]{xy}\r
\newtheorem{theorem}{Theorem}\r
\newtheorem{prop}{Proposition}\r
\newtheorem{lem}{Lemma}\r
(a) check its HMAC, and\r
(b) check that the previous entry HMAC field matches the previous\r
entry.\r
-\item Check that the last message version for our machine matches our\r
-last message sent.\r
+\item Check that the last-message entry for our machine matches the stored HMAC of our last message sent.\r
\item For all other machines, check that the latest sequence number is\r
at least as large (never goes backwards).\r
\item That the queue has a current queue state entry.\r
\r
\subsection{Resizing Queue}\r
Client can make a request to resize the queue. This is done as a write that combines:\r
- (a) a slot with the message, and\r
- (b) a request to the server\r
+ (a) a slot with the message, and (b) a request to the server. The queue can only be expanded, never contracted; attempting to decrease the size of the queue will cause future clients to throw an error.\r
\r
\subsection{Server Algorithm}\r
-$s \in SN$ is a sequence number set\\\r
+$s \in SN$ is a sequence number\\\r
$sv \in SV$ is a slot's value\\\r
$slot_s = \tuple{s, sv} \in SL \subseteq SN \times SV$ \\ \\\r
\textbf{State} \\\r
\r
\begin{algorithmic}[1]\r
\Function{PutSlot}{$s_p,sv_p,max'$}\r
-\If{$(max' \neq \emptyset)$}\Comment{Resize}\r
+\If{$(max' \neq \emptyset)$} \Comment{Resize}\r
\State $max \gets max'$\r
\EndIf\r
\State $\tuple{s_n,sv_n} \gets MaxSlot(SL)$\Comment{Last sv}\r
$de$ is a data entry \\\r
$k$ is key of entry \\\r
$v$ is value of entry \\\r
-$kv$ is a key-value entry $\tuple{k,v}$, $kv \in D$ \\\r
+$kv$ is a key-value entry $\tuple{k,v}$, $kv \in DE$ \\\r
$ss$ is a slot sequence entry $\tuple{id,s_{last}}$, \r
-id + last s of a machine, $ss \in D$ \\\r
-$qs$ is a queue state entry (contains $max$ size of queue), $qs \in D$ \\\r
+id + last s of a machine, $ss \in DE$ \\\r
+$qs$ is a queue state entry (contains $max$ size of queue), $qs \in DE$ \\\r
$cr$ is a collision resolution entry $\tuple{s_{col},id_{col}}$, \r
-s + id of a machine that wins a collision, $cr \in D$ \\\r
-$D = \{kv,ss,qs,cr\}$ \\\r
-$DE = \{de \mid de \in D\}$ \\ \\\r
-$s \in SN$ is a sequence number set\\\r
+s + id of a machine that wins a collision, $cr \in DE$ \\\r
+$DE$ is a set of all data entries, possibly of different types, in a single message \\\r
+$s \in SN$ is a sequence number \\\r
$id$ is a machine ID\\\r
$hmac_p$ is the HMAC value of the previous slot \\\r
$hmac_c$ is the HMAC value of the current slot \\\r
$Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
$sv_s = \tuple{s, E(Dat_s)} = \r
\tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\\r
+\r
\textbf{States} \\\r
-\textit{$hmac_{p_g}$ = the HMAC value of the previous slot \r
-($hmac_{p_g} = \emptyset$ for the first slot)} \\\r
\textit{$id_{self}$ = machine Id of this client} \\\r
\textit{$max_g$ = maximum number of slots (initially $max_g > 0$)} \\\r
-\textit{m = number of slots on client (initially $m = 0$ and $m \leq n$)} \\\r
+\textit{m = number of slots stored on client (initially $m = 0$)} \\\r
\textit{$sl_{last}$ = info of last slot in queue = \r
$\tuple{s_{last},sv_{last},id_{last}}$ (initially $\emptyset$)} \\\r
\textit{DT = set of $\tuple{k,v}$ on client} \\\r
-\textit{MS = set of $\tuple{id, s_{last}}$ of all clients on client \r
+\textit{MS = associative array of $\tuple{id, s_{last}}$ of all clients on client \r
(initially empty)} \\\r
\textit{$MS_g$ = set MS to save all $\tuple{id, s_{last}}$ pairs while\r
traversing DT after a request to server (initially empty)} \\\r
\textit{SK = Secret Key} \\\r
-\textit{$SM$ = set of $\tuple{s, id}$ of all slots in a previous read\r
+\textit{$SM$ = associative array of $\tuple{s, id}$ of all slots in a previous read\r
(initially empty)} \\ \\\r
+\r
\textbf{Helper Functions} \\\r
$MaxSlot(SL_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv}\r
\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
$GetPrevHmac(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=hmac_p$ \\\r
$GetCurrHmac(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=hmac_c$ \\\r
$GetDatEnt(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=DE$ \\\r
-$GetKV(de_s$ \textit{such that} $de_s \in D \land de_s = kv)=\tuple{k_s,v_s}$ \\\r
-$GetSS(de_s$ \textit{such that} $de_s \in D \land de_s = ss)=\tuple{id,s_{last}}$ \\\r
-$GetQS(de_s$ \textit{such that} $de_s \in D \land de_s = qs)=qs_s$ \\\r
-$GetCR(de_s$ \textit{such that} $de_s \in D \land de_s = cr)=\tuple{s_s,id_s}$ \\\r
-$GetLastSeqN(MS_s,id_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}}\r
-\in MS_s \wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, id = id_s$ \\\r
-$GetMachineId(SM_s,s_s)= id$ \textit{such that} $\tuple{s, id}\r
-\in SM_s \wedge \forall \tuple{s_s, id_s} \in SM_s, s = s_s$ \\\r
+$GetKV($key-value data entry$)=\tuple{k_s,v_s}$ \\\r
+$GetSS($slot-sequence data entry$)=\tuple{id,s_{last}}$ \\\r
+$GetQS($queue-state data entry$)=qs_s$ \\\r
+$GetCR($collision-resolution data entry$)=\tuple{s_s,id_s}$ \\\r
$GetS(\tuple{s, id})=s$ \\\r
$GetId(\tuple{s, id})=id$ \\\r
$GetKey(\tuple{k, v})=k$ \\\r
\wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \leq s_{s_{last}}$ \\\r
\r
\begin{algorithmic}[1]\r
-\Procedure{ReportError}{$msg$}\r
+\Procedure{Error}{$msg$}\r
\State $Print(msg)$\r
\State $Halt()$\r
\EndProcedure\r
\r
\begin{algorithmic}[1]\r
\Function{UpdateLastSeqN}{$id_s,s_s,MS_s$}\r
-\State $s_t \gets GetLastSeqN(MS_s,id_s)$\r
+\State $s_t \gets MS_s[id_s]$\r
\If{$s_t = \emptyset$}\r
- \State $MS_s \gets MS_s \cup \{\tuple{id_s,s_s}\}$\Comment{First occurrence}\r
+ \State $MS_s[id_s] = s_s$ \Comment{First occurrence}\r
\Else\r
- \If{$s_s > s_t$}\Comment{Update entry with a later s}\r
- \State $MS_s \gets (MS_s - \{\tuple{id_s,s_t}\}) \cup \r
- \{\tuple{id_s,s_s}\}$\r
- \EndIf\r
+ \State $MS_S[id_s] \gets max(s_t, s_s)$\r
\EndIf\r
\State \Return{$MS_s$}\r
\EndFunction\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
-\Procedure{CheckLastSeqN}{$MS_s,MS_t$}\Comment{Check $MS_t$ based on $MS_s$}\r
-\ForAll{$\tuple{id_t,s_{t_{last}}} \in MS_t$}\r
- \State $s_{s_{last}} \gets GetLastSeqN(MS_s,id_t)$\r
- \If{$s_{s_{last}} \neq \emptyset$}\r
- \If{$id_t = id_{self}$}\r
- \If{$s_{s_{last}} \neq s_{t_{last}}$}\r
- \State \Call{ReportError}{'Invalid last $s$ for this machine'}\r
- \EndIf\r
- \Else\r
- \If{$s_{s_{last}} \geq s_{t_{last}}$}\r
- \State $MS_s \gets (MS_s - \{\tuple{id_t,s_{t_{last}}}\}) \cup \r
- \{\tuple{id_t,s_{s_{last}}}\}$\r
- \Else\r
- \State \Call{ReportError}{'Invalid last $s$ for machine $id_t$'}\r
- \EndIf\r
- \EndIf\r
+\Procedure{CheckLastSeqN}{$MS_s,MS_t$}\Comment{Check $MS_t$ based on the newer $MS_s$}\r
+\For {$\tuple{id, s_t}$ in $MS_t$}\r
+ \State $s_s \gets MS_s[id]$\r
+ \If{$s_s = \emptyset$}\r
+ \Call{Error}{'No $s$ for machine $id$'}\r
+ \ElsIf{$id = id_{self}$ and $s_s \neq s_t$}\r
+ \State \Call{Error}{'Invalid last $s$ for this machine'}\r
+ \ElsIf{$id \neq id_{self}$ and $s_{s_{last}} < s_{t_{last}}$}\r
+ \State \Call{Error}{'Invalid last $s$ for machine $id$'}\r
+ \Else\r
+ \State $MS_t[id] \gets s_s$\r
\EndIf\r
\EndFor\r
\EndProcedure\r
\r
\begin{algorithmic}[1]\r
\Procedure{CheckColRes}{$SM_s,\tuple{s_t,id_t}$}\Comment{Check $id_s$ in $SM_s$}\r
-\State $s_t \gets GetS(\tuple{s_t,id_t})$\r
-\State $id_t \gets GetId(\tuple{s_t,id_t})$\r
-\State $id_s \gets GetMachineId(SM_s,s_t)$\r
+\State $id_s \gets SM_s[s_t]$\r
\If{$id_s \neq id_t$}\r
- \State \Call{ReportError}{'Invalid $id_s$ for this slot update'}\r
+ \State \Call{Error}{'Invalid $id_s$ for this slot update'}\r
\EndIf\r
\EndProcedure\r
\end{algorithmic}\r
\State $MS_g \gets \emptyset$\r
\State $SM_{curr} \gets \emptyset$\r
\State $\tuple{s_{g_{max}},sv_{g_{max}}} \gets MaxSlot(SL_g)$\r
-\State $s_{g_{max}} \gets SeqN(\tuple{s_{g_{max}},sv_{g_{max}}})$\r
\State $\tuple{s_{g_{min}},sv_{g_{min}}} \gets MinSlot(SL_g)$\r
-\State $s_{g_{min}} \gets SeqN(\tuple{s_{g_{min}},sv_{g_{min}}})$\r
\For{$s_g \gets s_{g_{min}}$ \textbf{to} $s_{g_{max}}$}\Comment{Process slots \r
in $SL_g$ in order}\r
\State $\tuple{s_g,sv_g} \gets Slot(SL_g,s_g)$\r
\State $SM_{curr} \gets SM_{curr} \cup \{\tuple{s_g,sv_g}\}$\r
- \State $s_g \gets SeqN(\tuple{s_g,sv_g})$\r
- \State $sv_g \gets SlotVal(\tuple{s_g,sv_g})$\r
\State $Dat_g \gets Decrypt(SK,sv_g)$\r
\State $s_{g_{in}} \gets GetSeqN(Dat_g)$\r
\If{$s_g \neq s_{g_{in}}$}\r
- \State \Call{ReportError}{'Invalid sequence number'}\r
+ \State \Call{Error}{'Invalid sequence number'}\r
\EndIf\r
\State $DE_g \gets GetDatEnt(Dat_g)$\r
\State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_g)$\r
\EndIf\r
\State $hmac_{c_g} \gets GetCurrHmac(Dat_g)$\r
\If{$\neg \Call{ValidHmac}{DE_g,SK,hmac_{c_g}}$}\r
- \State \Call{ReportError}{'Invalid current HMAC value'}\r
+ \State \Call{Error}{'Invalid current HMAC value'}\r
\EndIf\r
\State $hmac_{p_g} \gets Hmac(DE_g,SK)$\Comment{Update $hmac_{p_g}$ for next check}\r
\State $qs_g \gets \Call{GetQueSta}{Dat_g}$\Comment{Handle qs}\r
\If{$m + |SL_g| \leq max_g$}\Comment{Check actual size against $max_g$}\r
\State $m \gets m + |SL_g|$\r
\Else\r
- \State \Call{ReportError}{'Actual queue size exceeds $max_g$'}\r
+ \State \Call{Error}{'Actual queue size exceeds $max_g$'}\r
\EndIf\r
\State $\Call{CheckLastSeqN}{MS_g,MS}$\r
\EndProcedure\r
$k$ is key of entry \\\r
$v$ is value of entry \\\r
$kv$ is a key-value entry $\tuple{k,v}$\\\r
-$D = \{kv,ss,qs,cr\}$ \\\r
-$DE = \{de \mid de \in D\}$ \\\r
+$DE$ is a set of data entries, possibly of different types \\\r
$Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
$sv_s = \tuple{s, E(Dat_s)} = \r
\tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\\r
\textbf{States} \\\r
-\textit{$cp$ = data entry $DE$ maximum size/capacity} \\\r
+\textit{$capacity$ = data entry $DE$ maximum size/capacity} \\\r
\textit{$cr_p$ = saved cr entry $\tuple{s,id}$ on client if there is a collision\r
(sent in the following slot)} \\\r
\textit{$cr_{p_{last}}$ = saved cr entry $\tuple{s,id}$ on client if there is a \r
$\tuple{s_{last},sv_{last},id_{last}}$ (initially $\emptyset$)} \\\r
\textit{$th_p$ = threshold number of dead slots for a resize to happen} \\\r
\textit{$m'_p$ = offset added to $max$ for resize} \\\r
-\textit{$KV$ = set of $\tuple{ck, \tuple{k,v}}$ of kv entries on client} \\\r
+\textit{$KV$ = associative array of $\tuple{ck, \tuple{k,v}}$ kv entries on client} \\\r
\textit{$SL_p$ = set of returned slots on client} \\\r
\textit{SK = Secret Key} \\ \\\r
\textbf{Helper Functions} \\\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
+\r
\Function{ReinsertLastSlot}{$MS_s,SK_s,sl_{s_{last}},max'_s,hmac_{p_s}$}\r
\State $s_s \gets MaxLastSeqN(MS_s)$\r
\State $sv_s \gets GetSV(sl_{s_{last}})$\r
\State $\tuple{stat_s,SL_s} \gets \Call{PutSlot}{s_s,sv_s,max'_s}$ \r
\State $cr_s \gets \Call{HandleCollision}{\tuple{stat_s,SL_s}}$\r
\State \Return{$\tuple{cr_s,hmac_{p_p}}$}\r
+\r
\EndFunction\r
\end{algorithmic}\r
\note{Shouldn't this function do something pretty sophisticated about seeing what data we actually need to keep from the last slot and not just insert the entire thing?}\r
\r
\note{Probably best to just not call this function if $need_s$ is false and not pass in such parameters. It makes it harder to read.}\r
\r
-\r
\begin{algorithmic}[1]\r
\Function{GetDEPairs}{$KV_s,max'_s,need_s,sl_s$}\r
\State $DE_{ret} \gets \emptyset$\r
-\State $cp_s \gets cp$\r
+\State $capacity_s \gets capacity$\r
\If{$cr_p \neq \emptyset$}\Comment{Check and insert a $cr$}\r
\State $DE_{ret} \gets DE_{ret} \cup cr_p$\r
- \State $cp_s \gets cp_s - 1$\r
+ \State $capacity_s \gets capacity_s - 1$\r
\EndIf\r
\If{$cr_{p_{last}} \neq \emptyset$}\Comment{Check and insert a $cr$}\r
\State $DE_{ret} \gets DE_{ret} \cup cr_{p_{last}}$\r
- \State $cp_s \gets cp_s - 1$\r
+ \State $capacity_s \gets capacity_s - 1$\r
\EndIf\r
\If{$max'_s \neq \emptyset$}\Comment{Check and insert a $qs$}\r
\State $qs_s \gets max'_s$\r
\State $DE_{ret} \gets DE_{ret} \cup qs_s$\r
- \State $cp_s \gets cp_s - 1$\r
+ \State $capacity_s \gets capacity_s - 1$\r
\EndIf\r
\If{$need_s$}\Comment{Check and insert a $ss$}\r
\State $id_s \gets GetID(sl_s)$\r
\State $s_{s_{last}} \gets GetLastS(sl_s)$\r
\State $ss_s \gets CreateSS(id_s,s_{s_{last}})$\r
\State $DE_{ret} \gets DE_{ret} \cup ss_s$\r
- \State $cp_s \gets cp_s - 1$\r
+ \State $capacity_s \gets capacity_s - 1$\r
\EndIf\r
-\If{$|KV_s| \leq cp$}\Comment{$KV$ set can extend multiple slots}\r
+\If{$|KV_s| \leq capacity$}\Comment{$KV$ set can extend multiple slots}\r
\State $DE_{ret} \gets DE_{ret} \cup\r
\{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s\}$\r
\Else\r
\State $DE_{ret} \gets DE_{ret} \cup\r
\{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s,\r
- ck_g \leq ck_s < ck_g + cp_s\}$\r
- \If{$|DE_{ret}| = cp$}\r
- \State $ck_g \gets ck_g + cp_s$\Comment{Middle of KV set}\r
+ ck_g \leq ck_s < ck_g + capacity_s\}$\r
+ \If{$|DE_{ret}| = capacity$}\r
+ \State $ck_g \gets ck_g + capacity_s$\Comment{Middle of KV set}\r
\Else\r
\State $ck_g \gets 0$\Comment{End of KV set}\r
\EndIf\r
\State $\tuple{stat_p,SL_p} \gets \Call{PutSlot}{s_p,sv_p,max'_p}$\r
\State $cr_p \gets \Call{HandleCollision}{\tuple{stat_p,SL_p}}$\r
\If{$need_p$}\r
- \State $\tuple{cr_{p_{last}},hmac_{p_p}} \gets \r
- \Call{ReinsertLastSlot}{MS,SK,sl_{last},max'_p,hmac_{p_p}}$\r
+ \State $cr_{p_{last}} \gets \Call{ReinsertLastSlot}{sl_{last},max'_p}$\r
\EndIf\r
\EndProcedure\r
\end{algorithmic}\r
\item Equality: Two messages $t$ and $u$ are equal if their sequence numbers, senders, and contents are exactly the same.\r
\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.\r
\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))$.\r
-\item Chain: A chain of messages with length $n \ge 1$ is a message sequence $(t_i, t_{i+1}, ..., t_{i+n-1})$ such that for every index $i < k \le i+n-1$, $t_k$ has sequence number $k$ and is the parent of $t_{k-1}$. Note that no two entries in a chain can have the same sequence number.\note{This definition is never used, instead you refer to paths..}\r
-\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.\r
-\item Total message sequence: A total message sequence $T$ with length $n$ is a chain of messages that starts at $i = 1$. The path of a message $t$ is the total message sequence whose last message is $t$.\r
+\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, where a chain of messages with length $n \ge 1$ is a message sequence $(t_i, t_{i+1}, ..., t_{i+n-1})$ such that for every index $i < k \le i+n-1$, $t_k$ has sequence number $k$ and is the parent of $t_{k-1}$.\r
+\item Total message sequence: A total message sequence $T$ with length $n$ is a chain of messages that starts at $i = 1$.\r
+\item Path: The path of a message $t$ is the total message sequence whose last message is $t$.\r
\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.\r
-\item Transitive closure set at index $i$: 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) > i$.\note{Confusing to reuse i}\r
+\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$.\r
\r
\end{enumerate}\r
\r
\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}\r
\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}\r
\r
-\begin{lem} If two packets $t$ and $u$, with $i(t) \le i(u)$, are received without errors by a client $C$, then $t$ is in the path of $u$. \note{path never defined}\end{lem}\r
+\begin{figure}[h]\r
+ \centering\r
+ \xymatrix{\r
+\dots \ar[r] & q \ar[dr]_{J} \ar[r]^{K} & S_1 \ar[r] & S_2 \ar[rr] & & \dots \ar[r] & S_n = u \\\r
+& & R_1 \ar[r] & R_2 \ar[r] & \dots \ar[r] & R_m = t}\r
+\caption{By Lemma 1, receiving $u$ after $t$ is impossible.}\r
+\end{figure}\r
+\r
+\begin{lem} Two packets are received without errors by a client $C$; we can call them $t$ and $u$ such that $i(t) \le i(u)$. Then $t$ is in the path of $u$. \end{lem}\r
\begin{proof}\r
+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$.\r
+\r
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 largest index for this $u$. We will prove that an error occurs upon receipt of $u$.\r
\r
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$.\r
There are two cases:\r
\r
\begin{itemize}\r
-\item Case 1: $J$ did not send a message in $S$. Then $v_J(t) > v_J(q) = v_J(u)$. $C$ will throw an error, because the latest index of $J$ changes in the opposite direction of the sequence number: $v_J(u) < v_J(t)$ but $i(u) > i(t)$.\note{Need more contet as to why C would throw an error...You are assuming that it reads two disjoint windows...one with u and the other with t...other case is that they are contiguous, in which case the hashes can't match...}\r
+\item Case 1: $J$ did not send a message in $S$. Then $v_J(t) > v_J(q) = v_J(u)$.\r
+\begin{itemize}\r
+\item Case 1.2: $C$ receives a sequence of messages between $t$ and $u$ with contiguous sequence numbers. In particular, there is some packet $p$ such that $i(p) = i(u) + 1$. If $p$ is the parent of $u$, messages $t$ and $p$ are a violation of this lemma such that $p$ has a smaller sequence number than $u$; but this contradicts our assumption that $u$ had the smallest sequence number. If $t$ is not the parent of $u$, $HMAC_p(u) \neq HMAC_c(t)$, causing $C$ to error.\r
+\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 overall during this time, which means it must decrease when some message is received, which means C throws an error in the $CheckLastSeqN$ subroutine.\r
+\r
+\end{itemize}\r
+\r
+\r
+\r
\item Case 2: $J$ sent at least one message in $S$. Call the first one $p$. We know that $i(p) > i(S_1)$, since $J \neq K$. $R_1$ must be sent either before or after $p$.\r
\begin{itemize}\r
-\item Case 2.1: Client $J$ sends $p$, and then $R_1$. When $p$ was sent, whether it was accepted or rejected, $i(J, p) \geq i(p)$. Since $i(p) > i(S_1)$, $i(J, p) > q$. So $i(q) < i(J, p)$, which would cause $J$ to fail to send $R_1$, a contradiction.\note{Never defined i(J,p). don't you mean i(q)+1 instead of q?}\r
+\item Case 2.1: Client $J$ sends $p$, and then $R_1$. When $p$ was sent, whether it was accepted or rejected, $i(J, p) \geq i(p)$. Since $i(p) > i(S_1)$, $i(J, p) > q$. So $i(q) < i(J, p)$, which would cause $J$ to fail to send $R_1$, a contradiction.\r
+\begin{itemize}\r
+\item Case 2.2.1: \r
+\r
+\r
+\r
+\end{itemize}\r
\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$.\r
\begin{itemize}\r
\item Case 2.2.1: Some message in $X$ was accepted. In this case, before sending $p$, $J$'s value for its own latest index would be strictly greater than $v_J(q)$. ($J$ could not have sent a message with index less than $i(q)$ after receiving $q$). When preparing to send $p$, $J$ would have received its own latest index as at most $v_J(q)$. $J$ throws an error before sending $p$, because its own latest index decreases.\r
-\item Case 2.2.2: All messages in $X$ were rejected. Client $J$ will always add the latest rejected message to the rejected-message list in the next update; 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 $RML(p)$. Since every rejected message in $RML(p)$ will be in $RML(C, u)$, and $u$ is the first message that $C$ sees which does not have $t$ in its path, $R_1$ will be recorded in $RML(C, p)$. When $C$ receives $u$, $C$ will throw an error from the match $(J, iq+1)$ in $RML(C, p)$.\note{Missing case...what if C switches branches before J? It will see a version rollback...Also need more context...disjoint reads...etc...}\r
+\item Case 2.2.2: All messages in $X$ were rejected. Client $J$ will always add the latest rejected message to the rejected-message list in the next update; 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 $RML(p)$. Since every rejected message in $RML(p)$ will be in $RML(C, u)$, and $u$ is the first message that $C$ sees which does not have $t$ in its path, $R_1$ will be recorded in $RML(C, p)$. When $C$ receives $u$, $C$ will throw an error from the match $(J, iq+1)$ in $RML(C, p)$.\r
\end{itemize}\r
\end{itemize}\r
\end{itemize}\r
Suppose that there is a transitive closure set $\mathscr{S}$ of clients, at index $n$. Then there is some total message sequence $T$ of length $n$ such that every client $C$ in $\mathscr{S}$ sees a partial sequence $P_C$ consistent with $T$. \end{theorem}\r
\r
\begin{proof}\r
-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 message sequence $P_{C_1}$, and let $u$ be some message with $i(u) > i$ that $C_1$ shares with another client. Then let $T$ be the portion of the path of $u$ ending at index $i$ and $t$ be the message at that index. Clearly, by Lemma 1, $P_{C_1}$ is consistent with $T$, and furthermore. \note{typo in previous sentence?} 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 edges from $C_1$ to $D$. Call this $\mathscr{C} = (C_1, C_2, ..., D)$. I will prove by induction that $D$ has a message whose path includes $t$.\r
+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 message sequence $P_{C_1}$, and let $u$ be some message with $i(u) > i$ that $C_1$ shares with another client. Then let $T$ be the portion of the path of $u$ ending at index $i$ 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 edges from $C_1$ to $D$. Call this $\mathscr{C} = (C_1, C_2, ..., D)$. I will prove by induction that $D$ has a message whose path includes $t$.\r
\r
For the base case, $P_{C_1}$ includes $u$, whose path includes $t$. For the inductive step, suppose $P_{C_k}$ has an message $w$ with a path that includes $t$, and shares message $x$ with $P_{C_{k+1}}$ such that $i(x) > i$. If $i(w) = i(x)$, then $w = x$. If $i(w) < i(x)$, then, by Lemma 1, $w$ is in the path of $x$. If $i(w) > i(x)$, $x$ is in the path of $w$; note again that its index is greater than $i$. In any case, $t$ is in the path of $u_k+1$.\r
\r
Let $w$ 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 $w$. Since $t$ is in the path of $w$, every message in $P_D$ with smaller index than $i(t)$ is in $T$. Therefore, $P_D$ is consistent with $T$.\r
\end{proof}\r
\r
-\note{General comments...some diagrams could help...theorem 1 is pretty hard to follow...}\r
-\r
\subsection{Future Work}\r
\paragraph{Support Messages}\r
A message is dead once receiving machine sends an entry with a newer\r
\r
Idea is to separate subspace of entries... Shared with other cloud...\r
\end{document}\r
-\r
projects / iotcloud.git / commitdiff