Merge branch 'master' of ssh://plrg.eecs.uci.edu/home/git/iotcloud

diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex
index 36de049285e87168065191f8025e4d0f19d425cb..bf11fb0f56903da3ce4044c796a14711b8f9df7f 100644 (file)
--- a/doc/iotcloud.tex
+++ b/doc/iotcloud.tex
@@ -478,12 +478,13 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s
 $k$ is key of entry \\\r
 $v$ is value of entry \\\r
 $kv$ is a key-value entry $\tuple{k,v}$\\\r
-$DE$ is a set of data entries, possibly of different types \\\r
+$D = \{kv,ss,qs,cr\}$ \\\r
+$DE = \{de \mid de \in D\}$ \\\r
 $Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
 $sv_s = \tuple{s, E(Dat_s)} = \r
 \tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\\r
 \textbf{States} \\\r
-\textit{$capacity$ = data entry $DE$ maximum size/capacity} \\\r
+\textit{$cp$ = data entry $DE$ maximum size/capacity} \\\r
 \textit{$cr_p$ = saved cr entry $\tuple{s,id}$ on client if there is a collision\r
 (sent in the following slot)} \\\r
 \textit{$cr_{p_{last}}$ = saved cr entry $\tuple{s,id}$ on client if there is a \r
@@ -498,7 +499,7 @@ collision in reinserting the last slot (sent in the following slot)} \\
        $\tuple{s_{last},sv_{last},id_{last}}$ (initially $\emptyset$)} \\\r
 \textit{$th_p$ = threshold number of dead slots for a resize to happen} \\\r
 \textit{$m'_p$ = offset added to $max$ for resize} \\\r
-\textit{$KV$ = associative array of $\tuple{ck, \tuple{k,v}}$ kv entries on client} \\\r
+\textit{$KV$ = set of $\tuple{ck, \tuple{k,v}}$ of kv entries on client} \\\r
 \textit{$SL_p$ = set of returned slots on client} \\\r
 \textit{SK = Secret Key} \\ \\\r
 \textbf{Helper Functions} \\\r
@@ -578,7 +579,6 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge
 \end{algorithmic}\r
 \r
 \begin{algorithmic}[1]\r
-\r
 \Function{ReinsertLastSlot}{$MS_s,SK_s,sl_{s_{last}},max'_s,hmac_{p_s}$}\r
 \State $s_s \gets MaxLastSeqN(MS_s)$\r
 \State $sv_s \gets GetSV(sl_{s_{last}})$\r
@@ -590,46 +590,46 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge
 \State $\tuple{stat_s,SL_s} \gets \Call{PutSlot}{s_s,sv_s,max'_s}$   \r
 \State $cr_s \gets \Call{HandleCollision}{\tuple{stat_s,SL_s}}$\r
 \State \Return{$\tuple{cr_s,hmac_{p_p}}$}\r
-\r
 \EndFunction\r
 \end{algorithmic}\r
 \note{Shouldn't this function do something pretty sophisticated about seeing what data we actually need to keep from the last slot and not just insert the entire thing?}\r
 \r
 \note{Probably best to just not call this function if $need_s$ is false and not pass in such parameters.  It makes it harder to read.}\r
 \r
+\r
 \begin{algorithmic}[1]\r
 \Function{GetDEPairs}{$KV_s,max'_s,need_s,sl_s$}\r
 \State $DE_{ret} \gets \emptyset$\r
-\State $capacity_s \gets capacity$\r
+\State $cp_s \gets cp$\r
 \If{$cr_p \neq \emptyset$}\Comment{Check and insert a $cr$}\r
        \State $DE_{ret} \gets DE_{ret} \cup cr_p$\r
-       \State $capacity_s \gets capacity_s - 1$\r
-\EndIf\r
-\If{$cr_{p_{last}} \neq \emptyset$}\Comment{Check and insert a $cr$}\r
-       \State $DE_{ret} \gets DE_{ret} \cup cr_{p_{last}}$\r
-       \State $capacity_s \gets capacity_s - 1$\r
+       \State $cp_s \gets cp_s - 1$\r
 \EndIf\r
+%\If{$cr_{p_{last}} \neq \emptyset$}\Comment{Check and insert a $cr$}\r
+%      \State $DE_{ret} \gets DE_{ret} \cup cr_{p_{last}}$\r
+%      \State $cp_s \gets cp_s - 1$\r
+%\EndIf\r
 \If{$max'_s \neq \emptyset$}\Comment{Check and insert a $qs$}\r
        \State $qs_s \gets max'_s$\r
        \State $DE_{ret} \gets DE_{ret} \cup qs_s$\r
-       \State $capacity_s \gets capacity_s - 1$\r
+       \State $cp_s \gets cp_s - 1$\r
 \EndIf\r
-\If{$need_s$}\Comment{Check and insert a $ss$}\r
-       \State $id_s \gets GetID(sl_s)$\r
-       \State $s_{s_{last}} \gets GetLastS(sl_s)$\r
-       \State $ss_s \gets CreateSS(id_s,s_{s_{last}})$\r
-       \State $DE_{ret} \gets DE_{ret} \cup ss_s$\r
-       \State $capacity_s \gets capacity_s - 1$\r
-\EndIf\r
-\If{$|KV_s| \leq capacity$}\Comment{$KV$ set can extend multiple slots}\r
+%\If{$need_s$}\Comment{Check and insert a $ss$}\r
+%      \State $id_s \gets GetID(sl_s)$\r
+%      \State $s_{s_{last}} \gets GetLastS(sl_s)$\r
+%      \State $ss_s \gets CreateSS(id_s,s_{s_{last}})$\r
+%      \State $DE_{ret} \gets DE_{ret} \cup ss_s$\r
+%      \State $cp_s \gets cp_s - 1$\r
+%\EndIf\r
+\If{$|KV_s| \leq cp$}\Comment{$KV$ set can extend multiple slots}\r
        \State $DE_{ret} \gets DE_{ret} \cup\r
        \{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s\}$\r
 \Else\r
        \State $DE_{ret} \gets DE_{ret} \cup\r
        \{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s,\r
-               ck_g \leq ck_s < ck_g + capacity_s\}$\r
-       \If{$|DE_{ret}| = capacity$}\r
-               \State $ck_g \gets ck_g + capacity_s$\Comment{Middle of KV set}\r
+               ck_g \leq ck_s < ck_g + cp_s\}$\r
+       \If{$|DE_{ret}| = cp$}\r
+               \State $ck_g \gets ck_g + cp_s$\Comment{Middle of KV set}\r
        \Else\r
                \State $ck_g \gets 0$\Comment{End of KV set}\r
        \EndIf\r
@@ -640,19 +640,27 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge
 \r
 \begin{algorithmic}[1]\r
 \Procedure{PutDataEntries}{$th_p,m'_p$}\r
-\State $s_p \gets MaxLastSeqN(MS)$\r
-\State $max'_p \gets \Call{CheckResize}{MS,th_p,max'_g,m'_p}$\r
-\State $need_p \gets \Call{CheckNeedSS}{MS,max'_g}$\r
-\State $DE_p \gets \Call{GetDEPairs}{KV,max'_p,need_p,sl_{last}}$\r
-\State $hmac_{c_p} \gets Hmac(DE_p,SK)$\r
-\State $Dat_p \gets CreateDat(s_p,id_{self},hmac_{p_p},DE_p,hmac_{c_p})$\r
-\State $hmac_{p_p} \gets hmac_{c_p}$\r
-\State $sv_p \gets Encrypt(Dat_p,SK)$\r
-\State $\tuple{stat_p,SL_p} \gets \Call{PutSlot}{s_p,sv_p,max'_p}$\r
-\State $cr_p \gets \Call{HandleCollision}{\tuple{stat_p,SL_p}}$\r
-\If{$need_p$}\r
-       \State $cr_{p_{last}} \gets \Call{ReinsertLastSlot}{sl_{last},max'_p}$\r
-\EndIf\r
+\State $success \gets false$\r
+\While{$\neg success$}\r
+       \State $s_p \gets MaxLastSeqN(MS)$\r
+       \State $max'_p \gets \Call{CheckResize}{MS,th_p,max'_g,m'_p}$\r
+       \State $need_p \gets \Call{CheckNeedSS}{MS,max'_g}$\r
+       \State $DE_p \gets \Call{GetDEPairs}{KV,max'_p,need_p,sl_{last}}$\r
+       \State $hmac_{c_p} \gets Hmac(DE_p,SK)$\r
+       \State $Dat_p \gets CreateDat(s_p,id_{self},hmac_{p_p},DE_p,hmac_{c_p})$\r
+       \State $hmac_{p_p} \gets hmac_{c_p}$\r
+       \State $sv_p \gets Encrypt(Dat_p,SK)$\r
+       \State $\tuple{stat_p,SL_p} \gets \Call{PutSlot}{s_p,sv_p,max'_p}$\r
+       \State $success \gets stat_p$\r
+       \If{$\neg success$}\r
+               \State $cr_p \gets \Call{HandleCollision}{\tuple{stat_p,SL_p}}$\r
+       \EndIf\r
+       %\If{$need_p$}\r
+       %       \State $\tuple{cr_{p_{last}},hmac_{p_p}} \gets \r
+       %       \Call{ReinsertLastSlot}{MS,SK,sl_{last},max'_p,hmac_{p_p}}$\r
+       %\EndIf\r
+\EndWhile\r
+\State $MS \gets \Call{UpdateLastSeqN}{id_{self},s_p,MS}$\r
 \EndProcedure\r
 \end{algorithmic}\r
 \r
@@ -661,6 +669,8 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge
 \note{General comments...  Work on structuring things to improve\r
   readability...  This include names of functions/variables, how\r
   things are partitioned into functions, adding useful comments,...}\r
+  \r
+\note{Also Missing liveness state definition in algorithm...}\r
 \r
 \r
 \subsection{Definitions for Formal Guarantees}\r