Changes
authorAli Younis <ayounis@uci.edu>
Tue, 8 Nov 2016 02:57:22 +0000 (18:57 -0800)
committerAli Younis <ayounis@uci.edu>
Tue, 8 Nov 2016 02:57:22 +0000 (18:57 -0800)
doc2/iotcloud.tex

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