Edits

diff --git a/version2/doc/iotcloud_formal/iotcloud.tex b/version2/doc/iotcloud_formal/iotcloud.tex
index d4e201a45fefc7ca631913ef4845b575725a73d9..8f1559282d592b68082f3bbe197a9092cc55c68f 100644 (file)
--- a/version2/doc/iotcloud_formal/iotcloud.tex
+++ b/version2/doc/iotcloud_formal/iotcloud.tex
@@ -111,6 +111,43 @@ The data structure exposes the following functions:
     \item Create new key\r
 \end{itemize}\r
 \r
     \item Create new key\r
 \end{itemize}\r
 \r

+\r
+\subsubsection{\textbf{Types of Payloads}}\r
+The different types of record payloads are:\r
+\begin{itemize}\r
+    \item Transactions\r
+        \begin{itemize}\r
+            \item Used to make updates to key value pairs.\r
+        \end{itemize}\r
+    \item Commit notifications\r
+        \begin{itemize}\r
+            \item Contains the commit of a single transaction, the whole transaction.\r
+            \item There is 1 commit per transaction.\r
+            \item Generated by the arbitrator for the set of key-value gets and sets in the transaction.\r
+        \end{itemize}\r
+    \item Abort notifications\r
+        \begin{itemize}\r
+            \item Causes a transaction to be aborted, key-values not used in updates.\r
+        \end{itemize}\r
+    \item Data structure re-size notifications\r
+        \begin{itemize}\r
+            \item Contains new size of data structure (number of record allowed in the data structure or something like that).\r
+        \end{itemize}\r
+    \item Server sequence number confirmations.\r
+        \begin{itemize}\r
+            \item Created by any device if that device finds a record with a server sequence number that does not have a server sequence number conformation yet.\r
+        \end{itemize}\r
+    \item Delete notifications\r
+        \begin{itemize}\r
+            \item Generated when a device deletes a record.\r
+            \item records the record that was last deleted\r
+        \end{itemize}\r
+    \item New Key notification\r
+        \begin{itemize}\r
+            \item Generated when a device generates a new (never used) key-value pair.\r
+        \end{itemize}\r
+\end{itemize}\r
+\r

 \subsection{\textbf{Client Notation Conventions}}\r
 \r
 $K$ is the set of all keys.\\\r
 \subsection{\textbf{Client Notation Conventions}}\r
 \r
 $K$ is the set of all keys.\\\r


@@ -143,12 +180,10 @@ $record_s = \tuple{ssn_s,rd_s}$\\
 \subsection{\textbf{Client State}}\r
 \textit{s = largest server sequence number pulled from the server by a device} \\\r
 \textit{R = set of records pulled from the server so far with their server sequence numbers} \\\r
 \subsection{\textbf{Client State}}\r
 \textit{s = largest server sequence number pulled from the server by a device} \\\r
 \textit{R = set of records pulled from the server so far with their server sequence numbers} \\\r

-\textit{RL = set of records that contain live data} \\\r

 \r
 \subsection{Helper Functions}\r
 The following helper functions are needed:\\\r
 \r
 \r
 \subsection{Helper Functions}\r
 The following helper functions are needed:\\\r
 \r

-\r

 % Error\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
 % Error\r
 \noindent\fbox{%\r
 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r


@@ -838,6 +873,7 @@ The following helper functions are needed:\\
     \State $payload_s \gets$ \Call{RescuePayloadItems}{$payload_s$}\r
     \State $payload_s \gets$ \Call{PadPayload}{$payload_s$}\r
     \State $vc \gets $ \Call{GenerateVectorClock}{ }\r
     \State $payload_s \gets$ \Call{RescuePayloadItems}{$payload_s$}\r
     \State $payload_s \gets$ \Call{PadPayload}{$payload_s$}\r
     \State $vc \gets $ \Call{GenerateVectorClock}{ }\r

+    \State \Call{IncrementVectorClock}{ }\r

     \State $hmac \gets$ \Call{GenerateHmac}{$mid, vc, payload_s$}\r
     \State $record \gets \tuple{mid,vc,hmac,payload}$\r
     \State $record \gets $\Call{Encrypt}{$record$}\r
     \State $hmac \gets$ \Call{GenerateHmac}{$mid, vc, payload_s$}\r
     \State $record \gets \tuple{mid,vc,hmac,payload}$\r
     \State $record \gets $\Call{Encrypt}{$record$}\r


@@ -1012,14 +1048,6 @@ ock\gets True$
 \end{varwidth}% \r
 }\r
 \r
 \end{varwidth}% \r
 }\r
 \r

-\r
-\r
-\r
-\r
-%-Arbitration\r
-%   - Insert Commit\r
-\r
-\r

 \subsection{\textbf{Create new key}}\r
 This operation creates a key and assigns an arbitrator to arbitrate on that new key.  In the case where more than one clients concurrently try to create the same new key, the client that inserted the newkey payload with the lowest ssn will be the client to generate the key, all other clients generation attempts would be invalid.\r
 \r
 \subsection{\textbf{Create new key}}\r
 This operation creates a key and assigns an arbitrator to arbitrate on that new key.  In the case where more than one clients concurrently try to create the same new key, the client that inserted the newkey payload with the lowest ssn will be the client to generate the key, all other clients generation attempts would be invalid.\r
 \r


@@ -1175,4 +1203,110 @@ This operation gets the latest key value pair from the data structure.  This is
 %\end{varwidth}% \r
 %}\r
 \r
 %\end{varwidth}% \r
 %}\r
 \r

