Revisions

diff --git a/doc2/iotcloud.tex b/doc2/iotcloud.tex
index e80073de99d41b0c8e7496781d5d09f05fe836e6..e882dd923e9d5e95e430cec27bb830177819aa95 100644 (file)
--- a/doc2/iotcloud.tex
+++ b/doc2/iotcloud.tex
@@ -42,13 +42,13 @@ $hmac_p$ is the HMAC value of the previous slot \\
 $hmac_c$ is the HMAC value of the current slot \\\r
 $Guard$ is a set of$ \tuple{k,v,$logical operator$}$ which can be evaluated to a boolean \\\r
 \r
 $hmac_c$ is the HMAC value of the current slot \\\r
 $Guard$ is a set of$ \tuple{k,v,$logical operator$}$ which can be evaluated to a boolean \\\r
 \r

-$trans$ is a transaction entry , $\tuple{seq, KV, Guard}$  \\\r
+$trans$ is a transaction entry , $\tuple{seq, id, KV, Guard}$  \\\r

 $lastmsg$ is a last message entry, $\tuple{seq, id}$ \\\r
 $qstate$ is a queue state entry, $\tuple{size}$ \\\r
 $colres$ is a collision resolution entry, $\tuple{id, seq_{old}, seq_{new}, true \lor false}$ \\\r
 $newkey$ is a new key entry, $\tuple{seq, k, id}$, $id$ is ID of arbitrator \\\r
 $commit$ is a commit transaction entry, $\tuple{seq_{trans},KV}$, id is id of arbitrator \\\r
 $lastmsg$ is a last message entry, $\tuple{seq, id}$ \\\r
 $qstate$ is a queue state entry, $\tuple{size}$ \\\r
 $colres$ is a collision resolution entry, $\tuple{id, seq_{old}, seq_{new}, true \lor false}$ \\\r
 $newkey$ is a new key entry, $\tuple{seq, k, id}$, $id$ is ID of arbitrator \\\r
 $commit$ is a commit transaction entry, $\tuple{seq_{trans},KV}$, id is id of arbitrator \\\r

-$abort$ is an abort transaction entry, $\tuple{seq_{abrt},seq_{trans},id_{trans}}$ \\\r
+$abort$ is an abort transaction entry, $\tuple{seq_{trans},id_{trans}}$ \\\r

 \r
 \r
 $de$ is a data entry that can one of: $trans$, $lastmsg$, $qstate$, $colres$, $newkey$, $commit$, $abort$ \\\r
 \r
 \r
 $de$ is a data entry that can one of: $trans$, $lastmsg$, $qstate$, $colres$, $newkey$, $commit$, $abort$ \\\r


@@ -192,6 +192,25 @@ Get all commits that are currently in the local block chain.  Iterate over all t
 \end{varwidth}% \r
 }\r
 \r
 \end{varwidth}% \r
 }\r
 \r

+% Get all Transactions\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get all Transactions:}\\\r
+Get all transactions that are currently in the local block chain.  Iterate over all the local slots and extract all the transactions from each slot.\\\r
+\begin{algorithmic}[1]\r
+\Function{GetTrans}{$ $}\r
+    \State $TransSet \gets \emptyset$ \Comment{Set of the trans}\\\r
+        \r
+    \LeftComment{Iterate over all the slots saved locally}\r
+    \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
+        \State $TransSet \gets TransSet \cup \{c |c \in DE',c$is a $trans\}$\r
+    \EndFor\r
+    \State \Return{$TransSet$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r

 % Get all aborts\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 % Get all aborts\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r


@@ -230,6 +249,25 @@ Get all qstates that are currently in the local block chain.  Iterate over all t
 \end{varwidth}% \r
 }\r
 \r
 \end{varwidth}% \r
 }\r
 \r

