From 1e59b0b33298c1154c370341d27d8cc5f6dff012 Mon Sep 17 00:00:00 2001 From: Ali Younis Date: Thu, 17 Nov 2016 11:22:27 -0800 Subject: [PATCH] Updates to docs --- doc2/iotcloud.tex | 52 ++++++++++++++++++++++------------------------- 1 file changed, 24 insertions(+), 28 deletions(-) diff --git a/doc2/iotcloud.tex b/doc2/iotcloud.tex index 3eb10e1..9bbfc7c 100644 --- a/doc2/iotcloud.tex +++ b/doc2/iotcloud.tex @@ -84,7 +84,7 @@ A data entry can be one of these: \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.} \item Collision resolution entry: message identifier + machine id of a collision winner - \newline {The purpose of this is to keep keep track of the winner of all the collisions until allclients have seen the particular entry.} + \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.} \end{enumerate} \subsection{Live status} @@ -95,14 +95,14 @@ Live status of entries: \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). - \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). + \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. - \item New Key messages are always kept alive. + \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. \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. \item Queue state entry is dead if there is a newer queue state entry. - {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.} + {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} \item Collision resolution entry is dead if this entry has been seen by all clients after a collision happens. \end{enumerate} @@ -244,13 +244,13 @@ $max\_size$ = max size of the block chain\\ \subsubsection{Sets and Lists} -$PendingTransSet$ = Set of pending transactions that need to be pushed to the block chain, $\tuple{number,PendingTrans}$\\ +$PendingTransQueue$ = Queue of pending transactions that need to be pushed to the block chain, $\tuple{PendingTrans}$\\ $PendingTrans= \tuple{KV, Guard} = \tuple{$set of key value pairs, set of guard conditions$}$.\\ $Arbitrator$ = set of $\tuple{k,id}$ containing the key and its arbitrating device.\\ $LastSlot$ = set of $\tuple{id, seq}$ containing the machine ID and the largest sequence number from that machine ID.\\ $LocalSlots$ = set of slots that are in the clients local buffer (initially $\emptyset$), data is decrypted.\\ $RejectedSlotList$ = ordered list of the sequence numbers of slots that this client tried to insert but were rejected.\\ -$CommittedKV$ = set of committed key value pairs (initially $\emptyset$). +$CommittedKV$ = set of committed key value pairs (initially $\emptyset$).\\ $SpeculatedKV$ = set of speculated key value pairs (initially $\emptyset$). \subsection{Helper Functions} @@ -1727,18 +1727,8 @@ Get the value for the key while speculating.\\ \begin{algorithmic}[1] \Function{GetValueSpeculate}{$k_a$} %\State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpeculatedKV \land k = k_a$ - \State $SpecKVTmp \gets SpeculatedKV$ - \State $DKV \gets \emptyset$\\ - \LeftComment{Go Through local pending transactions and speculate} - \ForAll{$\tuple{num, \tuple{KV, Guard}} \in PendingTransSet$ sorted by num} - \If{\Call{EvaluateGuard}{$Guard, SpecKVTmp$}} - \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in SpecKVTmp \land \tuple{k',v'}\in KV \land k'=k\}$ - \State $SpecKVTmp \gets (SpecKVTmp \setminus DKV) \cup KV$ - \EndIf - \EndFor - - \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpecKVTmp \land k = k_a$ + \State $\tuple{k,v} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in SpeculatedKV \land k = k_a$ \State \Return{$v$} \EndFunction \end{algorithmic} @@ -1816,21 +1806,27 @@ Starts a transaction. Clears out the key value pair update buffer.\\ Commits the transaction into the block chain. Keeps attempting to insert the transaction into the block chain until it succeeds.\\ \begin{algorithmic}[1] \Function{Transaction Commit}{$ $} - \State $num_{largest} \gets 1$\\ - \If{$PendingTransSet \neq \emptyset$} - \State $num_{largest} \gets num$ such that $\tuple{num, pt} \in PendingTransSet \land \forall \tuple{num', pt'} \in PendingTransSet, num \geq num'$ \Comment{Get the next largest number} - \State $num_{largest} \gets num_{largest} +1$ - \EndIf\\ - - \State $PendingTransSet \gets PendingTransSet \cup \{\tuple{num_{largest},PendingTrans}\}$\\ + \State $DKV \gets \emptyset$ + \State $pt \gets NULL$\\ - \While{\Call{HasConnectionToServer}{ } $\land PendingTransSet \neq \emptyset$} - \State $\tuple{num, pt} \gets \tuple{num, pt}$ such that $\tuple{num, pt} \in PendingTransSet \land \forall \tuple{num', pt'} \in PendingTransSet, num \leq num'$ \Comment{Get the oldest one and try to commit it}\\ + \State $PendingTransQueue.$\Call{push}{$PendingTrans$}\\ + + \While{\Call{HasConnectionToServer}{ } $\land PendingTransQueue \neq \emptyset$} + \State $pt \gets PendingTransQueue.$\Call{peak}{ }\\ \If{\Call{TryInsertTransaction}{$pt, false$}} - \State $PendingTransSet \gets PendingTransSet \setminus \tuple{num, pt}$ + \State $PendingTransQueue.$\Call{pop}{ } \EndIf - \EndWhile + \EndWhile\\ + + \LeftComment{Go Through local pending transactions and speculate} + \ForAll{$\tuple{KV, Guard} \in PendingTransQueue$} + \If{\Call{EvaluateGuard}{$Guard, SpeculatedKV$}} + \State $DKV \gets \{\tuple{k,v}| \tuple{k,v} \in SpeculatedKV \land \tuple{k',v'}\in KV \land k'=k\}$ + \State $SpeculatedKV \gets (SpeculatedKV \setminus DKV) \cup KV$ + \EndIf + \EndFor + \EndFunction \end{algorithmic} \end{varwidth}% -- 2.34.1