+ \State \Return{$LstSlt_a$} \r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\r
+% Delete Local Slots\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Delete Local Slots:}\\\r
+Deletes local slots that are deleted at the server. This keeps the size of the local block chain bounded.\\\r
+\begin{algorithmic}[1]\r
+\Function{DeleteLocalSlots}{$ $}\r
+ \State $\tuple{seq_{max}, Dat_{max}} \gets $ \Call{MaxSlot}{$LocalSlots$}\r
+ \State $seq_{min} \gets seq_{max} - max\_size$ \Comment{Min sequence number we should keep}\r
+ \State $LSDelete \gets \emptyset$\r
+ \r
+ \If{$|LocalSlots| \leq max\_size$}\r
+ \State \Return{} \Comment{Nothing to delete}\r
+ \EndIf\\\r
+ \r
+ \State $LSDelete \gets \{\tuple{seq', Dat'}|\tuple{seq', Dat'} \in LocalSlots, seq' > seq_{min}\}$\r
+ \State $LocalSlots \gets LocalSlots \setminus LSDelete$ \r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Create Speculative KV\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Create Speculative KV:}\\\r
+Speculates on what the most recent key value pairs will be based on the latest committed key value pairs and the uncommitted transactions.\\\r
+\begin{algorithmic}[1]\r
+\Function{SpeculateKV}{$ $}\r
+ \State $AllTrans \gets$ \Call{GetTrans}{}\r
+ \State $LiveTrans \gets \{t| t\in AllTrans, $\Call{CheckTransLive}{$t$}$\}$\r
+ \State $CurrKV \gets CommittedKV$\r
+ \State $DKV \gets \emptyset$\r
+\r
+ \ForAll{$\tuple{seq_t, id_t, KV_t, Guard_t} \in LiveTrans$ ordered by $seq'$} \r
+ \If{\Call{EvaluateGuard}{$Guard_t, CurrKV$}}\r
+ \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CurrKV \land \tuple{k',v'}\in KV_t \land k'=k\}$\r
+ \State $CurrKV \gets (CurrKV \setminus DKV) \cup KV_t$\r
+ \EndIf\r
+ \EndFor\r
+ \r
+ \State \Return{$CurrKV$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\r
+% Validate and Update \r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Validate Update:}\\\r
+Validate the block chain and insert into the local block chain.\\\r
+\begin{algorithmic}[1]\r
+\Function{ValidateUpdate}{$NewSlots_a, updatinglocal_a$}\r
+ \State $\tuple{seq_{oldest}, Dat_{oldest}} \gets$ \Call{MinSlot}{$NewSlots_a$}\r
+ \State $\tuple{seq_{newest}, Dat_{newest}} \gets$ \Call{MaxSlot}{$NewSlots_a$}\r
+ \State $\tuple{seq_{local}, Dat_{local}} \gets$ \Call{MaxSlot}{$LocalSlots$}\r
+ \State $LastSlotTmp \gets LastSlot$\\\r
+ %\State $currsize \gets $\Call{InitExpSize}{$seq_{oldest}$}\\\r
+ \r
+ \State \Call{CheckSlotsHmacAndSeq}{$NewSlots_a$} \Comment{Check all the HMACs}\r
+ \State \Call{CheckHmacChain}{$NewSlots_a$} \Comment{Check HMAC Chain} \r
+ \State \Call{CheckOldSlots}{$NewSlots_a$} \Comment{Check if new slots are actually old slots} \r
+ \State \Call{CheckSize}{$NewSlots_a$} \Comment{Check if the size is correct}\\\r
+ \r
+ \ForAll{$slot_a \in NewSlots_a$ in order of sequence number}\r
+ \If{$slot_a \in LocalSlots$} \Comment{Client already has this slot}\r
+ \State $NewSlots_a \gets NewSlots_a \setminus \{slot_a\}$\r
+ \State Continue\r
+ \EndIf\\\r
+ \r
+ \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets slot_a$\r
+ \State $LstSlt_a \gets$ \Call{UpdateLastMessage}{$seq_{a_1}, id_a, LstSlt_a, updatinglocal_a$}\\\r
+ \r
+ \ForAll{$de_a \in DE_a$} \Comment{Process each data entry}\r
+ \State $LstSlt_a \gets $ \Call{ProccessDatEntry}{$de_a, NewSlots_a,LstSlt_a$}\r
+ \EndFor\\\r
+ \r
+ %\State $currsize \gets $ \Call{UpdateExpSize}{$currsize$}\\\r
+ \State $LocalSlots \gets LocalSlots \cup \{slot_a\}$ \Comment{Add to local Chain}\r
+ \EndFor\\\r
+ \r
+ \If{$seq_{oldest} > (seq_{local} +1) \land LastSlotTmp \neq \emptyset$}\r
+ \LeftComment{There was a gap so there should be a complete set of information on each previously seen client}\r
+ \State \Call{Error}{"Missing records for machines"}\r
+ \EndIf\\\r
+ \r
+ \State \Call{DeleteLocalSlots}{ } \Comment{Delete old slots from local}\r
+ \State $SpeculatedKV \gets $\Call{SpeculateKV}{ } \Comment{Speculate on what will be latest KV set}\r
+ \r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Decrypt Validate Insert Slots\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Decrypt Validate Insert Slots:}\\\r
+Decrypts slots, validates (checks for malicious activity) slots and inserts the slots into the local block chain.\\\r
+\begin{algorithmic}[1]\r
+\Function{DecryptValidateInsert}{$NewSlots_a, updatinglocal_a$}\r
+ \State $DecryptedSlots \gets \emptyset$\r
+ \State $DDat \gets NULL$\\\r
+ \r
+ \ForAll{$\tuple{seq', EDat'} \in NewSlots_a$}\r
+ \State $DDat \gets $ \Call{Decrypt}{$EDat'$}\r
+ \State $DecryptedSlots \gets DecryptedSlots \cup \tuple{seq',DDat}$\r
+ \EndFor\\\r
+ \State \Call{ValidateUpdate}{$DecryptedSlots, updatinglocal_a$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Check and Create Last Message Data Entry\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Check and Create Last Message Data Entry:}\\\r
+Check if a last message entry needs to be created for this slot and if so create it. The check is done by checking if there are any newer slots with the same id or if there is already a last message slot with a newer sequence number\\\r
+\begin{algorithmic}[1]\r
+\Function{CheckCreateLastMsgEntry}{$seq_a, id_a$}\r
+ \State $AllLastMsg \gets$ \Call{GetLastMsg}{}\\\r
+ \r
+ \LeftComment{Already Has one}\r
+ \If{$\exists \tuple{seq', id'} \in AllLastMsg, id_a=id' \land seq'=seq_a$}\r
+ \State \Return{$\{\}$}\\\r
+ \EndIf\\\r
+ \r
+ \LeftComment{Not latest slot from that client}\r
+ \If{$\exists \tuple{seq_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots, id_a=id' \land seq_1'>seq_a$}\r
+ \State \Return{$\{\}$}\\\r
+ \EndIf\\\r
+ \r
+ \r
+ \State \Return{$\{\tuple{seq_a, id_a}\}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Mandatory Rescue\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Mandatory Rescue:}\\\r
+This rescue is mandatory before any types of data entries (excpet queue states) can be placed into the data entry section of the new slot. Returns the data entry Set or null if the first slot could not be cleared (the live data in that slot could not fit in this current slot). \\\r
+\begin{algorithmic}[1]\r
+\Function{MandatoryRescue}{$DE_a$}\r
+ \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
+ \State $cseq \gets smallestseq$\\\r
+ \r
+ \LeftComment{Check the least slots to rescue and live entries}\r
+ \While{$cseq < (smallestseq + DEAD\_SLOT\_COUNT)$}\r
+ \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
+ \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\r
+ \State $DE' \gets DE' \cup$ \Call{CheckCreateLastMsgEntry}{$seq', id'$} \Comment{Get the last message too if we need it}\\\r
+ \r
+ \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
+ \If{\Call{CheckLive}{$de, cseq$}} \Comment{data entry is live}\r
+ \State $de \gets $ \Call{CreateRescuedEntry}{de} \Comment{Resize entry if needed}\r
+ \If{\Call{DEHasSpace}{$DE_a, de$}}\r
+ \State $DE_a \gets DE_a \cup de$ \Comment{Had enough space to add it}\r
+ \ElsIf{$currentseq = smallestseq$}\r
+ \State \Return{$NULL$}\r
+ \Else\r
+ \State \Return{$DE_a$}\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
+ \EndWhile\r
+ \r
+ \State \Return{$DE_a$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Optional Rescue\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Optional Rescue:}\\\r
+This rescue is not mandatory. This is trying to fill the remaining portion of the slot with rescued data so that no space is wasted. If we encounter a data entry that does not fit move on to the next, maybe that one will fit. Do this until we skipped too many live data entries\\\r
+\begin{algorithmic}[1]\r
+\Function{OptionalRescue}{$DE_a$}\r
+ \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
+ \State $largestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \geq seq')$\r
+\r
+ \State $numofskips \gets 0$\r
+ \State $cseq \gets smallestseq$\\\r
+ \r
+ \LeftComment{Check the least slots to rescue and live entries}\r
+ \While{$cseq < largestseq$}\r
+ \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
+ \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\\\r
+ \r
+ \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
+ \If{\Call{CheckLive}{$de, cseq$}} \Comment{data entry is live}\r
+ \State $de \gets $ \Call{CreateRescuedEntry}{de} \Comment{Resize entry if needed}\\\r
+ \r
+ \If{$de \in DE_a$} \Comment{Already being rescued}\r
+ \State Continue\r
+ \EndIf\\\r
+ \r
+ \If{\Call{DEHasSpace}{$DE_a, de$}}\r
+ \State $DE_a \gets DE_a \cup de$ \Comment{Had enoug space to add it}\r
+ \ElsIf{$numofskips \geq MAX\_RESCUE\_SKIPS$}\r
+ \State \Return{$DE_a$}\r
+ \Else\r
+ $numofskips \gets numofskips +1$\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
+ \EndWhile\r
+ \r
+ \State \Return{$DE_a$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\r
+% Rejected Messages\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Rejected Messages:}\\\r
+\begin{algorithmic}[1]\r
+\Function{RejectedMessages}{$DE_a$}\r
+ \State $seq_{old} \gets seq$ such that $\tuple{seq} \in RejectedSlotList \land \forall \tuple{seq'} \in RejectedSlotList, seq \geq seq'$\r
+ \State $prev \gets -1$\\\r
+ \r
+ \r
+ \r
+ \If{$|RejectedSlotList| \geq REJECTED\_THRESH$}\r
+ \State $seq_{new} \gets seq$ such that $\tuple{seq} \in RejectedSlotList \land \forall \tuple{seq'} \in RejectedSlotList, seq \leq seq'$\\\r
+ \State $colres \gets $ \Call{CreateColRes}{$LOCAL\_ID, seq_{old}, seq_{new}, false$} \r
+ \State \Return{$DE_a \cup \{colres\}$}\r
+ \EndIf\\\r
+ \r
+ \ForAll{$\tuple{seq} \in RejectedSlotList$ sorted by $seq$}\r
+ \If{$\exists \tuple{seq',Dat'} \in LocalSlots$}\r
+ \State Break\r
+ \EndIf\r
+ \State $prev \gets seq$\r
+ \EndFor\\\r
+ \r
+ \If{$prev \neq -1$}\r
+ \State $DE_a \gets DE_a \cup$ \Call{CreateColRes}{$LOCAL\_ID, seq_{old}, prev, false$}\r
+ \EndIf\\\r
+ \r
+ \State $RejectedSlotList \gets \{\tuple{seq}| \tuple{seq} \in RejectedSlotList, seq > prev\}$\\\r
+ \r
+ \ForAll{$\tuple{seq} \in RejectedSlotList$ sorted by $seq$}\r
+ \State $DE_a \gets DE_a \cup$ \Call{CreateColRes}{$LOCAL\_ID, seq,seq, false$}\r
+ \EndFor\\\r
+ \r
+ \State \Return{$DE_a$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\r
+\r
+% Arbitrate\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Arbitrate:}\\\r
+\begin{algorithmic}[1]\r
+\Function{Arbitrate}{$DE_a$}\r
+ \State $AllCommits \gets$ \Call{GetCommits}{}\r
+ \State $AllTrans \gets$ \Call{GetTrans}{}\r
+ \State $LiveCommits \gets \{c| c\in AllCommits, $\Call{CheckCommitLive}{$c$}$\}$\r
+ \State $LiveTrans \gets \{t| t\in AllTrans, $\Call{CheckTransLive}{$t$}$\}$\r
+ \State $KV \gets \emptyset$\r
+ \State $lastcomseq \gets -1$\r
+ \State $CurrKV \gets \emptyset$\r
+ \State $DKV \gets \emptyset$\r
+ \State $KVTmp \gets \emptyset$\\\r
+ \r
+ \LeftComment{Get all the latest commits}\r
+ \ForAll{$\tuple{seq_{trans}',KV'} \in LiveCommits$}\r
+ \State $CurrKV \gets CurrKV \cup KV'$\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{seq_t, id_t, KV_t, Guard_t} \in LiveTrans$ ordered by $seq'$} \r
+ \If{\Call{GetArbitratorKV}{$KV_t$} $\neq LOCAL\_ID$}\r
+ \State Continue \Comment{Client not arbitrator for this transaction}\r
+ \EndIf\\\r
+ \r
+ \If{$\lnot$\Call{EvaluateGuard}{$Guard_t, CurrKV$}}\r
+ \State $abortde \gets $\Call{CreateAbort}{$seq_t, id_t$}\r
+ \LeftComment{No more space so we cant arbitrate any further}\r
+ \If($lnot$\Call{DeHasSpace}{$DE_a, abortde$})\r
+ \State \Return{$DE_a$}\r
+ \EndIf\r
+ \State $DE_a \gets DE_a \cup abortde$\r
+ \Else\r
+ \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in KV \land \tuple{k',v'}\in KV_t \land k'=k\}$\r
+ \State $KVTmp \gets (KV \setminus DKV) \cup KV'$\r
+ \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CurrKV \land \tuple{k',v'}\in KVTmp \land k'=k\}$\r
+ \State $CurrKV \gets (CurrKV \setminus DKV) \cup KVTmp$\r
+ \State $commitde \gets $ \Call{CreateCommit}{$seq_t,KVTmp$}\r
+ \r
+ \If{$\lnot$ \Call{DeHasSpace}{$DE_a, commitde$}}\r
+ \If{$lastcomseq \neq -1$}\r
+ \State $DE_a \gets DE_a \cup$ \Call{CreateCommit}{$lastcomseq,KV$}\r
+ \EndIf\r
+ \State \Return{$DE_a$}\r
+ \Else\r
+ \State $KV \gets KVTmp$\r
+ \State $lastcomseq \gets seq_t$\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\r
+ \r
+ \State $DE_a \gets DE_a \cup$ \Call{CreateCommit}{$lastcomseq,KV$}\r
+ \State \Return{$DE_a$}\r
+\r
+ \r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Create New Slot\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Create New Slot:}\\\r
+Create a slot and encrypt it.\\\r
+\begin{algorithmic}[1]\r
+\Function{CreateNewSlot}{$seq_a, DE_a$}\r
+ \State $\tuple{seq, SDE} \gets \tuple{seq', SDE'}$ such that $\tuple{seq', SDE'}\in LocalSlots \land (\forall \tuple{seq'', DE''} \in LocalSlots, seq' \geq seq'')$\r
+ \State $\tuple{seq,id,DE,hmac_p,hmac_c} \gets SDE$\\\r
+ \r
+ \State $newhmac \gets $ \Call{GenerateHmac}{$seq_a, LOCAL\_ID, DE_a, hmac_p$}\r
+ \State $newSDE \gets \tuple{seq,LOCAL\_ID,DE_a,hmac_c,newhmac}$\r
+ \State $encryptnewSDE \gets $\Call{Encrypt}{newSDE}\\\r
+ \r
+ \State \Return{$\tuple{seq_a, encryptnewSDE}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Send Data to Server\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Send Data to Server:}\\\r
+Send the data to the server. If this fails then new slots will be returned by the server.\\\r
+\begin{algorithmic}[1]\r
+\Function{SendToServer}{$seq_a, DE_a, newsize_a$}\r
+ \LeftComment{Make the slot and try to send to server}\r
+ \State $newslot \gets $ \Call{CreateNewSlot}{$seq_a, DE_a$}\r
+ \State $\tuple{success, newslots} \gets$ \Call{PutSlot}{$seq_a, newslot, newsize_a$}\\\r
+ \r
+ \If{$success$}\r
+ \State $RejectedSlotList \gets \emptyset$\r
+ \State \Return{$\tuple{true, \{newslot\}}$}\r
+ \Else\r
+ \If{$|newslots| = 0$}\r
+ \State \Call{Error}{"Server rejected but did not send any slots"}\r
+ \EndIf\r
+ \State $RejectedSlotList \gets RejectedSlotList \cup \{seq_a\}$\r
+ \State \Return{$\tuple{false, newslots}$}\r
+ \EndIf\\\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\r
+% Try Insert Transaction\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Try Insert Transaction:}\\\r
+Try to insert a transaction into the block chain. Does resizing, rescues and insertion of other data entry types as needed. \\\r
+\begin{algorithmic}[1]\r
+\Function{TryInsertTransaction}{$pendingtrans_a, forceresize$}\r
+ \State $DE \gets \emptyset$ \Comment{The data entries for this slot}\r
+ \State $seq \gets $ \Call{GetNextSeq}{} \Comment{Get the sequence number for this slot}\r
+ \State $newsize \gets 0$\r
+ \State $trans \gets$ \Call{CreateTrans}{$pendingtrans_a, seq$}\r
+ \State $transinserted \gets false$\r
+ \State $slotstoinsert \gets \emptyset$\\\r
+ \r
+ \State $resize \gets $ \Call{ShouldResize}{ } \Comment{Check if we should resize}\r
+ \State $resize \gets resize \lor forceresize$\r
+ \If{$resize$}\r
+ \State $newsize \gets$ \Call{CalcNewSize}{$max\_size$}\r
+ \State $DE \gets DE \cup \{$\Call{CreateQState}{$newsize$}$\}$\r
+ \EndIf\\\r
+ \r
+ \If{$RejectedSlotList \neq \emptyset$} \r
+ \State $DE \gets$ \Call{RejectedMessages}{$DE$}\r
+ \EndIf\\\r
+ \r
+ \State $DE \gets$ \Call{MandatoryRescue}{$DE$} \Comment{Round 1 of rescue}\r
+ \If{$DE = NULL$}\r
+ \LeftComment{Data was going to fall off the end so try again with a forced resize}\r
+ \State \Return{\Call{TryInsertTransaction}{$trans_a, true$}}\r
+ \EndIf\\\r
+ \r
+ \State $DE \gets $\Call{Arbitrate}{$DE$}\\\r
+ \r
+ \If{\Call{DEHasSpace}{$DE, trans$}} \Comment{transaction fits}\r
+ \State $DE \gets DE \cup trans$\r
+ \State $transinserted \gets true$\r
+ \EndIf\\\r
+ \r
+ \LeftComment{Rescue data to fill slot data entry section}\r
+ \State $DE \gets$ \Call{OptionalRescue}{$DE$}\\\r
+ \r
+ \LeftComment{Send to server.}\r
+ \State $\tuple{sendsuccess, newslots} \gets $ \Call{SendToServer}{$seq, DE, newsize$}\\\r
+ \r
+ \LeftComment{Insert the slots into the local bloakc chain}\r
+ \State \Call{DecryptValidateInsert}{$newslots, true$}\\\r
+ \r
+ \State \Return{$transinserted \land success$} \Comment{Return if succeeded or not}\r
+ \r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\r
+% Try Insert New Key\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Try Insert New Key:}\\\r
+Try to insert a new key into the block chain. Does resizing, rescues and insertion of other data entry types as needed. \\\r
+\begin{algorithmic}[1]\r
+\Function{TryInsertNewKey}{$k_a, id_a, forceresize$}\r
+ \State $DE \gets \emptyset$ \Comment{The data entries for this slot}\r
+ \State $seq \gets $ \Call{GetNextSeq}{} \Comment{Get the sequence number for this slot}\r
+ \State $newsize \gets 0$\r
+ \r
+ \r
+ \State $newkey \gets$ \Call{CreateNewKey}{$k_a, id_a$}\r
+ \State $newkeyinserted \gets false$\r
+ \State $slotstoinsert \gets \emptyset$\\\r
+ \r
+ \State $resize \gets $ \Call{ShouldResize}{ } \Comment{Check if we should resize}\r
+ \State $resize \gets resize \lor forceresize$\r
+ \If{$resize$}\r
+ \State $newsize \gets$ \Call{CalcNewSize}{$max\_size$}\r
+ \State $DE \gets DE \cup \{$\Call{CreateQState}{$newsize$}$\}$\r
+ \EndIf\\\r
+ \r
+ \If{$RejectedSlotList \neq \emptyset$} \r
+ \State $DE \gets$ \Call{RejectedMessages}{$DE$}\r
+ \EndIf\\\r
+ \r
+ \State $DE \gets$ \Call{MandatoryRescue}{$DE$} \Comment{Round 1 of rescue}\r
+ \If{$DE = NULL$}\r
+ \LeftComment{Data was going to fall off the end so try again with a forced resize}\r
+ \State \Return{\Call{TryInsertNewKey}{$k_a, id_a, true$}}\r
+ \EndIf\\\r
+ \r
+ \State $DE \gets $\Call{Arbitrate}{$DE$}\\\r
+ \r
+ \If{\Call{DEHasSpace}{$DE, newkey$}} \Comment{new key fits}\r
+ \State $DE \gets DE \cup newkey$\r
+ \State $newkeyinserted \gets true$\r
+ \EndIf\\\r
+ \r
+ \LeftComment{Rescue data to fill slot data entry section}\r
+ \State $DE \gets$ \Call{OptionalRescue}{$DE$}\\\r
+ \r
+ \LeftComment{Send to server.}\r
+ \State $\tuple{sendsuccess, newslots} \gets $ \Call{SendToServer}{$seq, DE, newsize$}\\\r
+ \r
+ \LeftComment{Insert the slots into the local block chain}\r
+ \State \Call{DecryptValidateInsert}{$newslots, true$}\\\r
+ \r
+ \State \Return{$newkeyinserted \land success$} \Comment{Return if succeeded or not}\r
+ \r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\r
+\r
+\subsection{Client Interfaces}\r
+\r
+% Put KV pair\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Put Key Value Pair:}\\\r
+Puts a key value pair into the key value pair buffer\\\r
+\begin{algorithmic}[1]\r
+\Function{PutKeyValue}{$k,v$}\r
+ \State $\tuple{seq, KV, Guard} \gets PendingTrans$\\\r
+ \r
+ \LeftComment{Check if KV already has a key value pair for the specified key}\r
+ \State $DSet \gets \{\tuple{k_1,v_1} | \tuple{k_1,v_1} \in KV \land k_1 = k\}$\\\r
+ \r
+ \If{$DSet \neq \emptyset$}\r
+ \State \Call{Error}{"Value for key already in most recent update"}\r
+ \EndIf\\\r
+ \r
+ \State $KV \gets KV \cup \{\tuple{k,v}\}$ \Comment{Add key value pair}\r
+ \State $PendingTrans \gets \tuple{seq, KV, Guard}$\r
+ \State \Call{CheckArbitrator}{$PendingTrans$} \Comment{Check that the transaction still valid}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Get KV Pair Speculative\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get KV Pair Speculative:}\\\r
+Get the value for the key while speculating.\\\r
+\begin{algorithmic}[1]\r
+\Function{GetValueSpeculate}{$k_a$}\r
+ %\State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpeculatedKV \land k = k_a$\r
+ \r
+ \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpeculatedKV \land k = k_a$\r
+\State \Return{$v$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Update\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Update}\\\r
+Sync with the server and get all the latest slots.\\\r
+\begin{algorithmic}[1]\r
+\Function{Update}{$ $}\r
+ \State $\tuple{seq, Dat} \gets $ \Call{MaxSlot}{$LocalSlots$}\r
+ \State $NewSlots \gets$ \Call{GetSlots}{$seq$}\r
+ \State \Call{DecryptValidateInsert}{$NewSlots, false$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Get KV Pair Committed\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get KV Pair Committed:}\\\r
+Get the value for the key which have been committed.\\\r
+\begin{algorithmic}[1]\r
+\Function{GetValueCommit}{$k_a$}\r
+ \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in Committed \land k = k_a$\r
+ \State \Return{$v$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Put guard condition\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Put Guard:}\\\r
+Puts a guard transaction into the key value update. A guard is a key value with a logical operator ($lop$).\\\r
+\begin{algorithmic}[1]\r
+\Function{PutGuard}{$k,v, lop$}\r
+ \State $\tuple{seq, KV, Guard} \gets PendingTrans$\\\r
+ \r
+ \If{$\tuple{k,v, lop} \in Guard$}\r
+ \State \Return{} \Comment{Already have guard condition in update}\r
+ \EndIf\\\r
+ \r
+ \State $Guard \gets Guard \cup \{\tuple{k,v,lop}\}$\r
+ \State $PendingTrans \gets \tuple{seq, KV, Guard}$\r
+ \State \Call{CheckArbitrator}{$PendingTrans$} \Comment{Check that the transaction still valid}\r
+\EndFunction \r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Transaction Start\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{ Transaction Start:}\\\r
+Starts a transaction. Clears out the key value pair update buffer.\\\r
+\begin{algorithmic}[1]\r
+\Function{TransactionStart}{$ $}\r
+ % \LeftComment{Reset the key value update buffer}\r
+ % \State $KVUpdate \gets \tuple{\emptyset, \emptyset}$\r
+ \State $PendingTrans \gets NULL$\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Transaction Commit\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{ Transaction Commit:}\\\r
+Commits the transaction into the block chain. Keeps attempting to insert the transaction into the block chain until it succeeds.\\\r
+\begin{algorithmic}[1]\r
+\Function{Transaction Commit}{$ $}\r
+ \State $DKV \gets \emptyset$\r
+ \State $pt \gets NULL$\\\r
+ \r
+ \State $PendingTransQueue.$\Call{push}{$PendingTrans$}\\\r
+ \r
+ \While{\Call{HasConnectionToServer}{ } $\land PendingTransQueue \neq \emptyset$}\r
+ \State $pt \gets PendingTransQueue.$\Call{peak}{ }\\\r
+ \r
+ \If{\Call{TryInsertTransaction}{$pt, false$}}\r
+ \State $PendingTransQueue.$\Call{pop}{ }\r
+ \EndIf\r
+ \EndWhile\\ \r
+ \r
+ \LeftComment{Go Through local pending transactions and speculate}\r
+ \ForAll{$\tuple{KV, Guard} \in PendingTransQueue$}\r
+ \If{\Call{EvaluateGuard}{$Guard, SpeculatedKV$}}\r
+ \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in SpeculatedKV \land \tuple{k',v'}\in KV \land k'=k\}$\r
+ \State $SpeculatedKV \gets (SpeculatedKV \setminus DKV) \cup KV$\r
+ \EndIf\r
+ \EndFor\r
+ \r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\r
+%Create New Key \r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Create New Key:}\\\r
+Creates a new key and specifies which machine ID is the arbitrator. If there is already a new key entry in the block chain for this key name then do not insert into the chain, another client got there first. \\\r
+\begin{algorithmic}[1]\r
+\Function{Transaction Commit}{$k_a, id_a$}\r
+ \State $success \gets false$\\\r
+ \While{$\lnot success$}\r
+ \If{$\exists \tuple{k',id'} \in Arbitrator, k' = k_a$}\r
+ \State \Return{$false$} \Comment{Key already created}\r
+ \EndIf\\\r
+ \r
+ \State $success \gets$ \Call{TryInsertNewKey}{$k_a, id_a, false$}\r
+ \EndWhile\r
+ \r
+ \State \Return{$true$} \Comment{If got here then insertion was correct}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r