\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
\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
\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
\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
\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
\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
\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
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
\end{varwidth}% \r
}\r
\r
-\r
% Get KV Pair Committed\r
\noindent\fbox{%\r
\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
\end{varwidth}% \r
}\r
\r
-\r
% Transaction Start\r
\noindent\fbox{%\r
\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
\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
}\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
projects / iotcloud.git / commitdiff