From 75281d02d46c33b6b0dca30e39ab6203190cc97e Mon Sep 17 00:00:00 2001 From: Ali Younis Date: Mon, 7 Nov 2016 18:57:22 -0800 Subject: [PATCH] Changes --- doc2/iotcloud.tex | 196 +++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 184 insertions(+), 12 deletions(-) diff --git a/doc2/iotcloud.tex b/doc2/iotcloud.tex index 96d8b7f..c1a6fb2 100644 --- a/doc2/iotcloud.tex +++ b/doc2/iotcloud.tex @@ -72,7 +72,7 @@ $max\_size$ = max size of the block chain\\ \subsubsection{Sets and Lists} - +$PendingTransSet$ = Set of pending transactions that need to be pushed to the block chain, $\tuple{number,PendingTrans}$\\ $PendingTrans= \tuple{KV, Guard} = \tuple{$set of key value pairs, set of guard conditions$}$.\\ $Arbitrator$ = set of $\tuple{k,id}$ containing the key and its arbitrating device.\\ $LastSlot$ = set of $\tuple{id, seq}$ containing the machine ID and the largest sequence number from that machine ID.\\ @@ -540,6 +540,20 @@ Generate a abort data entry.\\ \end{varwidth}% } +% Create Collision +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Create ColRes:}\\ +Generate a colres data entry.\\ +\begin{algorithmic}[1] +\Function{CreateColRes}{$is_a, seq_{a_{old}}, seq_{a_{new}}, isequal_a$} + \State \Return{$\tuple{id_a, seq_{a_{old}}, seq_{a_{new}},}isequal_a$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + + % Create Transaction \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -567,6 +581,19 @@ Generate a commit data entry.\\ \end{varwidth}% } +% Create New Key +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Create New Key:}\\ +Generate a new key data entry.\\ +\begin{algorithmic}[1] +\Function{CreateNewKey}{$k_a, id_a$} + \State \Return{$\tuple{k_a,id_a}$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + % Data Entry Set Has Space \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -1212,7 +1239,7 @@ This rescue is not mandatory. This is trying to fill the remaining portion of t \EndIf\\ \If{\Call{DEHasSpace}{$DE_a, de$}} - \State $DE_a \gets DE_a \cup de$ \Comment{Had enough space to add it} + \State $DE_a \gets DE_a \cup de$ \Comment{Had enoug space to add it} \ElsIf{$numofskips \geq MAX\_RESCUE\_SKIPS$} \State \Return{$DE_a$} \Else @@ -1230,6 +1257,49 @@ This rescue is not mandatory. This is trying to fill the remaining portion of t \end{varwidth}% } + +% Rejected Messages +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Rejected Messages:}\\ +\begin{algorithmic}[1] +\Function{RejectedMessages}{$DE_a$} + \State $seq_{old} \gets seq$ such that $\tuple{seq} \in RejectedSlotList \land \forall \tuple{seq'} \in RejectedSlotList, seq \geq seq'$ + \State $prev \gets -1$\\ + + + + \If{$|RejectedSlotList| \geq REJECTED\_THRESH$} + \State $seq_{new} \gets seq$ such that $\tuple{seq} \in RejectedSlotList \land \forall \tuple{seq'} \in RejectedSlotList, seq \leq seq'$\\ + \State $colres \gets $ \Call{CreateColRes}{$LOCAL\_ID, seq_{old}, seq_{new}, false$} + \State \Return{$DE_a \cup \{colres\}$} + \EndIf\\ + + \ForAll{$\tuple{seq} \in RejectedSlotList$ sorted by $seq$} + \If{$\exists \tuple{seq',Dat'} \in LocalSlots$} + \State Break + \EndIf + \State $prev \gets seq$ + \EndFor\\ + + \If{$prev \neq -1$} + \State $DE_a \gets DE_a \cup$ \Call{CreateColRes}{$LOCAL\_ID, seq_{old}, prev, false$} + \EndIf\\ + + \State $RejectedSlotList \gets \{\tuple{seq}| \tuple{seq} \in RejectedSlotList, seq > prev\}$\\ + + \ForAll{$\tuple{seq} \in RejectedSlotList$ sorted by $seq$} + \State $DE_a \gets DE_a \cup$ \Call{CreateColRes}{$LOCAL\_ID, seq,seq, false$} + \EndFor\\ + + \State \Return{$DE_a$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + + + % Arbitrate \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -1359,8 +1429,9 @@ Try to insert a transaction into the block chain. Does resizing, rescues and ins \State $DE \gets DE \cup \{$\Call{CreateQState}{$newsize$}$\}$ \EndIf\\ - %\If{$RejectedSlotList \neq \emptyset$} - %\EndIf + \If{$RejectedSlotList \neq \emptyset$} + \State $DE \gets$ \Call{RejectedMessages}{$DE$} + \EndIf\\ \State $DE \gets$ \Call{MandatoryRescue}{$DE$} \Comment{Round 1 of rescue} \If{$DE = NULL$} @@ -1391,6 +1462,65 @@ Try to insert a transaction into the block chain. Does resizing, rescues and ins \end{varwidth}% } + +% Try Insert New Key +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Try Insert New Key:}\\ +Try to insert a new key into the block chain. Does resizing, rescues and insertion of other data entry types as needed. \\ +\begin{algorithmic}[1] +\Function{TryInsertNewKey}{$k_a, id_a, forceresize$} + \State $DE \gets \emptyset$ \Comment{The data entries for this slot} + \State $seq \gets $ \Call{GetNextSeq}{} \Comment{Get the sequence number for this slot} + \State $newsize \gets 0$ + + + \State $newkey \gets$ \Call{CreateNewKey}{$k_a, id_a$} + \State $newkeyinserted \gets false$ + \State $slotstoinsert \gets \emptyset$\\ + + \State $resize \gets $ \Call{ShouldResize}{ } \Comment{Check if we should resize} + \State $resize \gets resize \lor forceresize$ + \If{$resize$} + \State $newsize \gets$ \Call{CalcNewSize}{$max\_size$} + \State $DE \gets DE \cup \{$\Call{CreateQState}{$newsize$}$\}$ + \EndIf\\ + + \If{$RejectedSlotList \neq \emptyset$} + \State $DE \gets$ \Call{RejectedMessages}{$DE$} + \EndIf\\ + + \State $DE \gets$ \Call{MandatoryRescue}{$DE$} \Comment{Round 1 of rescue} + \If{$DE = NULL$} + \LeftComment{Data was going to fall off the end so try again with a forced resize} + \State \Return{\Call{TryInsertNewKey}{$k_a, id_a, true$}} + \EndIf\\ + + \State $DE \gets $\Call{Arbitrate}{$DE$}\\ + + \If{\Call{DEHasSpace}{$DE, newkey$}} \Comment{new key fits} + \State $DE \gets DE \cup newkey$ + \State $newkeyinserted \gets true$ + \EndIf\\ + + \LeftComment{Rescue data to fill slot data entry section} + \State $DE \gets$ \Call{OptionalRescue}{$DE$}\\ + + \LeftComment{Send to server.} + \State $\tuple{sendsuccess, newslots} \gets $ \Call{SendToServer}{$seq, DE, newsize$}\\ + + \LeftComment{Insert the slots into the local block chain} + \State \Call{DecryptValidateInsert}{$newslots, true$}\\ + + \State \Return{$newkeyinserted \land success$} \Comment{Return if succeeded or not} + +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + + + \subsection{Client Interfaces} % Put KV pair @@ -1424,14 +1554,25 @@ Puts a key value pair into the key value pair buffer\\ 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 $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpeculatedKV \land k = k_a$ + \State $SpecKVTmp \gets SpeculatedKV$ + \State $DKV \gets \emptyset$\\ + + \LeftComment{Go Through local pending transactions and speculate} + \ForAll{$\tuple{num, \tuple{KV, Guard}} \in PendingTransSet$ sorted by num} + \If{\Call{EvaluateGuard}{$Guard, SpecKVTmp$}} + \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in SpecKVTmp \land \tuple{k',v'}\in KV \land k'=k\}$ + \State $SpecKVTmp \gets (SpecKVTmp \setminus DKV) \cup KV$ + \EndIf + \EndFor + + \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpecKVTmp \land k = k_a$ \State \Return{$v$} \EndFunction \end{algorithmic} \end{varwidth}% } - % Update \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -1447,7 +1588,6 @@ Sync with the server and get all the latest slots.\\ \end{varwidth}% } - % Get KV Pair Committed \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -1483,7 +1623,6 @@ Puts a guard transaction into the key value update. A guard is a key value with \end{varwidth}% } - % Transaction Start \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -1502,12 +1641,23 @@ Starts a transaction. Clears out the key value pair update buffer.\\ \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} \textbf{ Transaction Commit:}\\ -Commits the transaction into the block chain. Keeps attempting to insert the transaction into the block chain until it succeeds. +Commits the transaction into the block chain. Keeps attempting to insert the transaction into the block chain until it succeeds.\\ \begin{algorithmic}[1] \Function{Transaction Commit}{$ $} - \State $success \gets False$ - \While{$\lnot success$} - \State $success \gets$ \Call{TryInsertTransaction}{$PendingTrans, false$} + \State $num_{largest} \gets 1$\\ + \If{$PendingTransSet \neq \emptyset$} + \State $num_{largest} \gets num$ such that $\tuple{num, pt} \in PendingTransSet \land \forall \tuple{num', pt'} \in PendingTransSet, num \geq num'$ \Comment{Get the next largest number} + \State $num_{largest} \gets num_{largest} +1$ + \EndIf\\ + + \State $PendingTransSet \gets PendingTransSet \cup \{\tuple{num_{largest},PendingTrans}\}$\\ + + \While{\Call{HasConnectionToServer}{ } $\land PendingTransSet \neq \emptyset$} + \State $\tuple{num, pt} \gets \tuple{num, pt}$ such that $\tuple{num, pt} \in PendingTransSet \land \forall \tuple{num', pt'} \in PendingTransSet, num \leq num'$ \Comment{Get the oldest one and try to commit it}\\ + + \If{\Call{TryInsertTransaction}{$pt, false$}} + \State $PendingTransSet \gets PendingTransSet \setminus \tuple{num, pt}$ + \EndIf \EndWhile \EndFunction \end{algorithmic} @@ -1515,5 +1665,27 @@ Commits the transaction into the block chain. Keeps attempting to insert the tr } +%Create New Key +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Create New Key:}\\ +Creates a new key and specifies which machine ID is the arbitrator. If there is already a new key entry in the block chain for this key name then do not insert into the chain, another client got there first. \\ +\begin{algorithmic}[1] +\Function{Transaction Commit}{$k_a, id_a$} + \State $success \gets false$\\ + \While{$\lnot success$} + \If{$\exists \tuple{k',id'} \in Arbitrator, k' = k_a$} + \State \Return{$false$} \Comment{Key already created} + \EndIf\\ + + \State $success \gets$ \Call{TryInsertNewKey}{$k_a, id_a$} + \EndWhile + + \State \Return{$true$} \Comment{If got here then insertion was correct} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + \end{document} -- 2.34.1