\usepackage{graphicx}\r
\usepackage{mathrsfs}\r
\usepackage{amssymb}\r
+\usepackage{algorithm}\r
\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx\r
\usepackage[all]{xy}\r
\usepackage{varwidth}\r
\newcommand{\push}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}\r
\newcommand*\xor{\mathbin{\oplus}}\r
\algnewcommand{\LeftComment}[1]{\Statex \(\triangleright\) #1}\r
+\algnewcommand{\algorithmicgoto}{\textbf{go to}}%\r
+\algnewcommand{\Goto}[1]{\algorithmicgoto~\ref{#1}}%\r
+\r
+\r
\begin{document}\r
\r
\r
\r
\section{Approach}\r
\r
-\subsection{Keys}\r
-\r
-Each device has: user id + password\r
-\r
-Server login is:\r
-hash1(user id), hash1(password)\r
-\r
-Symmetric Crypto keys is:\r
-hash2(user id | password)\r
-\r
-Server has finite length queue of entries + max\_entry\_identifier +\r
-server login key\r
-\r
-\subsection{Entry layout}\r
-Each entry has:\r
-\begin{enumerate}\r
-\item Sequence identifier\r
-\item Random IV (if needed by crypto algorithm)\r
-\item Encrypted payload\r
-\end{enumerate}\r
-\r
-Payload has:\r
-\begin{enumerate}\r
-\item Sequence identifier\r
-\item Machine id (most probably something like a 64-bit random number \r
-that is self-generated by client)\r
-\item HMAC of previous slot\r
-\item Data entries\r
-\item HMAC of current slot\r
-\end{enumerate}\r
-\r
-A data entry can be one of these:\r
-\begin{enumerate}\r
- \item A transaction:\r
- \begin{itemize}\r
- \item Contains a sequence number, a set of key value pair updates and a guard condition that can be evaluated.\r
- \item Must have the same arbitrator for all its key value pair updates and reads within the guard condition\r
- \end{itemize}\r
- \r
- \item A Commit\r
- \newline{Commits a transaction into the block chain. Until a transaction is committed, no client can be sure if that transaction's key value updates will be used to update the state of the system. Once an arbitrator commits a transaction then that transaction becomes a permanent state change in the system. Transactions should be committed and aborted in order of their sequence numbers.}\r
- \r
- \item An Abort\r
- \newline{An abort is used to show that a transactions key value update should not be used in the state change of the system. This occurs when the guard of a transaction evaluates to false meaning that the conditions under-which this transaction should be committed no longer exists in the system (another transaction could have been committed first that would have changed the system in a way that makes the current transaction invalid).}\r
- \r
- \item New Key:\r
- \newline{This creates a new key and assignes an arbitrator to that key. Only the first new key message for a given key is valid. Once a new key message is inserted into the block chain it is never removed and no other new key entries for the same key name can be inserted into the block chain.}\r
- \r
- \item Slot sequence entry: Machine id + last message identifier \r
- \newline {The purpose of this is to keep the record of the last slot from a certain client if a client's update has to expunge that other client's last entry from the queue. This is kept in the slot until the entry owner inserts a newer update into the queue.}\r
-\r
- \item Queue state entry: Includes queue size \r
- \newline {The purpose of this is for the client to tell if the server lies about the number of slots in the queue, e.g. if there are 2 queue state entry in the queue, e.g. 50 and 70, the client knows that when it sees 50, it should expect at most 50 slots in the queue and after it sees 70, it should expect 50 slots before that queue state entry slot 50 and at most 70 slots. The queue state entry slot 70 is counted as slot number 51 in the queue.}\r
-\r
- \item Collision resolution entry: message identifier + machine id of a collision winner\r
- \newline {The purpose of this is to keep keep track of the winner of all the collisions until all clients have seen the particular entry.}\r
-\end{enumerate}\r
-\r
-\subsection{Live status}\r
-\r
-Live status of entries:\r
-\begin{enumerate}\r
- \item Transaction is live if it has not been committed or aborted yet.\r
- \r
- \item Abort is live until the machine ID that created the transaction that is being aborted inserts into the block chain a message with a sequence number greater than the abort (that client sees the abort).\r
- \r
- \item Commit is dead if for all key value updates in the commit there is a commit with the same key value update that is newer (larger sequence number). The committing client (arbitrator) will see those newer commits since it is the one that generates them.\r
- \r
- \item New Key messages are always kept alive. Keys can not be deleted. Deleted keys will cause arbitration to fail if a key is deleted then reassigned to a new client device for arbitration.\r
- \r
- \item Slot sequence number (of either a message version data or user-level data) is dead if there is a newer slot from the same machine.\r
-\r
- \item Queue state entry is dead if there is a newer queue state entry.\r
- {In the case of queue state entries 50 and 70, this means that queue state entry 50 is dead and 70 is live. However, not until the number of slots reaches 70 that queue state entry 50 will be expunged from the queue. Further all entries before the 50 entry will also not be expunged until the queue size has reached 70}\r
-\r
- \item Collision resolution entry is dead if this entry has been seen by all clients after a collision happens.\r
-\end{enumerate}\r
-\r
-When data is at the end of the queue ready to expunge, if:\r
-\begin{enumerate}\r
- \item If any entry is not dead it must be reinserted into the queue.\r
-\r
- \item If the slot sequence number is not dead, then a message sequence entry must be inserted.\r
-\end{enumerate}\r
-\r
-\paragraph{Validation procedure on client:}\r
-\begin{enumerate}\r
- \item Decrypt each new slot in order.\r
- \item For each slot:\r
- (a) check its HMAC, and\r
- (b) check that the previous entry HMAC field matches the previous entry (in case of a gap do not check for slots on gap margins).\r
- \item That no slots are slots we have seen before (server trying to pass old slots). \r
- \r
- \item For all other machines, check that the latest sequence number is at least as large (never goes backwards).\r
- \r
- \item That the queue has a current queue state entry.\r
- \r
- \item That the number of entries received is consistent with the size specified in the queue state entry and/or the queue is growing in size.\r
-\end{enumerate}\r
-\r
-\subsection{Resizing Queue}\r
-Client can make a request to resize the queue. This is done as a write that combines:\r
- (a) a slot with the message, and (b) a request to the server. The queue can only be expanded, never contracted; attempting to decrease the size of the queue will cause future clients to throw an error.\r
-\r
-\r
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
\r
\subsection{The Arbitrator}\r
$SeqN(slot_s = \tuple{s, sv})=s$ \\\r
$SlotVal(slot_s = \tuple{s, sv})=sv$ \\\r
\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{Get Slot:}\\\r
-Returns to the client the slots that have a sequence number that is greater than or equal to the sequence number that is in the requese.\\\r
+Returns to the client the slots that have a sequence number that is greater than or equal to the sequence number that is in the request.\r
\begin{algorithmic}[1]\r
-\Function{GetSlot}{$s_g$}\r
+\Function{GetSlot}{$s_g$} throws $Server\_Connection\_Timeout$, $Server\_Response\_Timeout$\r
\State \Return{$\{\tuple{s, sv} \in SL \mid s \geq s_g\}$}\r
\EndFunction\r
-\end{algorithmic}\end{varwidth}% \r
-}\r
+\end{algorithmic}%\end{varwidth}% \r
+%}\r
\r
\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{Get Slot:}\\\r
-Puts a slot in the server memory if the slot has the correct sequence number. Also resizes the server memory if needed.\\\r
+Puts a slot in the server memory if the slot has the correct sequence number. Also resizes the server memory if needed.\r
\begin{algorithmic}[1]\r
-\Function{PutSlot}{$s_p,sv_p,max'$}\r
+\Function{PutSlot}{$s_p,sv_p,max'$} throws $Server\_Connection\_Timeout$, $Server\_Response\_Timeout$\r
\If{$(max' \neq \emptyset)$} \Comment{Resize}\r
\State $max \gets max'$\r
\EndIf\r
s \geq s_p\})$}\r
\EndIf\r
\EndFunction\r
-\end{algorithmic}\end{varwidth}% \r
-}\r
-\r
+\end{algorithmic}%\end{varwidth}% \r
+%}\r
\r
\r
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
-\section{\textbf{Client}}\r
+\section{Client Algorithm}\r
\r
\subsection{\textbf{Client Notation Conventions}}\r
$k$ is key of entry \\\r
$size$ is a size (target size of the current block chain) \\\r
$kv$ is a key-value pair $\tuple{k,v}$ \\\r
$KV$ is a set of $kv$ \\\r
+$G$ is a set of $kv$ that is the guard \\\r
$id$ is a machine ID \\\r
$seq$ is a sequence number \\\r
$hmac_p$ is the HMAC value of the previous slot \\\r
$hmac_c$ is the HMAC value of the current slot \\\r
-$Guard$ is a set of$ \tuple{k,v,$logical operator$}$ which can be evaluated to a boolean \\\r
\r
-$trans$ is a transaction entry , $\tuple{seq, id, KV, Guard}$ \\\r
+$colres$ is a collision resolution entry, $\tuple{id, seq_{old}, seq_{new}, true \lor false}$ \\\r
$lastmsg$ is a last message entry, $\tuple{seq, id}$ \\\r
$qstate$ is a queue state entry, $\tuple{size}$ \\\r
-$colres$ is a collision resolution entry, $\tuple{id, seq_{old}, seq_{new}, true \lor false}$ \\\r
$newkey$ is a new key entry, $\tuple{k, id}$, $id$ is ID of arbitrator \\\r
-$commit$ is a commit transaction entry, $\tuple{seq_{trans},KV}$, id is id of arbitrator \\\r
-$abort$ is an abort transaction entry, $\tuple{seq_{trans},id_{trans}}$ \\\r
-\r
+$abort$ is an abort transaction entry, $\tuple{seq_{clientlocal}, seq_{server}, id, arb, seq_{arb}}$ \\\r
+$transpart$ is a transaction part entry, $\tuple{Dat,arb,seq_{clientLocal}, seq_{server}, id, partnum, isLast}$\\\r
+$compart$ is a commit part entry, $\tuple{Dat,seq_{trans}, seq_{server}, id, partnum, isLast}$\\\r
\r
-$de$ is a data entry that can one of: $trans$, $lastmsg$, $qstate$, $colres$, $newkey$, $commit$, $abort$ \\\r
+$de$ is a data entry that can one of: $transpart$, $lastmsg$, $qstate$, $colres$, $newkey$, $compart$, $abort$ \\\r
$DE$ is a set of all data entries, possibly of different types, in a single message, set of $de$\\\r
\r
+\r
+$pendingTransaction$ is a pending transaction, $\tuple{KV, G, id, seq_{clientLocal}}$ \\\r
+$Transaction$ is a Transaction container that houses transaction parts together, $\tuple{Parts, KV, G,seq_{local}, seq_{server},id, arb}$\\\r
+$Commit$ is a commit container that houses commit parts together, $\tuple{Parts, KV, seq_{trans}, seq_{server},id}$\r
+$ArbitrationRound$ is a commit and a group of aborts where all the aborts must be sent before the commit, $\tuple{commit, AbortSet, SentSet}$\r
+\r
+$status$ is the status of a transaction and can be: $aborted, pending, committed, sentpartial, sentfully, noeffect$\r
+$TransStatus$ is the status of a transaction, $\tuple{status}$\\\r
+\r
$slotDat = \tuple{seq,id,DE,hmac_p,hmac_c}$ \\\r
$slot = \tuple{seq, Encrpt(slotDat)}$\\\r
\r
-\subsection{\textbf{Client State}}\r
\r
\subsubsection{Constants}\r
$LOCAL\_ID$ = machine ID of this client.\\\r
$DATA\_ENTRY\_SET\_MAX\_SIZE$ = max size that a data entry set can have (in bytes).\\\r
$DEAD\_SLOT\_COUNT$ = number of slots to keep dead if possible at the end of the block chain.\\\r
$MAX\_RESCUE\_SKIPS$ = number of skips that are allowed when saving data entries.\\\r
+$MAX\_ROUND\_SIZE$ = max number of parts that an arbitration round can have before being full. \\\r
\r
\subsubsection{Primitive Variables}\r
-$max\_size$ = max size of the block chain\\\r
+$max\_size$ = max size of the block chain.\\\r
+$clntTransactionNum \gets 0$ = current client transaction number that this client created.\\\r
+$newPendingTransaction$ = transaction being built.\\\r
+$arbitrationSeqNum \gets 0$ = sequence number used by the arbitrator to label the commits and aborts it creates\\\r
+$hadPartialSendToServer gets false$ = if the last attempt to send the server had a recieve timeout.\\\r
+\r
\r
\subsubsection{Sets and Lists}\r
\r
-$PendingTransQueue$ = Queue of pending transactions that need to be pushed to the block chain, $\tuple{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
+$LastSlot$ = set of $\tuple{id, seq}$ containing the machine id and the sequence number of the last slot.\\\r
+$Arbitrator$ = set of $\tuple{k,id}$ containing the key and its arbitrating device.\\ne ID and the largest sequence number from that machine ID.\\\r
$LocalSlots$ = set of slots that are in the clients local buffer (initially $\emptyset$), data is decrypted.\\\r
$RejectedSlotList$ = ordered list of the sequence numbers of slots that this client tried to insert but were rejected.\\\r
$CommittedKV$ = set of committed key value pairs (initially $\emptyset$).\\\r
-$SpeculatedKV$ = set of speculated key value pairs (initially $\emptyset$).\r
+$SpeculatedKV$ = set of speculated key value pairs (initially $\emptyset$).\\\r
+$PendingTransactionQueue$ = queue of transactions that need to be sent.\\\r
+$LastTransactionArbitrated$ = set of $\tuple{id, seq}$ with the last sequence number an arbitrator arbitrated on.\\\r
+$LiveTransactions$ = set of transactions with their parts.\\\r
+$LiveCommits$ = set of live commits and their parts.\\\r
+$OfflineTransAtServer$ = set of transactions that were sent to the server but were arbitrated through local communication.\\ \r
+$SendArbQueue$ = queue of arbitration rounds that have yet to be sent to the server.\\\r
+$LastTransSeenMid$ = Last transaction seen from a specific machine from the server.\\\r
+$LastArbLocalArbitrated$ = Last local sequence number seen from a client.\\\r
+$LastCommitSeenFromArbitrator$ = last commit seen from a specific arbitrator.\\\r
\r
\subsection{Helper Functions}\r
The following helper functions are needed:\\\r
\r
$MaxSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
$MinSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\\r
-\r
+$DecodeParts(transpart)= $ Converts the part data into KV sets and Guard Condition sets.\\\r
+$DecodeParts(compart)= $ Converts the part data into a KV set.\\\r
+$GenerateParts(Commit)= $ Fills the commit with parts generated by its content.\\\r
+$GenerateParts(Transaction)= $ Fills the transaction with parts generated by its content.\\\r
+$SetTransStatus(TransStatus, Transaction_Identifier) = $ saves a transaction status.\\ \r
+$ChangeTransStatus(TransStatus, newStatus) = $ changes a transaction status.\\ \r
+$GetTransStatus(Transaction_Identifier) = $ gets a transaction status.\\ \r
+$DeleteTransStatus(Transaction_Identifier) = $ delete a transaction status.\\ \r
\r
% Get Size\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{Get Byte Size:}\\\r
-Get the size in bytes of the thing that is passed in.\\\r
+Get the size in bytes of the thing that is passed in.\r
\begin{algorithmic}[1]\r
\Function{GetSize}{$a$}\r
\State \Return{Size in bytes of $a$}\r
\EndFunction\r
-\end{algorithmic}\end{varwidth}% \r
-}\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
\r
% Error\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{ Error:}\\\r
-Prints an error message and halts the execution of the client.\\\r
+Prints an error message and halts the execution of the client.\r
\begin{algorithmic}[1]\r
\Function{Error}{$msg$}\r
\State $Print(msg)$\r
\State $Halt()$\r
\EndFunction\r
-\end{algorithmic}\end{varwidth}% \r
-}\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Get Next Sequence Number\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Get Next Sequence Number:}\\\r
-Get the next sequence number for insertion into the block chain.\\\r
+% Calculate Resize Threshold\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Calculate Resize Threshold:}\\\r
+Calculate a threshold for how many slots need to have live data entries in them for a resize to take place.\r
\begin{algorithmic}[1]\r
-\Function{GetNextSeq}{$k$}\r
- \LeftComment{Get the largest known sequence number}\r
- \State $seq_{ret} \gets seq$ such that $\tuple{id, seq}\in LastSlo \land (\forall \tuple{id', seq'} \in LastSlo, seq \geq seq')$\\\r
- \r
- \LeftComment{Add one to the largest seq number to generate the new seq number}\r
- \State \Return{$seq_{ret} + 1$}\r
+\Function{CalcResizeThresh}{$maxsize$}\r
+ \State $lower \gets \left \lfloor {maxsize * RESIZE\_THRESH\_PERCENT} \right \rfloor - 1$\r
+ \State \Return{$lower + $\Call{Random}{$maxsize - lower$}}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Calculate Block Chain New Size\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Calculate Block Chain New Size:}\\\r
+Calculate the new size of the block chain which we need if we are to resize the data structure.\r
+\begin{algorithmic}[1]\r
+\Function{CalcNewSize}{$maxsize$}\r
+ \State \Return{$\left \lceil {maxsize * RESIZE\_PERCENT} \right \rceil$}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Should Resize\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Should Resize:}\\\r
+Check if the block should resize based on some metric of how many slots in the block chain are filled with live data. \r
+\begin{algorithmic}[1]\r
+\Function{ShouldResize}{$ $}\r
+ \State $LiveSlots \gets \{slot_s|slot_s \in LocalSlots \land $\Call{SlotHasLive}{$slot_s$}$\}$\r
+ \State \Return{$|LiveSlots| \geq $\Call{CalcResizeThresh}{$max\_size$}} \r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+\r
+% Data Entry Set Has Space \r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Data Entry Set Has Space :}\\\r
+Checks if a data entry set has enough space for a new data entry to be inserted.\r
+\begin{algorithmic}[1]\r
+\Function{DEHasSpace}{$DE_a, de_a$}\r
+ \State $newsize \gets $ \Call{GetSize}{$DE_a$} $ + $ \Call{GetSize}{$de_a$}\r
+ \State \Return{$newsize \leq DATA\_ENTRY\_SET\_MAX\_SIZE$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Get Arbitrator\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{Get Arbitrator:}\\\r
-Get the arbitrator for a given key.\\\r
+Get the arbitrator for a given key.\r
\begin{algorithmic}[1]\r
\Function{GetArbitrator}{$k$}\r
\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$\r
\State \Return{$id_1$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Get Arbitrator KV\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{Get Arbitrator for KV Set:}\\\r
-Get the arbitrator for a given key value set.\\\r
+Get the arbitrator for a given key value set.\r
\begin{algorithmic}[1]\r
-\Function{GetArbitratorKV}{$KV$}\r
- \State $\tuple{k,v} \gets \tuple{k',v'}$ such that $\tuple{k',v'} \in KV$\r
- \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$\r
- \State \Return{$id_1$}\r
+\Function{GetArbitratorKV}{$KV_a$} \r
+ \State \Return{$id'$ such that $\exists \tuple{k',v'} \in KV_a, id' =$ \Call{GetArbitrator}{$k'$}}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Check Transaction arbitrator\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Check Arbitrator for a Transaction:}\\\r
-Check that the arbitrators for a given set are all the same arbitrator.\\\r
+% Get Next Sequence Number\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get Next Sequence Number:}\\\r
+Get the next sequence number for insertion into the block chain.\r
\begin{algorithmic}[1]\r
-\Function{CheckArbitrator}{$PendingTrans_a$}\r
- \State $id_{arb} \gets NULL$\\\r
- \State $\tuple{KV_a, Guard_a} \gets PendingTrans_a$\r
- \r
- \ForAll{$\tuple{k',v'} \in KV_a$}\r
- \State $id' \gets$ \Call{GetArbitrator}{$k'$}\\\r
- \r
- \If{$id_{arb} = NULL$} \r
- \State $id_{arb} \gets id'$\r
- \ElsIf{$id' \neq id_{arb}$} \Comment{Check all arbitrators are the same}\r
- \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
- \EndIf\r
- \EndFor\r
+\Function{GetNextSeq}{$k$}\r
+ \LeftComment{Get the largest known sequence number}\r
+ \State $seq_{ret} \gets seq$ such that $\tuple{id, seq}\in LastSlot \land (\forall \tuple{id', seq'} \in LastSlo, seq \geq seq')$\\\r
\r
- \ForAll{$\tuple{k',v', lop'} \in Guard_a$}\r
- \State $id' \gets$ \Call{GetArbitrator}{$k'$}\\\r
- \r
- \If{$id_{arb} = NULL$} \r
- \State $id_{arb} \gets id'$\r
- \ElsIf{$id' \neq id_{arb}$} \Comment{Check all arbitrators are the same}\r
- \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
- \EndIf\r
- \EndFor\r
+ \LeftComment{Add one to the largest seq number to generate the new seq number}\r
+ \State \Return{$seq_{ret} + 1$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Get all Commits\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Get all Commits:}\\\r
-Get all commits that are currently in the local block chain. Iterate over all the local slots and extract all the commits from each slot.\\\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{GetCommits}{$ $}\r
- \State $ComSet \gets \emptyset$ \Comment{Set of the commits}\\\r
- \r
- \LeftComment{Iterate over all the slots saved locally}\r
- \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
- \State $ComSet \gets ComSet \cup \{c |c \in DE',c$is a $commit\}$\r
- \EndFor\r
- \State \Return{$ComSet$}\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
+%\end{varwidth}% \r
+%}\r
\r
-% Get all Transactions\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Get all Transactions:}\\\r
-Get all transactions that are currently in the local block chain. Iterate over all the local slots and extract all the transactions from each slot.\\\r
+% Check and Create Last Message Data Entry\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Check and Create Last Message Data Entry:}\\\r
+Check if a last message entry needs to be created for this slot and if so create it. The check is done by checking if there are any newer slots with the same id or if there is already a last message slot with a newer sequence number.\r
\begin{algorithmic}[1]\r
-\Function{GetTrans}{$ $}\r
- \State $TransSet \gets \emptyset$ \Comment{Set of the trans}\\\r
- \r
- \LeftComment{Iterate over all the slots saved locally}\r
- \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
- \State $TransSet \gets TransSet \cup \{c |c \in DE',c$is a $trans\}$\r
- \EndFor\r
- \State \Return{$TransSet$}\r
+\Function{CheckCreateLastMsgEntry}{$seq_a, id_a$}\r
+ \State $AllLastMsg \gets$ \Call{GetLastMsg}{}\\\r
+ \r
+ \LeftComment{Already Has one}\r
+ \If{$\exists \tuple{seq', id'} \in AllLastMsg, id_a=id' \land seq'=seq_a$}\r
+ \State \Return{$\emptyset$}\r
+ \EndIf\\\r
+ \r
+ \LeftComment{Not latest slot from that client}\r
+ \If{$\exists \tuple{seq_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots, id_a=id' \land seq_1'>seq_a$}\r
+ \State \Return{$\emptyset$}\\\r
+ \EndIf\\\r
+ \r
+ \State \Return{$\{\tuple{seq_a, id_a}\}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+%Evaluate Guard\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Evaluate Guard:}\\\r
+Evaluate Guard Condition checks if all the KV pairs in the guard condition match the declared KV pairs.\r
+\begin{algorithmic}[1]\r
+\Function{EvaluateGuard}{$G_a, KV_a$}\r
+\r
+ \If{$\exists \tuple{k_G, v_G} \in G_a, \tuple{k_{KV},v_{KV}} \in KV_a, k_G=K_{KV} \land v_G \neq v_{KV}$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \r
+ \State \Return{True}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Get all aborts\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{Get all aborts:}\\\r
-Get all aborts that are currently in the local block chain. Iterate over all the local slots and extract all the aborts from each slot.\\\r
+Get all aborts that are currently in the local block chain. Iterate over all the local slots and extract all the aborts from each slot.\r
\begin{algorithmic}[1]\r
\Function{GetAborts}{$ $}\r
\State $AbrtSet \gets \emptyset$ \Comment{Set of the aborts}\\\r
\r
\LeftComment{Iterate over all the slots saved locally}\r
- \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
- \State $AbrtSet \gets AbrtSet \cup \{c |c \in DE',c$is a $abort\}$\r
+ \ForAll{$\tuple{s_1', \tuple{seq',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
+ \ForAll{$a' \in DE', a'$ is a $abort$}\r
+ \State $\tuple{seq_l', seq_s', id', arb', seq_{arb}'} \gets a'$\r
+ \State $AbrtSet \gets AbrtSet \cup \{seq_l', seq_s', id', arb', seq_{arb}', seq'\}$\r
+ \EndFor\r
\EndFor\r
\State \Return{$AbrtSet$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Get all Queue States\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{Get all queue states:}\\\r
-Get all qstates that are currently in the local block chain. Iterate over all the local slots and extract all the qstates from each slot.\\\r
+Get all qstates that are currently in the local block chain. Iterate over all the local slots and extract all the qstates from each slot.\r
\begin{algorithmic}[1]\r
\Function{GetQStates}{$ $}\r
\State $QSet \gets \emptyset$ \Comment{Set of the qstates}\\\r
\r
\LeftComment{Iterate over all the slots saved locally}\r
- \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
- \State $QSet \gets QSet \cup \{c |c \in DE',c$is a $qstate\}$\r
+ \ForAll{$\tuple{s_1', \tuple{seq',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
+ \ForAll{$q' \in DE', q'$ is a $qstate$}\r
+ \State $\tuple{size'} \gets q'$\r
+ \State $QSet \gets QSet \cup \{\tuple{size', seq'}\}$\r
+ \EndFor\r
\EndFor\r
\State \Return{$QSet$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Get all New Keys\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get all new keys:}\\\r
+Get all new keys that are currently in the local block chain. Iterate over all the local slots and extract all the new keys from each slot.\r
+\begin{algorithmic}[1]\r
+\Function{GetNewKeys}{$ $}\r
+ \State $NKSet \gets \emptyset$ \Comment{Set of the new keys}\\\r
+ \r
+ \LeftComment{Iterate over all the slots saved locally}\r
+ \ForAll{$\tuple{s_1', \tuple{seq',id_1',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
+ \ForAll{$nk' \in DE', nk'$ is a $newkey$}\r
+ \State $\tuple{k', id_2'} \gets nk'$\r
+ \State $NKSet \gets NKSet \cup \{\tuple{k', id_2', seq'}\}$\r
+ \EndFor\r
+ \EndFor\r
+ \State \Return{$NKSet$}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Get all Collision Resolutions\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get all collision resolutions:}\\\r
+Get all the collision resolution entries fron the slots. \r
+\begin{algorithmic}[1]\r
+\Function{GetColRes}{$ $}\r
+ \State $CRSet \gets \emptyset$ \Comment{Set of the new keys}\\\r
+ \r
+ \LeftComment{Iterate over all the slots saved locally}\r
+ \ForAll{$\tuple{s_1', \tuple{seq',id_1',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
+ \ForAll{$cr' \in DE', nk'$ is a $colres$}\r
+ \State $\tuple{id', seq_{old}', seq_{new}', local'} \gets cr'$\r
+ \State $CRSet \gets CRSet \cup \{\tuple{id', seq_{old}', seq_{new}', local', seq'}\}$\r
+ \EndFor\r
+ \EndFor\r
+ \State \Return{$CRSet$}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
\r
% Get all Last Messages States\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Get all last message data entrues:}\\\r
-Get all last msg that are currently in the local block chain. Iterate over all the local slots and extract all the last msg from each slot.\\\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get all last message data entries:}\\\r
+Get all last msg that are currently in the local block chain. Iterate over all the local slots and extract all the last msg from each slot.\r
\begin{algorithmic}[1]\r
\Function{GetLastMsg}{$ $}\r
\State $LMSet \gets \emptyset$ \Comment{Set of the last msg}\\\r
\r
\LeftComment{Iterate over all the slots saved locally}\r
- \ForAll{$\tuple{s_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
- \State $LMSet \gets LMSet \cup \{c |c \in DE',c$is a $lastmsg\}$\r
+ \ForAll{$\tuple{s_1', \tuple{seq_1',id_1',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
+ \ForAll{$lm' \in DE', lm'$ is a $lastmsg$}\r
+ \State $\tuple{seq_2', id_2'} \gets lm'$\r
+ \State $LMSet \gets LMSet \cup \{\tuple{seq_2', id_2', seq_1'}\}$\r
+ \EndFor\r
\EndFor\r
\State \Return{$LMSet$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}%\r
+%}\r
+\r
+% Get all Transaction Parts\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get all the transaction part entries:}\\\r
+Get all the transaction parts from the slots.\r
+\begin{algorithmic}[1]\r
+\Function{GetTransParts}{$ $}\r
+ \State $TPSet \gets \emptyset$ \r
+ \r
+ \LeftComment{Iterate over all the slots saved locally}\r
+ \ForAll{$\tuple{s_1', \tuple{seq_1',id_1',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
+ \ForAll{$tp' \in DE', tp'$ is a $transpart$}\r
+ \State $\tuple{Dat',arb',seq_{clientLocal}', seq_{server}', id', partnum', isLast'} \gets tp'$\r
+ \State $TPSet \gets TPSet \cup \{\tuple{Dat',arb',seq_{clientLocal}', seq_{server}', id', partnum', isLast', seq_1'}\}$\r
+ \EndFor\r
+ \EndFor\r
+ \State \Return{$TPSet$}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}%\r
+%}\r
+\r
+% Get all Commit Parts\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get all the commit part entries:}\\\r
+Get all the commit parts from the slots.\r
+\begin{algorithmic}[1]\r
+\Function{GetComParts}{$ $}\r
+ \State $CPSet \gets \emptyset$ \r
+ \r
+ \LeftComment{Iterate over all the slots saved locally}\r
+ \ForAll{$\tuple{s_1', \tuple{seq_1',id_1',DE',hmac_p',hmac_c'}} \in LocalSlots$}\r
+ \ForAll{$cp' \in DE', cp'$ is a $compart$}\r
+ \State $\tuple{Dat',seq_{trans}', seq_{server}', id', partnum', isLast'} \gets cp'$\r
+ \State $CPSet \gets CPSet \cup \{\tuple{Dat',seq_{trans}', seq_{server}', id', partnum', isLast', seq_1'}\}$\r
+ \EndFor\r
+ \EndFor\r
+ \State \Return{$CPSet$}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}%\r
+%}\r
+\r
+\r
+\r
+\r
+\r
\r
% Check Queue State Live\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{Check Queue State Live:}\\\r
-A queue state is dead if there is another queue state data entry that has a larger queue state.\\\r
+A queue state is dead if there is another queue state data entry that has a larger queue state.\r
\begin{algorithmic}[1]\r
-\Function{CheckQStateLive}{$qstate_a$}\r
+\Function{CheckQStateLive}{$qstate_a, seq_a$}\r
\State $\tuple{size_a} \gets qstate_a$\r
\State $AllQStates \gets$ \Call{GetQState}{} \Comment{Get all the qstates} \\\r
\r
- \If{$\exists \tuple{size'} \in AllQStates, size' > size_a$}\r
+ \If{$\exists \tuple{size', seq'} \in AllQStates, size' > size_a$}\r
+ \State \Return{false}\r
+ \ElsIf{$\exists \tuple{size', seq'} \in AllQStates, size' = size_a \land seq' > seq_a$}\r
\State \Return{false}\r
\EndIf\r
\State \Return{true}\r
\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-% Check Commit Live\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Check Commit Live:}\\\r
-A commit is dead if for every key value pair in the commit there is a commit with a larger transaction sequence number that has a key value pair with the same key.\\\r
-\begin{algorithmic}[1]\r
-\Function{CheckCommitLive}{$commit_a$}\r
- \State $\tuple{seq_{a_{trans}},KV_a} \gets commit_a$\r
- \State $KSet \gets \{k|\tuple{k,v} \in KV\}$\r
- \State $AllCommits \gets$ \Call{GetCommits}{} \Comment{Get all the commits} \\\r
- \r
- \LeftComment{Iterate all commits that are newer in time}\r
- \ForAll{$\tuple{seq_{trans}',KV'}\in AllCommits, seq_{trans}' > seq_{a_{trans}}$}\r
- \State $KVSet \gets KVSet \setminus \{k|\tuple{k,v} \in KV'\}$\\\r
- \r
- \If{$KVSet = \emptyset$}\r
- \State \Return{false} \Comment{All keys have a newer commit}\r
- \EndIf\r
- \EndFor\r
- \State \Return{true} \Comment{If got here then some keys still live}\r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Check Last Message Live\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{Check Last Message Live:}\\\r
-The last message is dead if the device in question pushed a slot that has a larger sequence number than the one recorded in the last message data entry. \\\r
+The last message is dead if the device in question pushed a slot that has a larger sequence number than the one recorded in the last message data entry. \r
\begin{algorithmic}[1]\r
\Function{CheckLastMsgLive}{$lastmsg_a$}\r
\State $\tuple{seq_a, id_a} \gets lastmsg_a$\\\r
+ \State $AllLastMsg \gets$ \Call{GetLastMsg}{} \Comment{Get all the last messages} \\\r
\r
- \If{$\exists \tuple{id', seq'} \in LastSlot, id'=id_a \land seq' > seq_a$}\r
+ \If{$\exists \tuple{seq_1', id', seq_2'} \in AllLastMsg, id'=id_a \land seq_1' > seq_a$}\r
\State \Return{false}\r
- \EndIf\r
- \State \Return{True} \r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-%Check Collision Resolution Live\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Check Collision Resolution Live:}\\\r
-Check if a collision resolution data entry is live or not. This done by checking if all clients that we know about have seen the collision resolution entry. This is checked by seeing if all devices have inserted a message with a larger sequence number into the block chain.\\\r
-\begin{algorithmic}[1]\r
-\Function{CheckColResLive}{$colres_a$}\r
- \State $\tuple{id_a, seq_{a_{old}}, seq_{a_{new}}, equal_a} \gets colres_a$\\\r
- \r
- \If{$\forall \tuple{id', seq'} \in LastSlot, seq' \geq seq_{a_{new}}$}\r
+ \ElsIf{$\exists \tuple{seq_1', id', seq_2'} \in AllLastMsg, id'=id_a \land seq_1' = seq_a \land seq_2' > seq_a$}\r
\State \Return{false}\r
\EndIf\r
- \State \Return{true}\r
+ \r
+ \State \Return{True} \r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Check New Key Live\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{Check New Key Live:}\\\r
-A new key data entry is always live.\\\r
+A new key data entry is always live unless there is a resuced version of the new key that is newer.\r
\begin{algorithmic}[1]\r
-\Function{CheckNewkeyLive}{$newkey_a$}\r
- \State \Return{True} \r
+\Function{CheckNewkeyLive}{$newkey_a, seq$}\r
+ \State $\tuple{k_a, id_a} \gets newkey_a$\r
+ \State $AllNewKeys \gets$ \Call{GetNewKeys}{} \Comment{Get all the new keys} \\\r
+ \r
+ \If{$\exists \tuple{k', id', seq'} \in AllNewKeys, k'=k_a \land id'=id_a \land seq' > seq$}\r
+ \State \Return{False}\r
+ \ElsIf{$\exists \tuple{k', id', seq'} \in AllNewKeys, k'=k_a \land id'\neq id_a \land seq' > seq$}\r
+ \State \Return{False} \Comment{Delete an attempt to insert a new key that already exists}\r
+ \EndIf\r
+ \r
+ \State \Return{True} \r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Check Abort Live\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{Check Abort Live:}\\\r
-Check if an abort data entry is live or not. Abort is dead if the device whos transaction was aborted sees the abort. This is checked by seeing if that device inserted a slot into the block chain which has a sequence numberl that is larger than the aborts sequence number.\\\r
+Check if an abort data entry is live or not. Abort is dead if the device whos transaction was aborted sees the abort. This is checked by seeing if that device inserted a slot into the block chain which has a sequence number that is larger than the aborts sequence number.\r
\begin{algorithmic}[1]\r
\Function{CheckAbortLive}{$abort_a, seq_a$}\r
\State $\tuple{seq_{a_{trans}},id_a} \gets abort_a$\\\r
\LeftComment{The device whos transaction was aborted saw the abort}\r
\If{$\exists \tuple{id', seq'} \in LastSlot, id'=id_a \land seq' > seq_a$}\r
\State \Return{false}\r
+ \Else\r
+ \State $AllAborts \gets$ \Call{GetAborts}{} \Comment{Get all the aborts} \\\r
+ \If{$\exists \tuple{seq_{trans}',id_{trans}', seq'} \in AllAborts, seq_{a_{trans}} = seq_{trans}' \land id_a = id_{trans}' \land seq' > seq_a$}\r
+ \State \Return{false}\r
+ \EndIf\r
\EndIf\r
\State \Return{True} \r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Check Transaction Live\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Check Transaction Live:}\\\r
-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.\\\r
+%Check Collision Resolution Live\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Check Collision Resolution Live:}\\\r
+Check if a collision resolution data entry is live or not. This done by checking if all clients that we know about have seen the collision resolution entry. This is checked by seeing if all devices have inserted a message with a larger sequence number into the block chain.\r
\begin{algorithmic}[1]\r
-\Function{CheckTransLive}{$trans_a$}\r
- \State $\tuple{seq_a, id_a, KV_a, Guard_a} \gets trans_a$\r
- \State $AllCommits \gets$ \Call{GetCommits}{} \Comment{Get all the commits}\r
- \State $AllAborts \gets$ \Call{GetAborts}{} \Comment{Get all the aborts} \\\r
+\Function{CheckColResLive}{$colres_a, seq_a$}\r
+ \State $\tuple{id_a, seq_{a_{old}}, seq_{a_{new}}, equal_a} \gets colres_a$\\\r
\r
- \If{$\exists \tuple{seq_{abrt}',seq_{trans}',id'} \in AllAborts, seq_{trans}' = seq_a$}\r
+ \If{$\forall \tuple{id', seq'} \in LastSlot, seq' \geq seq_{a_{new}}$}\r
\State \Return{false}\r
- \ElsIf{$\exists \tuple{seq_{trans}',KV'} \in AllCommits, seq_{trans}' \geq seq_a$}\r
+ \EndIf\r
+ \r
+ \State $AllColRes \gets$ \Call{GetColRes}{}\r
+ \If{$\exists \tuple{id', seq_{old}', seq_{new}', local', seq'} \in AllColRes, id'=id_a \land seq_{old}'= seq_{a_{old}} \land seq_{new}'= seq_{a_{new}} \land local'=equal_a \land seq_2' > seq_a$}\r
\State \Return{false}\r
\EndIf\r
+ \r
\State \Return{true}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
+\r
+%Check Transaction Part Live\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Check Transaction Part Live:}\\\r
+Check if a transaction part is live or not.\r
+\begin{algorithmic}[1]\r
+\Function{CheckTransPartLive}{$transpart_a, seq_a$}\r
+ \State $\tuple{Dat, arb,seq_{clientLocal}, seq_{server}, id, partnum,isLast} \gets transpart_a$\r
+ \r
+ \If{$\exists \tuple{id',seq'} \in LastTransactionArbitrated \land id'=arb land seq' \geq seq_{server}$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \r
+ \State $AllTransParts \gets$ \Call{GetTransParts}{} \r
+ \If{$\exists \tuple{Dat',arb',seq_{clientLocal}', seq_{server}', id', partnum', isLast', seq'} \in AllTransParts, seq_{server} = seq_{server}' \land partnum' = partnum \land seq' > seq_a$}\r
+ \State \Return{false}\r
+ \EndIf \r
+ \State \Return{True}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+%Check Commit Part Live\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Check Commit Part Live:}\\\r
+Check if a commit part is live or not.\r
+\begin{algorithmic}[1]\r
+\Function{CheckCommitPartLive}{$commitpart_a, seq_a$}\r
+ \State $\tuple{Dat,seq_t, seq_s, id, partnum, isLast, seq} \gets commitpart_a$\r
+ \State $AllComParts \gets $ \Call{GetComParts}{}\\\r
+ \r
+ \If{$\exists \tuple{Dat',seq_t', seq_s', id, partnum', isLast', seq'} \in AllComParts, seq_s = seq_s' \land partnum'= partnum \land seq' > seq_a$}\r
+ \State \Return{False}\r
+ \EndIf\r
+ \r
+ \ForAll{$\tuple{P, KV, seq_t, seq_s,id} \in LiveCommits$}\r
+ \If{$commitpart_a \in P$}\r
+ \State \Return{True}\r
+ \EndIf\r
+ \EndFor\r
+ \r
+ \State \Return{False}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
\r
% Check Live\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{Check Live:}\\\r
-Checks if a data entry is live based on its type.\\\r
+Checks if a data entry is live based on its type.\r
\begin{algorithmic}[1]\r
\Function{CheckLive}{$datentry, seq$}\r
- \If{$datentry$ is a $commit$}\r
- \State \Return{\Call{CheckCommitLive}{$datentry$}}\\r
+ \If{$datentry$ is a $compart$}\r
+ \State \Return{\Call{CheckCommitPartLive}{$datentry, seq$}}\\r
\ElsIf{$datentry$ is a $abort$}\r
\State \Return{\Call{CheckAbortLive}{$datentry, seq$}}\\r
- \ElsIf{$datentry$ is a $trans$}\r
- \State \Return{\Call{CheckTransLive}{$datentry$}}\\r
+ \ElsIf{$datentry$ is a $transpart$}\r
+ \State \Return{\Call{CheckTransPartLive}{$datentry,seq$}}\\r
\ElsIf{$datentry$ is a $lastmsg$}\r
- \State \Return{\Call{CheckLastMsgLive}{$datentry$}}\\r
+ \State \Return{\Call{CheckLastMsgLive}{$datentry, seq$}}\\r
\ElsIf{$datentry$ is a $colres$}\r
- \State \Return{\Call{CheckColResLive}{$datentry$}}\\r
+ \State \Return{\Call{CheckColResLive}{$datentry, seq$}}\\r
\ElsIf{$datentry$ is a $qstate$}\r
- \State \Return{\Call{CheckQStateLive}{$datentry$}}\r
+ \State \Return{\Call{CheckQStateLive}{$datentry, seq$}}\r
\ElsIf{$datentry$ is a $newkey$}\r
- \State \Return{\Call{CheckNewkeyLive}{$datentry$}}\r
+ \State \Return{\Call{CheckNewkeyLive}{$datentry, seq$}}\r
\Else\r
\State \Call{Error}{"Unknown data entry type."}\r
\EndIf\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Slot Has Live\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{Slot Has Live:}\\\r
-Check if the slot has any live data entries in it. Do this by looking at all the data entries in the slot and checking if they are live\\\r
+Check if the slot has any live data entries in it. Do this by looking at all the data entries in the slot and checking if they are live.\r
\begin{algorithmic}[1]\r
\Function{SlotHasLive}{$slot_a$}\r
- \State $\tuple{s_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in LocalSlots$\r
+ \State $\tuple{seq_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in LocalSlots$\r
\r
\ForAll{$datentry \in DE$}\r
- \If{\Call{CheckLive}{$datentry, s_1$}} \Comment{an entry is alive}\r
+ \If{\Call{CheckLive}{$datentry, seq_1$}} \Comment{an entry is alive}\r
\State \Return{true}\r
\EndIf\r
\EndFor\r
\State \Return{false} \Comment{All entries were dead} \r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-% Calculate Resize Threshold\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Calculate Resize Threshold:}\\\r
-Calculate a threshold for how many slots need to have live data entries in them for a resize to take place.\\\r
-\begin{algorithmic}[1]\r
-\Function{CalcResizeThresh}{$maxsize$}\r
- \State \Return{$\left \lfloor {maxsize * RESIZE\_THRESH\_PERCENT} \right \rfloor$}\r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Calculate Block Chain New Size\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Calculate Block Chain New Size:}\\\r
-Calculate the new size of the block chain which we need if we are to resize the data structure.\\\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{CalcNewSize}{$maxsize$}\r
- \State \Return{$\left \lceil {maxsize * RESIZE\_THRESH\_PERCENT} \right \rceil$}\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
+ \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
+%\end{varwidth}% \r
+%}\r
\r
-% Should Resize\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Should Resize:}\\\r
-Check if the block should resize based on some metric of how many slots in the block chain are filled with live data. \\\r
+% Mandatory Rescue\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Mandatory Rescue:}\\\r
+This rescue is mandatory before any types of data entries (excpet queue states) can be placed into the data entry section of the new slot. Returns the data entry Set or null if the first slot could not be cleared (the live data in that slot could not fit in this current slot).\r
\begin{algorithmic}[1]\r
-\Function{ShouldResize}{$ $}\r
- \State $LiveSlots \gets \{slot_s|slot_s \in LocalSlots \land $\Call{SlotHasLive}{$slot_s$}$\}$\r
- \State $resizethreshold \gets $ \Call{CalcResizeThresh}{$max\_size$}\r
- \State \Return{$|LiveSlots| \geq resizethreshold$} \Comment{If passes threshold then resize}\r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-% Create Queue State \r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Create Queue State:}\\\r
-Generate a queue state data entry.\\\r
-\begin{algorithmic}[1]\r
-\Function{CreateQState}{$size_a$}\r
- \State \Return{$\tuple{size_a}$} \r
+\Function{MandatoryRescue}{$DE_a$}\r
+ \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
+ \State $cseq \gets smallestseq$\\\r
+ \r
+ \LeftComment{Check the least slots to rescue and live entries}\r
+ \While{$cseq < (smallestseq + DEAD\_SLOT\_COUNT)$}\r
+ \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
+ \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\r
+ \State $DE' \gets DE' \cup$ \Call{CheckCreateLastMsgEntry}{$seq', id'$} \Comment{Get the last message too if we need it}\\\r
+ \r
+ \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
+ \If{\Call{CheckLive}{$de, cseq$}} \Comment{data entry is live}\r
+ \If{\Call{DEHasSpace}{$DE_a, de$}}\r
+ \State $DE_a \gets DE_a \cup de$ \Comment{Had enough space to add it}\r
+ \ElsIf{$currentseq = smallestseq$}\r
+ \State \Return{$\tuple{$true$,DE_a}$}\r
+ \Else\r
+ \State \Return{$\tuple{$false$,DE_a}$}\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
+ \EndWhile\r
+ \r
+ \State \Return{$\tuple{$false$,DE_a}$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Create Abort\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Create Abort:}\\\r
-Generate a abort data entry.\\\r
+% Optional Rescue\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Optional Rescue:}\\\r
+This rescue is not mandatory. This is trying to fill the remaining portion of the slot with rescued data so that no space is wasted. If we encounter a data entry that does not fit move on to the next, maybe that one will fit. Do this until we skipped too many live data entries.\r
\begin{algorithmic}[1]\r
-\Function{CreateAbort}{$seq_a, id_a$}\r
- \State \Return{$\tuple{seq_a, id_a}$}\r
+\Function{OptionalRescue}{$DE_a$}\r
+ \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
+ \State $largestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \geq seq')$\r
+\r
+ \State $numofskips \gets 0$\r
+ \State $cseq \gets smallestseq$\\\r
+ \r
+ \LeftComment{Check the least slots to rescue and live entries}\r
+ \While{$cseq < largestseq$}\r
+ \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
+ \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\\\r
+ \r
+ \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
+ \If{\Call{CheckLive}{$de, cseq$}} \Comment{data entry is live}\r
+ \State $de \gets $ \Call{CreateRescuedEntry}{de} \Comment{Resize entry if needed}\\\r
+ \r
+ \If{$de \in DE_a$} \Comment{Already being rescued}\r
+ \State Continue\r
+ \EndIf\\\r
+ \r
+ \If{\Call{DEHasSpace}{$DE_a, de$}}\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
+ $numofskips \gets numofskips +1$\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
+ \EndWhile\r
+ \r
+ \State \Return{$DE_a$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\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
+% Create New Slot\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Create New Slot:}\\\r
+Create a slot and encrypt it.\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
+\Function{CreateNewSlot}{$seq_a, DE_a$}\r
+ \State $\tuple{seq, SDE} \gets \tuple{seq', SDE'}$ such that $\tuple{seq', SDE'}\in LocalSlots \land (\forall \tuple{seq'', DE''} \in LocalSlots, seq' \geq seq'')$\r
+ \State $\tuple{seq,id,DE,hmac_p,hmac_c} \gets SDE$\r
+ \State $newhmac \gets $ \Call{GenerateHmac}{$seq_a, LOCAL\_ID, DE_a, hmac_p$}\r
+ \State $newSDE \gets \tuple{seq,LOCAL\_ID,DE_a,hmac_c,newhmac}$\r
+ \State $encryptnewSDE \gets $\Call{Encrypt}{newSDE}\r
+ \State \Return{$\tuple{seq_a, encryptnewSDE}$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
\r
-% Create Transaction\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Create Transaction:}\\\r
-Generate a transaction data entry.\\\r
-\begin{algorithmic}[1]\r
-\Function{CreateTrans}{$pendingtrans_a, seq_a$}\r
- \State $\tuple{KV_a, Guard_a} \gets pendingtrans_a$\r
- \State \Return{$\tuple{seq_a, LOCAL\_ID, KV_a, Guard_a}$} \r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
\r
-% Create Commit\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Create Commit:}\\\r
-Generate a commit data entry.\\\r
-\begin{algorithmic}[1]\r
-\Function{CreateCommit}{$seq_a,KV_a$}\r
- \State \Return{$\tuple{seq_a,KV_a}$}\r
-\EndFunction\r
-\end{algorithmic}\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
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+% Fill Slot\r
+%% \noindent\fbox{%\r
+%% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+% \begin{algorithm}\r
+\textbf{Fill Slot:}\\\r
+Fill a slot with data that needs to be inserted into the block chain.\r
\begin{algorithmic}[1]\r
-\Function{CreateNewKey}{$k_a, id_a$}\r
- \State \Return{$\tuple{k_a,id_a}$}\r
+\Function{FillSlot}{$newkey_a $}\r
+ \State $resize \gets False$\r
+ \State $newsize \gets 0$\r
+ \r
+ \State $DE \gets \emptyset$ \Comment{The data entries for this slot} \label{resetMarker}\r
+ \State $seq \gets $ \Call{GetNextSeq}{} \Comment{Get the sequence number for this slot}\r
+\r
+ \r
+ \State $resize \gets resize \lor $ \Call{ShouldResize}{ } \Comment{Check if we should resize}\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 $\tuple{needRezize,DE} \gets$ \Call{MandatoryRescue}{$DE$} \Comment{Round 1 of rescue}\r
+ \If{$needRezize \land \lnot resize$}\r
+ \LeftComment{Data was going to fall off the end so try again with a forced resize}\r
+ \State $resize \gets $ true\r
+ \State \Goto{resetMarker}\r
+ \EndIf\\\r
+ \r
+ \If{$newkey_a \neq NULL \land $\Call{DEHasSpace}{$DE, newkey_a$}}\r
+ \State $DE \gets DE \cup \{newkey_a\}$\r
+ \EndIf\\\r
+ \r
+ \ForAll{$\tuple{commit, AbortSet, SentSet} \in ArbitrationRound$ in order of insertion}\r
+ \ForAll{$abort \in (AbortSet \setminus SentSet)$} \r
+ \State $\tuple{seq_{clientlocal}, seq_{server}, id, arb, seq_{arb}} \gets abort$\r
+ \State $abort \gets \tuple{seq_{clientlocal}, seq, id, arb, seq_{arb}}$ \Comment{Set sequence number}\r
+ \r
+ \If{\Call{DEHasSpace}{$De, abort$}}\r
+ \State $DE \gets DE \cup abort$\r
+ \Else\r
+ \State \Goto{EndArb}\r
+ \EndIf\r
+ \EndFor\r
+ \r
+ \If{$commit \neq NULL$}\r
+ \If{\Call{DEHasSpace}{$De, commit$}}\r
+ \State $DE \gets DE \cup commit$\r
+ \Else\r
+ \State \Goto{EndArb}\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor \label{EndArb}\r
+ \r
+ \r
+ \If{$|PendingTransactionQueue| > 0$}\r
+ \State $\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb}, Sent, hadTimeout} \gets PendingTransactionQueue.peak()$\r
+ \r
+ \If{$(|Sent| = 0 \land \lnot hadTimeout) \lor (seq_s = -1)$}\r
+ \State $seq_s \gets seq$\r
+ \ForAll{$part \in P$}\r
+ \State $\tuple{Dat,arb,seq_{cl}, seq_{server}, id, partnum, isLast} \gets part$\r
+ \State $part \gets \tuple{Dat,arb,seq_{cl}, seq, id, partnum, isLast}$\r
+ \EndFor\r
+ \EndIf\r
+ \r
+ \ForAll{$part \in (P \setminus Sent)$}\r
+ \If{\Call{DEHasSpace}{$De, part$}}\r
+ \State $DE \gets DE \cup part$\r
+ \Else\r
+ \State \Goto{EndTrans}\r
+ \EndIf\r
+ \EndFor\r
+ \EndIf \label{EndTrans}\r
+ \r
+\r
+ \LeftComment{Rescue data to fill slot data entry section}\r
+ \State $DE \gets$ \Call{OptionalRescue}{$DE$}\\\r
+ \State $newslot \gets $\Call{CreateNewSlot}{$seq, DE$}\r
+ \State \Return{$\tuple{newslot,DE, newsize}$} \r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+% \end{algorithm}\r
+\r
+% %\end{varwidth}% \r
+% } \r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+% Send to Server\r
+%% \noindent\fbox{%\r
+%% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+% \begin{algorithm}\r
+\textbf{Send to Server:}\\\r
+Send local data to server if there is any local data that needs to be sent.\r
+\algblock[TryCatchFinally]{try}{endtry}\r
+\algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}\r
+\algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}\r
+ [1]{\textbf{catch} #1}\r
+ {\textbf{end try}}\r
\r
-% Data Entry Set Has Space \r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Data Entry Set Has Space :}\\\r
-Checks if a data entry set has enough space for a new data entry to be inserted.\\\r
\begin{algorithmic}[1]\r
-\Function{DEHasSpace}{$DE_a, de_a$}\r
- \State $newsize \gets $ \Call{GetSize}{$DE_a$}\r
- \State $newsize \gets newsize +$ \Call{GetSize}{$de_a$}\r
- \State \Return{$newsize \leq DATA\_ENTRY\_SET\_MAX\_SIZE$}\r
+\Function{SendToServer}{$slot_a, newsize_a$} throws $Server\_Connection\_Timeout$, $Server\_Response\_Timeout$\r
+ \State $\tuple{seq_a, DE_A} \gets slot_a$\r
+ \State $EDE_a \gets $ \Call{Encrypt}{$DE_A$}\r
+ \State $slot_a \gets \tuple{seq_a, EDE_a}$\r
+ \State $\tuple{success, NewSlots} \gets$ \Call{PutSlot}{$seq_a, newslot, newsize_a$}\\\r
+ \r
+ \If{$success$}\r
+ \State $RejectedSlotList \gets \emptyset$\r
+ \State \Return{$\tuple{true, \{newslot\}}$}\r
+ \Else\r
+ \If{$|newslots| = 0$}\r
+ \State \Call{Error}{"Server rejected but did not send any slots"}\r
+ \EndIf\\\r
+ \r
+ \State $NewSlots_{decrypt} \gets \emptyset$\r
+ \ForAll{$\tuple{seq', EDat'} \in NewSlots$}\r
+ \State $DDat \gets $ \Call{Decrypt}{$EDat'$}\r
+ \State $NewSlots_{decrypt} \gets NewSlots_{decrypted} \cup \tuple{seq',DDat}$\r
+ \EndFor\\\r
+ \r
+ \If{$hadPartialSendToServer$}\r
+ \r
+ \If{$\exists \tuple{seq_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in NewSlots_{decrypt}, id=LOCAL\_ID \land seq_2 = seq_a$}\r
+ \Return{$\tuple{true, NewSlots_{decrypted}}$}\r
+ \EndIf\\\r
+ \r
+ \If{$\exists \tuple{seq_1, \tuple{seq_2,id,DE,hmac_p,hmac_c}} \in NewSlots_{decrypt}, \exists \tuple{seq', id'} \in DE, \tuple{seq', id'}$ is a $ \land id'=LOCAL\_ID \land seq'=seq_a$}\r
+ \Return{$\tuple{true, NewSlots_{decrypted}}$}\r
+ \EndIf\r
+ \EndIf\\\r
+ \r
+ \State $RejectedSlotList \gets RejectedSlotList \cup \{seq_a\}$\r
+ \State \Return{$\tuple{false, NewSlots_{decrypted}}$}\r
+ \EndIf\\\r
+ \r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+% \end{algorithm}\r
+% %\end{varwidth}% \r
+% }\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+% Send to Server\r
+%% \noindent\fbox{%\r
+%% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+% \begin{algorithm}\r
+\textbf{Send to Server:}\\\r
+Send local data to server if there is any local data that needs to be sent.\r
+\algblock[TryCatchFinally]{try}{endtry}\r
+\algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}\r
+\algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}\r
+ [1]{\textbf{catch} #1}\r
+ {\textbf{end try}}\r
\r
-% Create Rescued Commit\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Create Rescued Date Entry:}\\\r
-For commits only the key-value pairs that are most recent (no newer commit that has those key values in it).\\\r
\begin{algorithmic}[1]\r
-\Function{CreateRescuedCommit}{$commit_a$}\r
- \State $AllCommits \gets $ \Call{GetCommits}{}\r
- \State $\tuple{seq_{a_{trans}},KV_a} \gets de_a$\r
- \State $NewKV \gets KV_a$\\\r
+\Function{SendToServer}{$NewKey_a$}\r
+ \State $SlotDE \gets \emptyset$\r
+ \r
+ \try\r
+ \While{$|PendingTransactionQueue| > 0 \lor |SendArbQueue| > 0 \lor NewKey_a \neq NULL$}\r
+ \State $\tuple{slot, SlotDE, newsize} \gets $ \Call{FillSlot}{$NewKey_a$}\r
+ \State $\tuple{inserted, NewSlots} \gets $ \Call{SendToServer}{$slot, newsize$} \r
+ \If{$inserted$} \r
+ \State $NewKey_a \gets NULL$\r
+ \r
+ \r
+ \ForAll{$\tuple{commit, AbortSet, SentSet} \in ArbitrationRound$}\r
+ \State $ArbitrationRound \gets ArbitrationRound \setminus \tuple{commit, AbortSet, SentSet}$\r
+ \State $SentSet \gets SentSet \cup \{e| e\in(\{commit\} \cup AbortSet) \land e \in SlotDE\}$\r
+ \r
+ \LeftComment{Add Back to the set if not done sending}\r
+ \If{$(commit=NULL \land |AbortSet| \neq |SentSet|) \land (commit \neq NULL \land (|AbortSet|+1) \neq |SentSet|)$}\r
+ \State $ArbitrationRound \gets ArbitrationRound \cup \tuple{commit, AbortSet, SentSet}$\r
+ \EndIf\r
+ \EndFor\r
\r
- \LeftComment{Get rid of all key values that have newer commits}\r
- \ForAll{$\tuple{k_a, v_a} \in KV_a$}\r
- \LeftComment{Iterate over all commits that are newer than the rescue commit}\r
- \ForAll{$\tuple{seq', KV'} \in AllCommits, seq' > seq_{a_{trans}}$}\r
- \If{$\exists \tuple{k', v'} \in KV', k' = k_a$}\r
- \State $NewKV \gets NewKV \setminus \tuple{k_a, v_a}$\r
- \State Break\r
+ \r
+ \ForAll{$\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout} \in PendingTransactionQueue$ where $\exists p \in P, p \in SlotDE$}\r
+ \State $pos \gets PendingTransactionQueue.remove(\setminus \{\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout})$\r
+ \State $SentSet \gets SentSet \cup \{p|p \in P \land p \in SlotDE\}$\\\r
+ \r
+ \If{$|SentSet| > 0 \land id = LOCAL\_ID$}\r
+ \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
+ \State \Call{ChangeTransStatus}{$TransStatus,sentfully$}\r
+ \EndIf\\\r
+ \r
+ \If{$|P| \neq |SentSet|$}\r
+ \State $PendingTransactionQueue.insert(pos, \{\tuple{\tuple{P, KV, G,seq_l, -1,id, arb},SentSet,false})$\r
+ \ElsIf{$id = LOCAL\_ID$}\r
+ \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
+ \State \Call{ChangeTransStatus}{$TransStatus,sentfully$}\r
+ \State \Call{DeleteTransStatus}{$id,seq_l$}\r
+ \EndIf \r
+ \EndFor \r
+ \Else\r
+ \ForAll{$\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout} \in PendingTransactionQueue$ where $\exists p \in P, p \in SlotDE$}\r
+ \If{$|Sent| = 0$}\r
+ \State $PendingTransactionQueue.replace(\{\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout},\tuple{\tuple{P, KV, G,seq_l, -1,id, arb},SentSet,hadTimeout})\}$\r
\EndIf\r
\EndFor\r
- \EndFor\r
- \State \Return{$\tuple{seq_{a_{trans}}, NewKV}$}\r
+ \EndIf\r
+ \r
+ \r
+ \State \Call{ValidateAndUpdate}{$NewSlots$} \r
+ \EndWhile\r
+ \catch{$Server\_Connection\_Timeout$} \r
+ \ForAll{$\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout} \in PendingTransactionQueue$ where $\exists p \in P, p \in SlotDE$}\r
+ \If{$|Sent| = 0$}\r
+ \State $PendingTransactionQueue.replace(\{\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout}, \tuple{\tuple{P, KV, G,seq_l, -1,id, arb},SentSet,hadTimeout})$\r
+ \EndIf\r
+ \EndFor\r
+ \r
+ \State \textbf{rethrowException}\\\r
+ \r
+ \catch{$Server\_Response\_Timeout$}\r
+ \State $hadPartialSendToServer \gets True$\r
+ \ForAll{$\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout} \in PendingTransactionQueue$ where $\exists p \in P, p \in SlotDE$}\r
+ \State $PendingTransactionQueue.replace(\{\tuple{\tuple{P, KV, G,seq_l, seq_s,id, arb},SentSet,hadTimeout}, \tuple{\tuple{P, KV, G,seq_l, -1,id, arb},SentSet,True})$\r
+ \EndFor\r
+ \State \textbf{rethrowException}\r
+ \endtry\r
+ \r
+ \State \Return{$NewKey_a = NULL$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+% \end{algorithm}\r
+\r
+% %\end{varwidth}% \r
+% }\r
+\r
\r
-% Create Rescued Date Entry\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Create Rescued Date Entry:}\\\r
-Generate the data entry rescued version of the entry. For some data entry types such as commits, the entry is not rescued as is. For commits only the key-value pairs that are most recent (no newer commit that has those key values in it).\\\r
-\begin{algorithmic}[1]\r
-\Function{CreateRescuedEntry}{$de_a$}\r
\r
- \If{$de_a$is a $commit$}\r
- \State \Return{\Call{CreateRescuedCommit}{$de_a$}}\r
- \EndIf\r
- \r
- \State \Return{$de_a$} \Comment{No Modification needed}\r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
\r
% Check Slot Hmacs\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{Check Slot HMACs:}\\\r
-Check that each slot has not been tampered with by checking that the stored HMAC matches the calculated HMAC. Also check thatthe slot number reported by the server matches the slot number of the actual slot.\\\r
+Check that each slot has not been tampered with by checking that the stored HMAC matches the calculated HMAC. Also check thatthe slot number reported by the server matches the slot number of the actual slot.\r
\begin{algorithmic}[1]\r
\Function{CheckSlotsHmacAndSeq}{$Slots_a$}\r
\ForAll{$slot_a \in Slots_a$}\r
\EndFor\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Check HMAC Chain\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{Check HMAC Chain:}\\\r
-Check that the HMAC chain has not been violated.\\\r
+Check that the HMAC chain has not been violated.\r
\begin{algorithmic}[1]\r
\Function{CheckHmacChain}{$Slots_a$}\r
\State $SlotsList \gets Slots_a$ sorted by sequence number\\ \r
\r
- \r
\LeftComment{Check all new slots}\r
\ForAll{$index \in [2: |SlotsList|]$}\r
\State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets SlotList[i-1]$\r
\LeftComment{Check against slots that we already have in the block chain}\r
\If{$|LocalSlots| \neq 0$}\r
\State $\tuple{seq, SDE} \gets $\Call{MaxSlot}{$LocalSlots$}\r
- \State $\tuple{seq{last_2},id_{last},DE_{last},hmac_{last_p},hmac_{last_c}} \gets SDE$\\\r
- \r
+ \State $\tuple{seq{last_2},id_{last},DE_{last},hmac_{last_p},hmac_{last_c}} \gets SDE$\r
\State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets SlotList[1]$\\\r
\r
- \If{$(seq_{last_2} + 1) = seq_{a_1}$}\r
- \If{$hmac_{a_p} \neq hmac_{last_c}$}\r
- \State \Call{Error}{"Invalid previous HMAC."}\r
- \EndIf\r
+ \If{$(seq_{last_2} + 1) = seq_{a_1} \land hmac_{a_p} \neq hmac_{last_c}$} \r
+ \State \Call{Error}{"Invalid previous HMAC."}\r
\EndIf\r
\EndIf\r
\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
+%\end{varwidth}% \r
+%}\r
\r
% Check For Old Slots\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{Check For Old Slots:}\\\r
-Check if the slots are not new. Checks if the "new" slots are actually new or if they are older than the most recent slot that we have.\\\r
+Check if the slots are not new. Checks if the "new" slots are actually new or if they are older than the most recent slot that we have.\r
\begin{algorithmic}[1]\r
\Function{CheckOldSlots}{$Slots_a$}\r
\State $\tuple{seq_{new}, Dat_{new}} \gets$ \Call{MinSlot }{$Slots_a$} \Comment{Get the oldest new slot}\r
\r
\If{$seq_{new} \leq seq_{local}$} \Comment{The slots were not newer than what was already seen}\r
\State \Call{Error}{"Server sent old slots."}\r
- \EndIf\\\r
- \r
- \LeftComment{Check if slots have the same sequence number but different data entries}\r
- \ForAll{$\tuple{seq, Dat} \in Slots_a$}\r
- \If{$\exists \tuple{seq', Dat'} \in (LocalSlots \cup Slots_a), seq'=seq \land Dat' \neq Dat$}\r
- \State \Call{Error}{"Slot sequence number match but data does not"}\r
- \EndIf\r
- \EndFor\r
- \r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-% Get All Queue States with Sequence numbers\r
-% \noindent\fbox{%\r
-% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-% \textbf{Get All Queue States with Sequence numbers:}\\\r
-% Gets all the queue states with the sequence number of the slot that the queue state was inside.\r
-% \begin{algorithmic}[1]\r
-% \Function{GetQStateWithSeq}{$Slots_a$}\r
-% \State $QSet \gets \emptyset$\\\r
- \r
-% \ForAll{$\tuple{seq_1', \tuple{seq_2',id',DE',hmac_p', hmac_c'}} \in Slots_a$}\r
-% \ForAll{$de' \in DE'$}\r
-% \If{$de'$ is a $qstate$}\r
-% \State $QSet \gets QSet \cup \{\tuple{seq_1', de'}\}$\r
-% \EndIf\r
-% \EndFor\r
-% \EndFor\\\r
- \r
-% \State \Return{$QSet$}\r
-% \EndFunction\r
-% \end{algorithmic}\r
-% \end{varwidth}% \r
-% }\r
-\r
-% Get All Queue States\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Get All Queue States:}\\\r
-Gets all the queue states from the slots that were passed in.\\\r
-\begin{algorithmic}[1]\r
-\Function{GetQState}{$Slots_a$}\r
- \State $QSet \gets \emptyset$\\\r
- \r
- \ForAll{$\tuple{seq_1', \tuple{seq_2',id',DE',hmac_p', hmac_c'}} \in Slots_a$}\r
- \ForAll{$de' \in DE'$}\r
- \If{$de'$ is a $qstate$}\r
- \State $QSet \gets QSet \cup \{de'\}$\r
- \EndIf\r
- \EndFor\r
- \EndFor\\\r
- \r
- \State \Return{$QSet$}\r
+ \EndIf\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
+%\end{varwidth}% \r
+%}\r
\r
% Check Size With Gap\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{Check Size With Gap:}\\\r
-Checks that the block chain size is correct when there is a gap in the block chain. This check makes sure that the server is not hiding any information from the client. If there is a gap and there is only 1 queue state in the new slot entries then there must have at least that many slots since the old slot entry must have been purged. If there is more than 1 queue state then the block chain is still growing check the smallest max size and there should be at least that many slots. \\\r
+Checks that the block chain size is correct when there is a gap in the block chain. This check makes sure that the server is not hiding any information from the client. If there is a gap and there is only 1 queue state in the new slot entries then there must have at least that many slots since the old slot entry must have been purged. If there is more than 1 queue state then the block chain is still growing check the smallest max size and there should be at least that many slots. \r
\begin{algorithmic}[1]\r
\Function{CheckSizeWithGap}{$Slots_a$} \r
%\State $QSSet \gets $ \Call{GetQStateWithSeq}{$Slots_a$}\r
\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Check Size\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{Check Size:}\\\r
\begin{algorithmic}[1]\r
\Function{CheckSize}{$Slots_a$} \r
\EndIf\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-\r
-% % Initialize the expected size of the block chain\r
-% \noindent\fbox{%\r
-% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-% \textbf{Initialize the expected size of the block chain:}\\\r
-% Initialize the expected size of the block chain based on the size at the server.\\\r
-% \begin{algorithmic}[1]\r
-% \Function{InitExpSize}{$seq_a$}\r
-% \State $startingsize \gets 0$\\\r
-\r
-% \If{$seq_a < max\_size$} \Comment{Check whether saves slots are full on server}\r
-% \State $startingsize \gets seq_a$\r
-% \Else\r
-% \State $startingsize \gets max\_size$\r
-% \EndIf\\\r
- \r
-% \State \Return{$startingsize$}\r
-% \EndFunction\r
-% \end{algorithmic}\r
-% \end{varwidth}% \r
-% }\r
-\r
-% % Update the expected size of the block chain\r
-% \noindent\fbox{%\r
-% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-% \textbf{Update the expected size of the block chain:}\\\r
-% Update the expected size of the block chain.\\\r
-% \begin{algorithmic}[1]\r
-% \Function{UpdateExpSize}{$size_a$}\r
-% \State $size_a \gets size_a + 1$\\\r
- \r
-% \If{$size_a > max\_size$}\Comment{Expected size $\leq max\_size$}\r
-% \State $ssize_a \gets max_\_size$\r
-% \EndIf\\\r
- \r
-% \State \Return{$size_a$}\r
-% \EndFunction\r
-% \end{algorithmic}\r
-% \end{varwidth}% \r
-% }\r
-\r
-\r
-\r
-% Update Last Message\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Process Commit Data Entry:}\\\r
-Process a commit entry. Updates the local copy of commits.\\\r
-\begin{algorithmic}[1]\r
-\Function{UpdateLastMessage}{$seq_a, id_a, LstSlt_a, updateinglocal_a$}\r
- \State $\tuple{id_{old}, seq_{old}} \gets \tuple{id', seq'}$ such that $\tuple{id', seq'} \in LastSlot \land id'=id$\\\r
- \r
- \If{$id_a = LOCAL\_ID$}\r
- \If{$\lnot updateinglocal_a \land (seq_a \neq seq_{old})$}\r
- \LeftComment{This client did not make any updates so its latest sequence number should not change}\r
- \State \Call{Error}{"Mismatch on local machine sequence number"}\r
- \EndIf\r
- \Else\r
- \If{$seq_{old} > seq_a$}\r
- \State \Call{Error}{"Rollback on remote machine sequence number"}\r
- \EndIf\r
- \EndIf\\\r
- \r
- \State $LastSlot \gets LastSlot \setminus \{\tuple{id, seq} | \tuple{id, seq} \in LastSlot, id=id_a\}$\r
- \State $LastSlot \gets LastSlot \cup \{\tuple{id_a, seq_a}\}$\r
- \r
- \State \Return{$LstSlt_a \setminus \{\tuple{id, seq} | \tuple{id, seq} \in LstSlt_a, id=id_a\}$}\r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-% Process Commit Data Entry\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Process Commit Data Entry:}\\\r
-Process a commit entry. Updates the local copy of commits.\\\r
-\begin{algorithmic}[1]\r
-\Function{ProcessCommit}{$commit_a$}\r
- \State $\tuple{seq_{a_{trans}},KV_a} \gets commit_a$\r
- \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CommittedKV \land \tuple{k',v'}\in KV_a \land k'=k\}$\r
- \State $CommittedKV \gets (CommittedKV \setminus DKV) \cup KV_a$\r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Process Queue State Data Entry\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Process Queue State Entry:}\\\r
-Process a queue state entry. Updates the max size of the block chain\\\r
+% Process New Key Data Entry\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Process New Key Entry:}\\\r
+Process a queue state entry. Adds a key to the key arbitrator set.\r
\begin{algorithmic}[1]\r
-\Function{ProcessQState}{$qstate_a$}\r
- \State $\tuple{size_a} \gets qstate_a$\r
- \State $max\_size \gets size_a$ \Comment{Update the max size we can have}\r
+\Function{ProcessNewkey}{$newkey_a$}\r
+ \State $Arbitrator \gets Arbitrator \cup \{newkey_a\}$\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Process Collision Resolution Entry\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{Process Queue State Entry:}\\\r
-Process a collision resolution entry.\\\r
+Process a collision resolution entry.\r
\begin{algorithmic}[1]\r
\Function{ProcessColres}{$colres_a, NewSlots_a$}\r
\State $\tuple{id_a, seq_{a_{old}}, seq_{a_{new}}, isequal_a}$\r
\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Process New Key Data Entry\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Process New Key Entry:}\\\r
-Process a queue state entry. Adds a key to the key arbitrator set\\\r
+% Process Queue State Data Entry\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Process Queue State Entry:}\\\r
+Process a queue state entry. Updates the max size of the block chain.\r
\begin{algorithmic}[1]\r
-\Function{ProcessNewkey}{$newkey_a$}\r
- \State $\tuple{seq_a, k_a, id_a} \gets newkey_a$\r
- \State $Arbitrator \gets Arbitrator \cup \{\tuple{k_a,id_a}\}$\r
+\Function{ProcessQState}{$qstate_a$}\r
+ \State $\tuple{size_a} \gets qstate_a$\r
+ \State $max\_size \gets size_a$ \Comment{Update the max size we can have}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Process Process Data Entry\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Process Data Entry:}\\\r
-Process the data entry based on what kind of entry it is.\\\r
+% Process Transaction Part Entry\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Process Transaction Part Entry:}\\\r
+Process a new Transaction Part Entry.\r
\begin{algorithmic}[1]\r
-\Function{ProcessDatEntry}{$slot_a, NewSlots_a,LstSlt_a$}\r
- \If{$datentry_a$ is a $commit$}\r
- \State \Call{ProcessCommit}{$dataentry_a$}\r
- \r
- \ElsIf{$datentry_a$ is a $abort$}\r
- \LeftComment{Do Nothing in this case}\r
- \r
- \ElsIf{$datentry_a$ is a $trans$}\r
- \LeftComment{Do Nothing in this case}\r
+\Function{ProcessTransPart}{$TransactionPart_a$}\r
+ \State $\tuple{Dat,arb,seq_{clientLocal}, seq_{server}, id, partnum, isLast} \gets TransactionPart_a$\r
+ \State $Transaction \gets NULL$\\\r
\r
- \ElsIf{$datentry_a$ is a $lastmsg$}\r
- \State $\tuple{seq_a, id_a} \gets dataentry_a$\r
- \State $LstSlt_a \gets$ \Call{UpdateLastMessage}{$seq_a, id_a, LstSlt_a, false$}\r
+ \If{$\exists \tuple{id',seq'} \in LastTransactionArbitrated \land id'=arb land seq' \geq seq_{server}$}\r
+ \State \Return{}\r
+ \EndIf\\\r
\r
- \ElsIf{$datentry_a$ is a $colres$}\r
- \State \Call{ProcessColres}{$dataentry_a, NewSlots_a$}\r
- \r
- \ElsIf{$datentry_a$ is a $qstate$}\r
- \State \Call{ProcessQState}{$dataentry_a$}\r
- \r
- \ElsIf{$datentry_a$ is a $newkey$}\r
- \State \Call{ProcessNewkey}{$dataentry_a$}\r
- \r
+ \If{$\exists \tuple{Parts', KV', G',seq_{clientlocal}', seq_{server}',id', arb'} \in LiveTransactions, seq_{server}' = seq_{server}$}\r
+ \State $Transaction \gets \tuple{Parts', KV', G',seq_{clientlocal}', seq_{server}',id', arb'} \in LiveTransactions$such that$ seq_{server}' = seq_{server}$\r
+ \State $LiveTransactions \gets LiveTransactions \setminus \{Transaction\}$\r
\Else\r
- \State \Call{Error}{"Unknown data entry type."}\r
- \EndIf\r
- \r
- \State \Return{$LstSlt_a$} \r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-\r
-% Delete Local Slots\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Delete Local Slots:}\\\r
-Deletes local slots that are deleted at the server. This keeps the size of the local block chain bounded.\\\r
-\begin{algorithmic}[1]\r
-\Function{DeleteLocalSlots}{$ $}\r
- \State $\tuple{seq_{max}, Dat_{max}} \gets $ \Call{MaxSlot}{$LocalSlots$}\r
- \State $seq_{min} \gets seq_{max} - max\_size$ \Comment{Min sequence number we should keep}\r
- \State $LSDelete \gets \emptyset$\r
- \r
- \If{$|LocalSlots| \leq max\_size$}\r
- \State \Return{} \Comment{Nothing to delete}\r
+ \State $Transaction \gets \tuple{\emptyset, \emptyset, \emptyset, seq_{clientlocal}, seq_{server},id, arb}$\r
\EndIf\\\r
\r
- \State $LSDelete \gets \{\tuple{seq', Dat'}|\tuple{seq', Dat'} \in LocalSlots, seq' > seq_{min}\}$\r
- \State $LocalSlots \gets LocalSlots \setminus LSDelete$ \r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-% Create Speculative KV\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Create Speculative KV:}\\\r
-Speculates on what the most recent key value pairs will be based on the latest committed key value pairs and the uncommitted transactions.\\\r
-\begin{algorithmic}[1]\r
-\Function{SpeculateKV}{$ $}\r
- \State $AllTrans \gets$ \Call{GetTrans}{}\r
- \State $LiveTrans \gets \{t| t\in AllTrans, $\Call{CheckTransLive}{$t$}$\}$\r
- \State $CurrKV \gets CommittedKV$\r
- \State $DKV \gets \emptyset$\r
-\r
- \ForAll{$\tuple{seq_t, id_t, KV_t, Guard_t} \in LiveTrans$ ordered by $seq'$} \r
- \If{\Call{EvaluateGuard}{$Guard_t, CurrKV$}}\r
- \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CurrKV \land \tuple{k',v'}\in KV_t \land k'=k\}$\r
- \State $CurrKV \gets (CurrKV \setminus DKV) \cup KV_t$\r
- \EndIf\r
- \EndFor\r
+ \State $\tuple{Parts, KV, G,seq_{local}, seq_{server},id, arb} \gets Transaction$\r
+ \State $Parts \gets Parts \cup TransactionPart_a$\\\r
\r
- \State \Return{$CurrKV$}\r
+ \If{$\exists \tuple{Dat,arb,seq_{clientLocal}, seq_{server}, id, partnum, isLast} \in Parts \land isLast \land |Parts| = partnum$}\r
+ \State $\tuple{KV, G} \gets $\Call{DecodeParts}{$Parts$}\r
+ \EndIf\r
+ \r
+ \State $Transactin \gets \tuple{Parts, KV, G,seq_{local}, seq_{server},id,arb}$.\r
+ \State $LiveTransactions \gets LiveTransactions \cup \{Transaction\}$\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-\r
-% Validate and Update \r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Validate Update:}\\\r
-Validate the block chain and insert into the local block chain.\\\r
+% Process Abort Entry\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Process Abort Entry:}\\\r
+Process a new Abort Entry.\r
\begin{algorithmic}[1]\r
-\Function{ValidateUpdate}{$NewSlots_a, updatinglocal_a$}\r
- \State $\tuple{seq_{oldest}, Dat_{oldest}} \gets$ \Call{MinSlot}{$NewSlots_a$}\r
- \State $\tuple{seq_{newest}, Dat_{newest}} \gets$ \Call{MaxSlot}{$NewSlots_a$}\r
- \State $\tuple{seq_{local}, Dat_{local}} \gets$ \Call{MaxSlot}{$LocalSlots$}\r
- \State $LastSlotTmp \gets LastSlot$\\\r
- %\State $currsize \gets $\Call{InitExpSize}{$seq_{oldest}$}\\\r
+\Function{ProcessAbort}{$abort_a$}\r
+ \State $\tuple{seq_{cl}, seq_{s}, id, arb, seq_{arb}} \gets abort_a$\r
\r
- \State \Call{CheckSlotsHmacAndSeq}{$NewSlots_a$} \Comment{Check all the HMACs}\r
- \State \Call{CheckHmacChain}{$NewSlots_a$} \Comment{Check HMAC Chain} \r
- \State \Call{CheckOldSlots}{$NewSlots_a$} \Comment{Check if new slots are actually old slots} \r
- \State \Call{CheckSize}{$NewSlots_a$} \Comment{Check if the size is correct}\\\r
- \r
- \ForAll{$slot_a \in NewSlots_a$ in order of sequence number}\r
- \If{$slot_a \in LocalSlots$} \Comment{Client already has this slot}\r
- \State $NewSlots_a \gets NewSlots_a \setminus \{slot_a\}$\r
- \State Continue\r
- \EndIf\\\r
- \r
- \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets slot_a$\r
- \State $LstSlt_a \gets$ \Call{UpdateLastMessage}{$seq_{a_1}, id_a, LstSlt_a, updatinglocal_a$}\\\r
- \r
- \ForAll{$de_a \in DE_a$} \Comment{Process each data entry}\r
- \State $LstSlt_a \gets $ \Call{ProccessDatEntry}{$de_a, NewSlots_a,LstSlt_a$}\r
- \EndFor\\\r
+ \If{$\lnot(\exists \tuple{id',seq'} \in LastArbLocalArbitrated, id'=id \land seq' > seq_{arb})$}\r
+ \State $LastArbLocalArbitrated\gets \tuple{\tuple{id',seq'}|\tuple{id',seq'} \in LastArbLocalArbitrated, id' \neq id} \cup \{\tuple{id, }\}$\r
+ \EndIf\r
\r
- %\State $currsize \gets $ \Call{UpdateExpSize}{$currsize$}\\\r
- \State $LocalSlots \gets LocalSlots \cup \{slot_a\}$ \Comment{Add to local Chain}\r
- \EndFor\\\r
+ \If{$\lnot(\exists \tuple{id',seq'} \in LastTransactionArbitrated, id'=id \land seq' > seq_{s})$}\r
+ \State $LastTransactionArbitrated \gets \tuple{\tuple{id',seq'}|\tuple{id',seq'} \in LastTransactionArbitrated, id' \neq id} \cup \{\tuple{id, seq_{s}}\}$\r
+ \EndIf \r
\r
- \If{$seq_{oldest} > (seq_{local} +1) \land LastSlotTmp \neq \emptyset$}\r
- \LeftComment{There was a gap so there should be a complete set of information on each previously seen client}\r
- \State \Call{Error}{"Missing records for machines"}\r
+ \If{$id = LOCAL\_ID$}\r
+ \State $TransStatus \gets $ \Call{GetTransStatus}{$id, seq_{cl}$}\r
+ \State \Call{ChangeTransStatus}{$TransStatus,abort$}\r
+ \State \Call{DeleteTransStatus}{$id, seq_{cl}$}\r
+ \EndIf\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Process Commit Part Entry\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Process Commit Part Entry:}\\\r
+Process a new Commit Part Entry.\r
+\begin{algorithmic}[1]\r
+\Function{ProcessCommitPart}{$CommitPart_a$}\r
+ \State $\tuple{Dat,seq_t, seq_s, id, partnum, isLast} \gets CommitPart_a$\r
+ \State $Commit \gets NULL$\\\r
+ \r
+ \If{$\exists \tuple{P', KV', seq_t', seq_s',id'} \in LiveCommits, seq_s' = seq_s$}\r
+ \State $Commit \gets \tuple{P', KV', seq_t', seq_s',id} \in LiveCommits$ such that$ seq_{s}' = seq_{s}$\r
+ \State $LiveCommits \gets LiveCommits \setminus \{Commit\}$\r
+ \Else\r
+ \State $Commit \gets \tuple{\emptyset, \emptyset, seq_t, seq_s,id}$\r
\EndIf\\\r
\r
- \State \Call{DeleteLocalSlots}{ } \Comment{Delete old slots from local}\r
- \State $SpeculatedKV \gets $\Call{SpeculateKV}{ } \Comment{Speculate on what will be latest KV set}\r
+ \State $\tuple{P, KV, seq_t, seq_s,id} \gets Commit$\r
+ \State $P \gets P \cup CommitPart_a$\\\r
\r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-% Decrypt Validate Insert Slots\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Decrypt Validate Insert Slots:}\\\r
-Decrypts slots, validates (checks for malicious activity) slots and inserts the slots into the local block chain.\\\r
-\begin{algorithmic}[1]\r
-\Function{DecryptValidateInsert}{$NewSlots_a, updatinglocal_a$}\r
- \State $DecryptedSlots \gets \emptyset$\r
- \State $DDat \gets NULL$\\\r
+ \If{$\exists \tuple{Dat',seq_t', seq_s', id', partnum', isLast'} \in P \land isLast' \land |P| = partnum$}\r
+ \State $KV \gets $\Call{DecodeParts}{$P$}\r
+ \EndIf\\\r
\r
- \ForAll{$\tuple{seq', EDat'} \in NewSlots_a$}\r
- \State $DDat \gets $ \Call{Decrypt}{$EDat'$}\r
- \State $DecryptedSlots \gets DecryptedSlots \cup \tuple{seq',DDat}$\r
- \EndFor\\\r
- \State \Call{ValidateUpdate}{$DecryptedSlots, updatinglocal_a$}\r
+ \State $Commit \gets \tuple{P, KV, seq_t, seq_s,id}$\r
+ \State $LiveCommits \gets LiveCommits \cup \{Commit\}$\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Check and Create Last Message Data Entry\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Check and Create Last Message Data Entry:}\\\r
-Check if a last message entry needs to be created for this slot and if so create it. The check is done by checking if there are any newer slots with the same id or if there is already a last message slot with a newer sequence number\\\r
+% Update Last Message\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Process Commit Data Entry:}\\\r
+Process a commit entry. Updates the local copy of commits.\r
\begin{algorithmic}[1]\r
-\Function{CheckCreateLastMsgEntry}{$seq_a, id_a$}\r
- \State $AllLastMsg \gets$ \Call{GetLastMsg}{}\\\r
- \r
- \LeftComment{Already Has one}\r
- \If{$\exists \tuple{seq', id'} \in AllLastMsg, id_a=id' \land seq'=seq_a$}\r
- \State \Return{$\{\}$}\\\r
- \EndIf\\\r
+\Function{UpdateLastMessage}{$seq_a, id_a, updateinglocal_a, MachinesSeen$}\r
+ \State $\tuple{id_{old}, seq_{old}} \gets \tuple{id', seq'}$ such that $\tuple{id', seq'} \in LastSlot \land id'=id$\\\r
\r
- \LeftComment{Not latest slot from that client}\r
- \If{$\exists \tuple{seq_1', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \in LocalSlots, id_a=id' \land seq_1'>seq_a$}\r
- \State \Return{$\{\}$}\\\r
+ \If{$id_a = LOCAL\_ID$}\r
+ \If{$hadPartialSendToServer$}\r
+ \If{$\lnot updateinglocal_a \land (seq_a < seq_{old})$}\r
+ \LeftComment{This client did not make any updates so its latest sequence number should not change}\r
+ \State \Call{Error}{"Mismatch on local machine sequence number"}\r
+ \EndIf\r
+ \Else\r
+ \If{$\lnot updateinglocal_a \land (seq_a \neq seq_{old})$}\r
+ \LeftComment{This client did not make any updates so its latest sequence number should not change}\r
+ \State \Call{Error}{"Mismatch on local machine sequence number"}\r
+ \EndIf\r
+ \EndIf\r
+ \Else\r
+ \If{$seq_{old} > seq_a$}\r
+ \State \Call{Error}{"Rollback on remote machine sequence number"}\r
+ \EndIf\r
\EndIf\\\r
\r
- \r
- \State \Return{$\{\tuple{seq_a, id_a}\}$}\r
+ \State $LastSlot \gets LastSlot \setminus \{\tuple{id, seq} | \tuple{id, seq} \in LastSlot, id=id_a\}$\r
+ \State $LastSlot \gets LastSlot \cup \{\tuple{id_a, seq_a}\}$\r
+ \State $MachinesSeen \gets MachinesSeen \setminus \{id_a\}$\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Mandatory Rescue\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Mandatory Rescue:}\\\r
-This rescue is mandatory before any types of data entries (excpet queue states) can be placed into the data entry section of the new slot. Returns the data entry Set or null if the first slot could not be cleared (the live data in that slot could not fit in this current slot). \\\r
+% Process Process Data Entry\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Process Data Entry:}\\\r
+Process the data entry based on what kind of entry it is.\r
\begin{algorithmic}[1]\r
-\Function{MandatoryRescue}{$DE_a$}\r
- \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
- \State $cseq \gets smallestseq$\\\r
+\Function{ProcessDatEntry}{$slot_a, NewSlots_a,MachinesSeen$}\r
+ \If{$datentry_a$ is a $compart$}\r
+ \State \Call{ProcessCommitPart}{$dataentry_a$}\r
+ \r
+ \ElsIf{$datentry_a$ is a $abort$}\r
+ \LeftComment{Do Nothing in this case}\r
+ \r
+ \ElsIf{$datentry_a$ is a $transpart$}\r
+ \State \Call{ProcessTransPart}{$dataentry_a$}\r
\r
- \LeftComment{Check the least slots to rescue and live entries}\r
- \While{$cseq < (smallestseq + DEAD\_SLOT\_COUNT)$}\r
- \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
- \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\r
- \State $DE' \gets DE' \cup$ \Call{CheckCreateLastMsgEntry}{$seq', id'$} \Comment{Get the last message too if we need it}\\\r
+ \ElsIf{$datentry_a$ is a $lastmsg$}\r
+ \State $\tuple{seq_a, id_a} \gets dataentry_a$\r
+ \State \Call{UpdateLastMessage}{$seq_a, id_a, false, MachinesSeen$}\r
+ \r
+ \ElsIf{$datentry_a$ is a $colres$}\r
+ \State \Call{ProcessColres}{$dataentry_a, NewSlots_a$}\r
\r
- \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
- \If{\Call{CheckLive}{$de, cseq$}} \Comment{data entry is live}\r
- \State $de \gets $ \Call{CreateRescuedEntry}{de} \Comment{Resize entry if needed}\r
- \If{\Call{DEHasSpace}{$DE_a, de$}}\r
- \State $DE_a \gets DE_a \cup de$ \Comment{Had enough space to add it}\r
- \ElsIf{$currentseq = smallestseq$}\r
- \State \Return{$NULL$}\r
- \Else\r
- \State \Return{$DE_a$}\r
- \EndIf\r
- \EndIf\r
- \EndFor\\\r
+ \ElsIf{$datentry_a$ is a $qstate$}\r
+ \State \Call{ProcessQState}{$dataentry_a$}\r
\r
- \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
- \EndWhile\r
+ \ElsIf{$datentry_a$ is a $newkey$}\r
+ \State \Call{ProcessNewkey}{$dataentry_a$}\r
+ \Else\r
+ \State \Call{Error}{"Unknown data entry type."}\r
+ \EndIf\r
\r
- \State \Return{$DE_a$}\r
+ \State \Return{$LstSlt_a$} \r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Optional Rescue\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Optional Rescue:}\\\r
-This rescue is not mandatory. This is trying to fill the remaining portion of the slot with rescued data so that no space is wasted. If we encounter a data entry that does not fit move on to the next, maybe that one will fit. Do this until we skipped too many live data entries\\\r
+% Update Committed Table\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Update Committed Key value Table:}\\\r
+Update the table of committed Key Value Pairs based on commits that we received.\r
\begin{algorithmic}[1]\r
-\Function{OptionalRescue}{$DE_a$}\r
- \State $smallestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \leq seq')$\r
- \State $largestseq \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \geq seq')$\r
-\r
- \State $numofskips \gets 0$\r
- \State $cseq \gets smallestseq$\\\r
+\Function{UpdateCommitTable}{$ $} \r
\r
- \LeftComment{Check the least slots to rescue and live entries}\r
- \While{$cseq < largestseq$}\r
- \State $currentslot \gets s'$ such that $\tuple{s',DE'} \in LocalSlots \land s' = cseq$\r
- \State $\tuple{seq', \tuple{seq_2',id',DE',hmac_p',hmac_c'}} \gets currentslot$\\\r
+ \State $ArbSet \gets \{id'| \tuple{P, KV, seq_t, seq_s,id'} \in LiveCommits\}$\r
+ \r
+ \ForAll{$id \in ArbSet$}\r
+ \State $Commits \gets \{\tuple{P, KV, seq_t, seq_s,id'}| \tuple{P, KV, seq_t, seq_s,id'} \in LiveCommits \land id' = id\}$\r
\r
- \ForAll{$de \in DE'$} \Comment{Iterate over all the entries}\r
- \If{\Call{CheckLive}{$de, cseq$}} \Comment{data entry is live}\r
- \State $de \gets $ \Call{CreateRescuedEntry}{de} \Comment{Resize entry if needed}\\\r
- \r
- \If{$de \in DE_a$} \Comment{Already being rescued}\r
- \State Continue\r
- \EndIf\\\r
- \r
- \If{\Call{DEHasSpace}{$DE_a, de$}}\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
+ \State $lastComSeenSeq \gets -1$\r
+ \If{$\exists \tuple{id',seq'} \in LastCommitSeenFromArbitrator, id'=id$}\r
+ \State $lastComSeenSeq \gets seq$ such that $\tuple{id',seq'} \in LastCommitSeenFromArbitrator, id'=id$\r
+ \EndIf\\\r
+ \r
+ \ForAll{$\tuple{P, KV, seq_t, seq_s,id} \in Commits$ sorted by $seq_s$ where $seq_s > lastComSeenSeq$}\r
+\r
+ \If{$(\forall \tuple{D',seq_t', seq_s', id', pn', isLast'} \in P, \lnot isLast')\lor(\exists \tuple{D',seq_t', seq_s', id', pn', isLast'} \in P,isLast') \land |P| \neq pn)$}\r
+ \If{$\forall \tuple{P', KV', seq_t', seq_s',id'} \in Commits, seq_s' < seq_s$}\r
+ \State Break \Comment{This is the last slot so ignore it}\r
\Else\r
- $numofskips \gets numofskips +1$\r
+ \State Continue\r
\EndIf\r
+ \EndIf\\\r
+ \r
+ \If{$\lnot(\exists \tuple{id',seq'} \in LastArbLocalArbitrated, id'=id \land seq' > seq_s)$}\r
+ \State $LastArbLocalArbitrated\gets \tuple{\tuple{id',seq'}|\tuple{id',seq'} \in LastArbLocalArbitrated, id' \neq id} \cup \{\tuple{id, seq_s}\}$\r
\EndIf\r
- \EndFor\\\r
+ \r
+ \State $LastCommitSeenFromArbitrator \gets \{ \tuple{id',seq'}| \tuple{id',seq'} \in LastCommitSeenFromArbitrator,id' \neq id\} \cup \{\tuple{id, seq_s}\}$\r
+\r
+ \If{$\lnot(\exists \tuple{id',seq'} \in LastTransactionArbitrated, id'=id \land seq' > seq_{t})$}\r
+ \State $LastTransactionArbitrated \gets \tuple{\tuple{id',seq'}|\tuple{id',seq'} \in LastTransactionArbitrated, id' \neq id} \cup \{\tuple{id, seq_{t}}\}$\r
+ \EndIf \r
+ \r
+ \LeftComment{Update Committed Table}\r
+ \State $CommittedKV \gets \{\tuple{k,v}| \tuple{k,v} \in CommittedKV \land \forall \tuple{k',v'} \in KV, k\neq k' \} \cup KV$ \r
+ \State $LiveCommits \gets LiveCommits \cup \tuple{P, KV, seq_t, seq_s,id}$\\\r
\r
- \State $cseq \gets cseq+1$ \Comment{Move onto the next slot}\r
- \EndWhile\r
- \r
- \State \Return{$DE_a$}\r
+ \ForAll{$\tuple{P, KV, seq_t, seq_s,id} \in LiveCommits$}\r
+ \LeftComment{All Key Values in this commit have been overridden by a newer commit} \r
+ \If{$\forall \tuple{k,v} \in KV, \exists \tuple{P', KV', seq_t', seq_s',id'} \in LiveCommits, \exists \tuple{k',v'} \in KV', k'=k \land seq_s' > seq_s$}\r
+ \State $LiveCommits \gets LiveCommits \setminus \{\tuple{P, KV, seq_t, seq_s,id}\}$\r
+ \EndIf\r
+ \EndFor \r
+ \EndFor\r
+ \EndFor\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
+%\end{varwidth}% \r
+%}\r
\r
-% Rejected Messages\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Rejected Messages:}\\\r
+% Update Speculative Table\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Update Speculated Key value Table:}\\\r
+Update the table of speculative Key Value Pairs based on commits that we received.\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
+\Function{UpdateSpeculativeKV}{$ $}\r
+ \State $SpecKV \gets CommittedKV$\\\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
+ \ForAll{$\tuple{P, KV, G,seq_{cl}, seq_s,id, arb} \in LiveTransactions$ sorted by $seq_s$}\r
+ \If{$\forall \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P, \lnot isLast'$}\r
+ \State Continue\r
+ \ElsIf{$(\exists \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P,isLast') \land |P| \neq pn$}\r
+ \State Continue\r
+ \EndIf\\\r
+ \r
+ \If{\Call{EvaluateGuard}{$G, SpecKV$}}\r
+ \State $SpecKV\gets \{\tuple{k',v'}| \tuple{k',v'} \in SpecKV \land \forall \tuple{k,v} \in KV, k' \neq k\}\cup KV$\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
+ \ForAll{$\tuple{KV, G, id, seq} \in PendingTransactionQueue$ sorted by $seq$}\r
+ \If{\Call{EvaluateGuard}{$G, SpecKV$}}\r
+ \State $SpecKV\gets \{\tuple{k',v'}| \tuple{k',v'} \in SpecKV \land \forall \tuple{k,v} \in KV, k' \neq k\}\cup KV$\r
+ \EndIf\r
\EndFor\\\r
\r
- \State \Return{$DE_a$}\r
+ \State $SpeculatedKV \gets SpecKV$\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
-\textbf{Arbitrate:}\\\r
-\begin{algorithmic}[1]\r
-\Function{Arbitrate}{$DE_a$}\r
- \State $AllCommits \gets$ \Call{GetCommits}{}\r
- \State $AllTrans \gets$ \Call{GetTrans}{}\r
- \State $LiveCommits \gets \{c| c\in AllCommits, $\Call{CheckCommitLive}{$c$}$\}$\r
- \State $LiveTrans \gets \{t| t\in AllTrans, $\Call{CheckTransLive}{$t$}$\}$\r
- \State $KV \gets \emptyset$\r
- \State $lastcomseq \gets -1$\r
- \State $CurrKV \gets \emptyset$\r
- \State $DKV \gets \emptyset$\r
- \State $KVTmp \gets \emptyset$\\\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Compact Arbitration Rounds\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Compact Arbitration Rounds:}\\\r
+Compact Arbitration Rounds to reduce the amount of data needed to be sent to the server.\r
+\begin{algorithmic}[1]\r
+\Function{CompactArbitrationRounds}{$ $}\r
+ \If{$|SendArbQueue| < 2$}\r
+ \State \Return{False}\r
+ \EndIf\\\r
\r
- \LeftComment{Get all the latest commits}\r
- \ForAll{$\tuple{seq_{trans}',KV'} \in LiveCommits$}\r
- \State $CurrKV \gets CurrKV \cup KV'$\r
- \EndFor\\\r
+ \State $didMergeWithCommit \gets False$\r
\r
- \ForAll{$\tuple{seq_t, id_t, KV_t, Guard_t} \in LiveTrans$ ordered by $seq'$} \r
- \If{\Call{GetArbitratorKV}{$KV_t$} $\neq LOCAL\_ID$}\r
- \State Continue \Comment{Client not arbitrator for this transaction}\r
+ \While{$|SendArbQueue| > 1$}\r
+ \State $\tuple{c_1, A_1, S_1} \gets SendArbQueue.peak(|SendArbQueue|)$\r
+ \State $\tuple{c_2, A_2, S_2} \gets SendArbQueue.peakEnd(|SendArbQueue| - 1)$\\\r
+ \r
+ \If{$|S_1| \neq 0 \lor |S_2| \neq 0$}\r
+ \State \Return{$didMergeWithCommit$}\r
\EndIf\\\r
- \r
- \If{$\lnot$\Call{EvaluateGuard}{$Guard_t, CurrKV$}}\r
- \State $abortde \gets $\Call{CreateAbort}{$seq_t, id_t$}\r
- \LeftComment{No more space so we cant arbitrate any further}\r
- \If($lnot$\Call{DeHasSpace}{$DE_a, abortde$})\r
- \State \Return{$DE_a$}\r
- \EndIf\r
- \State $DE_a \gets DE_a \cup abortde$\r
+ \r
+ \If{$c_2 = NULL$}\r
+ \If{$|A_1| + |A_2| > MAX\_ROUND\_SIZE$}\r
+ \State \Return{$didMergeWithCommit$}\r
+ \EndIf \r
+ \State $SendArbQueue.remove(|SendArbQueue|)$\r
+ \State $SendArbQueue.remove(|SendArbQueue|)$\r
+ \State $SendArbQueue \gets SendArbQueue \cup \tuple{c_1, A_1 \cup A_2, \emptyset}$\r
\Else\r
- \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in KV \land \tuple{k',v'}\in KV_t \land k'=k\}$\r
- \State $KVTmp \gets (KV \setminus DKV) \cup KV'$\r
- \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in CurrKV \land \tuple{k',v'}\in KVTmp \land k'=k\}$\r
- \State $CurrKV \gets (CurrKV \setminus DKV) \cup KVTmp$\r
- \State $commitde \gets $ \Call{CreateCommit}{$seq_t,KVTmp$}\r
+ \State $\tuple{P_1, KV_1, seq_{1_t}, seq_{1_s},id_1} \gets c_1$\r
+ \State $\tuple{P_2, KV_2, seq_{2_t}, seq_{2_s},id_2} \gets c_2$\r
+ \State $newKV \gets \{\tuple{k_2,v_2}| \tuple{k_2,v_2} \in KV_2 \land \forall \tuple{k_1,v_1} \in KV_1 \land k_1 \neq k_2\} \cup KV_1$\r
+ \State $NewCom \gets \tuple{P_1, newKV, seq_{1_t}, seq_{1_s},id_1}$\r
+ \State \Call{GenerateParts}{$NewCom$}\r
+ \State $\tuple{P_1, newKV, seq_{1_t}, seq_{1_s},id_1} \gets NewCom$\\\r
\r
- \If{$\lnot$ \Call{DeHasSpace}{$DE_a, commitde$}}\r
- \If{$lastcomseq \neq -1$}\r
- \State $DE_a \gets DE_a \cup$ \Call{CreateCommit}{$lastcomseq,KV$}\r
- \EndIf\r
- \State \Return{$DE_a$}\r
- \Else\r
- \State $KV \gets KVTmp$\r
- \State $lastcomseq \gets seq_t$\r
- \EndIf\r
+ \If{$|P_1| > MAX\_ROUND\_SIZE$}\r
+ \State \Return{$didMergeWithCommit$}\r
+ \EndIf\\\r
+ \r
+ \State $SendArbQueue.remove(|SendArbQueue|)$\r
+ \State $SendArbQueue.remove(|SendArbQueue|)$\r
+ \State $SendArbQueue \gets SendArbQueue \cup \tuple{newCom, A_1 \cup A_2, \emptyset}$\r
+ \State $didMergeWithCommit \gets True$\r
\EndIf\r
- \EndFor\r
+ \EndWhile \r
\r
- \State $DE_a \gets DE_a \cup$ \Call{CreateCommit}{$lastcomseq,KV$}\r
- \State \Return{$DE_a$}\r
-\r
+ \State \Return{$didMergeWithCommit$}\r
\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
-% Create New Slot\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Create New Slot:}\\\r
-Create a slot and encrypt it.\\\r
+% Arbitrate From Server\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Arbitrate Form Server:}\\\r
+Arbitrate on the transactions that were received from the server\r
\begin{algorithmic}[1]\r
-\Function{CreateNewSlot}{$seq_a, DE_a$}\r
- \State $\tuple{seq, SDE} \gets \tuple{seq', SDE'}$ such that $\tuple{seq', SDE'}\in LocalSlots \land (\forall \tuple{seq'', DE''} \in LocalSlots, seq' \geq seq'')$\r
- \State $\tuple{seq,id,DE,hmac_p,hmac_c} \gets SDE$\\\r
+\Function{ArbitrateFromServer}{$ $}\r
\r
- \State $newhmac \gets $ \Call{GenerateHmac}{$seq_a, LOCAL\_ID, DE_a, hmac_p$}\r
- \State $newSDE \gets \tuple{seq,LOCAL\_ID,DE_a,hmac_c,newhmac}$\r
- \State $encryptnewSDE \gets $\Call{Encrypt}{newSDE}\\\r
+ \State $KVCom \gets \emptyset$\r
+ \State $KVTmp \gets CommittedKV$\r
+ \State $lastTransCommitted = 0$\r
+ \State $AbortSet \gets \emptyset$\r
+ \State $NewCom \gets NULL$\r
\r
- \State \Return{$\tuple{seq_a, encryptnewSDE}$}\r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-% Send Data to Server\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Send Data to Server:}\\\r
-Send the data to the server. If this fails then new slots will be returned by the server.\\\r
-\begin{algorithmic}[1]\r
-\Function{SendToServer}{$seq_a, DE_a, newsize_a$}\r
- \LeftComment{Make the slot and try to send to server}\r
- \State $newslot \gets $ \Call{CreateNewSlot}{$seq_a, DE_a$}\r
- \State $\tuple{success, newslots} \gets$ \Call{PutSlot}{$seq_a, newslot, newsize_a$}\\\r
+ \State $TransArb \gets \{\tuple{P, KV, G,seq_{l}, seq_{s},id,arb}|\tuple{p, KV, G,seq_{l}, seq_{s},id,arb} \in LiveTransactions \land arb = LOCAL\_ID\}$\\\r
\r
- \If{$success$}\r
- \State $RejectedSlotList \gets \emptyset$\r
- \State \Return{$\tuple{true, \{newslot\}}$}\r
- \Else\r
- \If{$|newslots| = 0$}\r
- \State \Call{Error}{"Server rejected but did not send any slots"}\r
+ \ForAll{$\tuple{P, KV, G,seq_{cl}, seq_{s},id,arb} \in Transarb$ sorted by $seq_{s}$}\r
+ \r
+ \If{$\forall \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P, \lnot isLast'$}\r
+ \State Break\r
+ \ElsIf{$(\exists \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P,isLast') \land |P| \neq pn$}\r
+ \State Break\r
+ \ElsIf{$\exists \tuple{id', seq_{l}'} \in OfflineTransAtServer, id' = id\land seq_{cl}' = seq_{cl} $}\r
+ \State Break\r
+ \EndIf\\\r
+ \r
+ \State $LastTransSeenMid \gets \{\tuple{id',seq'}|\tuple{id',seq'} \in LastTransSeenMid \land id'\neq id\} \cup \{\tuple{id, seq_s}\}$\\\r
+ \r
+ \r
+ \If{\Call{EvaluateGuard}{$G, KVTmp$}}\r
+ \State $KVTmp \gets \{\tuple{k',v'} |\tuple{k',v'} \in KVTmp \land \forall \tuple{k,v} \in KV, k' \neq k\}\cup KV$\r
+ \State $KVCom \gets \{\tuple{k',v'} |\tuple{k',v'} \in KVCom \land \forall \tuple{k,v} \in KV, k' \neq k\}\cup KV$\r
+ \State $lastTransCommitted \gets seq_{s}$ \r
+ \Else\r
+ \State $newAbort \gets \tuple{seq_{cl}, seq_{s}, id, arb, arbitrationSeqNum}$\r
+ \State $AbortSet \gets AbortSet \cup newAbort$\r
+ \State $arbitrationSeqNum \gets arbitrationSeqNum + 1$\r
+ \State \Call{ProcessAbort}{$newAbort$}\r
\EndIf\r
- \State $RejectedSlotList \gets RejectedSlotList \cup \{seq_a\}$\r
- \State \Return{$\tuple{false, newslots}$}\r
- \EndIf\\\r
+ \EndFor\r
+ \r
+ \If{$|KVCom| \neq 0$}\r
+ \State $NewCom \gets \tuple{\emptyset, KVCom, lastTransCommitted, arbitrationSeqNum,id}$\r
+ \State \Call{GenerateParts}{$NewCom$}\r
+ \State $arbitrationSeqNum \gets arbitrationSeqNum + 1$\r
+ \ForAll{$compart \in NewCom$}\r
+ \State \Call{ProcessCommitPart}{compart}\r
+ \EndFor\r
+ \EndIf\r
+ \r
+ \If{$|KVCom| \neq 0 \lor |AbortSet| \neq 0$}\r
+ \State $ArbitrationQueue \gets ArbitrationQueue \cup \tuple{NewCom, AbortSet, \emptyset}$\r
+ \r
+ \If{\Call{CompactArbitrationRounds}{$ $}}\r
+ \State $\tuple{NewCom, AbortSet, \emptyset} \gets ArbitrationQueue.peakEnd()$\r
+ \ForAll{$compart \in NewCom$}\r
+ \State \Call{ProcessCommitPart}{compart}\r
+ \EndFor\r
+ \EndIf\r
+ \EndIf \r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
+\r
\r
\r
-% Try Insert Transaction\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Try Insert Transaction:}\\\r
-Try to insert a transaction into the block chain. Does resizing, rescues and insertion of other data entry types as needed. \\\r
+% Arbitrate From Local\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Arbitrate from local:}\\\r
+Arbitrate on the transactions that were received from the local.\r
\begin{algorithmic}[1]\r
-\Function{TryInsertTransaction}{$pendingtrans_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
- \State $trans \gets$ \Call{CreateTrans}{$pendingtrans_a, seq$}\r
- \State $transinserted \gets false$\r
- \State $slotstoinsert \gets \emptyset$\\\r
+\Function{ArbitrateFromLocal}{$Transaction_a$}\r
+ \State $\tuple{Parts, KV, G,seq_l, seq_s,id, arb} \gets Transaction_a$\\\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
+ \If{$id \neq LOCAL\_ID$} \Comment{If is arbitrator}\r
+ \State \Return{$\tuple{False, False}$}\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{TryInsertTransaction}{$trans_a, true$}}\r
+ \LeftComment{transaction is complete}\r
+ \If{$\forall \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P, \lnot isLast'$}\r
+ \State \Return{$\tuple{False, False}$}\r
+ \ElsIf{$(\exists \tuple{D',arb',seq_{l}', seq_{s}', id', pn', isLast'} \in P,isLast') \land |P| \neq pn$}\r
+ \State \Return{$\tuple{False, False}$}\r
\EndIf\\\r
\r
- \State $DE \gets $\Call{Arbitrate}{$DE$}\\\r
- \r
- \If{\Call{DEHasSpace}{$DE, trans$}} \Comment{transaction fits}\r
- \State $DE \gets DE \cup trans$\r
- \State $transinserted \gets true$\r
+ \If{$id \neq LOCAL\_ID$}\r
+ \If{$\exists \tuple{id',seq'} \in LastTransSeenMid, id'=id \land seq' > seq_l$}\r
+ \State \Return{$\tuple{False, False}$} \Comment{Already seen this transaction}\r
+ \EndIf\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 bloakc chain}\r
- \State \Call{DecryptValidateInsert}{$newslots, true$}\\\r
- \r
- \State \Return{$transinserted \land success$} \Comment{Return if succeeded or not}\r
+ \If{\Call{EvaluateGuard}{$G, CommittedKV$}} \r
+ \State $NewCom \gets \tuple{\emptyset, KV, seq_s, arbitrationSeqNum,id}$\r
+ \State \Call{GenerateParts}{$NewCom$}\r
+ \State $arbitrationSeqNum \gets arbitrationSeqNum + 1$\r
+ \ForAll{$compart \in NewCom$}\r
+ \State \Call{ProcessCommitPart}{compart}\r
+ \EndFor\\\r
+ \r
+ \State $ArbitrationQueue \gets ArbitrationQueue \cup \tuple{NewCom, \emptyset, \emptyset}$\r
+ \If{\Call{CompactArbitrationRounds}{$ $}}\r
+ \State $\tuple{NewCom, AbortSet, \emptyset} \gets ArbitrationQueue.peakEnd()$\r
+ \ForAll{$compart \in NewCom$}\r
+ \State \Call{ProcessCommitPart}{compart}\r
+ \EndFor\r
+ \EndIf\r
+ \r
+ \r
+ \If{$id = LOCAL\_ID$}\r
+ \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
+ \State \Call{ChangeTransStatus}{$TransStatus,committed$}\r
+ \State \Call{DeleteTransStatus}{$id,seq_l$}\r
+ \EndIf\r
+ \r
+ \State \Call{UpdateCommittedKV}{}\r
+ \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
+ \State \Call{UpdateSpeculativeKV}{} \r
+ \State \Return{$\tuple{True, True}$} \r
+ \Else\r
+ \r
+ \If{$id = LOCAL\_ID$}\r
+ \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
+ \State \Call{ChangeTransStatus}{$TransStatus,aborted$}\r
+ \State \Call{DeleteTransStatus}{$id,seq_l$}\r
+ \Else\r
+ \State $newAbort \gets \tuple{seq_{cl}, seq_{s}, id, arb, arbitrationSeqNum}$\r
+ \State $arbitrationSeqNum \gets arbitrationSeqNum + 1$\r
+ \State \Call{ProcessAbort}{$newAbort$} \r
+ \State $ArbitrationQueue \gets ArbitrationQueue \cup \tuple{NULL, \{newAbort\}, \emptyset}$\r
+ \r
+ \If{\Call{CompactArbitrationRounds}{$ $}}\r
+ \State $\tuple{NewCom, AbortSet, \emptyset} \gets ArbitrationQueue.peakEnd()$\r
+ \ForAll{$compart \in NewCom$}\r
+ \State \Call{ProcessCommitPart}{compart}\r
+ \EndFor\r
+ \EndIf\r
+ \EndIf \r
+ \EndIf\r
\r
+ \State \Call{UpdateCommittedKV}{}\r
+ \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
+ \State \Call{UpdateSpeculativeKV}{} \r
+ \State \Return{$\tuple{True, False}$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Update Live Transaction and Statuses\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Update Live Transactions And Statuses:}\\\r
+Update the live transactions and the transaction statuses.\r
+\begin{algorithmic}[1]\r
+\Function{UpdateLiveTransactionsAndStatuses}{$ $}\r
+ \ForAll{$\tuple{P, KV, G,seq_l, seq_s,id, arb} \in LiveTransactions$}\r
+ \If{$\exists \tuple{id',seq'} \in LastTransactionArbitrated, id=id' \land seq' > seq_s$}\r
+ \If{$id = LOCAL\_ID$}\r
+ \State $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
+ \State \Call{ChangeTransStatus}{$TransStatus,committed$}\r
+ \State \Call{DeleteTransStatus}{$id,seq_l$}\r
+ \EndIf\r
+ \EndIf\r
+ \EndFor\r
+ \State $LiveTransactions \gets \{\tuple{P, KV, G,seq_l, seq_s,id, arb}| \tuple{P, KV, G,seq_l, seq_s,id, arb} \in LiveTransactions \land \forall \tuple{id',seq'} \in LastTransactionArbitrated, id'\neq id \lor seq_s > seq'\}$\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \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
+% Validate and Update \r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Validate Update:}\\\r
+Validate the block chain and insert into the local block chain.\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
+\Function{ValidateUpdate}{$NewSlots_a, updatinglocal_a$}\r
+ \State $\tuple{seq_{oldest}, Dat_{oldest}} \gets$ \Call{MinSlot}{$NewSlots_a$}\r
+ \State $\tuple{seq_{newest}, Dat_{newest}} \gets$ \Call{MaxSlot}{$NewSlots_a$}\r
+ \State $\tuple{seq_{local}, Dat_{local}} \gets$ \Call{MaxSlot}{$LocalSlots$}\r
+ \State $MachinesSeen \gets \{id'|\tuple{id',seq'} \in LastSlot\}$\\\r
\r
- \State $newkey \gets$ \Call{CreateNewKey}{$k_a, id_a$}\r
- \State $newkeyinserted \gets false$\r
- \State $slotstoinsert \gets \emptyset$\\\r
+ \State \Call{CheckSlotsHmacAndSeq}{$NewSlots_a$}\r
+ \State \Call{CheckHmacChain}{$NewSlots_a$}\r
+ \State \Call{CheckOldSlots}{$NewSlots_a$}\r
+ \State \Call{CheckSize}{$NewSlots_a$}\\\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
+ \ForAll{$slot_a \in NewSlots_a$ in order of sequence number} \r
+ \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets slot_a$\r
+ \State \Call{UpdateLastMessage}{$seq_{a_1}, id_a, updatinglocal_a, MachinesSeen$}\\\r
+ \r
+ \ForAll{$de_a \in DE_a$}\r
+ \State \Call{ProccessDatEntry}{$de_a, NewSlots_a, MachinesSeen$}\r
+ \EndFor\\\r
\r
- \If{$RejectedSlotList \neq \emptyset$} \r
- \State $DE \gets$ \Call{RejectedMessages}{$DE$}\r
- \EndIf\\\r
+ \State $LocalSlots \gets LocalSlots \cup \{slot_a\}$ \Comment{Add to local Chain}\r
+ \EndFor\\\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
+ \If{$seq_{oldest} > (seq_{local} +1) \land MachinesSeen \neq \emptyset$}\r
+ \LeftComment{There was a gap so there should be a complete set of information on each previously seen client}\r
+ \State \Call{Error}{"Missing records for machines"}\r
\EndIf\\\r
\r
- \State $DE \gets $\Call{Arbitrate}{$DE$}\\\r
+ \State \Call{DeleteLocalSlots}{ } \Comment{Delete old slots from local}\r
\r
- \If{\Call{DEHasSpace}{$DE, newkey$}} \Comment{new key fits}\r
- \State $DE \gets DE \cup newkey$\r
- \State $newkeyinserted \gets true$\r
+ \State \Call{ArbitrateFromServer}{}\r
+ \State \Call{UpdateCommittedKV}{}\r
+ \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
+ \State \Call{UpdateSpeculativeKV}{}\r
+ \r
+ \State $offlineTransactionAtServer \gets \emptyset$\r
+ \State $hadPartialSendToServer \gets false$\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Accept from local \r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Accept from Local:}\\\r
+The local transaction handling accept.\r
+\begin{algorithmic}[1]\r
+\Function{AcceptFromLocal}{$seq_a, transaction_a$}\r
+ \State $arbitrated \gets false$\r
+ \State $committed \gets false$\r
+ \State $ReturnSet \gets \emptyset$\\\r
+ \r
+ \If{$transaction_a \neq NULL$}\r
+ \State $\tuple{arbitrated, committed} \gets $ \Call{ArbitrateFromLocal}{$transaction_a$} \r
+ \State $\tuple{P, KV, G,seq_l, seq_s,id, arb} \gets transaction_a$\r
+ \If{$seq_s \neq -1$}\r
+ \State $OfflineTransAtServer \gets OfflineTransAtServer \cup \{\tuple{id, seq_l}\}$\r
+ \EndIf\r
+ \State \Call{UpdateCommittedKV}{}\r
+ \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
+ \State \Call{UpdateSpeculativeKV}{}\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
+ \State $AllAborts \gets$ \Call{GetAborts}{} \Comment{Get all the aborts} \\\r
+ \State $ReturnSet \gets ReturnSet \cup \{\tuple{seq_l', seq_s', id', arb', seq_{arb}'}|\tuple{seq_l', seq_s', id', arb', seq_{arb}', seq'} \in A \land id'=LOCAL\_ID \land seq_l' > seq_a\}$\r
+ \State $ReturnSet \gets ReturnSet \cup \{p'|p'\in P' \land \tuple{P', KV', seq_t', seq_s',id'} \in LiveCommits \land id'=LOCAL\_ID \land seq_s' > seq_a\}$\r
+ \State \Return{$\tuple{arbitrated, committed,ReturnSet}$} \r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
\r
+% Send to local \r
+%% \noindent\fbox{%\r
+%% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Send To Local:}\\\r
+Send transaction to local to be arbitrated on or not.\r
+\begin{algorithmic}[1]\r
+\Function{SendToLocal}{$transaction_a$}\r
+ \State $\tuple{P, KV, G,seq_l, seq_s,id, arb} \gets transaction_a$\r
+ \If{Cannot communicate locally with client $id$}\r
+ \State \Return{$False$}\r
+ \EndIf\r
\r
-\subsection{Client Interfaces}\r
\r
-% Put KV pair\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Put Key Value Pair:}\\\r
-Puts a key value pair into the key value pair buffer\\\r
-\begin{algorithmic}[1]\r
-\Function{PutKeyValue}{$k,v$}\r
- \State $\tuple{seq, KV, Guard} \gets PendingTrans$\\\r
+ \State $seq_{lastseen} \gets seq'$ such that $\tuple{id',seq'} \in LastArbLocalArbitrated \land id'=id$\r
+ \State $\tuple{arbitrated, committed,ReturnSet} \gets $\Call{AcceptFromLocal}{$seq_{lastseen}, transaction_a$}\\\r
+\r
+ \ForAll{$e \in ReturnSet$}\r
+ \If{$e$ is an $abort$}\r
+ \State \Call{ProcessAbort}{$e$}\r
+ \Else\r
+ \State \Call{ProcessCommitPart}{$e$}\r
+ \EndIf\r
+ \EndFor\\\r
\r
- \LeftComment{Check if KV already has a key value pair for the specified key}\r
- \State $DSet \gets \{\tuple{k_1,v_1} | \tuple{k_1,v_1} \in KV \land k_1 = k\}$\\\r
+ \State \Call{UpdateCommittedKV}{}\r
+ \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
+ \State \Call{UpdateSpeculativeKV}{}\\\r
\r
- \If{$DSet \neq \emptyset$}\r
- \State \Call{Error}{"Value for key already in most recent update"}\r
- \EndIf\\\r
- \r
- \State $KV \gets KV \cup \{\tuple{k,v}\}$ \Comment{Add key value pair}\r
- \State $PendingTrans \gets \tuple{seq, KV, Guard}$\r
- \State \Call{CheckArbitrator}{$PendingTrans$} \Comment{Check that the transaction still valid}\r
-\EndFunction\r
-\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\r
-% Get KV Pair Speculative\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Get KV Pair Speculative:}\\\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 $TransStatus \gets $ \Call{GetTransStatus}{$id,seq_l$}\r
+ \If{$arbitrated$}\r
+ \If{$committed$}\r
+ \State \Call{ChangeTransStatus}{$TransStatus,committed$}\r
+ \Else\r
+ \State \Call{ChangeTransStatus}{$TransStatus,aborted$}\r
+ \EndIf\r
+ \ElsIf{$\exists \tuple{seq_l', seq_s', id', arb', seq_{arb}'} \in ReturnSet, \tuple{seq_l', seq_s', id', arb', seq_{arb}'}$ is an $abort \land id' = LOCAL\_ID \land seq_l' = seq_l$}\r
+ \State \Call{ChangeTransStatus}{$TransStatus,aborted$}\r
+ \Else\r
+ \State \Call{ChangeTransStatus}{$TransStatus,committed$} \r
+ \EndIf\r
\r
- \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpeculatedKV \land k = k_a$\r
-\State \Return{$v$}\r
+ \State \Call{DeleteTransStatus}{$id,seq_l$}\r
+ \State \Return{$True$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+% %\end{varwidth}% \r
+% }\r
+\r
+\r
+\subsection{Client Interfaces}\r
+\r
+\r
+\r
\r
% Update\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{Update}\\\r
-Sync with the server and get all the latest slots.\\\r
+Sync with the server and get all the latest slots.\r
+\r
+\algblock[TryCatchFinally]{try}{endtry}\r
+\algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}\r
+\algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}\r
+ [1]{\textbf{catch} #1}\r
+ {\textbf{end try}}\r
+\r
\begin{algorithmic}[1]\r
-\Function{Update}{$ $}\r
- \State $\tuple{seq, Dat} \gets $ \Call{MaxSlot}{$LocalSlots$}\r
- \State $NewSlots \gets$ \Call{GetSlots}{$seq$}\r
- \State \Call{DecryptValidateInsert}{$NewSlots, false$}\r
+\Function{UpdateFromServer}{$ $}\r
+ \State $NewSlots_{decrypt} \gets \emptyset$\r
+ \State $\tuple{seq, Dat} \gets $ \Call{MaxSlot}{$LocalSlots$}\\\r
+ \r
+ \try\r
+ \State $NewSlots \gets$ \Call{GetSlots}{$seq$}\\\r
+ \r
+ \ForAll{$\tuple{seq', EDat'} \in NewSlots$}\r
+ \State $DDat \gets $ \Call{Decrypt}{$EDat'$}\r
+ \State $NewSlots_{decrypt} \gets NewSlots_{decrypted} \cup \tuple{seq',DDat}$\r
+ \EndFor\\\r
+ \r
+ \State \Call{ValidateAndUpdate}{$NewSlots_{decrypt}$} \r
+ \State \Call{SendToServer}{$Null$}\r
+ \State \Return{$True$} \r
+ \catch{$Exception$}\r
+ \LeftComment{Do nothing here}\r
+ \endtry\r
+ \r
+ \State \Return{$False$}\r
+ \r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Update from local\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Update from local}\\\r
+Get the latest from a client through local communication.\r
+\begin{algorithmic}[1]\r
+\Function{UpdateFromLocal}{$id_a$}\r
+ \If{Cannot communicate locally with client $id$}\r
+ \State \Return{}\r
+ \EndIf\r
+ \r
+ \State $seq_{lastseen} \gets seq'$ such that $\tuple{id',seq'} \in LastArbLocalArbitrated \land id'=id_a$\r
+ \State $\tuple{arbitrated, committed,ReturnSet} \gets $\Call{AcceptFromLocal}{$seq_{lastseen}, transaction_a$}\\\r
+\r
+ \ForAll{$e \in ReturnSet$}\r
+ \If{$e$ is an $abort$}\r
+ \State \Call{ProcessAbort}{$e$}\r
+ \Else\r
+ \State \Call{ProcessCommitPart}{$e$}\r
+ \EndIf\r
+ \EndFor\\\r
+ \r
+ \State \Call{UpdateCommittedKV}{}\r
+ \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
+ \State \Call{UpdateSpeculativeKV}{}\\\r
\r
-% Get KV Pair Committed\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Get KV Pair Committed:}\\\r
-Get the value for the key which have been committed.\\\r
-\begin{algorithmic}[1]\r
-\Function{GetValueCommit}{$k_a$}\r
- \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in Committed \land k = k_a$\r
- \State \Return{$v$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
+\r
\r
-% Put guard condition\r
-\noindent\fbox{%\r
-\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
-\textbf{Put Guard:}\\\r
-Puts a guard transaction into the key value update. A guard is a key value with a logical operator ($lop$).\\\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{PutGuard}{$k,v, lop$}\r
- \State $\tuple{seq, KV, Guard} \gets PendingTrans$\\\r
- \r
- \If{$\tuple{k,v, lop} \in Guard$}\r
- \State \Return{} \Comment{Already have guard condition in update}\r
- \EndIf\\\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{SendToServer}{$\tuple{k_a, id_a}$}\r
+ \EndWhile\r
\r
- \State $Guard \gets Guard \cup \{\tuple{k,v,lop}\}$\r
- \State $PendingTrans \gets \tuple{seq, KV, Guard}$\r
- \State \Call{CheckArbitrator}{$PendingTrans$} \Comment{Check that the transaction still valid}\r
-\EndFunction \r
+ \State \Return{$true$} \Comment{If got here then insertion was correct}\r
+\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \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 Start:}\\\r
-Starts a transaction. Clears out the key value pair update buffer.\\\r
+Starts a transaction.\r
\begin{algorithmic}[1]\r
\Function{TransactionStart}{$ $}\r
- % \LeftComment{Reset the key value update buffer}\r
- % \State $KVUpdate \gets \tuple{\emptyset, \emptyset}$\r
- \State $PendingTrans \gets NULL$\r
+ \State $newPendingTransaction \gets \tuple{\emptyset, \emptyset, LOCAL\_ID,clntTransactionNum}$\r
+ \State $clntTransactionNum \gets clntTransactionNum + 1$\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Put KV pair\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Put Key Value Pair:}\\\r
+Puts a key value pair into the key value pair buffer.\r
+\begin{algorithmic}[1]\r
+\Function{PutKeyValue}{$k,v$}\r
+ \State $\tuple{KV, G,id, seq_{clientLocal}} \gets newPendingTransaction$\r
+ \State $KV \gets \{\tuple{k',v'}| \tuple{k,v} \in KV, k \neq k'\}\cup \{\tuple{k,v}\}$ \r
+ \State $ArbSet \gets \{arb| \exists \tuple{k',v'} \in (KV \cup G), arb=$\Call{GetArbitrator}{$k'$}$\}$\r
+ \If{$|ArbSet| > 1$}\r
+ \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
+ \EndIf\r
+ \State $newPendingTransaction \gets \tuple{KV, G,id, seq_{clientLocal}}$\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
% Transaction Commit\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 a transaction.\r
+\r
+\algblock[TryCatchFinally]{try}{endtry}\r
+\algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}\r
+\algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}\r
+ [1]{\textbf{catch} #1}\r
+ {\textbf{end try}}\r
\begin{algorithmic}[1]\r
-\Function{Transaction Commit}{$ $}\r
- \State $DKV \gets \emptyset$\r
- \State $pt \gets NULL$\\\r
+\Function{TransactionCommit}{$ $}\r
+ \State $\tuple{KV, G,id, seq_{clientLocal}} \gets newPendingTransaction$\r
\r
- \State $PendingTransQueue.$\Call{push}{$PendingTrans$}\\\r
- \r
- \While{\Call{HasConnectionToServer}{ } $\land PendingTransQueue \neq \emptyset$}\r
- \State $pt \gets PendingTransQueue.$\Call{peak}{ }\\\r
+ \If{$|KV| = 0$} \Comment{Nothing To Update}\r
+ \State $TransStatus \gets \tuple{noeffect}$ \r
+ \State \Return{$TransStatus$}\r
+ \EndIf\r
+ \State $transArb \gets $\Call{GetArbitratorKV}{$KV$}\r
\r
- \If{\Call{TryInsertTransaction}{$pt, false$}}\r
- \State $PendingTransQueue.$\Call{pop}{ }\r
- \EndIf\r
- \EndWhile\\ \r
+ \If{$transArb = LOCAL\_ID$}\r
+ \State \Call{ArbitrateFromLocal}{$\tuple{\emptyset, KV, G,seq_{clientLocal},-1,LOCAL\_ID,transArb}$}\r
+ \State \Call{UpdateCommittedKV}{}\r
+ \State \Call{UpdateLiveTransactionsAndStatuses}{}\r
+ \State \Call{UpdateSpeculativeKV}{} \r
+ \Else\r
+ \State $TransStatus \gets \tuple{pending}$ \r
+ \State \Call{SetTransStatus}{$LOCAL\_ID, seq_{clientLocal}, TransStatus$}\r
+ \r
+ \State $newTrans \gets \tuple{\emptyset, KV, G,seq_{clientLocal},-1,LOCAL\_ID,transArb}$\r
+ \State \Call{GenerateParts}{newTrans} \r
+ \State $PendingTransactionQueue.push(\tuple{newTrans, \emptyset, false}$ \r
+ \EndIf\r
\r
- \LeftComment{Go Through local pending transactions and speculate}\r
- \ForAll{$\tuple{KV, Guard} \in PendingTransQueue$}\r
- \If{\Call{EvaluateGuard}{$Guard, SpeculatedKV$}}\r
- \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in SpeculatedKV \land \tuple{k',v'}\in KV \land k'=k\}$\r
- \State $SpeculatedKV \gets (SpeculatedKV \setminus DKV) \cup KV$\r
- \EndIf\r
- \EndFor\r
+ \State $newPendingTransaction \gets \tuple{\emptyset, \emptyset, LOCAL\_ID,clntTransactionNum}$\r
+ \State $clntTransactionNum \gets clntTransactionNum + 1$\r
+\r
+ \try\r
+ \State \Call{SendToServer}{$NULL$}\r
+ \catch{$Exception$} \r
+ \ForAll{$transaction \in PendingTransactionQueue$}\r
+ \If{\Call{SendToLocal}{$transaction$}}\r
+ \State $PendingTransactionQueue.remove(transaction)$\r
+ \EndIf\r
+ \EndFor\r
+ \endtry\r
\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
-\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
-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
+% Get KV Pair Committed\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get KV Pair Committed:}\\\r
+Get the value for the key which have been committed.\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, false$}\r
- \EndWhile\r
+\Function{GetCommit}{$k_a$}\r
+ \If{$\exists \tuple{k,v} \in CommittedKV \land k \neq k_a$}\r
+ \State \Return{$NULL$}\r
+ \EndIf\r
+ \State \Return{$v$ such that $\tuple{k,v} \in CommittedKV \land k = k_a$}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Get KV Pair Committed Atomic\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get KV Pair Committed Atomic:}\\\r
+Get the value for the key which have been committed and add it to the guard condition of the current pending transaction.\r
+\begin{algorithmic}[1]\r
+\Function{GetCommitAtomic}{$k_a$}\r
+ \State $val \gets NULL$\r
+ \If{$\exists \tuple{k,v} \in CommittedKV \land k = k_a$}\r
+ \State $val \gets v$ such that $\tuple{k,v} \in CommittedKV \land k = k_a$\r
+ \EndIf\\\r
\r
- \State \Return{$true$} \Comment{If got here then insertion was correct}\r
+ \State $\tuple{KV, G, seq_{clientLocal}} \gets newPendingTransaction$\r
+ \State $G \gets G \cup \{\tuple{k_a,val}\}$\r
+ \State $ArbSet \gets \{arb| \exists \tuple{k',v'} \in (KV \cup G), arb=$\Call{GetArbitrator}{$k'$}$\}$\r
+ \If{$|ArbSet| > 1$}\r
+ \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
+ \EndIf\r
+ \State $newPendingTransaction \gets \tuple{KV, G, seq_{clientLocal}}$\r
+ \State \Return{$val$}\r
\EndFunction\r
\end{algorithmic}\r
-\end{varwidth}% \r
-}\r
+%\end{varwidth}% \r
+%}\r
\r
+% Get KV Pair Speculative \r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get KV Pair Speculative:}\\\r
+Get the value for the key which have been speculated on.\r
+\begin{algorithmic}[1]\r
+\Function{GetSpeculated}{$k_a$}\r
+ \If{$\exists \tuple{k,v} \in SpeculatedKV \land k \neq k_a$}\r
+ \State \Return{$NULL$}\r
+ \EndIf\r
+ \State \Return{$v$ such that $\tuple{k,v} \in SpeculatedKV \land k = k_a$}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+% Get KV Pair Speculative Atomic\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get KV Pair Speculative Atomic:}\\\r
+Get the value for the key which have been speculative and add it to the guard condition of the current pending transaction.\r
+\begin{algorithmic}[1]\r
+\Function{GetSpeculatedAtomic}{$k_a$}\r
+ \State $val \gets NULL$\r
+ \If{$\exists \tuple{k,v} \in SpeculatedKV \land k = k_a$}\r
+ \State $val \gets v$ such that $\tuple{k,v} \in SpeculatedKV \land k = k_a$\r
+ \EndIf\\\r
+ \r
+ \State $\tuple{KV, G, id,seq_{clientLocal}} \gets newPendingTransaction$\r
+ \State $G \gets G \cup \{\tuple{k_a,val}\}$\r
+ \State $ArbSet \gets \{arb| \exists \tuple{k',v'} \in (KV \cup G), arb=$\Call{GetArbitrator}{$k'$}$\}$\r
+ \If{$|ArbSet| > 1$}\r
+ \State \Call{Error}{"Multiple arbitrators for key values in transaction."}\r
+ \EndIf\r
+ \State $newPendingTransaction \gets \tuple{KV, G, seq_{clientLocal}}$\r
+ \State \Return{$val$}\r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
\r
\end{document}\r
projects / iotcloud.git / blobdiff