+\EndFor\r
+\EndProcedure\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
+ \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
+ \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 $s_t \gets GetS(\tuple{s_t,id_t})$\r
+\State $id_t \gets GetId(\tuple{s_t,id_t})$\r
+\State $id_s \gets GetMachineId(SM_s,s_t)$\r
+\If{$id_s \neq id_t$}\r
+ \State \Call{ReportError}{'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
+\If{$s_{min} \neq \emptyset \land s_{min} = s_s$}\Comment{$MS$ initially empty}\r
+ \State $sl_l \gets CreateLastSL(s_s,sv_s,id_s)$\r
+\EndIf\r
+\State \Return{$sl_l$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{UpdateDT}{$DT_s,Dat_s$}\r
+\State $DE_s \gets GetDatEnt(Dat_s)$\r
+\ForAll{$de_s \in DE_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
+ \{\tuple{k_s,v_s}\}$\r
+ \EndIf\r
+ \EndIf\r
+\EndFor\r
+\State \Return{$DT_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_{max}},sv_{g_{max}}} \gets MaxSlot(SL_g)$\r
+\State $s_{g_{max}} \gets SeqN(\tuple{s_{g_{max}},sv_{g_{max}}})$\r
+\State $\tuple{s_{g_{min}},sv_{g_{min}}} \gets MinSlot(SL_g)$\r
+\State $s_{g_{min}} \gets SeqN(\tuple{s_{g_{min}},sv_{g_{min}}})$\r
+\For{$s_g \gets s_{g_{min}}$ \textbf{to} $s_{g_{max}}$}\Comment{Process slots \r
+ in $SL_g$ in order}\r
+ \State $\tuple{s_g,sv_g} \gets Slot(SL_g,s_g)$\r
+ \State $SM_{curr} \gets SM_{curr} \cup \{\tuple{s_g,sv_g}\}$\r
+ \State $s_g \gets SeqN(\tuple{s_g,sv_g})$\r
+ \State $sv_g \gets SlotVal(\tuple{s_g,sv_g})$\r
+ \State $Dat_g \gets Decrypt(SK,sv_g)$\r
+ \State $s_{g_{in}} \gets GetSeqN(Dat_g)$\r
+ \If{$s_g \neq s_{g_{in}}$}\r
+ \State \Call{ReportError}{'Invalid sequence number'}\r
+ \EndIf\r
+ \State $DE_g \gets GetDatEnt(Dat_g)$\r
+ \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_g)$\r
+ \If{$\neg \Call{ValidPrevHmac}{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{ReportError}{'Invalid current HMAC value'}\r
+ \EndIf\r
+ \State $hmac_{p_g} \gets Hmac(DE_g,SK)$\Comment{Update $hmac_{p_g}$ for next check}\r
+ \State $qs_g \gets \Call{GetQueSta}{Dat_g}$\Comment{Handle qs}\r
+ \If{$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 $\tuple{id_d,s_{d_{last}}} \gets \Call{GetSlotSeq}{Dat_g}$\Comment{Handle ss}\r
+ \If{$\tuple{id_d,s_{d_{last}}} \neq \emptyset$}\r
+ \State $MS_g \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_g}$\r
+ \EndIf\r
+ \State $\{\tuple{s_e,id_e},\tuple{s_f,id_f}\} \gets \r
+ \Call{GetColRes}{Dat_g}$\Comment{Handle cr}\r
+ \State $\Call{CheckCollision}{MS,SM,\tuple{s_e,id_e}}$\Comment{From normal slot}\r
+ \State $\Call{CheckCollision}{MS,SM,\tuple{s_f,id_f}}$\Comment{From reinsertion}\r
+ \State $sl_{last} \gets \Call{StoreLastSlot}{MS,sl_{last},s_g,sv_g,id_g}$\r
+ \State $DT \gets \Call{UpdateDT}{DT,Dat_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{ReportError}{'Actual queue size exceeds $max_g$'}\r
+\EndIf\r
+\State $\Call{CheckLastSeqN}{MS_g,MS}$\r
+\EndProcedure\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Procedure{GetKVPairs}{}\r
+\State $s_g \gets GetLastSeqN(MS,id_{self}) + 1$\r
+\State $SL_c \gets \Call{GetSlot}{s_g}$\r
+\State $\Call{ProcessSL}{SL_c}$\Comment{Process slots and update DT}\r
+\EndProcedure\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{GetValFromKey}{$k_g$}\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
+\EndFunction\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{$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{$hmac_{c_p}$ = the HMAC value of the current slot} \\\r
+\textit{$hmac_{p_p}$ = the HMAC value of the previous slot \r
+($hmac_{p_p} = \emptyset$ for the first slot)} \\\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{$th_p$ = threshold number of dead slots for a resize to happen} \\\r
+\textit{$m'_p$ = offset added to $max$ for resize} \\\r
+\textit{$KV$ = set of $\tuple{ck, \tuple{k,v}}$ of kv entries on client} \\\r
+\textit{$SL_p$ = set of returned slots on client} \\\r
+\textit{SK = Secret Key} \\ \\\r
+\textbf{Helper Functions} \\\r
+$CreateDat(s,id,hmac_p,DE,hmac_c)=Dat_s=\tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
+$CreateCR(s,id)=\tuple{s,id}$ \\\r
+$CreateQS(max')=qs$ \\\r
+$CreateSS(id,s_{last})=\tuple{id,s_{last}}$ \\\r
+$Encrypt(Dat_s,SK_s)=sv_s$ \\\r
+$GetStatus(\tuple{status,SL})=status$ \\\r
+$GetSL(\tuple{status,SL})=SL$ \\\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
+$GetKV(KV_s,k_s)= \tuple{ck,\tuple{k, v}}$ \textit{such that} \r
+$\tuple{ck,\tuple{k, v}} \in KV_s \wedge\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 GetKV(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
+\Else\r
+ \State $KV_s \gets (KV_s - \{\tuple{ck_s, \tuple{k_s,v_t}}\}) \cup \r
+ \{\tuple{ck_s, \tuple{k_s,v_s}}\}$\r
+\EndIf\r
+\State \Return{$KV_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
+\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
+\State $n_{dead} \gets max'_t - n_{live}$\r
+\If{$n_{dead} \leq th_s$}\r
+ \State $max'_s \gets max'_t + m'_s$\r
+\Else\r
+ \State $max'_s \gets \emptyset$\r
+\EndIf\r
+\State \Return{$max'_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{CheckNeedSS}{$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
+\State $n_{dead} \gets max'_t - n_{live}$\r
+\State \Return {$n_{dead} = 0$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{HandleCollision}{$\tuple{stat_s,SL_s}$}\r
+\State $stat_s \gets GetStatus(\tuple{stat_s,SL_s})$\r
+\State $SL_s \gets GetSL(\tuple{stat_s,SL_s})$\r
+\If{$\neg stat_s$}\Comment{Handle collision}\r
+ \State $\tuple{s_{col},sv_{col}} \gets GetColSeqN(SL_s,s_s)$\r
+ \State $s_{col} \gets SeqN(\tuple{s_{col},sv_{col}})$\r
+ \State $sv_{col} \gets SlotVal(\tuple{s_{col},sv_{col}})$\r
+ \State $Dat_{col} \gets Decrypt(SK,sv_{col})$\r
+ \State $id_{col} \gets GetMacId(Dat_{col})$\r
+ \State $\tuple{s_{col},id_{col}} \gets CreateCR(s_{col},id_{col})$\r
+ \State $cr_s \gets \tuple{s_{col},id_{col}}$\r
+\Else\r
+ \State $cr_s \gets \emptyset$\r
+\EndIf\r
+\State $\Call{ProcessSL}{SL_s}$\r
+\State \Return{$cr_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{ReinsertLastSlot}{$need_s,sl_{s_{last}},max'_s$}\r
+\If{$need_s$}\r
+ \State $s_s \gets GetLastS(sl_{s_{last}})$\r
+ \State $sv_s \gets GetSV(sl_{s_{last}})$\r
+ \State $\tuple{stat_s,SL_s} \gets \Call{PutSlot}{s_s,sv_s,max'_s}$\r
+ \State $cr_s \gets \Call{HandleCollision}{\tuple{stat_s,SL_s}}$\r
+\EndIf\r
+\State \Return{$cr_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\note{Shouldn't this function do something pretty sophisticated about seeing what data we actually need to keep from the last slot and not just insert the entire thing?}\r
+\r
+\note{Probably best to just not call this function is $need_s$ is false and not pass in such parameters. It makes it harder to read.}\r