+\subsection{\textbf{Arbitrate On Transaction}}\r
+\r
+%\noindent\fbox{%\r
+%\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get  Latest Data Structure From Server}:\r
+\begin{algorithmic}[1]\r
+\Function{Arbitrate }{ }\r
+    \State $API \gets \emptyset$   \Comment{Set of all Payload Items}\r
+    \State $AT \gets \emptyset$    \Comment{Set of all Payload Items that are transactions}\r
+    \State $AC \gets \emptyset$    \Comment{Set of all Payload Items that are commits}\r
+    \State $AA \gets \emptyset$    \Comment{Set of all Payload Items that are aborts}\r
+    \State $kSet \gets \emptyset$ \Comment{Set of all key names in the system}\r
+    \State $tid \gets NULL$\r
+    \State $currentKV \gets \emptyset$\r
+    \State $newPayload \gets NULL$\r
+    \State $midClient \gets mid$ of this client\\\r
+    \r
+    \State \Call{GetLatestDataStruct}{ } \Comment{Update local version of data struct}\\\r
+    \r
+    \ForAll{$record$ in $R$}\r
+        \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}\r
+    \EndFor\\\r
+    \r
+    \ForAll{$\tuple{ssn, payload}$ in $API$}\r
+        \If{$payload$ is a $transaction$}\r
+            \State $AT \gets AT \cup \{\tuple{ssn,payload}\}$\r
+        \ElsIf{$payload$ is a $commit$}\r
+            \State $AC \gets AC \cup \{payload\}$\r
+        \ElsIf{$payload$ is a $abort$}\r
+            \State $AA \gets AA \cup \{payload\}$\r
+        \EndIf\r
+    \EndFor\\\r
+    \r
+    \State Sort $AT$ by ssn from oldest to newest\\\r
+    \r
+    \ForAll{$trans$ in $AT$} \Comment{Get the latest committed keys}\r
+        \State $\tuple{mid,vc ,kvSet,guard} \gets trans$\\\r
+    \r
+        \ForAll{$\tuple{k,v}$ in $kvSet$} \Comment{Get all key names in the system}\r
+            \State $kSet \gets kSet \cup \{k\}$\r
+        \EndFor\\\r
+\r
+        \If{$\lnot $\Call{TransactionLive}{$trans$}} \Comment{Only keep live transactions}\r
+            \State $AT \gets AT - \{trans\}$\r
+            \State Continue\r
+        \EndIf\\\r
+    \r
+        \State $tid \gets $ \Call{GetTid}{$trans$}\r
+        \ForAll{$com$ in $AC$}\r
+            \State $\tuple{tid', vc'} \gets com$\r
+            \If{$tid' = tid$}\r
+                \ForAll{$\tuple{k,v}$ in $kvSet$}\r
+                    \If{\Call{KeyValueLive}{$k,trans$}}\r
+                        \State $currentKV \gets currentKV \cup \{\tuple{k,v}\}$\r
+                    \EndIf\r
+                \EndFor\\\r
+                \r
+                \State $AT \gets AT - \{trans\}$ \Comment{No need for committed transactions}\r
+                \State Break\r
+            \EndIf\r
+        \EndFor\r
+    \EndFor\\\r
+    \r
+    \ForAll{$trans$ in $AT$} \Comment{Uncommitted ones only in order from lowest ssn to highest ssn}\r
+        \State $\tuple{mid,vc ,kvSet,guard} \gets trans$\r
+        \r
+        \If{\Call{GetArbitrator}{$guard$} $\neq midClient$}\r
+            \State Continue\r
+        \EndIf\r
+        \r
+        \If{\Call{EvaluateGuard}{$guard, currentKV$}} \Comment{Check if will abort}\r
+            \State $currentKV \gets $\Call{UpdateKVSet}{$currentKV, kvSet$}\r
+            \State $newPayload \gets \tuple{$\Call{GetTid}{$trans$}$, $\Call{GenerateVectorClock}{ } $}$ \Comment{Make new commit payload}\r
+        \Else\r
+            \State $newPayload \gets \tuple{$\Call{GetTid}{$trans$}$, mid, $\Call{GenerateVectorClock}{ } $}$ \Comment{Make new abort payload}\r
+        \EndIf\\\r
+        \r
+        \State \Call{InsertPayload}{$newPayload$}\r
+    \EndFor\\\r
+    \r
+\EndFunction\r
+\end{algorithmic}\r
+%\end{varwidth}% \r
+%}\r
+\r
+\r
+\r
+\section{\textbf{System Guarantees}}\r
+\begin{itemize}\r
+    \item Server cannot view data inside records\r
+    \item Server cannot forge or modify or create any records\r
+    \item Server cannot withhold any records\r
+    \item Server cannot reorder records that could not have been ordered differently due to network latency\r
+    \item Server cannot delete records unless told to do so.\r
+    \item There will always be an obvious key-value pair that is the latest key value pair.\r
+    \item The data structure is bounded in size such that $m$ is the minimum size of the data structure,  $n$ is the number of devices in the system and $s$ is the current size of the data structure: $m \leq s \leq (m+n-1)$\r
+    \item Data structure can only grow when there are too may key-value pairs (and aborts) than what fit in the current data structure size within reason.\r
+    \item No currently valid data can be lost by the system and go undetected.\r
+    \item Devices can operate offline and re-sync with the system and get a consistent view of the system\r
+    \item If the server tries to hold a device on an older version of the data structure, that device can eventually rejoin the main data structure without problems.\r
+    \item Devices that have a transaction aborted will be able to be notified about the abort indefinitely (no time frame when notification must be accepted).\r
+    \item Server cannot hold a device on an old version of the data structure and then move them to a newer version of the data structure without being detected (The server sequence numbers would reveal conflicts or gaps or both).\r
+\r
+\end{itemize}\r
+\r
+\r

 \end{document}\r
 \end{document}\r