From 3c75b82ece6d28dc3719993c8df1c91d32558698 Mon Sep 17 00:00:00 2001 From: Ali Younis Date: Sat, 15 Oct 2016 14:18:38 -0700 Subject: [PATCH] Formal Document edits --- version2/doc/iotcloud_formal/iotcloud.tex | 162 +++++++++++++++++----- 1 file changed, 130 insertions(+), 32 deletions(-) diff --git a/version2/doc/iotcloud_formal/iotcloud.tex b/version2/doc/iotcloud_formal/iotcloud.tex index ad3e4bf..679c218 100644 --- a/version2/doc/iotcloud_formal/iotcloud.tex +++ b/version2/doc/iotcloud_formal/iotcloud.tex @@ -29,8 +29,6 @@ - - \section{\textbf{Server}} The server maintains a collection of slots such that each slot contains some data. The operations on the slot are as follows: @@ -140,7 +138,7 @@ $abort_s = \tuple{tid_s,mid_s,vc_s}$\\ $sequence_s = \tuple{rid_s, ssn_s}$\\ $delete_s = \tuple{ssn_d}$\\ $resize_s = \tuple{x | x \in \mathbb{N}}$\\ -$newkey_s = \tuple{k_s, vc_s, ssn_s$ or $-1, mid_s}$\\ +$newkey_s = \tuple{k_s, vc_s, ssn_s$ or $NULL, mid_s}$\\ $payload_s = \{x_1, x_2,..., x_k | \forall k, x_k \in \{$transaction, commit, abort, resize, newkey, sequence, delete$\}\}$\\ $rd_s = \tuple{mid_s, vc_s, hmac_s, payload_s}$ \\ @@ -168,7 +166,7 @@ The following helper functions are needed:\\ \end{varwidth}% } - +%Error Message \begin{algorithmic}[1] \Procedure{Error}{$msg$} \State $Print(msg)$ @@ -177,6 +175,19 @@ The following helper functions are needed:\\ \end{algorithmic} +%Get Latest Data Structure From Server +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Get Latest Data Structure From Server}: +\begin{algorithmic}[1] +\Function{GetLatestDataStruct}{} + \State $largestSsn \gets $ Largest $ssn$ of all $ssn$ in $R$ + \State $R \gets R \cup $ \Call{GetSlotServer}{$largestSsn + 1$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + %Get Payload Items from Record with SSN \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -345,7 +356,7 @@ The following helper functions are needed:\\ \State $ANK \gets \emptyset$ \Comment{Set of all Payload Items that are new keys} \State $\tuple{k_s, vc_s, ssn_s, mid_s}\gets newkey_s$\\ - \If{$ssn_s = -1$} \Comment{Make sure ssn is the correct one} + \If{$ssn_s = NULL$} \Comment{Make sure ssn is the correct one} \State $ssn_s \gets ssn_r$ \EndIf\\ @@ -549,17 +560,56 @@ The following helper functions are needed:\\ \end{varwidth}% } -\textbf{Evaluate Guard Condition:}\\ -\textbf{Get Latest Data Structure From Server:}\\ -\textbf{Check Data Structure for Malicious Activity:}\\ +%Get Arbitrator +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Get Arbitrator:} +\begin{algorithmic}[1] +\Function{GetArbitrator}{$key$} + \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\\ + + \ForAll{record in R} + \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record} + \EndFor\\ + + \ForAll{$\tuple{ssn, payload}$ in $API$} + \If{($payload$ is a $newkey) \land$ \Call{IsLive}{$payload, ssn$}} + \State $\tuple{k', vc', ssn', mid'} \gets payload$ + + \If{$k' = key$} + \State \Return{$mid'$} + \EndIf + \EndIf + \EndFor\\ + \State \Call{Error}{No arbitrator for key: $key$} +\EndFunction +\end{algorithmic} +\begin{algorithmic}[1] +\Function{GetArbitrator}{$guard$} + \State $API \gets \emptyset$ \Comment{Set of all Payload Items} + \State $\tuple{kvSet, condition} \gets guard$\\ + + \ForAll{record in R} + \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record} + \EndFor\\ + + \ForAll{$\tuple{key, value}$ in $kvSet$} + \ForAll{$\tuple{ssn, payload}$ in $API$} + \If{($payload$ is a $newkey) \land$ \Call{IsLive}{$payload, ssn$}} + \State $\tuple{k', vc', ssn', mid'} \gets payload$ + \If{$k' = key$} + \State \Return{$mid'$} + \EndIf + \EndIf + \EndFor + \EndFor\\ + \State \Call{Error}{No arbitrator for key: $key$} +\EndFunction +\end{algorithmic} -\textbf{Get Arbitrator for key}:\\ -\textbf{Get Transaction Arbitrator}:\\ -\textbf{Transaction Live}:\\ -\textbf{Commit Live}:\\ -\textbf{Key Value Live}:\\ -\textbf{Get Vector Clock}:\\ +\end{varwidth}% +} %Insert Payload \noindent\fbox{% @@ -571,10 +621,10 @@ The following helper functions are needed:\\ \State $numOfRecords \gets |R|+1$ \State $targetSize \gets $ \Call{GetDataStrucSize}{ } \State $numToDelete \gets numOfRecords - targetSize$ - \State $rp \gets NULL$\\ + \State $rp \gets NULL$ \State $hmac \gets NULL$ \State $vc \gets NULL$ - \State $record \gets NULL$ + \State $record \gets NULL$\\ \If{\Call{GetSize}{$payload_s$} $> MaxPayloadSize$} \State \Call{Error}{Payload too large} @@ -591,9 +641,9 @@ The following helper functions are needed:\\ \EndIf \EndIf\\ - \State $payload_s \gets$ \Call{RescuePayloadItems}{$payload_s$} \State $payload_s \gets$ \Call{PadPayload}{$payload_s$} + \State $vc \gets $ \Call{GenerateVectorClock}{ } \State $hmac \gets$ \Call{GetHmac}{$mid, vc, payload_s$} \State $record \gets \tuple{mid,vc,hmac,payload}$ \State $record \gets $\Call{Encrypt}{$record$} @@ -603,34 +653,79 @@ The following helper functions are needed:\\ \end{varwidth}% } + + + + +\textbf{Check Data Structure for Malicious Activity:}\\ +\textbf{Transaction Live}:\\ +\textbf{Commit Live}:\\ +\textbf{Key Value Live}:\\ + + %-Rescues % - Need to Change Transaction sizes -%-Deletes -%-Resize -%-Puts +% - Need to Change New Key ssn in transaction %-Gets -%-New Key %-Arbitration +% - Insert Commit %-Check Data Structure + + +\subsection{\textbf{Create new key}} +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Create new key:} +\begin{algorithmic}[1] +\Function{CreateNewKey}{$keyName, mid$} + \State $vc \gets $ \Call{GenerateVectorClock}{ } + \State $newKeyPayload \gets \tuple{keyName, vc, NULL, mid}$ + \State $API \gets \emptyset$ \Comment{Set of all Payload Items}\\ + + \State \Call{GetLatestDataStruct}{ } \Comment{Update local version of data struct}\\ + + \ForAll{record in R} + \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record} + \EndFor\\ + + \ForAll{$\tuple{ssn, payload}$ in $API$} + \If{($payload$ is a $newkey) \land$ \Call{IsLive}{$payload, ssn$}} + \State $\tuple{k', vc', ssn', mid'} \gets payload$ + + \If{$k' = key$} + \State \Return{False} + \EndIf + \EndIf + \EndFor\\ + + \State \Call{InsertPayload}{$newKeyPayload$} + \State \Return{True} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + \subsection{\textbf{Put Transaction}} This operation puts a transaction into the data structure if this transaction fits inside a payload. -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. +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.\\ - -%Create Resize Data Structure Payload Item +% \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} \textbf{Put Transaction:} \begin{algorithmic}[1] \Function{PutTransaction}{$kVUpdates, guard$} - \State $mid \gets -1$\\ - \State $dsSize \gets $ - + \State $mid \gets NULL$ + \State $vc \gets $ \Call{GenerateVectorClock}{ } + \State $transPayload \gets NULL$\\ + + \State \Call{GetLatestDataStruct}{ } \Comment{Update local version of data struct}\\ + \ForAll{$kv$ in $kVUpdates$} \State $\tuple{k', v'} \gets kv$ - \If{$mid = -1$} + \If{$mid = NULL$} \State $mid \gets$ \Call{GetArbitrator}{$k'$} \ElsIf{$mid \neq $ \Call{GetArbitrator}{$k'$}} \State \Call{Error}{Multiple Arbitrators} @@ -639,17 +734,20 @@ If by adding this transaction the data structure size exceeds the proposed max d \If{\Call{GetArbitrator}{$guard$} $\neq mid$} \State \Call{Error}{Multiple Arbitrators} - \EndIf - - + \EndIf\\ + \State $transPayload \gets \tuple{mid, vc, kVUpdates, guard}$ + \State \Call{InsertPayload}{$transPayload$} \EndFunction \end{algorithmic} \end{varwidth}% } \subsection{\textbf{Get key-value pair}} -\subsection{\textbf{Create new key}} + + + + \end{document} -- 2.34.1