+\begin{algorithmic}[1]\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
+\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}{$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
+\State $cr_s \gets CreateCR(s_{col},id_{col})$\r
+\State $\Call{ProcessSL}{SL_s}$\r
+\State \Return{$cr_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Procedure{CheckLastSlot}{$sl_{s_{last}}$}\r
+\State $s_s \gets GetLastS(sl_{s_{last}})$\r
+\State $sv_s \gets GetSV(sl_{s_{last}})$\r
+\State $Dat_s \gets Decrypt(SK,sv_s)$\r
+\State $DE_s \gets GetDatEnt(Dat_s)$\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
+ \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
+ \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
+ \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
+ \State $reinsert_{qs} \gets true$\r
+ \EndIf\r
+ \EndIf\r
+\EndFor\r
+\EndProcedure\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{CheckLiveness}{$s_s,de_s$}\r
+\State $live \gets true$\r
+\If{$de_s = kv$}\r
+ \State $s_l \gets GetLivEntLastS(LV,de_s)$\r
+ \If{$s_l = \emptyset \lor s_s < s_l$}\r
+ \State $live \gets false$\r
+ \EndIf\r
+\ElsIf{$de_s = ss$}\r
+ \State $ss_s \gets GetSS(de_s)$\r
+ \State $ss_l \gets GetLiveSS(SS_{live},ss_s)$\r
+ \If{$ss_l = \emptyset$}\r
+ \State $live \gets false$\r
+ \EndIf\r
+\ElsIf{$de_s = cr$}\r
+ \State $cr_s \gets GetCR(de_s)$\r
+ \State $cr_l \gets GetLiveCR(CR_{live},cr_s)$\r
+ \If{$cr_l = \emptyset$}\r
+ \State $live \gets false$\r
+ \EndIf\r
+\ElsIf{$de_s = qs$}\r
+ \State $qs_s \gets GetQS(de_s)$\r
+ \If{$qs_s \neq max_g$}\r
+ \State $live \gets false$\r
+ \EndIf\r
+\Else\r
+ \State \Call{Error}{'Unrecognized $de$ type'}\r
+\EndIf\r
+\State \Return{$live$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{CreateSlotSeq}{$sl_s$}\r
+\State $id_s \gets GetID(sl_s)$\r
+\State $s_{s_{last}} \gets GetLastS(sl_s)$\r
+\State $ss_s \gets CreateSS(id_s,s_{s_{last}})$\r
+\State \Return{$\tuple{ss_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 $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{GetKVPairs}{$DE_s,KV_s,cp_s$}\r
+\State $DE_{ret} \gets \emptyset$\r
+\If{$|KV_s| \leq cp_s$}\Comment{$KV$ set can span multiple slots}\r
+ \State $DE_{ret} \gets DE_s \cup\r
+ \{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s\}$\r
+\Else\r
+ \State $DE_{ret} \gets DE_s \cup\r
+ \{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s,\r
+ ck_g \leq ck_s < ck_g + cp_s\}$\r
+\EndIf\r
+\State \Return{$\tuple{DE_{ret}}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{GetSSPairs}{$DE_s,SS_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 \Return{$\tuple{DE_{ret},cp_s}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{GetCRPairs}{$DE_s,CR_s,cp_s$}\r
+\State $DE_{ret} \gets \emptyset$\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 \Return{$\tuple{DE_{ret},cp_s}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Procedure{PutDataEntries}{$th_p,m'_p$}\r
+\State $success_p \gets false$\r
+\State $CR_p \gets \emptyset$\r
+\While{$\neg success_p$}\r
+ \State $DE_p \gets \emptyset$\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$}\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 $reinsert_{qs} \gets false$\r
+ \EndIf\r
+ \EndIf\r
+ \If{$SS \neq \emptyset$}\Comment{Add $ss$ entries}\r
+ \State $\tuple{DE_p,cp_p} \gets \Call{GetSSPairs}{DE_p,SS,cp_p}$\r
+ \EndIf\r
+ \If{$CR \neq \emptyset$}\Comment{Add $cr$ entries}\r
+ \State $\tuple{DE_p,cp_p} \gets \Call{GetCRPairs}{DE_p,CR,cp_p}$\r
+ \EndIf\r
+ \State $\tuple{DE_p,cp_p} \gets \Call{GetKVPairs}{DE_p,KV,cp_p}$\Comment{Add $kv$ entries}\r
+ \State $hmac_{c_p} \gets Hmac(DE_p,SK)$\r
+ \State $Dat_p \gets CreateDat(s_p,id_{self},hmac_{p_p},DE_p,hmac_{c_p})$\r
+ \State $hmac_{p_p} \gets hmac_{c_p}$\r
+ \State $sv_p \gets Encrypt(Dat_p,SK)$\r
+ \State $\tuple{success_p,SL_p} \gets \Call{PutSlot}{s_p,sv_p,max'_p}$\r
+ \If{$\neg success_p$}\r
+ \State $cr_p \gets \Call{HandleCollision}{SL_p,s_p}$\r
+ \State $\tuple{s_{p_{col}},id_{p_{col}}} \gets GetCR(cr_p)$\r
+ \State $CR \gets \Call{PutCRPair}{CR,\tuple{s_{p_{col}},id_{p_{col}}}}$\r
+ \EndIf\r
+\EndWhile\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 $ck_g \gets 0$\r
+ \State $cs_g \gets 0$\r
+ \State $cc_g \gets 0$\r
+\EndIf\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
+\EndIf\r
+\EndProcedure\r
+\end{algorithmic}\r
+\r
+%\note{Lots of problems with PutDataEntries: (1) What happens if lose network connectivity after adding the key value pair, but before reinserting the last slot? You probably need to create space first and then insert your data entry... (2) What if reinsertlastslot kicks something else important out? What if the server rejects our update because it is out of date? At the very least, any putdataentries function w/o a loop is wrong!}\r