From 5483fe67c1fe2248fa0880c97594092a2247b1c9 Mon Sep 17 00:00:00 2001 From: Ali Younis Date: Fri, 14 Oct 2016 14:40:31 -0700 Subject: [PATCH] Updates --- version2/doc/iotcloud_formal/iotcloud.tex | 161 ++++++++++++++++++++-- 1 file changed, 153 insertions(+), 8 deletions(-) diff --git a/version2/doc/iotcloud_formal/iotcloud.tex b/version2/doc/iotcloud_formal/iotcloud.tex index 17c03f0..ad3e4bf 100644 --- a/version2/doc/iotcloud_formal/iotcloud.tex +++ b/version2/doc/iotcloud_formal/iotcloud.tex @@ -154,6 +154,29 @@ $record_s = \tuple{ssn_s,rd_s}$\\ \subsection{Helper Functions} The following helper functions are needed:\\ + +%Throw Error +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Throw Error:} +\begin{algorithmic}[1] +\Function{Error}{$msg$} + \State $Print(msg)$ + \State $Halt()$ +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + + +\begin{algorithmic}[1] +\Procedure{Error}{$msg$} +\State $Print(msg)$ +\State $Halt()$ +\EndProcedure +\end{algorithmic} + + %Get Payload Items from Record with SSN \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -312,6 +335,43 @@ The following helper functions are needed:\\ \end{varwidth}% } +%New Key Live +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{New Key Live:} +\begin{algorithmic}[1] +\Function{NewKeyLive}{$newkey_s, ssn_r$} + \State $API \gets \emptyset$ \Comment{Set of all Payload Items} + \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} + \State $ssn_s \gets ssn_r$ + \EndIf\\ + + \ForAll{record in R} + \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record} + \EndFor\\ + + \ForAll{$\tuple{ssn', payload'}$ in $API$} + \If{$payload'$ is a $newkey$} + \State $ANK \gets ANK \cup \{\tuple{ssn', payload'}\}$ \Comment{Extract all new key payloads} + \EndIf + \EndFor\\ + + \ForAll{$\tuple{ssn', \tuple{k_s', vc_s', ssn_s', mid_s'}}$ in $ANK$} + \If{$vc_s' < vc_s$} + \State \Return{False} + \ElsIf{$\lnot (vc_s' < vc_s) \land (ssn_s' < ssn_s)$} + \State \Return{False} + \EndIf + \EndFor \\ + \State \Return{True} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + %Is Live \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -434,8 +494,7 @@ The following helper functions are needed:\\ \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} \textbf{Pad Payload}: \begin{algorithmic}[1] -\Function{PadPayload}{$payload_s$} - \State $SpaceRemaining = MaxPayloadSize - $ \Call{GetSize}{$payload_s$} +\Function{PadPayload}{$payload_s$} \State $SpaceRemaining = MaxPayloadSize - $ \Call{GetSize}{$payload_s$} \If{$SpaceRemaining = 0$} \State \Return{$payload_s$} @@ -457,7 +516,6 @@ The following helper functions are needed:\\ \ForAll{$\tuple{ssn_s, record_s}$ in $RS$} \If{\Call{HasLivePayload}{$record_s, ssn_s$}} - \State \Call{ResizeDataStruc}{ } \State \Return{False} \Else \State \Call{DeleteSlotServer}{$ssn_s$} @@ -476,18 +534,74 @@ The following helper functions are needed:\\ \end{varwidth}% } - - +%Create Resize Data Structure Payload Item +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Create Resize Data Structure Payload Item:} +\begin{algorithmic}[1] +\Function{MakeResizePayload}{ } + \State $rp \gets$ Empty $resize$ payload + \State $cs \gets$ \Call{GetDataStrucSize}{ } + \State $rp \gets \tuple{cs * 2}$ + \State \Return{$rp$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} \textbf{Evaluate Guard Condition:}\\ \textbf{Get Latest Data Structure From Server:}\\ \textbf{Check Data Structure for Malicious Activity:}\\ -\textbf{Resize Data Structure:}\\ + + +\textbf{Get Arbitrator for key}:\\ \textbf{Get Transaction Arbitrator}:\\ \textbf{Transaction Live}:\\ \textbf{Commit Live}:\\ -\textbf{New Key Live}:\\\ -\textbf{Key Value Live}:\\\ +\textbf{Key Value Live}:\\ +\textbf{Get Vector Clock}:\\ + +%Insert Payload +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Insert Payload:} +\begin{algorithmic}[1] +\Function{InsertPayload}{$payload_s$} + + \State $numOfRecords \gets |R|+1$ + \State $targetSize \gets $ \Call{GetDataStrucSize}{ } + \State $numToDelete \gets numOfRecords - targetSize$ + \State $rp \gets NULL$\\ + \State $hmac \gets NULL$ + \State $vc \gets NULL$ + \State $record \gets NULL$ + + \If{\Call{GetSize}{$payload_s$} $> MaxPayloadSize$} + \State \Call{Error}{Payload too large} + \EndIf\\ + + \If{$numToDelete > 0$} + \If{$\lnot$\Call{Delete}{$numToDelete$}} + \State $rp \gets$\Call{MakeResizePayload}{ } + \If{\Call{GetSize}{$payload_s \cup rp$} $> MaxPayloadSize$} + \State \Call{InsertPayload}{$rp$} + \Else + \State $payload_s \gets payload_s \cup rp$ + \EndIf + \EndIf + \EndIf\\ + + + \State $payload_s \gets$ \Call{RescuePayloadItems}{$payload_s$} + \State $payload_s \gets$ \Call{PadPayload}{$payload_s$} + \State $hmac \gets$ \Call{GetHmac}{$mid, vc, payload_s$} + \State $record \gets \tuple{mid,vc,hmac,payload}$ + \State $record \gets $\Call{Encrypt}{$record$} + \State \Call{PutSlotServer}{$record$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} %-Rescues % - Need to Change Transaction sizes @@ -500,8 +614,39 @@ The following helper functions are needed:\\ %-Check Data Structure \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. +%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 $ + + \ForAll{$kv$ in $kVUpdates$} + \State $\tuple{k', v'} \gets kv$ + + \If{$mid = -1$} + \State $mid \gets$ \Call{GetArbitrator}{$k'$} + \ElsIf{$mid \neq $ \Call{GetArbitrator}{$k'$}} + \State \Call{Error}{Multiple Arbitrators} + \EndIf + \EndFor\\ + + \If{\Call{GetArbitrator}{$guard$} $\neq mid$} + \State \Call{Error}{Multiple Arbitrators} + \EndIf + + + +\EndFunction +\end{algorithmic} +\end{varwidth}% +} \subsection{\textbf{Get key-value pair}} \subsection{\textbf{Create new key}} -- 2.34.1