Merge branch 'master' of ssh://plrg.eecs.uci.edu/home/git/iotcloud
authortkwa <kwathomas0@gmail.com>
Thu, 18 Aug 2016 00:12:39 +0000 (17:12 -0700)
committertkwa <kwathomas0@gmail.com>
Thu, 18 Aug 2016 00:12:39 +0000 (17:12 -0700)
1  2 
doc/iotcloud.tex

diff --combined doc/iotcloud.tex
@@@ -587,7 -587,7 +587,7 @@@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedg
  \r
  \begin{algorithmic}[1]\r
  \Function{Put}{$KV_s,\tuple{k_s,v_s}$}  \Comment{Interface function to update a key-value pair}\r
 -\State $\tuple{ck_s,\tuple{k_s,v_t}} \gets GetKVPair(KV,k_s)$\r
 +\State $\tuple{ck_s,\tuple{k_s,v_t}} \gets GetKVPair(KV_s,k_s)$\r
  \If{$\tuple{ck_s,\tuple{k_s,v_t}} = \emptyset$}\r
        \State $KV_s \gets KV_s \cup \{\tuple{ck_p, \tuple{k_s,v_s}}\}$\r
        \State $ck_p \gets ck_p + 1$\r
@@@ -909,7 -909,8 +909,8 @@@ received the same message $\mathsf{t}$ 
  \r
  \subsubsection{Lemmas and Proofs}\r
  \r
- \begin{prop} \r
+ \begin{prop}\r
+ \label{prop:parentmessage}\r
  Every client $\mathsf{J}$ who sends a message $\mathsf{t}$ \r
  has parent $\mathsf{p_t}$ as its latest stored message, and \r
  $\mathsf{s_t = s_{p_t} + 1}$. \r
@@@ -920,7 -921,9 +921,9 @@@ $\mathsf{s_t = }$ $\mathsf{s_{p_t + 1}}
  is sent. \r
  \end{proof}\r
  \r
- \begin{prop} If a rejected message entry is added to the set $\mathsf{CR}$ \r
+ \begin{prop} \r
+ \label{prop:rejectedmessage}\r
+ If a rejected message entry is added to the set $\mathsf{CR}$ \r
  at sequence number $\mathsf{s}$, the message will remain in $\mathsf{CR}$ \r
  until every client has seen it. \r
  \end{prop}\r
@@@ -943,18 -946,19 +946,20 @@@ $\mathsf{s - 1}$, this client will hav
  \restore\r
  \restore\r
  }\r
- \caption{By Lemma 1, receiving both $t$ and $u$ here is impossible.}\r
+ \caption{By \textbf{Lemma \ref{lem:twomessages}}, receiving both $t$ and $u$ here is impossible.}\r
  \end{figure}\r
  \r
- \begin{lem} Two messages are received without errors by a client $\mathsf{C}$; \r
+ \begin{lem}\r
+ \label{lem:twomessages}\r
+ Two messages are received without errors by a client $\mathsf{C}$; \r
  call them $\mathsf{t}$ and $\mathsf{u}$ such that $\mathsf{s_t \le s_u}$. \r
  Then $\mathsf{t}$ is in the path of $\mathsf{u}$. \r
  \end{lem}\r
  \begin{proof}\r
 -Assume otherwise. Then there are some pairs $\mathsf{(t,u)}$ that violate this lemma. \r
 -Take a specific $\mathsf{(t,u)}$ such that $\mathsf{s_u}$ is minimized and \r
 -$\mathsf{s_t}$ is maximized for this choice of $\mathsf{s_u}$.\r
 +Assume that there are some pairs of messages $\mathsf{(t,u)}$ that violate this lemma. \r
 +Take a specific $\mathsf{(t,u)}$ such that $\mathsf{s_u}$ is minimized, and \r
 +$\mathsf{s_t}$ is maximized for this choice of $\mathsf{s_u}$. We will show that $\mathsf{C}$\r
 +cannot receive both $\mathsf{t}$ and $\mathsf{u}$ without throwing an error.\r
  \r
  Clearly $\mathsf{C}$ will throw an error if $\mathsf{s_t = s_u}$. So \r
  $\mathsf{s_t < s_u}$. Additionally, if $\mathsf{C}$ receives $\mathsf{u}$ before \r
