doc2/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{algpseudocode}% http://ctan.org/pkg/algorithmicx\r
  10 \usepackage[all]{xy}\r
  11 \usepackage{varwidth}\r
  12 \r
  13 \newtheorem{theorem}{Theorem}\r
  14 \newtheorem{prop}{Proposition}\r
  15 \newtheorem{lem}{Lemma}\r
  16 \newtheorem{defn}{Definition}\r
  17 \newcommand{\note}[1]{{\color{red} \bf [[#1]]}}\r
  18 \newcommand{\push}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}\r
  19 \newcommand*\xor{\mathbin{\oplus}}\r
  20 \algnewcommand{\LeftComment}[1]{\Statex \(\triangleright\) #1}\r
  21 \begin{document}\r
  22 \r
  23 \r
  24 \setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text\r
  25 \r
  26 \r
  27 \section{\textbf{Introduction}}\r
  28 \r
  29 \section{\textbf{Client}}\r
  30 \r
  31 \subsection{\textbf{Client Notation Conventions}}\r
  32 \r
  33 \r
  34 $k$ is key of entry \\\r
  35 $v$ is value of entry \\\r
  36 $size$ is a size (target size of the current block chain) \\\r
  37 $kv$ is a key-value pair $\tuple{k,v}$ \\\r
  38 $KV$ is a set of $kv$ \\\r
  39 $id$ is a machine ID \\\r
  40 $seq$ is a sequence number \\\r
  41 $hmac_p$ is the HMAC value of the previous slot \\\r
  42 $hmac_c$ is the HMAC value of the current slot \\\r
  43 $Guard$ is a set of$ \tuple{k,v,$logical operator$}$ which can be evaluated to a boolean \\\r
  44 \r
  45 $trans$ is a transaction entry , $\tuple{seq, id, KV, Guard}$  \\\r
  46 $lastmsg$ is a last message entry, $\tuple{seq, id}$ \\\r
  47 $qstate$ is a queue state entry, $\tuple{size}$ \\\r
  48 $colres$ is a collision resolution entry, $\tuple{id, seq_{old}, seq_{new}, true \lor false}$ \\\r
  49 $newkey$ is a new key entry, $\tuple{k, id}$, $id$ is ID of arbitrator \\\r
  50 $commit$ is a commit transaction entry, $\tuple{seq_{trans},KV}$, id is id of arbitrator \\\r
  51 $abort$ is an abort transaction entry, $\tuple{seq_{trans},id_{trans}}$ \\\r
  52 \r
  53 \r
  54 $de$ is a data entry that can one of: $trans$, $lastmsg$, $qstate$, $colres$, $newkey$, $commit$, $abort$ \\\r
  55 $DE$ is a set of all data entries, possibly of different types, in a single message, set of $de$\\\r
  56 \r
  57 $slotDat = \tuple{seq,id,DE,hmac_p,hmac_c}$ \\\r
  58 $slot = \tuple{seq, Encrpt(slotDat)}$\\\r
  59 \r
  60 \subsection{\textbf{Client State}}\r
  61 \r
  62 \subsubsection{Constants}\r
  63 $LOCAL\_ID$ = machine ID of this client.\\\r
  64 $RESIZE\_THRESH\_PERCENT$ = percent of slots that need to have live data to trigger a resize.\\\r
  65 $RESIZE\_PERCENT$ = percent that we should grow the block chain to.\\\r
  66 $DATA\_ENTRY\_SET\_MAX\_SIZE$ = max size that a data entry set can have (in bytes).\\\r
  67 $DEAD\_SLOT\_COUNT$ = number of slots to keep dead if possible at the end of the block chain.\\\r
  68 $MAX\_RESCUE\_SKIPS$ = number of skips that are allowed when saving data entries.\\\r
  69 \r
  70 \subsubsection{Primitive Variables}\r
  71 $max\_size$ = max size of the block chain\\\r
  72 \r
  73 \subsubsection{Sets and Lists}\r
  74 \r
  75 $PendingTransSet$ = Set of pending transactions that need to be pushed to the block chain, $\tuple{number,PendingTrans}$\\\r
  76 $PendingTrans= \tuple{KV, Guard} = \tuple{$set of key value pairs, set of guard conditions$}$.\\\r
  77 $Arbitrator$ = set of $\tuple{k,id}$ containing the key and its arbitrating device.\\\r
  78 $LastSlot$ = set of $\tuple{id, seq}$ containing the machine ID and the largest sequence number from that machine ID.\\\r
  79 $LocalSlots$ = set of slots that are in the clients local buffer (initially $\emptyset$), data is decrypted.\\\r
  80 $RejectedSlotList$ = ordered list of the sequence numbers of slots that this client tried to insert but were rejected.\\\r
  81 $CommittedKV$ = set of committed key value pairs (initially $\emptyset$).\r
  82 $SpeculatedKV$ = set of speculated key value pairs (initially $\emptyset$).\r
  83 \r
  84 \subsection{Helper Functions}\r
  85 The following helper functions are needed:\\\r
  86 \r
  87 $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
  88 $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
  89 \r
  90 \r
  91 % Get Size\r
  92 \noindent\fbox{%\r
  93 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
  94 \textbf{Get Byte Size:}\\\r
  95 Get the size in bytes of the thing that is passed in.\\\r
  96 \begin{algorithmic}[1]\r
  97 \Function{GetSize}{$a$}\r
  98     \State \Return{Size in bytes of $a$}\r
  99 \EndFunction\r
 100 \end{algorithmic}\end{varwidth}% \r
 101 }\r
 102 \r
 103 % Error\r
 104 \noindent\fbox{%\r
 105 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 106 \textbf{ Error:}\\\r
 107 Prints an error message and halts the execution of the client.\\\r
 108 \begin{algorithmic}[1]\r
 109 \Function{Error}{$msg$}\r
 110     \State $Print(msg)$\r
 111     \State $Halt()$\r
 112 \EndFunction\r
 113 \end{algorithmic}\end{varwidth}% \r
 114 }\r
 115 \r
 116 % Get Next Sequence Number\r
 117 \noindent\fbox{%\r
 118 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 119 \textbf{Get Next Sequence Number:}\\\r
 120 Get the next sequence number for insertion into the block chain.\\\r
 121 \begin{algorithmic}[1]\r
 122 \Function{GetNextSeq}{$k$}\r
 123     \LeftComment{Get the largest known sequence number}\r
 124     \State $seq_{ret} \gets seq$ such that $\tuple{id, seq}\in LastSlo \land (\forall \tuple{id', seq'} \in LastSlo, seq \geq seq')$\\\r
 125     \r
 126     \LeftComment{Add one to the largest seq number to generate the new seq number}\r
 127     \State \Return{$seq_{ret} + 1$}\r
 128 \EndFunction\r
 129 \end{algorithmic}\r
 130 \end{varwidth}% \r
 131 }\r
 132 \r
 133 % Get Arbitrator\r
 134 \noindent\fbox{%\r
 135 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 136 \textbf{Get Arbitrator:}\\\r
 137 Get the arbitrator for a given key.\\\r
 138 \begin{algorithmic}[1]\r
 139 \Function{GetArbitrator}{$k$}\r
 140     \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
 141     \State \Return{$id_1$}\r
 142 \EndFunction\r
 143 \end{algorithmic}\r
 144 \end{varwidth}% \r
 145 }\r
 146 \r
 147 % Get Arbitrator KV\r
 148 \noindent\fbox{%\r
 149 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 150 \textbf{Get Arbitrator for KV Set:}\\\r
 151 Get the arbitrator for a given key value set.\\\r
 152 \begin{algorithmic}[1]\r
 153 \Function{GetArbitratorKV}{$KV$}\r
 154     \State $\tuple{k,v} \gets \tuple{k',v'}$ such that $\tuple{k',v'} \in KV$\r
 155     \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
 156     \State \Return{$id_1$}\r
 157 \EndFunction\r
 158 \end{algorithmic}\r
 159 \end{varwidth}% \r
 160 }\r
 161 \r
 162 % Check Transaction arbitrator\r
 163 \noindent\fbox{%\r
 164 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 165 \textbf{Check Arbitrator for a Transaction:}\\\r
 166 Check that the arbitrators for a given set are all the same arbitrator.\\\r
 167 \begin{algorithmic}[1]\r
 168 \Function{CheckArbitrator}{$PendingTrans_a$}\r
 169     \State $id_{arb} \gets NULL$\\\r
 170     \State $\tuple{KV_a, Guard_a} \gets PendingTrans_a$\r
 171     \r
 172     \ForAll{$\tuple{k',v'} \in KV_a$}\r
 173         \State $id' \gets$ \Call{GetArbitrator}{$k'$}\\\r
 174         \r
 175         \If{$id_{arb} = NULL$}  \r
 176             \State $id_{arb} \gets id'$\r
 177         \ElsIf{$id' \neq id_{arb}$} \Comment{Check all arbitrators are the same}\r
 178             \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
 179         \EndIf\r
 180     \EndFor\r
 181     \r
 182     \ForAll{$\tuple{k',v', lop'} \in Guard_a$}\r
 183         \State $id' \gets$ \Call{GetArbitrator}{$k'$}\\\r
 184         \r
 185         \If{$id_{arb} = NULL$}  \r
 186             \State $id_{arb} \gets id'$\r
 187         \ElsIf{$id' \neq id_{arb}$} \Comment{Check all arbitrators are the same}\r
 188             \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
 189         \EndIf\r
 190     \EndFor\r
 191 \EndFunction\r
 192 \end{algorithmic}\r
 193 \end{varwidth}% \r
 194 }\r
 195 \r
 196 % Get all Commits\r
 197 \noindent\fbox{%\r
 198 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 199 \textbf{Get all Commits:}\\\r
 200 Get all commits that are currently in the local block chain.  Iterate over all the local slots and extract all the commits from each slot.\\\r
 201 \begin{algorithmic}[1]\r
 202 \Function{GetCommits}{$ $}\r
 203     \State $ComSet \gets \emptyset$ \Comment{Set of the commits}\\\r
 204         \r
 205     \LeftComment{Iterate over all the slots saved locally}\r
 206     \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 207         \State $ComSet \gets ComSet \cup \{c |c \in DE',c$is a $commit\}$\r
 208     \EndFor\r
 209     \State \Return{$ComSet$}\r
 210 \EndFunction\r
 211 \end{algorithmic}\r
 212 \end{varwidth}% \r
 213 }\r
 214 \r
 215 % Get all Transactions\r
 216 \noindent\fbox{%\r
 217 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 218 \textbf{Get all Transactions:}\\\r
 219 Get all transactions that are currently in the local block chain.  Iterate over all the local slots and extract all the transactions from each slot.\\\r
 220 \begin{algorithmic}[1]\r
 221 \Function{GetTrans}{$ $}\r
 222     \State $TransSet \gets \emptyset$ \Comment{Set of the trans}\\\r
 223         \r
 224     \LeftComment{Iterate over all the slots saved locally}\r
 225     \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 226         \State $TransSet \gets TransSet \cup \{c |c \in DE',c$is a $trans\}$\r
 227     \EndFor\r
 228     \State \Return{$TransSet$}\r
 229 \EndFunction\r
 230 \end{algorithmic}\r
 231 \end{varwidth}% \r
 232 }\r
 233 \r
 234 % Get all aborts\r
 235 \noindent\fbox{%\r
 236 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 237 \textbf{Get all aborts:}\\\r
 238 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
 239 \begin{algorithmic}[1]\r
 240 \Function{GetAborts}{$ $}\r
 241     \State $AbrtSet \gets \emptyset$ \Comment{Set of the aborts}\\\r
 242         \r
 243     \LeftComment{Iterate over all the slots saved locally}\r
 244     \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 245         \State $AbrtSet \gets AbrtSet \cup \{c |c \in DE',c$is a $abort\}$\r
 246     \EndFor\r
 247     \State \Return{$AbrtSet$}\r
 248 \EndFunction\r
 249 \end{algorithmic}\r
 250 \end{varwidth}% \r
 251 }\r
 252 \r
 253 % Get all Queue States\r
 254 \noindent\fbox{%\r
 255 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 256 \textbf{Get all queue states:}\\\r
 257 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
 258 \begin{algorithmic}[1]\r
 259 \Function{GetQStates}{$ $}\r
 260     \State $QSet \gets \emptyset$ \Comment{Set of the qstates}\\\r
 261         \r
 262     \LeftComment{Iterate over all the slots saved locally}\r
 263     \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 264         \State $QSet \gets QSet \cup \{c |c \in DE',c$is a $qstate\}$\r
 265     \EndFor\r
 266     \State \Return{$QSet$}\r
 267 \EndFunction\r
 268 \end{algorithmic}\r
 269 \end{varwidth}% \r
 270 }\r
 271 \r
 272 % Get all Last Messages States\r
 273 \noindent\fbox{%\r
 274 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 275 \textbf{Get all last message data entrues:}\\\r
 276 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
 277 \begin{algorithmic}[1]\r
 278 \Function{GetLastMsg}{$ $}\r
 279     \State $LMSet \gets \emptyset$ \Comment{Set of the last msg}\\\r
 280         \r
 281     \LeftComment{Iterate over all the slots saved locally}\r
 282     \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 283         \State $LMSet \gets LMSet \cup \{c |c \in DE',c$is a $lastmsg\}$\r
 284     \EndFor\r
 285     \State \Return{$LMSet$}\r
 286 \EndFunction\r
 287 \end{algorithmic}\r
 288 \end{varwidth}% \r
 289 }\r
 290 \r
 291 % Check Queue State Live\r
 292 \noindent\fbox{%\r
 293 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 294 \textbf{Check Queue State Live:}\\\r
 295 A queue state is dead if there is another queue state data entry that has a larger queue state.\\\r
 296 \begin{algorithmic}[1]\r
 297 \Function{CheckQStateLive}{$qstate_a$}\r
 298     \State $\tuple{size_a} \gets qstate_a$\r
 299     \State $AllQStates \gets$ \Call{GetQState}{} \Comment{Get all the qstates} \\\r
 300     \r
 301     \If{$\exists \tuple{size'} \in AllQStates, size' > size_a$}\r
 302         \State \Return{false}\r
 303     \EndIf\r
 304     \State \Return{true}\r
 305     \r
 306 \EndFunction\r
 307 \end{algorithmic}\r
 308 \end{varwidth}% \r
 309 }\r
 310 \r
 311 % Check Commit Live\r
 312 \noindent\fbox{%\r
 313 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 314 \textbf{Check Commit Live:}\\\r
 315 A commit is dead if for every key value pair in the commit there is a commit with a larger transaction sequence number that has a key value pair with the same key.\\\r
 316 \begin{algorithmic}[1]\r
 317 \Function{CheckCommitLive}{$commit_a$}\r
 318     \State $\tuple{seq_{a_{trans}},KV_a} \gets commit_a$\r
 319     \State $KSet \gets \{k|\tuple{k,v} \in KV\}$\r
 320     \State $AllCommits \gets$ \Call{GetCommits}{} \Comment{Get all the commits} \\\r
 321     \r
 322     \LeftComment{Iterate all commits that are newer in time}\r
 323     \ForAll{$\tuple{seq_{trans}',KV'}\in AllCommits, seq_{trans}' > seq_{a_{trans}}$}\r
 324         \State $KVSet \gets KVSet \setminus \{k|\tuple{k,v} \in KV'\}$\\\r
 325         \r
 326         \If{$KVSet = \emptyset$}\r
 327             \State \Return{false} \Comment{All keys have a newer commit}\r
 328         \EndIf\r
 329     \EndFor\r
 330     \State \Return{true} \Comment{If got here then some keys still live}\r
 331 \EndFunction\r
 332 \end{algorithmic}\r
 333 \end{varwidth}% \r
 334 }\r
 335 \r
 336 % Check Last Message Live\r
 337 \noindent\fbox{%\r
 338 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 339 \textbf{Check Last Message Live:}\\\r
 340 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
 341 \begin{algorithmic}[1]\r
 342 \Function{CheckLastMsgLive}{$lastmsg_a$}\r
 343     \State $\tuple{seq_a, id_a} \gets lastmsg_a$\\\r
 344     \r
 345     \If{$\exists \tuple{id', seq'} \in LastSlot, id'=id_a \land seq' > seq_a$}\r
 346         \State \Return{false}\r
 347     \EndIf\r
 348     \State \Return{True}    \r
 349 \EndFunction\r
 350 \end{algorithmic}\r
 351 \end{varwidth}% \r
 352 }\r
 353 \r
 354 %Check Collision Resolution Live\r
 355 \noindent\fbox{%\r
 356 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 357 \textbf{Check Collision Resolution Live:}\\\r
 358 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
 359 \begin{algorithmic}[1]\r
 360 \Function{CheckColResLive}{$colres_a$}\r
 361     \State $\tuple{id_a, seq_{a_{old}}, seq_{a_{new}}, equal_a} \gets colres_a$\\\r
 362     \r
 363     \If{$\forall \tuple{id', seq'} \in LastSlot, seq' \geq seq_{a_{new}}$}\r
 364         \State \Return{false}\r
 365     \EndIf\r
 366     \State \Return{true}\r
 367 \EndFunction\r
 368 \end{algorithmic}\r
 369 \end{varwidth}% \r
 370 }\r
 371 \r
 372 % Check New Key Live\r
 373 \noindent\fbox{%\r
 374 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 375 \textbf{Check New Key Live:}\\\r
 376 A new key data entry is always live.\\\r
 377 \begin{algorithmic}[1]\r
 378 \Function{CheckNewkeyLive}{$newkey_a$}\r
 379     \State \Return{True}    \r
 380 \EndFunction\r
 381 \end{algorithmic}\r
 382 \end{varwidth}% \r
 383 }\r
 384 \r
 385 % Check Abort Live\r
 386 \noindent\fbox{%\r
 387 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 388 \textbf{Check Abort Live:}\\\r
 389 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 numberl that is larger than the aborts sequence number.\\\r
 390 \begin{algorithmic}[1]\r
 391 \Function{CheckAbortLive}{$abort_a, seq_a$}\r
 392     \State $\tuple{seq_{a_{trans}},id_a} \gets abort_a$\\\r
 393     \r
 394     \LeftComment{The device whos transaction was aborted saw the abort}\r
 395     \If{$\exists \tuple{id', seq'} \in LastSlot, id'=id_a \land seq' > seq_a$}\r
 396         \State \Return{false}\r
 397     \EndIf\r
 398     \State \Return{True}    \r
 399 \EndFunction\r
 400 \end{algorithmic}\r
 401 \end{varwidth}% \r
 402 }\r
 403 \r
 404 % Check Transaction Live\r
 405 \noindent\fbox{%\r
 406 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 407 \textbf{Check Transaction Live:}\\\r
 408 A transaction is dead if there is an abort for that transaction or if there is a commit for that a transaction that came after this transaction.  Since transactions must be committed in order of there insertion, seeing a transaction that is committed and has a larger sequence number than the transaction in question means that the transaction in question was committed at some point.\\\r
 409 \begin{algorithmic}[1]\r
 410 \Function{CheckTransLive}{$trans_a$}\r
 411     \State $\tuple{seq_a, id_a, KV_a, Guard_a} \gets trans_a$\r
 412     \State $AllCommits \gets$ \Call{GetCommits}{} \Comment{Get all the commits}\r
 413     \State $AllAborts \gets$ \Call{GetAborts}{} \Comment{Get all the aborts} \\\r
 414     \r
 415     \If{$\exists \tuple{seq_{abrt}',seq_{trans}',id'} \in AllAborts, seq_{trans}' = seq_a$}\r
 416         \State \Return{false}\r
 417     \ElsIf{$\exists \tuple{seq_{trans}',KV'} \in AllCommits, seq_{trans}' \geq seq_a$}\r
 418         \State \Return{false}\r
 419     \EndIf\r
 420     \State \Return{true}\r
 421 \EndFunction\r
 422 \end{algorithmic}\r
 423 \end{varwidth}% \r
 424 }\r
 425 \r
 426 % Check Live\r
 427 \noindent\fbox{%\r
 428 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 429 \textbf{Check Live:}\\\r
 430 Checks if a data entry is live based on its type.\\\r
 431 \begin{algorithmic}[1]\r
 432 \Function{CheckLive}{$datentry, seq$}\r
 433     \If{$datentry$ is a $commit$}\r
 434         \State \Return{\Call{CheckCommitLive}{$datentry$}}\\r
 435     \ElsIf{$datentry$ is a $abort$}\r
 436         \State \Return{\Call{CheckAbortLive}{$datentry, seq$}}\\r
 437     \ElsIf{$datentry$ is a $trans$}\r
 438         \State \Return{\Call{CheckTransLive}{$datentry$}}\\r
 439     \ElsIf{$datentry$ is a $lastmsg$}\r
 440         \State \Return{\Call{CheckLastMsgLive}{$datentry$}}\\r
 441     \ElsIf{$datentry$ is a $colres$}\r
 442         \State \Return{\Call{CheckColResLive}{$datentry$}}\\r
 443     \ElsIf{$datentry$ is a $qstate$}\r
 444         \State \Return{\Call{CheckQStateLive}{$datentry$}}\r
 445     \ElsIf{$datentry$ is a $newkey$}\r
 446         \State \Return{\Call{CheckNewkeyLive}{$datentry$}}\r
 447     \Else\r
 448         \State \Call{Error}{"Unknown data entry type."}\r
 449     \EndIf\r
 450 \EndFunction\r
 451 \end{algorithmic}\r
 452 \end{varwidth}% \r
 453 }\r
 454 \r
 455 % Slot Has Live\r
 456 \noindent\fbox{%\r
 457 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 458 \textbf{Slot Has Live:}\\\r
 459 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
 460 \begin{algorithmic}[1]\r
 461 \Function{SlotHasLive}{$slot_a$}\r
 462     \State $\tuple{s_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in LocalSlots$\r
 463     \r
 464     \ForAll{$datentry \in DE$}\r
 465         \If{\Call{CheckLive}{$datentry, s_1$}} \Comment{an entry is alive}\r
 466             \State \Return{true}\r
 467         \EndIf\r
 468     \EndFor\r
 469     \r
 470     \State \Return{false} \Comment{All entries were dead}    \r
 471 \EndFunction\r
 472 \end{algorithmic}\r
 473 \end{varwidth}% \r
 474 }\r
 475 \r
 476 % Calculate Resize Threshold\r
 477 \noindent\fbox{%\r
 478 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 479 \textbf{Calculate Resize Threshold:}\\\r
 480 Calculate a threshold for how many slots need to have live data entries in them for a resize to take place.\\\r
 481 \begin{algorithmic}[1]\r
 482 \Function{CalcResizeThresh}{$maxsize$}\r
 483     \State \Return{$\left \lfloor {maxsize * RESIZE\_THRESH\_PERCENT} \right \rfloor$}\r
 484 \EndFunction\r
 485 \end{algorithmic}\r
 486 \end{varwidth}% \r
 487 }\r
 488 \r
 489 % Calculate Block Chain New Size\r
 490 \noindent\fbox{%\r
 491 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 492 \textbf{Calculate Block Chain New Size:}\\\r
 493 Calculate the new size of the block chain which we need if we are to resize the data structure.\\\r
 494 \begin{algorithmic}[1]\r
 495 \Function{CalcNewSize}{$maxsize$}\r
 496     \State \Return{$\left \lceil {maxsize * RESIZE\_THRESH\_PERCENT} \right \rceil$}\r
 497 \EndFunction\r
 498 \end{algorithmic}\r
 499 \end{varwidth}% \r
 500 }\r
 501 \r
 502 % Should Resize\r
 503 \noindent\fbox{%\r
 504 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 505 \textbf{Should Resize:}\\\r
 506 Check if the block should resize based on some metric of how many slots in the block chain are filled with live data. \\\r
 507 \begin{algorithmic}[1]\r
 508 \Function{ShouldResize}{$ $}\r
 509     \State $LiveSlots \gets \{slot_s|slot_s \in LocalSlots \land $\Call{SlotHasLive}{$slot_s$}$\}$\r
 510     \State $resizethreshold \gets $ \Call{CalcResizeThresh}{$max\_size$}\r
 511     \State \Return{$|LiveSlots| \geq resizethreshold$} \Comment{If passes threshold then resize}\r
 512 \EndFunction\r
 513 \end{algorithmic}\r
 514 \end{varwidth}% \r
 515 }\r
 516 \r
 517 % Create Queue State \r
 518 \noindent\fbox{%\r
 519 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 520 \textbf{Create Queue State:}\\\r
 521 Generate a queue state data entry.\\\r
 522 \begin{algorithmic}[1]\r
 523 \Function{CreateQState}{$size_a$}\r
 524     \State \Return{$\tuple{size_a}$}    \r
 525 \EndFunction\r
 526 \end{algorithmic}\r
 527 \end{varwidth}% \r
 528 }\r
 529 \r
 530 % Create Abort\r
 531 \noindent\fbox{%\r
 532 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 533 \textbf{Create Abort:}\\\r
 534 Generate a abort data entry.\\\r
 535 \begin{algorithmic}[1]\r
 536 \Function{CreateAbort}{$seq_a, id_a$}\r
 537     \State \Return{$\tuple{seq_a, id_a}$}\r
 538 \EndFunction\r
 539 \end{algorithmic}\r
 540 \end{varwidth}% \r
 541 }\r
 542 \r
 543 % Create Collision\r
 544 \noindent\fbox{%\r
 545 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 546 \textbf{Create ColRes:}\\\r
 547 Generate a colres data entry.\\\r
 548 \begin{algorithmic}[1]\r
 549 \Function{CreateColRes}{$is_a, seq_{a_{old}}, seq_{a_{new}}, isequal_a$}\r
 550     \State \Return{$\tuple{id_a, seq_{a_{old}}, seq_{a_{new}},}isequal_a$}\r
 551 \EndFunction\r
 552 \end{algorithmic}\r
 553 \end{varwidth}% \r
 554 }\r
 555 \r
 556 \r
 557 % Create Transaction\r
 558 \noindent\fbox{%\r
 559 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 560 \textbf{Create Transaction:}\\\r
 561 Generate a transaction data entry.\\\r
 562 \begin{algorithmic}[1]\r
 563 \Function{CreateTrans}{$pendingtrans_a, seq_a$}\r
 564     \State $\tuple{KV_a, Guard_a} \gets pendingtrans_a$\r
 565     \State \Return{$\tuple{seq_a, LOCAL\_ID, KV_a, Guard_a}$}    \r
 566 \EndFunction\r
 567 \end{algorithmic}\r
 568 \end{varwidth}% \r
 569 }\r
 570 \r
 571 % Create Commit\r
 572 \noindent\fbox{%\r
 573 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 574 \textbf{Create Commit:}\\\r
 575 Generate a commit data entry.\\\r
 576 \begin{algorithmic}[1]\r
 577 \Function{CreateCommit}{$seq_a,KV_a$}\r
 578     \State \Return{$\tuple{seq_a,KV_a}$}\r
 579 \EndFunction\r
 580 \end{algorithmic}\r
 581 \end{varwidth}% \r
 582 }\r
 583 \r
 584 % Create New Key\r
 585 \noindent\fbox{%\r
 586 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 587 \textbf{Create New Key:}\\\r
 588 Generate a new key data entry.\\\r
 589 \begin{algorithmic}[1]\r
 590 \Function{CreateNewKey}{$k_a, id_a$}\r
 591     \State \Return{$\tuple{k_a,id_a}$}\r
 592 \EndFunction\r
 593 \end{algorithmic}\r
 594 \end{varwidth}% \r
 595 }\r
 596 \r
 597 % Data Entry Set Has Space \r
 598 \noindent\fbox{%\r
 599 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 600 \textbf{Data Entry Set Has Space :}\\\r
 601 Checks if a data entry set has enough space for a new data entry to be inserted.\\\r
 602 \begin{algorithmic}[1]\r
 603 \Function{DEHasSpace}{$DE_a, de_a$}\r
 604     \State $newsize \gets $ \Call{GetSize}{$DE_a$}\r
 605     \State $newsize \gets newsize +$ \Call{GetSize}{$de_a$}\r
 606     \State \Return{$newsize \leq DATA\_ENTRY\_SET\_MAX\_SIZE$}\r
 607 \EndFunction\r
 608 \end{algorithmic}\r
 609 \end{varwidth}% \r
 610 }\r
 611 \r
 612 % Create Rescued Commit\r
 613 \noindent\fbox{%\r
 614 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 615 \textbf{Create Rescued Date Entry:}\\\r
 616 For commits only the key-value pairs that are most recent (no newer commit that has those key values in it).\\\r
 617 \begin{algorithmic}[1]\r
 618 \Function{CreateRescuedCommit}{$commit_a$}\r
 619     \State $AllCommits \gets $ \Call{GetCommits}{}\r
 620     \State $\tuple{seq_{a_{trans}},KV_a} \gets de_a$\r
 621     \State $NewKV \gets KV_a$\\\r
 622 \r
 623     \LeftComment{Get rid of all key values that have newer commits}\r
 624     \ForAll{$\tuple{k_a, v_a} \in KV_a$}\r
 625         \LeftComment{Iterate over all commits that are newer than the rescue commit}\r
 626         \ForAll{$\tuple{seq', KV'} \in AllCommits, seq' > seq_{a_{trans}}$}\r
 627             \If{$\exists \tuple{k', v'} \in KV', k' = k_a$}\r
 628                 \State $NewKV \gets NewKV \setminus \tuple{k_a, v_a}$\r
 629                 \State Break\r
 630             \EndIf\r
 631         \EndFor\r
 632     \EndFor\r
 633     \State \Return{$\tuple{seq_{a_{trans}}, NewKV}$}\r
 634 \EndFunction\r
 635 \end{algorithmic}\r
 636 \end{varwidth}% \r
 637 }\r
 638 \r
 639 % Create Rescued Date Entry\r
 640 \noindent\fbox{%\r
 641 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 642 \textbf{Create Rescued Date Entry:}\\\r
 643 Generate the data entry rescued version of the entry.  For some data entry types such as commits, the entry is not rescued as is.  For commits only the key-value pairs that are most recent (no newer commit that has those key values in it).\\\r
 644 \begin{algorithmic}[1]\r
 645 \Function{CreateRescuedEntry}{$de_a$}\r
 646 \r
 647     \If{$de_a$is a $commit$}\r
 648         \State \Return{\Call{CreateRescuedCommit}{$de_a$}}\r
 649     \EndIf\r
 650     \r
 651     \State \Return{$de_a$} \Comment{No Modification needed}\r
 652 \EndFunction\r
 653 \end{algorithmic}\r
 654 \end{varwidth}% \r
 655 }\r
 656 \r
 657 % Check Slot Hmacs\r
 658 \noindent\fbox{%\r
 659 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 660 \textbf{Check Slot HMACs:}\\\r
 661 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
 662 \begin{algorithmic}[1]\r
 663 \Function{CheckSlotsHmacAndSeq}{$Slots_a$}\r
 664     \ForAll{$slot_a \in Slots_a$}\r
 665         \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets slot_a$\r
 666         \State $calchmac \gets $ \Call{GenerateHmac}{$seq_{a_2}, id_a, DE_a, hmac_{a_p}$}\r
 667     \r
 668         \If{$seq_{a_1} \neq seq_{a_2}$}\r
 669           \State \Call{Error}{"Slot sequence number mismatch"}\r
 670         \ElsIf{$calchmac \neq hmac_{a_c}$}\r
 671             \State \Call{Error}{"Slot HMAC mismatch"}\r
 672         \EndIf\r
 673     \EndFor\r
 674 \EndFunction\r
 675 \end{algorithmic}\r
 676 \end{varwidth}% \r
 677 }\r
 678 \r
 679 % Check HMAC Chain\r
 680 \noindent\fbox{%\r
 681 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 682 \textbf{Check HMAC Chain:}\\\r
 683 Check that the HMAC chain has not been violated.\\\r
 684 \begin{algorithmic}[1]\r
 685 \Function{CheckHmacChain}{$Slots_a$}\r
 686     \State $SlotsList \gets Slots_a$ sorted by sequence number\\  \r
 687     \r
 688     \r
 689     \LeftComment{Check all new slots}\r
 690     \ForAll{$index \in [2: |SlotsList|]$}\r
 691         \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets SlotList[i-1]$\r
 692         \State $\tuple{seq_{b_1}, \tuple{seq_{b_2},id_b,DE_b,hmac_{b_p},hmac_{b_c}}} \gets SlotList[i]$\r
 693         \r
 694         \If{$hmac_{b_p} \neq hmac_{b_c}$}\r
 695             \State \Call{Error}{"Invalid previous HMAC."}\r
 696         \EndIf    \r
 697     \EndFor\\\r
 698     \r
 699     \LeftComment{Check against slots that we already have in the block chain}\r
 700     \If{$|LocalSlots| \neq 0$}\r
 701         \State $\tuple{seq, SDE} \gets $\Call{MaxSlot}{$LocalSlots$}\r
 702         \State $\tuple{seq{last_2},id_{last},DE_{last},hmac_{last_p},hmac_{last_c}} \gets SDE$\\\r
 703         \r
 704         \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets SlotList[1]$\\\r
 705 \r
 706         \If{$(seq_{last_2} + 1) = seq_{a_1}$}\r
 707             \If{$hmac_{a_p} \neq hmac_{last_c}$}\r
 708                 \State \Call{Error}{"Invalid previous HMAC."}\r
 709             \EndIf\r
 710         \EndIf\r
 711     \EndIf\r
 712     \r
 713 \EndFunction\r
 714 \end{algorithmic}\r
 715 \end{varwidth}% \r
 716 }\r
 717 \r
 718 \r
 719 % Check For Old Slots\r
 720 \noindent\fbox{%\r
 721 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 722 \textbf{Check For Old Slots:}\\\r
 723 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
 724 \begin{algorithmic}[1]\r
 725 \Function{CheckOldSlots}{$Slots_a$}\r
 726     \State $\tuple{seq_{new}, Dat_{new}} \gets$ \Call{MinSlot }{$Slots_a$} \Comment{Get the oldest new slot}\r
 727     \State $\tuple{seq_{local}, Dat_{local}} \gets$ \Call{MaxSlot }{$LocalSlots$} \Comment{Get the newest slot seen}\\\r
 728     \r
 729     \If{$seq_{new} \leq seq_{local}$} \Comment{The slots were not newer than what was already seen}\r
 730         \State \Call{Error}{"Server sent old slots."}\r
 731     \EndIf\\\r
 732     \r
 733     \LeftComment{Check if slots have the same sequence number but different data entries}\r
 734     \ForAll{$\tuple{seq, Dat} \in Slots_a$}\r
 735         \If{$\exists \tuple{seq', Dat'} \in (LocalSlots \cup Slots_a), seq'=seq \land Dat' \neq Dat$}\r
 736             \State \Call{Error}{"Slot sequence number match but data does not"}\r
 737         \EndIf\r
 738     \EndFor\r
 739     \r
 740 \EndFunction\r
 741 \end{algorithmic}\r
 742 \end{varwidth}% \r
 743 }\r
 744 \r
 745 % Get All Queue States with Sequence numbers\r
 746 % \noindent\fbox{%\r
 747 % \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 748 % \textbf{Get All Queue States with Sequence numbers:}\\\r
 749 % Gets all the queue states with the sequence number of the slot that the queue state was inside.\r
 750 % \begin{algorithmic}[1]\r
 751 % \Function{GetQStateWithSeq}{$Slots_a$}\r
 752 %     \State $QSet \gets \emptyset$\\\r
 753     \r
 754 %     \ForAll{$\tuple{seq_1', \tuple{seq_2',id',DE',hmac_p', hmac_c'}} \in Slots_a$}\r
 755 %         \ForAll{$de' \in DE'$}\r
 756 %             \If{$de'$ is a  $qstate$}\r
 757 %                 \State $QSet \gets QSet \cup \{\tuple{seq_1', de'}\}$\r
 758 %             \EndIf\r
 759 %         \EndFor\r
 760 %     \EndFor\\\r
 761     \r
 762 %     \State \Return{$QSet$}\r
 763 % \EndFunction\r
 764 % \end{algorithmic}\r
 765 % \end{varwidth}% \r
 766 % }\r
 767 \r
 768 % Get All Queue States\r
 769 \noindent\fbox{%\r
 770 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 771 \textbf{Get All Queue States:}\\\r
 772 Gets all the queue states from the slots that were passed in.\\\r
 773 \begin{algorithmic}[1]\r
 774 \Function{GetQState}{$Slots_a$}\r
 775     \State $QSet \gets \emptyset$\\\r
 776     \r
 777     \ForAll{$\tuple{seq_1', \tuple{seq_2',id',DE',hmac_p', hmac_c'}} \in Slots_a$}\r
 778         \ForAll{$de' \in DE'$}\r
 779             \If{$de'$ is a  $qstate$}\r
 780                 \State $QSet \gets QSet \cup \{de'\}$\r
 781             \EndIf\r
 782         \EndFor\r
 783     \EndFor\\\r
 784     \r
 785     \State \Return{$QSet$}\r
 786 \EndFunction\r
 787 \end{algorithmic}\r
 788 \end{varwidth}% \r
 789 }\r
 790 \r
 791 \r
 792 % Check Size With Gap\r
 793 \noindent\fbox{%\r
 794 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 795 \textbf{Check Size With Gap:}\\\r
 796 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
 797 \begin{algorithmic}[1]\r
 798 \Function{CheckSizeWithGap}{$Slots_a$}    \r
 799     %\State $QSSet \gets $ \Call{GetQStateWithSeq}{$Slots_a$}\r
 800     %\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
 801     %\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
 802     \r
 803     \State $QSet \gets $ \Call{GetQState}{$Slots_a$}\r
 804     \State $size_{max} \gets size$ such that $size \in QSet \land \forall size' \in QSet, size \geq size'$ \r
 805     \State $size_{min} \gets size$ such that $size \in QSet \land \forall size' \in QSet, size \leq size'$     \r
 806     \State $Slots_{oldmax} \gets \emptyset$\\\r
 807 \r
 808     \r
 809     \LeftComment{If only 1 max size then we must have all the slots for that size}\r
 810     \If{$(|QSSet| = 1) \land (|Slots_a| \neq size_{max})$}\r
 811         \State \Call{Error}{"Missing Slots"}\r
 812     \EndIf\\\r
 813     \r
 814     \LeftComment{We definitely have all the slots}\r
 815     \If$|Slots_a| = size_{max}$\r
 816         \State \Return{} \Comment{We have all the slots}\r
 817     \EndIf\\\r
 818     \r
 819     \LeftComment{We must have at least this many slots}\r
 820     \If$|Slots_a| < size_{min}$\r
 821         \State \Call{Error}{"Missing Slots"}\r
 822     \EndIf\\\r
 823 \r
 824 \EndFunction\r
 825 \end{algorithmic}\r
 826 \end{varwidth}% \r
 827 }\r
 828 \r
 829 % Check Size\r
 830 \noindent\fbox{%\r
 831 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 832 \textbf{Check Size:}\\\r
 833 \begin{algorithmic}[1]\r
 834 \Function{CheckSize}{$Slots_a$}    \r
 835     \State $\tuple{seq_{old_{max}}, Dat_{old_{max}}} \gets $ \Call{MaxSlot}{$LocalSlots$}\r
 836     \State $\tuple{seq_{new_{max}}, Dat_{new_{max}}} \gets $ \Call{MinSlot}{$Slots_a$}\\\r
 837     \r
 838     \If{$(seq_{old_{max}} + 1) = seq_{new_{max}}$}\r
 839         \LeftComment{No Gap so cannot say anything about the size}\r
 840         \State \Return{} \r
 841     \Else \r
 842         \LeftComment{Has a gap so we need to do checks}\r
 843         \State \Call{CheckSizeWithGap}{$Slots_a$}\r
 844     \EndIf\r
 845 \EndFunction\r
 846 \end{algorithmic}\r
 847 \end{varwidth}% \r
 848 }\r
 849 \r
 850 \r
 851 % % Initialize the expected size of the block chain\r
 852 % \noindent\fbox{%\r
 853 % \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 854 % \textbf{Initialize the expected size of the block chain:}\\\r
 855 % Initialize the expected size of the block chain based on the size at the server.\\\r
 856 % \begin{algorithmic}[1]\r
 857 % \Function{InitExpSize}{$seq_a$}\r
 858 %     \State $startingsize \gets 0$\\\r
 859 \r
 860 %     \If{$seq_a < max\_size$} \Comment{Check whether saves slots are full on server}\r
 861 %         \State $startingsize \gets seq_a$\r
 862 %     \Else\r
 863 %         \State $startingsize \gets max\_size$\r
 864 %     \EndIf\\\r
 865     \r
 866 %     \State \Return{$startingsize$}\r
 867 % \EndFunction\r
 868 % \end{algorithmic}\r
 869 % \end{varwidth}% \r
 870 % }\r
 871 \r
 872 % % Update the expected size of the block chain\r
 873 % \noindent\fbox{%\r
 874 % \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 875 % \textbf{Update the expected size of the block chain:}\\\r
 876 % Update the expected size of the block chain.\\\r
 877 % \begin{algorithmic}[1]\r
 878 % \Function{UpdateExpSize}{$size_a$}\r
 879 %     \State $size_a \gets size_a + 1$\\\r
 880     \r
 881 %     \If{$size_a > max\_size$}\Comment{Expected size $\leq max\_size$}\r
 882 %         \State $ssize_a \gets max_\_size$\r
 883 %     \EndIf\\\r
 884     \r
 885 %     \State \Return{$size_a$}\r
 886 % \EndFunction\r
 887 % \end{algorithmic}\r
 888 % \end{varwidth}% \r
 889 % }\r
 890 \r
 891 \r
 892 \r
 893 % Update Last Message\r
 894 \noindent\fbox{%\r
 895 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 896 \textbf{Process Commit Data Entry:}\\\r
 897 Process a commit entry.  Updates the local copy of commits.\\\r
 898 \begin{algorithmic}[1]\r
 899 \Function{UpdateLastMessage}{$seq_a, id_a, LstSlt_a, updateinglocal_a$}\r
 900     \State $\tuple{id_{old}, seq_{old}} \gets \tuple{id', seq'}$ such that $\tuple{id', seq'} \in LastSlot \land id'=id$\\\r
 901     \r
 902     \If{$id_a = LOCAL\_ID$}\r
 903         \If{$\lnot updateinglocal_a \land (seq_a \neq seq_{old})$}\r
 904             \LeftComment{This client did not make any updates so its latest sequence number should not change}\r
 905             \State \Call{Error}{"Mismatch on local machine sequence number"}\r
 906         \EndIf\r
 907     \Else\r
 908         \If{$seq_{old} > seq_a$}\r
 909             \State \Call{Error}{"Rollback on remote machine sequence number"}\r
 910         \EndIf\r
 911     \EndIf\\\r
 912     \r
 913     \State $LastSlot \gets LastSlot \setminus \{\tuple{id, seq} | \tuple{id, seq} \in LastSlot, id=id_a\}$\r
 914     \State $LastSlot \gets LastSlot \cup \{\tuple{id_a, seq_a}\}$\r
 915     \r
 916     \State \Return{$LstSlt_a \setminus \{\tuple{id, seq} | \tuple{id, seq} \in LstSlt_a, id=id_a\}$}\r
 917 \EndFunction\r
 918 \end{algorithmic}\r
 919 \end{varwidth}% \r
 920 }\r
 921 \r
 922 % Process Commit Data Entry\r
 923 \noindent\fbox{%\r
 924 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 925 \textbf{Process Commit Data Entry:}\\\r
 926 Process a commit entry.  Updates the local copy of commits.\\\r
 927 \begin{algorithmic}[1]\r
 928 \Function{ProcessCommit}{$commit_a$}\r
 929     \State $\tuple{seq_{a_{trans}},KV_a} \gets commit_a$\r
 930     \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CommittedKV \land \tuple{k',v'}\in KV_a \land k'=k\}$\r
 931     \State $CommittedKV \gets (CommittedKV \setminus DKV) \cup KV_a$\r
 932 \EndFunction\r
 933 \end{algorithmic}\r
 934 \end{varwidth}% \r
 935 }\r
 936 \r
 937 % Process Queue State Data Entry\r
 938 \noindent\fbox{%\r
 939 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 940 \textbf{Process Queue State Entry:}\\\r
 941 Process a queue state entry. Updates the max size of the block chain\\\r
 942 \begin{algorithmic}[1]\r
 943 \Function{ProcessQState}{$qstate_a$}\r
 944     \State $\tuple{size_a} \gets qstate_a$\r
 945     \State $max\_size \gets size_a$ \Comment{Update the max size we can have}\r
 946 \EndFunction\r
 947 \end{algorithmic}\r
 948 \end{varwidth}% \r
 949 }\r
 950 \r
 951 % Process Collision Resolution Entry\r
 952 \noindent\fbox{%\r
 953 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 954 \textbf{Process Queue State Entry:}\\\r
 955 Process a collision resolution entry.\\\r
 956 \begin{algorithmic}[1]\r
 957 \Function{ProcessColres}{$colres_a, NewSlots_a$}\r
 958     \State $\tuple{id_a, seq_{a_{old}}, seq_{a_{new}}, isequal_a}$\r
 959     \State $AllSlots \gets LocalSlots \cup NewSlots_a$\r
 960     \State $index \gets seq_{a_{old}}$\\\r
 961     \r
 962     \While{$index <= seq_{a_{new}}$}\r
 963         \State $slt \gets \tuple{seq' Dat'}$ such that $\tuple{seq' Dat'} \in AllSlots \land seq'=index$\r
 964         \r
 965         \If{$\exists \tuple{seq' Dat'} \in AllSlots, seq' = index$}\r
 966             \State $\tuple{seq, Dat} \gets \tuple{seq' Dat'}$ such that $\tuple{seq' Dat'} \in AllSlots \land seq'=index$\r
 967             \State $\tuple{seq,id,DE,hmac_p,hmac_c} \gets Dat$\r
 968             \If{$isequal_a \neq (id=id_a)$}\r
 969                 \State \Call{Error}{"Trying to insert rejected messages for slot"}\r
 970             \EndIf\r
 971         \EndIf\\\r
 972         \State $index \gets index + 1$\r
 973     \EndWhile\r
 974     \r
 975     \r
 976 \EndFunction\r
 977 \end{algorithmic}\r
 978 \end{varwidth}% \r
 979 }\r
 980 \r
 981 % Process New Key Data Entry\r
 982 \noindent\fbox{%\r
 983 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 984 \textbf{Process New Key Entry:}\\\r
 985 Process a queue state entry. Adds a key to the key arbitrator set\\\r
 986 \begin{algorithmic}[1]\r
 987 \Function{ProcessNewkey}{$newkey_a$}\r
 988     \State $\tuple{seq_a, k_a, id_a} \gets newkey_a$\r
 989     \State $Arbitrator \gets Arbitrator \cup \{\tuple{k_a,id_a}\}$\r
 990 \EndFunction\r
 991 \end{algorithmic}\r
 992 \end{varwidth}% \r
 993 }\r
 994 \r
 995 % Process Process Data Entry\r
 996 \noindent\fbox{%\r
 997 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 998 \textbf{Process Data Entry:}\\\r
 999 Process the data entry based on what kind of entry it is.\\\r
1000 \begin{algorithmic}[1]\r
1001 \Function{ProcessDatEntry}{$slot_a, NewSlots_a,LstSlt_a$}\r
1002     \If{$datentry_a$ is a $commit$}\r
1003         \State \Call{ProcessCommit}{$dataentry_a$}\r
1004         \r
1005     \ElsIf{$datentry_a$ is a $abort$}\r
1006         \LeftComment{Do Nothing in this case}\r
1007         \r
1008     \ElsIf{$datentry_a$ is a $trans$}\r
1009         \LeftComment{Do Nothing in this case}\r
1010     \r
1011     \ElsIf{$datentry_a$ is a $lastmsg$}\r
1012         \State $\tuple{seq_a, id_a} \gets dataentry_a$\r
1013         \State $LstSlt_a \gets$ \Call{UpdateLastMessage}{$seq_a, id_a, LstSlt_a, false$}\r
1014     \r
1015     \ElsIf{$datentry_a$ is a $colres$}\r
1016         \State \Call{ProcessColres}{$dataentry_a, NewSlots_a$}\r
1017         \r
1018     \ElsIf{$datentry_a$ is a $qstate$}\r
1019         \State \Call{ProcessQState}{$dataentry_a$}\r
1020         \r
1021     \ElsIf{$datentry_a$ is a $newkey$}\r
1022         \State \Call{ProcessNewkey}{$dataentry_a$}\r
1023         \r
1024     \Else\r
1025         \State \Call{Error}{"Unknown data entry type."}\r
1026     \EndIf\r
1027     \r
1028     \State \Return{$LstSlt_a$}    \r
1029 \EndFunction\r
1030 \end{algorithmic}\r
1031 \end{varwidth}% \r
1032 }\r
1033 \r
1034 \r
1035 % Delete Local Slots\r
1036 \noindent\fbox{%\r
1037 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1038 \textbf{Delete Local Slots:}\\\r
1039 Deletes local slots that are deleted at the server.  This keeps the size of the local block chain bounded.\\\r
1040 \begin{algorithmic}[1]\r
1041 \Function{DeleteLocalSlots}{$ $}\r
1042     \State $\tuple{seq_{max}, Dat_{max}} \gets $ \Call{MaxSlot}{$LocalSlots$}\r
1043     \State $seq_{min} \gets seq_{max} - max\_size$ \Comment{Min sequence number we should keep}\r
1044     \State $LSDelete \gets \emptyset$\r
1045         \r
1046     \If{$|LocalSlots| \leq max\_size$}\r
1047         \State \Return{} \Comment{Nothing to delete}\r
1048     \EndIf\\\r
1049     \r
1050     \State $LSDelete \gets \{\tuple{seq', Dat'}|\tuple{seq', Dat'} \in LocalSlots, seq' > seq_{min}\}$\r
1051     \State $LocalSlots \gets LocalSlots \setminus LSDelete$    \r
1052 \EndFunction\r
1053 \end{algorithmic}\r
1054 \end{varwidth}% \r
1055 }\r
1056 \r
1057 % Create Speculative KV\r
1058 \noindent\fbox{%\r
1059 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1060 \textbf{Create Speculative KV:}\\\r
1061 Speculates on what the most recent key value pairs will be based on the latest committed key value pairs and the uncommitted transactions.\\\r
1062 \begin{algorithmic}[1]\r
1063 \Function{SpeculateKV}{$ $}\r
1064     \State $AllTrans \gets$ \Call{GetTrans}{}\r
1065     \State $LiveTrans \gets \{t| t\in AllTrans, $\Call{CheckTransLive}{$t$}$\}$\r
1066     \State $CurrKV \gets CommittedKV$\r
1067     \State $DKV \gets \emptyset$\r
1068 \r
1069     \ForAll{$\tuple{seq_t, id_t, KV_t, Guard_t} \in LiveTrans$ ordered by $seq'$} \r
1070         \If{\Call{EvaluateGuard}{$Guard_t, CurrKV$}}\r
1071             \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CurrKV \land \tuple{k',v'}\in KV_t \land k'=k\}$\r
1072             \State $CurrKV \gets (CurrKV \setminus DKV) \cup KV_t$\r
1073         \EndIf\r
1074     \EndFor\r
1075     \r
1076     \State \Return{$CurrKV$}\r
1077 \EndFunction\r
1078 \end{algorithmic}\r
1079 \end{varwidth}% \r
1080 }\r
1081 \r
1082 \r
1083 % Validate and Update \r
1084 \noindent\fbox{%\r
1085 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1086 \textbf{Validate Update:}\\\r
1087 Validate the block chain and insert into the local block chain.\\\r
1088 \begin{algorithmic}[1]\r
1089 \Function{ValidateUpdate}{$NewSlots_a, updatinglocal_a$}\r
1090     \State $\tuple{seq_{oldest}, Dat_{oldest}} \gets$ \Call{MinSlot}{$NewSlots_a$}\r
1091     \State $\tuple{seq_{newest}, Dat_{newest}} \gets$ \Call{MaxSlot}{$NewSlots_a$}\r
1092     \State $\tuple{seq_{local}, Dat_{local}} \gets$ \Call{MaxSlot}{$LocalSlots$}\r
1093     \State $LastSlotTmp \gets LastSlot$\\\r
1094     %\State $currsize \gets $\Call{InitExpSize}{$seq_{oldest}$}\\\r
1095     \r
1096     \State \Call{CheckSlotsHmacAndSeq}{$NewSlots_a$} \Comment{Check all the HMACs}\r
1097     \State \Call{CheckHmacChain}{$NewSlots_a$} \Comment{Check HMAC Chain} \r
1098     \State \Call{CheckOldSlots}{$NewSlots_a$} \Comment{Check if new slots are actually old slots} \r
1099     \State \Call{CheckSize}{$NewSlots_a$} \Comment{Check if the size is correct}\\\r
1100     \r
1101     \ForAll{$slot_a \in NewSlots_a$ in order of sequence number}\r
1102         \If{$slot_a \in LocalSlots$} \Comment{Client already has this slot}\r
1103             \State $NewSlots_a \gets NewSlots_a \setminus \{slot_a\}$\r
1104             \State Continue\r
1105         \EndIf\\\r
1106     \r
1107         \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets slot_a$\r
1108         \State $LstSlt_a \gets$ \Call{UpdateLastMessage}{$seq_{a_1}, id_a, LstSlt_a, updatinglocal_a$}\\\r
1109         \r
1110         \ForAll{$de_a \in DE_a$} \Comment{Process each data entry}\r
1111             \State $LstSlt_a \gets $ \Call{ProccessDatEntry}{$de_a, NewSlots_a,LstSlt_a$}\r
1112         \EndFor\\\r
1113     \r
1114         %\State $currsize \gets $ \Call{UpdateExpSize}{$currsize$}\\\r
1115         \State $LocalSlots \gets LocalSlots \cup \{slot_a\}$ \Comment{Add to local Chain}\r
1116     \EndFor\\\r
1117     \r
1118     \If{$seq_{oldest} > (seq_{local} +1) \land LastSlotTmp \neq \emptyset$}\r
1119         \LeftComment{There was a gap so there should be a complete set of information on each previously seen client}\r
1120         \State \Call{Error}{"Missing records for machines"}\r
1121     \EndIf\\\r
1122     \r
1123     \State \Call{DeleteLocalSlots}{ } \Comment{Delete old slots from local}\r
1124     \State $SpeculatedKV \gets $\Call{SpeculateKV}{ } \Comment{Speculate on what will be latest KV set}\r
1125     \r
1126 \EndFunction\r
1127 \end{algorithmic}\r
1128 \end{varwidth}% \r
1129 }\r
1130 \r
1131 % Decrypt Validate Insert Slots\r
1132 \noindent\fbox{%\r
1133 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1134 \textbf{Decrypt Validate Insert Slots:}\\\r
1135 Decrypts slots, validates (checks for malicious activity) slots and inserts the slots into the local block chain.\\\r
1136 \begin{algorithmic}[1]\r
1137 \Function{DecryptValidateInsert}{$NewSlots_a, updatinglocal_a$}\r
1138     \State $DecryptedSlots \gets \emptyset$\r
1139     \State $DDat \gets NULL$\\\r
1140     \r
1141     \ForAll{$\tuple{seq', EDat'} \in NewSlots_a$}\r
1142         \State $DDat \gets $ \Call{Decrypt}{$EDat'$}\r
1143         \State $DecryptedSlots \gets DecryptedSlots \cup \tuple{seq',DDat}$\r
1144     \EndFor\\\r
1145     \State \Call{ValidateUpdate}{$DecryptedSlots, updatinglocal_a$}\r
1146 \EndFunction\r
1147 \end{algorithmic}\r
1148 \end{varwidth}% \r
1149 }\r
1150 \r
1151 % Check and Create Last Message Data Entry\r
1152 \noindent\fbox{%\r
1153 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1154 \textbf{Check and Create Last Message Data Entry:}\\\r
1155 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
1156 \begin{algorithmic}[1]\r
1157 \Function{CheckCreateLastMsgEntry}{$seq_a, id_a$}\r
1158     \State $AllLastMsg \gets$ \Call{GetLastMsg}{}\\\r
1159     \r
1160     \LeftComment{Already Has one}\r
1161     \If{$\exists  \tuple{seq', id'} \in AllLastMsg, id_a=id' \land seq'=seq_a$}\r
1162         \State \Return{$\{\}$}\\\r
1163     \EndIf\\\r
1164     \r
1165     \LeftComment{Not latest slot from that client}\r
1166     \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
1167         \State \Return{$\{\}$}\\\r
1168     \EndIf\\\r
1169     \r
1170     \r
1171     \State \Return{$\{\tuple{seq_a, id_a}\}$}\r
1172 \EndFunction\r
1173 \end{algorithmic}\r
1174 \end{varwidth}% \r
1175 }\r
1176 \r
1177 % Mandatory Rescue\r
1178 \noindent\fbox{%\r
1179 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1180 \textbf{Mandatory Rescue:}\\\r
1181 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
1182 \begin{algorithmic}[1]\r
1183 \Function{MandatoryRescue}{$DE_a$}\r
1184     \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
1185     \State $cseq \gets smallestseq$\\\r
1186     \r
1187     \LeftComment{Check the least slots to rescue and live entries}\r
1188     \While{$cseq < (smallestseq + DEAD\_SLOT\_COUNT)$}\r
1189         \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
1190         \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\r
1191         \State $DE' \gets DE' \cup$ \Call{CheckCreateLastMsgEntry}{$seq', id'$} \Comment{Get the last message too if we need it}\\\r
1192         \r
1193         \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
1194             \If{\Call{CheckLive}{$de, cseq$}} \Comment{data entry is live}\r
1195                 \State $de \gets $ \Call{CreateRescuedEntry}{de} \Comment{Resize entry if needed}\r
1196                 \If{\Call{DEHasSpace}{$DE_a, de$}}\r
1197                     \State $DE_a \gets DE_a \cup de$ \Comment{Had enough space to add it}\r
1198                 \ElsIf{$currentseq = smallestseq$}\r
1199                     \State \Return{$NULL$}\r
1200                 \Else\r
1201                     \State \Return{$DE_a$}\r
1202                 \EndIf\r
1203             \EndIf\r
1204         \EndFor\\\r
1205         \r
1206         \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
1207     \EndWhile\r
1208     \r
1209     \State \Return{$DE_a$}\r
1210 \EndFunction\r
1211 \end{algorithmic}\r
1212 \end{varwidth}% \r
1213 }\r
1214 \r
1215 % Optional Rescue\r
1216 \noindent\fbox{%\r
1217 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1218 \textbf{Optional Rescue:}\\\r
1219 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
1220 \begin{algorithmic}[1]\r
1221 \Function{OptionalRescue}{$DE_a$}\r
1222     \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
1223     \State $largestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \geq seq')$\r
1224 \r
1225     \State $numofskips \gets 0$\r
1226     \State $cseq \gets smallestseq$\\\r
1227     \r
1228     \LeftComment{Check the least slots to rescue and live entries}\r
1229     \While{$cseq < largestseq$}\r
1230         \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
1231         \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\\\r
1232         \r
1233         \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
1234             \If{\Call{CheckLive}{$de, cseq$}} \Comment{data entry is live}\r
1235                 \State $de \gets $ \Call{CreateRescuedEntry}{de} \Comment{Resize entry if needed}\\\r
1236                 \r
1237                 \If{$de \in DE_a$} \Comment{Already being rescued}\r
1238                     \State Continue\r
1239                 \EndIf\\\r
1240                 \r
1241                 \If{\Call{DEHasSpace}{$DE_a, de$}}\r
1242                     \State $DE_a \gets DE_a \cup de$ \Comment{Had enoug space to add it}\r
1243                 \ElsIf{$numofskips \geq MAX\_RESCUE\_SKIPS$}\r
1244                     \State \Return{$DE_a$}\r
1245                 \Else\r
1246                     $numofskips \gets numofskips +1$\r
1247                 \EndIf\r
1248             \EndIf\r
1249         \EndFor\\\r
1250         \r
1251         \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
1252     \EndWhile\r
1253     \r
1254     \State \Return{$DE_a$}\r
1255 \EndFunction\r
1256 \end{algorithmic}\r
1257 \end{varwidth}% \r
1258 }\r
1259 \r
1260 \r
1261 % Rejected Messages\r
1262 \noindent\fbox{%\r
1263 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1264 \textbf{Rejected Messages:}\\\r
1265 \begin{algorithmic}[1]\r
1266 \Function{RejectedMessages}{$DE_a$}\r
1267     \State $seq_{old} \gets seq$ such that $\tuple{seq} \in RejectedSlotList \land \forall \tuple{seq'} \in RejectedSlotList, seq \geq seq'$\r
1268     \State $prev \gets -1$\\\r
1269     \r
1270     \r
1271     \r
1272     \If{$|RejectedSlotList| \geq REJECTED\_THRESH$}\r
1273         \State $seq_{new} \gets seq$ such that $\tuple{seq} \in RejectedSlotList \land \forall \tuple{seq'} \in RejectedSlotList, seq \leq seq'$\\\r
1274         \State $colres \gets $ \Call{CreateColRes}{$LOCAL\_ID, seq_{old}, seq_{new}, false$}    \r
1275         \State \Return{$DE_a \cup \{colres\}$}\r
1276     \EndIf\\\r
1277     \r
1278     \ForAll{$\tuple{seq} \in RejectedSlotList$ sorted by $seq$}\r
1279         \If{$\exists \tuple{seq',Dat'} \in LocalSlots$}\r
1280             \State Break\r
1281         \EndIf\r
1282         \State $prev \gets seq$\r
1283     \EndFor\\\r
1284     \r
1285     \If{$prev \neq -1$}\r
1286         \State $DE_a \gets DE_a \cup$ \Call{CreateColRes}{$LOCAL\_ID, seq_{old}, prev, false$}\r
1287     \EndIf\\\r
1288     \r
1289     \State $RejectedSlotList \gets \{\tuple{seq}| \tuple{seq} \in RejectedSlotList, seq > prev\}$\\\r
1290     \r
1291     \ForAll{$\tuple{seq} \in RejectedSlotList$ sorted by $seq$}\r
1292         \State $DE_a \gets DE_a \cup$ \Call{CreateColRes}{$LOCAL\_ID, seq,seq, false$}\r
1293     \EndFor\\\r
1294     \r
1295     \State \Return{$DE_a$}\r
1296 \EndFunction\r
1297 \end{algorithmic}\r
1298 \end{varwidth}% \r
1299 }\r
1300 \r
1301 \r
1302 \r
1303 % Arbitrate\r
1304 \noindent\fbox{%\r
1305 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1306 \textbf{Arbitrate:}\\\r
1307 \begin{algorithmic}[1]\r
1308 \Function{Arbitrate}{$DE_a$}\r
1309     \State $AllCommits \gets$ \Call{GetCommits}{}\r
1310     \State $AllTrans \gets$ \Call{GetTrans}{}\r
1311     \State $LiveCommits \gets \{c| c\in AllCommits, $\Call{CheckCommitLive}{$c$}$\}$\r
1312     \State $LiveTrans \gets \{t| t\in AllTrans, $\Call{CheckTransLive}{$t$}$\}$\r
1313     \State $KV \gets \emptyset$\r
1314     \State $lastcomseq \gets -1$\r
1315     \State $CurrKV \gets \emptyset$\r
1316     \State $DKV \gets \emptyset$\r
1317     \State $KVTmp \gets \emptyset$\\\r
1318     \r
1319     \LeftComment{Get all the latest commits}\r
1320     \ForAll{$\tuple{seq_{trans}',KV'} \in LiveCommits$}\r
1321         \State $CurrKV \gets CurrKV \cup KV'$\r
1322     \EndFor\\\r
1323     \r
1324     \ForAll{$\tuple{seq_t, id_t, KV_t, Guard_t} \in LiveTrans$ ordered by $seq'$} \r
1325         \If{\Call{GetArbitratorKV}{$KV_t$} $\neq LOCAL\_ID$}\r
1326             \State Continue \Comment{Client not arbitrator for this transaction}\r
1327         \EndIf\\\r
1328     \r
1329         \If{$\lnot$\Call{EvaluateGuard}{$Guard_t, CurrKV$}}\r
1330             \State $abortde \gets $\Call{CreateAbort}{$seq_t, id_t$}\r
1331             \LeftComment{No more space so we cant arbitrate any further}\r
1332             \If($lnot$\Call{DeHasSpace}{$DE_a, abortde$})\r
1333                 \State \Return{$DE_a$}\r
1334             \EndIf\r
1335             \State $DE_a \gets DE_a \cup abortde$\r
1336         \Else\r
1337             \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in KV \land \tuple{k',v'}\in KV_t \land k'=k\}$\r
1338             \State $KVTmp \gets (KV \setminus DKV) \cup KV'$\r
1339             \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CurrKV \land \tuple{k',v'}\in KVTmp \land k'=k\}$\r
1340             \State $CurrKV \gets (CurrKV \setminus DKV) \cup KVTmp$\r
1341             \State $commitde \gets $ \Call{CreateCommit}{$seq_t,KVTmp$}\r
1342             \r
1343             \If{$\lnot$ \Call{DeHasSpace}{$DE_a, commitde$}}\r
1344                 \If{$lastcomseq \neq -1$}\r
1345                     \State $DE_a \gets DE_a \cup$ \Call{CreateCommit}{$lastcomseq,KV$}\r
1346                 \EndIf\r
1347                 \State \Return{$DE_a$}\r
1348             \Else\r
1349                 \State $KV \gets KVTmp$\r
1350                 \State $lastcomseq \gets seq_t$\r
1351             \EndIf\r
1352         \EndIf\r
1353     \EndFor\r
1354     \r
1355     \State $DE_a \gets DE_a \cup$ \Call{CreateCommit}{$lastcomseq,KV$}\r
1356     \State \Return{$DE_a$}\r
1357 \r
1358     \r
1359 \EndFunction\r
1360 \end{algorithmic}\r
1361 \end{varwidth}% \r
1362 }\r
1363 \r
1364 % Create New Slot\r
1365 \noindent\fbox{%\r
1366 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1367 \textbf{Create New Slot:}\\\r
1368 Create a slot and encrypt it.\\\r
1369 \begin{algorithmic}[1]\r
1370 \Function{CreateNewSlot}{$seq_a, DE_a$}\r
1371     \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
1372     \State $\tuple{seq,id,DE,hmac_p,hmac_c} \gets SDE$\\\r
1373     \r
1374     \State $newhmac \gets $ \Call{GenerateHmac}{$seq_a, LOCAL\_ID, DE_a, hmac_p$}\r
1375     \State $newSDE \gets \tuple{seq,LOCAL\_ID,DE_a,hmac_c,newhmac}$\r
1376     \State $encryptnewSDE \gets $\Call{Encrypt}{newSDE}\\\r
1377     \r
1378     \State \Return{$\tuple{seq_a, encryptnewSDE}$}\r
1379 \EndFunction\r
1380 \end{algorithmic}\r
1381 \end{varwidth}% \r
1382 }\r
1383 \r
1384 % Send Data to Server\r
1385 \noindent\fbox{%\r
1386 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1387 \textbf{Send Data to Server:}\\\r
1388 Send the data to the server.  If this fails then new slots will be returned by the server.\\\r
1389 \begin{algorithmic}[1]\r
1390 \Function{SendToServer}{$seq_a, DE_a, newsize_a$}\r
1391     \LeftComment{Make the slot and try to send to server}\r
1392     \State $newslot \gets $ \Call{CreateNewSlot}{$seq_a, DE_a$}\r
1393     \State $\tuple{success, newslots} \gets$ \Call{PutSlot}{$seq_a, newslot, newsize_a$}\\\r
1394     \r
1395     \If{$success$}\r
1396         \State $RejectedSlotList \gets \emptyset$\r
1397         \State \Return{$\tuple{true, \{newslot\}}$}\r
1398     \Else\r
1399         \If{$|newslots| = 0$}\r
1400             \State \Call{Error}{"Server rejected but did not send any slots"}\r
1401         \EndIf\r
1402         \State $RejectedSlotList \gets RejectedSlotList \cup \{seq_a\}$\r
1403         \State \Return{$\tuple{false, newslots}$}\r
1404     \EndIf\\\r
1405 \EndFunction\r
1406 \end{algorithmic}\r
1407 \end{varwidth}% \r
1408 }\r
1409 \r
1410 \r
1411 % Try Insert Transaction\r
1412 \noindent\fbox{%\r
1413 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1414 \textbf{Try Insert Transaction:}\\\r
1415 Try to insert a transaction into the block chain. Does resizing, rescues and insertion of other data entry types as needed. \\\r
1416 \begin{algorithmic}[1]\r
1417 \Function{TryInsertTransaction}{$pendingtrans_a, forceresize$}\r
1418     \State $DE \gets \emptyset$ \Comment{The data entries for this slot}\r
1419     \State $seq \gets $ \Call{GetNextSeq}{} \Comment{Get the sequence number for this slot}\r
1420     \State $newsize \gets 0$\r
1421     \State $trans \gets$ \Call{CreateTrans}{$pendingtrans_a, seq$}\r
1422     \State $transinserted \gets false$\r
1423     \State $slotstoinsert \gets \emptyset$\\\r
1424     \r
1425     \State $resize \gets $ \Call{ShouldResize}{ } \Comment{Check if we should resize}\r
1426     \State $resize \gets resize \lor forceresize$\r
1427     \If{$resize$}\r
1428         \State $newsize \gets$ \Call{CalcNewSize}{$max\_size$}\r
1429         \State $DE \gets DE \cup \{$\Call{CreateQState}{$newsize$}$\}$\r
1430     \EndIf\\\r
1431     \r
1432     \If{$RejectedSlotList \neq \emptyset$}   \r
1433         \State $DE \gets$ \Call{RejectedMessages}{$DE$}\r
1434     \EndIf\\\r
1435     \r
1436     \State $DE \gets$ \Call{MandatoryRescue}{$DE$} \Comment{Round 1 of rescue}\r
1437     \If{$DE = NULL$}\r
1438         \LeftComment{Data was going to fall off the end so try again with a forced resize}\r
1439         \State \Return{\Call{TryInsertTransaction}{$trans_a, true$}}\r
1440     \EndIf\\\r
1441     \r
1442     \State $DE \gets $\Call{Arbitrate}{$DE$}\\\r
1443     \r
1444     \If{\Call{DEHasSpace}{$DE, trans$}} \Comment{transaction fits}\r
1445         \State $DE \gets DE \cup trans$\r
1446         \State $transinserted \gets true$\r
1447     \EndIf\\\r
1448     \r
1449     \LeftComment{Rescue data to fill slot data entry section}\r
1450     \State $DE \gets$ \Call{OptionalRescue}{$DE$}\\\r
1451     \r
1452     \LeftComment{Send to server.}\r
1453     \State $\tuple{sendsuccess, newslots} \gets $ \Call{SendToServer}{$seq, DE, newsize$}\\\r
1454     \r
1455     \LeftComment{Insert the slots into the local bloakc chain}\r
1456     \State \Call{DecryptValidateInsert}{$newslots, true$}\\\r
1457     \r
1458     \State \Return{$transinserted \land success$} \Comment{Return if  succeeded or not}\r
1459     \r
1460 \EndFunction\r
1461 \end{algorithmic}\r
1462 \end{varwidth}% \r
1463 }\r
1464 \r
1465 \r
1466 % Try Insert New Key\r
1467 \noindent\fbox{%\r
1468 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1469 \textbf{Try Insert New Key:}\\\r
1470 Try to insert a new key into the block chain. Does resizing, rescues and insertion of other data entry types as needed. \\\r
1471 \begin{algorithmic}[1]\r
1472 \Function{TryInsertNewKey}{$k_a, id_a, forceresize$}\r
1473     \State $DE \gets \emptyset$ \Comment{The data entries for this slot}\r
1474     \State $seq \gets $ \Call{GetNextSeq}{} \Comment{Get the sequence number for this slot}\r
1475     \State $newsize \gets 0$\r
1476     \r
1477     \r
1478     \State $newkey \gets$ \Call{CreateNewKey}{$k_a, id_a$}\r
1479     \State $newkeyinserted \gets false$\r
1480     \State $slotstoinsert \gets \emptyset$\\\r
1481     \r
1482     \State $resize \gets $ \Call{ShouldResize}{ } \Comment{Check if we should resize}\r
1483     \State $resize \gets resize \lor forceresize$\r
1484     \If{$resize$}\r
1485         \State $newsize \gets$ \Call{CalcNewSize}{$max\_size$}\r
1486         \State $DE \gets DE \cup \{$\Call{CreateQState}{$newsize$}$\}$\r
1487     \EndIf\\\r
1488     \r
1489     \If{$RejectedSlotList \neq \emptyset$}   \r
1490         \State $DE \gets$ \Call{RejectedMessages}{$DE$}\r
1491     \EndIf\\\r
1492     \r
1493     \State $DE \gets$ \Call{MandatoryRescue}{$DE$} \Comment{Round 1 of rescue}\r
1494     \If{$DE = NULL$}\r
1495         \LeftComment{Data was going to fall off the end so try again with a forced resize}\r
1496         \State \Return{\Call{TryInsertNewKey}{$k_a, id_a, true$}}\r
1497     \EndIf\\\r
1498     \r
1499     \State $DE \gets $\Call{Arbitrate}{$DE$}\\\r
1500     \r
1501     \If{\Call{DEHasSpace}{$DE, newkey$}} \Comment{new key fits}\r
1502         \State $DE \gets DE \cup newkey$\r
1503         \State $newkeyinserted \gets true$\r
1504     \EndIf\\\r
1505     \r
1506     \LeftComment{Rescue data to fill slot data entry section}\r
1507     \State $DE \gets$ \Call{OptionalRescue}{$DE$}\\\r
1508     \r
1509     \LeftComment{Send to server.}\r
1510     \State $\tuple{sendsuccess, newslots} \gets $ \Call{SendToServer}{$seq, DE, newsize$}\\\r
1511     \r
1512     \LeftComment{Insert the slots into the local block chain}\r
1513     \State \Call{DecryptValidateInsert}{$newslots, true$}\\\r
1514     \r
1515     \State \Return{$newkeyinserted \land success$} \Comment{Return if  succeeded or not}\r
1516     \r
1517 \EndFunction\r
1518 \end{algorithmic}\r
1519 \end{varwidth}% \r
1520 }\r
1521 \r
1522 \r
1523 \r
1524 \subsection{Client Interfaces}\r
1525 \r
1526 % Put KV pair\r
1527 \noindent\fbox{%\r
1528 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1529 \textbf{Put Key Value Pair:}\\\r
1530 Puts a key value pair into the key value pair buffer\\\r
1531 \begin{algorithmic}[1]\r
1532 \Function{PutKeyValue}{$k,v$}\r
1533     \State $\tuple{seq, KV, Guard} \gets PendingTrans$\\\r
1534     \r
1535     \LeftComment{Check if KV already has a key value pair for the specified key}\r
1536     \State $DSet \gets \{\tuple{k_1,v_1} | \tuple{k_1,v_1} \in KV \land k_1 = k\}$\\\r
1537     \r
1538     \If{$DSet \neq \emptyset$}\r
1539         \State \Call{Error}{"Value for key already in most recent update"}\r
1540     \EndIf\\\r
1541         \r
1542     \State $KV \gets KV \cup \{\tuple{k,v}\}$ \Comment{Add key value pair}\r
1543     \State $PendingTrans \gets \tuple{seq, KV, Guard}$\r
1544     \State \Call{CheckArbitrator}{$PendingTrans$} \Comment{Check that the transaction still valid}\r
1545 \EndFunction\r
1546 \end{algorithmic}\r
1547 \end{varwidth}% \r
1548 }\r
1549 \r
1550 % Get KV Pair Speculative\r
1551 \noindent\fbox{%\r
1552 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1553 \textbf{Get KV Pair Speculative:}\\\r
1554 Get the value for the key while speculating.\\\r
1555 \begin{algorithmic}[1]\r
1556 \Function{GetValueSpeculate}{$k_a$}\r
1557     %\State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpeculatedKV \land k = k_a$\r
1558     \State $SpecKVTmp \gets SpeculatedKV$\r
1559     \State $DKV \gets \emptyset$\\\r
1560     \r
1561     \LeftComment{Go Through local pending transactions and speculate}\r
1562     \ForAll{$\tuple{num, \tuple{KV, Guard}} \in PendingTransSet$ sorted by num}\r
1563         \If{\Call{EvaluateGuard}{$Guard, SpecKVTmp$}}\r
1564             \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in SpecKVTmp \land \tuple{k',v'}\in KV \land k'=k\}$\r
1565             \State $SpecKVTmp \gets (SpecKVTmp \setminus DKV) \cup KV$\r
1566         \EndIf\r
1567     \EndFor\r
1568     \r
1569     \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpecKVTmp \land k = k_a$\r
1570 \State \Return{$v$}\r
1571 \EndFunction\r
1572 \end{algorithmic}\r
1573 \end{varwidth}% \r
1574 }\r
1575 \r
1576 % Update\r
1577 \noindent\fbox{%\r
1578 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1579 \textbf{Update}\\\r
1580 Sync with the server and get all the latest slots.\\\r
1581 \begin{algorithmic}[1]\r
1582 \Function{Update}{$ $}\r
1583     \State $\tuple{seq, Dat} \gets $ \Call{MaxSlot}{$LocalSlots$}\r
1584     \State $NewSlots \gets$ \Call{GetSlots}{$seq$}\r
1585     \State \Call{DecryptValidateInsert}{$NewSlots, false$}\r
1586 \EndFunction\r
1587 \end{algorithmic}\r
1588 \end{varwidth}% \r
1589 }\r
1590 \r
1591 % Get KV Pair Committed\r
1592 \noindent\fbox{%\r
1593 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1594 \textbf{Get KV Pair Committed:}\\\r
1595 Get the value for the key which have been committed.\\\r
1596 \begin{algorithmic}[1]\r
1597 \Function{GetValueCommit}{$k_a$}\r
1598     \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in Committed \land k = k_a$\r
1599     \State \Return{$v$}\r
1600 \EndFunction\r
1601 \end{algorithmic}\r
1602 \end{varwidth}% \r
1603 }\r
1604 \r
1605 % Put guard condition\r
1606 \noindent\fbox{%\r
1607 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1608 \textbf{Put Guard:}\\\r
1609 Puts a guard transaction into the key value update.  A guard is a key value with a logical operator ($lop$).\\\r
1610 \begin{algorithmic}[1]\r
1611 \Function{PutGuard}{$k,v, lop$}\r
1612     \State $\tuple{seq, KV, Guard} \gets PendingTrans$\\\r
1613     \r
1614     \If{$\tuple{k,v, lop} \in Guard$}\r
1615         \State \Return{} \Comment{Already have guard condition in update}\r
1616     \EndIf\\\r
1617     \r
1618     \State $Guard \gets Guard \cup \{\tuple{k,v,lop}\}$\r
1619     \State $PendingTrans \gets \tuple{seq, KV, Guard}$\r
1620     \State \Call{CheckArbitrator}{$PendingTrans$} \Comment{Check that the transaction still valid}\r
1621 \EndFunction    \r
1622 \end{algorithmic}\r
1623 \end{varwidth}% \r
1624 }\r
1625 \r
1626 % Transaction Start\r
1627 \noindent\fbox{%\r
1628 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1629 \textbf{ Transaction Start:}\\\r
1630 Starts a transaction.  Clears out the key value pair update buffer.\\\r
1631 \begin{algorithmic}[1]\r
1632 \Function{TransactionStart}{$ $}\r
1633     \LeftComment{Reset the key value update buffer}\r
1634     \State $KVUpdate \gets \tuple{\emptyset, \emptyset}$\r
1635 \EndFunction\r
1636 \end{algorithmic}\r
1637 \end{varwidth}% \r
1638 }\r
1639 \r
1640 % Transaction Commit\r
1641 \noindent\fbox{%\r
1642 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1643 \textbf{ Transaction Commit:}\\\r
1644 Commits the transaction into the block chain.  Keeps attempting to insert the transaction into the block chain until it succeeds.\\\r
1645 \begin{algorithmic}[1]\r
1646 \Function{Transaction Commit}{$ $}\r
1647     \State $num_{largest} \gets 1$\\\r
1648     \If{$PendingTransSet \neq \emptyset$}\r
1649         \State $num_{largest} \gets num$ such that $\tuple{num, pt} \in PendingTransSet \land \forall \tuple{num', pt'} \in PendingTransSet, num \geq num'$ \Comment{Get the next largest number}\r
1650         \State $num_{largest} \gets num_{largest} +1$\r
1651     \EndIf\\\r
1652     \r
1653     \State $PendingTransSet \gets PendingTransSet \cup \{\tuple{num_{largest},PendingTrans}\}$\\\r
1654     \r
1655     \While{\Call{HasConnectionToServer}{ } $\land PendingTransSet \neq \emptyset$}    \r
1656         \State $\tuple{num, pt} \gets \tuple{num, pt}$ such that $\tuple{num, pt} \in PendingTransSet \land \forall \tuple{num', pt'} \in PendingTransSet, num \leq num'$ \Comment{Get the oldest one and try to commit it}\\\r
1657     \r
1658         \If{\Call{TryInsertTransaction}{$pt, false$}}\r
1659             \State $PendingTransSet \gets PendingTransSet \setminus \tuple{num, pt}$\r
1660         \EndIf\r
1661     \EndWhile\r
1662 \EndFunction\r
1663 \end{algorithmic}\r
1664 \end{varwidth}% \r
1665 }\r
1666 \r
1667 \r
1668 %Create New Key \r
1669 \noindent\fbox{%\r
1670 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
1671 \textbf{Create New Key:}\\\r
1672 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
1673 \begin{algorithmic}[1]\r
1674 \Function{Transaction Commit}{$k_a, id_a$}\r
1675     \State $success \gets false$\\\r
1676     \While{$\lnot success$}\r
1677         \If{$\exists \tuple{k',id'} \in Arbitrator, k' = k_a$}\r
1678             \State \Return{$false$} \Comment{Key already created}\r
1679         \EndIf\\\r
1680     \r
1681         \State $success \gets$ \Call{TryInsertNewKey}{$k_a, id_a$}\r
1682     \EndWhile\r
1683     \r
1684     \State \Return{$true$} \Comment{If got here then insertion was correct}\r
1685 \EndFunction\r
1686 \end{algorithmic}\r
1687 \end{varwidth}% \r
1688 }\r
1689 \r
1690 \r
1691 \end{document}\r