--- /dev/null
+\documentclass[11pt]{article}\r
+\newcommand{\tuple}[1]{\ensuremath \langle #1 \rangle}\r
+\usepackage{color}\r
+\usepackage{amsthm}\r
+\usepackage{amsmath}\r
+\usepackage{graphicx}\r
+\usepackage{mathrsfs}\r
+\usepackage{amssymb}\r
+\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx\r
+\usepackage[all]{xy}\r
+\usepackage{varwidth}\r
+\r
+\newtheorem{theorem}{Theorem}\r
+\newtheorem{prop}{Proposition}\r
+\newtheorem{lem}{Lemma}\r
+\newtheorem{defn}{Definition}\r
+\newcommand{\note}[1]{{\color{red} \bf [[#1]]}}\r
+\newcommand{\push}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}\r
+\newcommand*\xor{\mathbin{\oplus}}\r
+\begin{document}\r
+\r
+\r
+\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text\r
+\r
+\r
+\section{\textbf{Introduction}}\r
+\r
+\r
+\r
+\r
+\r
+\section{\textbf{Server}}\r
+The server maintains a collection of slots such that each slot contains some data.\r
+The operations on the slot are as follows:\r
+\begin{itemize}\r
+ \item Put slot\r
+ \item Get slot\r
+ \item Delete Slot\r
+\end{itemize}\r
+\r
+\subsection{\textbf{Server Notation Conventions}}\r
+$s \in SN$ is a server sequence number\\\r
+$sv \in SV$ is a slot's value\\\r
+$slot_s = \tuple{s, sv} \in SL \subseteq SN \times SV$\r
+\r
+\subsection{\textbf{Server State}}\r
+\textit{n = current server sequence number}\\\r
+\textit{SL = set of live slots on the server}\\\r
+\r
+\textbf{Initial Server State}\\\r
+$SL = \emptyset$\\\r
+$n = 0$\r
+\r
+\subsection{\textbf{Put Slot}}\r
+Put slot is an operation that inserts data into a new slot at the server.\\\r
+\r
+%Put Function\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Put Function:}\r
+\begin{algorithmic}[1]\r
+\Function{PutSlotServer}{$sv_p$}\r
+ \State $s_p \gets n$\r
+ \State $n \gets n + 1$\r
+ \State $SL \gets SL \cup \{\tuple{s_p,sv_p}\}$\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\subsection{\textbf{Get Slot}}\r
+Get slot is an operation that returns all server slots that are greater than some server sequence number.\\\r
+\r
+% Get Function\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get Function:}\r
+\begin{algorithmic}[1]\r
+\Function{GetSlotServer}{$s_g$}\r
+ \State \Return{$\{\tuple{s, sv} \in SL \mid s \geq s_g\}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\subsection{\textbf{Delete Slot}}\r
+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
+\r
+%Delete Function\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Delete Function:}\r
+\begin{algorithmic}[1]\r
+\Function{DeleteSlotServer}{$s_d$}\r
+ \State $SD \gets \{\tuple{s, sv} \in SL \mid s \leq s_g\}$\r
+ \State $SL \gets SL - SD$\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\r
+\r
+\r
+\section{\textbf{Client}}\r
+The data structure acts as a key store where key-value pairs can be read and set.\r
+The data structure exposes the following functions:\r
+\begin{itemize}\r
+ \item Put Transaction\r
+ \item Get key-value pair\r
+ \item Create new key\r
+\end{itemize}\r
+\r
+\r
+\subsubsection{\textbf{Types of Payloads}}\r
+The different types of record payloads are:\r
+\begin{itemize}\r
+ \item Transactions\r
+ \begin{itemize}\r
+ \item Used to make updates to key value pairs.\r
+ \end{itemize}\r
+ \item Commit notifications\r
+ \begin{itemize}\r
+ \item Contains the commit of a single transaction, the whole transaction.\r
+ \item There is 1 commit per transaction.\r
+ \item Generated by the arbitrator for the set of key-value gets and sets in the transaction.\r
+ \end{itemize}\r
+ \item Abort notifications\r
+ \begin{itemize}\r
+ \item Causes a transaction to be aborted, key-values not used in updates.\r
+ \end{itemize}\r
+ \item Data structure re-size notifications\r
+ \begin{itemize}\r
+ \item Contains new size of data structure (number of record allowed in the data structure or something like that).\r
+ \end{itemize}\r
+ \item Server sequence number confirmations.\r
+ \begin{itemize}\r
+ \item Created by any device if that device finds a record with a server sequence number that does not have a server sequence number conformation yet.\r
+ \end{itemize}\r
+ \item Delete notifications\r
+ \begin{itemize}\r
+ \item Generated when a device deletes a record.\r
+ \item records the record that was last deleted\r
+ \end{itemize}\r
+ \item New Key notification\r
+ \begin{itemize}\r
+ \item Generated when a device generates a new (never used) key-value pair.\r
+ \end{itemize}\r
+\end{itemize}\r
+\r
+\subsection{\textbf{Client Notation Conventions}}\r
+\r
+$K$ is the set of all keys.\\\r
+$MID$ is the set of the machine IDs of the devices that are in the system.\r
+$K_{mid}$ is a set of all keys that have device mid as the arbitrator\\\r
+$ssn_s$ is the server sequence number of a record $s$\\\r
+$mid_s \in MID$ is the machine ID for the device that created $record_s$.\\\r
+$hmac_s$ is the HMAC of $record_s$\\\r
+$c_{mid}$ is the latest read clock for a device with machine ID $mid$\\\r
+$vc_s = \{c_{mid} | mid \in MID\}$\\\r
+$rid_s = \tuple{mid_s, c_{mid_s}}$\r
+$k$ is a key entry\\\r
+$v$ is a value entry\\\r
+$kv_n$ is a key-value entry $\tuple{k_n,v_n} , k \in K$\\\r
+\r
+$tid_s = \tuple{mid_s,c_{mid_s}}$\\\r
+$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
+$transaction_s = \tuple{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
+$commit_s = \tuple{tid_s,vc_s}$\\\r
+$abort_s = \tuple{tid_s,mid_s,vc_s}$\\\r
+$sequence_s = \tuple{rid_s, ssn_s}$\\\r
+$delete_s = \tuple{ssn_d}$\\\r
+$resize_s = \tuple{x | x \in \mathbb{N}}$\\\r
+$newkey_s = \tuple{k_s, vc_s, ssn_s$ or $NULL, mid_s}$\\\r
+\r
+$payload_s = \{x_1, x_2,..., x_k | \forall k, x_k \in \{$transaction, commit, abort, resize, newkey, sequence, delete$\}\}$\\\r
+$rd_s = \tuple{mid_s, vc_s, hmac_s, payload_s}$ \\\r
+$record_s = \tuple{ssn_s,rd_s}$\\\r
+\r
+\subsection{\textbf{Client State}}\r
+\textit{s = largest server sequence number pulled from the server by a device} \\\r
+\textit{R = set of records pulled from the server so far with their server sequence numbers} \\\r
+\r
+\subsection{Helper Functions}\r
+The following helper functions are needed:\\\r
+\r
+% Error\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{ Error:}\r
+\begin{algorithmic}[1]\r
+\Function{Error}{$msg$}\r
+ \State $Print(msg)$\r
+ \State $Halt()$\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Get Payload Items from Record with SSN\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get Payload Items from Record with SSN}:\r
+\begin{algorithmic}[1]\r
+\Function{GetPayloadItemsWithSSN}{$record_s$}\r
+ \State $PISSN \gets \emptyset$ \Comment{Set of Payload Items with ssn}\r
+ \State $\tuple{ssn_s, rd_s} \gets record_s$\r
+ \State $\tuple{mid_s, vc_s, hmac_s, payload_s} \gets rd_s$\\\r
+ \r
+ \ForAll{$payloadItems$ in $payload_s$}\r
+ \State $PISSN \gets PISSN \cup \{\tuple{payloadItem, ssn_s}\}$\r
+ \EndFor\\\r
+ \r
+ \State \Return {$PISSN$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Get rid of record\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get rid of record:}\r
+\begin{algorithmic}[1]\r
+\Function{GetRid}{$record_s$}\r
+ \State $\tuple{ssn_s, \tuple{mid_s, \{c_{mid_1}, c_{mid_2}, ... , c_{mid_k}\}, hmac_s, payload_s}} \gets record_s$\r
+ \State \Return {$\tuple{mid_s, c_{mid_s}}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Get tid of transaction\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get tid of transaction:}\r
+\begin{algorithmic}[1]\r
+\Function{GetTid}{$transaction_s$}\r
+ \State $\tuple{ssn_s,\{c_{mid_1}, c_{mid_2}, ... , c_{mid_k}\}, \{kv_1, kv_2,...kv_n\}, guard_s} \gets record_s$\r
+ \State \Return {$\tuple{mid_s, c_{mid_s}}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Key Value Live\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Key Value Live:}\r
+\begin{algorithmic}[1]\r
+\Function{KeyValueLive}{$keyName_s, transaction_s$}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $AT \gets \emptyset$ \Comment{Set of all Payload Items that are transactions}\r
+ \State $AC \gets \emptyset$ \Comment{Set of all Payload Items that are commits}\r
+ \State $AA \gets \emptyset$ \Comment{Set of all Payload Items that are aborts}\r
+ \State $commitTrans = NULL$\r
+ \State $tid \gets $ \Call{GetTid}{$transaction_s$}\\\r
+\r
+ \ForAll{$record$ in $R$}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{$payload$ is a $transaction$}\r
+ \State $AT \gets AT \cup \{payload\}$\r
+ \ElsIf{$payload$ is a $commit$}\r
+ \State $AC \gets AC \cup \{payload\}$\r
+ \ElsIf{$payload$ is a $abort$}\r
+ \State $AA \gets AA \cup \{payload\}$\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{tid',mid',vc'}$ in $AA$} \Comment{Has an abort}\r
+ \If{$tid' = tid$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \EndFor\\\r
+\r
+ \ForAll{$\tuple{tid',vc'}$ in $AC$} \Comment{Has a commit}\r
+ \If{$tid' = tid$}\r
+ \State $commitTrans \gets \tuple{tid',vc'}$\r
+ \State Break\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \If{$commitTrans = NULL$} \r
+ \State \Return{True} \Comment{If transaction not yet committed then alive}\r
+ \EndIf\\\r
+ \r
+ \State $\tuple{tid_c, vc_c} \gets commitTrans$\r
+ \ForAll{$trans$ in $AT$}\r
+ \State $\{mid_t,vc_t ,\{\tuple{k_1, v_1}, \tuple{k_2, v_2},..., \tuple{k_k, v_k}\},guard_t\} \gets trans$\r
+ \If{$(trans \neq transaction_s) \land (keyName_s = k_n)$}\r
+ \ForAll{$\tuple{tid_c',vc_c'}$ in $AC$}\r
+ \If{$(tid_c = $ \Call{GetTid}{$trans$} $) \land (vc_c' > vc_c)$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \EndFor\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State \Return{True}\r
+ \r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+%Sequence Live\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Sequence Live}:\r
+\begin{algorithmic}[1]\r
+\Function{SequenceLive}{$sequence_s, ssn_{s1}$}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $AS \gets \emptyset$ \Comment{Set of all Payload Items that are sequences}\r
+ \State $StillHasRecord \gets False$\r
+ \State $\tuple{rid_s, ssn_{s2}} \gets sequence_s$\\\r
+ \r
+ \ForAll{$record$ in $R$}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \If{$rid_s = $\Call{GetRid}{$record$}}\r
+ \State $StillHasRecord \gets True$\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \If{$\lnot StillHasRecord$} \Comment{The Record does not exists anymore}\r
+ \State \Return{False}\r
+ \EndIf\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{$payload$ is a $sequence$}\r
+ \State $AS \gets AS \cup \{\tuple{ssn, payload}\}$ \Comment{Extract all sequence payloads}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn_1', \tuple{rid', ssn_2'}}$ in $AS$}\r
+ \If{$(rid'=rid_s) \land (ssn_1' > ssn_{s_1})$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \EndFor \\\r
+ \State \Return{True}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Delete Live\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Delete Live}:\r
+\begin{algorithmic}[1]\r
+\Function{DeleteLive}{$delete_s, ssn_s$}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $AD \gets \emptyset$ \Comment{Set of all Payload Items that are deletes}\r
+ \State $\tuple{ssn_d} \gets delete_s$\\\r
+ \r
+ \ForAll{record in R}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{$payload$ is a $delete$}\r
+ \State $AD \gets AD \cup \{\tuple{ssn, payload}\}$ \Comment{Extract all delete payloads}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \ForAll{delete in AD}\r
+ \State $\tuple{{ssn_s}', \tuple{{ssn_d}'}} \gets delete$\r
+ \If{${ssn_d}' > ssn_d$} \Comment{More recently deleted record}\r
+ \State \Return{False}\r
+ \ElsIf{$({ssn_d}'= ssn_d) \land ({ssn_s}' > ssn_s)$} \Comment{More recent delete of same record}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \EndFor \\\r
+ \State \Return{True}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Abort Live\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Abort Live}:\r
+\begin{algorithmic}[1]\r
+\Function{AbortLive}{$abort_s$}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $tid \gets NULL$\r
+ \State $\tuple{tid_s,mid_s,vc_s} \gets abort_s$\\\r
+\r
+ \ForAll{$record$ in $R$}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$} \Comment{Transaction still in data structure}\r
+ \If{$payload$ is a $transaction$}\r
+ \State $tid \gets $\Call{GetTid}{$payload$}\r
+ \If{$tid = tid_s$}\r
+ \State Return{True}\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \r
+ \r
+ \ForAll{record in R}\r
+ \State $\tuple{ssn_s',\tuple{mid_s', vc_s', hmac_s', payload_s'}} \gets record$\r
+ \If{$(mid_s'=mid_s) \land (vc_s' > vc_s)$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \EndFor\\\r
+ \State \Return{True}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Resize Live\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Resize Live}:\r
+\begin{algorithmic}[1]\r
+\Function{ResizeLive}{$resize_s, ssn_s$}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $AR \gets \emptyset$ \Comment{Set of all Payload Items that are resize}\r
+ \State $\tuple{size} \gets resize_s$\\\r
+ \r
+ \ForAll{record in R}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{$payload$ is a $resize$}\r
+ \State $AR \gets AR \cup \{\tuple{ssn, payload}\}$ \Comment{Extract all resize payloads}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn', \tuple{size'}}$ in $AR$}\r
+ \If{$size' > size$}\r
+ \State \Return{False}\r
+ \ElsIf{$(size'=size) \land (ssn' > ssn_s)$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \EndFor \\\r
+ \State \Return{True}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%New Key Live\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{New Key Live:}\r
+\begin{algorithmic}[1]\r
+\Function{NewKeyLive}{$newkey_s, ssn_r$}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $ANK \gets \emptyset$ \Comment{Set of all Payload Items that are new keys}\r
+ \State $\tuple{k_s, vc_s, ssn_s, mid_s}\gets newkey_s$\\\r
+ \r
+ \If{$ssn_s = NULL$} \Comment{Make sure ssn is the correct one}\r
+ \State $ssn_s \gets ssn_r$\r
+ \EndIf\\\r
+ \r
+ \ForAll{record in R}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn', payload'}$ in $API$}\r
+ \If{$payload'$ is a $newkey$}\r
+ \State $ANK \gets ANK \cup \{\tuple{ssn', payload'}\}$ \Comment{Extract all new key payloads}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn', \tuple{k_s', vc_s', ssn_s', mid_s'}}$ in $ANK$}\r
+ \If{$vc_s' < vc_s$}\r
+ \State \Return{False}\r
+ \ElsIf{$\lnot (vc_s' < vc_s) \land (ssn_s' < ssn_s)$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \EndFor \\\r
+ \State \Return{True}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Transaction Live\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Transaction Live:}\r
+\begin{algorithmic}[1]\r
+\Function{TransactionLive}{$transaction_s$}\r
+ \State $AA \gets \emptyset$ \Comment{Set of all Payload Items that are aborts}\r
+ \State $AC \gets \emptyset$ \Comment{Set of all Payload Items that are commits}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $tid \gets $ \Call{GetTid}{$transaction_s$}\r
+ \State $foundCommit \gets False$\\\r
+ \r
+ \ForAll{$record$ in $R$}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{$payload$ is a $abort$}\r
+ \State $AA \gets AA \cup \{payload\}$\r
+ \ElsIf{$payload$ is a $commit$}\r
+ \State $AC \gets AC \cup \{payload\}$\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{tid',mid',vc'}$ in $AA$} \Comment{There is an abort}\r
+ \If{$tid' = tid$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{tid',vc'}$ in $AC$} \Comment{There is no commit}\r
+ \If{$tid' = tid$}\r
+ \State $foundCommit \gets True$\r
+ \State Break\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \If{$\lnot foundCommit$}\r
+ \State \Return{True}\r
+ \EndIf\\\r
+ \r
+ \State $\tuple{mid',vc' ,kvSet',guard'} \gets transaction_s$ \Comment{All Keys are dead}\r
+ \ForAll{$\tuple{k',v'}$ in $kvSet'$}\r
+ \If{\Call{KeyValueLive}{$k', transaction_s$}}\r
+ \State \Return{True}\r
+ \EndIf\r
+ \EndFor\r
+\r
+ \State \Return{False}\r
+\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Commit Live\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Commit Live:}\r
+\begin{algorithmic}[1]\r
+\Function{CommitLive}{$commit_s, ssn_s$}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $AT \gets \emptyset$ \Comment{Set of all Payload Items that are transaction}\r
+ \State $tid' \gets NULL$ \r
+ \State $\tuple{tid, vc} \gets commit_s$ \\ \r
+\r
+ \ForAll{$record$ in $R$}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{$payload$ is a $transaction$}\r
+ \State $tid' \gets$ \Call{GetTid}{$payload$}\r
+ \If{$tid' = tid$}\r
+ \State \Return{True}\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\\\r
+\r
+ \State \Return{False}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Is Live\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Is Live:}:\r
+\begin{algorithmic}[1]\r
+\Function{IsLive}{$item_s, ssn_S$}\r
+ \If{$item_s$ is a $tansaction$}\r
+ \State \Return{\Call{TransactionLive}{$item_s$}}\r
+ \r
+ \ElsIf{$item_s$ is a $commit$}\r
+ \State \Return{\Call{CommitLive}{$item_s, ssn_s$}}\r
+ \r
+ \ElsIf{$item_s$ is a $abort$}\r
+ \State \Return{\Call{AbortLive}{$item_s$}}\r
+ \r
+ \ElsIf{$item_s$ is a $delete$}\r
+ \State \Return{\Call{DeleteLive}{$item_s, ssn_s$}}\r
+ \r
+ \ElsIf{$item_s$ is a $commit$}\r
+ \State \Return{\Call{ResizeLive}{$item_s, ssn_s$}}\r
+ \r
+ \ElsIf{$item_s$ is a $sequence$}\r
+ \State \Return{\Call{SequenceLive}{$item_s, ssn_s$}}\r
+ \r
+ \ElsIf{$item_s$ is a $newkey$}\r
+ \State \Return{\Call{NewKeyLive}{$item_s, ssn_s$}}\r
+ \r
+ \ElsIf{$item_s$ is a $keyvalue$}\r
+ \State \Return{\Call{KeyValueLive}{$item_s, ssn_s$}}\r
+ \EndIf\\\r
+ \r
+ \State \Return{False} \Comment{Will never get here}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Record has live payload data\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Record has live payload data:}:\r
+\begin{algorithmic}[1]\r
+\Function{HasLivePayload}{$record_s, ssn_s$}\r
+ \State $\tuple{mid_s, vc_s, hmac_s, payload_s} \gets record_s$\r
+ \ForAll{$item$ in $payload_s$}\r
+ \If{\Call{IsLive}{$item, ssn_s$}}\r
+ \State \Return{True}\r
+ \EndIf\r
+ \EndFor\r
+ \State \Return{False}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+% Get Data Structure Size\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get Data Structure Size:}\r
+\begin{algorithmic}[1]\r
+\Function{GetDataStrucSize}{ }\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $AR \gets \emptyset$ \Comment{Set of all Payload Items that are resize}\r
+\r
+ \ForAll{record in R}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{($payload$ is a $resize) \land$ \Call{IsLive}{$payload, ssn$}}\r
+ \State $\tuple{size'} \gets payload$\r
+ \State \Return{$size'$}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State \Return{$0$} \Comment{Get Here only if data structure has no entries}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Rescue New Key\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Rescue New Key:}\r
+\begin{algorithmic}[1]\r
+\Function{RescueNewKey}{$newKeyPayload, ssn$}\r
+ \State $\tuple{k', vc', ssn', mid'} \gets newKeyPayload$\r
+ \State \Return{$\tuple{k', vc', ssn, mid'}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Rescue Transaction\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Rescue New Key:}\r
+\begin{algorithmic}[1]\r
+\Function{RescueTransaction}{$transPayload, ssn$}\r
+ \State $KVRescue \gets \emptyset$\r
+ \State $\tuple{mid',vc', KVSet,guard_s} \gets transPayload$\\\r
+ \r
+ \ForAll{$\tuple{k,v}$ in $KVSet$}\r
+ \If{\Call{KeyValueLive}{$k, transPayload$}}\r
+ \State $KVRescue \gets KVRescue \cup \{\tuple{k,v}\}$\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State \Return{$\tuple{mid',vc', KVRescue,guard_s}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\r
+%Rescue Payload Items\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Rescue Payload Items}:\r
+\begin{algorithmic}[1]\r
+\Function{RescuePayloadItems}{$payload_s$}\r
+ \State $PIList =$ empty list of $\tuple{ssn, payload}$\r
+ \State $SpaceRemaining = MaxPayloadSize - $ \Call{GetSize}{$payload_s$}\r
+ \r
+ \If{$SpaceRemaining = 0$}\r
+ \Return{$payload_s$}\r
+ \EndIf\\\r
+ \r
+ \ForAll{record in R}\r
+ \State $PIList \gets PIList \cup$ \Call{GetPayloadItemsWithSSN}{$record$}\r
+ \EndFor\\\r
+ \r
+ \State Sort $PIList$ by $ssn$ from lowest to highest\\\r
+ \r
+ \ForAll{$\tuple{ssn', payload'}$ in $PIList$}\r
+ \If{\Call{IsLive}{$payload', ssn'$} $\land$ \Call{getRandomBoolean}{ } }\\\r
+ \r
+ \If{$payload'$ is a $newkey$}\r
+ \State $payload' \gets $ \Call{RescueNewKey}{$payload'$}\r
+ \ElsIf{$payload'$ is a $transaction$}\r
+ \State $payload' \gets $ \Call{RescueTransaction}{$payload'$}\r
+ \EndIf\\\r
+ \r
+ \If{\Call{GetSize}{$payload'$} $ > SpaceRemaining$} \Comment{No more space for resuces in payload}\r
+ \State \Return{$payload_s$}\r
+ \EndIf\r
+ \r
+ \State $SpaceRemaining \gets SpaceRemaining -$ \Call{GetSize}{$payload'$}\r
+ \State $payload_s \gets payload_s \cup \{payload'\}$\r
+ \EndIf\r
+ \EndFor\\\r
+ \State \Return{$payload_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Pad Payload\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Pad Payload}:\r
+\begin{algorithmic}[1]\r
+\Function{PadPayload}{$payload_s$} \State $SpaceRemaining = MaxPayloadSize - $ \Call{GetSize}{$payload_s$}\r
+ \r
+ \If{$SpaceRemaining = 0$}\r
+ \State \Return{$payload_s$}\r
+ \EndIf\\\r
+ \State \Return{$payload_s \gets payload_s \cup$ \Call{GenerateFiller}{$SpaceRemaining$}}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Delete Records\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Delete Records (Deletes n records)}:\r
+\begin{algorithmic}[1]\r
+\Function{Delete}{$num\_of\_records$}\r
+ \State $RS \gets$ List of all Records sorted by ssn and has form $\tuple{ssn_s, record_s}$\r
+ \State $n \gets 0$\\\r
+ \r
+ \ForAll{$\tuple{ssn_s, record_s}$ in $RS$}\r
+ \If{\Call{HasLivePayload}{$record_s, ssn_s$}}\r
+ \State \Return{False}\r
+ \Else\r
+ \State \Call{DeleteSlotServer}{$ssn_s$}\r
+ \State $n \gets n + 1$\r
+ \EndIf\\\r
+ \r
+ \If{$n = num\_of\_records$}\r
+ \State \textbf{break}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State \Return{True}\r
+ \r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Create Resize Data Structure Payload Item\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Create Resize Data Structure Payload Item:}\r
+\begin{algorithmic}[1]\r
+\Function{MakeResizePayload}{ }\r
+ \State $rp \gets$ Empty $resize$ payload\r
+ \State $cs \gets$ \Call{GetDataStrucSize}{ }\r
+ \State $rp \gets \tuple{cs * 2}$\r
+ \State \Return{$\{rp\}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Get Arbitrator\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get Arbitrator:}\r
+\begin{algorithmic}[1]\r
+\Function{GetArbitrator}{$key$}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\\\r
+\r
+ \ForAll{record in R}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{($payload$ is a $newkey) \land$ \Call{IsLive}{$payload, ssn$}}\r
+ \State $\tuple{k', vc', ssn', mid'} \gets payload$\r
+ \r
+ \If{$k' = key$}\r
+ \State \Return{$mid'$}\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\\\r
+ \State \Call{Error}{No arbitrator for key: $key$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{GetArbitrator}{$guard$}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $\tuple{kvSet, condition} \gets guard$\\\r
+ \r
+ \ForAll{record in R}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{key, value}$ in $kvSet$}\r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{($payload$ is a $newkey) \land$ \Call{IsLive}{$payload, ssn$}}\r
+ \State $\tuple{k', vc', ssn', mid'} \gets payload$\r
+ \If{$k' = key$}\r
+ \State \Return{$mid'$}\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\r
+ \EndFor\\\r
+ \State \Call{Error}{No arbitrator for key: $key$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\end{varwidth}% \r
+}\r
+\r
+%Insert Payload\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Insert Payload:}\r
+\begin{algorithmic}[1]\r
+\Function{InsertPayload}{$payload_s$}\r
+ \r
+ \State $numOfRecords \gets |R|+1$\r
+ \State $targetSize \gets $ \Call{GetDataStrucSize}{ }\r
+ \State $numToDelete \gets numOfRecords - targetSize$\r
+ \State $rp \gets NULL$\r
+ \State $hmac \gets NULL$\r
+ \State $vc \gets NULL$\r
+ \State $record \gets NULL$\\\r
+\r
+ \If{\Call{GetSize}{$payload_s$} $> MaxPayloadSize$}\r
+ \State \Call{Error}{Payload too large}\r
+ \EndIf\\\r
+ \r
+ \If{$numToDelete > 0$}\r
+ \If{$\lnot$\Call{Delete}{$numToDelete$}}\r
+ \State $rp \gets$\Call{MakeResizePayload}{ }\r
+ \If{\Call{GetSize}{$payload_s \cup rp$} $> MaxPayloadSize$}\r
+ \State \Call{InsertPayload}{$rp$}\r
+ \Else\r
+ \State $payload_s \gets payload_s \cup rp$\r
+ \EndIf\r
+ \EndIf\r
+ \EndIf\\\r
+ \r
+ \State $payload_s \gets$ \Call{RescuePayloadItems}{$payload_s$}\r
+ \State $payload_s \gets$ \Call{PadPayload}{$payload_s$}\r
+ \State $vc \gets $ \Call{GenerateVectorClock}{ }\r
+ \State \Call{IncrementVectorClock}{ }\r
+ \State $hmac \gets$ \Call{GenerateHmac}{$mid, vc, payload_s$}\r
+ \State $record \gets \tuple{mid,vc,hmac,payload}$\r
+ \State $record \gets $\Call{Encrypt}{$record$}\r
+ \State \Call{PutSlotServer}{$record$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Check Data Structure for Malicious Activity\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Check Data Structure for Malicious Activity:}\r
+\begin{algorithmic}[1]\r
+\Function{CheckDataStructForValidity}{ }\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $ASeq \gets \emptyset$ \Comment{Set of all Payload Items that are sequences}\r
+ \State $MID \gets \emptyset$ \Comment{Set of all machine IDs}\r
+ \State $midClocks \gets \emptyset$ \Comment{Set of all clocks for the same machine IDs}\r
+ \State $oldestDeletedSsn \gets NULL$\r
+ \State $didFindSsn \gets False$\r
+ \State $didFindClock \gets False$\r
+ \State $hmac \gets NULL$\\\r
+ \r
+ \State Sort $R$ by $ssn$ from smallest $ssn$ to largest $ssn$\\\r
+ \r
+ \ForAll{record in R}\r
+ \State $\tuple{ssn',\tuple{mid', vc', hmac', payload'}} \gets record$\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \State $MID \gets MID \cup \{mid'\}$\r
+ \EndFor\\\r
+\r
+ \ForAll{$record$ in $R$} \Comment{Check HMACs are all valid}\r
+ \State $\tuple{ssn',\tuple{mid', vc', hmac', payload'}} \gets record$\r
+ \State $hmac \gets $ \Call{GenerateHmac}{$mid', vc', payload'$}\r
+ \If{$hmac \neq hmac'$}\r
+ \State \Call{Error}{HMAC mismatch}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \ForAll{$record_1$ in $R$} \Comment{Check no SSN duplicates}\r
+ \State $\tuple{ssn_1,rData_1} \gets record_1$\r
+ \ForAll{$record_2$ in $R$}\r
+ \If{$record_2 \neq record_1$}\r
+ \State $\tuple{ssn_2,rData_2} \gets record_2$\r
+ \If{$ssn_2 = ssn_1$}\r
+ \State \Call{Error}{Duplicate SSN for different records}\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\r
+ \EndFor\\\r
+ \r
+ \r
+ \ForAll{$record_1$ in $R[0:-1]$} \Comment{Check for missing SSN}\r
+ \State $\tuple{ssn_1,rData_1} \gets record_1$\r
+ \State $didFindSsn \gets False$\r
+ \ForAll{$record_2$ in $R[1:]$}\r
+ \State $\tuple{ssn_2,rData_2} \gets record_2$\r
+ \If{$ssn_2 = (ssn_1 + 1)$}\r
+ \ State $didFindSsn \gets True$\r
+ \State Break\r
+ \EndIf\r
+ \EndFor\r
+ \r
+ \If{$\lnot didFindSsn$}\r
+ \State \Call{Error}{Missing SSN in SSN sequence.}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{($payload$ is a $delete) \land$ \Call{IsLive}{$payload, ssn$}}\r
+ \State $\tuple{ssn'} \gets payload$\r
+ \State $oldestDeleteSsn \gets ssn'$\r
+ \ElsIf{($payload$ is a $sequence) \land$ \Call{IsLive}{$payload, ssn$}}\r
+ \State $ASeq \gets ASeq \cup \{payload\}$\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \r
+ \ForAll{$record$ in $R$} \Comment{Check SSN's are all valid}\r
+ \State $\tuple{ssn, rData} \gets record$\r
+ \ForAll{$\tuple{rid', ssn'}$ in $ASeq$}\r
+ \If{$(rid' =$ \Call{GetRid}{$record$}$) \land ssn' \neq ssn$}\r
+ \State \Call{Error}{SSN mismatch}\r
+ \EndIf\r
+ \EndFor\r
+ \EndFor\\\r
+ \r
+ \r
+ \State $\tuple{ssn, payload} \gets R[0]$ \Comment{Get first record in the sorted R}\r
+ \If{$ssn > (oldestDeleteSsn + 1) $}\r
+ \State \Call{Error}{Missing records}\r
+ \EndIf\\\r
+ \r
+ \r
+ \ForAll{$mid$ in $MID$}\r
+ \State $midClocks \gets \emptyset$\r
+ \r
+ \ForAll{record in R}\r
+ \State $\tuple{ssn',\tuple{mid', vc', hmac', payload'}} \gets record$\r
+ \If{$mid' = mid$}\r
+ \State $\tuple{c_{mid_1}, c_{mid_2},...,c_{mid_k}} \gets vc'$\r
+ \State $midClocks \gets midClocks \cup \{c_{mid_n}|mid_n=mid\}$\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State Sort $midClocks$ from smallest clock to largest clock\\\r
+ \r
+ \ForAll{$c_1$ in $midClocks[0:-1]$} \Comment{Check for missing SSN}\r
+ \State $didFindSsn \gets False$\r
+ \ForAll{$c_2$ in $midClocks[1:]$}\r
+ \If{$c_2 = (c_1 + 1)$}\r
+ \State $didFindC\r
+ock\gets True$\r
+ \State Break\r
+ \EndIf\r
+ \EndFor\r
+ \EndFor\r
+ \r
+ \If{$\lnot didFindClock$}\r
+ \State \Call{Error}{Missing clock in clock sequence for: $mid$.}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State \Comment{If got here then data structure is valid}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+%Get Latest Data Structure From Server\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get Latest Data Structure From Server}:\r
+\begin{algorithmic}[1]\r
+\Function{GetLatestDataStruct}{}\r
+ \State $largestSsn \gets $ Largest $ssn$ of all $ssn$ in $R$\r
+ \State $R \gets R \cup $ \Call{GetSlotServer}{$largestSsn + 1$}\r
+ \State \Call{CheckDataStructForValidity}{ }\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+%Update Key Value Set\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Update Key Value Set:}\r
+\begin{algorithmic}[1]\r
+\Function{UpdateKVSet}{$currentKV, kvSet$}\r
+ \State $newKVSet \gets kvSet$\r
+ \State $foundKey \gets False$\\\r
+ \r
+ \ForAll{$\tuple{k,v}$ in $currentKV$}\r
+ \State $foundKey \gets False$\\\r
+ \r
+ \ForAll{$\tuple{k',v'}$ in $kvSet$}\r
+ \If{$k = k'$}\r
+ \State $foundKey \gets True$\r
+ \State Break\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \If{$\lnot foundKey$}\r
+ \State $newKVSet \gets newKVSet \cup \{\tuple{k,v}\}$\r
+ \EndIf\r
+ \EndFor\r
+ \r
+ \State \Return{$newKVSet$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\subsection{\textbf{Create new key}}\r
+This operation creates a key and assigns an arbitrator to arbitrate on that new key. In the case where more than one clients concurrently try to create the same new key, the client that inserted the newkey payload with the lowest ssn will be the client to generate the key, all other clients generation attempts would be invalid.\r
+\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Create new key:}\r
+\begin{algorithmic}[1]\r
+\Function{CreateNewKey}{$keyName, mid$}\r
+ \State $vc \gets $ \Call{GenerateVectorClock}{ }\r
+ \State $newKeyPayload \gets \tuple{keyName, vc, NULL, mid}$\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\\\r
+\r
+ \State \Call{GetLatestDataStruct}{ } \Comment{Update local version of data struct}\\\r
+\r
+ \ForAll{record in R}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{($payload$ is a $newkey) \land$ \Call{IsLive}{$payload, ssn$}}\r
+ \State $\tuple{k', vc', ssn', mid'} \gets payload$\r
+ \r
+ \If{$k' = key$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State \Call{InsertPayload}{$newKeyPayload$}\r
+ \State \Return{True}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\subsection{\textbf{Put Transaction}}\r
+This operation puts a transaction into the data structure if this transaction fits inside a payload.\r
+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
+\r
+%\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Put Transaction:}\r
+\begin{algorithmic}[1]\r
+\Function{PutTransaction}{$kVUpdates, guard$}\r
+ \State $mid \gets NULL$\r
+ \State $vc \gets $ \Call{GenerateVectorClock}{ }\r
+ \State $transPayload \gets NULL$\\\r
+\r
+ \State \Call{GetLatestDataStruct}{ } \Comment{Update local version of data struct}\\\r
+\r
+ \ForAll{$kv$ in $kVUpdates$}\r
+ \State $\tuple{k', v'} \gets kv$\r
+ \r
+ \If{$mid = NULL$}\r
+ \State $mid \gets$ \Call{GetArbitrator}{$k'$}\r
+ \ElsIf{$mid \neq $ \Call{GetArbitrator}{$k'$}}\r
+ \State \Call{Error}{Multiple Arbitrators}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \If{\Call{GetArbitrator}{$guard$} $\neq mid$}\r
+ \State \Call{Error}{Multiple Arbitrators}\r
+ \EndIf\\\r
+ \r
+ \State $transPayload \gets \tuple{mid, vc, kVUpdates, guard}$\r
+ \State \Call{InsertPayload}{$transPayload$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\end{varwidth}% \r
+}\r
+\r
+\subsection{\textbf{Get key-value pair}}\r
+This operation gets the latest key value pair from the data structure. This is done by starting at the last known committed key value pairs then extrapolating into the future of uncommitted transactions till the transaction with the largest ssn is reached. Everytime a new transaction is evaluated, it is evaluated against the current best guess of key value pairs based on the transactions up to the transaction being evaluated (by ssn). This allows each client to "guess" what the latest value for a specified key will be even when the arbitrator has not stepped in yet to arbitrate.\r
+\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get Latest Data Structure From Server}:\r
+\begin{algorithmic}[1]\r
+\Function{GetValueForKey}{$keyName$}\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $AT \gets \emptyset$ \Comment{Set of all Payload Items that are transactions}\r
+ \State $AC \gets \emptyset$ \Comment{Set of all Payload Items that are commits}\r
+ \State $AA \gets \emptyset$ \Comment{Set of all Payload Items that are aborts}\r
+ \State $kSet \gets \emptyset$ \Comment{Set of all key names in the system}\r
+ \State $tid \gets NULL$\r
+ \State $currentKV \gets \emptyset$\\\r
+ \r
+ \State \Call{GetLatestDataStruct}{ } \Comment{Update local version of data struct}\\\r
+ \r
+ \ForAll{$record$ in $R$}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{$payload$ is a $transaction$}\r
+ \State $AT \gets AT \cup \{\tuple{ssn,payload}\}$\r
+ \ElsIf{$payload$ is a $commit$}\r
+ \State $AC \gets AC \cup \{payload\}$\r
+ \ElsIf{$payload$ is a $abort$}\r
+ \State $AA \gets AA \cup \{payload\}$\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State Sort $AT$ by ssn from oldest to newest\\\r
+ \r
+ \ForAll{$trans$ in $AT$} \Comment{Get the latest committed keys}\r
+ \State $\tuple{mid,vc ,kvSet,guard} \gets trans$\\\r
+ \r
+ \ForAll{$\tuple{k,v}$ in $kvSet$} \Comment{Get all key names in the system}\r
+ \State $kSet \gets kSet \cup \{k\}$\r
+ \EndFor\\\r
+\r
+ \If{$\lnot $\Call{TransactionLive}{$trans$}} \Comment{Only keep live transactions}\r
+ \State $AT \gets AT - \{trans\}$\r
+ \State Continue\r
+ \EndIf\\\r
+ \r
+ \State $tid \gets $ \Call{GetTid}{$trans$}\r
+ \ForAll{$com$ in $AC$}\r
+ \State $\tuple{tid', vc'} \gets com$\r
+ \If{$tid' = tid$}\r
+ \ForAll{$\tuple{k,v}$ in $kvSet$}\r
+ \If{\Call{KeyValueLive}{$k,trans$}}\r
+ \State $currentKV \gets currentKV \cup \{\tuple{k,v}\}$\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State $AT \gets AT - \{trans\}$ \Comment{No need for committed transactions}\r
+ \State Break\r
+ \EndIf\r
+ \EndFor\r
+ \EndFor\\\r
+ \r
+ \ForAll{$trans$ in $AT$} \Comment{Uncommitted ones only in order from lowest ssn to highest ssn}\r
+ \State $\tuple{mid,vc ,kvSet,guard} \gets trans$\r
+ \If{\Call{EvaluateGuard}{$guard, currentKV$}} \Comment{Check if will abort}\r
+ \State $currentKV \gets $\Call{UpdateKVSet}{$currentKV, kvSet$}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \r
+ \ForAll{$\tuple{k,v}$ in $currentKV$} \Comment{Return the latest guessed value}\r
+ \If{$k = keyName$}\r
+ \State \Return{$v$}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State \Return{$NULL$} \Comment{Key was not present}\r
+ \r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+\subsection{\textbf{Arbitrate On Transaction}}\r
+\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get Latest Data Structure From Server}:\r
+\begin{algorithmic}[1]\r
+\Function{Arbitrate }{ }\r
+ \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\r
+ \State $AT \gets \emptyset$ \Comment{Set of all Payload Items that are transactions}\r
+ \State $AC \gets \emptyset$ \Comment{Set of all Payload Items that are commits}\r
+ \State $AA \gets \emptyset$ \Comment{Set of all Payload Items that are aborts}\r
+ \State $kSet \gets \emptyset$ \Comment{Set of all key names in the system}\r
+ \State $tid \gets NULL$\r
+ \State $currentKV \gets \emptyset$\r
+ \State $newPayload \gets NULL$\r
+ \State $midClient \gets mid$ of this client\\\r
+ \r
+ \State \Call{GetLatestDataStruct}{ } \Comment{Update local version of data struct}\\\r
+ \r
+ \ForAll{$record$ in $R$}\r
+ \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+ \EndFor\\\r
+ \r
+ \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+ \If{$payload$ is a $transaction$}\r
+ \State $AT \gets AT \cup \{\tuple{ssn,payload}\}$\r
+ \ElsIf{$payload$ is a $commit$}\r
+ \State $AC \gets AC \cup \{payload\}$\r
+ \ElsIf{$payload$ is a $abort$}\r
+ \State $AA \gets AA \cup \{payload\}$\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State Sort $AT$ by ssn from oldest to newest\\\r
+ \r
+ \ForAll{$trans$ in $AT$} \Comment{Get the latest committed keys}\r
+ \State $\tuple{mid,vc ,kvSet,guard} \gets trans$\\\r
+ \r
+ \ForAll{$\tuple{k,v}$ in $kvSet$} \Comment{Get all key names in the system}\r
+ \State $kSet \gets kSet \cup \{k\}$\r
+ \EndFor\\\r
+\r
+ \If{$\lnot $\Call{TransactionLive}{$trans$}} \Comment{Only keep live transactions}\r
+ \State $AT \gets AT - \{trans\}$\r
+ \State Continue\r
+ \EndIf\\\r
+ \r
+ \State $tid \gets $ \Call{GetTid}{$trans$}\r
+ \ForAll{$com$ in $AC$}\r
+ \State $\tuple{tid', vc'} \gets com$\r
+ \If{$tid' = tid$}\r
+ \ForAll{$\tuple{k,v}$ in $kvSet$}\r
+ \If{\Call{KeyValueLive}{$k,trans$}}\r
+ \State $currentKV \gets currentKV \cup \{\tuple{k,v}\}$\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State $AT \gets AT - \{trans\}$ \Comment{No need for committed transactions}\r
+ \State Break\r
+ \EndIf\r
+ \EndFor\r
+ \EndFor\\\r
+ \r
+ \ForAll{$trans$ in $AT$} \Comment{Uncommitted ones only in order from lowest ssn to highest ssn}\r
+ \State $\tuple{mid,vc ,kvSet,guard} \gets trans$\r
+ \r
+ \If{\Call{GetArbitrator}{$guard$} $\neq midClient$}\r
+ \State Continue\r
+ \EndIf\r
+ \r
+ \If{\Call{EvaluateGuard}{$guard, currentKV$}} \Comment{Check if will abort}\r
+ \State $currentKV \gets $\Call{UpdateKVSet}{$currentKV, kvSet$}\r
+ \State $newPayload \gets \tuple{$\Call{GetTid}{$trans$}$, $\Call{GenerateVectorClock}{ } $}$ \Comment{Make new commit payload}\r
+ \Else\r
+ \State $newPayload \gets \tuple{$\Call{GetTid}{$trans$}$, mid, $\Call{GenerateVectorClock}{ } $}$ \Comment{Make new abort payload}\r
+ \EndIf\\\r
+ \r
+ \State \Call{InsertPayload}{$newPayload$}\r
+ \EndFor\\\r
+ \r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+\r
+\r
+\section{\textbf{System Guarantees}}\r
+\begin{itemize}\r
+ \item Server cannot view data inside records\r
+ \item Server cannot forge or modify or create any records\r
+ \item Server cannot withhold any records\r
+ \item Server cannot reorder records that could not have been ordered differently due to network latency\r
+ \item Server cannot delete records unless told to do so.\r
+ \item There will always be an obvious key-value pair that is the latest key value pair.\r
+ \item The data structure is bounded in size such that $m$ is the minimum size of the data structure, $n$ is the number of devices in the system and $s$ is the current size of the data structure: $m \leq s \leq (m+n-1)$\r
+ \item Data structure can only grow when there are too may key-value pairs (and aborts) than what fit in the current data structure size within reason.\r
+ \item No currently valid data can be lost by the system and go undetected.\r
+ \item Devices can operate offline and re-sync with the system and get a consistent view of the system\r
+ \item If the server tries to hold a device on an older version of the data structure, that device can eventually rejoin the main data structure without problems.\r
+ \item Devices that have a transaction aborted will be able to be notified about the abort indefinitely (no time frame when notification must be accepted).\r
+ \item Server cannot hold a device on an old version of the data structure and then move them to a newer version of the data structure without being detected (The server sequence numbers would reveal conflicts or gaps or both).\r
+\r
+\end{itemize}\r
+\r
+\r
+\end{document}\r
projects / iotcloud.git / blobdiff