\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
\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($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
+$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
\begin{algorithmic}[1]\r
\Function{GetQueSta}{$DE_s$}\r
\State $qs_{de} \gets qs$ \textit{such that} $qs \in DE_s, \r
- de_s \in D \land IsQS(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
\r
\begin{algorithmic}[1]\r
\Function{GetSlotSeq}{$DE_s$}\r
-\State $DE_{ss} \gets \{de | de \in DE_s \land IsSS(de)\}$\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 | de \in DE_s \land IsCR(de)\}$\r
+\State $DE_{cr} \gets \{de | de \in DE_s \land IsCr(de)\}$\r
\State \Return{$DE_{cr}$}\r
\EndFunction\r
\end{algorithmic}\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
-\Function{ValidSlotsRange}{$|SL_s|,s_{s_{min}},s_{s_{max}}$}\r
-\State $sz_{SL} \gets s_{s_{max}} - s_{s_{min}} + 1$\r
-\If{$sz_{SL} \neq |SL_s|$}\r
- \State \Call{Error}{'Sequence numbers range does not match actual set'}\r
-\EndIf\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
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
-\Procedure{CheckSlotsRange}{$|SL_s|$}\r
-\State $s_{s_{max}} \gets MaxLastSeqN(MS)$\r
-\State $s_{self} \gets MS[id_{self}]$\r
-\State $sz_{expected} \gets s_{s_{max}} - s_{self} + 1$\r
-\If{$|SL_s| \neq sz_{expected}$}\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
\r
\begin{algorithmic}[1]\r
-\Function{ValidateHmacChain}{$Dat_s,s_s,hmac_{p_s},sl_l$}\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
\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 \land IsKV(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
\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 $\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}{|SL_g|,s_{g_{min}},s_{g_{max}}}$\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
\If{$s_g \neq s_{g_{in}}$}\r
\State \Call{Error}{'Invalid sequence number'}\r
\EndIf\r
- \State $hmac_{p_g} \gets \Call{ValidateHmacChain}{Dat_g,s_g,hmac_{p_g},sl_{last}}$\r
-\r
-% \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_g)$\r
-% \If {$ \neg(s_g = 0 \land hmac_{p_g} = 0) \land hmac_{p_{stored}} \neq hmac_{p_g}$}\r
-% \State \Call{Error}{'Invalid previous HMAC value'}\r
-% \EndIf\r
-% \If{$Hmac(Dat_g,SK) \neq GetCurrHmac(Dat_g)$ }\r
-% \State \Call{Error}{'Invalid current HMAC value'}\r
-% \EndIf\r
-% \State $hmac_{p_g} \gets Hmac(Dat_g,SK)$\Comment{Update $hmac_{p_g}$ for next check}\r
-\r
- \State $DE_g \gets GetDatEnt(Dat_g)$\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 $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
- %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},cr_g}$\r
- \EndFor\r
- \EndIf\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
-\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,d}$\r
-\State $\Call{CheckSlotsRange}{|SL_g|}$\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
\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