\subsection{Client Algorithm}\r
\subsubsection{Reading Slots}\r
\textbf{Data Entry} \\\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 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 DE$ \\\r
+$de$ is a data entry that can be a $kv$, $ss$, $qs$, or $cr$ \\\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
+$hmac_{p_g}$ is the HMAC value of the previous slot in procedure $\Call{ProcessSL}{}$ \\\r
+$hmac_{c_g}$ is the HMAC value of the current slot in procedure $\Call{ProcessSL}{}$ \\\r
$Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
$slot_s = \tuple{s, E(Dat_s)} = \r
\tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\\r
\textbf{States} \\\r
+\textit{$d$ = delta between the last $s$ recorded and the first $s$ received} \\\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 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_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$ = associative array of $\tuple{s, id}$ of all slots in a previous read\r
+\textit{$SM$ = associative array of $\tuple{s, id}$ of all slots in previous reads\r
(initially empty)} \\ \\\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
+ \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
$MinSlot(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 \leq s_s$ \\\r
+ \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\\r
$Slot(SL_s,s_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 = s_s$ \\\r
+ \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s = s_s$ \\\r
$SeqN(\tuple{s, sv})=s$ \\\r
$SlotVal(\tuple{s, sv})=sv$ \\\r
$CreateLastSL(s,sv,id)=\tuple{s,sv,id}=sl_{last}$ \\\r
-$CreateEntLV(kv_s,s_s)=\tuple{kv_s,s_s}$ \\\r
$Decrypt(SK_s,sv_s)=Dat_s=\tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
$GetSeqN(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=s$ \\\r
$GetMacId(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=id$ \\\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
$GetLiveSS(SS_{live},ss_s)= ss$ \textit{such that} $ss \in SS_{live} \r
-\wedge \forall ss_s \in SS_{live}, ss = ss_s$ \\\r
+ \wedge \forall ss_s \in SS_{live}, ss = ss_s$ \\\r
$GetLiveCR(CR_{live},cr_s)= cr$ \textit{such that} $cr \in CR_{live} \r
-\wedge \forall cr_s \in CR_{live}, cr = cr_s$ \\\r
+ \wedge \forall cr_s \in CR_{live}, cr = cr_s$ \\\r
$GetLivEntLastS(LV_s,kv_s)= s$ \textit{such that} $\tuple{kv, s} \in LV_s \r
-\wedge \forall \tuple{kv_s, s_s} \in LV_s, kv_s = kv$ \\\r
+ \wedge \forall \tuple{kv_s, s_s} \in LV_s, kv_s = kv$ \\\r
$GetKV($key-value data entry$)=\tuple{k_s,v_s} = kv_s$ \\\r
$GetSS($slot-sequence data entry$)=\tuple{id_s,s_{s_{last}}} = ss_s$ \\\r
-$GetQS($queue-state data entry$)=qs_s$ \\\r
-$GetCR($collision-resolution data entry$)=\tuple{s_s,id_s} = cr_s$ \\\r
-$GetKey(kv = \tuple{k, v})=k$ \\\r
-$GetVal(kv = \tuple{k, v})=v$ \\\r
-$GetId(ss = \tuple{id, s_{last}})=id$ \\\r
-$GetSLast(ss = \tuple{id, s_{last}})=s_{last}$ \\\r
-$GetS(cr = \tuple{s, id})=s$ \\\r
-$GetId(cr = \tuple{s, id})=id$ \\\r
+$GetCR($de$)=\tuple{s_s,id_s} = cr_s$ \\\r
+$Hmac(Dat_s,SK) = hmac_c$ \textit{value computed from $s$, $id$,\r
+$hmac_p$, and $DE$ taken from $Dat_s$} \\\r
+$IsKv(de) = true$ \textit{if $de$ is a $kv$, false otherwise} \\\r
+$IsSs(de) = true$ \textit{if $de$ is a $ss$, false otherwise} \\\r
+$IsQs(de) = true$ \textit{if $de$ is a $qs$, false otherwise} \\\r
+$IsCr(de) = true$ \textit{if $de$ is a $cr$, false otherwise} \\\r
+$GetKey(kv)=k$\Comment{$kv = \tuple{k, v}$} \\\r
+$GetVal(kv)=v$ \\\r
+$GetId(ss)=id$\Comment{$ss = \tuple{id, s_{last}}$} \\\r
+$GetSLast(ss)=s_{last}$ \\\r
+$GetS(cr)=s$\Comment{$cr = \tuple{s, id}$} \\\r
+$GetId(cr)=id$ \\\r
+$GetLastS(sl_{last})=s$\Comment{$sl_{last} = \tuple{s,sv,id}$} \\\r
+$GetSV(sl_{last})=sv$ \\\r
+$GetID(sl_{last})=id$ \\\r
$GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} \r
-\in DT_s \wedge \forall \tuple{k_s, v_s} \in DT_s, k = k_s$ \\\r
+ \in DT_s \wedge \forall \tuple{k_s, v_s} \in DT_s, k = k_s$ \\\r
$MaxLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \r
-\wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \geq s_{s_{last}}$ \\\r
+ \wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \geq s_{s_{last}}$ \\\r
$MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \r
-\wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \leq s_{s_{last}}$ \\\r
+ \wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \leq s_{s_{last}}$ \\\r
+$MinCRSeqN(CR_s)= s$ \textit{such that} $\tuple{s, id} \in CR_s \r
+ \wedge \forall \tuple{s_s, id_s} \in CR_s, s \leq s_s$ \\\r
+$MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s \r
+ \wedge \forall \tuple{s_s, id_s} \in SM_s, s \geq s_s$ \\\r
\r
\begin{algorithmic}[1]\r
\Procedure{Error}{$msg$}\r
\EndProcedure\r
\end{algorithmic}\r
\r
-\begin{algorithmic}[1]\r
-\Function{ValidHmac}{$DE_s,SK_s,hmac_{stored}$}\r
-\State $hmac_{computed} \gets Hmac(DE_s,SK_s)$\r
-\State \Return {$hmac_{stored} = hmac_{computed}$}\r
-\EndFunction\r
-\end{algorithmic}\r
-\r
-\begin{algorithmic}[1]\r
-\Function{ValidPrevHmac}{$s_s,DE_s,hmac_{p_s},hmac_{p_{sto}}$}\r
-\If{$s_s = 0 \land hmac_{p_s} = \emptyset$}\Comment{First slot - no previous HMAC}\r
- \State \Return $true$\r
-\Else\r
- \State \Return {$hmac_{p_{sto}} = hmac_{p_s}$}\r
-\EndIf\r
-\EndFunction\r
-\end{algorithmic}\r
-\r
\begin{algorithmic}[1]\r
\Function{GetQueSta}{$DE_s$}\r
-\State $de_{qs} \gets de_s$ \textit{such that} $de_s \in DE_s, \r
- de_s \in D \land de_s = qs$\r
-\If{$de_{qs} \neq \emptyset$}\r
- \State $qs_{ret} \gets GetQS(de_{qs})$\r
+\State $qs_{de} \gets qs$ \textit{such that} $qs \in DE_s, \r
+ de_s \in D \land IsQs(de_s)$\r
+\If{$qs_{de} \neq \emptyset$}\r
+ \State $qs_{ret} \gets qs_{de})$\r
\Else\r
\State $qs_{ret} \gets \emptyset$\r
\EndIf\r
\r
\begin{algorithmic}[1]\r
\Function{GetSlotSeq}{$DE_s$}\r
-\State $DE_{ss} \gets \{de_s | de_s \in DE_s, de_s = ss\}$\r
+\State $DE_{ss} \gets \{de | de \in DE_s \land IsSs(de)\}$\r
\State \Return{$DE_{ss}$}\r
\EndFunction\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
\Function{GetColRes}{$DE_s$}\r
-\State $DE_{cr} \gets \{de_s | de_s \in DE_s, de_s = cr\}$\r
+\State $DE_{cr} \gets \{de | de \in DE_s \land IsCr(de)\}$\r
\State \Return{$DE_{cr}$}\r
\EndFunction\r
\end{algorithmic}\r
\If{$s_t = \emptyset$}\r
\State $MS_s[id_s] = s_s$ \Comment{First occurrence}\r
\Else\r
+ \If{$id_s = id_{self}$}\r
+ \If{$s_t \neq s_s$}\Comment{Check for mismatch on $s$}\r
+ \State \Call{Error}{'Mismatch on $s$ for $id_{self}$'}\r
+ \EndIf\r
+ \Else\r
+ \If{$s_t > s_s$}\Comment{Check for rollback on $s$}\r
+ \State \Call{Error}{'Rollback on $s$ for $id_s$'}\r
+ \EndIf\r
+ \EndIf\r
\State $MS_S[id_s] \gets max(s_t, s_s)$\r
\EndIf\r
\State \Return{$MS_s$}\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
-\Function{AddCRLivEnt}{$CR_{s_{live}},de_s$}\r
-\State $cr_s \gets GetCR(de_s)$\r
+\Function{AddCRLivEnt}{$CR_{s_{live}},cr_s$}\r
\State $cr_t \gets GetLiveCR(CR_{s_{live}},cr_s)$\r
\If{$cr_t = \emptyset$}\r
\State $CR_{s_{live}} \gets CR_{s_{live}} \cup \{cr_s\}$\Comment{First occurrence}\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
-\Procedure{CheckLastSeqN}{$MS_s,MS_t$}\r
+\Function{UpdateSM}{$SM_s,CR_s$}\Comment{Remove if dead}\r
+\State $s_{cr_{min}} \gets MinCRSeqN(CR_s)$\r
+ \State $SM_s \gets SM_s - \{\tuple{s_s,id_s} \mid \tuple{s_s,id_s}\r
+ \in SM_s \wedge s_s < s_{cr_{min}}\}$\r
+\State \Return{$CR_{s_{live}}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Procedure{CheckLastSeqN}{$MS_s,MS_t,d$}\r
\For {$\tuple{id, s_t}$ in $MS_t$}\Comment{Check $MS_t$ based on the newer $MS_s$}\r
\State $s_s \gets MS_s[id]$\r
- \If{$s_s = \emptyset$}\r
- \Call{Error}{'No $s$ for machine $id$'}\r
+ \If{$d \land s_s = \emptyset$}\r
+ \State \Call{Error}{'Missing $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
+ \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 $id_s \gets GetId(cr_s)$\r
\State $s_{s_{last}} \gets GetLastSeqN(MS_s,id_s)$\r
\If{$s_{s_{last}} < s_s$}\r
- \State $\Call{CheckColRes}{SM_s,cr_s}$\r
+ \State $id_t \gets SM_s[s_s]$\r
+ \If{$id_s \neq id_t$}\r
+ \State \Call{Error}{'Invalid $id$ for this slot update'}\r
+ \EndIf\r
\EndIf\r
\EndIf\r
\EndProcedure\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
-\Procedure{CheckColRes}{$SM_s,cr_t$}\Comment{Check $id_s$ in $SM_s$}\r
-\State $s_t \gets GetS(cr_t)$\r
-\State $id_s \gets SM_s[s_t]$\r
-\If{$id_s \neq id_t$}\r
- \State \Call{Error}{'Invalid $id$ for this slot update'}\r
+\Function{ValidSlotsRange}{$s_{s_{min}}$}\r
+\State $s_{s_{last}} \gets MaxSMSeqN(SM)$\r
+\If{$s_{s_{min}} \leq s_{s_{last}}$}\r
+ \State \Call{Error}{'Server sent old slots'}\r
+\EndIf\r
+\State \Return{$s_{s_{min}} > s_{s_{last}} + 1$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Procedure{CheckNumSlots}{$|SL_s|,sz_s$}\r
+\If{$|SL_s| \neq sz_s$}\r
+ \State \Call{Error}{'Actual number of slots does not match expected'}\r
\EndIf\r
\EndProcedure\r
\end{algorithmic}\r
\EndFunction\r
\end{algorithmic}\r
\r
+\begin{algorithmic}[1]\r
+\Function{ValidHmacChain}{$Dat_s,s_s,hmac_{p_s},sl_l$}\r
+ \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_s)$\r
+ \If {$ \neg(s_s = 0 \land hmac_{p_s} = 0)$}\r
+ \State $s_l \gets GetLastS(sl_l)$\r
+ \If {$(s_s > s_l + 1) \land (hmac_{p_{stored}} \neq hmac_{p_s})$}\r
+ \State \Call{Error}{'Invalid previous HMAC value'}\r
+ \EndIf\r
+ \EndIf\r
+ \If{$Hmac(Dat_s,SK) \neq GetCurrHmac(Dat_s)$ }\r
+ \State \Call{Error}{'Invalid current HMAC value'}\r
+ \EndIf\r
+ \State $hmac_{p_s} \gets Hmac(Dat_s,SK)$\Comment{Update $hmac_{p_s}$ for next check}\r
+\State \Return{$hmac_{p_s}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
\begin{algorithmic}[1]\r
\Function{UpdateDT}{$DT_s,DE_s,LV_s,s_s$}\r
-\State $DE_{s_{kv}} \gets \{de_s | de_s \in DE_s, de_s = kv\}$\r
-\ForAll{$de_s \in DE_s$}\r
+\State $DE_{s_{kv}} \gets \{de_s | de_s \in DE_s \land IsKv(de_s)\}$\r
+\ForAll{$de_s \in DE_{s_{kv}}$}\r
\State $kv_s \gets GetKV(de_s)$\r
\State $LV_s \gets \Call{UpdateKVLivEnt}{LV_s,kv_s,s_s}$\r
\State $k_s \gets GetKey(kv_s)$\r
\EndFunction\r
\end{algorithmic}\r
\r
+\begin{algorithmic}[1]\r
+\Function{InitExpSize}{$s_{min}$}\r
+\If{$s_{min} < max_g$}\Comment{Check whether $SL$ is full on server}\r
+ \State $sz_s \gets s_{min}$\r
+\Else\r
+ \State $sz_s \gets max_g$\r
+\EndIf\r
+\State \Return{$sz_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{UpdateExpSize}{$sz_s$}\r
+\State $sz_s \gets sz_s + 1$\r
+\If{$sz_s > max_g$}\Comment{Expected size $\leq max_g$}\r
+ \State $sz_s \gets max_g$\r
+\EndIf\r
+\State \Return{$sz_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{UpdateQS}{$Dat_s,max_s$}\r
+\State $DE_s \gets GetDatEnt(Dat_s)$\r
+\State $qs_s \gets \Call{GetQueSta}{DE_s}$\Comment{Handle qs}\r
+\If{$qs_s \neq \emptyset \land qs_s > max_s$}\r
+ \State $max_s \gets qs_s$\r
+\EndIf\r
+\State \Return{$max_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Procedure{UpdateCR}{$DE_s$}\r
+\State $DE_{s_{cr}} \gets \Call{GetColRes}{DE_s}$\Comment{Handle cr}\r
+\If{$DE_{s_{cr}} \neq \emptyset$}\r
+ \ForAll{$de_{s_{cr}} \in DE_{s_{cr}}$}\r
+ \State $cr_s \gets GetCR(de_{s_{cr}})$\r
+ \State $\Call{CheckCollision}{MS,SM,cr_s}$\r
+ \State $CR_{live} \gets \Call{AddCRLivEnt}{CR_{live},cr_s}$\r
+ \EndFor\r
+\EndIf\r
+\EndProcedure\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{UpdateSS}{$DE_s,MS_s$}\r
+\State $DE_{s_{ss}} \gets \Call{GetSlotSeq}{DE_s}$\Comment{Handle ss}\r
+\If{$DE_{s_{ss}} \neq \emptyset$}\r
+ \ForAll{$de_{s_{ss}} \in DE_{s_{ss}}$}\r
+ \State $\tuple{id_d,s_{d_{last}}} \gets GetSS(de_{s_{ss}})$\r
+ \State $MS_s \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_s}$\r
+ \State $SS_{live} \gets \Call{AddSSLivEnt}{SS_{live},de_{s_{ss}}}$\r
+ \EndFor\r
+\EndIf\r
+\State \Return{$MS_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
\begin{algorithmic}[1]\r
\Procedure{ProcessSL}{$SL_g$}\r
\State $MS_g \gets \emptyset$\r
-\State $SM_{curr} \gets \emptyset$\r
\State $\tuple{s_{g_{min}},sv_{g_{min}}} \gets MinSlot(SL_g)$\r
\State $\tuple{s_{g_{max}},sv_{g_{max}}} \gets MaxSlot(SL_g)$\r
+\State $d \gets \Call{ValidSlotsRange}{s_{g_{min}}}$\r
+\State $sz \gets \Call{InitExpSize}{s_{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 $Dat_g \gets Decrypt(SK,sv_g)$\r
+ \State $id_g \gets GetMacId(Dat_g)$\r
+ \State $SM \gets SM \cup \{\tuple{s_g,id_g}\}$\r
\State $s_{g_{in}} \gets GetSeqN(Dat_g)$\r
\If{$s_g \neq s_{g_{in}}$}\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
- \If{$\neg \Call{ValidPrevHmac}{s_g,DE_g,hmac_{p_g},hmac_{p_{stored}}}$}\r
- \State \Call{ReportError}{'Invalid previous HMAC value'}\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{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}{DE_g}$\Comment{Handle qs}\r
- \If{$qs_g \neq \emptyset \land qs_g > max_g$}\r
- \State $max_g \gets qs_g$\r
- \EndIf\r
- %Check for last s in Dat\r
- \State $id_g \gets GetMacId(Dat_g)$\Comment{Handle last s}\r
- \State $MS_g \gets \Call{UpdateLastSeqN}{id_g,s_g,MS_g}$\r
- %Check for last s in DE in Dat\r
- \State $DE_{g_{ss}} \gets \Call{GetSlotSeq}{DE_g}$\Comment{Handle ss}\r
- \If{$DE_{g_{ss}} \neq \emptyset$}\r
- \ForAll{$de_{g_{ss}} \in DE_{g_{ss}}$}\r
- \State $\tuple{id_d,s_{d_{last}}} \gets GetSS(de_{g_{ss}})$\r
- \State $MS_g \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_g}$\r
- \State $SS_{live} \gets \Call{AddSSLivEnt}{SS_{live},de_{g_{ss}}}$\r
- \EndFor\r
- \EndIf\r
- \State $DE_{g_{cr}} \gets \Call{GetColRes}{DE_g}$\Comment{Handle cr}\r
- \If{$DE_{g_{cr}} \neq \emptyset$}\r
- \ForAll{$de_{g_{cr}} \in DE_{g_{cr}}$}\r
- \State $cr_g \gets GetCR(de_{g_{cr}})$\r
- \State $\Call{CheckCollision}{MS,SM,cr_g}$\r
- \State $CR_{live} \gets \Call{AddCRLivEnt}{CR_{live},de_{g_{cr}}}$\r
- \EndFor\r
- \EndIf\r
+ \State $hmac_{p_g} \gets \Call{ValidHmacChain}{Dat_g,s_g,hmac_{p_g},sl_{last}}$\r
+ \State $sz \gets \Call{UpdateExpSize}{sz}$\r
+ \State $max_g \gets \Call{UpdateQS}{Dat_g,max_g}$\Comment{Handle qs}\r
+ \State $MS_g \gets \Call{UpdateLastSeqN}{id_g,s_g,MS_g}$\Comment{Handle last s}\r
+ \State $MS_g \gets \Call{UpdateSS}{DE_g,MS_g}$\Comment{Handle ss}\r
+ %\State $DE_{g_{ss}} \gets \Call{GetSlotSeq}{DE_g}$\Comment{Handle ss}\r
+ %\If{$DE_{g_{ss}} \neq \emptyset$}\r
+ % \ForAll{$de_{g_{ss}} \in DE_{g_{ss}}$}\r
+ % \State $\tuple{id_d,s_{d_{last}}} \gets GetSS(de_{g_{ss}})$\r
+ % \State $MS_g \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_g}$\r
+ % \State $SS_{live} \gets \Call{AddSSLivEnt}{SS_{live},de_{g_{ss}}}$\r
+ % \EndFor\r
+ %\EndIf\r
+ \State $\Call{UpdateCR}{DE_g}$\Comment{Handle cr}\r
+ %\State $DE_{g_{cr}} \gets \Call{GetColRes}{DE_g}$\Comment{Handle cr}\r
+ %\If{$DE_{g_{cr}} \neq \emptyset$}\r
+ % \ForAll{$de_{g_{cr}} \in DE_{g_{cr}}$}\r
+ % \State $cr_g \gets GetCR(de_{g_{cr}})$\r
+ % \State $\Call{CheckCollision}{MS,SM,cr_g}$\r
+ % \State $CR_{live} \gets \Call{AddCRLivEnt}{CR_{live},cr_g}$\r
+ % \EndFor\r
+ %\EndIf\r
\State $sl_{last} \gets \Call{StoreLastSlot}{MS,sl_{last},s_g,sv_g,id_g}$\r
\State $DT \gets \Call{UpdateDT}{DT,DE_g,LV,s_g}$\r
\EndFor\r
-\State $SM \gets SM_{curr}$\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{Error}{'Actual $SL$ size on server exceeds $max_g$'}\r
-\EndIf\r
-\State $\Call{CheckLastSeqN}{MS_g,MS}$\r
+\State $\Call{CheckLastSeqN}{MS_g,MS,d}$\r
+\State $\Call{CheckNumSlots}{|SL_g|,sz}$\r
\State $\Call{UpdateSSLivEnt}{SS_{live},MS}$\r
\State $\Call{UpdateCRLivEnt}{CR_{live},MS}$\r
+\State $\Call{UpdateSM}{SM,CR_{live}}$\r
\EndProcedure\r
\end{algorithmic}\r
\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
-\Function{GetValFromKey}{$k_g$}\r
+\Function{Get}{$k_g$} \Comment{Interface function to get a value}\r
\State $\tuple{k_s,v_s} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \r
\in DT \land k = k_g$\r
\State \Return{$v_s$}\r
\subsubsection{Writing Slots}\r
\textbf{States} \\\r
\textit{$cp$ = 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
-%collision in reinserting the last slot (sent in the following slot)} \\\r
\textit{$ck_p$ = counter of $kv \in KV$ for putting pairs (initially 0)} \\\r
\textit{$ck_g$ = counter of $kv \in KV$ for getting pairs (initially 0)} \\\r
\textit{$cs_p$ = counter of $ss \in SS$ for putting pairs (initially 0)} \\\r
\textit{$cs_g$ = counter of $ss \in SS$ for getting pairs (initially 0)} \\\r
\textit{$cc_p$ = counter of $cr \in CR$ for putting pairs (initially 0)} \\\r
\textit{$cc_g$ = counter of $cr \in CR$ for getting pairs (initially 0)} \\\r
-\textit{$hmac_{c_p}$ = the HMAC value of the current slot} \\\r
+\textit{$hmac_{c_p}$ = the HMAC value of the current slot in procedure \r
+$\Call{PutDataEntries}{}$} \\\r
\textit{$hmac_{p_p}$ = the HMAC value of the previous slot \r
-($hmac_{p_p} = \emptyset$ for the first slot)} \\\r
+($hmac_{p_p} = \emptyset$ for the first slot) in procedure \r
+$\Call{PutDataEntries}{}$} \\\r
\textit{$id_{self}$ = machine Id of this client} \\\r
\textit{$sl_{last}$ = info of last slot in queue = \r
$\tuple{s_{last},sv_{last},id_{last}}$ (initially $\emptyset$)} \\\r
+\textit{$sz$ = expected size of received slots from server} \\\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{$reinsert_{qs}$ = boolean to decide $qs$($max_g$) reinsertion} \\\r
$CreateQS(max'_s)=qs_s$ \\\r
$CreateCR(s_s,id_s)=\tuple{s_s,id_s} = cr_s$ \\\r
$Encrypt(Dat_s,SK_s)=sv_s$ \\\r
-$GetLastS(sl = \tuple{s,sv,id})=s$ \\\r
-$GetSV(sl = \tuple{s,sv,id})=sv$ \\\r
-$GetID(sl = \tuple{s,sv,id})=id$ \\\r
$GetColSeqN(SL_s,s_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 = s_s$ \\\r
$GetKVPair(KV_s,k_s)= \tuple{ck,\tuple{k, v}}$ \textit{such that} \r
\forall \tuple{ck_s,\tuple{k_s, v_s}} \in KV_s, k = k_s$ \\\r
\r
\begin{algorithmic}[1]\r
-\Function{PutKVPair}{$KV_s,\tuple{k_s,v_s}$}\r
-\State $\tuple{ck_s,\tuple{k_s,v_t}} \gets GetKVPair(KV,k_s)$\r
+\Function{Put}{$KV_s,\tuple{k_s,v_s}$} \Comment{Interface function to update a key-value pair}\r
+\State $\tuple{ck_s,\tuple{k_s,v_t}} \gets GetKVPair(KV_s,k_s)$\r
\If{$\tuple{ck_s,\tuple{k_s,v_t}} = \emptyset$}\r
\State $KV_s \gets KV_s \cup \{\tuple{ck_p, \tuple{k_s,v_s}}\}$\r
\State $ck_p \gets ck_p + 1$\r
\r
\begin{algorithmic}[1]\r
\Function{HandleCollision}{$SL_s,s_s$}\r
+\If{$SL_s = \emptyset$}\r
+ \State \Call{Error}{'No slots received from server'}\r
+\EndIf\r
\State $\tuple{s_{col},sv_{col}} \gets GetColSeqN(SL_s,s_s)$\r
\State $Dat_{col} \gets Decrypt(SK,sv_{col})$\r
\State $id_{col} \gets GetMacId(Dat_{col})$\r
\ForAll{$de_s \in DE_s$}\r
\State $live \gets \Call{CheckLiveness}{s_s,de_s}$\r
\If{$live$}\r
- \If{$de_s = kv$}\r
+ \If{$type(de_s) = ``kv"$}\r
\State $\tuple{k_s,v_s} \gets GetKV(de_s)$\r
\State $KV \gets \Call{PutKVPair}{KV,\tuple{k_s,v_s}}$\r
- \ElsIf{$de_s = ss$}\r
+ \ElsIf{$type(de_s) = ``ss"$}\r
\State $\tuple{id_s,s_{s_{last}}} \gets GetSS(de_s)$\r
\State $SS \gets \Call{PutSSPair}{SS,\tuple{id_s,s_{s_{last}}}}$\r
- \ElsIf{$de_s = cr$}\r
+ \ElsIf{$type(de_s) = ``cr"$}\r
\State $\tuple{s_s,id_s} \gets GetCR(de_s)$\r
\State $CR \gets \Call{PutCRPair}{CR,\tuple{s_s,id_s}}$\r
- \ElsIf{$de_s = qs$}\r
+ \ElsIf{$type(de_s) = ``qs"$}\r
\State $reinsert_{qs} \gets true$\r
\EndIf\r
\EndIf\r
\end{defn}\r
\r
\begin{defn}[Parent]\r
-A parent of a message $\mathsf{t}$ is the message $\mathsf{\mathscr{P}_t}$, \r
+A parent of a message $\mathsf{t}$ is the message $\mathsf{p_t}$, \r
unique by the correctness of HMACs in $\mathsf{Dat_t}$, such that \r
-$\mathsf{hmac_p(t) = hmac_c(\mathscr{P}_t)}$.\r
+$\mathsf{hmac_p(t) = hmac_c(p_t)}$.\r
\end{defn}\r
\r
\begin{defn}[Chain]\r
Transitive closure set at sequence number $\mathsf{s_n}$ is a set \r
$\mathsf{\mathscr{S}}$ of clients comprising a connected component of an \r
undirected graph, where two clients are connected by an edge if they both \r
-received the same message $\mathsf{t}$ with sequence number $\mathsf{s_t > n}$.\r
+received the same message $\mathsf{t}$ with sequence number $\mathsf{s_t > s_n}$.\r
\end{defn}\r
\r
\subsubsection{Lemmas and Proofs}\r
\r
-\begin{prop} \r
+\begin{prop}\r
+\label{prop:parentmessage}\r
Every client $\mathsf{J}$ who sends a message $\mathsf{t}$ \r
-has $\mathsf{\mathscr{P}_t}$ as its latest stored message, and \r
-$\mathsf{s_t = s_{\mathscr{P}_t} + 1}$. \r
+has parent $\mathsf{p_t}$ as its latest stored message, and \r
+$\mathsf{s_t = s_{p_t} + 1}$. \r
\end{prop}\r
\begin{proof} True by definition, because $J$ sets \r
-$\mathsf{hmac_p(t) = hmac_c(\mathscr{P}_t)}$ and \r
-$\mathsf{s_t = }$ $\mathsf{s_{\mathscr{P}_t + 1}}$ when a message \r
+$\mathsf{hmac_p(t) = hmac_c(p_t)}$ and \r
+$\mathsf{s_t = }$ $\mathsf{s_{p_t + 1}}$ when a message \r
is sent. \r
\end{proof}\r
\r
-\begin{prop} If a rejected message entry is added to the set $\mathsf{CR}$ \r
+\begin{prop} \r
+\label{prop:rejectedmessage}\r
+If a rejected message entry is added to the set $\mathsf{CR}$ \r
at sequence number $\mathsf{s}$, the message will remain in $\mathsf{CR}$ \r
until every client has seen it. \r
\end{prop}\r
\begin{figure}[h]\r
\centering\r
\xymatrix{ & & L \\\r
-\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
+\dots \ar[r] & q \ar[dr]_{J} \ar[r]^{K} & l_1 \ar[r] & l_2 \ar[r] & \dots \ar[r] & m \ar[r] & \dots \ar[r] & l_n = u \\\r
& & r_1 \ar[r] & r_2 \ar[r] & \dots \ar[r] & r_m = t \\\r
& & R\r
\save "2,3"."2,8"*+\frm{^\}}\r
\restore\r
\restore\r
}\r
-\caption{By Lemma 1, receiving $t$ after $u$ is impossible.}\r
+\caption{By \textbf{Lemma \ref{lem:twomessages}}, receiving both $t$ and $u$ here is impossible.}\r
\end{figure}\r
\r
-\begin{lem} Two messages are received without errors by a client $\mathsf{C}$; \r
+\begin{lem}\r
+\label{lem:twomessages}\r
+Two messages are received without errors by a client $\mathsf{C}$; \r
call them $\mathsf{t}$ and $\mathsf{u}$ such that $\mathsf{s_t \le s_u}$. \r
Then $\mathsf{t}$ is in the path of $\mathsf{u}$. \r
\end{lem}\r
\begin{proof}\r
+Assume that there are some pairs of messages $\mathsf{(t,u)}$ that violate this lemma. \r
+Take a specific $\mathsf{(t,u)}$ such that $\mathsf{s_u}$ is minimized, and \r
+$\mathsf{s_t}$ is maximized for this choice of $\mathsf{s_u}$. We will show that $\mathsf{C}$\r
+cannot receive both $\mathsf{t}$ and $\mathsf{u}$ without throwing an error.\r
+\r
Clearly $\mathsf{C}$ will throw an error if $\mathsf{s_t = s_u}$. So \r
$\mathsf{s_t < s_u}$. Additionally, if $\mathsf{C}$ receives $\mathsf{u}$ before \r
$\mathsf{t}$, this will cause it to throw an error, so $\mathsf{t}$ is received \r
-before $\mathsf{u}$.\r
-\r
-Assume that $\mathsf{t}$ is not in the path of $\mathsf{u}$. Take $\mathsf{u}$ \r
-to be the packet of smallest sequence number for which this occurs, and \r
-$\mathsf{t}$ be the packet with greatest sequence number for this $\mathsf{u}$. \r
-We will prove that an error occurs upon receipt of $\mathsf{u}$.\r
+before $\mathsf{u}$. We will prove that an error occurs upon receipt of $\mathsf{u}$.\r
\r
Let $\mathsf{r_1}$ be the earliest member of the path of $\mathsf{t}$ that is \r
not in the path of $\mathsf{u}$, and $\mathsf{q}$ be its parent. Message \r
$\mathsf{q}$, the last common ancestor of $\mathsf{t}$ and $\mathsf{u}$, must exist, \r
since all clients and the server were initialized with the same state. Let \r
$\mathsf{l_1}$ be the successor of $\mathsf{q}$ that is in the path of $\mathsf{u}$; \r
-we know $\mathsf{l_1 \neq r_1}$. Let $\mathsf{R = (r_1, r_2, \dots, r_m = t)}$ be \r
+we know $\mathsf{l_1 \neq r_1}$. Let $\mathsf{R = (r_1, r_2, \dots, r_{|R|} = t)}$ be \r
the distinct portion of the path of $\mathsf{t}$, and similarly let $\mathsf{L}$ \r
-be the distinct portion of the path of $\mathsf{l_n = u}$.\r
+be the distinct portion of the path of $\mathsf{l_{|L|} = u}$.\r
\r
Let $\mathsf{J}$ be the client who sent $\mathsf{r_1}$; that is, such that \r
$\mathsf{{id_{self}}_J = GetMacID(r_1)}$, and $\mathsf{K}$ be the client who \r
-sent $\mathsf{l_1}$.\r
-\r
-We know the following three facts: \r
+sent $\mathsf{l_1}$. Because no client can send two messages with the same sequence number, and \r
+$\mathsf{s_{r_1} = s_{l_1} = s_q + 1}$, $\mathsf{J \neq K}$.\r
\r
-\begin{enumerate}\r
+We also know the following facts: \r
\r
-\item Because no client can send two messages with the same sequence number, and \r
-$\mathsf{s_{r_1} = s_{l_1} = s_q + 1}$, $\mathsf{J \neq K}$.\r
+\begin{prop} \r
+\label{prop:bothmessages}\r
+No client sends both a message in $\mathsf{(r_2,...,t)}$ and a message in $\mathsf{(l_2,...,u)}$. \r
+\end{prop}\r
\r
-\item To send a message $\mathsf{p}$ that is the parent of some other \r
+\begin{proof}\r
+To send a message $\mathsf{p}$ that is the parent of some other \r
message, one must have received the parent of $\mathsf{p}$. Since \r
$\mathsf{u}$ is the message with smallest sequence number received by any \r
-client that violates this lemma, no client receives both a message in $\mathsf{r}$ \r
-and a message in $\mathsf{l}$; therefore, no client sends both a message in \r
-$\mathsf{(r_2,...,t)}$ and a message in $\mathsf{(l_2,...,u)}$.\r
+client that violates Lemma \ref{lem:twomessages}, no client receives both a message \r
+in $\mathsf{r}$ and a message in $\mathsf{l}$. \r
+\end{proof}\r
\r
-\item Since $\mathsf{u}$ is the message with the greatest- and least- sequence \r
-number that violates this lemma, $\mathsf{C}$ does not receive any message with \r
-sequence number strictly between $\mathsf{s_t}$ and $\mathsf{s_u}$. Because the \r
-$\mathsf{s_{last}}$ that $\mathsf{C}$ stores increases at every message receipt \r
-event, $\mathsf{C}$ also does not receive any message after $\mathsf{t}$ and before \r
-$\mathsf{u}$ in real time.\r
+\begin{prop} \r
+\label{prop:seqnumb}\r
+$\mathsf{C}$ does not receive any message with a\r
+sequence number strictly between $\mathsf{s_t}$ and $\mathsf{s_u}$. \r
+\end{prop}\r
+\r
+\begin{proof} If there were such a message with sequence number smaller than \r
+$\mathsf{s_u}$, it would contradict the assumption that $\mathsf{u}$ is the \r
+message with the least sequence number that violates Lemma \ref{lem:twomessages}. \r
+\end{proof}\r
\r
-\end{enumerate}\r
There are two cases:\r
\begin{itemize}\r
-\item Case 1: $\mathsf{J}$ did not send a message in $\mathsf{L}$. Then \r
-%$\mathsf{v_J(t) > v_J(q) = v_J(u)}$.\r
-$\mathsf{s_{t_J} > s_{q_J} = s_{u_J}}$.\r
+\item Case 1: $\mathsf{J}$ did not send a message in $\mathsf{L}$. Then, where $\mathsf{s_{t_J}}$ \r
+is the greatest sequence number of the messages that client $\mathsf{J}$ sent in \r
+the path of message $\mathsf{t}$, $\mathsf{s_{t_J} > s_{q_J} = s_{u_J}}$.\r
\begin{itemize}\r
\item Case 1.1: $\mathsf{C}$ never updates its slot sequence list $\mathsf{SS}$ \r
between receiving $\mathsf{t}$ and receiving $\mathsf{u}$; this can only happen if \r
$\mathsf{s_t = s_u - 1}$. Since $\mathsf{t}$ is not the parent of $\mathsf{u}$, \r
-$\mathsf{hmac_p(u) \neq hmac_c(t)}$, causing $\mathsf{C}$ to error.\r
+$\mathsf{hmac_p(u) \neq hmac_c(t)}$, causing $\mathsf{C}$ to throw an error.\r
\item Case 1.2: Case 1.1 does not occur; therefore, $\mathsf{C}$ must update \r
its slot sequence list $\mathsf{SS}$ at some point between receiving $\mathsf{t}$ \r
and $\mathsf{u}$. \r
The latest sequence number of $\mathsf{J}$ decreases during this time, which \r
means it must decrease when some message is received, which means $\mathsf{C}$ \r
-throws an error in the $\mathsf{CheckLastSeqN}$ subroutine.\r
+throws an error in the $\mathsf{CheckLastSeqN()}$ subroutine.\r
\end{itemize}\r
\r
\item Case 2: $\mathsf{J}$ sent at least one message in $\mathsf{L}$. Call the \r
-first one $\mathsf{p}$. We know that $\mathsf{s_p > s_{r_1}}$, since \r
-$\mathsf{J \neq K}$ and $\mathsf{p \neq l_1}$. Message $\mathsf{r_1}$ must be sent \r
-either before or after $\mathsf{p}$.\r
+first one $\mathsf{m}$. We know that $\mathsf{s_m > s_{r_1}}$, since \r
+$\mathsf{J \neq K}$ and $\mathsf{m \neq l_1}$. Message $\mathsf{r_1}$ must be sent \r
+either before or after $\mathsf{m}$.\r
\begin{itemize}\r
-\item Case 2.1: Client $\mathsf{J}$ sends $\mathsf{p}$, and then $\mathsf{r_1}$. \r
-Before sending $\mathsf{p}$, the greatest sequence number of a message that \r
+\item Case 2.1: Client $\mathsf{J}$ sends $\mathsf{m}$, and then $\mathsf{r_1}$. \r
+Before sending $\mathsf{m}$, the greatest sequence number of a message that \r
$\mathsf{J}$ has received, $\mathsf{{s_{last}}_J}$, must be equal to \r
-$\mathsf{s_p - 1 \ge s_{r_1}}$. Since $\mathsf{{s_{last}}_J}$ never decreases, \r
+$\mathsf{s_m - 1 \ge s_{r_1}}$. Since $\mathsf{{s_{last}}_J}$ never decreases, \r
client $\mathsf{J}$ cannot then send a message with sequence number \r
$\mathsf{s_{r_1}}$, a contradiction.\r
-\item Case 2.2: Client $\mathsf{J}$ sends $\mathsf{r_1}$, and then $\mathsf{p}$. \r
-Let $\mathsf{X = (r_1, \dots )}$ be the list of messages $\mathsf{J}$ sends \r
-starting before $\mathsf{r_1}$ and ending before $p$.\r
+\item Case 2.2: Client $\mathsf{J}$ sends $\mathsf{r_1}$, and then $\mathsf{m}$. \r
+Let $\mathsf{X = (r_1 = x_1, \dots , x_n)}$ be the list of messages $\mathsf{J}$ sends \r
+starting before $\mathsf{r_1}$ and ending before $m$; clearly these all have sequence \r
+number $\mathsf{s_p = s_q + 1}$.\r
\begin{itemize}\r
-\item Case 2.2.1: Some message in $\mathsf{X}$ was accepted. Let $\mathsf{s_{w_J}}$ \r
-be the greatest sequence number of the messages that client $\mathsf{J}$ sent in \r
-the path of message $\mathsf{w}$. In this case, before sending $\mathsf{p}$, \r
-$\mathsf{J}$'s value in $\mathsf{SM_J}$ for its own latest sequence number would \r
+\item Case 2.2.1: Some message in $\mathsf{X}$ was accepted. Before sending $\mathsf{m}$, \r
+$\mathsf{J}$'s value in $\mathsf{MS_J}$ for its own latest sequence number would \r
be strictly greater than $\mathsf{s_{q_J}}$. If there is a sequence of messages with \r
contiguous sequence numbers that $\mathsf{J}$ receives between $\mathsf{r_1}$ and \r
-$\mathsf{p}$, $\mathsf{J}$ throws an error for a similar reason as Case 1.1. Otherwise, \r
-when preparing to send $\mathsf{p}$, $\mathsf{J}$ would have received an update of its \r
+$\mathsf{m}$, $\mathsf{J}$ throws an error for a similar reason as Case 1.1. Otherwise, \r
+when preparing to send $\mathsf{m}$, $\mathsf{J}$ would have received an update of its \r
own latest sequence number as at most $\mathsf{s_{q_J}}$. $J$ throws an error before \r
sending $\mathsf{p}$, because its own latest sequence number decreases.\r
-\item Case 2.2.2: All messages in $\mathsf{X}$ were rejected, making $\mathsf{p}$ \r
-the first message of $\mathsf{J}$ that is accepted after $\mathsf{r_1}$. Note that \r
-$\mathsf{u}$ is the message with least sequence number that violates this lemma, and \r
-therefore the first one that $\mathsf{C}$ receives after $\mathsf{t}$. Therefore, \r
+\item Case 2.2.2: All messages in $\mathsf{X}$ were rejected, making $\mathsf{m}$ \r
+the first message of $\mathsf{J}$ that is accepted after $\mathsf{r_1}$.\r
+\r
+We will show that $\mathsf{C}$ sees $\mathsf{r_1}$. Assume not. Then $\mathsf{(r_2, ..., u)}$ \r
+must have at least $\mathsf{{max_g}_C} \geq 2$ messages for $\mathsf{r_1}$ to fall off the \r
+end of the queue. Consider the sender of $\mathsf{r_3}$ and call it $\mathsf{H}$. \r
+$\mathsf{H \neq J}$ by Proposition \ref{prop:bothmessages} and the existence of $\mathsf{m}$. \r
+Since $\mathsf{H \neq J}$, then by Proposition \ref{prop:bothmessages} it could not also \r
+have sent a message in $\mathsf{(l_2,..., u)}$. Therefore, $\mathsf{s_{u_H} < s_q + 2 = s_{t_H}}$, \r
+so upon receipt of $\mathsf{u}$, $\mathsf{C}$ will throw an error by the decrease in a \r
+last sequence number similar to Case 1, a contradiction.\r
+\r
+Now that we know that $\mathsf{C}$ sees $\mathsf{r_1}$, note that C receives $\mathsf{u}$ \r
+immediately after $\mathsf{t}$ by Proposition \ref{prop:seqnumb}. Therefore, \r
$\mathsf{C}$ could not have seen a message after $\mathsf{t}$ with sequence number less \r
-than $\mathsf{s_p}$. In the $\mathsf{PutDataEntries}$ subroutine, $\mathsf{J}$ adds every \r
-%TODO: Check with Thomas about this part\r
-rejected message to $\mathsf{CR(p)}$; so for every $\mathsf{s}$, $\mathsf{1 \leq s < |X|}$, \r
-the $\mathsf{s}$-th element of $\mathsf{X}$ will be recorded in the rejected message list\r
-$\mathsf{CR}$ of all further elements of $\mathsf{X}$; and every element of \r
-$\mathsf{X}$ will be recorded in $\mathsf{CR_C(p)}$. Since every rejected message in \r
-$\mathsf{CR(p)}$ will be in $\mathsf{CR_C(u)}$, ${r_1}$ will be recorded in \r
-$\mathsf{CR_C(p)}$. When $\mathsf{C}$ receives $\mathsf{u}$, $\mathsf{C}$ will throw \r
-an error from the match $\mathsf{\tuple{s_q+1, id_J}}$ in $\mathsf{CR_C(p)}$.\r
-\item Case 2.2.2.1: \r
+than $\mathsf{s_m}$. In the $\mathsf{PutDataEntries()}$ subroutine, $\mathsf{J}$ adds every \r
+$\mathsf{cr}$ entry that contains sequence number $\mathsf{s}$ and machine ID \r
+$\mathsf{id}$ of the messsages that win in the collisions before $\mathsf{m}$ into \r
+$\mathsf{CR}$; $\mathsf{CR}$ keeps the collection of live $\mathsf{cr}$ entries, namely\r
+those which not all clients have seen. Hence, for every $\mathsf{i}$, $\mathsf{1 \leq i < |X|}$, \r
+the collision winner that has collided with $\mathsf{x_i}$ will be recorded appropriately. Since all the $\mathsf{cr}$ entries that record the results of the collisions before $\mathsf{p}$ will also be seen when $\mathsf{u}$ \r
+is received, and $\mathsf{C}$ sees $\mathsf{r_1}$, ${l_1}$ will be recorded in a $\mathsf{cr}$ entry as the winner in the \r
+collision against ${r_1}$.\r
+\r
+When $\mathsf{C}$ receives $\mathsf{u}$, if $\mathsf{C}$ \r
+has seen the $\mathsf{cr}$ entry that records the collision at index $\mathsf{s_q + 1}$, it will throw \r
+an error from the mismatch of $\mathsf{\tuple{s_q+1, id_J}}$ with \r
+$\mathsf{\tuple{s_q+1, id_K}}$ in the corresponding $\mathsf{cr}$ entry.\r
+\r
\end{itemize}\r
\end{itemize}\r
\r
\end{itemize}\r
\end{proof}\r
\r
-\begin{lem} If there are two packets $\mathsf{t}$ and $\mathsf{u}$, with \r
+\begin{lem} \r
+\label{lem:pathmessages}\r
+If there are two messages $\mathsf{t}$ and $\mathsf{u}$, with \r
$\mathsf{s_t \leq s_u}$, such that $\mathsf{t}$ is in the path of $\mathsf{u}$, \r
then for any message $\mathsf{p}$ with $\mathsf{s_p \leq s_t}$, iff $\mathsf{p}$ is in \r
the path of $\mathsf{t}$, it is in the path of $\mathsf{u}$. \r
set, with partial sequence $\mathsf{P_{C_1}}$, and let $\mathsf{u}$ be some message with \r
$\mathsf{s_u > s_n}$ that $\mathsf{C_1}$ shares with another client. Then let $\mathsf{T}$ \r
be the portion of the path of $\mathsf{u}$ ending at sequence number $\mathsf{s_n}$ and \r
-$\mathsf{t}$ be the message at that sequence number. Clearly, by Lemma 1, $\mathsf{P_{C_1}}$ \r
-is consistent with $\mathsf{T}$. We will show that, for every other client $\mathsf{D}$ \r
-with partial sequence $\mathsf{P_D}$, $\mathsf{P_D}$ has some message whose path includes \r
-$\mathsf{t}$. Because $\mathsf{D}$ is in the transitive closure, there is a sequence of \r
-clients $\mathsf{\mathscr{C} = (C_1, C_2, ..., D)}$ from $\mathsf{C_1}$ to $\mathsf{D}$, \r
+$\mathsf{t}$ be the message at that sequence number. Clearly, by Lemma \ref{lem:twomessages}, \r
+$\mathsf{P_{C_1}}$ is consistent with $\mathsf{T}$. We will show that, for every other client \r
+$\mathsf{D}$ with partial sequence $\mathsf{P_D}$, $\mathsf{P_D}$ has some message whose path \r
+includes $\mathsf{t}$. Because $\mathsf{D}$ is in the transitive closure, there is a sequence \r
+of clients $\mathsf{\mathscr{C} = (C_1, C_2, ..., D)}$ from $\mathsf{C_1}$ to $\mathsf{D}$, \r
where each shares an edge with the next.\r
We prove by induction that $\mathsf{P_D}$ has a message whose path includes $\mathsf{t}$.\r
\begin{itemize}\r
\item Inductive step: Each client in $\mathsf{\mathscr{C}}$ has a partial sequence with a message \r
that includes $\mathsf{t}$ if the previous client does. Suppose $\mathsf{P_{C_k}}$ has \r
a message $\mathsf{w}$ with a path that includes $\mathsf{t}$, and shares message $\mathsf{x}$ \r
-with $\mathsf{P_{C_{k+1}}}$ such that $\mathsf{s_x > s_n}$. By Lemma 1, $\mathsf{w}$ or \r
-$\mathsf{x}$, whichever has the least sequence number, is in the path of the other, and therefore \r
-by Lemma 2, $\mathsf{t}$ is in the path of $\mathsf{x}$.\r
+with $\mathsf{P_{C_{k+1}}}$ such that $\mathsf{s_x > s_n}$. By Lemma \ref{lem:twomessages}, \r
+$\mathsf{w}$ or $\mathsf{x}$, whichever has the least sequence number, is in the path of the other, \r
+and therefore by Lemma \ref{lem:pathmessages}, $\mathsf{t}$ is in the path of $\mathsf{x}$.\r
\r
\item Let $\mathsf{z}$ be the message of $\mathsf{D}$ whose path includes $\mathsf{t}$. \r
-By Lemma 1, every message in $\mathsf{P_D}$ with sequence number smaller than $\mathsf{s_w}$ \r
-is in the path of $\mathsf{z}$. Since $\mathsf{t}$ is in the path of $\mathsf{z}$, every \r
-message in $\mathsf{P_D}$ with smaller sequence number than $\mathsf{s_t = s_n}$ is in $\mathsf{T}$. \r
+By Lemma \ref{lem:twomessages}, every message in $\mathsf{P_D}$ with sequence number smaller \r
+than $\mathsf{s_w}$ is in the path of $\mathsf{z}$. Since $\mathsf{t}$ is in the path of \r
+$\mathsf{z}$, every message in $\mathsf{P_D}$ with smaller sequence number than \r
+$\mathsf{s_t = s_n}$ is in $\mathsf{T}$. \r
Therefore, $\mathsf{P_D}$ is consistent with $\mathsf{T}$.\r
\r
\end{itemize}\r
projects / iotcloud.git / blobdiff