@@@ -977,25 -981,28 +982,28 @@@ $\mathsf{s_{r_1} = s_{l_1} = s_q + 1}$
  \r
  We also know the following facts: \r
  \r
- \begin{prop} No client sends both a message in \r
- $\mathsf{(r_2,...,t)}$ and a message in $\mathsf{(l_2,...,u)}$. \r
+ \begin{prop} \r
+ \label{prop:bothmessages}\r
+ No client sends both a message in $\mathsf{(r_2,...,t)}$ and a message in $\mathsf{(l_2,...,u)}$. \r
  \end{prop}\r
  \r
  \begin{proof}\r
  To send a message $\mathsf{p}$ that is the parent of some other \r
  message, one must have received the parent of $\mathsf{p}$. Since \r
  $\mathsf{u}$ is the message with smallest sequence number received by any \r
- client that violates Lemma 1, no client receives both a message in $\mathsf{r}$ \r
- and a message in $\mathsf{l}$. \r
+ client that violates Lemma \ref{lem:twomessages}, no client receives both a message \r
in $\mathsf{r}$ and a message in $\mathsf{l}$. \r
  \end{proof}\r
  \r
- \begin{prop} $\mathsf{C}$ does not receive any message with a\r
+ \begin{prop} \r
+ \label{prop:seqnumb}\r
+ $\mathsf{C}$ does not receive any message with a\r
  sequence number strictly between $\mathsf{s_t}$ and $\mathsf{s_u}$. \r
  \end{prop}\r
  \r
  \begin{proof} If there were such a message with sequence number smaller than \r
  $\mathsf{s_u}$, it would contradict the assumption that $\mathsf{u}$ is the \r
- message with the least sequence number that violates Lemma 1\r
+ message with the least sequence number that violates Lemma \ref{lem:twomessages}\r
  \end{proof}\r
  \r
  There are two cases:\r
@@@ -1007,13 -1014,13 +1015,13 @@@ the path of message $\mathsf{t}$, $\mat
  \item Case 1.1: $\mathsf{C}$ never updates its slot sequence list $\mathsf{SS}$ \r
  between receiving $\mathsf{t}$ and receiving $\mathsf{u}$; this can only happen if \r
  $\mathsf{s_t = s_u - 1}$. Since $\mathsf{t}$ is not the parent of $\mathsf{u}$, \r
- $\mathsf{hmac_p(u) \neq hmac_c(t)}$, causing $\mathsf{C}$ to error.\r
+ $\mathsf{hmac_p(u) \neq hmac_c(t)}$, causing $\mathsf{C}$ to throw an error.\r
  \item Case 1.2: Case 1.1 does not occur; therefore, $\mathsf{C}$ must update \r
  its slot sequence list $\mathsf{SS}$ at some point between receiving $\mathsf{t}$ \r
  and $\mathsf{u}$. \r
  The latest sequence number of $\mathsf{J}$ decreases during this time, which \r
  means it must decrease when some message is received, which means $\mathsf{C}$ \r
- throws an error in the $\mathsf{CheckLastSeqN}$ subroutine.\r
+ throws an error in the $\mathsf{CheckLastSeqN()}$ subroutine.\r
  \end{itemize}\r
  \r
  \item Case 2: $\mathsf{J}$ sent at least one message in $\mathsf{L}$. Call the \r
@@@ -1029,7 -1036,8 +1037,8 @@@ client $\mathsf{J}$ cannot then send a 
  $\mathsf{s_{r_1}}$, a contradiction.\r
  \item Case 2.2: Client $\mathsf{J}$ sends $\mathsf{r_1}$, and then $\mathsf{m}$. \r
  Let $\mathsf{X = (r_1 = x_1, \dots , x_n)}$ be the list of messages $\mathsf{J}$ sends \r
- starting before $\mathsf{r_1}$ and ending before $m$; clearly these all have sequence number $\mathsf{s_p = s_q + 1}$.\r
+ starting before $\mathsf{r_1}$ and ending before $m$; clearly these all have sequence \r
+ number $\mathsf{s_p = s_q + 1}$.\r
  \begin{itemize}\r
  \item Case 2.2.1: Some message in $\mathsf{X}$ was accepted. Before sending $\mathsf{m}$, \r
  $\mathsf{J}$'s value in $\mathsf{MS_J}$ for its own latest sequence number would \r
