version2/doc/iotcloud_formal/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 \begin{document}\r
  21 \r
  22 \r
  23 \setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text\r
  24 \r
  25 \r
  26 \section{\textbf{Introduction}}\r
  27 \r
  28 \r
  29 \r
  30 \r
  31 \r
  32 \section{\textbf{Server}}\r
  33 The server maintains a collection of slots such that each slot contains some data.\r
  34 The operations on the slot are as follows:\r
  35 \begin{itemize}\r
  36     \item Put slot\r
  37     \item Get slot\r
  38     \item Delete Slot\r
  39 \end{itemize}\r
  40 \r
  41 \subsection{\textbf{Server Notation Conventions}}\r
  42 $s \in SN$ is a server sequence number\\\r
  43 $sv \in SV$ is a slot's value\\\r
  44 $slot_s = \tuple{s, sv} \in SL \subseteq SN \times SV$\r
  45 \r
  46 \subsection{\textbf{Server State}}\r
  47 \textit{n = current server sequence number}\\\r
  48 \textit{SL = set of live slots on the server}\\\r
  49 \r
  50 \textbf{Initial Server State}\\\r
  51 $SL = \emptyset$\\\r
  52 $n = 0$\r
  53 \r
  54 \subsection{\textbf{Put Slot}}\r
  55 Put slot is an operation that inserts data into a new slot at the server.\\\r
  56 \r
  57 %Put Function\r
  58 \noindent\fbox{%\r
  59 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
  60 \textbf{Put Function:}\r
  61 \begin{algorithmic}[1]\r
  62 \Function{PutSlotServer}{$sv_p$}\r
  63     \State $s_p \gets n$\r
  64     \State $n \gets n + 1$\r
  65     \State $SL \gets SL \cup \{\tuple{s_p,sv_p}\}$\r
  66 \EndFunction\r
  67 \end{algorithmic}\r
  68 \end{varwidth}% \r
  69 }\r
  70 \r
  71 \subsection{\textbf{Get Slot}}\r
  72 Get slot is an operation that returns all server slots that are greater than some server sequence number.\\\r
  73 \r
  74 % Get Function\r
  75 \noindent\fbox{%\r
  76 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
  77 \textbf{Get Function:}\r
  78 \begin{algorithmic}[1]\r
  79 \Function{GetSlotServer}{$s_g$}\r
  80     \State \Return{$\{\tuple{s, sv} \in SL \mid s \geq s_g\}$}\r
  81 \EndFunction\r
  82 \end{algorithmic}\r
  83 \end{varwidth}% \r
  84 }\r
  85 \r
  86 \subsection{\textbf{Delete Slot}}\r
  87 Delete slot is an operation that deletes all live slots that have server sequence numbers that are equal to or less than some server sequence number.\\\r
  88 \r
  89 %Delete Function\r
  90 \noindent\fbox{%\r
  91 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
  92 \textbf{Delete Function:}\r
  93 \begin{algorithmic}[1]\r
  94 \Function{DeleteSlotServer}{$s_d$}\r
  95     \State $SD \gets \{\tuple{s, sv} \in SL \mid s \leq s_g\}$\r
  96     \State $SL \gets SL - SD$\r
  97 \EndFunction\r
  98 \end{algorithmic}\r
  99 \end{varwidth}% \r
 100 }\r
 101 \r
 102 \r
 103 \r
 104 \r
 105 \r
 106 \r
 107 \r
 108 \r
 109 \section{\textbf{Client}}\r
 110 The data structure acts as a key store where key-value pairs can be read and set.\r
 111 The data structure exposes the following functions:\r
 112 \begin{itemize}\r
 113     \item Put Transaction\r
 114     \item Get key-value pair\r
 115     \item Create new key\r
 116 \end{itemize}\r
 117 \r
 118 \subsection{\textbf{Client Notation Conventions}}\r
 119 \r
 120 $K$ is the set of all keys.\\\r
 121 $MID$ is the set of the machine IDs of the devices that are in the system.\r
 122 $K_{mid}$ is a set of all keys that have device mid as the arbitrator\\\r
 123 $ssn_s$ is the server sequence number of a record $s$\\\r
 124 $mid_s \in MID$ is the machine ID for the device that created $record_s$.\\\r
 125 $hmac_s$ is the HMAC of $record_s$\\\r
 126 $c_{mid}$ is the latest read clock for a device with machine ID $mid$\\\r
 127 $vc_s = \{c_{mid} | mid \in MID\}$\\\r
 128 $rid_s = \tuple{mid_s, c_{mid_s}}$\r
 129 $k$ is a key entry\\\r
 130 $v$ is a value entry\\\r
 131 $kv_n$ is a key-value entry $\tuple{k_n,v_n} , k \in K$\\\r
 132 \r
 133 $tid_s = \tuple{mid_s,c_{mid_s}}$\\\r
 134 $guard_s = \tuple{\{kv_1, kv_2, ... ,kv_n | \exists mid \in MID, \forall n, kv_n[k] \in K_{mid}\},$ boolean condition using $ \{kv_1, kv_2, ... ,kv_n\}} $\\\r
 135 $transaction_s = \{mid_s,vc_{s_t} ,\{kv_1, kv_2,...kv_n | \exists mid \in MID, mid = guard_s[mid], \forall n, kv_n[k] \in K_{mid}\},guard_s\}$\\\r
 136 $commit_s = \tuple{tid_s,vc_s}$\\\r
 137 $abort_s = \tuple{tid_s,mid_s,vc_s}$\\\r
 138 $sequence_s = \tuple{rid_s, ssn_s}$\\\r
 139 $delete_s = \tuple{ssn_d}$\\\r
 140 $resize_s = \tuple{x | x \in \mathbb{N}}$\\\r
 141 $newkey_s = \tuple{k_s, vc_s, ssn_s$ or $NULL, mid_s}$\\\r
 142 \r
 143 $payload_s = \{x_1, x_2,..., x_k | \forall k, x_k \in \{$transaction, commit, abort, resize, newkey, sequence, delete$\}\}$\\\r
 144 $rd_s = \tuple{mid_s, vc_s, hmac_s, payload_s}$ \\\r
 145 $record_s = \tuple{ssn_s,rd_s}$\\\r
 146 \r
 147 \subsection{\textbf{Client State}}\r
 148 \textit{s = largest server sequence number pulled from the server by a device} \\\r
 149 \textit{R = set of records pulled from the server so far with their server sequence numbers} \\\r
 150 \textit{RL = set of records that contain live data} \\\r
 151 \r
 152 \subsection{Helper Functions}\r
 153 The following helper functions are needed:\\\r
 154 \r
 155 \r
 156 %Throw Error\r
 157 \noindent\fbox{%\r
 158 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 159 \textbf{Throw Error:}\r
 160 \begin{algorithmic}[1]\r
 161 \Function{Error}{$msg$}\r
 162     \State $Print(msg)$\r
 163     \State $Halt()$\r
 164 \EndFunction\r
 165 \end{algorithmic}\r
 166 \end{varwidth}% \r
 167 }\r
 168 \r
 169 %Error Message\r
 170 \begin{algorithmic}[1]\r
 171 \Procedure{Error}{$msg$}\r
 172 \State $Print(msg)$\r
 173 \State $Halt()$\r
 174 \EndProcedure\r
 175 \end{algorithmic}\r
 176 \r
 177 \r
 178 %Get Latest Data Structure From Server\r
 179 \noindent\fbox{%\r
 180 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 181 \textbf{Get  Latest Data Structure From Server}:\r
 182 \begin{algorithmic}[1]\r
 183 \Function{GetLatestDataStruct}{}\r
 184     \State $largestSsn \gets $ Largest $ssn$ of all $ssn$ in $R$\r
 185     \State $R \gets R \cup $ \Call{GetSlotServer}{$largestSsn + 1$}\r
 186 \EndFunction\r
 187 \end{algorithmic}\r
 188 \end{varwidth}% \r
 189 }\r
 190 \r
 191 %Get Payload Items from Record with SSN\r
 192 \noindent\fbox{%\r
 193 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 194 \textbf{Get Payload Items from Record with SSN}:\r
 195 \begin{algorithmic}[1]\r
 196 \Function{GetPayloadItemsWithSSN}{$record_s$}\r
 197     \State $PISSN \gets \emptyset$ \Comment{Set of Payload Items with ssn}\r
 198     \State $\tuple{ssn_s, rd_s} \gets record_s$\r
 199     \State $\tuple{mid_s, vc_s, hmac_s, payload_s} \gets rd_s$\\\r
 200     \r
 201     \ForAll{$payloadItems$ in $payload_s$}\r
 202         \State $PISSN \gets PISSN \cup \{\tuple{payloadItem, ssn_s}\}$\r
 203     \EndFor\\\r
 204     \r
 205     \State \Return {$PISSN$}\r
 206 \EndFunction\r
 207 \end{algorithmic}\r
 208 \end{varwidth}% \r
 209 }\r
 210 \r
 211 %Get rid For Record\r
 212 \noindent\fbox{%\r
 213 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 214 \textbf{Get rid For Record}:\r
 215 \begin{algorithmic}[1]\r
 216 \Function{GetRid}{$record_s$}\r
 217     \State $\tuple{ssn_s, \tuple{mid_s, \{c_{mid_1}, c_{mid_2}, ... , c_{mid_k}\}, hmac_s, payload_s}} \gets record_s$\r
 218     \State \Return {$\tuple{mid_s, c_{mid_s}}$}\r
 219 \EndFunction\r
 220 \end{algorithmic}\r
 221 \end{varwidth}% \r
 222 }\r
 223 \r
 224 %Sequence Live\r
 225 \noindent\fbox{%\r
 226 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 227 \textbf{Sequence Live}:\r
 228 \begin{algorithmic}[1]\r
 229 \Function{SequenceLive}{$sequence_s, ssn_{s1}$}\r
 230     \State $API \gets \emptyset$   \Comment{Set of all Payload Items}\r
 231     \State $AS \gets \emptyset$    \Comment{Set of all Payload Items that are sequences}\r
 232     \State $StillHasRecord \gets False$\r
 233     \State $\tuple{rid_s, ssn_{s2}} \gets sequence_s$\\\r
 234     \r
 235     \ForAll{$record$ in $R$}\r
 236         \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
 237         \If{$rid_s = $\Call{GetRid}{$record$}}\r
 238             \State $StillHasRecord \gets True$\r
 239         \EndIf\r
 240     \EndFor\\\r
 241     \r
 242     \If{$\lnot StillHasRecord$}  \Comment{The Record does not exists anymore}\r
 243         \State \Return{False}\r
 244     \EndIf\\\r
 245     \r
 246     \ForAll{$\tuple{ssn, payload}$ in $API$}\r
 247         \If{$payload$ is a $sequence$}\r
 248             \State $AS \gets AS \cup \{\tuple{ssn, payload}\}$   \Comment{Extract all sequence payloads}\r
 249         \EndIf\r
 250     \EndFor\\\r
 251     \r
 252     \ForAll{$\tuple{ssn_1', \tuple{rid', ssn_2'}}$ in $AS$}\r
 253         \If{$(rid'=rid_s) \land (ssn_1' > ssn_{s_1})$}\r
 254             \State \Return{False}\r
 255         \EndIf\r
 256     \EndFor \\\r
 257     \State \Return{True}\r
 258 \EndFunction\r
 259 \end{algorithmic}\r
 260 \end{varwidth}% \r
 261 }\r
 262 \r
 263 % Delete Live\r
 264 \noindent\fbox{%\r
 265 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 266 \textbf{Delete Live}:\r
 267 \begin{algorithmic}[1]\r
 268 \Function{DeleteLive}{$delete_s, ssn_s$}\r
 269     \State $API \gets \emptyset$   \Comment{Set of all Payload Items}\r
 270     \State $AD \gets \emptyset$    \Comment{Set of all Payload Items that are deletes}\r
 271     \State $\tuple{ssn_d} \gets delete_s$\\\r
 272     \r
 273     \ForAll{record in R}\r
 274         \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
 275     \EndFor\\\r
 276     \r
 277     \ForAll{$\tuple{ssn, payload}$ in $API$}\r
 278         \If{$payload$ is a $delete$}\r
 279             \State $AD \gets AD \cup \{\tuple{ssn, payload}\}$   \Comment{Extract all delete payloads}\r
 280         \EndIf\r
 281     \EndFor\\\r
 282     \r
 283     \ForAll{delete in AD}\r
 284         \State $\tuple{{ssn_s}', \tuple{{ssn_d}'}} \gets delete$\r
 285         \If{${ssn_d}' > ssn_d$}    \Comment{More recently deleted record}\r
 286             \State \Return{False}\r
 287         \ElsIf{$({ssn_d}'= ssn_d) \land ({ssn_s}' > ssn_s)$} \Comment{More recent delete of same record}\r
 288             \State \Return{False}\r
 289         \EndIf\r
 290     \EndFor \\\r
 291     \State \Return{True}\r
 292 \EndFunction\r
 293 \end{algorithmic}\r
 294 \end{varwidth}% \r
 295 }\r
 296 \r
 297 %Abort Live\r
 298 \noindent\fbox{%\r
 299 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 300 \textbf{Abort Live}:\r
 301 \begin{algorithmic}[1]\r
 302 \Function{AbortLive}{$abort_s$}\r
 303     \State $\tuple{tid_s,mid_s,vc_s} \gets abort_s$\\\r
 304     \ForAll{record in R}\r
 305         \State $\tuple{ssn_s',\tuple{mid_s', vc_s', hmac_s', payload_s'}} \gets record$\r
 306         \If{$(mid_s'=mid_s) \land (vc_s' > vc_s)$}\r
 307             \State \Return{True}\r
 308         \EndIf\r
 309     \EndFor\\\r
 310     \State \Return{False}\r
 311 \EndFunction\r
 312 \end{algorithmic}\r
 313 \end{varwidth}% \r
 314 }\r
 315 \r
 316 %Resize Live\r
 317 \noindent\fbox{%\r
 318 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 319 \textbf{Resize Live}:\r
 320 \begin{algorithmic}[1]\r
 321 \Function{ResizeLive}{$resize_s, ssn_s$}\r
 322     \State $API \gets \emptyset$   \Comment{Set of all Payload Items}\r
 323     \State $AR \gets \emptyset$    \Comment{Set of all Payload Items that are resize}\r
 324     \State $\tuple{size} \gets resize_s$\\\r
 325     \r
 326     \ForAll{record in R}\r
 327         \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
 328     \EndFor\\\r
 329     \r
 330     \ForAll{$\tuple{ssn, payload}$ in $API$}\r
 331         \If{$payload$ is a $resize$}\r
 332             \State $AR \gets AR \cup \{\tuple{ssn, payload}\}$   \Comment{Extract all resize payloads}\r
 333         \EndIf\r
 334     \EndFor\\\r
 335     \r
 336     \ForAll{$\tuple{ssn', \tuple{size'}}$ in $AR$}\r
 337         \If{$size' > size$}\r
 338             \State \Return{False}\r
 339         \ElsIf{$(size'=size) \land (ssn' > ssn_s)$}\r
 340             \State \Return{False}\r
 341         \EndIf\r
 342     \EndFor \\\r
 343     \State \Return{True}\r
 344 \EndFunction\r
 345 \end{algorithmic}\r
 346 \end{varwidth}% \r
 347 }\r
 348 \r
 349 %New Key Live\r
 350 \noindent\fbox{%\r
 351 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 352 \textbf{New Key Live:}\r
 353 \begin{algorithmic}[1]\r
 354 \Function{NewKeyLive}{$newkey_s, ssn_r$}\r
 355     \State $API \gets \emptyset$   \Comment{Set of all Payload Items}\r
 356     \State $ANK \gets \emptyset$    \Comment{Set of all Payload Items that are new keys}\r
 357     \State $\tuple{k_s, vc_s, ssn_s, mid_s}\gets newkey_s$\\\r
 358     \r
 359     \If{$ssn_s = NULL$}                    \Comment{Make sure ssn is the correct one}\r
 360         \State $ssn_s \gets ssn_r$\r
 361     \EndIf\\\r
 362     \r
 363     \ForAll{record in R}\r
 364         \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
 365     \EndFor\\\r
 366     \r
 367     \ForAll{$\tuple{ssn', payload'}$ in $API$}\r
 368         \If{$payload'$ is a $newkey$}\r
 369             \State $ANK \gets ANK \cup \{\tuple{ssn', payload'}\}$   \Comment{Extract all new key payloads}\r
 370         \EndIf\r
 371     \EndFor\\\r
 372     \r
 373     \ForAll{$\tuple{ssn', \tuple{k_s', vc_s', ssn_s', mid_s'}}$ in $ANK$}\r
 374         \If{$vc_s' < vc_s$}\r
 375             \State \Return{False}\r
 376         \ElsIf{$\lnot (vc_s' < vc_s) \land (ssn_s' < ssn_s)$}\r
 377             \State \Return{False}\r
 378         \EndIf\r
 379     \EndFor \\\r
 380     \State \Return{True}\r
 381 \EndFunction\r
 382 \end{algorithmic}\r
 383 \end{varwidth}% \r
 384 }\r
 385 \r
 386 %Is Live\r
 387 \noindent\fbox{%\r
 388 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 389 \textbf{Is Live:}:\r
 390 \begin{algorithmic}[1]\r
 391 \Function{IsLive}{$item_s, ssn_S$}\r
 392     \If{$item_s$ is a $tansaction$}\r
 393         \State \Return{\Call{TransactionLive}{$item_s, ssn_s$}}\r
 394     \r
 395     \ElsIf{$item_s$ is a $commit$}\r
 396         \State \Return{\Call{CommitLive}{$item_s, ssn_s$}}\r
 397     \r
 398     \ElsIf{$item_s$ is a $abort$}\r
 399         \State \Return{\Call{AbortLive}{$item_s$}}\r
 400             \r
 401     \ElsIf{$item_s$ is a $delete$}\r
 402         \State \Return{\Call{DeleteLive}{$item_s, ssn_s$}}\r
 403         \r
 404     \ElsIf{$item_s$ is a $commit$}\r
 405         \State \Return{\Call{ResizeLive}{$item_s, ssn_s$}}\r
 406         \r
 407     \ElsIf{$item_s$ is a $sequence$}\r
 408         \State \Return{\Call{SequenceLive}{$item_s, ssn_s$}}\r
 409         \r
 410     \ElsIf{$item_s$ is a $newkey$}\r
 411         \State \Return{\Call{NewKeyLive}{$item_s, ssn_s$}}\r
 412         \r
 413     \ElsIf{$item_s$ is a $keyvalue$}\r
 414         \State \Return{\Call{KeyValueLive}{$item_s, ssn_s$}}\r
 415     \EndIf\\\r
 416     \r
 417     \State \Return{False}  \Comment{Will never get here}\r
 418 \EndFunction\r
 419 \end{algorithmic}\r
 420 \end{varwidth}% \r
 421 }\r
 422 \r
 423 %Record has live payload data\r
 424 \noindent\fbox{%\r
 425 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 426 \textbf{Record has live payload data:}:\r
 427 \begin{algorithmic}[1]\r
 428 \Function{HasLivePayload}{$record_s, ssn_s$}\r
 429     \State $\tuple{mid_s, vc_s, hmac_s, payload_s} \gets record_s$\r
 430     \ForAll{$item$ in $payload_s$}\r
 431         \If{\Call{IsLive}{$item, ssn_s$}}\r
 432             \State \Return{True}\r
 433         \EndIf\r
 434     \EndFor\r
 435     \State \Return{False}\r
 436 \EndFunction\r
 437 \end{algorithmic}\r
 438 \end{varwidth}% \r
 439 }\r
 440 \r
 441 % Get Data Structure Size\r
 442 \noindent\fbox{%\r
 443 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 444 \textbf{Get Data Structure Size:}\r
 445 \begin{algorithmic}[1]\r
 446 \Function{GetDataStrucSize}{ }\r
 447     \State $API \gets \emptyset$   \Comment{Set of all Payload Items}\r
 448     \State $AR \gets \emptyset$    \Comment{Set of all Payload Items that are resize}\r
 449 \r
 450     \ForAll{record in R}\r
 451         \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
 452     \EndFor\\\r
 453     \r
 454     \ForAll{$\tuple{ssn, payload}$ in $API$}\r
 455         \If{($payload$ is a $resize) \land$ \Call{IsLive}{$payload, ssn$}}\r
 456             \State $\tuple{size'} \gets payload$\r
 457             \State \Return{$size'$}\r
 458         \EndIf\r
 459     \EndFor\\\r
 460     \r
 461     \State \Return{$0$}  \Comment{Get Here only if data structure has no entries}\r
 462 \EndFunction\r
 463 \end{algorithmic}\r
 464 \end{varwidth}% \r
 465 }\r
 466 \r
 467 %Rescue Payload Items\r
 468 \noindent\fbox{%\r
 469 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 470 \textbf{Rescue Payload Items}:\r
 471 \begin{algorithmic}[1]\r
 472 \Function{RescuePayloadItems}{$payload_s$}\r
 473     \State $PIList =$ empty list of $\tuple{ssn, payload}$\r
 474     \State $SpaceRemaining = MaxPayloadSize - $ \Call{GetSize}{$payload_s$}\r
 475     \r
 476     \If{$SpaceRemaining = 0$}\r
 477         \Return{$payload_s$}\r
 478     \EndIf\\\r
 479     \r
 480     \ForAll{record in R}\r
 481         \State $PIList \gets PIList \cup$ \Call{GetPayloadItemsWithSSN}{$record$}\r
 482     \EndFor\\\r
 483     \r
 484     \State Sort $PIList$ by $ssn$ from lowest to highest\\\r
 485     \r
 486     \ForAll{$\tuple{ssn', payload'}$ in $PIList$}\r
 487         \If{\Call{IsLive}{$payload', ssn'$} $\land$ \Call{getRandomBoolean}{ } }\r
 488         \r
 489             \If{\Call{GetSize}{$payload'$} $ > SpaceRemaining$} \Comment{No more space for resuces in payload}\r
 490                 \State \Return{$payload_s$}\r
 491             \EndIf\r
 492             \r
 493             \State $SpaceRemaining \gets SpaceRemaining -$ \Call{GetSize}{$payload'$}\r
 494             \State $payload_s \gets payload_s \cup \{payload'\}$\r
 495         \EndIf\r
 496     \EndFor\\\r
 497     \State \Return{$payload_s$}\r
 498 \EndFunction\r
 499 \end{algorithmic}\r
 500 \end{varwidth}% \r
 501 }\r
 502 \r
 503 %Pad Payload\r
 504 \noindent\fbox{%\r
 505 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 506 \textbf{Pad Payload}:\r
 507 \begin{algorithmic}[1]\r
 508 \Function{PadPayload}{$payload_s$}    \State $SpaceRemaining =  MaxPayloadSize - $ \Call{GetSize}{$payload_s$}\r
 509     \r
 510     \If{$SpaceRemaining = 0$}\r
 511         \State \Return{$payload_s$}\r
 512     \EndIf\\\r
 513     \State \Return{$payload_s \gets payload_s \cup$ \Call{GenerateFiller}{$SpaceRemaining$}}\r
 514 \EndFunction\r
 515 \end{algorithmic}\r
 516 \end{varwidth}% \r
 517 }\r
 518 \r
 519 %Delete Records\r
 520 \noindent\fbox{%\r
 521 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 522 \textbf{Delete Records (Deletes n records)}:\r
 523 \begin{algorithmic}[1]\r
 524 \Function{Delete}{$num\_of\_records$}\r
 525     \State $RS \gets$ List of all Records sorted by ssn and has form $\tuple{ssn_s, record_s}$\r
 526     \State $n \gets 0$\\\r
 527         \r
 528     \ForAll{$\tuple{ssn_s, record_s}$ in $RS$}\r
 529         \If{\Call{HasLivePayload}{$record_s, ssn_s$}}\r
 530             \State \Return{False}\r
 531         \Else\r
 532             \State \Call{DeleteSlotServer}{$ssn_s$}\r
 533             \State $n \gets n + 1$\r
 534         \EndIf\\\r
 535         \r
 536         \If{$n = num\_of\_records$}\r
 537             \State \textbf{break}\r
 538         \EndIf\r
 539     \EndFor\\\r
 540     \r
 541     \State \Return{True}\r
 542     \r
 543 \EndFunction\r
 544 \end{algorithmic}\r
 545 \end{varwidth}% \r
 546 }\r
 547 \r
 548 %Create Resize Data Structure Payload Item\r
 549 \noindent\fbox{%\r
 550 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 551 \textbf{Create Resize Data Structure Payload Item:}\r
 552 \begin{algorithmic}[1]\r
 553 \Function{MakeResizePayload}{ }\r
 554     \State $rp \gets$ Empty $resize$ payload\r
 555     \State $cs \gets$ \Call{GetDataStrucSize}{ }\r
 556     \State $rp \gets \tuple{cs * 2}$\r
 557     \State \Return{$\{rp\}$}\r
 558 \EndFunction\r
 559 \end{algorithmic}\r
 560 \end{varwidth}% \r
 561 }\r
 562 \r
 563 %Get Arbitrator\r
 564 \noindent\fbox{%\r
 565 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 566 \textbf{Get Arbitrator:}\r
 567 \begin{algorithmic}[1]\r
 568 \Function{GetArbitrator}{$key$}\r
 569     \State $API \gets \emptyset$   \Comment{Set of all Payload Items}\\\r
 570 \r
 571     \ForAll{record in R}\r
 572         \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
 573     \EndFor\\\r
 574     \r
 575     \ForAll{$\tuple{ssn, payload}$ in $API$}\r
 576         \If{($payload$ is a $newkey) \land$ \Call{IsLive}{$payload, ssn$}}\r
 577             \State $\tuple{k', vc', ssn', mid'} \gets payload$\r
 578             \r
 579             \If{$k' = key$}\r
 580                 \State \Return{$mid'$}\r
 581             \EndIf\r
 582         \EndIf\r
 583     \EndFor\\\r
 584     \State \Call{Error}{No arbitrator for key: $key$}\r
 585 \EndFunction\r
 586 \end{algorithmic}\r
 587 \r
 588 \begin{algorithmic}[1]\r
 589 \Function{GetArbitrator}{$guard$}\r
 590     \State $API \gets \emptyset$   \Comment{Set of all Payload Items}\r
 591     \State $\tuple{kvSet, condition} \gets guard$\\\r
 592     \r
 593     \ForAll{record in R}\r
 594         \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
 595     \EndFor\\\r
 596     \r
 597     \ForAll{$\tuple{key, value}$ in $kvSet$}\r
 598         \ForAll{$\tuple{ssn, payload}$ in $API$}\r
 599             \If{($payload$ is a $newkey) \land$ \Call{IsLive}{$payload, ssn$}}\r
 600                 \State $\tuple{k', vc', ssn', mid'} \gets payload$\r
 601                 \If{$k' = key$}\r
 602                     \State \Return{$mid'$}\r
 603                 \EndIf\r
 604             \EndIf\r
 605         \EndFor\r
 606     \EndFor\\\r
 607     \State \Call{Error}{No arbitrator for key: $key$}\r
 608 \EndFunction\r
 609 \end{algorithmic}\r
 610 \r
 611 \end{varwidth}% \r
 612 }\r
 613 \r
 614 %Insert Payload\r
 615 \noindent\fbox{%\r
 616 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 617 \textbf{Insert Payload:}\r
 618 \begin{algorithmic}[1]\r
 619 \Function{InsertPayload}{$payload_s$}\r
 620     \r
 621     \State $numOfRecords \gets |R|+1$\r
 622     \State $targetSize \gets $ \Call{GetDataStrucSize}{ }\r
 623     \State $numToDelete \gets numOfRecords - targetSize$\r
 624     \State $rp \gets NULL$\r
 625     \State $hmac \gets NULL$\r
 626     \State $vc \gets NULL$\r
 627     \State $record \gets NULL$\\\r
 628 \r
 629     \If{\Call{GetSize}{$payload_s$} $> MaxPayloadSize$}\r
 630         \State \Call{Error}{Payload too large}\r
 631     \EndIf\\\r
 632     \r
 633     \If{$numToDelete > 0$}\r
 634         \If{$\lnot$\Call{Delete}{$numToDelete$}}\r
 635             \State $rp \gets$\Call{MakeResizePayload}{ }\r
 636             \If{\Call{GetSize}{$payload_s \cup rp$} $> MaxPayloadSize$}\r
 637                 \State \Call{InsertPayload}{$rp$}\r
 638             \Else\r
 639                 \State $payload_s \gets payload_s \cup rp$\r
 640             \EndIf\r
 641         \EndIf\r
 642     \EndIf\\\r
 643     \r
 644     \State $payload_s \gets$ \Call{RescuePayloadItems}{$payload_s$}\r
 645     \State $payload_s \gets$ \Call{PadPayload}{$payload_s$}\r
 646     \State $vc \gets $ \Call{GenerateVectorClock}{ }\r
 647     \State $hmac \gets$ \Call{GenerateHmac}{$mid, vc, payload_s$}\r
 648     \State $record \gets \tuple{mid,vc,hmac,payload}$\r
 649     \State $record \gets $\Call{Encrypt}{$record$}\r
 650     \State \Call{PutSlotServer}{$record$}\r
 651 \EndFunction\r
 652 \end{algorithmic}\r
 653 \end{varwidth}% \r
 654 }\r
 655 \r
 656 %Check Data Structure for Malicious Activity\r
 657 %\noindent\fbox{%\r
 658 %\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 659 \textbf{Check Data Structure for Malicious Activity:}\r
 660 \begin{algorithmic}[1]\r
 661 \Function{CheckDataStructForValidity}{ }\r
 662     \State $API \gets \emptyset$   \Comment{Set of all Payload Items}\r
 663     \State $ASeq \gets \emptyset$   \Comment{Set of all Payload Items that are sequences}\r
 664     \State $MID \gets \emptyset$   \Comment{Set of all machine IDs}\r
 665     \State $midClocks \gets \emptyset$ \Comment{Set of all clocks for the same machine IDs}\r
 666     \State $oldestDeletedSsn \gets NULL$\r
 667     \State $didFindSsn \gets False$\r
 668     \State $didFindClock \gets False$\r
 669     \State $hmac \gets NULL$\\\r
 670     \r
 671     \State Sort $R$ by $ssn$ from smallest $ssn$ to largest $ssn$\\\r
 672     \r
 673     \ForAll{record in R}\r
 674         \State $\tuple{ssn',\tuple{mid', vc', hmac', payload'}} \gets record$\r
 675         \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
 676         \State $MID \gets MID \cup \{mid'\}$\r
 677     \EndFor\\\r
 678 \r
 679     \ForAll{$record$ in $R$} \Comment{Check HMACs are all valid}\r
 680         \State $\tuple{ssn',\tuple{mid', vc', hmac', payload'}} \gets record$\r
 681         \State $hmac \gets $ \Call{GenerateHmac}{$mid', vc', payload'$}\r
 682         \If{$hmac \neq hmac'$}\r
 683             \State \Call{Error}{HMAC mismatch}\r
 684         \EndIf\r
 685     \EndFor\\\r
 686     \r
 687     \ForAll{$record_1$ in $R$} \Comment{Check no SSN duplicates}\r
 688         \State $\tuple{ssn_1,rData_1} \gets record_1$\r
 689         \ForAll{$record_2$ in $R$}\r
 690             \If{$record_2 \neq record_1$}\r
 691                \State $\tuple{ssn_2,rData_2} \gets record_2$\r
 692                \If{$ssn_2 = ssn_1$}\r
 693                     \State \Call{Error}{Duplicate SSN for different records}\r
 694                \EndIf\r
 695             \EndIf\r
 696         \EndFor\r
 697     \EndFor\\\r
 698     \r
 699     \r
 700     \ForAll{$record_1$ in $R[0:-1]$} \Comment{Check for missing SSN}\r
 701         \State $\tuple{ssn_1,rData_1} \gets record_1$\r
 702         \State $didFindSsn \gets False$\r
 703         \ForAll{$record_2$ in $R[1:]$}\r
 704             \State $\tuple{ssn_2,rData_2} \gets record_2$\r
 705             \If{$ssn_2 = (ssn_1 + 1)$}\r
 706                 \State $didFindSsn \gets True$\r
 707                 \State Break\r
 708             \EndIf\r
 709         \EndFor\r
 710         \r
 711         \If{$\lnot didFindSsn$}\r
 712             \State \Call{Error}{Missing SSN in SSN sequence.}\r
 713         \EndIf\r
 714     \EndFor\\\r
 715     \r
 716      \ForAll{$\tuple{ssn, payload}$ in $API$}\r
 717         \If{($payload$ is a $delete) \land$ \Call{IsLive}{$payload, ssn$}}\r
 718             \State $\tuple{ssn'} \gets payload$\r
 719             \State $oldestDeleteSsn \gets ssn'$\r
 720         \ElsIf{($payload$ is a $sequence) \land$ \Call{IsLive}{$payload, ssn$}}\r
 721             \State $ASeq \gets ASeq \cup \{payload\}$\r
 722         \EndIf\r
 723     \EndFor\\\r
 724     \r
 725     \r
 726     \ForAll{$record$ in $R$} \Comment{Check SSN's are all valid}\r
 727         \State $\tuple{ssn, rData} \gets record$\r
 728         \ForAll{$\tuple{rid', ssn'}$ in $ASeq$}\r
 729             \If{$(rid' =$ \Call{GetRid}{$record$}$) \land ssn' \neq ssn$}\r
 730                 \State \Call{Error}{SSN mismatch}\r
 731             \EndIf\r
 732         \EndFor\r
 733     \EndFor\\\r
 734     \r
 735     \r
 736     \State $\tuple{ssn, payload} \gets R[0]$ \Comment{Get first record in the sorted R}\r
 737     \If{$ssn > (oldestDeleteSsn + 1) $}\r
 738         \State \Call{Error}{Missing records}\r
 739     \EndIf\\\r
 740     \r
 741     \r
 742     \ForAll{$mid$ in $MID$}\r
 743         \State $midClocks \gets \emptyset$\r
 744         \r
 745         \ForAll{record in R}\r
 746             \State $\tuple{ssn',\tuple{mid', vc', hmac', payload'}} \gets record$\r
 747             \If{$mid' = mid$}\r
 748                 \State $\tuple{c_{mid_1}, c_{mid_2},...,c_{mid_k}} \gets vc'$\r
 749                 \State $midClocks \gets midClocks \cup \{c_{mid_n}|mid_n=mid\}$\r
 750             \EndIf\r
 751         \EndFor\\\r
 752         \r
 753         \State Sort $midClocks$ from smallest clock to largest clock\\\r
 754         \r
 755         \ForAll{$c_1$ in $midClocks[0:-1]$} \Comment{Check for missing SSN}\r
 756             \State $didFindSsn \gets False$\r
 757             \ForAll{$c_2$ in $midClocks[1:]$}\r
 758                 \If{$c_2 = (c_1 + 1)$}\r
 759                     \State $didFindClock\gets True$\r
 760                     \State Break\r
 761                 \EndIf\r
 762             \EndFor\r
 763         \EndFor\r
 764         \r
 765         \If{$\lnot didFindClock$}\r
 766             \State \Call{Error}{Missing clock in clock sequence for: $mid$.}\r
 767         \EndIf\r
 768     \EndFor\\\r
 769     \r
 770     \State \Comment{If got here then data structure is valid}\r
 771 \EndFunction\r
 772 \end{algorithmic}\r
 773 %\end{varwidth}% \r
 774 %}\r
 775 \r
 776 \r
 777 \r
 778 \r
 779 \textbf{Transaction Live}:\\\r
 780 \textbf{Commit Live}:\\\r
 781 \textbf{Key Value Live}:\\\r
 782 \r
 783 \r
 784 %-Rescues\r
 785 %    - Need to Change Transaction sizes\r
 786 %    - Need to Change New Key ssn in transaction\r
 787 %-Gets\r
 788 %-Arbitration\r
 789 %   - Insert Commit\r
 790 %-Check Data Structure\r
 791 \r
 792 \r
 793 \r
 794 \subsection{\textbf{Create new key}}\r
 795 \noindent\fbox{%\r
 796 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 797 \textbf{Create new key:}\r
 798 \begin{algorithmic}[1]\r
 799 \Function{CreateNewKey}{$keyName, mid$}\r
 800     \State $vc \gets $ \Call{GenerateVectorClock}{ }\r
 801     \State $newKeyPayload \gets \tuple{keyName, vc, NULL, mid}$\r
 802     \State $API \gets \emptyset$   \Comment{Set of all Payload Items}\\\r
 803 \r
 804     \State \Call{GetLatestDataStruct}{ } \Comment{Update local version of data struct}\\\r
 805 \r
 806     \ForAll{record in R}\r
 807         \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
 808     \EndFor\\\r
 809     \r
 810     \ForAll{$\tuple{ssn, payload}$ in $API$}\r
 811         \If{($payload$ is a $newkey) \land$ \Call{IsLive}{$payload, ssn$}}\r
 812             \State $\tuple{k', vc', ssn', mid'} \gets payload$\r
 813             \r
 814             \If{$k' = key$}\r
 815                 \State \Return{False}\r
 816             \EndIf\r
 817         \EndIf\r
 818     \EndFor\\\r
 819     \r
 820     \State \Call{InsertPayload}{$newKeyPayload$}\r
 821     \State \Return{True}\r
 822 \EndFunction\r
 823 \end{algorithmic}\r
 824 \end{varwidth}% \r
 825 }\r
 826 \r
 827 \subsection{\textbf{Put Transaction}}\r
 828 This operation puts a transaction into the data structure if this transaction fits inside a payload.\r
 829 If by adding this transaction the data structure size exceeds the proposed max data structure size then deletes take place.  If no deletes can take place (too much live data) then the data structure is resized.\\\r
 830 \r
 831 %\r
 832 \noindent\fbox{%\r
 833 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 834 \textbf{Put Transaction:}\r
 835 \begin{algorithmic}[1]\r
 836 \Function{PutTransaction}{$kVUpdates, guard$}\r
 837     \State $mid \gets NULL$\r
 838     \State $vc \gets $ \Call{GenerateVectorClock}{ }\r
 839     \State $transPayload \gets NULL$\\\r
 840 \r
 841     \State \Call{GetLatestDataStruct}{ } \Comment{Update local version of data struct}\\\r
 842 \r
 843     \ForAll{$kv$ in $kVUpdates$}\r
 844         \State $\tuple{k', v'} \gets kv$\r
 845         \r
 846         \If{$mid = NULL$}\r
 847             \State $mid \gets$ \Call{GetArbitrator}{$k'$}\r
 848         \ElsIf{$mid \neq $ \Call{GetArbitrator}{$k'$}}\r
 849             \State \Call{Error}{Multiple Arbitrators}\r
 850         \EndIf\r
 851     \EndFor\\\r
 852     \r
 853     \If{\Call{GetArbitrator}{$guard$} $\neq mid$}\r
 854         \State \Call{Error}{Multiple Arbitrators}\r
 855     \EndIf\\\r
 856     \r
 857     \State $transPayload \gets \tuple{mid, vc, kVUpdates, guard}$\r
 858     \State \Call{InsertPayload}{$transPayload$}\r
 859 \EndFunction\r
 860 \end{algorithmic}\r
 861 \end{varwidth}% \r
 862 }\r
 863 \r
 864 \subsection{\textbf{Get key-value pair}}\r
 865 \r
 866 \r
 867 \r
 868 \r
 869 \r
 870 \r
 871 \end{document}\r