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, 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{seq, 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_{abrt},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 \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 \r
  82 \r
  83 \subsection{Helper Functions}\r
  84 The following helper functions are needed:\\\r
  85 \r
  86 % Get Size\r
  87 \noindent\fbox{%\r
  88 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
  89 \textbf{Get Byte Size:}\\\r
  90 Get the size in bytes of the thing that is passed in.\\\r
  91 \begin{algorithmic}[1]\r
  92 \Function{GetSize}{$a$}\r
  93     \State \Return{Size in bytes of $a$}\r
  94 \EndFunction\r
  95 \end{algorithmic}\end{varwidth}% \r
  96 }\r
  97 \r
  98 % Error\r
  99 \noindent\fbox{%\r
 100 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 101 \textbf{ Error:}\\\r
 102 Prints an error message and halts the execution of the client.\\\r
 103 \begin{algorithmic}[1]\r
 104 \Function{Error}{$msg$}\r
 105     \State $Print(msg)$\r
 106     \State $Halt()$\r
 107 \EndFunction\r
 108 \end{algorithmic}\end{varwidth}% \r
 109 }\r
 110 \r
 111 % Get Next Sequence Number\r
 112 \noindent\fbox{%\r
 113 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 114 \textbf{Get Next Sequence Number:}\\\r
 115 Get the next sequence number for insertion into the block chain.\\\r
 116 \begin{algorithmic}[1]\r
 117 \Function{GetNextSeq}{$k$}\r
 118     \LeftComment{Get the largest known sequence number}\r
 119     \State $seq_{ret} \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \geq seq')$\\\r
 120     \r
 121     \LeftComment{Add one to the largest seq number to generate the new seq number}\r
 122     \State \Return{$seq_{ret} + 1$}\r
 123 \EndFunction\r
 124 \end{algorithmic}\r
 125 \end{varwidth}% \r
 126 }\r
 127 \r
 128 % Get Arbitrator\r
 129 \noindent\fbox{%\r
 130 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 131 \textbf{Get Arbitrator:}\\\r
 132 Get the arbitrator for a given key.\\\r
 133 \begin{algorithmic}[1]\r
 134 \Function{GetArbitrator}{$k$}\r
 135     \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
 136     \State \Return{$id_1$}\r
 137 \EndFunction\r
 138 \end{algorithmic}\r
 139 \end{varwidth}% \r
 140 }\r
 141 \r
 142 % Check Transaction arbitrator\r
 143 \noindent\fbox{%\r
 144 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 145 \textbf{Check Arbitrator for a Transaction:}\\\r
 146 Check that the arbitrators for a given set are all the same arbitrator.\\\r
 147 \begin{algorithmic}[1]\r
 148 \Function{CheckArbitrator}{$PendingTrans_a$}\r
 149     \State $id_{arb} \gets NULL$\\\r
 150     \State $\tuple{KV_a, Guard_a} \gets PendingTrans_a$\r
 151     \r
 152     \ForAll{$\tuple{k',v'} \in KV_a$}\r
 153         \State $id' \gets$ \Call{GetArbitrator}{$k'$}\\\r
 154         \r
 155         \If{$id_{arb} = NULL$}  \r
 156             \State $id_{arb} \gets id'$\r
 157         \ElsIf{$id' \neq id_{arb}$} \Comment{Check all arbitrators are the same}\r
 158             \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
 159         \EndIf\r
 160     \EndFor\r
 161     \r
 162     \ForAll{$\tuple{k',v', lop'} \in Guard_a$}\r
 163         \State $id' \gets$ \Call{GetArbitrator}{$k'$}\\\r
 164         \r
 165         \If{$id_{arb} = NULL$}  \r
 166             \State $id_{arb} \gets id'$\r
 167         \ElsIf{$id' \neq id_{arb}$} \Comment{Check all arbitrators are the same}\r
 168             \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
 169         \EndIf\r
 170     \EndFor\r
 171 \EndFunction\r
 172 \end{algorithmic}\r
 173 \end{varwidth}% \r
 174 }\r
 175 \r
 176 % Get all Commits\r
 177 \noindent\fbox{%\r
 178 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 179 \textbf{Get all Commits:}\\\r
 180 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
 181 \begin{algorithmic}[1]\r
 182 \Function{GetCommits}{$ $}\r
 183     \State $ComSet \gets \emptyset$ \Comment{Set of the commits}\\\r
 184         \r
 185     \LeftComment{Iterate over all the slots saved locally}\r
 186     \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 187         \State $ComSet \gets ComSet \cup \{c |c \in DE',c$is a $commit\}$\r
 188     \EndFor\r
 189     \State \Return{$ComSet$}\r
 190 \EndFunction\r
 191 \end{algorithmic}\r
 192 \end{varwidth}% \r
 193 }\r
 194 \r
 195 % Get all aborts\r
 196 \noindent\fbox{%\r
 197 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 198 \textbf{Get all aborts:}\\\r
 199 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
 200 \begin{algorithmic}[1]\r
 201 \Function{GetAborts}{$ $}\r
 202     \State $AbrtSet \gets \emptyset$ \Comment{Set of the aborts}\\\r
 203         \r
 204     \LeftComment{Iterate over all the slots saved locally}\r
 205     \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 206         \State $AbrtSet \gets AbrtSet \cup \{c |c \in DE',c$is a $abort\}$\r
 207     \EndFor\r
 208     \State \Return{$AbrtSet$}\r
 209 \EndFunction\r
 210 \end{algorithmic}\r
 211 \end{varwidth}% \r
 212 }\r
 213 \r
 214 % Get all Queue States\r
 215 \noindent\fbox{%\r
 216 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 217 \textbf{Get all queue states:}\\\r
 218 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
 219 \begin{algorithmic}[1]\r
 220 \Function{GetQStates}{$ $}\r
 221     \State $QSet \gets \emptyset$ \Comment{Set of the qstates}\\\r
 222         \r
 223     \LeftComment{Iterate over all the slots saved locally}\r
 224     \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
 225         \State $QSet \gets QSet \cup \{c |c \in DE',c$is a $qstate\}$\r
 226     \EndFor\r
 227     \State \Return{$QSet$}\r
 228 \EndFunction\r
 229 \end{algorithmic}\r
 230 \end{varwidth}% \r
 231 }\r
 232 \r
 233 % Check Queue State Live\r
 234 \noindent\fbox{%\r
 235 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 236 \textbf{Check Queue State Live:}\\\r
 237 A queue state is dead if there is another queue state data entry that has a larger queue state.\\\r
 238 \begin{algorithmic}[1]\r
 239 \Function{CheckQStateLive}{$qstate_a$}\r
 240     \State $\tuple{size_a} \gets qstate_a$\r
 241     \State $AllQStates \gets$ \Call{GetQState}{} \Comment{Get all the qstates} \\\r
 242     \r
 243     \If{$\exists \tuple{size'} \in AllQStates, size' > size_a$}\r
 244         \State \Return{false}\r
 245     \EndIf\r
 246     \State \Return{true}\r
 247     \r
 248 \EndFunction\r
 249 \end{algorithmic}\r
 250 \end{varwidth}% \r
 251 }\r
 252 \r
 253 % Check Commit Live\r
 254 \noindent\fbox{%\r
 255 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 256 \textbf{Check Commit Live:}\\\r
 257 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
 258 \begin{algorithmic}[1]\r
 259 \Function{CheckCommitLive}{$commit_a$}\r
 260     \State $\tuple{seq_{a_{trans}},KV_a} \gets commit_a$\r
 261     \State $KSet \gets \{k|\tuple{k,v} \in KV\}$\r
 262     \State $AllCommits \gets$ \Call{GetCommits}{} \Comment{Get all the commits} \\\r
 263     \r
 264     \LeftComment{Iterate all commits that are newer in time}\r
 265     \ForAll{$\tuple{seq_{trans}',KV'}\in AllCommits, seq_{trans}' > seq_{a_{trans}}$}\r
 266         \State $KVSet \gets KVSet \setminus \{k|\tuple{k,v} \in KV'\}$\\\r
 267         \r
 268         \If{$KVSet = \emptyset$}\r
 269             \State \Return{false} \Comment{All keys have a newer commit}\r
 270         \EndIf\r
 271     \EndFor\r
 272     \State \Return{true} \Comment{If got here then some keys still live}\r
 273 \EndFunction\r
 274 \end{algorithmic}\r
 275 \end{varwidth}% \r
 276 }\r
 277 \r
 278 % Check Last Message Live\r
 279 \noindent\fbox{%\r
 280 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 281 \textbf{Check Last Message Live:}\\\r
 282 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
 283 \begin{algorithmic}[1]\r
 284 \Function{CheckLastMsgLive}{$lastmsg_a$}\r
 285     \State $\tuple{seq_a, id_a} \gets lastmsg_a$\\\r
 286     \r
 287     \If{$\exists \tuple{id', seq'} \in LastSlot, id'=id_a \land seq' > seq_a$}\r
 288         \State \Return{false}\r
 289     \EndIf\r
 290     \State \Return{True}    \r
 291 \EndFunction\r
 292 \end{algorithmic}\r
 293 \end{varwidth}% \r
 294 }\r
 295 \r
 296 %Check Collision Resolution Live\r
 297 \noindent\fbox{%\r
 298 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 299 \textbf{Check Collision Resolution Live:}\\\r
 300 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
 301 \begin{algorithmic}[1]\r
 302 \Function{CheckColResLive}{$colres_a$}\r
 303     \State $\tuple{id_a, seq_{a_{old}}, seq_{a_{new}}, equal_a} \gets colres_a$\\\r
 304     \r
 305     \If{$\forall \tuple{id', seq'} \in LastSlot, seq' \geq seq_{a_{new}}$}\r
 306         \State \Return{false}\r
 307     \EndIf\r
 308     \State \Return{true}\r
 309 \EndFunction\r
 310 \end{algorithmic}\r
 311 \end{varwidth}% \r
 312 }\r
 313 \r
 314 % Check New Key Live\r
 315 \noindent\fbox{%\r
 316 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 317 \textbf{Check New Key Live:}\\\r
 318 A new key data entry is always live.\\\r
 319 \begin{algorithmic}[1]\r
 320 \Function{CheckNewkeyLive}{$newkey_a$}\r
 321     \State \Return{True}    \r
 322 \EndFunction\r
 323 \end{algorithmic}\r
 324 \end{varwidth}% \r
 325 }\r
 326 \r
 327 % Check Abort Live\r
 328 \noindent\fbox{%\r
 329 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 330 \textbf{Check Abort Live:}\\\r
 331 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
 332 \begin{algorithmic}[1]\r
 333 \Function{CheckAbortLive}{$abort_a$}\r
 334     \State $\tuple{seq_{a_{abrt}}, seq_{a_{trans}},id_a} \gets abort_a$\\\r
 335     \r
 336     \LeftComment{The device whos transaction was aborted saw the abort}\r
 337     \If{$\exists \tuple{id', seq'} \in LastSlot, id'=id_a \land seq' > seq_{a_{abrt}}$}\r
 338         \State \Return{false}\r
 339     \EndIf\r
 340     \State \Return{True}    \r
 341 \EndFunction\r
 342 \end{algorithmic}\r
 343 \end{varwidth}% \r
 344 }\r
 345 \r
 346 % Check Transaction Live\r
 347 \noindent\fbox{%\r
 348 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 349 \textbf{Check Transaction Live:}\\\r
 350 A transaction is dead if there is an abort for that transaction or if there is a commit for that transaction or a transaction that came after this transaction.  Since transactions must be commited in order of there insertion, seeing a transaction that is commited and has a larger sequence number than the transaction in question means that the transaction in question was commited at some point.\\\r
 351 \begin{algorithmic}[1]\r
 352 \Function{CheckTransLive}{$trans_a$}\r
 353     \State $\tuple{seq_a, KV_a, Guard_a} \gets trans_a$\r
 354     \State $AllCommits \gets$ \Call{GetCommits}{} \Comment{Get all the commits}\r
 355     \State $AllAborts \gets$ \Call{GetAborts}{} \Comment{Get all the aborts} \\\r
 356     \r
 357     \If{$\exists \tuple{seq_{abrt}',seq_{trans}',id'} \in AllAborts, seq_{trans}' = seq_a$}\r
 358         \State \Return{false}\r
 359     \ElsIf{$\exists \tuple{seq_{trans}',KV'} \in AllCommits, seq_{trans}' \geq seq_a$}\r
 360         \State \Return{false}\r
 361     \EndIf\r
 362     \State \Return{true}\r
 363 \EndFunction\r
 364 \end{algorithmic}\r
 365 \end{varwidth}% \r
 366 }\r
 367 \r
 368 % Check Live\r
 369 \noindent\fbox{%\r
 370 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 371 \textbf{Check Live:}\\\r
 372 Checks if a data entry is live based on its type.\\\r
 373 \begin{algorithmic}[1]\r
 374 \Function{CheckLive}{$datentry$}\r
 375     \If{$datentry$ is a $commit$}\r
 376         \State \Return{\Call{CheckCommitLive}{$datentry$}}\\r
 377     \ElsIf{$datentry$ is a $abort$}\r
 378         \State \Return{\Call{CheckAbortLive}{$datentry$}}\\r
 379     \ElsIf{$datentry$ is a $trans$}\r
 380         \State \Return{\Call{CheckTransLive}{$datentry$}}\\r
 381     \ElsIf{$datentry$ is a $lastmsg$}\r
 382         \State \Return{\Call{CheckLastMsgLive}{$datentry$}}\\r
 383     \ElsIf{$datentry$ is a $colres$}\r
 384         \State \Return{\Call{CheckColResLive}{$datentry$}}\\r
 385     \ElsIf{$datentry$ is a $qstate$}\r
 386         \State \Return{\Call{CheckQStateLive}{$datentry$}}\r
 387     \ElsIf{$datentry$ is a $newkey$}\r
 388         \State \Return{\Call{CheckNewkeyLive}{$datentry$}}\r
 389     \Else\r
 390         \State \Call{Error}{"Unknown data entry type."}\r
 391     \EndIf\r
 392 \EndFunction\r
 393 \end{algorithmic}\r
 394 \end{varwidth}% \r
 395 }\r
 396 \r
 397 % Slot Has Live\r
 398 \noindent\fbox{%\r
 399 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 400 \textbf{Slot Has Live:}\\\r
 401 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
 402 \begin{algorithmic}[1]\r
 403 \Function{SlotHasLive}{$slot_a$}\r
 404     \State $\tuple{s_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in LocalSlots$\r
 405     \r
 406     \ForAll{$datentry \in DE$}\r
 407         \If{\Call{CheckLive}{$datentry$}} \Comment{an entry is alive}\r
 408             \State \Return{true}\r
 409         \EndIf\r
 410     \EndFor\r
 411     \r
 412     \State \Return{false} \Comment{All entries were dead}    \r
 413 \EndFunction\r
 414 \end{algorithmic}\r
 415 \end{varwidth}% \r
 416 }\r
 417 \r
 418 % Calculate Resize Threshold\r
 419 \noindent\fbox{%\r
 420 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 421 \textbf{Calculate Resize Threshold:}\\\r
 422 Calculate a threshold for how many slots need to have live data entries in them for a resize to take place.\\\r
 423 \begin{algorithmic}[1]\r
 424 \Function{CalcResizeThresh}{$maxsize$}\r
 425     \State \Return{$\left \lfloor {maxsize * RESIZE\_THRESH\_PERCENT} \right \rfloor$}\r
 426 \EndFunction\r
 427 \end{algorithmic}\r
 428 \end{varwidth}% \r
 429 }\r
 430 \r
 431 % Calculate Block Chain New Size\r
 432 \noindent\fbox{%\r
 433 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 434 \textbf{Calculate Block Chain New Size:}\\\r
 435 Calculate the new size of the block chain which we need if we are to resize the data structure.\\\r
 436 \begin{algorithmic}[1]\r
 437 \Function{CalcNewSize}{$maxsize$}\r
 438     \State \Return{$\left \lceil {maxsize * RESIZE\_THRESH\_PERCENT} \right \rceil$}\r
 439 \EndFunction\r
 440 \end{algorithmic}\r
 441 \end{varwidth}% \r
 442 }\r
 443 \r
 444 % Should Resize\r
 445 \noindent\fbox{%\r
 446 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 447 \textbf{Should Resize:}\\\r
 448 Check if the block should resize based on some metric of how many slots in the block chain are filled with live data. \\\r
 449 \begin{algorithmic}[1]\r
 450 \Function{ShouldResize}{$ $}\r
 451     \State $LiveSlots \gets \{slot_s|slot_s \in LocalSlots \land $\Call{SlotHasLive}{$slot_s$}$\}$\r
 452     \State $resizethreshold \gets $ \Call{CalcResizeThresh}{$max\_size$}\r
 453     \State \Return{$|LiveSlots| \geq resizethreshold$} \Comment{If passes threshold then resize}\r
 454 \EndFunction\r
 455 \end{algorithmic}\r
 456 \end{varwidth}% \r
 457 }\r
 458 \r
 459 % Create Queue State \r
 460 \noindent\fbox{%\r
 461 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 462 \textbf{Create Queue State:}\\\r
 463 Generate a queue state data entry.\\\r
 464 \begin{algorithmic}[1]\r
 465 \Function{CreateQState}{$size_a$}\r
 466     \State \Return{$\tuple{size_a}$}    \r
 467 \EndFunction\r
 468 \end{algorithmic}\r
 469 \end{varwidth}% \r
 470 }\r
 471 \r
 472 % Generate Transaction\r
 473 \noindent\fbox{%\r
 474 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 475 \textbf{Create Transaction:}\\\r
 476 Generate a transaction data entry.\\\r
 477 \begin{algorithmic}[1]\r
 478 \Function{CreateTrans}{$pendingtrans_a, seq_a$}\r
 479     \State $\tuple{KV_a, Guard_a} \gets pendingtrans_a$\r
 480     \State \Return{$\tuple{seq_a, KV_a, Guard_a}$}    \r
 481 \EndFunction\r
 482 \end{algorithmic}\r
 483 \end{varwidth}% \r
 484 }\r
 485 \r
 486 \r
 487 % Data Entry Set Has Space \r
 488 \noindent\fbox{%\r
 489 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 490 \textbf{Data Entry Set Has Space :}\\\r
 491 Checks if a data entry set has enough space for a new data entry to be inserted.\\\r
 492 \begin{algorithmic}[1]\r
 493 \Function{DEHasSpace}{$DE_a, de_a$}\r
 494     \State $newsize \gets $ \Call{GetSize}{$DE_a$}\r
 495     \State $newsize \gets newsize +$ \Call{GetSize}{$de_a$}\r
 496     \State \Return{$newsize \leq DATA\_ENTRY\_SET\_MAX\_SIZE$}\r
 497 \EndFunction\r
 498 \end{algorithmic}\r
 499 \end{varwidth}% \r
 500 }\r
 501 \r
 502 \r
 503 \r
 504 % Create Rescued Commit\r
 505 \noindent\fbox{%\r
 506 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 507 \textbf{Create Rescued Date Entry:}\\\r
 508 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
 509 \begin{algorithmic}[1]\r
 510 \Function{CreateRescuedCommit}{$commit_a$}\r
 511     \State $AllCommits \gets $ \Call{GetCommits}{}\r
 512     \State $\tuple{seq_{a_{trans}},KV_a} \gets de_a$\r
 513     \State $NewKV \gets KV_a$\\\r
 514 \r
 515     \LeftComment{Get rid of all key values that have newer commits}\r
 516     \ForAll{$\tuple{k_a, v_a} \in KV_a$}\r
 517         \LeftComment{Iterate over all commits that are newer than the rescue commit}\r
 518         \ForAll{$\tuple{seq', KV'} \in AllCommits, seq' > seq_{a_{trans}}$}\r
 519             \If{$\exists \tuple{k', v'} \in KV', k' = k_a$}\r
 520                 \State $NewKV \gets NewKV \setminus \tuple{k_a, v_a}$\r
 521                 \State Break\r
 522             \EndIf\r
 523         \EndFor\r
 524     \EndFor\r
 525     \State \Return{$\tuple{seq_{a_{trans}}, NewKV}$}\r
 526 \EndFunction\r
 527 \end{algorithmic}\r
 528 \end{varwidth}% \r
 529 }\r
 530 \r
 531 \r
 532 % Create Rescued Date Entry\r
 533 \noindent\fbox{%\r
 534 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 535 \textbf{Create Rescued Date Entry:}\\\r
 536 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
 537 \begin{algorithmic}[1]\r
 538 \Function{CreateRescuedEntry}{$de_a$}\r
 539 \r
 540     \If{$de_a$is a $commit$}\r
 541         \State \Return{\Call{CreateRescuedCommit}{$de_a$}}\r
 542     \EndIf\r
 543     \r
 544     \State \Return{$de_a$} \Comment{No Modification needed}\r
 545 \r
 546 \EndFunction\r
 547 \end{algorithmic}\r
 548 \end{varwidth}% \r
 549 }\r
 550 \r
 551 \r
 552 % Mandatory Rescue\r
 553 \noindent\fbox{%\r
 554 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 555 \textbf{Mandatory Rescue:}\\\r
 556 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
 557 \begin{algorithmic}[1]\r
 558 \Function{MandatoryRescue}{$DE_a$}\r
 559     \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
 560     \State $cseq \gets smallestseq$\\\r
 561     \r
 562     \LeftComment{Check the least slots to rescue and live entries}\r
 563     \While{$cseq < (smallestseq + DEAD\_SLOT\_COUNT)$}\r
 564         \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
 565         \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\\\r
 566         \r
 567         \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
 568             \If{\Call{CheckLive}{$de$}} \Comment{data entry is live}\r
 569                 \State $de \gets $ \Call{CreateRescuedEntry}{de} \Comment{Resize entry if needed}\r
 570                 \If{\Call{DEHasSpace}{$DE_a, de$}}\r
 571                     \State $DE_a \gets DE_a \cup de$ \Comment{Had enough space to add it}\r
 572                 \ElsIf{$currentseq = smallestseq$}\r
 573                     \State \Return{$NULL$}\r
 574                 \Else\r
 575                     \State \Return{$DE_a$}\r
 576                 \EndIf\r
 577             \EndIf\r
 578         \EndFor\\\r
 579         \r
 580         \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
 581     \EndWhile\r
 582     \r
 583     \State \Return{$DE_a$}\r
 584 \EndFunction\r
 585 \end{algorithmic}\r
 586 \end{varwidth}% \r
 587 }\r
 588 \r
 589 \r
 590 \r
 591 \r
 592 % Try Insert Transaction\r
 593 \noindent\fbox{%\r
 594 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 595 \textbf{Try Insert Transaction:}\\\r
 596 Try to insert a transaction into the block chain.\\\r
 597 \begin{algorithmic}[1]\r
 598 \Function{TryInsertTransaction}{$pendingtrans_a, forceresize$}\r
 599     \State $DE \gets \emptyset$ \Comment{The data entries for this slot}\r
 600     \State $seq \gets $ \Call{GetNextSeq}{} \Comment{Get the sequence number for this slot}\r
 601     \State $newsize \gets 0$\r
 602     \State $trans \gets$ \Call{CreateTrans}{$pendingtrans_a, seq$}\r
 603     \State $transinserted \gets false$\r
 604     \r
 605     \State $resize \gets $ \Call{ShouldResize}{ } \Comment{Check if we should resize}\r
 606     \State $resize \gets resize \lor forceresize$\r
 607     \If{$resize$}\r
 608         \State $newsize \gets$ \Call{CalcNewSize}{$max\_size$}\r
 609         \State $DE \gets DE \cup \{$\Call{CreateQState}{$newsize$}$\}$\r
 610     \EndIf\\\r
 611     \r
 612     \r
 613     \r
 614     \r
 615     %\If{$RejectedSlotList \neq \emptyset$}   \r
 616     %\EndIf\r
 617     \r
 618     % Arbitrate\r
 619     \r
 620     \State $DE \gets$ \Call{MandatoryRescue}{$DE$} \Comment{Round 1 of rescue}\r
 621     \If{$DE = NULL$}\r
 622         \LeftComment{Data was going to fall off the end so try again with a forced resize}\r
 623         \State \Return{\Call{TryInsertTransaction}{$trans_a, true$}}\r
 624     \EndIf\\\r
 625     \r
 626     \If{\Call{DEHasSpace}{$DE, trans$}} \Comment{transaction fits}\r
 627         \State $DE \gets DE \cup trans$\r
 628         \State $transinserted \gets true$\r
 629     \EndIf\r
 630     \r
 631     \r
 632     \r
 633 \EndFunction\r
 634 \end{algorithmic}\r
 635 \end{varwidth}% \r
 636 }\r
 637 \r
 638 \r
 639 \r
 640 \subsection{Client Interfaces}\r
 641 \r
 642 % Put KV pair\r
 643 \noindent\fbox{%\r
 644 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 645 \textbf{Put Key Value Pair:}\\\r
 646 Puts a key value pair into the key value pair buffer\\\r
 647 \begin{algorithmic}[1]\r
 648 \Function{PutKeyValue}{$k,v$}\r
 649     \State $\tuple{seq, KV, Guard} \gets PendingTrans$\\\r
 650     \r
 651     \LeftComment{Check if KV already has a key value pair for the specified key}\r
 652     \State $DSet \gets \{\tuple{k_1,v_1} | \tuple{k_1,v_1} \in KV \land k_1 = k\}$\\\r
 653     \r
 654     \If{$DSet \neq \emptyset$}\r
 655         \State \Call{Error}{"Value for key already in most recent update"}\r
 656     \EndIf\\\r
 657         \r
 658     \State $KV \gets KV \cup \{\tuple{k,v}\}$ \Comment{Add key value pair}\r
 659     \State $PendingTrans \gets \tuple{seq, KV, Guard}$\r
 660     \State \Call{CheckArbitrator}{$PendingTrans$} \Comment{Check that the transaction still valid}\r
 661 \EndFunction\r
 662 \end{algorithmic}\r
 663 \end{varwidth}% \r
 664 }\r
 665 \r
 666 \r
 667 % Put guard condition\r
 668 \noindent\fbox{%\r
 669 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 670 \textbf{Put Guard:}\\\r
 671 Puts a guard transaction into the key value update.  A guard is a key value with a logical operator ($lop$).\\\r
 672 \begin{algorithmic}[1]\r
 673 \Function{PutGuard}{$k,v, lop$}\r
 674     \State $\tuple{seq, KV, Guard} \gets PendingTrans$\\\r
 675     \r
 676     \If{$\tuple{k,v, lop} \in Guard$}\r
 677         \State \Return{} \Comment{Already have guard condition in update}\r
 678     \EndIf\\\r
 679     \r
 680     \State $Guard \gets Guard \cup \{\tuple{k,v,lop}\}$\r
 681     \State $PendingTrans \gets \tuple{seq, KV, Guard}$\r
 682     \State \Call{CheckArbitrator}{$PendingTrans$} \Comment{Check that the transaction still valid}\r
 683 \EndFunction    \r
 684 \end{algorithmic}\r
 685 \end{varwidth}% \r
 686 }\r
 687 \r
 688 \r
 689 % Transaction Start\r
 690 \noindent\fbox{%\r
 691 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 692 \textbf{ Transaction Start:}\\\r
 693 Starts a transaction.  Clears out the key value pair update buffer.\\\r
 694 \begin{algorithmic}[1]\r
 695 \Function{TransactionStart}{$ $}\r
 696     \LeftComment{Reset the key value update buffer}\r
 697     \State $KVUpdate \gets \tuple{\emptyset, \emptyset}$\r
 698 \EndFunction\r
 699 \end{algorithmic}\r
 700 \end{varwidth}% \r
 701 }\r
 702 \r
 703 % Transaction Commit\r
 704 \noindent\fbox{%\r
 705 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 706 \textbf{ Transaction Commit:}\\\r
 707 Commits the transaction into the block chain.  Keeps attempting to insert the transaction into the block chain until it succeeds.\r
 708 \begin{algorithmic}[1]\r
 709 \Function{Transaction Commit}{$ $}\r
 710     \State $success \gets False$\r
 711     \r
 712     \While{$\lnot success$}\r
 713         \State $success \gets$\r
 714     \EndWhile\r
 715     \r
 716     \r
 717 \EndFunction\r
 718 \end{algorithmic}\r
 719 \end{varwidth}% \r
 720 }\r
 721 \r
 722 \end{document}\r