version2/doc/iotcloud.tex

   1 \documentclass[11pt]{article}\r
   2 \newcommand{\tuple}[1]{\ensuremath \langle #1 \rangle}\r
   3 \usepackage{color}\r
   4 \usepackage{amsthm}\r
   5 \usepackage{amsmath}\r
   6 \usepackage{graphicx}\r
   7 \usepackage{mathrsfs}\r
   8 \usepackage{amssymb}\r
   9 \usepackage{algorithm}\r
  10 \usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx\r
  11 \usepackage[all]{xy}\r
  12 \usepackage{varwidth}\r
  13 \r
  14 \newtheorem{theorem}{Theorem}\r
  15 \newtheorem{prop}{Proposition}\r
  16 \newtheorem{lem}{Lemma}\r
  17 \newtheorem{defn}{Definition}\r
  18 \newcommand{\note}[1]{{\color{red} \bf [[#1]]}}\r
  19 \newcommand{\push}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}\r
  20 \newcommand*\xor{\mathbin{\oplus}}\r
  21 \algnewcommand{\LeftComment}[1]{\Statex \(\triangleright\) #1}\r
  22 \algnewcommand{\algorithmicgoto}{\textbf{go to}}%\r
  23 \algnewcommand{\Goto}[1]{\algorithmicgoto~\ref{#1}}%\r
  24 \r
  25 \r
  26 \begin{document}\r
  27 \r
  28 \r
  29 \setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text\r
  30 \r
  31 \r
  32 \section{\textbf{Introduction}}\r
  33 \r
  34 \r
  35 \section{Approach}\r
  36 \r
  37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
  38 \r
  39 \subsection{The Arbitrator}\r
  40 Each key has an arbitrator that makes the final decision when it comes to whether a specific transaction containing that key updates the state of the system or is aborted.  This ensures that clients can make offline updates and then push those updates to the server at a later time.  The arbitrator then tries to merge those updates and if possible will commit them into the current working state of the system.  If not possible then the arbitrator will abort that transaction.  The arbitrator arbitrates on transactions in order of transaction sequence number.\r
  41 \r
  42 \r
  43 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
  44 \section{Server Algorithm}\r
  45 $s \in SN$ is a sequence number\\\r
  46 $sv \in SV$ is a slot's value\\\r
  47 $slot_s = \tuple{s, sv} \in SL \subseteq SN \times SV$ \\ \\\r
  48 \textbf{State} \\\r
  49 \textit{SL = set of live slots on server} \\\r
  50 \textit{max = maximum number of slots (input only for resize message)} \\\r
  51 \textit{n = number of slots} \\ \\\r
  52 \textbf{Helper Function} \\\r
  53 $MaxSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv}\r
  54 \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
  55 $MinSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \r
  56 \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\\r
  57 $SeqN(slot_s = \tuple{s, sv})=s$ \\\r
  58 $SlotVal(slot_s = \tuple{s, sv})=sv$ \\\r
  59 \r
  60 %\noindent\fbox{%\r
  61 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
  62 \textbf{Get Slot:}\\\r
  63 Returns to the client the slots that have a sequence number that is greater than or equal to the sequence number that is in the request.\r
  64 \begin{algorithmic}[1]\r
  65 \Function{GetSlot}{$s_g$} throws $Server\_Connection\_Timeout$, $Server\_Response\_Timeout$\r
  66 \State \Return{$\{\tuple{s, sv} \in SL \mid s \geq s_g\}$}\r
  67 \EndFunction\r
  68 \end{algorithmic}%\end{varwidth}% \r
  69 %}\r
  70 \r
  71 \r
  72 %\noindent\fbox{%\r
  73 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
  74 \textbf{Get Slot:}\\\r
  75 Puts a slot in the server memory if the slot has the correct sequence number.  Also resizes the server memory if needed.\r
  76 \begin{algorithmic}[1]\r
  77 \Function{PutSlot}{$s_p,sv_p,max'$} throws $Server\_Connection\_Timeout$, $Server\_Response\_Timeout$\r
  78 \If{$(max' \neq \emptyset)$}  \Comment{Resize}\r
  79 \State $max \gets max'$\r
  80 \EndIf\r
  81 \State $\tuple{s_n,sv_n} \gets MaxSlot(SL)$\Comment{Last sv}\r
  82 %\State $s_n \gets SeqN(\tuple{s_n,sv_n})$\r
  83 \If{$(s_p = s_n + 1)$}\r
  84     \If{$n = max$}\r
  85         \State $\tuple{s_m,sv_m} \gets MinSlot(SL)$\Comment{First sv}\r
  86         \State $SL \gets SL - \{\tuple{s_m,sv_m}\}$\r
  87     \Else \Comment{$n < max$}\r
  88         \State $n \gets n + 1$\r
  89     \EndIf\r
  90     \State $SL \gets SL \cup \{\tuple{s_p,sv_p}\}$\r
  91     \State \Return{$(true,\emptyset)$}\r
  92 \Else\r
  93     \State \Return{$(false,\{\tuple{s,sv}\in SL \mid \r
  94     s \geq s_p\})$}\r
  95 \EndIf\r
  96 \EndFunction\r
  97 \end{algorithmic}%\end{varwidth}% \r
  98 %}\r
  99 \r
 100 \r
 101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 102 \section{Client Algorithm}\r
 103 \r
 104 \subsection{\textbf{Client Notation Conventions}}\r
 105 $k$ is key of entry \\\r
 106 $v$ is value of entry \\\r
 107 $size$ is a size (target size of the current block chain) \\\r
 108 $kv$ is a key-value pair $\tuple{k,v}$ \\\r
 109 $KV$ is a set of $kv$ \\\r
 110 $G$ is a set of $kv$ that is the guard \\\r
 111 $id$ is a machine ID \\\r
 112 $seq$ is a sequence number \\\r
 113 $hmac_p$ is the HMAC value of the previous slot \\\r
 114 $hmac_c$ is the HMAC value of the current slot \\\r
 115 \r
 116 $colres$ is a collision resolution entry, $\tuple{id, seq_{old}, seq_{new}, true \lor false}$ \\\r
 117 $lastmsg$ is a last message entry, $\tuple{seq, id}$ \\\r
 118 $qstate$ is a queue state entry, $\tuple{size}$ \\\r
 119 $newkey$ is a new key entry, $\tuple{k, id}$, $id$ is ID of arbitrator \\\r
 120 $abort$ is an abort transaction entry, $\tuple{seq_{clientlocal}, seq_{server}, id, arb, seq_{arb}}$ \\\r
 121 $transpart$ is a transaction part entry, $\tuple{Dat,arb,seq_{clientLocal}, seq_{server}, id, partnum, isLast}$\\\r
 122 $compart$ is a commit part entry, $\tuple{Dat,seq_{trans}, seq_{server}, id, partnum, isLast}$\\\r
 123 \r
 124 $de$ is a data entry that can one of: $transpart$, $lastmsg$, $qstate$, $colres$, $newkey$, $compart$, $abort$ \\\r
 125 $DE$ is a set of all data entries, possibly of different types, in a single message, set of $de$\\\r
 126 \r
 127 \r
 128 $pendingTransaction$ is a pending transaction, $\tuple{KV, G, id, seq_{clientLocal}}$ \\\r
 129 $Transaction$ is a Transaction container that houses transaction parts together, $\tuple{Parts, KV, G,seq_{local}, seq_{server},id, arb}$\\\r
 130 $Commit$ is a commit container that houses commit parts together, $\tuple{Parts, KV, seq_{trans}, seq_{server},id}$\r
 131 $ArbitrationRound$ is a commit and a group of aborts where all the aborts must be sent before the commit, $\tuple{commit, AbortSet, SentSet}$\r
 132 \r
 133 $status$ is the status of a transaction and can be: $aborted, pending, committed, sentpartial, sentfully, noeffect$\r
 134 $TransStatus$ is the status of a transaction, $\tuple{status}$\\\r
 135 \r
 136 $slotDat = \tuple{seq,id,DE,hmac_p,hmac_c}$ \\\r
 137 $slot = \tuple{seq, Encrpt(slotDat)}$\\\r
 138 \r
 139 \r
 140 \subsubsection{Constants}\r
 141 $LOCAL\_ID$ = machine ID of this client.\\\r
 142 $RESIZE\_THRESH\_PERCENT$ = percent of slots that need to have live data to trigger a resize.\\\r
 143 $RESIZE\_PERCENT$ = percent that we should grow the block chain to.\\\r
 144 $DATA\_ENTRY\_SET\_MAX\_SIZE$ = max size that a data entry set can have (in bytes).\\\r
 145 $DEAD\_SLOT\_COUNT$ = number of slots to keep dead if possible at the end of the block chain.\\\r
 146 $MAX\_RESCUE\_SKIPS$ = number of skips that are allowed when saving data entries.\\\r
 147 $MAX\_ROUND\_SIZE$ = max number of parts that an arbitration round can have before being full. \\\r
 148 \r
 149 \subsubsection{Primitive Variables}\r
 150 $max\_size$ = max size of the block chain.\\\r
 151 $clntTransactionNum \gets 0$ = current client transaction number that this client created.\\\r
 152 $newPendingTransaction$ = transaction being built.\\\r
 153 $arbitrationSeqNum \gets 0$ = sequence number used by the arbitrator to label the commits and aborts it creates\\\r
 154 $hadPartialSendToServer gets false$ = if the last attempt to send the server had a recieve timeout.\\\r
 155 \r
 156 \r
 157 \subsubsection{Sets and Lists}\r
 158 \r
 159 $Arbitrator$ = set of $\tuple{k,id}$ containing the key and its arbitrating device.\\\r
 160 $LastSlot$ = set of $\tuple{id, seq}$ containing the machine id and the sequence number of the last slot.\\\r
 161 $Arbitrator$ = set of $\tuple{k,id}$ containing the key and its arbitrating device.\\ne ID and the largest sequence number from that machine ID.\\\r
 162 $LocalSlots$ = set of slots that are in the clients local buffer (initially $\emptyset$), data is decrypted.\\\r
 163 $RejectedSlotList$ = ordered list of the sequence numbers of slots that this client tried to insert but were rejected.\\\r
 164 $CommittedKV$ = set of committed key value pairs (initially $\emptyset$).\\\r
 165 $SpeculatedKV$ = set of speculated key value pairs (initially $\emptyset$).\\\r
 166 $PendingTransactionQueue$ = queue of transactions that need to be sent.\\\r
 167 $LastTransactionArbitrated$ = set of $\tuple{id, seq}$ with the last sequence number an arbitrator arbitrated on.\\\r
 168 $LiveTransactions$ = set of transactions with their parts.\\\r
 169 $LiveCommits$ = set of live commits and their parts.\\\r
 170 $OfflineTransAtServer$ = set of transactions that were sent to the server but were arbitrated through local communication.\\ \r
 171 $SendArbQueue$ = queue of arbitration rounds that have yet to be sent to the server.\\\r
 172 $LastTransSeenMid$ = Last transaction seen from a specific machine from the server.\\\r
 173 $LastArbLocalArbitrated$ = Last local sequence number seen from a client.\\\r
 174 $LastCommitSeenFromArbitrator$ = last commit seen from a specific arbitrator.\\\r
 175 \r
 176 \subsection{Helper Functions}\r
 177 The following helper functions are needed:\\\r
 178 \r
 179 $MaxSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
 180 $MinSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\\r
 181 $DecodeParts(transpart)= $ Converts the part data into KV sets and Guard Condition sets.\\\r
 182 $DecodeParts(compart)= $ Converts the part data into a KV set.\\\r
 183 $GenerateParts(Commit)= $ Fills the commit with parts generated by its content.\\\r
 184 $GenerateParts(Transaction)= $ Fills the transaction with parts generated by its content.\\\r
 185 $SetTransStatus(TransStatus, Transaction_Identifier) = $ saves a transaction status.\\ \r
 186 $ChangeTransStatus(TransStatus, newStatus) = $ changes a transaction status.\\ \r
 187 $GetTransStatus(Transaction_Identifier) = $ gets a transaction status.\\ \r
 188 $DeleteTransStatus(Transaction_Identifier) = $ delete a transaction status.\\ \r
 189 \r
 190 % Get Size\r
 191 %\noindent\fbox{%\r
 192 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 193 \textbf{Get Byte Size:}\\\r
 194 Get the size in bytes of the thing that is passed in.\r
 195 \begin{algorithmic}[1]\r
 196 \Function{GetSize}{$a$}\r
 197     \State \Return{Size in bytes of $a$}\r
 198 \EndFunction\r
 199 \end{algorithmic}\r
 200 %\end{varwidth}% \r
 201 %}\r
 202 \r
 203 % Error\r
 204 %\noindent\fbox{%\r
 205 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 206 \textbf{ Error:}\\\r
 207 Prints an error message and halts the execution of the client.\r
 208 \begin{algorithmic}[1]\r
 209 \Function{Error}{$msg$}\r
 210     \State $Print(msg)$\r
 211     \State $Halt()$\r
 212 \EndFunction\r
 213 \end{algorithmic}\r
 214 %\end{varwidth}% \r
 215 %}\r
 216 \r
 217 % Calculate Resize Threshold\r
 218 %\noindent\fbox{%\r
 219 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 220 \textbf{Calculate Resize Threshold:}\\\r
 221 Calculate a threshold for how many slots need to have live data entries in them for a resize to take place.\r
 222 \begin{algorithmic}[1]\r
 223 \Function{CalcResizeThresh}{$maxsize$}\r
 224     \State $lower \gets \left \lfloor {maxsize * RESIZE\_THRESH\_PERCENT} \right \rfloor - 1$\r
 225     \State \Return{$lower + $\Call{Random}{$maxsize - lower$}}\r
 226 \EndFunction\r
 227 \end{algorithmic}\r
 228 %\end{varwidth}% \r
 229 %}\r
 230 \r
 231 % Calculate Block Chain New Size\r
 232 %\noindent\fbox{%\r
 233 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 234 \textbf{Calculate Block Chain New Size:}\\\r
 235 Calculate the new size of the block chain which we need if we are to resize the data structure.\r
 236 \begin{algorithmic}[1]\r
 237 \Function{CalcNewSize}{$maxsize$}\r
 238     \State \Return{$\left \lceil {maxsize * RESIZE\_PERCENT} \right \rceil$}\r
 239 \EndFunction\r
 240 \end{algorithmic}\r
 241 %\end{varwidth}% \r
 242 %}\r
 243 \r
 244 % Should Resize\r
 245 %\noindent\fbox{%\r
 246 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 247 \textbf{Should Resize:}\\\r
 248 Check if the block should resize based on some metric of how many slots in the block chain are filled with live data. \r
 249 \begin{algorithmic}[1]\r
 250 \Function{ShouldResize}{$ $}\r
 251     \State $LiveSlots \gets \{slot_s|slot_s \in LocalSlots \land $\Call{SlotHasLive}{$slot_s$}$\}$\r
 252     \State \Return{$|LiveSlots| \geq $\Call{CalcResizeThresh}{$max\_size$}} \r
 253 \EndFunction\r
 254 \end{algorithmic}\r
 255 %\end{varwidth}% \r
 256 %}\r
 257 \r
 258 \r
 259 % Data Entry Set Has Space \r
 260 %\noindent\fbox{%\r
 261 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 262 \textbf{Data Entry Set Has Space :}\\\r
 263 Checks if a data entry set has enough space for a new data entry to be inserted.\r
 264 \begin{algorithmic}[1]\r
 265 \Function{DEHasSpace}{$DE_a, de_a$}\r
 266     \State $newsize \gets $ \Call{GetSize}{$DE_a$} $ + $ \Call{GetSize}{$de_a$}\r
 267     \State \Return{$newsize \leq DATA\_ENTRY\_SET\_MAX\_SIZE$}\r
 268 \EndFunction\r
 269 \end{algorithmic}\r
 270 %\end{varwidth}% \r
 271 %}\r
 272 \r
 273 % Get Arbitrator\r
 274 %\noindent\fbox{%\r
 275 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 276 \textbf{Get Arbitrator:}\\\r
 277 Get the arbitrator for a given key.\r
 278 \begin{algorithmic}[1]\r
 279 \Function{GetArbitrator}{$k$}\r
 280     \State $\tuple{k_1,id_1} \gets \tuple{k_2,id_2} $ \textit{such that} $ \tuple{k_2,id_2} \in Arbitrator \land k_2=k$\r
 281     \State \Return{$id_1$}\r
 282 \EndFunction\r
 283 \end{algorithmic}\r
 284 %\end{varwidth}% \r
 285 %}\r
 286 \r
 287 % Get Arbitrator KV\r
 288 %\noindent\fbox{%\r
 289 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 290 \textbf{Get Arbitrator for KV Set:}\\\r
 291 Get the arbitrator for a given key value set.\r
 292 \begin{algorithmic}[1]\r
 293 \Function{GetArbitratorKV}{$KV_a$} \r
 294     \State \Return{$id'$ such that $\exists \tuple{k',v'} \in KV_a, id' =$ \Call{GetArbitrator}{$k'$}}\r
 295 \EndFunction\r
 296 \end{algorithmic}\r
 297 %\end{varwidth}% \r
 298 %}\r
 299 \r
 300 % Get Next Sequence Number\r
 301 %\noindent\fbox{%\r
 302 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 303 \textbf{Get Next Sequence Number:}\\\r
 304 Get the next sequence number for insertion into the block chain.\r
 305 \begin{algorithmic}[1]\r
 306 \Function{GetNextSeq}{$k$}\r
 307     \LeftComment{Get the largest known sequence number}\r
 308     \State $seq_{ret} \gets seq$ such that $\tuple{id, seq}\in LastSlot \land (\forall \tuple{id', seq'} \in LastSlo, seq \geq seq')$\\\r
 309     \r
 310     \LeftComment{Add one to the largest seq number to generate the new seq number}\r
 311     \State \Return{$seq_{ret} + 1$}\r
 312 \EndFunction\r
 313 \end{algorithmic}\r
 314 %\end{varwidth}% \r
 315 %}\r
 316 \r
 317 % Create Collision\r
 318 %\noindent\fbox{%\r
 319 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 320 \textbf{Create ColRes:}\\\r
 321 Generate a colres data entry.\r
 322 \begin{algorithmic}[1]\r
 323 \Function{CreateColRes}{$is_a, seq_{a_{old}}, seq_{a_{new}}, isequal_a$}\r
 324     \State \Return{$\tuple{id_a, seq_{a_{old}}, seq_{a_{new}},}isequal_a$}\r
 325 \EndFunction\r
 326 \end{algorithmic}\r
 327 %\end{varwidth}% \r
 328 %}\r
 329 \r
 330 % Check and Create Last Message Data Entry\r
 331 %\noindent\fbox{%\r
 332 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 333 \textbf{Check and Create Last Message Data Entry:}\\\r
 334 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
 335 \begin{algorithmic}[1]\r
 336 \Function{CheckCreateLastMsgEntry}{$seq_a, id_a$}\r
 337     \State $AllLastMsg \gets$ \Call{GetLastMsg}{}\\\r
 338     \r
 339     \LeftComment{Already Has one}\r
 340     \If{$\exists  \tuple{seq', id'} \in AllLastMsg, id_a=id' \land seq'=seq_a$}\r
 341         \State \Return{$\emptyset$}\r
 342     \EndIf\\\r
 343     \r
 344     \LeftComment{Not latest slot from that client}\r
 345     \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
 346         \State \Return{$\emptyset$}\\\r
 347     \EndIf\\\r
 348     \r
 349     \State \Return{$\{\tuple{seq_a, id_a}\}$}\r
 350 \EndFunction\r
 351 \end{algorithmic}\r
 352 %\end{varwidth}% \r
 353 %}\r
 354 \r
 355 %Evaluate Guard\r
 356 %\noindent\fbox{%\r
 357 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 358 \textbf{Evaluate Guard:}\\\r
 359 Evaluate Guard Condition checks if all the KV pairs in the guard condition match the declared KV pairs.\r
 360 \begin{algorithmic}[1]\r
 361 \Function{EvaluateGuard}{$G_a, KV_a$}\r
 362 \r
 363     \If{$\exists \tuple{k_G, v_G} \in G_a, \tuple{k_{KV},v_{KV}} \in KV_a, k_G=K_{KV} \land v_G \neq v_{KV}$}\r
 364         \State \Return{False}\r
 365     \EndIf\r
 366     \r
 367     \State \Return{True}\r
 368 \EndFunction\r
 369 \end{algorithmic}\r
 370 %\end{varwidth}% \r
 371 %}\r
 372 \r
 373 % Get all aborts\r
 374 %\noindent\fbox{%\r
 375 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 376 \textbf{Get all aborts:}\\\r
 377 Get all aborts that are currently in the local block chain.  Iterate over all the local slots and extract all the aborts from each slot.\r
 378 \begin{algorithmic}[1]\r
 379 \Function{GetAborts}{$ $}\r
 380     \State $AbrtSet \gets \emptyset$ \Comment{Set of the aborts}\\\r
 381         \r
 382     \LeftComment{Iterate over all the slots saved locally}\r
 383     \ForAll{$\tuple{s_1', \tuple{seq',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 384         \ForAll{$a' \in DE', a'$ is a $abort$}\r
 385             \State $\tuple{seq_l', seq_s', id', arb', seq_{arb}'} \gets a'$\r
 386             \State $AbrtSet \gets AbrtSet \cup \{seq_l', seq_s', id', arb', seq_{arb}', seq'\}$\r
 387         \EndFor\r
 388     \EndFor\r
 389     \State \Return{$AbrtSet$}\r
 390 \EndFunction\r
 391 \end{algorithmic}\r
 392 %\end{varwidth}% \r
 393 %}\r
 394 \r
 395 % Get all Queue States\r
 396 %\noindent\fbox{%\r
 397 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 398 \textbf{Get all queue states:}\\\r
 399 Get all qstates that are currently in the local block chain.  Iterate over all the local slots and extract all the qstates from each slot.\r
 400 \begin{algorithmic}[1]\r
 401 \Function{GetQStates}{$ $}\r
 402     \State $QSet \gets \emptyset$ \Comment{Set of the qstates}\\\r
 403         \r
 404     \LeftComment{Iterate over all the slots saved locally}\r
 405     \ForAll{$\tuple{s_1', \tuple{seq',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 406         \ForAll{$q' \in DE', q'$ is a $qstate$}\r
 407             \State $\tuple{size'} \gets q'$\r
 408             \State $QSet \gets QSet \cup \{\tuple{size', seq'}\}$\r
 409         \EndFor\r
 410     \EndFor\r
 411     \State \Return{$QSet$}\r
 412 \EndFunction\r
 413 \end{algorithmic}\r
 414 %\end{varwidth}% \r
 415 %}\r
 416 \r
 417 % Get all New Keys\r
 418 %\noindent\fbox{%\r
 419 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 420 \textbf{Get all new keys:}\\\r
 421 Get all new keys that are currently in the local block chain.  Iterate over all the local slots and extract all the new keys from each slot.\r
 422 \begin{algorithmic}[1]\r
 423 \Function{GetNewKeys}{$ $}\r
 424     \State $NKSet \gets \emptyset$ \Comment{Set of the new keys}\\\r
 425         \r
 426     \LeftComment{Iterate over all the slots saved locally}\r
 427     \ForAll{$\tuple{s_1', \tuple{seq',id_1',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 428         \ForAll{$nk' \in DE', nk'$ is a $newkey$}\r
 429             \State $\tuple{k', id_2'} \gets nk'$\r
 430             \State $NKSet \gets NKSet \cup \{\tuple{k', id_2', seq'}\}$\r
 431         \EndFor\r
 432     \EndFor\r
 433     \State \Return{$NKSet$}\r
 434 \EndFunction\r
 435 \end{algorithmic}\r
 436 %\end{varwidth}% \r
 437 %}\r
 438 \r
 439 % Get all Collision Resolutions\r
 440 %\noindent\fbox{%\r
 441 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 442 \textbf{Get all collision resolutions:}\\\r
 443 Get all the collision resolution entries fron the slots. \r
 444 \begin{algorithmic}[1]\r
 445 \Function{GetColRes}{$ $}\r
 446     \State $CRSet \gets \emptyset$ \Comment{Set of the new keys}\\\r
 447         \r
 448     \LeftComment{Iterate over all the slots saved locally}\r
 449     \ForAll{$\tuple{s_1', \tuple{seq',id_1',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 450         \ForAll{$cr' \in DE', nk'$ is a $colres$}\r
 451             \State $\tuple{id', seq_{old}', seq_{new}', local'} \gets cr'$\r
 452             \State $CRSet \gets CRSet \cup \{\tuple{id', seq_{old}', seq_{new}', local', seq'}\}$\r
 453         \EndFor\r
 454     \EndFor\r
 455     \State \Return{$CRSet$}\r
 456 \EndFunction\r
 457 \end{algorithmic}\r
 458 %\end{varwidth}% \r
 459 %}\r
 460 \r
 461 % Get all Last Messages States\r
 462 %\noindent\fbox{%\r
 463 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 464 \textbf{Get all last message data entries:}\\\r
 465 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
 466 \begin{algorithmic}[1]\r
 467 \Function{GetLastMsg}{$ $}\r
 468     \State $LMSet \gets \emptyset$ \Comment{Set of the last msg}\\\r
 469         \r
 470     \LeftComment{Iterate over all the slots saved locally}\r
 471     \ForAll{$\tuple{s_1', \tuple{seq_1',id_1',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 472         \ForAll{$lm' \in DE', lm'$ is a $lastmsg$}\r
 473             \State $\tuple{seq_2', id_2'} \gets lm'$\r
 474             \State $LMSet \gets LMSet \cup \{\tuple{seq_2', id_2', seq_1'}\}$\r
 475         \EndFor\r
 476     \EndFor\r
 477     \State \Return{$LMSet$}\r
 478 \EndFunction\r
 479 \end{algorithmic}\r
 480 %\end{varwidth}%\r
 481 %}\r
 482 \r
 483 % Get all Transaction Parts\r
 484 %\noindent\fbox{%\r
 485 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 486 \textbf{Get all the transaction part entries:}\\\r
 487 Get all the transaction parts from the slots.\r
 488 \begin{algorithmic}[1]\r
 489 \Function{GetTransParts}{$ $}\r
 490     \State $TPSet \gets \emptyset$ \r
 491         \r
 492     \LeftComment{Iterate over all the slots saved locally}\r
 493     \ForAll{$\tuple{s_1', \tuple{seq_1',id_1',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 494         \ForAll{$tp' \in DE', tp'$ is a $transpart$}\r
 495             \State $\tuple{Dat',arb',seq_{clientLocal}', seq_{server}', id', partnum', isLast'} \gets tp'$\r
 496             \State $TPSet \gets TPSet \cup \{\tuple{Dat',arb',seq_{clientLocal}', seq_{server}', id', partnum', isLast', seq_1'}\}$\r
 497         \EndFor\r
 498     \EndFor\r
 499     \State \Return{$TPSet$}\r
 500 \EndFunction\r
 501 \end{algorithmic}\r
 502 %\end{varwidth}%\r
 503 %}\r
 504 \r
 505 % Get all Commit Parts\r
 506 %\noindent\fbox{%\r
 507 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 508 \textbf{Get all the commit part entries:}\\\r
 509 Get all the commit parts from the slots.\r
 510 \begin{algorithmic}[1]\r
 511 \Function{GetComParts}{$ $}\r
 512     \State $CPSet \gets \emptyset$ \r
 513         \r
 514     \LeftComment{Iterate over all the slots saved locally}\r
 515     \ForAll{$\tuple{s_1', \tuple{seq_1',id_1',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 516         \ForAll{$cp' \in DE', cp'$ is a $compart$}\r
 517             \State $\tuple{Dat',seq_{trans}', seq_{server}', id', partnum', isLast'} \gets cp'$\r
 518             \State $CPSet \gets CPSet \cup \{\tuple{Dat',seq_{trans}', seq_{server}', id', partnum', isLast', seq_1'}\}$\r
 519         \EndFor\r
 520     \EndFor\r
 521     \State \Return{$CPSet$}\r
 522 \EndFunction\r
 523 \end{algorithmic}\r
 524 %\end{varwidth}%\r
 525 %}\r
 526 \r
 527 \r
 528 \r
 529 \r
 530 \r
 531 \r
 532 % Check Queue State Live\r
 533 %\noindent\fbox{%\r
 534 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 535 \textbf{Check Queue State Live:}\\\r
 536 A queue state is dead if there is another queue state data entry that has a larger queue state.\r
 537 \begin{algorithmic}[1]\r
 538 \Function{CheckQStateLive}{$qstate_a, seq_a$}\r
 539     \State $\tuple{size_a} \gets qstate_a$\r
 540     \State $AllQStates \gets$ \Call{GetQState}{} \Comment{Get all the qstates} \\\r
 541     \r
 542     \If{$\exists \tuple{size', seq'} \in AllQStates, size' > size_a$}\r
 543         \State \Return{false}\r
 544     \ElsIf{$\exists \tuple{size', seq'} \in AllQStates, size' = size_a \land seq' > seq_a$}\r
 545         \State \Return{false}\r
 546     \EndIf\r
 547     \State \Return{true}\r
 548     \r
 549 \EndFunction\r
 550 \end{algorithmic}\r
 551 %\end{varwidth}% \r
 552 %}\r
 553 \r
 554 % Check Last Message Live\r
 555 %\noindent\fbox{%\r
 556 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 557 \textbf{Check Last Message Live:}\\\r
 558 The last message is dead if the device in question pushed a slot that has a larger sequence number than the one recorded in the last message data entry. \r
 559 \begin{algorithmic}[1]\r
 560 \Function{CheckLastMsgLive}{$lastmsg_a$}\r
 561     \State $\tuple{seq_a, id_a} \gets lastmsg_a$\\\r
 562     \State $AllLastMsg \gets$ \Call{GetLastMsg}{} \Comment{Get all the last messages} \\\r
 563     \r
 564     \If{$\exists \tuple{seq_1', id', seq_2'} \in AllLastMsg, id'=id_a \land seq_1' > seq_a$}\r
 565         \State \Return{false}\r
 566     \ElsIf{$\exists \tuple{seq_1', id', seq_2'} \in AllLastMsg, id'=id_a \land seq_1' = seq_a \land seq_2' > seq_a$}\r
 567         \State \Return{false}\r
 568     \EndIf\r
 569     \r
 570     \State \Return{True}    \r
 571 \EndFunction\r
 572 \end{algorithmic}\r
 573 %\end{varwidth}% \r
 574 %}\r
 575 \r
 576 % Check New Key Live\r
 577 %\noindent\fbox{%\r
 578 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 579 \textbf{Check New Key Live:}\\\r
 580 A new key data entry is always live unless there is a resuced version of the new key that is newer.\r
 581 \begin{algorithmic}[1]\r
 582 \Function{CheckNewkeyLive}{$newkey_a, seq$}\r
 583     \State $\tuple{k_a, id_a} \gets newkey_a$\r
 584     \State $AllNewKeys \gets$ \Call{GetNewKeys}{} \Comment{Get all the new keys} \\\r
 585     \r
 586     \If{$\exists \tuple{k', id', seq'} \in AllNewKeys, k'=k_a \land id'=id_a \land seq' > seq$}\r
 587         \State \Return{False}\r
 588     \ElsIf{$\exists \tuple{k', id', seq'} \in AllNewKeys, k'=k_a \land id'\neq id_a \land seq' > seq$}\r
 589         \State \Return{False} \Comment{Delete an attempt to insert a new key that already exists}\r
 590     \EndIf\r
 591     \r
 592     \State \Return{True}      \r
 593 \EndFunction\r
 594 \end{algorithmic}\r
 595 %\end{varwidth}% \r
 596 %}\r
 597 \r
 598 % Check Abort Live\r
 599 %\noindent\fbox{%\r
 600 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 601 \textbf{Check Abort Live:}\\\r
 602 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
 603 \begin{algorithmic}[1]\r
 604 \Function{CheckAbortLive}{$abort_a, seq_a$}\r
 605     \State $\tuple{seq_{a_{trans}},id_a} \gets abort_a$\\\r
 606     \r
 607     \LeftComment{The device whos transaction was aborted saw the abort}\r
 608     \If{$\exists \tuple{id', seq'} \in LastSlot, id'=id_a \land seq' > seq_a$}\r
 609         \State \Return{false}\r
 610     \Else\r
 611         \State $AllAborts \gets$ \Call{GetAborts}{} \Comment{Get all the aborts} \\\r
 612         \If{$\exists \tuple{seq_{trans}',id_{trans}', seq'} \in AllAborts,  seq_{a_{trans}} = seq_{trans}' \land id_a = id_{trans}' \land seq' > seq_a$}\r
 613             \State \Return{false}\r
 614         \EndIf\r
 615     \EndIf\r
 616     \State \Return{True}    \r
 617 \EndFunction\r
 618 \end{algorithmic}\r
 619 %\end{varwidth}% \r
 620 %}\r
 621 \r
 622 %Check Collision Resolution Live\r
 623 %\noindent\fbox{%\r
 624 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 625 \textbf{Check Collision Resolution Live:}\\\r
 626 Check if a collision resolution data entry is live or not.  This done by checking if all clients that we know about have seen the collision resolution entry.  This is checked by seeing if all devices have inserted a message with a larger sequence number into the block chain.\r
 627 \begin{algorithmic}[1]\r
 628 \Function{CheckColResLive}{$colres_a, seq_a$}\r
 629     \State $\tuple{id_a, seq_{a_{old}}, seq_{a_{new}}, equal_a} \gets colres_a$\\\r
 630     \r
 631     \If{$\forall \tuple{id', seq'} \in LastSlot, seq' \geq seq_{a_{new}}$}\r
 632         \State \Return{false}\r
 633     \EndIf\r
 634     \r
 635     \State $AllColRes \gets$ \Call{GetColRes}{}\r
 636     \If{$\exists \tuple{id', seq_{old}', seq_{new}', local', seq'} \in AllColRes, id'=id_a \land seq_{old}'= seq_{a_{old}} \land seq_{new}'= seq_{a_{new}} \land local'=equal_a \land seq_2' > seq_a$}\r
 637         \State \Return{false}\r
 638     \EndIf\r
 639     \r
 640     \State \Return{true}\r
 641 \EndFunction\r
 642 \end{algorithmic}\r
 643 %\end{varwidth}% \r
 644 %}\r
 645 \r
 646 %Check Transaction Part Live\r
 647 %\noindent\fbox{%\r
 648 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 649 \textbf{Check Transaction Part Live:}\\\r
 650 Check if a transaction part is live or not.\r
 651 \begin{algorithmic}[1]\r
 652 \Function{CheckTransPartLive}{$transpart_a, seq_a$}\r
 653     \State $\tuple{Dat, arb,seq_{clientLocal}, seq_{server}, id, partnum,isLast} \gets transpart_a$\r
 654     \r
 655     \If{$\exists \tuple{id',seq'} \in LastTransactionArbitrated \land id'=arb land seq' \geq seq_{server}$}\r
 656         \State \Return{False}\r
 657     \EndIf\r
 658     \r
 659     \State $AllTransParts \gets$ \Call{GetTransParts}{} \r
 660     \If{$\exists \tuple{Dat',arb',seq_{clientLocal}', seq_{server}', id', partnum', isLast', seq'} \in AllTransParts, seq_{server} = seq_{server}' \land partnum' = partnum \land seq' > seq_a$}\r
 661         \State \Return{false}\r
 662     \EndIf    \r
 663     \State \Return{True}\r
 664 \EndFunction\r
 665 \end{algorithmic}\r
 666 %\end{varwidth}% \r
 667 %}\r
 668 \r
 669 %Check Commit Part Live\r
 670 %\noindent\fbox{%\r
 671 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 672 \textbf{Check Commit Part Live:}\\\r
 673 Check if a commit part is live or not.\r
 674 \begin{algorithmic}[1]\r
 675 \Function{CheckCommitPartLive}{$commitpart_a, seq_a$}\r
 676     \State $\tuple{Dat,seq_t, seq_s, id, partnum, isLast, seq} \gets commitpart_a$\r
 677     \State $AllComParts \gets $ \Call{GetComParts}{}\\\r
 678     \r
 679     \If{$\exists \tuple{Dat',seq_t', seq_s', id, partnum', isLast', seq'} \in AllComParts, seq_s = seq_s' \land partnum'= partnum \land seq' > seq_a$}\r
 680         \State \Return{False}\r
 681     \EndIf\r
 682     \r
 683     \ForAll{$\tuple{P, KV, seq_t, seq_s,id} \in LiveCommits$}\r
 684         \If{$commitpart_a \in P$}\r
 685             \State \Return{True}\r
 686         \EndIf\r
 687     \EndFor\r
 688     \r
 689     \State \Return{False}\r
 690 \EndFunction\r
 691 \end{algorithmic}\r
 692 %\end{varwidth}% \r
 693 %}\r
 694 \r
 695 % Check Live\r
 696 %\noindent\fbox{%\r
 697 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 698 \textbf{Check Live:}\\\r
 699 Checks if a data entry is live based on its type.\r
 700 \begin{algorithmic}[1]\r
 701 \Function{CheckLive}{$datentry, seq$}\r
 702     \If{$datentry$ is a $compart$}\r
 703         \State \Return{\Call{CheckCommitPartLive}{$datentry, seq$}}\\r
 704     \ElsIf{$datentry$ is a $abort$}\r
 705         \State \Return{\Call{CheckAbortLive}{$datentry, seq$}}\\r
 706     \ElsIf{$datentry$ is a $transpart$}\r
 707         \State \Return{\Call{CheckTransPartLive}{$datentry,seq$}}\\r
 708     \ElsIf{$datentry$ is a $lastmsg$}\r
 709         \State \Return{\Call{CheckLastMsgLive}{$datentry, seq$}}\\r
 710     \ElsIf{$datentry$ is a $colres$}\r
 711         \State \Return{\Call{CheckColResLive}{$datentry, seq$}}\\r
 712     \ElsIf{$datentry$ is a $qstate$}\r
 713         \State \Return{\Call{CheckQStateLive}{$datentry, seq$}}\r
 714     \ElsIf{$datentry$ is a $newkey$}\r
 715         \State \Return{\Call{CheckNewkeyLive}{$datentry, seq$}}\r
 716     \Else\r
 717         \State \Call{Error}{"Unknown data entry type."}\r
 718     \EndIf\r
 719 \EndFunction\r
 720 \end{algorithmic}\r
 721 %\end{varwidth}% \r
 722 %}\r
 723 \r
 724 % Slot Has Live\r
 725 %\noindent\fbox{%\r
 726 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 727 \textbf{Slot Has Live:}\\\r
 728 Check if the slot has any live data entries in it. Do this by looking at all the data entries in the slot and checking if they are live.\r
 729 \begin{algorithmic}[1]\r
 730 \Function{SlotHasLive}{$slot_a$}\r
 731     \State $\tuple{seq_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in LocalSlots$\r
 732     \r
 733     \ForAll{$datentry \in DE$}\r
 734         \If{\Call{CheckLive}{$datentry, seq_1$}} \Comment{an entry is alive}\r
 735             \State \Return{true}\r
 736         \EndIf\r
 737     \EndFor\r
 738     \r
 739     \State \Return{false} \Comment{All entries were dead}    \r
 740 \EndFunction\r
 741 \end{algorithmic}\r
 742 %\end{varwidth}% \r
 743 %}\r
 744 \r
 745 % Rejected Messages\r
 746 %\noindent\fbox{%\r
 747 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 748 \textbf{Rejected Messages:}\\\r
 749 \begin{algorithmic}[1]\r
 750 \Function{RejectedMessages}{$DE_a$}\r
 751     \State $seq_{old} \gets seq$ such that $\tuple{seq} \in RejectedSlotList \land \forall \tuple{seq'} \in RejectedSlotList, seq \geq seq'$\r
 752     \State $prev \gets -1$\\\r
 753     \r
 754     \If{$|RejectedSlotList| \geq REJECTED\_THRESH$}\r
 755         \State $seq_{new} \gets seq$ such that $\tuple{seq} \in RejectedSlotList \land \forall \tuple{seq'} \in RejectedSlotList, seq \leq seq'$\\\r
 756         \State $colres \gets $ \Call{CreateColRes}{$LOCAL\_ID, seq_{old}, seq_{new}, false$}    \r
 757         \State \Return{$DE_a \cup \{colres\}$}\r
 758     \EndIf\\\r
 759     \r
 760     \ForAll{$\tuple{seq} \in RejectedSlotList$ sorted by $seq$}\r
 761         \If{$\exists \tuple{seq',Dat'} \in LocalSlots$}\r
 762             \State Break\r
 763         \EndIf\r
 764         \State $prev \gets seq$\r
 765     \EndFor\\\r
 766     \r
 767     \If{$prev \neq -1$}\r
 768         \State $DE_a \gets DE_a \cup$ \Call{CreateColRes}{$LOCAL\_ID, seq_{old}, prev, false$}\r
 769     \EndIf\\\r
 770     \r
 771     \State $RejectedSlotList \gets \{\tuple{seq}| \tuple{seq} \in RejectedSlotList, seq > prev\}$\\\r
 772     \r
 773     \ForAll{$\tuple{seq} \in RejectedSlotList$ sorted by $seq$}\r
 774         \State $DE_a \gets DE_a \cup$ \Call{CreateColRes}{$LOCAL\_ID, seq,seq, false$}\r
 775     \EndFor\\\r
 776     \r
 777     \State \Return{$DE_a$}\r
 778 \EndFunction\r
 779 \end{algorithmic}\r
 780 %\end{varwidth}% \r
 781 %}\r
 782 \r
 783 % Mandatory Rescue\r
 784 %\noindent\fbox{%\r
 785 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 786 \textbf{Mandatory Rescue:}\\\r
 787 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
 788 \begin{algorithmic}[1]\r
 789 \Function{MandatoryRescue}{$DE_a$}\r
 790     \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
 791     \State $cseq \gets smallestseq$\\\r
 792     \r
 793     \LeftComment{Check the least slots to rescue and live entries}\r
 794     \While{$cseq < (smallestseq + DEAD\_SLOT\_COUNT)$}\r
 795         \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
 796         \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\r
 797         \State $DE' \gets DE' \cup$ \Call{CheckCreateLastMsgEntry}{$seq', id'$} \Comment{Get the last message too if we need it}\\\r
 798         \r
 799         \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
 800             \If{\Call{CheckLive}{$de, cseq$}} \Comment{data entry is live}\r
 801                 \If{\Call{DEHasSpace}{$DE_a, de$}}\r
 802                     \State $DE_a \gets DE_a \cup de$ \Comment{Had enough space to add it}\r
 803                 \ElsIf{$currentseq = smallestseq$}\r
 804                     \State \Return{$\tuple{$true$,DE_a}$}\r
 805                 \Else\r
 806                     \State \Return{$\tuple{$false$,DE_a}$}\r
 807                 \EndIf\r
 808             \EndIf\r
 809         \EndFor\\\r
 810         \r
 811         \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
 812     \EndWhile\r
 813     \r
 814     \State \Return{$\tuple{$false$,DE_a}$}\r
 815 \EndFunction\r
 816 \end{algorithmic}\r
 817 %\end{varwidth}% \r
 818 %}\r
 819 \r
 820 % Optional Rescue\r
 821 %\noindent\fbox{%\r
 822 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 823 \textbf{Optional Rescue:}\\\r
 824 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
 825 \begin{algorithmic}[1]\r
 826 \Function{OptionalRescue}{$DE_a$}\r
 827     \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
 828     \State $largestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \geq seq')$\r
 829 \r
 830     \State $numofskips \gets 0$\r
 831     \State $cseq \gets smallestseq$\\\r
 832     \r
 833     \LeftComment{Check the least slots to rescue and live entries}\r
 834     \While{$cseq < largestseq$}\r
 835         \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
 836         \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\\\r
 837         \r
 838         \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
 839             \If{\Call{CheckLive}{$de, cseq$}} \Comment{data entry is live}\r
 840                 \State $de \gets $ \Call{CreateRescuedEntry}{de} \Comment{Resize entry if needed}\\\r
 841                 \r
 842                 \If{$de \in DE_a$} \Comment{Already being rescued}\r
 843                     \State Continue\r
 844                 \EndIf\\\r
 845                 \r
 846                 \If{\Call{DEHasSpace}{$DE_a, de$}}\r
 847                     \State $DE_a \gets DE_a \cup de$ \Comment{Had enoug space to add it}\r
 848                 \ElsIf{$numofskips \geq MAX\_RESCUE\_SKIPS$}\r
 849                     \State \Return{$DE_a$}\r
 850                 \Else\r
 851                     $numofskips \gets numofskips +1$\r
 852                 \EndIf\r
 853             \EndIf\r
 854         \EndFor\\\r
 855         \r
 856         \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
 857     \EndWhile\r
 858     \r
 859     \State \Return{$DE_a$}\r
 860 \EndFunction\r
 861 \end{algorithmic}\r
 862 %\end{varwidth}% \r
 863 %}\r
 864 \r
 865 % Create New Slot\r
 866 %\noindent\fbox{%\r
 867 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 868 \textbf{Create New Slot:}\\\r
 869 Create a slot and encrypt it.\r
 870 \begin{algorithmic}[1]\r
 871 \Function{CreateNewSlot}{$seq_a, DE_a$}\r
 872     \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
 873     \State $\tuple{seq,id,DE,hmac_p,hmac_c} \gets SDE$\r
 874     \State $newhmac \gets $ \Call{GenerateHmac}{$seq_a, LOCAL\_ID, DE_a, hmac_p$}\r
 875     \State $newSDE \gets \tuple{seq,LOCAL\_ID,DE_a,hmac_c,newhmac}$\r
 876     \State $encryptnewSDE \gets $\Call{Encrypt}{newSDE}\r
 877     \State \Return{$\tuple{seq_a, encryptnewSDE}$}\r
 878 \EndFunction\r
 879 \end{algorithmic}\r
 880 %\end{varwidth}% \r
 881 %}\r
 882 \r
 883 \r
 884 \r
 885 \r
 886 \r
 887 \r
 888 \r
 889 \r
 890 \r
 891 \r
 892 \r
 893 \r
 894 \r
 895 % Fill Slot\r
 896 %% \noindent\fbox{%\r
 897 %% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 898 % \begin{algorithm}\r
 899 \textbf{Fill Slot:}\\\r
 900 Fill a slot with data that needs to be inserted into the block chain.\r
 901 \begin{algorithmic}[1]\r
 902 \Function{FillSlot}{$newkey_a $}\r
 903     \State $resize \gets False$\r
 904     \State $newsize \gets 0$\r
 905      \r
 906     \State $DE \gets \emptyset$ \Comment{The data entries for this slot} \label{resetMarker}\r
 907     \State $seq \gets $ \Call{GetNextSeq}{} \Comment{Get the sequence number for this slot}\r
 908 \r
 909      \r
 910     \State $resize \gets resize \lor $ \Call{ShouldResize}{ } \Comment{Check if we should resize}\r
 911     \If{$resize$}\r
 912         \State $newsize \gets$ \Call{CalcNewSize}{$max\_size$}\r
 913         \State $DE \gets DE \cup \{$\Call{CreateQState}{$newsize$}$\}$\r
 914     \EndIf\\\r
 915      \r
 916     \If{$RejectedSlotList \neq \emptyset$}   \r
 917         \State $DE \gets$ \Call{RejectedMessages}{$DE$}\r
 918     \EndIf\\\r
 919 \r
 920     \State $\tuple{needRezize,DE} \gets$ \Call{MandatoryRescue}{$DE$} \Comment{Round 1 of rescue}\r
 921     \If{$needRezize \land \lnot resize$}\r
 922         \LeftComment{Data was going to fall off the end so try again with a forced resize}\r
 923         \State $resize \gets $ true\r
 924         \State \Goto{resetMarker}\r
 925     \EndIf\\\r
 926     \r
 927     \If{$newkey_a \neq NULL \land $\Call{DEHasSpace}{$DE, newkey_a$}}\r
 928         \State $DE \gets DE \cup \{newkey_a\}$\r
 929     \EndIf\\\r
 930     \r
 931     \ForAll{$\tuple{commit, AbortSet, SentSet} \in ArbitrationRound$ in order of insertion}\r
 932         \ForAll{$abort \in (AbortSet \setminus SentSet)$}  \r
 933             \State $\tuple{seq_{clientlocal}, seq_{server}, id, arb, seq_{arb}} \gets abort$\r
 934             \State $abort \gets \tuple{seq_{clientlocal}, seq, id, arb, seq_{arb}}$ \Comment{Set sequence number}\r
 935             \r
 936             \If{\Call{DEHasSpace}{$De, abort$}}\r
 937                 \State $DE \gets DE \cup abort$\r
 938             \Else\r
 939                 \State \Goto{EndArb}\r
 940             \EndIf\r
 941         \EndFor\r
 942         \r
 943         \If{$commit \neq NULL$}\r
 944             \If{\Call{DEHasSpace}{$De, commit$}}\r
 945                 \State $DE \gets DE \cup commit$\r
 946             \Else\r
 947                 \State \Goto{EndArb}\r
 948             \EndIf\r
 949         \EndIf\r
 950     \EndFor \label{EndArb}\r
 951     \r
 952     \r
 953     \If{$|PendingTransactionQueue| > 0$}\r
 954         \State $\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb}, Sent, hadTimeout} \gets PendingTransactionQueue.peak()$\r
 955         \r
 956         \If{$(|Sent| = 0 \land \lnot hadTimeout) \lor (seq_s = -1)$}\r
 957             \State $seq_s \gets seq$\r
 958             \ForAll{$part \in P$}\r
 959                 \State $\tuple{Dat,arb,seq_{cl}, seq_{server}, id, partnum, isLast} \gets part$\r
 960                 \State $part \gets \tuple{Dat,arb,seq_{cl}, seq, id, partnum, isLast}$\r
 961             \EndFor\r
 962         \EndIf\r
 963         \r
 964         \ForAll{$part \in (P \setminus Sent)$}\r
 965             \If{\Call{DEHasSpace}{$De, part$}}\r
 966                 \State $DE \gets DE \cup part$\r
 967             \Else\r
 968                 \State \Goto{EndTrans}\r
 969             \EndIf\r
 970         \EndFor\r
 971     \EndIf \label{EndTrans}\r
 972     \r
 973 \r
 974     \LeftComment{Rescue data to fill slot data entry section}\r
 975     \State $DE \gets$ \Call{OptionalRescue}{$DE$}\\\r
 976     \State $newslot \gets $\Call{CreateNewSlot}{$seq, DE$}\r
 977     \State \Return{$\tuple{newslot,DE, newsize}$}    \r
 978 \EndFunction\r
 979 \end{algorithmic}\r
 980 % \end{algorithm}\r
 981 \r
 982 % %\end{varwidth}% \r
 983 % } \r
 984 \r
 985 \r
 986 \r
 987 \r
 988 \r
 989 \r
 990 \r
 991 \r
 992 % Send to Server\r
 993 %% \noindent\fbox{%\r
 994 %% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 995 % \begin{algorithm}\r
 996 \textbf{Send to Server:}\\\r
 997 Send local data to server if there is any local data that needs to be sent.\r
 998 \algblock[TryCatchFinally]{try}{endtry}\r
 999 \algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}\r
1000 \algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}\r
1001     [1]{\textbf{catch} #1}\r
1002     {\textbf{end try}}\r
1003 \r
1004 \begin{algorithmic}[1]\r
1005 \Function{SendToServer}{$slot_a, newsize_a$} throws $Server\_Connection\_Timeout$, $Server\_Response\_Timeout$\r
1006     \State $\tuple{seq_a, DE_A} \gets slot_a$\r
1007     \State $EDE_a \gets $ \Call{Encrypt}{$DE_A$}\r
1008     \State $slot_a \gets \tuple{seq_a, EDE_a}$\r
1009     \State $\tuple{success, NewSlots} \gets$ \Call{PutSlot}{$seq_a, newslot, newsize_a$}\\\r
1010     \r
1011     \If{$success$}\r
1012         \State $RejectedSlotList \gets \emptyset$\r
1013         \State \Return{$\tuple{true, \{newslot\}}$}\r
1014     \Else\r
1015         \If{$|newslots| = 0$}\r
1016             \State \Call{Error}{"Server rejected but did not send any slots"}\r
1017         \EndIf\\\r
1018         \r
1019         \State $NewSlots_{decrypt} \gets \emptyset$\r
1020         \ForAll{$\tuple{seq', EDat'} \in NewSlots$}\r
1021             \State $DDat \gets $ \Call{Decrypt}{$EDat'$}\r
1022             \State $NewSlots_{decrypt} \gets NewSlots_{decrypted} \cup \tuple{seq',DDat}$\r
1023         \EndFor\\\r
1024         \r
1025         \If{$hadPartialSendToServer$}\r
1026             \r
1027             \If{$\exists \tuple{seq_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in NewSlots_{decrypt}, id=LOCAL\_ID \land seq_2 = seq_a$}\r
1028                 \Return{$\tuple{true, NewSlots_{decrypted}}$}\r
1029             \EndIf\\\r
1030             \r
1031              \If{$\exists \tuple{seq_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in NewSlots_{decrypt}, \exists \tuple{seq', id'} \in DE, \tuple{seq', id'}$ is a $ \land id'=LOCAL\_ID \land seq'=seq_a$}\r
1032                 \Return{$\tuple{true, NewSlots_{decrypted}}$}\r
1033             \EndIf\r
1034         \EndIf\\\r
1035         \r
1036         \State $RejectedSlotList \gets RejectedSlotList \cup \{seq_a\}$\r
1037         \State \Return{$\tuple{false, NewSlots_{decrypted}}$}\r
1038     \EndIf\\\r
1039     \r
1040 \EndFunction\r
1041 \end{algorithmic}\r
1042 % \end{algorithm}\r
1043 % %\end{varwidth}% \r
1044 % }\r
1045 \r
1046 \r
1047 \r
1048 \r
1049 \r
1050 \r
1051 \r
1052 % Send to Server\r
1053 %% \noindent\fbox{%\r
1054 %% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1055 % \begin{algorithm}\r
1056 \textbf{Send to Server:}\\\r
1057 Send local data to server if there is any local data that needs to be sent.\r
1058 \algblock[TryCatchFinally]{try}{endtry}\r
1059 \algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}\r
1060 \algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}\r
1061     [1]{\textbf{catch} #1}\r
1062     {\textbf{end try}}\r
1063 \r
1064 \begin{algorithmic}[1]\r
1065 \Function{SendToServer}{$NewKey_a$}\r
1066     \State $SlotDE \gets \emptyset$\r
1067     \r
1068     \try\r
1069         \While{$|PendingTransactionQueue| > 0 \lor |SendArbQueue| > 0 \lor NewKey_a \neq NULL$}\r
1070             \State $\tuple{slot, SlotDE, newsize} \gets $ \Call{FillSlot}{$NewKey_a$}\r
1071             \State $\tuple{inserted, NewSlots} \gets $ \Call{SendToServer}{$slot, newsize$} \r
1072             \If{$inserted$} \r
1073                 \State $NewKey_a \gets NULL$\r
1074                 \r
1075                 \r
1076                 \ForAll{$\tuple{commit, AbortSet, SentSet} \in ArbitrationRound$}\r
1077                     \State $ArbitrationRound \gets ArbitrationRound \setminus \tuple{commit, AbortSet, SentSet}$\r
1078                     \State $SentSet \gets SentSet \cup \{e| e\in(\{commit\} \cup AbortSet) \land e \in SlotDE\}$\r
1079                     \r
1080                     \LeftComment{Add Back to the set if not done sending}\r
1081                     \If{$(commit=NULL \land |AbortSet| \neq |SentSet|) \land (commit \neq NULL \land (|AbortSet|+1) \neq |SentSet|)$}\r
1082                         \State $ArbitrationRound \gets ArbitrationRound \cup \tuple{commit, AbortSet, SentSet}$\r
1083                     \EndIf\r
1084                 \EndFor\r
1085 \r
1086             \r
1087                 \ForAll{$\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout} \in PendingTransactionQueue$ where $\exists p \in P, p \in SlotDE$}\r
1088                     \State $pos \gets PendingTransactionQueue.remove(\setminus \{\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout})$\r
1089                     \State $SentSet \gets SentSet \cup \{p|p \in P \land p \in SlotDE\}$\\\r
1090                     \r
1091                     \If{$|SentSet| > 0 \land id = LOCAL\_ID$}\r
1092                         \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
1093                         \State \Call{ChangeTransStatus}{$TransStatus,sentfully$}\r
1094                     \EndIf\\\r
1095                     \r
1096                     \If{$|P| \neq |SentSet|$}\r
1097                         \State $PendingTransactionQueue.insert(pos, \{\tuple{\tuple{P, KV, G,seq_l, -1,id, arb},SentSet,false})$\r
1098                     \ElsIf{$id = LOCAL\_ID$}\r
1099                         \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
1100                         \State \Call{ChangeTransStatus}{$TransStatus,sentfully$}\r
1101                         \State \Call{DeleteTransStatus}{$id,seq_l$}\r
1102                     \EndIf                    \r
1103                 \EndFor                \r
1104             \Else\r
1105                 \ForAll{$\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout} \in PendingTransactionQueue$ where $\exists p \in P, p \in SlotDE$}\r
1106             \If{$|Sent| = 0$}\r
1107                 \State $PendingTransactionQueue.replace(\{\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout},\tuple{\tuple{P, KV, G,seq_l, -1,id, arb},SentSet,hadTimeout})\}$\r
1108             \EndIf\r
1109         \EndFor\r
1110             \EndIf\r
1111             \r
1112             \r
1113             \State \Call{ValidateAndUpdate}{$NewSlots$}        \r
1114         \EndWhile\r
1115     \catch{$Server\_Connection\_Timeout$}        \r
1116         \ForAll{$\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout} \in PendingTransactionQueue$ where $\exists p \in P, p \in SlotDE$}\r
1117             \If{$|Sent| = 0$}\r
1118                 \State $PendingTransactionQueue.replace(\{\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout}, \tuple{\tuple{P, KV, G,seq_l, -1,id, arb},SentSet,hadTimeout})$\r
1119             \EndIf\r
1120         \EndFor\r
1121         \r
1122         \State \textbf{rethrowException}\\\r
1123         \r
1124     \catch{$Server\_Response\_Timeout$}\r
1125         \State $hadPartialSendToServer \gets True$\r
1126         \ForAll{$\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout} \in PendingTransactionQueue$ where $\exists p \in P, p \in SlotDE$}\r
1127             \State $PendingTransactionQueue.replace(\{\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout}, \tuple{\tuple{P, KV, G,seq_l, -1,id, arb},SentSet,True})$\r
1128         \EndFor\r
1129         \State \textbf{rethrowException}\r
1130     \endtry\r
1131     \r
1132     \State \Return{$NewKey_a = NULL$}\r
1133 \EndFunction\r
1134 \end{algorithmic}\r
1135 % \end{algorithm}\r
1136 \r
1137 % %\end{varwidth}% \r
1138 % }\r
1139 \r
1140 \r
1141 \r
1142 \r
1143 % Check Slot Hmacs\r
1144 %\noindent\fbox{%\r
1145 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1146 \textbf{Check Slot HMACs:}\\\r
1147 Check that each slot has not been tampered with by checking that the stored HMAC matches the calculated HMAC.  Also check thatthe slot number reported by the server matches the slot number of the actual slot.\r
1148 \begin{algorithmic}[1]\r
1149 \Function{CheckSlotsHmacAndSeq}{$Slots_a$}\r
1150     \ForAll{$slot_a \in Slots_a$}\r
1151         \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets slot_a$\r
1152         \State $calchmac \gets $ \Call{GenerateHmac}{$seq_{a_2}, id_a, DE_a, hmac_{a_p}$}\r
1153     \r
1154         \If{$seq_{a_1} \neq seq_{a_2}$}\r
1155           \State \Call{Error}{"Slot sequence number mismatch"}\r
1156         \ElsIf{$calchmac \neq hmac_{a_c}$}\r
1157             \State \Call{Error}{"Slot HMAC mismatch"}\r
1158         \EndIf\r
1159     \EndFor\r
1160 \EndFunction\r
1161 \end{algorithmic}\r
1162 %\end{varwidth}% \r
1163 %}\r
1164 \r
1165 % Check HMAC Chain\r
1166 %\noindent\fbox{%\r
1167 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1168 \textbf{Check HMAC Chain:}\\\r
1169 Check that the HMAC chain has not been violated.\r
1170 \begin{algorithmic}[1]\r
1171 \Function{CheckHmacChain}{$Slots_a$}\r
1172     \State $SlotsList \gets Slots_a$ sorted by sequence number\\  \r
1173     \r
1174     \LeftComment{Check all new slots}\r
1175     \ForAll{$index \in [2: |SlotsList|]$}\r
1176         \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets SlotList[i-1]$\r
1177         \State $\tuple{seq_{b_1}, \tuple{seq_{b_2},id_b,DE_b,hmac_{b_p},hmac_{b_c}}} \gets SlotList[i]$\r
1178         \r
1179         \If{$hmac_{b_p} \neq hmac_{b_c}$}\r
1180             \State \Call{Error}{"Invalid previous HMAC."}\r
1181         \EndIf    \r
1182     \EndFor\\\r
1183     \r
1184     \LeftComment{Check against slots that we already have in the block chain}\r
1185     \If{$|LocalSlots| \neq 0$}\r
1186         \State $\tuple{seq, SDE} \gets $\Call{MaxSlot}{$LocalSlots$}\r
1187         \State $\tuple{seq{last_2},id_{last},DE_{last},hmac_{last_p},hmac_{last_c}} \gets SDE$\r
1188         \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets SlotList[1]$\\\r
1189 \r
1190         \If{$(seq_{last_2} + 1) = seq_{a_1} \land hmac_{a_p} \neq hmac_{last_c}$}    \r
1191             \State \Call{Error}{"Invalid previous HMAC."}\r
1192         \EndIf\r
1193     \EndIf\r
1194     \r
1195 \EndFunction\r
1196 \end{algorithmic}\r
1197 %\end{varwidth}% \r
1198 %}\r
1199 \r
1200 % Check For Old Slots\r
1201 %\noindent\fbox{%\r
1202 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1203 \textbf{Check For Old Slots:}\\\r
1204 Check if the slots are not new.  Checks if the "new" slots are actually new or if they are older than the most recent slot that we have.\r
1205 \begin{algorithmic}[1]\r
1206 \Function{CheckOldSlots}{$Slots_a$}\r
1207     \State $\tuple{seq_{new}, Dat_{new}} \gets$ \Call{MinSlot }{$Slots_a$} \Comment{Get the oldest new slot}\r
1208     \State $\tuple{seq_{local}, Dat_{local}} \gets$ \Call{MaxSlot }{$LocalSlots$} \Comment{Get the newest slot seen}\\\r
1209     \r
1210     \If{$seq_{new} \leq seq_{local}$} \Comment{The slots were not newer than what was already seen}\r
1211         \State \Call{Error}{"Server sent old slots."}\r
1212     \EndIf\r
1213 \EndFunction\r
1214 \end{algorithmic}\r
1215 %\end{varwidth}% \r
1216 %}\r
1217 \r
1218 % Check Size With Gap\r
1219 %\noindent\fbox{%\r
1220 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1221 \textbf{Check Size With Gap:}\\\r
1222 Checks that the block chain size is correct when there is a gap in the block chain.  This check makes sure that the server is not hiding any information from the client.  If there is a gap and there is only 1 queue state in the new slot entries then there must have at least that many slots since the old slot entry must have been purged.  If there is more than 1 queue state then the block chain is still growing check the smallest max size and there should be at least that many slots. \r
1223 \begin{algorithmic}[1]\r
1224 \Function{CheckSizeWithGap}{$Slots_a$}    \r
1225     %\State $QSSet \gets $ \Call{GetQStateWithSeq}{$Slots_a$}\r
1226     %\State $\tuple{seq_{max}, size_{max}} \gets \tuple{seq, size}$ such that $\tuple{seq, size} \in QSSet \land \forall \tuple{seq', size'} \in QSSet, size \geq size'$ \Comment{Get largest size}\r
1227     %\State $\tuple{seq_{min}, size_{min}} \gets \tuple{seq, size}$ such that $\tuple{seq, size} \in QSSet \land \forall \tuple{seq', size'} \in QSSet , size \leq size'$ \Comment{Get smallest size}\r
1228     \r
1229     \State $QSet \gets $ \Call{GetQState}{$Slots_a$}\r
1230     \State $size_{max} \gets size$ such that $size \in QSet \land \forall size' \in QSet, size \geq size'$ \r
1231     \State $size_{min} \gets size$ such that $size \in QSet \land \forall size' \in QSet, size \leq size'$     \r
1232     \State $Slots_{oldmax} \gets \emptyset$\\\r
1233 \r
1234     \r
1235     \LeftComment{If only 1 max size then we must have all the slots for that size}\r
1236     \If{$(|QSSet| = 1) \land (|Slots_a| \neq size_{max})$}\r
1237         \State \Call{Error}{"Missing Slots"}\r
1238     \EndIf\\\r
1239     \r
1240     \LeftComment{We definitely have all the slots}\r
1241     \If$|Slots_a| = size_{max}$\r
1242         \State \Return{} \Comment{We have all the slots}\r
1243     \EndIf\\\r
1244     \r
1245     \LeftComment{We must have at least this many slots}\r
1246     \If$|Slots_a| < size_{min}$\r
1247         \State \Call{Error}{"Missing Slots"}\r
1248     \EndIf\\\r
1249 \r
1250 \EndFunction\r
1251 \end{algorithmic}\r
1252 %\end{varwidth}% \r
1253 %}\r
1254 \r
1255 % Check Size\r
1256 %\noindent\fbox{%\r
1257 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1258 \textbf{Check Size:}\\\r
1259 \begin{algorithmic}[1]\r
1260 \Function{CheckSize}{$Slots_a$}    \r
1261     \State $\tuple{seq_{old_{max}}, Dat_{old_{max}}} \gets $ \Call{MaxSlot}{$LocalSlots$}\r
1262     \State $\tuple{seq_{new_{max}}, Dat_{new_{max}}} \gets $ \Call{MinSlot}{$Slots_a$}\\\r
1263     \r
1264     \If{$(seq_{old_{max}} + 1) = seq_{new_{max}}$}\r
1265         \LeftComment{No Gap so cannot say anything about the size}\r
1266         \State \Return{} \r
1267     \Else \r
1268         \LeftComment{Has a gap so we need to do checks}\r
1269         \State \Call{CheckSizeWithGap}{$Slots_a$}\r
1270     \EndIf\r
1271 \EndFunction\r
1272 \end{algorithmic}\r
1273 %\end{varwidth}% \r
1274 %}\r
1275 \r
1276 % Process New Key Data Entry\r
1277 %\noindent\fbox{%\r
1278 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1279 \textbf{Process New Key Entry:}\\\r
1280 Process a queue state entry. Adds a key to the key arbitrator set.\r
1281 \begin{algorithmic}[1]\r
1282 \Function{ProcessNewkey}{$newkey_a$}\r
1283     \State $Arbitrator \gets Arbitrator \cup \{newkey_a\}$\r
1284 \EndFunction\r
1285 \end{algorithmic}\r
1286 %\end{varwidth}% \r
1287 %}\r
1288 \r
1289 % Process Collision Resolution Entry\r
1290 %\noindent\fbox{%\r
1291 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1292 \textbf{Process Queue State Entry:}\\\r
1293 Process a collision resolution entry.\r
1294 \begin{algorithmic}[1]\r
1295 \Function{ProcessColres}{$colres_a, NewSlots_a$}\r
1296     \State $\tuple{id_a, seq_{a_{old}}, seq_{a_{new}}, isequal_a}$\r
1297     \State $AllSlots \gets LocalSlots \cup NewSlots_a$\r
1298     \State $index \gets seq_{a_{old}}$\\\r
1299     \r
1300     \While{$index <= seq_{a_{new}}$}\r
1301         \State $slt \gets \tuple{seq' Dat'}$ such that $\tuple{seq' Dat'} \in AllSlots \land seq'=index$\r
1302         \r
1303         \If{$\exists \tuple{seq' Dat'} \in AllSlots, seq' = index$}\r
1304             \State $\tuple{seq, Dat} \gets \tuple{seq' Dat'}$ such that $\tuple{seq' Dat'} \in AllSlots \land seq'=index$\r
1305             \State $\tuple{seq,id,DE,hmac_p,hmac_c} \gets Dat$\r
1306             \If{$isequal_a \neq (id=id_a)$}\r
1307                 \State \Call{Error}{"Trying to insert rejected messages for slot"}\r
1308             \EndIf\r
1309         \EndIf\\\r
1310         \State $index \gets index + 1$\r
1311     \EndWhile\r
1312     \r
1313     \r
1314 \EndFunction\r
1315 \end{algorithmic}\r
1316 %\end{varwidth}% \r
1317 %}\r
1318 \r
1319 % Process Queue State Data Entry\r
1320 %\noindent\fbox{%\r
1321 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1322 \textbf{Process Queue State Entry:}\\\r
1323 Process a queue state entry. Updates the max size of the block chain.\r
1324 \begin{algorithmic}[1]\r
1325 \Function{ProcessQState}{$qstate_a$}\r
1326     \State $\tuple{size_a} \gets qstate_a$\r
1327     \State $max\_size \gets size_a$ \Comment{Update the max size we can have}\r
1328 \EndFunction\r
1329 \end{algorithmic}\r
1330 %\end{varwidth}% \r
1331 %}\r
1332 \r
1333 % Process Transaction Part Entry\r
1334 %\noindent\fbox{%\r
1335 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1336 \textbf{Process Transaction Part Entry:}\\\r
1337 Process a new Transaction Part Entry.\r
1338 \begin{algorithmic}[1]\r
1339 \Function{ProcessTransPart}{$TransactionPart_a$}\r
1340     \State $\tuple{Dat,arb,seq_{clientLocal}, seq_{server}, id, partnum, isLast} \gets TransactionPart_a$\r
1341     \State $Transaction \gets NULL$\\\r
1342     \r
1343     \If{$\exists \tuple{id',seq'} \in LastTransactionArbitrated \land id'=arb land seq' \geq seq_{server}$}\r
1344         \State \Return{}\r
1345     \EndIf\\\r
1346     \r
1347     \If{$\exists \tuple{Parts', KV', G',seq_{clientlocal}', seq_{server}',id', arb'} \in LiveTransactions, seq_{server}' = seq_{server}$}\r
1348         \State $Transaction \gets \tuple{Parts', KV', G',seq_{clientlocal}', seq_{server}',id', arb'} \in LiveTransactions$such that$ seq_{server}' = seq_{server}$\r
1349         \State $LiveTransactions \gets LiveTransactions \setminus \{Transaction\}$\r
1350     \Else\r
1351         \State $Transaction \gets \tuple{\emptyset, \emptyset, \emptyset, seq_{clientlocal}, seq_{server},id, arb}$\r
1352     \EndIf\\\r
1353     \r
1354     \State $\tuple{Parts, KV, G,seq_{local}, seq_{server},id, arb} \gets Transaction$\r
1355     \State $Parts \gets Parts \cup TransactionPart_a$\\\r
1356     \r
1357     \If{$\exists \tuple{Dat,arb,seq_{clientLocal}, seq_{server}, id, partnum, isLast} \in Parts \land isLast \land |Parts| = partnum$}\r
1358         \State $\tuple{KV, G} \gets $\Call{DecodeParts}{$Parts$}\r
1359     \EndIf\r
1360     \r
1361     \State $Transactin \gets \tuple{Parts, KV, G,seq_{local}, seq_{server},id,arb}$.\r
1362     \State $LiveTransactions \gets LiveTransactions \cup \{Transaction\}$\r
1363 \EndFunction\r
1364 \end{algorithmic}\r
1365 %\end{varwidth}% \r
1366 %}\r
1367 \r
1368 % Process Abort Entry\r
1369 %\noindent\fbox{%\r
1370 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1371 \textbf{Process Abort Entry:}\\\r
1372 Process a new Abort Entry.\r
1373 \begin{algorithmic}[1]\r
1374 \Function{ProcessAbort}{$abort_a$}\r
1375     \State $\tuple{seq_{cl}, seq_{s}, id, arb, seq_{arb}} \gets abort_a$\r
1376     \r
1377     \If{$\lnot(\exists \tuple{id',seq'} \in LastArbLocalArbitrated, id'=id \land seq' > seq_{arb})$}\r
1378         \State $LastArbLocalArbitrated\gets \tuple{\tuple{id',seq'}|\tuple{id',seq'}  \in LastArbLocalArbitrated, id' \neq id} \cup \{\tuple{id, }\}$\r
1379     \EndIf\r
1380     \r
1381     \If{$\lnot(\exists \tuple{id',seq'} \in LastTransactionArbitrated, id'=id \land seq' > seq_{s})$}\r
1382         \State $LastTransactionArbitrated \gets \tuple{\tuple{id',seq'}|\tuple{id',seq'}  \in LastTransactionArbitrated, id' \neq id} \cup \{\tuple{id, seq_{s}}\}$\r
1383     \EndIf    \r
1384     \r
1385     \If{$id = LOCAL\_ID$}\r
1386         \State $TransStatus \gets $ \Call{GetTransStatus}{$id, seq_{cl}$}\r
1387         \State \Call{ChangeTransStatus}{$TransStatus,abort$}\r
1388         \State \Call{DeleteTransStatus}{$id, seq_{cl}$}\r
1389     \EndIf\r
1390 \EndFunction\r
1391 \end{algorithmic}\r
1392 %\end{varwidth}% \r
1393 %}\r
1394 \r
1395 % Process Commit Part Entry\r
1396 %\noindent\fbox{%\r
1397 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1398 \textbf{Process Commit Part Entry:}\\\r
1399 Process a new Commit Part Entry.\r
1400 \begin{algorithmic}[1]\r
1401 \Function{ProcessCommitPart}{$CommitPart_a$}\r
1402     \State $\tuple{Dat,seq_t, seq_s, id, partnum, isLast} \gets CommitPart_a$\r
1403     \State $Commit \gets NULL$\\\r
1404     \r
1405     \If{$\exists \tuple{P', KV', seq_t', seq_s',id'} \in LiveCommits, seq_s' = seq_s$}\r
1406         \State $Commit \gets \tuple{P', KV', seq_t', seq_s',id} \in LiveCommits$ such that$ seq_{s}' = seq_{s}$\r
1407         \State $LiveCommits \gets LiveCommits \setminus \{Commit\}$\r
1408     \Else\r
1409         \State $Commit \gets \tuple{\emptyset, \emptyset, seq_t, seq_s,id}$\r
1410     \EndIf\\\r
1411     \r
1412     \State $\tuple{P, KV, seq_t, seq_s,id} \gets Commit$\r
1413     \State $P \gets P \cup CommitPart_a$\\\r
1414     \r
1415     \If{$\exists \tuple{Dat',seq_t', seq_s', id', partnum', isLast'} \in P \land isLast' \land |P| = partnum$}\r
1416         \State $KV \gets $\Call{DecodeParts}{$P$}\r
1417     \EndIf\\\r
1418     \r
1419     \State $Commit \gets \tuple{P, KV, seq_t, seq_s,id}$\r
1420     \State $LiveCommits \gets LiveCommits \cup \{Commit\}$\r
1421 \EndFunction\r
1422 \end{algorithmic}\r
1423 %\end{varwidth}% \r
1424 %}\r
1425 \r
1426 % Update Last Message\r
1427 %\noindent\fbox{%\r
1428 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1429 \textbf{Process Commit Data Entry:}\\\r
1430 Process a commit entry.  Updates the local copy of commits.\r
1431 \begin{algorithmic}[1]\r
1432 \Function{UpdateLastMessage}{$seq_a, id_a, updateinglocal_a, MachinesSeen$}\r
1433     \State $\tuple{id_{old}, seq_{old}} \gets \tuple{id', seq'}$ such that $\tuple{id', seq'} \in LastSlot \land id'=id$\\\r
1434     \r
1435     \If{$id_a = LOCAL\_ID$}\r
1436         \If{$hadPartialSendToServer$}\r
1437             \If{$\lnot updateinglocal_a \land (seq_a < seq_{old})$}\r
1438                 \LeftComment{This client did not make any updates so its latest sequence number should not change}\r
1439                 \State \Call{Error}{"Mismatch on local machine sequence number"}\r
1440             \EndIf\r
1441         \Else\r
1442             \If{$\lnot updateinglocal_a \land (seq_a \neq seq_{old})$}\r
1443                 \LeftComment{This client did not make any updates so its latest sequence number should not change}\r
1444                 \State \Call{Error}{"Mismatch on local machine sequence number"}\r
1445             \EndIf\r
1446         \EndIf\r
1447     \Else\r
1448         \If{$seq_{old} > seq_a$}\r
1449             \State \Call{Error}{"Rollback on remote machine sequence number"}\r
1450         \EndIf\r
1451     \EndIf\\\r
1452     \r
1453     \State $LastSlot \gets LastSlot \setminus \{\tuple{id, seq} | \tuple{id, seq} \in LastSlot, id=id_a\}$\r
1454     \State $LastSlot \gets LastSlot \cup \{\tuple{id_a, seq_a}\}$\r
1455     \State $MachinesSeen \gets MachinesSeen \setminus \{id_a\}$\r
1456 \EndFunction\r
1457 \end{algorithmic}\r
1458 %\end{varwidth}% \r
1459 %}\r
1460 \r
1461 % Process Process Data Entry\r
1462 %\noindent\fbox{%\r
1463 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1464 \textbf{Process Data Entry:}\\\r
1465 Process the data entry based on what kind of entry it is.\r
1466 \begin{algorithmic}[1]\r
1467 \Function{ProcessDatEntry}{$slot_a, NewSlots_a,MachinesSeen$}\r
1468     \If{$datentry_a$ is a $compart$}\r
1469         \State \Call{ProcessCommitPart}{$dataentry_a$}\r
1470         \r
1471     \ElsIf{$datentry_a$ is a $abort$}\r
1472         \LeftComment{Do Nothing in this case}\r
1473         \r
1474     \ElsIf{$datentry_a$ is a $transpart$}\r
1475         \State \Call{ProcessTransPart}{$dataentry_a$}\r
1476     \r
1477     \ElsIf{$datentry_a$ is a $lastmsg$}\r
1478         \State $\tuple{seq_a, id_a} \gets dataentry_a$\r
1479         \State \Call{UpdateLastMessage}{$seq_a, id_a, false, MachinesSeen$}\r
1480     \r
1481     \ElsIf{$datentry_a$ is a $colres$}\r
1482         \State \Call{ProcessColres}{$dataentry_a, NewSlots_a$}\r
1483         \r
1484     \ElsIf{$datentry_a$ is a $qstate$}\r
1485         \State \Call{ProcessQState}{$dataentry_a$}\r
1486         \r
1487     \ElsIf{$datentry_a$ is a $newkey$}\r
1488         \State \Call{ProcessNewkey}{$dataentry_a$}\r
1489     \Else\r
1490         \State \Call{Error}{"Unknown data entry type."}\r
1491     \EndIf\r
1492     \r
1493     \State \Return{$LstSlt_a$}    \r
1494 \EndFunction\r
1495 \end{algorithmic}\r
1496 %\end{varwidth}% \r
1497 %}\r
1498 \r
1499 % Update Committed Table\r
1500 %\noindent\fbox{%\r
1501 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1502 \textbf{Update Committed Key value Table:}\\\r
1503 Update the table of committed Key Value Pairs based on commits that we received.\r
1504 \begin{algorithmic}[1]\r
1505 \Function{UpdateCommitTable}{$ $}   \r
1506     \r
1507     \State $ArbSet \gets \{id'| \tuple{P, KV, seq_t, seq_s,id'} \in LiveCommits\}$\r
1508     \r
1509     \ForAll{$id \in ArbSet$}\r
1510         \State $Commits \gets \{\tuple{P, KV, seq_t, seq_s,id'}| \tuple{P, KV, seq_t, seq_s,id'} \in LiveCommits \land id' = id\}$\r
1511         \r
1512         \State $lastComSeenSeq \gets -1$\r
1513         \If{$\exists \tuple{id',seq'} \in LastCommitSeenFromArbitrator, id'=id$}\r
1514             \State $lastComSeenSeq  \gets seq$ such that $\tuple{id',seq'} \in LastCommitSeenFromArbitrator, id'=id$\r
1515         \EndIf\\\r
1516         \r
1517         \ForAll{$\tuple{P, KV, seq_t, seq_s,id} \in Commits$ sorted by $seq_s$ where $seq_s > lastComSeenSeq$}\r
1518 \r
1519             \If{$(\forall \tuple{D',seq_t', seq_s', id', pn', isLast'} \in P, \lnot isLast')\lor(\exists \tuple{D',seq_t', seq_s', id', pn', isLast'} \in P,isLast') \land |P| \neq pn)$}\r
1520                 \If{$\forall \tuple{P', KV', seq_t', seq_s',id'} \in Commits, seq_s' < seq_s$}\r
1521                     \State Break \Comment{This is the last slot so ignore it}\r
1522                 \Else\r
1523                     \State Continue\r
1524                 \EndIf\r
1525             \EndIf\\\r
1526             \r
1527             \If{$\lnot(\exists \tuple{id',seq'} \in LastArbLocalArbitrated, id'=id \land seq' > seq_s)$}\r
1528                 \State $LastArbLocalArbitrated\gets \tuple{\tuple{id',seq'}|\tuple{id',seq'}  \in LastArbLocalArbitrated, id' \neq id} \cup \{\tuple{id, seq_s}\}$\r
1529             \EndIf\r
1530             \r
1531             \State $LastCommitSeenFromArbitrator \gets \{ \tuple{id',seq'}| \tuple{id',seq'} \in LastCommitSeenFromArbitrator,id' \neq id\} \cup \{\tuple{id, seq_s}\}$\r
1532 \r
1533              \If{$\lnot(\exists \tuple{id',seq'} \in LastTransactionArbitrated, id'=id \land seq' > seq_{t})$}\r
1534                 \State $LastTransactionArbitrated \gets \tuple{\tuple{id',seq'}|\tuple{id',seq'}  \in LastTransactionArbitrated, id' \neq id} \cup \{\tuple{id, seq_{t}}\}$\r
1535             \EndIf    \r
1536             \r
1537             \LeftComment{Update Committed Table}\r
1538             \State $CommittedKV \gets \{\tuple{k,v}| \tuple{k,v} \in CommittedKV \land \forall \tuple{k',v'} \in KV, k\neq k' \} \cup KV$              \r
1539             \State $LiveCommits \gets LiveCommits \cup \tuple{P, KV, seq_t, seq_s,id}$\\\r
1540         \r
1541             \ForAll{$\tuple{P, KV, seq_t, seq_s,id} \in LiveCommits$}\r
1542                 \LeftComment{All Key Values in this commit have been overridden by a newer commit}    \r
1543                 \If{$\forall \tuple{k,v} \in KV, \exists \tuple{P', KV', seq_t', seq_s',id'} \in LiveCommits, \exists \tuple{k',v'} \in KV', k'=k \land seq_s' > seq_s$}\r
1544                     \State $LiveCommits \gets LiveCommits \setminus \{\tuple{P, KV, seq_t, seq_s,id}\}$\r
1545                 \EndIf\r
1546             \EndFor            \r
1547         \EndFor\r
1548     \EndFor\r
1549 \EndFunction\r
1550 \end{algorithmic}\r
1551 %\end{varwidth}% \r
1552 %}\r
1553 \r
1554 % Update Speculative Table\r
1555 %\noindent\fbox{%\r
1556 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1557 \textbf{Update Speculated Key value Table:}\\\r
1558 Update the table of speculative Key Value Pairs based on commits that we received.\r
1559 \begin{algorithmic}[1]\r
1560 \Function{UpdateSpeculativeKV}{$ $}\r
1561     \State $SpecKV \gets CommittedKV$\\\r
1562     \r
1563     \ForAll{$\tuple{P, KV, G,seq_{cl}, seq_s,id, arb} \in LiveTransactions$ sorted by $seq_s$}\r
1564          \If{$\forall \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P, \lnot isLast'$}\r
1565             \State Continue\r
1566         \ElsIf{$(\exists \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P,isLast') \land |P| \neq pn$}\r
1567             \State Continue\r
1568         \EndIf\\\r
1569         \r
1570         \If{\Call{EvaluateGuard}{$G, SpecKV$}}\r
1571             \State $SpecKV\gets \{\tuple{k',v'}| \tuple{k',v'} \in SpecKV \land \forall \tuple{k,v} \in KV, k' \neq k\}\cup KV$\r
1572         \EndIf\r
1573     \EndFor\\\r
1574     \r
1575     \ForAll{$\tuple{KV, G, id, seq} \in PendingTransactionQueue$ sorted by $seq$}\r
1576         \If{\Call{EvaluateGuard}{$G, SpecKV$}}\r
1577             \State $SpecKV\gets \{\tuple{k',v'}| \tuple{k',v'} \in SpecKV \land \forall \tuple{k,v} \in KV, k' \neq k\}\cup KV$\r
1578         \EndIf\r
1579     \EndFor\\\r
1580     \r
1581     \State $SpeculatedKV \gets SpecKV$\r
1582 \EndFunction\r
1583 \end{algorithmic}\r
1584 %\end{varwidth}% \r
1585 %}\r
1586 \r
1587 % Compact Arbitration Rounds\r
1588 %\noindent\fbox{%\r
1589 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1590 \textbf{Compact Arbitration Rounds:}\\\r
1591 Compact Arbitration Rounds to reduce the amount of data needed to be sent to the server.\r
1592 \begin{algorithmic}[1]\r
1593 \Function{CompactArbitrationRounds}{$ $}\r
1594     \If{$|SendArbQueue| < 2$}\r
1595         \State \Return{False}\r
1596     \EndIf\\\r
1597     \r
1598     \State $didMergeWithCommit \gets False$\r
1599     \r
1600     \While{$|SendArbQueue| > 1$}\r
1601         \State $\tuple{c_1, A_1, S_1} \gets SendArbQueue.peak(|SendArbQueue|)$\r
1602         \State $\tuple{c_2, A_2, S_2} \gets SendArbQueue.peakEnd(|SendArbQueue| - 1)$\\\r
1603         \r
1604         \If{$|S_1| \neq 0 \lor |S_2| \neq 0$}\r
1605             \State \Return{$didMergeWithCommit$}\r
1606         \EndIf\\\r
1607         \r
1608         \If{$c_2 = NULL$}\r
1609             \If{$|A_1| + |A_2| > MAX\_ROUND\_SIZE$}\r
1610                 \State \Return{$didMergeWithCommit$}\r
1611             \EndIf            \r
1612             \State $SendArbQueue.remove(|SendArbQueue|)$\r
1613             \State $SendArbQueue.remove(|SendArbQueue|)$\r
1614             \State $SendArbQueue \gets SendArbQueue \cup \tuple{c_1, A_1 \cup A_2, \emptyset}$\r
1615         \Else\r
1616             \State $\tuple{P_1, KV_1, seq_{1_t}, seq_{1_s},id_1} \gets c_1$\r
1617             \State $\tuple{P_2, KV_2, seq_{2_t}, seq_{2_s},id_2} \gets c_2$\r
1618             \State $newKV \gets \{\tuple{k_2,v_2}| \tuple{k_2,v_2} \in KV_2 \land \forall \tuple{k_1,v_1} \in KV_1 \land k_1 \neq k_2\} \cup KV_1$\r
1619             \State $NewCom \gets \tuple{P_1, newKV, seq_{1_t}, seq_{1_s},id_1}$\r
1620             \State \Call{GenerateParts}{$NewCom$}\r
1621             \State $\tuple{P_1, newKV, seq_{1_t}, seq_{1_s},id_1} \gets NewCom$\\\r
1622             \r
1623             \If{$|P_1| > MAX\_ROUND\_SIZE$}\r
1624                 \State \Return{$didMergeWithCommit$}\r
1625             \EndIf\\\r
1626             \r
1627             \State $SendArbQueue.remove(|SendArbQueue|)$\r
1628             \State $SendArbQueue.remove(|SendArbQueue|)$\r
1629             \State $SendArbQueue \gets SendArbQueue \cup \tuple{newCom, A_1 \cup A_2, \emptyset}$\r
1630             \State $didMergeWithCommit \gets True$\r
1631         \EndIf\r
1632     \EndWhile  \r
1633     \r
1634     \State \Return{$didMergeWithCommit$}\r
1635     \r
1636 \EndFunction\r
1637 \end{algorithmic}\r
1638 %\end{varwidth}% \r
1639 %}\r
1640 \r
1641 % Arbitrate From Server\r
1642 %\noindent\fbox{%\r
1643 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1644 \textbf{Arbitrate Form Server:}\\\r
1645 Arbitrate on the transactions that were received from the server\r
1646 \begin{algorithmic}[1]\r
1647 \Function{ArbitrateFromServer}{$ $}\r
1648     \r
1649     \State $KVCom \gets \emptyset$\r
1650     \State $KVTmp \gets CommittedKV$\r
1651     \State $lastTransCommitted = 0$\r
1652     \State $AbortSet \gets \emptyset$\r
1653     \State $NewCom \gets NULL$\r
1654     \r
1655     \State $TransArb \gets \{\tuple{P, KV, G,seq_{l}, seq_{s},id,arb}|\tuple{p, KV, G,seq_{l}, seq_{s},id,arb} \in LiveTransactions \land arb = LOCAL\_ID\}$\\\r
1656     \r
1657     \ForAll{$\tuple{P, KV, G,seq_{cl}, seq_{s},id,arb} \in Transarb$ sorted by $seq_{s}$}\r
1658         \r
1659         \If{$\forall \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P, \lnot isLast'$}\r
1660             \State Break\r
1661         \ElsIf{$(\exists \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P,isLast') \land |P| \neq pn$}\r
1662             \State Break\r
1663         \ElsIf{$\exists \tuple{id', seq_{l}'} \in OfflineTransAtServer, id' = id\land seq_{cl}' = seq_{cl} $}\r
1664             \State Break\r
1665         \EndIf\\\r
1666         \r
1667         \State $LastTransSeenMid \gets \{\tuple{id',seq'}|\tuple{id',seq'} \in LastTransSeenMid \land id'\neq id\} \cup \{\tuple{id, seq_s}\}$\\\r
1668         \r
1669         \r
1670         \If{\Call{EvaluateGuard}{$G, KVTmp$}}\r
1671             \State $KVTmp \gets \{\tuple{k',v'} |\tuple{k',v'} \in KVTmp \land \forall \tuple{k,v} \in KV, k' \neq k\}\cup KV$\r
1672             \State $KVCom \gets \{\tuple{k',v'} |\tuple{k',v'} \in KVCom \land \forall \tuple{k,v} \in KV, k' \neq k\}\cup KV$\r
1673             \State $lastTransCommitted \gets seq_{s}$ \r
1674         \Else\r
1675             \State $newAbort \gets \tuple{seq_{cl}, seq_{s}, id, arb, arbitrationSeqNum}$\r
1676             \State $AbortSet \gets AbortSet \cup newAbort$\r
1677             \State $arbitrationSeqNum \gets arbitrationSeqNum + 1$\r
1678             \State \Call{ProcessAbort}{$newAbort$}\r
1679         \EndIf\r
1680     \EndFor\r
1681     \r
1682     \If{$|KVCom| \neq 0$}\r
1683         \State $NewCom \gets \tuple{\emptyset, KVCom, lastTransCommitted, arbitrationSeqNum,id}$\r
1684         \State \Call{GenerateParts}{$NewCom$}\r
1685         \State $arbitrationSeqNum \gets arbitrationSeqNum + 1$\r
1686         \ForAll{$compart \in NewCom$}\r
1687                 \State \Call{ProcessCommitPart}{compart}\r
1688         \EndFor\r
1689     \EndIf\r
1690     \r
1691     \If{$|KVCom| \neq 0 \lor |AbortSet| \neq 0$}\r
1692         \State $ArbitrationQueue \gets ArbitrationQueue \cup \tuple{NewCom, AbortSet, \emptyset}$\r
1693         \r
1694         \If{\Call{CompactArbitrationRounds}{$ $}}\r
1695             \State $\tuple{NewCom, AbortSet, \emptyset} \gets ArbitrationQueue.peakEnd()$\r
1696             \ForAll{$compart \in NewCom$}\r
1697                 \State \Call{ProcessCommitPart}{compart}\r
1698             \EndFor\r
1699         \EndIf\r
1700     \EndIf    \r
1701 \EndFunction\r
1702 \end{algorithmic}\r
1703 %\end{varwidth}% \r
1704 %}\r
1705 \r
1706 \r
1707 \r
1708 % Arbitrate From Local\r
1709 %\noindent\fbox{%\r
1710 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1711 \textbf{Arbitrate from local:}\\\r
1712 Arbitrate on the transactions that were received from the local.\r
1713 \begin{algorithmic}[1]\r
1714 \Function{ArbitrateFromLocal}{$Transaction_a$}\r
1715     \State $\tuple{Parts, KV, G,seq_l, seq_s,id, arb} \gets Transaction_a$\\\r
1716     \r
1717     \If{$id \neq LOCAL\_ID$} \Comment{If is arbitrator}\r
1718         \State \Return{$\tuple{False, False}$}\r
1719     \EndIf\\\r
1720     \r
1721     \LeftComment{transaction is complete}\r
1722     \If{$\forall \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P, \lnot isLast'$}\r
1723         \State \Return{$\tuple{False, False}$}\r
1724     \ElsIf{$(\exists \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P,isLast') \land |P| \neq pn$}\r
1725         \State \Return{$\tuple{False, False}$}\r
1726     \EndIf\\\r
1727     \r
1728     \If{$id \neq LOCAL\_ID$}\r
1729         \If{$\exists \tuple{id',seq'} \in LastTransSeenMid, id'=id \land seq' > seq_l$}\r
1730             \State \Return{$\tuple{False, False}$} \Comment{Already seen this transaction}\r
1731         \EndIf\r
1732     \EndIf\\\r
1733     \r
1734     \If{\Call{EvaluateGuard}{$G, CommittedKV$}}        \r
1735         \State $NewCom \gets \tuple{\emptyset, KV, seq_s, arbitrationSeqNum,id}$\r
1736         \State \Call{GenerateParts}{$NewCom$}\r
1737         \State $arbitrationSeqNum \gets arbitrationSeqNum + 1$\r
1738         \ForAll{$compart \in NewCom$}\r
1739                 \State \Call{ProcessCommitPart}{compart}\r
1740         \EndFor\\\r
1741         \r
1742         \State $ArbitrationQueue \gets ArbitrationQueue \cup \tuple{NewCom, \emptyset, \emptyset}$\r
1743         \If{\Call{CompactArbitrationRounds}{$ $}}\r
1744             \State $\tuple{NewCom, AbortSet, \emptyset} \gets ArbitrationQueue.peakEnd()$\r
1745             \ForAll{$compart \in NewCom$}\r
1746                 \State \Call{ProcessCommitPart}{compart}\r
1747             \EndFor\r
1748         \EndIf\r
1749         \r
1750         \r
1751          \If{$id = LOCAL\_ID$}\r
1752                 \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
1753                 \State \Call{ChangeTransStatus}{$TransStatus,committed$}\r
1754                 \State \Call{DeleteTransStatus}{$id,seq_l$}\r
1755         \EndIf\r
1756         \r
1757         \State \Call{UpdateCommittedKV}{}\r
1758         \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
1759         \State \Call{UpdateSpeculativeKV}{}    \r
1760         \State \Return{$\tuple{True, True}$}        \r
1761     \Else\r
1762         \r
1763         \If{$id = LOCAL\_ID$}\r
1764             \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
1765             \State \Call{ChangeTransStatus}{$TransStatus,aborted$}\r
1766             \State \Call{DeleteTransStatus}{$id,seq_l$}\r
1767         \Else\r
1768             \State $newAbort \gets \tuple{seq_{cl}, seq_{s}, id, arb, arbitrationSeqNum}$\r
1769             \State $arbitrationSeqNum \gets arbitrationSeqNum + 1$\r
1770             \State \Call{ProcessAbort}{$newAbort$}        \r
1771             \State $ArbitrationQueue \gets ArbitrationQueue \cup \tuple{NULL, \{newAbort\}, \emptyset}$\r
1772         \r
1773             \If{\Call{CompactArbitrationRounds}{$ $}}\r
1774                 \State $\tuple{NewCom, AbortSet, \emptyset} \gets ArbitrationQueue.peakEnd()$\r
1775                 \ForAll{$compart \in NewCom$}\r
1776                     \State \Call{ProcessCommitPart}{compart}\r
1777                 \EndFor\r
1778             \EndIf\r
1779         \EndIf    \r
1780     \EndIf\r
1781     \r
1782     \State \Call{UpdateCommittedKV}{}\r
1783     \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
1784     \State \Call{UpdateSpeculativeKV}{}    \r
1785     \State \Return{$\tuple{True, False}$}\r
1786 \EndFunction\r
1787 \end{algorithmic}\r
1788 %\end{varwidth}% \r
1789 %}\r
1790 \r
1791 % Update Live Transaction and Statuses\r
1792 %\noindent\fbox{%\r
1793 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1794 \textbf{Update Live Transactions And Statuses:}\\\r
1795 Update the live transactions and the transaction statuses.\r
1796 \begin{algorithmic}[1]\r
1797 \Function{UpdateLiveTransactionsAndStatuses}{$ $}\r
1798     \ForAll{$\tuple{P, KV, G,seq_l, seq_s,id, arb} \in LiveTransactions$}\r
1799         \If{$\exists \tuple{id',seq'} \in LastTransactionArbitrated, id=id' \land seq' > seq_s$}\r
1800             \If{$id = LOCAL\_ID$}\r
1801                 \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
1802                 \State \Call{ChangeTransStatus}{$TransStatus,committed$}\r
1803                 \State \Call{DeleteTransStatus}{$id,seq_l$}\r
1804             \EndIf\r
1805         \EndIf\r
1806     \EndFor\r
1807     \State $LiveTransactions \gets \{\tuple{P, KV, G,seq_l, seq_s,id, arb}| \tuple{P, KV, G,seq_l, seq_s,id, arb} \in LiveTransactions \land \forall \tuple{id',seq'} \in LastTransactionArbitrated, id'\neq id \lor seq_s > seq'\}$\r
1808 \EndFunction\r
1809 \end{algorithmic}\r
1810 %\end{varwidth}% \r
1811 %}\r
1812 \r
1813 % Validate and Update \r
1814 %\noindent\fbox{%\r
1815 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1816 \textbf{Validate Update:}\\\r
1817 Validate the block chain and insert into the local block chain.\r
1818 \begin{algorithmic}[1]\r
1819 \Function{ValidateUpdate}{$NewSlots_a, updatinglocal_a$}\r
1820     \State $\tuple{seq_{oldest}, Dat_{oldest}} \gets$ \Call{MinSlot}{$NewSlots_a$}\r
1821     \State $\tuple{seq_{newest}, Dat_{newest}} \gets$ \Call{MaxSlot}{$NewSlots_a$}\r
1822     \State $\tuple{seq_{local}, Dat_{local}} \gets$ \Call{MaxSlot}{$LocalSlots$}\r
1823     \State $MachinesSeen \gets \{id'|\tuple{id',seq'} \in LastSlot\}$\\\r
1824     \r
1825     \State \Call{CheckSlotsHmacAndSeq}{$NewSlots_a$}\r
1826     \State \Call{CheckHmacChain}{$NewSlots_a$}\r
1827     \State \Call{CheckOldSlots}{$NewSlots_a$}\r
1828     \State \Call{CheckSize}{$NewSlots_a$}\\\r
1829     \r
1830     \ForAll{$slot_a \in NewSlots_a$ in order of sequence number}    \r
1831         \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets slot_a$\r
1832         \State \Call{UpdateLastMessage}{$seq_{a_1}, id_a, updatinglocal_a, MachinesSeen$}\\\r
1833         \r
1834         \ForAll{$de_a \in DE_a$}\r
1835             \State \Call{ProccessDatEntry}{$de_a, NewSlots_a, MachinesSeen$}\r
1836         \EndFor\\\r
1837     \r
1838         \State $LocalSlots \gets LocalSlots \cup \{slot_a\}$ \Comment{Add to local Chain}\r
1839     \EndFor\\\r
1840     \r
1841     \If{$seq_{oldest} > (seq_{local} +1) \land MachinesSeen \neq \emptyset$}\r
1842         \LeftComment{There was a gap so there should be a complete set of information on each previously seen client}\r
1843         \State \Call{Error}{"Missing records for machines"}\r
1844     \EndIf\\\r
1845     \r
1846     \State \Call{DeleteLocalSlots}{ } \Comment{Delete old slots from local}\r
1847     \r
1848     \State \Call{ArbitrateFromServer}{}\r
1849     \State \Call{UpdateCommittedKV}{}\r
1850     \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
1851     \State \Call{UpdateSpeculativeKV}{}\r
1852         \r
1853     \State $offlineTransactionAtServer \gets \emptyset$\r
1854     \State $hadPartialSendToServer \gets false$\r
1855 \EndFunction\r
1856 \end{algorithmic}\r
1857 %\end{varwidth}% \r
1858 %}\r
1859 \r
1860 % Accept from local \r
1861 %\noindent\fbox{%\r
1862 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1863 \textbf{Accept from Local:}\\\r
1864 The local transaction handling accept.\r
1865 \begin{algorithmic}[1]\r
1866 \Function{AcceptFromLocal}{$seq_a, transaction_a$}\r
1867     \State $arbitrated \gets false$\r
1868     \State $committed \gets false$\r
1869     \State $ReturnSet \gets \emptyset$\\\r
1870         \r
1871     \If{$transaction_a \neq NULL$}\r
1872         \State $\tuple{arbitrated, committed} \gets $ \Call{ArbitrateFromLocal}{$transaction_a$} \r
1873         \State $\tuple{P, KV, G,seq_l, seq_s,id, arb} \gets transaction_a$\r
1874         \If{$seq_s \neq -1$}\r
1875             \State $OfflineTransAtServer \gets OfflineTransAtServer \cup \{\tuple{id, seq_l}\}$\r
1876         \EndIf\r
1877         \State \Call{UpdateCommittedKV}{}\r
1878         \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
1879         \State \Call{UpdateSpeculativeKV}{}\r
1880     \EndIf\\\r
1881     \r
1882     \State $AllAborts \gets$ \Call{GetAborts}{} \Comment{Get all the aborts} \\\r
1883     \State $ReturnSet \gets ReturnSet \cup \{\tuple{seq_l', seq_s', id', arb', seq_{arb}'}|\tuple{seq_l', seq_s', id', arb', seq_{arb}', seq'} \in A \land id'=LOCAL\_ID \land seq_l' > seq_a\}$\r
1884     \State $ReturnSet \gets ReturnSet \cup \{p'|p'\in P' \land \tuple{P', KV', seq_t', seq_s',id'} \in LiveCommits \land id'=LOCAL\_ID \land seq_s' > seq_a\}$\r
1885     \State \Return{$\tuple{arbitrated, committed,ReturnSet}$}   \r
1886 \EndFunction\r
1887 \end{algorithmic}\r
1888 %\end{varwidth}% \r
1889 %}\r
1890 \r
1891 \r
1892 % Send to local \r
1893 %% \noindent\fbox{%\r
1894 %% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1895 \textbf{Send To Local:}\\\r
1896 Send transaction to local to be arbitrated on or not.\r
1897 \begin{algorithmic}[1]\r
1898 \Function{SendToLocal}{$transaction_a$}\r
1899     \State $\tuple{P, KV, G,seq_l, seq_s,id, arb} \gets transaction_a$\r
1900     \If{Cannot communicate locally with client $id$}\r
1901         \State \Return{$False$}\r
1902     \EndIf\r
1903 \r
1904 \r
1905     \State $seq_{lastseen} \gets seq'$ such that $\tuple{id',seq'} \in LastArbLocalArbitrated \land id'=id$\r
1906     \State $\tuple{arbitrated, committed,ReturnSet} \gets $\Call{AcceptFromLocal}{$seq_{lastseen}, transaction_a$}\\\r
1907 \r
1908     \ForAll{$e \in ReturnSet$}\r
1909         \If{$e$ is an $abort$}\r
1910             \State \Call{ProcessAbort}{$e$}\r
1911         \Else\r
1912             \State \Call{ProcessCommitPart}{$e$}\r
1913         \EndIf\r
1914     \EndFor\\\r
1915     \r
1916     \State \Call{UpdateCommittedKV}{}\r
1917     \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
1918     \State \Call{UpdateSpeculativeKV}{}\\\r
1919     \r
1920     \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
1921     \If{$arbitrated$}\r
1922         \If{$committed$}\r
1923             \State \Call{ChangeTransStatus}{$TransStatus,committed$}\r
1924         \Else\r
1925             \State \Call{ChangeTransStatus}{$TransStatus,aborted$}\r
1926         \EndIf\r
1927     \ElsIf{$\exists \tuple{seq_l', seq_s', id', arb', seq_{arb}'} \in ReturnSet, \tuple{seq_l', seq_s', id', arb', seq_{arb}'}$ is an $abort \land id' = LOCAL\_ID \land seq_l' = seq_l$}\r
1928         \State \Call{ChangeTransStatus}{$TransStatus,aborted$}\r
1929     \Else\r
1930         \State \Call{ChangeTransStatus}{$TransStatus,committed$} \r
1931     \EndIf\r
1932     \r
1933     \State \Call{DeleteTransStatus}{$id,seq_l$}\r
1934     \State \Return{$True$}\r
1935 \EndFunction\r
1936 \end{algorithmic}\r
1937 % %\end{varwidth}% \r
1938 % }\r
1939 \r
1940 \r
1941 \subsection{Client Interfaces}\r
1942 \r
1943 \r
1944 \r
1945 \r
1946 % Update\r
1947 %\noindent\fbox{%\r
1948 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1949 \textbf{Update}\\\r
1950 Sync with the server and get all the latest slots.\r
1951 \r
1952 \algblock[TryCatchFinally]{try}{endtry}\r
1953 \algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}\r
1954 \algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}\r
1955     [1]{\textbf{catch} #1}\r
1956     {\textbf{end try}}\r
1957 \r
1958 \begin{algorithmic}[1]\r
1959 \Function{UpdateFromServer}{$ $}\r
1960     \State $NewSlots_{decrypt} \gets \emptyset$\r
1961     \State $\tuple{seq, Dat} \gets $ \Call{MaxSlot}{$LocalSlots$}\\\r
1962     \r
1963     \try\r
1964         \State $NewSlots \gets$ \Call{GetSlots}{$seq$}\\\r
1965         \r
1966         \ForAll{$\tuple{seq', EDat'} \in NewSlots$}\r
1967             \State $DDat \gets $ \Call{Decrypt}{$EDat'$}\r
1968             \State $NewSlots_{decrypt} \gets NewSlots_{decrypted} \cup \tuple{seq',DDat}$\r
1969         \EndFor\\\r
1970         \r
1971         \State \Call{ValidateAndUpdate}{$NewSlots_{decrypt}$}        \r
1972         \State \Call{SendToServer}{$Null$}\r
1973         \State \Return{$True$}    \r
1974     \catch{$Exception$}\r
1975         \LeftComment{Do nothing here}\r
1976     \endtry\r
1977     \r
1978     \State \Return{$False$}\r
1979     \r
1980 \EndFunction\r
1981 \end{algorithmic}\r
1982 %\end{varwidth}% \r
1983 %}\r
1984 \r
1985 % Update from local\r
1986 %\noindent\fbox{%\r
1987 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1988 \textbf{Update from local}\\\r
1989 Get the latest from a client through local communication.\r
1990 \begin{algorithmic}[1]\r
1991 \Function{UpdateFromLocal}{$id_a$}\r
1992     \If{Cannot communicate locally with client $id$}\r
1993         \State \Return{}\r
1994     \EndIf\r
1995     \r
1996     \State $seq_{lastseen} \gets seq'$ such that $\tuple{id',seq'} \in LastArbLocalArbitrated \land id'=id_a$\r
1997     \State $\tuple{arbitrated, committed,ReturnSet} \gets $\Call{AcceptFromLocal}{$seq_{lastseen}, transaction_a$}\\\r
1998 \r
1999     \ForAll{$e \in ReturnSet$}\r
2000         \If{$e$ is an $abort$}\r
2001             \State \Call{ProcessAbort}{$e$}\r
2002         \Else\r
2003             \State \Call{ProcessCommitPart}{$e$}\r
2004         \EndIf\r
2005     \EndFor\\\r
2006     \r
2007     \State \Call{UpdateCommittedKV}{}\r
2008     \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
2009     \State \Call{UpdateSpeculativeKV}{}\\\r
2010 \r
2011 \EndFunction\r
2012 \end{algorithmic}\r
2013 %\end{varwidth}% \r
2014 %}\r
2015 \r
2016 \r
2017 %Create New Key \r
2018 %\noindent\fbox{%\r
2019 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
2020 \textbf{Create New Key:}\\\r
2021 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
2022 \begin{algorithmic}[1]\r
2023 \Function{Transaction Commit}{$k_a, id_a$}\r
2024     \State $success \gets false$\\\r
2025     \While{$\lnot success$}\r
2026         \If{$\exists \tuple{k',id'} \in Arbitrator, k' = k_a$}\r
2027             \State \Return{$false$} \Comment{Key already created}\r
2028         \EndIf\\\r
2029         \r
2030         \State $success \gets$ \Call{SendToServer}{$\tuple{k_a, id_a}$}\r
2031     \EndWhile\r
2032     \r
2033     \State \Return{$true$} \Comment{If got here then insertion was correct}\r
2034 \EndFunction\r
2035 \end{algorithmic}\r
2036 %\end{varwidth}% \r
2037 %}\r
2038 \r
2039 % Transaction Start\r
2040 %\noindent\fbox{%\r
2041 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
2042 \textbf{ Transaction Start:}\\\r
2043 Starts a transaction.\r
2044 \begin{algorithmic}[1]\r
2045 \Function{TransactionStart}{$ $}\r
2046     \State $newPendingTransaction \gets \tuple{\emptyset, \emptyset, LOCAL\_ID,clntTransactionNum}$\r
2047     \State $clntTransactionNum \gets clntTransactionNum + 1$\r
2048 \EndFunction\r
2049 \end{algorithmic}\r
2050 %\end{varwidth}% \r
2051 %}\r
2052 \r
2053 % Put KV pair\r
2054 %\noindent\fbox{%\r
2055 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
2056 \textbf{Put Key Value Pair:}\\\r
2057 Puts a key value pair into the key value pair buffer.\r
2058 \begin{algorithmic}[1]\r
2059 \Function{PutKeyValue}{$k,v$}\r
2060     \State $\tuple{KV, G,id, seq_{clientLocal}} \gets newPendingTransaction$\r
2061     \State $KV \gets \{\tuple{k',v'}| \tuple{k,v} \in KV, k \neq k'\}\cup \{\tuple{k,v}\}$ \r
2062     \State $ArbSet \gets \{arb| \exists \tuple{k',v'} \in (KV \cup G), arb=$\Call{GetArbitrator}{$k'$}$\}$\r
2063     \If{$|ArbSet| > 1$}\r
2064         \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
2065     \EndIf\r
2066     \State $newPendingTransaction \gets \tuple{KV, G,id, seq_{clientLocal}}$\r
2067 \EndFunction\r
2068 \end{algorithmic}\r
2069 %\end{varwidth}% \r
2070 %}\r
2071 \r
2072 % Transaction Commit\r
2073 %\noindent\fbox{%\r
2074 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
2075 \textbf{ Transaction Commit:}\\\r
2076 Commits a transaction.\r
2077 \r
2078 \algblock[TryCatchFinally]{try}{endtry}\r
2079 \algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}\r
2080 \algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}\r
2081     [1]{\textbf{catch} #1}\r
2082     {\textbf{end try}}\r
2083 \begin{algorithmic}[1]\r
2084 \Function{TransactionCommit}{$ $}\r
2085     \State $\tuple{KV, G,id, seq_{clientLocal}} \gets newPendingTransaction$\r
2086     \r
2087     \If{$|KV| = 0$} \Comment{Nothing To Update}\r
2088         \State $TransStatus \gets \tuple{noeffect}$ \r
2089         \State \Return{$TransStatus$}\r
2090     \EndIf\r
2091     \State $transArb \gets $\Call{GetArbitratorKV}{$KV$}\r
2092     \r
2093     \If{$transArb = LOCAL\_ID$}\r
2094         \State \Call{ArbitrateFromLocal}{$\tuple{\emptyset, KV, G,seq_{clientLocal},-1,LOCAL\_ID,transArb}$}\r
2095         \State \Call{UpdateCommittedKV}{}\r
2096         \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
2097         \State \Call{UpdateSpeculativeKV}{}    \r
2098     \Else\r
2099         \State $TransStatus \gets \tuple{pending}$ \r
2100         \State \Call{SetTransStatus}{$LOCAL\_ID, seq_{clientLocal}, TransStatus$}\r
2101         \r
2102         \State $newTrans \gets \tuple{\emptyset, KV, G,seq_{clientLocal},-1,LOCAL\_ID,transArb}$\r
2103         \State \Call{GenerateParts}{newTrans}        \r
2104         \State $PendingTransactionQueue.push(\tuple{newTrans, \emptyset, false}$    \r
2105     \EndIf\r
2106     \r
2107     \State $newPendingTransaction \gets \tuple{\emptyset, \emptyset, LOCAL\_ID,clntTransactionNum}$\r
2108     \State $clntTransactionNum \gets clntTransactionNum + 1$\r
2109 \r
2110     \try\r
2111         \State \Call{SendToServer}{$NULL$}\r
2112     \catch{$Exception$}   \r
2113         \ForAll{$transaction \in PendingTransactionQueue$}\r
2114             \If{\Call{SendToLocal}{$transaction$}}\r
2115                 \State $PendingTransactionQueue.remove(transaction)$\r
2116             \EndIf\r
2117         \EndFor\r
2118     \endtry\r
2119     \r
2120 \EndFunction\r
2121 \end{algorithmic}\r
2122 %\end{varwidth}% \r
2123 %}\r
2124 \r
2125 % Get KV Pair Committed\r
2126 %\noindent\fbox{%\r
2127 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
2128 \textbf{Get KV Pair Committed:}\\\r
2129 Get the value for the key which have been committed.\r
2130 \begin{algorithmic}[1]\r
2131 \Function{GetCommit}{$k_a$}\r
2132     \If{$\exists \tuple{k,v} \in CommittedKV \land k \neq k_a$}\r
2133         \State \Return{$NULL$}\r
2134     \EndIf\r
2135     \State \Return{$v$ such that $\tuple{k,v} \in CommittedKV \land k = k_a$}\r
2136 \EndFunction\r
2137 \end{algorithmic}\r
2138 %\end{varwidth}% \r
2139 %}\r
2140 \r
2141 % Get KV Pair Committed Atomic\r
2142 %\noindent\fbox{%\r
2143 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
2144 \textbf{Get KV Pair Committed Atomic:}\\\r
2145 Get the value for the key which have been committed and add it to the guard condition of the current pending transaction.\r
2146 \begin{algorithmic}[1]\r
2147 \Function{GetCommitAtomic}{$k_a$}\r
2148     \State $val \gets NULL$\r
2149     \If{$\exists \tuple{k,v} \in CommittedKV \land k = k_a$}\r
2150         \State $val \gets v$ such that $\tuple{k,v} \in CommittedKV \land k = k_a$\r
2151     \EndIf\\\r
2152     \r
2153     \State $\tuple{KV, G, seq_{clientLocal}} \gets newPendingTransaction$\r
2154     \State $G \gets G \cup \{\tuple{k_a,val}\}$\r
2155     \State $ArbSet \gets \{arb| \exists \tuple{k',v'} \in (KV \cup G), arb=$\Call{GetArbitrator}{$k'$}$\}$\r
2156     \If{$|ArbSet| > 1$}\r
2157         \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
2158     \EndIf\r
2159     \State $newPendingTransaction \gets \tuple{KV, G, seq_{clientLocal}}$\r
2160     \State \Return{$val$}\r
2161 \EndFunction\r
2162 \end{algorithmic}\r
2163 %\end{varwidth}% \r
2164 %}\r
2165 \r
2166 % Get KV Pair Speculative \r
2167 %\noindent\fbox{%\r
2168 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
2169 \textbf{Get KV Pair Speculative:}\\\r
2170 Get the value for the key which have been speculated on.\r
2171 \begin{algorithmic}[1]\r
2172 \Function{GetSpeculated}{$k_a$}\r
2173     \If{$\exists \tuple{k,v} \in SpeculatedKV \land k \neq k_a$}\r
2174         \State \Return{$NULL$}\r
2175     \EndIf\r
2176     \State \Return{$v$ such that $\tuple{k,v} \in SpeculatedKV \land k = k_a$}\r
2177 \EndFunction\r
2178 \end{algorithmic}\r
2179 %\end{varwidth}% \r
2180 %}\r
2181 \r
2182 % Get KV Pair Speculative Atomic\r
2183 %\noindent\fbox{%\r
2184 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
2185 \textbf{Get KV Pair Speculative Atomic:}\\\r
2186 Get the value for the key which have been speculative and add it to the guard condition of the current pending transaction.\r
2187 \begin{algorithmic}[1]\r
2188 \Function{GetSpeculatedAtomic}{$k_a$}\r
2189     \State $val \gets NULL$\r
2190     \If{$\exists \tuple{k,v} \in SpeculatedKV \land k = k_a$}\r
2191         \State $val \gets v$ such that $\tuple{k,v} \in SpeculatedKV \land k = k_a$\r
2192     \EndIf\\\r
2193     \r
2194     \State $\tuple{KV, G, id,seq_{clientLocal}} \gets newPendingTransaction$\r
2195     \State $G \gets G \cup \{\tuple{k_a,val}\}$\r
2196     \State $ArbSet \gets \{arb| \exists \tuple{k',v'} \in (KV \cup G), arb=$\Call{GetArbitrator}{$k'$}$\}$\r
2197     \If{$|ArbSet| > 1$}\r
2198         \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
2199     \EndIf\r
2200     \State $newPendingTransaction \gets \tuple{KV, G, seq_{clientLocal}}$\r
2201     \State \Return{$val$}\r
2202 \EndFunction\r
2203 \end{algorithmic}\r
2204 %\end{varwidth}% \r
2205 %}\r
2206 \r
2207 \end{document}\r