Give more explanations on data entries, add a few punctuations, etc.
authorrtrimana <rtrimana@uci.edu>
Thu, 30 Jun 2016 15:36:17 +0000 (08:36 -0700)
committerrtrimana <rtrimana@uci.edu>
Thu, 30 Jun 2016 15:36:17 +0000 (08:36 -0700)
doc/iotcloud.tex

index b4dd588..acad12b 100644 (file)
@@ -12,7 +12,7 @@
 Each device has: user id + password\r
 \r
 Server login is:\r
-hash1(user id), hash1(password)...\r
+hash1(user id), hash1(password)\r
 \r
 Symmetric Crypto keys is:\r
 hash2(user id | password)\r
@@ -31,17 +31,28 @@ Each entry has:
 Payload has:\r
 \begin{enumerate}\r
 \item Sequence identifier\r
-\item Machine id\r
-\item Hash of previous slot\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
-Data entry can be:\r
+A data entry can be one of these:\r
 \begin{enumerate}\r
-\item All or part of a Key-value entry,\r
-\item Slot sequence entry: Machine id + last message identifier, or\r
-\item Queue state entry: Includes queue size\r
+\item All or part of a Key-value entry\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 \r
+from a certain client if a client's update has to expunge that other \r
+client's last entry from the queue. This is kept in the slot until \r
+the entry owner inserts a newer update into the queue.}\r
+\item Queue state entry: Includes queue size \newline {The purpose \r
+of this is for the client to tell if the server lies about the number \r
+of slots in the queue, e.g. if there are 2 queue state entry in the queue, \r
+e.g. 50 and 70, the client knows that when it sees 50, it should expect \r
+at most 50 slots in the queue and after it sees 70, it should expect \r
+50 slots before that queue state entry slot 50 and at most 70 slots. \r
+The queue state entry slot 70 is counted as slot number 51 in the queue.}\r
 \end{enumerate}\r
 \r
 \subsection{Live status}\r
@@ -51,9 +62,12 @@ Live status of entries:
 \item Key-Value Entry is dead if either (a) there is a newer key-value pair or (b) it is incomplete.\r
        \r
 \item Slot sequence number (of either a message version data\r
-or user-level data) is dead if there is a newer slot from the same machine\r
+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
+\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 \r
+entry 50 is dead and 70 is live. However, not until the number of slotes reaches \r
+70 that queue state entry 50 will be expunged from the queue.}\r
 \end{enumerate}\r
 \r
 When data is at the end of the queue ready to expunge, if:\r
@@ -62,10 +76,10 @@ When data is at the end of the queue ready to expunge, if:
 beginning of the queue.\r
 \r
 \item If the slot sequence number is not dead, then a message sequence\r
-entry must be inserted\r
+entry must be inserted.\r
 \r
 \item If the queue state entry is not dead, it must be reinserted at the\r
-beginning of the queue\r
+beginning of the queue.\r
 \end{enumerate}\r
 \r
 \r
@@ -80,35 +94,35 @@ pass.  On success, client updates its sequence number.  On failure,
 server sends updates slots to client and client validates those slots.\r
 \r
 \paragraph{Local state on each client:}\r
-A list of machines and the corresponding latest sequence numbers\r
+A list of machines and the corresponding latest sequence numbers.\r
 \r
 \paragraph{Validation procedure on client:}\r
 \begin{enumerate}\r
-\item Decrypt each new slot in order\r
+\item Decrypt each new slot in order.\r
 \item For each slot:\r
-    (a) check its HMAC\r
+    (a) check its HMAC, and\r
     (b) check that the previous entry HMAC field matches the previous\r
-    entry\r
+    entry.\r
 \item Check that the last message version for our machine matches our\r
-last message sent\r
+last message sent.\r
 \item For all other machines, check that the latest sequence number is\r
-at least as large (never goes backwards)\r
-\item That the queue has a current queue state entry\r
+at least as large (never goes backwards).\r
+\item That the queue has a current queue state entry.\r
 \item That the number of entries received is consistent with the size\r
-specified in the queue state entry\r
+specified in the queue state entry.\r
 \end{enumerate}\r
 \r
 Key-value entries can span multiple slots.  They aren't valid until\r
 they are complete.\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\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\r
        (b) a request to the server\r
 \r
 \subsection{Formal Guarantees}\r
 \r
-Rahmadi should clean this section up.\r
+\textit{To be completed ...}\r
 \r
 \begin{defn}[System Execution]\r
 Formalize a system execution as a sequence of slot updates...  There\r
@@ -121,7 +135,6 @@ edge from a slot update to a slot receive event if the receive event
 reads from the update event.\r
 \end{defn}\r
 \r
-\r
 \begin{defn}[Suborder]\r
 Define suborder of total order.  It is a sequence of contiguous slots\r
 updates (as observed by a given device).\r
@@ -153,7 +166,7 @@ for node n is consistent with the prefix suborder for all other nodes
 that are in the transitive closure.\r
 \end{theorem}\r
 \begin{proof}\r
-Exercise for Rahmadi.\r
+\textit{TODO}\r
 \end{proof}\r
 \r
 \begin{defn}[State of Data Structure]\r
@@ -165,7 +178,7 @@ structure.
 Algorithm gives consistent view of data structure.\r
 \end{theorem}\r
 \begin{proof}\r
-Exercise for Rahmadi.\r
+\textit{TODO}\r
 \end{proof}\r
 \r
 \subsection{Future Work}\r