\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
$MinSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \r
\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\\r
-$SeqN(\tuple{s, sv})=s$ \\\r
-$SlotVal(\tuple{s, sv})=sv$ \\\r
+$SeqN(slot_s = \tuple{s, sv})=s$ \\\r
+$SlotVal(slot_s = \tuple{s, sv})=sv$ \\\r
\r
\begin{algorithmic}[1]\r
\Function{GetSlot}{$s_g$}\r
\State $max \gets max'$\r
\EndIf\r
\State $\tuple{s_n,sv_n} \gets MaxSlot(SL)$\Comment{Last sv}\r
-\State $s_n \gets SeqN(\tuple{s_n,sv_n})$\r
+%\State $s_n \gets SeqN(\tuple{s_n,sv_n})$\r
\If{$(s_p = s_n + 1)$}\r
\If{$n = max$}\r
\State $\tuple{s_m,sv_m} \gets MinSlot(SL)$\Comment{First sv}\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
+$slot_s = \tuple{s, E(Dat_s)} = \r
\tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\\r
\textbf{States} \\\r
\textit{$id_{self}$ = machine Id of this 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
-$GetLivEntLastS(LV_s,de_s)= s$ \textit{such that} $\tuple{de, s} \in LV_s \r
-\wedge \forall \tuple{de_s, s_s} \in LV_s, de_s = de$ \\\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
$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
-$GetS(\tuple{s, id})=s$ \\\r
-$GetId(\tuple{s, id})=id$ \\\r
-$GetKey(\tuple{k, v})=k$ \\\r
-$GetVal(\tuple{k, v})=v$ \\\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
$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
\r
\begin{algorithmic}[1]\r
\Procedure{Error}{$msg$}\r
\r
\begin{algorithmic}[1]\r
\Function{GetSlotSeq}{$DE_s$}\r
-\State $DE_{ss} \gets \{de_s | de_s \in DE_s, de_s \in D \land de_s = ss\}$\r
+\State $DE_{ss} \gets \{de_s | de_s \in DE_s, de_s = ss\}$\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 \in D \land de_s = cr\}$\r
+\State $DE_{cr} \gets \{de_s | de_s \in DE_s, de_s = cr\}$\r
\State \Return{$DE_{cr}$}\r
\EndFunction\r
\end{algorithmic}\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
-\Function{UpdateKVLivEnt}{$LV_s,de_s,s_s$}\r
-\State $s_t \gets GetLivEntLastS(LV_s,de_s)$\r
+\Function{UpdateKVLivEnt}{$LV_s,kv_s,s_s$}\r
+\State $s_t \gets GetLivEntLastS(LV_s,kv_s)$\r
\If{$s_t = \emptyset$}\r
- \State $LV_s \gets LV_s \cup \{\tuple{de_s,s_s}\}$\Comment{First occurrence}\r
+ \State $LV_s \gets LV_s \cup \{\tuple{kv_s,s_s}\}$\Comment{First occurrence}\r
\Else\r
\If{$s_s > s_t$}\Comment{Update entry with a later s}\r
- \State $LV_s \gets (LV_s - \{\tuple{de_s,s_t}\}) \cup \r
- \{\tuple{de_s,s_s}\}$\r
+ \State $LV_s \gets (LV_s - \{\tuple{kv_s,s_t}\}) \cup \r
+ \{\tuple{kv_s,s_s}\}$\r
\EndIf\r
\EndIf\r
\State \Return{$LV_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_s \gets GetCR(de_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
\Function{UpdateSSLivEnt}{$SS_{s_{live}},MS_s$}\r
\State $s_{s_{min}} \gets MinLastSeqN(MS_s)$\r
\ForAll{$ss_s \in SS_{s_{live}}$}\r
- \State $\tuple{id_s,s_{s_{last}}} \gets GetSS(ss_s)$\r
+ \State $s_{s_{last}} \gets GetSLast(ss_s)$\r
\If{$s_{s_{min}} > s_{s_{last}}$}\Comment{Remove if dead}\r
- \State $SS_{s_{live}} \gets SS_{s_{live}} - \{\tuple{id_s,s_{s_{last}}}\}$ \r
+ \State $SS_{s_{live}} \gets SS_{s_{live}} - \{ss_s\}$ \r
\EndIf\r
\EndFor\r
\State \Return{$SS_{s_{live}}$}\r
\Function{UpdateCRLivEnt}{$CR_{s_{live}},MS_s$}\r
\State $s_{s_{min}} \gets MinLastSeqN(MS_s)$\r
\ForAll{$cr_s \in CR_{s_{live}}$}\r
- \State $\tuple{s_s,id_s} \gets GetCR(cr_s)$\r
+ \State $s_s \gets GetS(cr_s)$\r
\If{$s_{s_{min}} > s_s$}\Comment{Remove if dead}\r
- \State $SS_{s_{live}} \gets SS_{s_{live}} - \{\tuple{s_s,id_s}\}$ \r
+ \State $CR_{s_{live}} \gets CR_{s_{live}} - \{cr_s\}$ \r
\EndIf\r
\EndFor\r
\State \Return{$CR_{s_{live}}$}\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\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
+\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$}\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
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
-\Procedure{CheckCollision}{$MS_s,SM_s,\tuple{s_s,id_s}$}\r
-\If{$\tuple{s_s,id_s} \neq \emptyset$}\r
- \State $s_s \gets GetS(\tuple{s_s,id_s})$\r
- \State $id_s \gets GetId(\tuple{s_s,id_s})$\r
+\Procedure{CheckCollision}{$MS_s,SM_s,cr_s$}\r
+\If{$cr_s \neq \emptyset$}\r
+ \State $s_s \gets GetS(cr_s)$\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,\tuple{s_s,id_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,\tuple{s_t,id_t}$}\Comment{Check $id_s$ in $SM_s$}\r
-\State $id_s \gets SM_s[s_t]$\r
-\If{$id_s \neq id_t$}\r
- \State \Call{Error}{'Invalid $id_s$ for this slot update'}\r
-\EndIf\r
-\EndProcedure\r
-\end{algorithmic}\r
-\r
\begin{algorithmic}[1]\r
\Function{StoreLastSlot}{$MS_s,sl_l,s_s,sv_s,id_s$}\r
\State $s_{min} \gets MinLastSeqN(MS_s)$\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 $LV_s \gets \Call{UpdateKVLivEnt}{LV_s,de_s,s_s}$\r
- \If{$de_s$ \textit{such that} $de_s \in D \land de_s = kv$}\r
- \State $\tuple{k_s,v_s} \gets GetKV(de_s)$\r
- \State $\tuple{k_s,v_t} \gets GetKeyVal(DT_s,k_s)$\r
- \If{$\tuple{k_s,v_t} = \emptyset$}\r
- \State $DT_s \gets DT_s \cup \{\tuple{k_s,v_s}\}$\r
- \Else\r
- \State $DT_s \gets (DT_s - \{\tuple{k_s,v_t}\}) \cup \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
+ \State $\tuple{k_s,v_t} \gets GetKeyVal(DT_s,k_s)$\r
+ \If{$\tuple{k_s,v_t} = \emptyset$}\r
+ \State $DT_s \gets DT_s \cup \{\tuple{k_s,v_s}\}$\r
+ \Else\r
+ \State $DT_s \gets (DT_s - \{\tuple{k_s,v_t}\}) \cup \r
\{\tuple{k_s,v_s}\}$\r
- \EndIf\r
- \EndIf\r
+ \EndIf\r
\EndFor\r
\State \Return{$DT_s$}\r
\EndFunction\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_{max}},sv_{g_{max}}} \gets MaxSlot(SL_g)$\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
\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_{curr} \gets SM_{curr} \cup \{\tuple{s_g,id_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
\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 $\tuple{s_e,id_e} \gets GetCR(de_{g_{cr}})$\r
- \State $\Call{CheckCollision}{MS,SM,\tuple{s_e,id_e}}$\r
- \State $CR_{live} \gets \Call{AddCRLivEnt}{SS_{live},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
+ \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
+%\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 queue size exceeds $max_g$'}\r
+ \State \Call{Error}{'Actual $SL$ size on server exceeds $max_g$'}\r
\EndIf\r
\State $\Call{CheckLastSeqN}{MS_g,MS}$\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
\subsubsection{Writing Slots}\r
-\textbf{Data Entry} \\\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
-$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{$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{$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
\EndFunction\r
\end{algorithmic}\r
\r
+\begin{algorithmic}[1]\r
+\Function{PutSSPair}{$SS_s,\tuple{id_s,s_{s_{last}}}$}\Comment{Insert a set of $ss$ entries}\r
+\State $SS_s \gets SS_s \cup \{\tuple{cs_p, \tuple{id_s,s_{s_{last}}}}\}$\r
+\State $cs_p \gets cs_p + 1$\r
+\State \Return{$SS_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{PutCRPair}{$CR_s,\tuple{s_s,id_s}$}\Comment{Insert a set of $cr$ entries}\r
+\State $CR_s \gets CR_s \cup \{\tuple{cc_p, \tuple{s_s,id_s}}\}$\r
+\State $cc_p \gets cc_p + 1$\r
+\State \Return{$CR_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
\begin{algorithmic}[1]\r
\Function{CheckResize}{$MS_s,th_s,max_t,m'_s$}\r
\State $s_{last_{min}} \gets MinLastSeqN(MS_s)$\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
-\Function{CheckNeedSS}{$MS_s,max_t$}\Comment{Check if $ss$ is needed}\r
+\Function{CheckSLFull}{$MS_s,max_t$}\Comment{Check if $ss$ is needed}\r
\State $s_{last_{min}} \gets MinLastSeqN(MS_s)$\r
\State $s_{last_{max}} \gets MaxLastSeqN(MS_s)$\r
\State $n_{live} \gets s_{last_{max}} - s_{last_{min}}$\Comment{Number of live slots}\r
\EndFunction\r
\end{algorithmic}\r
\r
-%\begin{algorithmic}[1]\r
-%\Function{AddSlotSeq}{$DE_s,SS_s,cp_s$}\Comment{Insert a $ss$}\r
-%\State $DE_{ret} \gets DE_s \cup SS_s$\r
-%\State $cp_s \gets cp_s - |SS_s|$\r
-%\State \Return{$\tuple{DE_{ret},cp_s}$}\r
-%\EndFunction\r
-%\end{algorithmic}\r
-\r
-\begin{algorithmic}[1]\r
-\Function{PutSSPair}{$SS_s,\tuple{id_s,s_{s_{last}}}$}\Comment{Insert a set of $ss$ entries}\r
-\State $SS_s \gets SS_s \cup \{\tuple{cs_p, \tuple{id_s,s_{s_{last}}}}\}$\r
-\State $cs_p \gets cs_p + 1$\r
-\State \Return{$SS_s$}\r
-\EndFunction\r
-\end{algorithmic}\r
-\r
-\begin{algorithmic}[1]\r
-\Function{PutCRPair}{$CR_s,\tuple{s_s,id_s}$}\Comment{Insert a set of $cr$ entries}\r
-\State $CR_s \gets CR_s \cup \{\tuple{cc_p, \tuple{s_s,id_s}}\}$\r
-\State $cc_p \gets cc_p + 1$\r
-\State \Return{$CR_s$}\r
-\EndFunction\r
-\end{algorithmic}\r
-\r
\begin{algorithmic}[1]\r
\Function{AddQueSta}{$DE_s,max'_s,cp_s$}\Comment{Insert a $qs$}\r
\State $DE_{ret} \gets \emptyset$\r
\State $qs_s \gets max'_s$\r
-\State $DE_{ret} \gets DE_s \cup qs_s$\r
+\State $DE_{ret} \gets DE_s \cup \{qs_s\}$\r
\State $cp_s \gets cp_s - 1$\r
\State \Return{$\tuple{DE_{ret},cp_s}$}\r
\EndFunction\r
\end{algorithmic}\r
\r
-%\begin{algorithmic}[1]\r
-%\Function{AddColRes}{$DE_s,CR_s,cp_s$}\Comment{Insert a $cr$}\r
-%\State $DE_{ret} \gets \emptyset$\r
-%\State $DE_{ret} \gets DE_s \cup CR_s$\r
-%\State $cp_s \gets cp_s - |CR_s|$\r
-%\State \Return{$\tuple{DE_{ret},cp_s}$}\r
-%\EndFunction\r
-%\end{algorithmic}\r
-\r
\begin{algorithmic}[1]\r
\Function{GetKVPairs}{$DE_s,KV_s,cp_s$}\r
\State $DE_{ret} \gets \emptyset$\r
\If{$|SS_s| \leq cp_s$}\Comment{$SS$ set can span multiple slots}\r
\State $DE_{ret} \gets DE_s \cup\r
\{\tuple{id_s,s_{s_{last}}} \mid \tuple{cs_s,\tuple{id_s,s_{s_{last}}}} \in SS_s\}$\r
+ \State $cp_s \gets cp_s - |SS_s|$\r
\Else\r
\State $DE_{ret} \gets DE_s \cup\r
\{\tuple{id_s,s_{s_{last}}} \mid \tuple{cs_s,\tuple{id_s,s_{s_{last}}}} \in SS_s,\r
cs_g \leq cs_s < cs_g + cp_s\}$\r
+ \State $cp_s \gets 0$\r
\EndIf\r
-\State $cp_s \gets cp_s - |SS_s|$\r
\State \Return{$\tuple{DE_{ret},cp_s}$}\r
\EndFunction\r
\end{algorithmic}\r
\If{$|CR_s| \leq cp_s$}\Comment{$CR$ set can span multiple slots}\r
\State $DE_{ret} \gets DE_s \cup\r
\{\tuple{s_s,id_s} \mid \tuple{cc_s,\tuple{s_s,id_s}} \in CR_s\}$\r
+ \State $cp_s \gets cp_s - |CR_s|$\r
\Else\r
\State $DE_{ret} \gets DE_s \cup\r
\{\tuple{s_s,id_s} \mid \tuple{cc_s,\tuple{s_s,id_s}} \in CR_s,\r
cc_g \leq cc_s < cc_g + cp_s\}$\r
+ \State $cp_s \gets 0$\r
\EndIf\r
-\State $cp_s \gets cp_s - |CR_s|$\r
\State \Return{$\tuple{DE_{ret},cp_s}$}\r
\EndFunction\r
\end{algorithmic}\r
\State $s_p \gets MaxLastSeqN(MS)$\r
\State $cp_p \gets cp$\r
\State $max'_p \gets \Call{CheckResize}{MS,th_p,max_g,m'_p}$\r
- \If{$max'_p \neq \emptyset$}\r
- \State $\tuple{DE_p,cp_p} \gets \Call{AddQueSta}{DE_p,max'_p,cp_p}$\Comment{Add qs}\r
+ \If{$max'_p \neq \emptyset$}\Comment{Add a qs entry}\r
+ \State $\tuple{DE_p,cp_p} \gets \Call{AddQueSta}{DE_p,max'_p,cp_p}$\r
+ \State $reinsert_{qs} \gets false$\r
\Else\Comment{Check if there is $qs$ reinsertion}\r
\If{$reinsert_{qs}$}\r
\State $\tuple{DE_p,cp_p} \gets \Call{AddQueSta}{DE_p,max_g,cp_p}$\r
\State $CR \gets \Call{PutCRPair}{CR,\tuple{s_{p_{col}},id_{p_{col}}}}$\r
\EndIf\r
\EndWhile\r
-\If{$|DE_p| = cp$}\Comment{Middle of set}\r
- \State $ck_g \gets ck_g + cp_s$\r
+\State $MS \gets \Call{UpdateLastSeqN}{id_{self},s_p,MS}$\r
+\If{$|DE_p| = cp$}\Comment{Update set counters}\r
+ \State $ck_g \gets ck_g + cp_p$\Comment{Middle of set}\r
\State $cs_g \gets cs_g + |SS|$\r
\State $cc_g \gets cc_g + |CR|$\r
\Else\Comment{End of set}\r
\State $cs_g \gets 0$\r
\State $cc_g \gets 0$\r
\EndIf\r
-\State $MS \gets \Call{UpdateLastSeqN}{id_{self},s_p,MS}$\r
-\State $need_p \gets \Call{CheckNeedSS}{MS,max_g}$\r
-\If{$need_p$}\r
- \State $\Call{CheckLastSlot}{sl_{last}}$\Comment{Get ready to expunge first slot}\r
+\State $need_p \gets \Call{CheckSLFull}{MS,max_g}$\r
+\If{$need_p$}\Comment{SL on server is full}\r
+ \State $\Call{CheckLastSlot}{sl_{last}}$\Comment{Salvage entries from expunged slot}\r
\State $ss_p \gets \Call{CreateSlotSeq}{sl_{last}}$\r
\State $\tuple{id_p,s_{p_{last}}} \gets GetSS(ss_p)$\r
\State $SS \gets \Call{PutSSPair}{SS,\tuple{id_p,s_{p_{last}}}}$\Comment{Add ss}\r
%\note{Also Missing liveness state definition in algorithm...}\r
\r
\r
-\subsection{Definitions for Formal Guarantees}\r
-\r
-\begin{enumerate}\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 $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}$.\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$.\r
-\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.\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 $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
-\subsection{Formal Guarantee}\r
-\r
-\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}\r
-\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}\r
+\subsection{Formal Guarantees}\r
+\subsubsection{Definitions}\r
+\r
+\begin{defn}[Message]\r
+A message $\mathsf{t}$, is the tuple \r
+\begin{center}\r
+$\mathsf{t = \tuple{s, E(Dat_s)}}$ \\\r
+$\mathsf{Dat_t = \tuple{s,id,hmac_p, DE,hmac_c}}$\r
+\end{center}\r
+containing $\mathsf{s}$ as sequence number and $\mathsf{Dat_t}$ as its \r
+encrypted contents. $\mathsf{Dat_t}$ consists of $\mathsf{s}$, \r
+$\mathsf{id}$ as machine ID of the sender, $\mathsf{hmac_p}$ as HMAC \r
+from a previous message, $\mathsf{DE}$ as set of data entries, and \r
+$\mathsf{hmac_c}$ as HMAC from message $\mathsf{t}$ respectively.\r
+\end{defn}\r
+\r
+\begin{defn}[Equality]\r
+Two messages $\mathsf{t}$ and $\mathsf{u}$ are equal if their $\mathsf{s}$, \r
+and $\mathsf{Dat_t}$ are exactly the same.\r
+\end{defn}\r
+\r
+\begin{defn}[Parent]\r
+A parent of a message $\mathsf{t}$ is the message $\mathsf{\mathscr{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
+\end{defn}\r
+\r
+\begin{defn}[Chain]\r
+A chain of messages with length $\mathsf{n \ge 1}$ is a message sequence \r
+$\mathsf{R = (r_s, r_{s+1}, ..., r_{s+n-1})}$ such that for every sequence \r
+number $\mathsf{s < k \le s+n-1}$, $\mathsf{r_k}$ has sequence number \r
+$\mathsf{k}$ and is the parent of $\mathsf{r_{k-1}}$.\r
+\end{defn}\r
+\r
+\begin{defn}[Partial sequence]\r
+A partial sequence $\mathsf{P}$ is a sequence of messages, no two \r
+with the same sequence number, that can be divided into disjoint chains.\r
+\end{defn}\r
+\r
+\begin{defn}[Total sequence]\r
+A total sequence $\mathsf{T =}$ $\mathsf{(t_1, t_2, ..., t_n)}$ with \r
+length $\mathsf{n}$ is a chain of messages that starts at $\mathsf{s = 1}$.\r
+\end{defn}\r
+\r
+\begin{defn}[Path]\r
+The path of a message $\mathsf{t}$ is the chain that starts at $\mathsf{s = 1}$ \r
+and whose last message is $\mathsf{t}$. The uniqueness of a path follows \r
+from the uniqueness of a parent.\r
+\end{defn}\r
+\r
+\begin{defn}[Consistency]\r
+A partial sequence $\mathsf{P}$ is consistent with a total sequence \r
+$\mathsf{T}$ of length $\mathsf{n}$ if for every message $\mathsf{p \in P}$ \r
+with $\mathsf{s_p \leq n}$, $\mathsf{t_{s_p} = p}$. This implies that \r
+$\mathsf{\{p \in P | s_p \le n\}}$ is a partial sequence of $\mathsf{T}$.\r
+\end{defn}\r
+\r
+\begin{defn}[Transitive closure]\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
+\end{defn}\r
+\r
+\subsubsection{Lemmas and Proofs}\r
+\r
+\begin{prop} \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
+\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
+is sent. \r
+\end{proof}\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
+\begin{prop} 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{proof} Every $\mathsf{CR}$ entry $\mathsf{cr}$ remains in the queue until it \r
+reaches the tail, and is refreshed by the next sender $\mathsf{J}$ at that time if \r
+$\mathsf{min(MS) > s_{cr}}$; that is, until every client has sent a message with \r
+sequence number greater than $\mathsf{s_{cr}}$. Because every client who sends a \r
+message with sequence number $\mathsf{s}$ has the state of the set $\mathsf{SL}$ at \r
+$\mathsf{s - 1}$, this client will have seen the message at $\mathsf{s_{cr}}$. \r
+\end{proof}\r
\r
\begin{figure}[h]\r
\centering\r
- \xymatrix{ & & S \\\r
-\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
-& & R_1 \ar[r] & R_2 \ar[r] & \dots \ar[r] & R_m = t \\\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
+& & r_1 \ar[r] & r_2 \ar[r] & \dots \ar[r] & r_m = t \\\r
& & R\r
\save "2,3"."2,8"*+\frm{^\}}\r
\save "3,3"."3,6"*+\frm{_\}}\r
\restore\r
\restore\r
}\r
-\caption{By Lemma 1, receiving $u$ after $t$ is impossible.}\r
+\caption{By Lemma 1, receiving $t$ after $u$ is impossible.}\r
\end{figure}\r
\r
-\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}\r
+\begin{lem} 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
-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 greatest 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
-\r
-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$.\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
+\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
+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
+\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
\r
\begin{enumerate}\r
\r
-\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$.\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
\r
-\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)$.\r
+\item 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
\r
-\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.\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
\r
\end{enumerate}\r
-\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)$.\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
\begin{itemize}\r
-\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.\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 during this time, which means it must decrease when some message is received, which means C throws an error in the $CheckLastSeqN$ subroutine.\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
+\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
\end{itemize}\r
\r
-\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$.\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
\begin{itemize}\r
-\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.\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
+\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
+$\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
+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
\begin{itemize}\r
-\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.\r
-\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)$.\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{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
+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
+$\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
+$\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{p}$ 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{s}$, $\mathsf{1 \leq s < |X|}$, \r
+the collision winner that has collided with $\mathsf{s}$-th element of $\mathsf{X}$ \r
+will be recorded in $\mathsf{CR}$. Since all the $\mathsf{cr}$ entries before \r
+$\mathsf{p}$ will also be seen when $\mathsf{u}$ is received, ${l_1}$ will be recorded \r
+in $\mathsf{CR_C}$ as the winner in the collision against ${r_1}$. When $\mathsf{C}$ \r
+receives $\mathsf{u}$, $\mathsf{C}$ will throw an error from the match \r
+$\mathsf{\tuple{s_q+1, id_K}}$ in $\mathsf{CR_C}$.\r
\item Case 2.2.2.1: \r
\end{itemize}\r
\end{itemize}\r
\end{itemize}\r
\end{proof}\r
\r
-\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}\r
+\begin{lem} If there are two packets $\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
+\end{lem}\r
\r
\begin{proof}\r
-If $i(t) = i(u)$ or $i(p) = i(t)$, then we are done, because the two relevant messages are the same.\r
-\r
-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$.\r
-\r
-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$.\r
+If $\mathsf{s_t = s_u}$ or $\mathsf{s_p = s_t}$, then we are done, because the two \r
+relevant messages are the same. If they are different messages, then:\r
+\begin{itemize}\r
+\item Reverse direction: The definition of $\mathsf{t}$ being in the path of \r
+$\mathsf{u}$ is the existence of a message sequence $\mathsf{(\dots, t, \dots, u)}$ \r
+such that each message except $\mathsf{u}$ is the parent of the succeeding message. \r
+The path of $\mathsf{u}$ must contain some message with sequence number $\mathsf{s_p}$; \r
+because $\mathsf{p}$ is in the path of $\mathsf{u}$, this message is $\mathsf{p}$ \r
+itself. The path of $\mathsf{t}$ is then the prefix of this path ending at $\mathsf{t}$, \r
+which clearly contains $\mathsf{p}$.\r
+\r
+\item Forward direction: The path of $\mathsf{t}$ is a substring of the path of \r
+$\mathsf{u}$, so if the path of $\mathsf{t}$ contains $\mathsf{p}$, so does the path \r
+of $\mathsf{u}$.\r
+\end{itemize}\r
\end{proof}\r
\r
\begin{theorem}\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
+Suppose that there is a transitive closure set $\mathsf{\mathscr{S}}$ of clients, \r
+at sequence number $\mathsf{s_n}$. Then there is some total sequence $\mathsf{T}$ of \r
+length $\mathsf{n}$ such that every client $\mathsf{C}$ in $\mathsf{\mathscr{S}}$ \r
+sees a partial sequence $\mathsf{P_C}$ consistent with $\mathsf{T}$. \r
+\end{theorem}\r
\r
\begin{proof}\r
\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) > 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.\r
-\r
-We prove by induction that $P_D$ has a message whose path includes $t$.\r
+The definition of consistency of $\mathsf{P_C}$ with $\mathsf{T}$ is that every message \r
+$\mathsf{p \in P_C}$ with sequence number $\mathsf{s_p \le s_n}$ is equal to the message \r
+in that slot in $\mathsf{T}$. Let $\mathsf{C_1}$ be some client in the transitive closure \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
+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 Base case: $P_{C_1}$ includes $u$, whose path includes $t$.\r
-\r
-\item Inductive step: Each client in $\mathscr{C}$ has a partial message 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$.\r
-\r
-\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$.\r
+\item Base case: $\mathsf{P_{C_1}}$ includes $\mathsf{u}$, whose path includes $\mathsf{t}$.\r
+\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
+\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
+Therefore, $\mathsf{P_D}$ is consistent with $\mathsf{T}$.\r
\r
\end{itemize}\r
\end{proof}\r
projects / iotcloud.git / blobdiff