+% Get all Last Messages States\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get all last message data entrues:}\\\r
+Get all last msg that are currently in the local block chain.  Iterate over all the local slots and extract all the last msg from each slot.\\\r
+\begin{algorithmic}[1]\r
+\Function{GetLastMsg}{$ $}\r
+    \State $LMSet \gets \emptyset$ \Comment{Set of the last msg}\\\r
+        \r
+    \LeftComment{Iterate over all the slots saved locally}\r
+    \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
+        \State $LMSet \gets LMSet \cup \{c |c \in DE',c$is a $lastmsg\}$\r
+    \EndFor\r
+    \State \Return{$LMSet$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r

 % Check Queue State Live\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 % Check Queue State Live\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r


@@ -330,11 +368,11 @@ A new key data entry is always live.\\
 \textbf{Check Abort Live:}\\\r
 Check if an abort data entry is live or not.  Abort is dead if the device whos transaction was aborted sees the abort.  This is checked by seeing if that device inserted a slot into the block chain which has a sequence number that is larger than the aborts sequence number.\\\r
 \begin{algorithmic}[1]\r
 \textbf{Check Abort Live:}\\\r
 Check if an abort data entry is live or not.  Abort is dead if the device whos transaction was aborted sees the abort.  This is checked by seeing if that device inserted a slot into the block chain which has a sequence number that is larger than the aborts sequence number.\\\r
 \begin{algorithmic}[1]\r

-\Function{CheckAbortLive}{$abort_a$}\r
-    \State $\tuple{seq_{a_{abrt}}, seq_{a_{trans}},id_a} \gets abort_a$\\\r
+\Function{CheckAbortLive}{$abort_a, seq_a$}\r
+    \State $\tuple{seq_{a_{trans}},id_a} \gets abort_a$\\\r

     \r
     \LeftComment{The device whos transaction was aborted saw the abort}\r
     \r
     \LeftComment{The device whos transaction was aborted saw the abort}\r

-    \If{$\exists \tuple{id', seq'} \in LastSlot, id'=id_a \land seq' > seq_{a_{abrt}}$}\r
+    \If{$\exists \tuple{id', seq'} \in LastSlot, id'=id_a \land seq' > seq_a$}\r

         \State \Return{false}\r
     \EndIf\r
     \State \Return{True}    \r
         \State \Return{false}\r
     \EndIf\r
     \State \Return{True}    \r


@@ -347,10 +385,10 @@ Check if an abort data entry is live or not.  Abort is dead if the device whos t
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 \textbf{Check Transaction Live:}\\\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 \textbf{Check Transaction Live:}\\\r

-A transaction is dead if there is an abort for that transaction or if there is a commit for that transaction or a transaction that came after this transaction.  Since transactions must be commited in order of there insertion, seeing a transaction that is commited and has a larger sequence number than the transaction in question means that the transaction in question was commited at some point.\\\r
+A transaction is dead if there is an abort for that transaction or if there is a commit for that a transaction that came after this transaction.  Since transactions must be commited in order of there insertion, seeing a transaction that is commited and has a larger sequence number than the transaction in question means that the transaction in question was commited at some point.\\\r

 \begin{algorithmic}[1]\r
 \Function{CheckTransLive}{$trans_a$}\r
 \begin{algorithmic}[1]\r
 \Function{CheckTransLive}{$trans_a$}\r

-    \State $\tuple{seq_a, KV_a, Guard_a} \gets trans_a$\r
+    \State $\tuple{seq_a, id_a, KV_a, Guard_a} \gets trans_a$\r

     \State $AllCommits \gets$ \Call{GetCommits}{} \Comment{Get all the commits}\r
     \State $AllAborts \gets$ \Call{GetAborts}{} \Comment{Get all the aborts} \\\r
     \r
     \State $AllCommits \gets$ \Call{GetCommits}{} \Comment{Get all the commits}\r
     \State $AllAborts \gets$ \Call{GetAborts}{} \Comment{Get all the aborts} \\\r
     \r


@@ -371,11 +409,11 @@ A transaction is dead if there is an abort for that transaction or if there is a
 \textbf{Check Live:}\\\r
 Checks if a data entry is live based on its type.\\\r
 \begin{algorithmic}[1]\r
 \textbf{Check Live:}\\\r
 Checks if a data entry is live based on its type.\\\r
 \begin{algorithmic}[1]\r

-\Function{CheckLive}{$datentry$}\r
+\Function{CheckLive}{$datentry, seq$}\r

     \If{$datentry$ is a $commit$}\r
         \State \Return{\Call{CheckCommitLive}{$datentry$}}\\r
     \ElsIf{$datentry$ is a $abort$}\r
     \If{$datentry$ is a $commit$}\r
         \State \Return{\Call{CheckCommitLive}{$datentry$}}\\r
     \ElsIf{$datentry$ is a $abort$}\r

-        \State \Return{\Call{CheckAbortLive}{$datentry$}}\\r
+        \State \Return{\Call{CheckAbortLive}{$datentry, seq$}}\\r

     \ElsIf{$datentry$ is a $trans$}\r
         \State \Return{\Call{CheckTransLive}{$datentry$}}\\r
     \ElsIf{$datentry$ is a $lastmsg$}\r
     \ElsIf{$datentry$ is a $trans$}\r
         \State \Return{\Call{CheckTransLive}{$datentry$}}\\r
     \ElsIf{$datentry$ is a $lastmsg$}\r


@@ -404,7 +442,7 @@ Check if the slot has any live data entries in it. Do this by looking at all the
     \State $\tuple{s_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in LocalSlots$\r
     \r
     \ForAll{$datentry \in DE$}\r
     \State $\tuple{s_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in LocalSlots$\r
     \r
     \ForAll{$datentry \in DE$}\r

-        \If{\Call{CheckLive}{$datentry$}} \Comment{an entry is alive}\r
+        \If{\Call{CheckLive}{$datentry, s_1$}} \Comment{an entry is alive}\r

             \State \Return{true}\r
         \EndIf\r
     \EndFor\r
             \State \Return{true}\r
         \EndIf\r
     \EndFor\r


@@ -469,7 +507,20 @@ Generate a queue state data entry.\\
 \end{varwidth}% \r
 }\r
 \r
 \end{varwidth}% \r
 }\r
 \r

-% Generate Transaction\r
+% Create Abort\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Create Abort:}\\\r
+Generate a abort data entry.\\\r
+\begin{algorithmic}[1]\r
+\Function{CreateAbort}{$seq_a, id_a$}\r
+    \State \Return{$\tuple{seq_a, id_a}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Create Transaction\r

 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 \textbf{Create Transaction:}\\\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 \textbf{Create Transaction:}\\\r


@@ -477,7 +528,20 @@ Generate a transaction data entry.\\
 \begin{algorithmic}[1]\r
 \Function{CreateTrans}{$pendingtrans_a, seq_a$}\r
     \State $\tuple{KV_a, Guard_a} \gets pendingtrans_a$\r
 \begin{algorithmic}[1]\r
 \Function{CreateTrans}{$pendingtrans_a, seq_a$}\r
     \State $\tuple{KV_a, Guard_a} \gets pendingtrans_a$\r

-    \State \Return{$\tuple{seq_a, KV_a, Guard_a}$}    \r
+    \State \Return{$\tuple{seq_a, LOCAL\_ID, KV_a, Guard_a}$}    \r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Create Commit\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Create Commit:}\\\r
+Generate a commit data entry.\\\r
+\begin{algorithmic}[1]\r
+\Function{CreateCommit}{$seq_a,KV_a$}\r
+    \State \Return{$\tuple{seq_a,KV_a}$}\r

 \EndFunction\r
 \end{algorithmic}\r
 \end{varwidth}% \r
 \EndFunction\r
 \end{algorithmic}\r
 \end{varwidth}% \r


@@ -499,13 +563,11 @@ Checks if a data entry set has enough space for a new data entry to be inserted.
 \end{varwidth}% \r
 }\r
 \r
 \end{varwidth}% \r
 }\r
 \r

