From fbf137341810ac877016e4da4427e7a2ca411ad9 Mon Sep 17 00:00:00 2001
From: rtrimana <rtrimana@uci.edu>
Date: Thu, 30 Jun 2016 08:36:17 -0700
Subject: [PATCH] Give more explanations on data entries, add a few
punctuations, etc.
---
doc/iotcloud.tex | 63 +++++++++++++++++++++++++++++-------------------
1 file changed, 38 insertions(+), 25 deletions(-)
diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex
index b4dd588..acad12b 100644
--- a/doc/iotcloud.tex
+++ b/doc/iotcloud.tex
@@ -12,7 +12,7 @@
Each device has: user id + password
Server login is:
-hash1(user id), hash1(password)...
+hash1(user id), hash1(password)
Symmetric Crypto keys is:
hash2(user id | password)
@@ -31,17 +31,28 @@ Each entry has:
Payload has:
\begin{enumerate}
\item Sequence identifier
-\item Machine id
-\item Hash of previous slot
+\item Machine id (most probably something like a 64-bit random number
+that is self-generated by client)
+\item HMAC of previous slot
\item Data entries
\item HMAC of current slot
\end{enumerate}
-Data entry can be:
+A data entry can be one of these:
\begin{enumerate}
-\item All or part of a Key-value entry,
-\item Slot sequence entry: Machine id + last message identifier, or
-\item Queue state entry: Includes queue size
+\item All or part of a Key-value entry
+\item Slot sequence entry: Machine id + last message identifier
+\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.}
+\item Queue state entry: Includes queue size \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.}
\end{enumerate}
\subsection{Live status}
@@ -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.
\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
+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
+\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 slotes reaches
+70 that queue state entry 50 will be expunged from the queue.}
\end{enumerate}
When data is at the end of the queue ready to expunge, if:
@@ -62,10 +76,10 @@ When data is at the end of the queue ready to expunge, if:
beginning of the queue.
\item If the slot sequence number is not dead, then a message sequence
-entry must be inserted
+entry must be inserted.
\item If the queue state entry is not dead, it must be reinserted at the
-beginning of the queue
+beginning of the queue.
\end{enumerate}
@@ -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.
\paragraph{Local state on each client:}
-A list of machines and the corresponding latest sequence numbers
+A list of machines and the corresponding latest sequence numbers.
\paragraph{Validation procedure on client:}
\begin{enumerate}
-\item Decrypt each new slot in order
+\item Decrypt each new slot in order.
\item For each slot:
- (a) check its HMAC
+ (a) check its HMAC, and
(b) check that the previous entry HMAC field matches the previous
- entry
+ entry.
\item Check that the last message version for our machine matches our
-last message sent
+last message sent.
\item For all other machines, check that the latest sequence number is
-at least as large (never goes backwards)
-\item That the queue has a current queue state entry
+at least as large (never goes backwards).
+\item That the queue has a current queue state entry.
\item That the number of entries received is consistent with the size
-specified in the queue state entry
+specified in the queue state entry.
\end{enumerate}
Key-value entries can span multiple slots. They aren't valid until
they are complete.
\subsection{Resizing Queue}
-Client can make a request to resize the queue... This is done as a write that combines:
- (a) a slot with the message
+Client can make a request to resize the queue. This is done as a write that combines:
+ (a) a slot with the message, and
(b) a request to the server
\subsection{Formal Guarantees}
-Rahmadi should clean this section up.
+\textit{To be completed ...}
\begin{defn}[System Execution]
Formalize a system execution as a sequence of slot updates... There
@@ -121,7 +135,6 @@ edge from a slot update to a slot receive event if the receive event
reads from the update event.
\end{defn}
-
\begin{defn}[Suborder]
Define suborder of total order. It is a sequence of contiguous slots
updates (as observed by a given device).
@@ -153,7 +166,7 @@ for node n is consistent with the prefix suborder for all other nodes
that are in the transitive closure.
\end{theorem}
\begin{proof}
-Exercise for Rahmadi.
+\textit{TODO}
\end{proof}
\begin{defn}[State of Data Structure]
@@ -165,7 +178,7 @@ structure.
Algorithm gives consistent view of data structure.
\end{theorem}
\begin{proof}
-Exercise for Rahmadi.
+\textit{TODO}
\end{proof}
\subsection{Future Work}
--
2.34.1