From 905c301cc90e18eb599f4f9f2b3887baf2ce0720 Mon Sep 17 00:00:00 2001 From: Ali Younis Date: Thu, 3 Nov 2016 15:10:59 -0700 Subject: [PATCH] Changes --- doc2/iotcloud.tex | 356 +++++++++++++++++++++++++++++++++++++++------- 1 file changed, 304 insertions(+), 52 deletions(-) diff --git a/doc2/iotcloud.tex b/doc2/iotcloud.tex index 712f152..96d8b7f 100644 --- a/doc2/iotcloud.tex +++ b/doc2/iotcloud.tex @@ -46,7 +46,7 @@ $trans$ is a transaction entry , $\tuple{seq, id, KV, Guard}$ \\ $lastmsg$ is a last message entry, $\tuple{seq, id}$ \\ $qstate$ is a queue state entry, $\tuple{size}$ \\ $colres$ is a collision resolution entry, $\tuple{id, seq_{old}, seq_{new}, true \lor false}$ \\ -$newkey$ is a new key entry, $\tuple{seq, k, id}$, $id$ is ID of arbitrator \\ +$newkey$ is a new key entry, $\tuple{k, id}$, $id$ is ID of arbitrator \\ $commit$ is a commit transaction entry, $\tuple{seq_{trans},KV}$, id is id of arbitrator \\ $abort$ is an abort transaction entry, $\tuple{seq_{trans},id_{trans}}$ \\ @@ -78,7 +78,8 @@ $Arbitrator$ = set of $\tuple{k,id}$ containing the key and its arbitrating devi $LastSlot$ = set of $\tuple{id, seq}$ containing the machine ID and the largest sequence number from that machine ID.\\ $LocalSlots$ = set of slots that are in the clients local buffer (initially $\emptyset$), data is decrypted.\\ $RejectedSlotList$ = ordered list of the sequence numbers of slots that this client tried to insert but were rejected.\\ - +$CommittedKV$ = set of committed key value pairs (initially $\emptyset$). +$SpeculatedKV$ = set of speculated key value pairs (initially $\emptyset$). \subsection{Helper Functions} The following helper functions are needed:\\ @@ -136,7 +137,22 @@ Get the next sequence number for insertion into the block chain.\\ Get the arbitrator for a given key.\\ \begin{algorithmic}[1] \Function{GetArbitrator}{$k$} - \State $\tuple{k_1,id_1} \gets \tuple{k_2,id_2} $ \textit{such that} $ \tuple{k_2,id_2} \in Arbitrator \land k_2=k$ + \State $\tuple{k_1,id_1} \gets \tuple{k_2,id_2} $ \textit{such that} $ \tuple{k_2,id_2} \in Arbitrator \land k_2=k$ + \State \Return{$id_1$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + +% Get Arbitrator KV +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Get Arbitrator for KV Set:}\\ +Get the arbitrator for a given key value set.\\ +\begin{algorithmic}[1] +\Function{GetArbitratorKV}{$KV$} + \State $\tuple{k,v} \gets \tuple{k',v'}$ such that $\tuple{k',v'} \in KV$ + \State $\tuple{k_1,id_1} \gets \tuple{k_2,id_2} $ \textit{such that} $ \tuple{k_2,id_2} \in Arbitrator \land k_2=k$ \State \Return{$id_1$} \EndFunction \end{algorithmic} @@ -389,7 +405,7 @@ Check if an abort data entry is live or not. Abort is dead if the device whos t \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} \textbf{Check Transaction Live:}\\ -A transaction is dead if there is an abort for that transaction or if there is a commit for that a transaction that came after this transaction. Since transactions must be commited in order of there insertion, seeing a transaction that is commited and has a larger sequence number than the transaction in question means that the transaction in question was commited at some point.\\ +A transaction is dead if there is an abort for that transaction or if there is a commit for that a transaction that came after this transaction. Since transactions must be committed in order of there insertion, seeing a transaction that is committed and has a larger sequence number than the transaction in question means that the transaction in question was committed at some point.\\ \begin{algorithmic}[1] \Function{CheckTransLive}{$trans_a$} \State $\tuple{seq_a, id_a, KV_a, Guard_a} \gets trans_a$ @@ -804,50 +820,237 @@ Checks that the block chain size is correct when there is a gap in the block cha \end{varwidth}% } -% Initialize the expected size of the block chain + +% % Initialize the expected size of the block chain +% \noindent\fbox{% +% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +% \textbf{Initialize the expected size of the block chain:}\\ +% Initialize the expected size of the block chain based on the size at the server.\\ +% \begin{algorithmic}[1] +% \Function{InitExpSize}{$seq_a$} +% \State $startingsize \gets 0$\\ + +% \If{$seq_a < max\_size$} \Comment{Check whether saves slots are full on server} +% \State $startingsize \gets seq_a$ +% \Else +% \State $startingsize \gets max\_size$ +% \EndIf\\ + +% \State \Return{$startingsize$} +% \EndFunction +% \end{algorithmic} +% \end{varwidth}% +% } + +% % Update the expected size of the block chain +% \noindent\fbox{% +% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +% \textbf{Update the expected size of the block chain:}\\ +% Update the expected size of the block chain.\\ +% \begin{algorithmic}[1] +% \Function{UpdateExpSize}{$size_a$} +% \State $size_a \gets size_a + 1$\\ + +% \If{$size_a > max\_size$}\Comment{Expected size $\leq max\_size$} +% \State $ssize_a \gets max_\_size$ +% \EndIf\\ + +% \State \Return{$size_a$} +% \EndFunction +% \end{algorithmic} +% \end{varwidth}% +% } + + + +% Update Last Message \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} -\textbf{Initialize the expected size of the block chain:}\\ -Initialize the expected size of the block chain based on the size at the server.\\ +\textbf{Process Commit Data Entry:}\\ +Process a commit entry. Updates the local copy of commits.\\ \begin{algorithmic}[1] -\Function{InitExpSize}{$seq_a$} - \State $startingsize \gets 0$\\ - - \If{$seq_a < max\_size$} \Comment{Check whether saves slots are full on server} - \State $startingsize \gets seq_a$ +\Function{UpdateLastMessage}{$seq_a, id_a, LstSlt_a, updateinglocal_a$} + \State $\tuple{id_{old}, seq_{old}} \gets \tuple{id', seq'}$ such that $\tuple{id', seq'} \in LastSlot \land id'=id$\\ + + \If{$id_a = LOCAL\_ID$} + \If{$\lnot updateinglocal_a \land (seq_a \neq seq_{old})$} + \LeftComment{This client did not make any updates so its latest sequence number should not change} + \State \Call{Error}{"Mismatch on local machine sequence number"} + \EndIf \Else - \State $startingsize \gets max\_size$ + \If{$seq_{old} > seq_a$} + \State \Call{Error}{"Rollback on remote machine sequence number"} + \EndIf \EndIf\\ - \State \Return{$startingsize$} + \State $LastSlot \gets LastSlot \setminus \{\tuple{id, seq} | \tuple{id, seq} \in LastSlot, id=id_a\}$ + \State $LastSlot \gets LastSlot \cup \{\tuple{id_a, seq_a}\}$ + + \State \Return{$LstSlt_a \setminus \{\tuple{id, seq} | \tuple{id, seq} \in LstSlt_a, id=id_a\}$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + +% Process Commit Data Entry +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Process Commit Data Entry:}\\ +Process a commit entry. Updates the local copy of commits.\\ +\begin{algorithmic}[1] +\Function{ProcessCommit}{$commit_a$} + \State $\tuple{seq_{a_{trans}},KV_a} \gets commit_a$ + \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CommittedKV \land \tuple{k',v'}\in KV_a \land k'=k\}$ + \State $CommittedKV \gets (CommittedKV \setminus DKV) \cup KV_a$ +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + +% Process Queue State Data Entry +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Process Queue State Entry:}\\ +Process a queue state entry. Updates the max size of the block chain\\ +\begin{algorithmic}[1] +\Function{ProcessQState}{$qstate_a$} + \State $\tuple{size_a} \gets qstate_a$ + \State $max\_size \gets size_a$ \Comment{Update the max size we can have} \EndFunction \end{algorithmic} \end{varwidth}% } -% Update the expected size of the block chain +% Process Collision Resolution Entry \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} -\textbf{Update the expected size of the block chain:}\\ -Update the expected size of the block chain.\\ +\textbf{Process Queue State Entry:}\\ +Process a collision resolution entry.\\ \begin{algorithmic}[1] -\Function{UpdateExpSize}{$size_a$} - \State $size_a \gets size_a + 1$\\ +\Function{ProcessColres}{$colres_a, NewSlots_a$} + \State $\tuple{id_a, seq_{a_{old}}, seq_{a_{new}}, isequal_a}$ + \State $AllSlots \gets LocalSlots \cup NewSlots_a$ + \State $index \gets seq_{a_{old}}$\\ + + \While{$index <= seq_{a_{new}}$} + \State $slt \gets \tuple{seq' Dat'}$ such that $\tuple{seq' Dat'} \in AllSlots \land seq'=index$ + + \If{$\exists \tuple{seq' Dat'} \in AllSlots, seq' = index$} + \State $\tuple{seq, Dat} \gets \tuple{seq' Dat'}$ such that $\tuple{seq' Dat'} \in AllSlots \land seq'=index$ + \State $\tuple{seq,id,DE,hmac_p,hmac_c} \gets Dat$ + \If{$isequal_a \neq (id=id_a)$} + \State \Call{Error}{"Trying to insert rejected messages for slot"} + \EndIf + \EndIf\\ + \State $index \gets index + 1$ + \EndWhile - \If{$size_a > max\_size$}\Comment{Expected size $\leq max\_size$} - \State $ssize_a \gets max_\_size$ - \EndIf\\ - \State \Return{$size_a$} \EndFunction \end{algorithmic} \end{varwidth}% } +% Process New Key Data Entry +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Process New Key Entry:}\\ +Process a queue state entry. Adds a key to the key arbitrator set\\ +\begin{algorithmic}[1] +\Function{ProcessNewkey}{$newkey_a$} + \State $\tuple{seq_a, k_a, id_a} \gets newkey_a$ + \State $Arbitrator \gets Arbitrator \cup \{\tuple{k_a,id_a}\}$ +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + +% Process Process Data Entry +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Process Data Entry:}\\ +Process the data entry based on what kind of entry it is.\\ +\begin{algorithmic}[1] +\Function{ProcessDatEntry}{$slot_a, NewSlots_a,LstSlt_a$} + \If{$datentry_a$ is a $commit$} + \State \Call{ProcessCommit}{$dataentry_a$} + + \ElsIf{$datentry_a$ is a $abort$} + \LeftComment{Do Nothing in this case} + + \ElsIf{$datentry_a$ is a $trans$} + \LeftComment{Do Nothing in this case} + + \ElsIf{$datentry_a$ is a $lastmsg$} + \State $\tuple{seq_a, id_a} \gets dataentry_a$ + \State $LstSlt_a \gets$ \Call{UpdateLastMessage}{$seq_a, id_a, LstSlt_a, false$} + + \ElsIf{$datentry_a$ is a $colres$} + \State \Call{ProcessColres}{$dataentry_a, NewSlots_a$} + + \ElsIf{$datentry_a$ is a $qstate$} + \State \Call{ProcessQState}{$dataentry_a$} + + \ElsIf{$datentry_a$ is a $newkey$} + \State \Call{ProcessNewkey}{$dataentry_a$} + + \Else + \State \Call{Error}{"Unknown data entry type."} + \EndIf + + \State \Return{$LstSlt_a$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} +% Delete Local Slots +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Delete Local Slots:}\\ +Deletes local slots that are deleted at the server. This keeps the size of the local block chain bounded.\\ +\begin{algorithmic}[1] +\Function{DeleteLocalSlots}{$ $} + \State $\tuple{seq_{max}, Dat_{max}} \gets $ \Call{MaxSlot}{$LocalSlots$} + \State $seq_{min} \gets seq_{max} - max\_size$ \Comment{Min sequence number we should keep} + \State $LSDelete \gets \emptyset$ + + \If{$|LocalSlots| \leq max\_size$} + \State \Return{} \Comment{Nothing to delete} + \EndIf\\ + + \State $LSDelete \gets \{\tuple{seq', Dat'}|\tuple{seq', Dat'} \in LocalSlots, seq' > seq_{min}\}$ + \State $LocalSlots \gets LocalSlots \setminus LSDelete$ +\EndFunction +\end{algorithmic} +\end{varwidth}% +} +% Create Speculative KV +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Create Speculative KV:}\\ +Speculates on what the most recent key value pairs will be based on the latest committed key value pairs and the uncommitted transactions.\\ +\begin{algorithmic}[1] +\Function{SpeculateKV}{$ $} + \State $AllTrans \gets$ \Call{GetTrans}{} + \State $LiveTrans \gets \{t| t\in AllTrans, $\Call{CheckTransLive}{$t$}$\}$ + \State $CurrKV \gets CommittedKV$ + \State $DKV \gets \emptyset$ + \ForAll{$\tuple{seq_t, id_t, KV_t, Guard_t} \in LiveTrans$ ordered by $seq'$} + \If{\Call{EvaluateGuard}{$Guard_t, CurrKV$}} + \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CurrKV \land \tuple{k',v'}\in KV_t \land k'=k\}$ + \State $CurrKV \gets (CurrKV \setminus DKV) \cup KV_t$ + \EndIf + \EndFor + + \State \Return{$CurrKV$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} % Validate and Update @@ -856,52 +1059,55 @@ Update the expected size of the block chain.\\ \textbf{Validate Update:}\\ Validate the block chain and insert into the local block chain.\\ \begin{algorithmic}[1] -\Function{ValidateUpdate}{$NewSlots_a$} +\Function{ValidateUpdate}{$NewSlots_a, updatinglocal_a$} \State $\tuple{seq_{oldest}, Dat_{oldest}} \gets$ \Call{MinSlot}{$NewSlots_a$} \State $\tuple{seq_{newest}, Dat_{newest}} \gets$ \Call{MaxSlot}{$NewSlots_a$} - - \State $currsize \gets $\Call{InitExpSize}{$seq_{oldest}$}\\ + \State $\tuple{seq_{local}, Dat_{local}} \gets$ \Call{MaxSlot}{$LocalSlots$} + \State $LastSlotTmp \gets LastSlot$\\ + %\State $currsize \gets $\Call{InitExpSize}{$seq_{oldest}$}\\ \State \Call{CheckSlotsHmacAndSeq}{$NewSlots_a$} \Comment{Check all the HMACs} \State \Call{CheckHmacChain}{$NewSlots_a$} \Comment{Check HMAC Chain} \State \Call{CheckOldSlots}{$NewSlots_a$} \Comment{Check if new slots are actually old slots} \State \Call{CheckSize}{$NewSlots_a$} \Comment{Check if the size is correct}\\ - \ForAll{$slot_a \in NewSlots_a$} \Comment{Process each slot} + \ForAll{$slot_a \in NewSlots_a$ in order of sequence number} + \If{$slot_a \in LocalSlots$} \Comment{Client already has this slot} + \State $NewSlots_a \gets NewSlots_a \setminus \{slot_a\}$ + \State Continue + \EndIf\\ + \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets slot_a$ + \State $LstSlt_a \gets$ \Call{UpdateLastMessage}{$seq_{a_1}, id_a, LstSlt_a, updatinglocal_a$}\\ + \ForAll{$de_a \in DE_a$} \Comment{Process each data entry} - + \State $LstSlt_a \gets $ \Call{ProccessDatEntry}{$de_a, NewSlots_a,LstSlt_a$} \EndFor\\ - \State $currsize \gets $ \Call{UpdateExpSize}{$currsize$}\\ + %\State $currsize \gets $ \Call{UpdateExpSize}{$currsize$}\\ \State $LocalSlots \gets LocalSlots \cup \{slot_a\}$ \Comment{Add to local Chain} - \EndFor - + \EndFor\\ + + \If{$seq_{oldest} > (seq_{local} +1) \land LastSlotTmp \neq \emptyset$} + \LeftComment{There was a gap so there should be a complete set of information on each previously seen client} + \State \Call{Error}{"Missing records for machines"} + \EndIf\\ - %Delete from local chain to maintain size + \State \Call{DeleteLocalSlots}{ } \Comment{Delete old slots from local} + \State $SpeculatedKV \gets $\Call{SpeculateKV}{ } \Comment{Speculate on what will be latest KV set} \EndFunction \end{algorithmic} \end{varwidth}% } - - - - - - - - - - % Decrypt Validate Insert Slots \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} \textbf{Decrypt Validate Insert Slots:}\\ Decrypts slots, validates (checks for malicious activity) slots and inserts the slots into the local block chain.\\ \begin{algorithmic}[1] -\Function{DecryptValidateInsert}{$NewSlots_a$} +\Function{DecryptValidateInsert}{$NewSlots_a, updatinglocal_a$} \State $DecryptedSlots \gets \emptyset$ \State $DDat \gets NULL$\\ @@ -909,7 +1115,7 @@ Decrypts slots, validates (checks for malicious activity) slots and inserts the \State $DDat \gets $ \Call{Decrypt}{$EDat'$} \State $DecryptedSlots \gets DecryptedSlots \cup \tuple{seq',DDat}$ \EndFor\\ - \State \Call{ValidateUpdate}{$DecryptedSlots$} + \State \Call{ValidateUpdate}{$DecryptedSlots, updatinglocal_a$} \EndFunction \end{algorithmic} \end{varwidth}% @@ -1042,11 +1248,15 @@ This rescue is not mandatory. This is trying to fill the remaining portion of t \LeftComment{Get all the latest commits} \ForAll{$\tuple{seq_{trans}',KV'} \in LiveCommits$} - \State $CurrKV \gets CUrrKV \cup KV'$ + \State $CurrKV \gets CurrKV \cup KV'$ \EndFor\\ - \ForAll{$\tuple{seq_t, id_t, KV_t, Guard_t} \in LiveTrans$ ordered by $seq'$} - \If{\Call{EvaluateGuard}{$Guard_t, CurrKV$}} + \ForAll{$\tuple{seq_t, id_t, KV_t, Guard_t} \in LiveTrans$ ordered by $seq'$} + \If{\Call{GetArbitratorKV}{$KV_t$} $\neq LOCAL\_ID$} + \State Continue \Comment{Client not arbitrator for this transaction} + \EndIf\\ + + \If{$\lnot$\Call{EvaluateGuard}{$Guard_t, CurrKV$}} \State $abortde \gets $\Call{CreateAbort}{$seq_t, id_t$} \LeftComment{No more space so we cant arbitrate any further} \If($lnot$\Call{DeHasSpace}{$DE_a, abortde$}) @@ -1054,9 +1264,9 @@ This rescue is not mandatory. This is trying to fill the remaining portion of t \EndIf \State $DE_a \gets DE_a \cup abortde$ \Else - \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in KV \land \tuple{k',v'}\in KV_t \land k'=v'\}$ + \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in KV \land \tuple{k',v'}\in KV_t \land k'=k\}$ \State $KVTmp \gets (KV \setminus DKV) \cup KV'$ - \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CurrKV \land \tuple{k',v'}\in KVTmp \land k'=v'\}$ + \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CurrKV \land \tuple{k',v'}\in KVTmp \land k'=k\}$ \State $CurrKV \gets (CurrKV \setminus DKV) \cup KVTmp$ \State $commitde \gets $ \Call{CreateCommit}{$seq_t,KVTmp$} @@ -1172,7 +1382,7 @@ Try to insert a transaction into the block chain. Does resizing, rescues and ins \State $\tuple{sendsuccess, newslots} \gets $ \Call{SendToServer}{$seq, DE, newsize$}\\ \LeftComment{Insert the slots into the local bloakc chain} - \State \Call{DecryptValidateInsert}{$newslots$}\\ + \State \Call{DecryptValidateInsert}{$newslots, true$}\\ \State \Return{$transinserted \land success$} \Comment{Return if succeeded or not} @@ -1207,6 +1417,50 @@ Puts a key value pair into the key value pair buffer\\ \end{varwidth}% } +% Get KV Pair Speculative +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Get KV Pair Speculative:}\\ +Get the value for the key while speculating.\\ +\begin{algorithmic}[1] +\Function{GetValueSpeculate}{$k_a$} + \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpeculatedKV \land k = k_a$ +\State \Return{$v$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + + +% Update +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Update}\\ +Sync with the server and get all the latest slots.\\ +\begin{algorithmic}[1] +\Function{Update}{$ $} + \State $\tuple{seq, Dat} \gets $ \Call{MaxSlot}{$LocalSlots$} + \State $NewSlots \gets$ \Call{GetSlots}{$seq$} + \State \Call{DecryptValidateInsert}{$NewSlots, false$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + + +% Get KV Pair Committed +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Get KV Pair Committed:}\\ +Get the value for the key which have been committed.\\ +\begin{algorithmic}[1] +\Function{GetValueCommit}{$k_a$} + \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in Committed \land k = k_a$ + \State \Return{$v$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} % Put guard condition \noindent\fbox{% @@ -1262,6 +1516,4 @@ Commits the transaction into the block chain. Keeps attempting to insert the tr - - \end{document} -- 2.34.1