-\r
-\r

 % Create Rescued Commit\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 \textbf{Create Rescued Date Entry:}\\\r
 % Create Rescued Commit\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 \textbf{Create Rescued Date Entry:}\\\r

-Generate the data entry rescued version of the entry.  For some data entry types such as commits, the entry is not rescued as is.  For commits only the key-value pairs that are most recent (no newer commit that has those key values in it).\\\r
+For commits only the key-value pairs that are most recent (no newer commit that has those key values in it).\\\r

 \begin{algorithmic}[1]\r
 \Function{CreateRescuedCommit}{$commit_a$}\r
     \State $AllCommits \gets $ \Call{GetCommits}{}\r
 \begin{algorithmic}[1]\r
 \Function{CreateRescuedCommit}{$commit_a$}\r
     \State $AllCommits \gets $ \Call{GetCommits}{}\r


@@ -528,7 +590,6 @@ Generate the data entry rescued version of the entry.  For some data entry types
 \end{varwidth}% \r
 }\r
 \r
 \end{varwidth}% \r
 }\r
 \r

-\r

 % Create Rescued Date Entry\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 % Create Rescued Date Entry\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r


@@ -542,12 +603,36 @@ Generate the data entry rescued version of the entry.  For some data entry types
     \EndIf\r
     \r
     \State \Return{$de_a$} \Comment{No Modification needed}\r
     \EndIf\r
     \r
     \State \Return{$de_a$} \Comment{No Modification needed}\r