@@@ -1042,11 -1050,19 +1051,19 @@@ sending $\mathsf{p}$, because its own l
  \item Case 2.2.2: All messages in $\mathsf{X}$ were rejected, making $\mathsf{m}$ \r
  the first message of $\mathsf{J}$ that is accepted after $\mathsf{r_1}$.\r
  \r
- We will show that $\mathsf{C}$ sees $\mathsf{r_1}$. Assume not. Then $\mathsf{(r_2, ..., u)}$ must have at least $\mathsf{{max_g}_C} >= 2$ messages for $\mathsf{r_1}$ to fall off the end of the queue. Consider the sender of $\mathsf{r_3}$ and call it $\mathsf{H}$. $\mathsf{H \neq J}$ by Proposition 3 and the existence of $\mathsf{m}$. Since $\mathsf{H \neq J}$, then by Proposition 3 it could not also have sent a message in $\mathsf{(l_2,..., u}$. Therefore, $\mathsf{s_{u_H} < s_q + 2 = s_{t_H}}$, so upon receipt of $\mathsf{u}$, $\mathsf{C}$ will throw an error by the decrease in a last sequence number similar to Case 1, a contradiction.\r
\r
- Now that we know that $\mathsf{C}$ sees $\mathsf{r_1}$, note that C receives $\mathsf{u}$ immediately after $\mathsf{t}$ by Proposition 4. Therefore, \r
+ We will show that $\mathsf{C}$ sees $\mathsf{r_1}$. Assume not. Then $\mathsf{(r_2, ..., u)}$ \r
+ must have at least $\mathsf{{max_g}_C} \geq 2$ messages for $\mathsf{r_1}$ to fall off the \r
+ end of the queue. Consider the sender of $\mathsf{r_3}$ and call it $\mathsf{H}$. \r
+ $\mathsf{H \neq J}$ by Proposition \ref{prop:bothmessages} and the existence of $\mathsf{m}$. \r
+ Since $\mathsf{H \neq J}$, then by Proposition \ref{prop:bothmessages} it could not also \r
+ have sent a message in $\mathsf{(l_2,..., u)}$. Therefore, $\mathsf{s_{u_H} < s_q + 2 = s_{t_H}}$, \r
+ so upon receipt of $\mathsf{u}$, $\mathsf{C}$ will throw an error by the decrease in a \r
+ last sequence number similar to Case 1, a contradiction.\r
\r
+ Now that we know that $\mathsf{C}$ sees $\mathsf{r_1}$, note that C receives $\mathsf{u}$ \r
+ immediately after $\mathsf{t}$ by Proposition \ref{prop:seqnumb}. Therefore, \r
  $\mathsf{C}$ could not have seen a message after $\mathsf{t}$ with sequence number less \r
- than $\mathsf{s_m}$. In the $\mathsf{PutDataEntries}$ subroutine, $\mathsf{J}$ adds every \r
+ than $\mathsf{s_m}$. In the $\mathsf{PutDataEntries()}$ subroutine, $\mathsf{J}$ adds every \r
  $\mathsf{cr}$ entry that contains sequence number $\mathsf{s}$ and machine ID \r
  $\mathsf{id}$ of the messsages that win in the collisions before $\mathsf{m}$ into \r
  $\mathsf{CR}$; $\mathsf{CR}$ keeps the collection of live $\mathsf{cr}$ entries, namely\r
@@@ -1066,7 -1082,9 +1083,9 @@@ $\mathsf{\tuple{s_q+1, id_K}}$ in the c
  \end{itemize}\r
  \end{proof}\r
  \r
- \begin{lem} If there are two packets $\mathsf{t}$ and $\mathsf{u}$, with \r
+ \begin{lem} \r
+ \label{lem:pathmessages}\r
+ If there are two messages $\mathsf{t}$ and $\mathsf{u}$, with \r
  $\mathsf{s_t \leq s_u}$, such that $\mathsf{t}$ is in the path of $\mathsf{u}$, \r
  then for any message $\mathsf{p}$ with $\mathsf{s_p \leq s_t}$, iff $\mathsf{p}$ is in \r
  the path of $\mathsf{t}$, it is in the path of $\mathsf{u}$. \r
@@@ -1105,11 -1123,11 +1124,11 @@@ in that slot in $\mathsf{T}$. Let $\mat
  set, with partial sequence $\mathsf{P_{C_1}}$, and let $\mathsf{u}$ be some message with \r
  $\mathsf{s_u > s_n}$ that $\mathsf{C_1}$ shares with another client. Then let $\mathsf{T}$ \r
  be the portion of the path of $\mathsf{u}$ ending at sequence number $\mathsf{s_n}$ and \r
- $\mathsf{t}$ be the message at that sequence number. Clearly, by Lemma 1, $\mathsf{P_{C_1}}$ \r
- is consistent with $\mathsf{T}$. We will show that, for every other client $\mathsf{D}$ \r
- with partial sequence $\mathsf{P_D}$, $\mathsf{P_D}$ has some message whose path includes \r
- $\mathsf{t}$. Because $\mathsf{D}$ is in the transitive closure, there is a sequence of \r
- clients $\mathsf{\mathscr{C} = (C_1, C_2, ..., D)}$ from $\mathsf{C_1}$ to $\mathsf{D}$, \r
+ $\mathsf{t}$ be the message at that sequence number. Clearly, by Lemma \ref{lem:twomessages}, \r
+ $\mathsf{P_{C_1}}$ is consistent with $\mathsf{T}$. We will show that, for every other client \r
+ $\mathsf{D}$ with partial sequence $\mathsf{P_D}$, $\mathsf{P_D}$ has some message whose path \r
+ includes $\mathsf{t}$. Because $\mathsf{D}$ is in the transitive closure, there is a sequence \r
of clients $\mathsf{\mathscr{C} = (C_1, C_2, ..., D)}$ from $\mathsf{C_1}$ to $\mathsf{D}$, \r
  where each shares an edge with the next.\r
  We prove by induction that $\mathsf{P_D}$ has a message whose path includes $\mathsf{t}$.\r
  \begin{itemize}\r
  \item Inductive step: Each client in $\mathsf{\mathscr{C}}$ has a partial sequence with a message \r
  that includes $\mathsf{t}$ if the previous client does. Suppose $\mathsf{P_{C_k}}$ has \r
  a message $\mathsf{w}$ with a path that includes $\mathsf{t}$, and shares message $\mathsf{x}$ \r
- with $\mathsf{P_{C_{k+1}}}$ such that $\mathsf{s_x > s_n}$. By Lemma 1, $\mathsf{w}$ or \r
- $\mathsf{x}$, whichever has the least sequence number, is in the path of the other, and therefore \r
by Lemma 2, $\mathsf{t}$ is in the path of $\mathsf{x}$.\r
+ with $\mathsf{P_{C_{k+1}}}$ such that $\mathsf{s_x > s_n}$. By Lemma \ref{lem:twomessages}, \r
+ $\mathsf{w}$ or $\mathsf{x}$, whichever has the least sequence number, is in the path of the other, \r
and therefore by Lemma \ref{lem:pathmessages}, $\mathsf{t}$ is in the path of $\mathsf{x}$.\r
  \r
  \item Let $\mathsf{z}$ be the message of $\mathsf{D}$ whose path includes $\mathsf{t}$. \r
- By Lemma 1, every message in $\mathsf{P_D}$ with sequence number smaller than $\mathsf{s_w}$ \r
- is in the path of $\mathsf{z}$. Since $\mathsf{t}$ is in the path of $\mathsf{z}$, every \r
- message in $\mathsf{P_D}$ with smaller sequence number than $\mathsf{s_t = s_n}$ is in $\mathsf{T}$. \r
+ By Lemma \ref{lem:twomessages}, every message in $\mathsf{P_D}$ with sequence number smaller \r
+ than $\mathsf{s_w}$ is in the path of $\mathsf{z}$. Since $\mathsf{t}$ is in the path of \r
+ $\mathsf{z}$, every message in $\mathsf{P_D}$ with smaller sequence number than \r
+ $\mathsf{s_t = s_n}$ is in $\mathsf{T}$. \r
  Therefore, $\mathsf{P_D}$ is consistent with $\mathsf{T}$.\r
  \r
  \end{itemize}\r