-\r

 \EndFunction\r
 \end{algorithmic}\r
 \end{varwidth}% \r
 }\r
 \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
 \r
 % Mandatory Rescue\r
 \noindent\fbox{%\r


@@ -562,10 +647,11 @@ This rescue is mandatory before any types of data entries (excpet queue states)
     \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
     \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 $\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
         \r
         \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r

-            \If{\Call{CheckLive}{$de$}} \Comment{data entry is live}\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
                 \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


@@ -586,14 +672,160 @@ This rescue is mandatory before any types of data entries (excpet queue states)
 \end{varwidth}% \r
 }\r
 \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 enough 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
+% 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{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'=v'\}$\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'=v'\}$\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
 \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
 \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.\\\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
 \begin{algorithmic}[1]\r
 \Function{TryInsertTransaction}{$pendingtrans_a, forceresize$}\r
     \State $DE \gets \emptyset$ \Comment{The data entries for this slot}\r


@@ -601,6 +833,7 @@ Try to insert a transaction into the block chain.\\
     \State $newsize \gets 0$\r
     \State $trans \gets$ \Call{CreateTrans}{$pendingtrans_a, seq$}\r
     \State $transinserted \gets false$\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
     \r
     \State $resize \gets $ \Call{ShouldResize}{ } \Comment{Check if we should resize}\r
     \State $resize \gets resize \lor forceresize$\r


@@ -609,26 +842,29 @@ Try to insert a transaction into the block chain.\\
         \State $DE \gets DE \cup \{$\Call{CreateQState}{$newsize$}$\}$\r
     \EndIf\\\r
     \r
         \State $DE \gets DE \cup \{$\Call{CreateQState}{$newsize$}$\}$\r
     \EndIf\\\r
     \r

-    \r
-    \r
-    \r

     %\If{$RejectedSlotList \neq \emptyset$}   \r
     %\EndIf\r
     \r
     %\If{$RejectedSlotList \neq \emptyset$}   \r
     %\EndIf\r
     \r

-    % Arbitrate\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{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
     \If{\Call{DEHasSpace}{$DE, trans$}} \Comment{transaction fits}\r
         \State $DE \gets DE \cup trans$\r
         \State $transinserted \gets true$\r

-    \EndIf\r
+    \EndIf\\\r

     \r
     \r

+    \LeftComment{Rescue data to fill slot data entry section}\r
+    \State $DE \gets$ \Call{OptionalRescue}{$DE$}\\\r

     \r
     \r

+    \LeftComment{Send to server.}\r
+    \State $\tuple{sendsuccess, newslots} \gets $ \Call{SendToServer}{$seq, DE, newsize$}\r
+    \r
+    \State \Return{$transinserted \land success$} \Comment{Return if  succeeded or not}\r

     \r
 \EndFunction\r
 \end{algorithmic}\r
     \r
 \EndFunction\r
 \end{algorithmic}\r


@@ -708,12 +944,9 @@ Commits the transaction into the block chain.  Keeps attempting to insert the tr
 \begin{algorithmic}[1]\r
 \Function{Transaction Commit}{$ $}\r
     \State $success \gets False$\r
 \begin{algorithmic}[1]\r
 \Function{Transaction Commit}{$ $}\r
     \State $success \gets False$\r

-    \r

     \While{$\lnot success$}\r
     \While{$\lnot success$}\r

-        \State $success \gets$\r
+        \State $success \gets$ \Call{TryInsertTransaction}{$PendingTrans, false$}\r

     \EndWhile\r
     \EndWhile\r

-    \r
-    \r

 \EndFunction\r
 \end{algorithmic}\r
 \end{varwidth}% \r
 \EndFunction\r
 \end{algorithmic}\r
 \end{varwidth}% \r