From: rtrimana Date: Tue, 2 Aug 2016 18:12:00 +0000 (-0700) Subject: Adding loop and status updates when putting data entries on server X-Git-Url: http://plrg.eecs.uci.edu/git/?p=iotcloud.git;a=commitdiff_plain;h=bda7c4d917ef1c87d3b9aa32528d03dd397e7bf1 Adding loop and status updates when putting data entries on server --- diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex index 89c1c86..5e3928e 100644 --- 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 \\ $v$ is value of entry \\ $kv$ is a key-value entry $\tuple{k,v}$\\ -$DE$ is a set of data entries, possibly of different types \\ +$D = \{kv,ss,qs,cr\}$ \\ +$DE = \{de \mid de \in D\}$ \\ $Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\ $sv_s = \tuple{s, E(Dat_s)} = \tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\ \textbf{States} \\ -\textit{$capacity$ = data entry $DE$ maximum size/capacity} \\ +\textit{$cp$ = data entry $DE$ maximum size/capacity} \\ \textit{$cr_p$ = saved cr entry $\tuple{s,id}$ on client if there is a collision (sent in the following slot)} \\ \textit{$cr_{p_{last}}$ = saved cr entry $\tuple{s,id}$ on client if there is a @@ -498,7 +499,7 @@ collision in reinserting the last slot (sent in the following slot)} \\ $\tuple{s_{last},sv_{last},id_{last}}$ (initially $\emptyset$)} \\ \textit{$th_p$ = threshold number of dead slots for a resize to happen} \\ \textit{$m'_p$ = offset added to $max$ for resize} \\ -\textit{$KV$ = associative array of $\tuple{ck, \tuple{k,v}}$ kv entries on client} \\ +\textit{$KV$ = set of $\tuple{ck, \tuple{k,v}}$ of kv entries on client} \\ \textit{$SL_p$ = set of returned slots on client} \\ \textit{SK = Secret Key} \\ \\ \textbf{Helper Functions} \\ @@ -578,7 +579,6 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \end{algorithmic} \begin{algorithmic}[1] - \Function{ReinsertLastSlot}{$MS_s,SK_s,sl_{s_{last}},max'_s,hmac_{p_s}$} \State $s_s \gets MaxLastSeqN(MS_s)$ \State $sv_s \gets GetSV(sl_{s_{last}})$ @@ -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}$ \State $cr_s \gets \Call{HandleCollision}{\tuple{stat_s,SL_s}}$ \State \Return{$\tuple{cr_s,hmac_{p_p}}$} - \EndFunction \end{algorithmic} \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?} \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.} + \begin{algorithmic}[1] \Function{GetDEPairs}{$KV_s,max'_s,need_s,sl_s$} \State $DE_{ret} \gets \emptyset$ -\State $capacity_s \gets capacity$ +\State $cp_s \gets cp$ \If{$cr_p \neq \emptyset$}\Comment{Check and insert a $cr$} \State $DE_{ret} \gets DE_{ret} \cup cr_p$ - \State $capacity_s \gets capacity_s - 1$ -\EndIf -\If{$cr_{p_{last}} \neq \emptyset$}\Comment{Check and insert a $cr$} - \State $DE_{ret} \gets DE_{ret} \cup cr_{p_{last}}$ - \State $capacity_s \gets capacity_s - 1$ + \State $cp_s \gets cp_s - 1$ \EndIf +%\If{$cr_{p_{last}} \neq \emptyset$}\Comment{Check and insert a $cr$} +% \State $DE_{ret} \gets DE_{ret} \cup cr_{p_{last}}$ +% \State $cp_s \gets cp_s - 1$ +%\EndIf \If{$max'_s \neq \emptyset$}\Comment{Check and insert a $qs$} \State $qs_s \gets max'_s$ \State $DE_{ret} \gets DE_{ret} \cup qs_s$ - \State $capacity_s \gets capacity_s - 1$ + \State $cp_s \gets cp_s - 1$ \EndIf -\If{$need_s$}\Comment{Check and insert a $ss$} - \State $id_s \gets GetID(sl_s)$ - \State $s_{s_{last}} \gets GetLastS(sl_s)$ - \State $ss_s \gets CreateSS(id_s,s_{s_{last}})$ - \State $DE_{ret} \gets DE_{ret} \cup ss_s$ - \State $capacity_s \gets capacity_s - 1$ -\EndIf -\If{$|KV_s| \leq capacity$}\Comment{$KV$ set can extend multiple slots} +%\If{$need_s$}\Comment{Check and insert a $ss$} +% \State $id_s \gets GetID(sl_s)$ +% \State $s_{s_{last}} \gets GetLastS(sl_s)$ +% \State $ss_s \gets CreateSS(id_s,s_{s_{last}})$ +% \State $DE_{ret} \gets DE_{ret} \cup ss_s$ +% \State $cp_s \gets cp_s - 1$ +%\EndIf +\If{$|KV_s| \leq cp$}\Comment{$KV$ set can extend multiple slots} \State $DE_{ret} \gets DE_{ret} \cup \{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s\}$ \Else \State $DE_{ret} \gets DE_{ret} \cup \{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s, - ck_g \leq ck_s < ck_g + capacity_s\}$ - \If{$|DE_{ret}| = capacity$} - \State $ck_g \gets ck_g + capacity_s$\Comment{Middle of KV set} + ck_g \leq ck_s < ck_g + cp_s\}$ + \If{$|DE_{ret}| = cp$} + \State $ck_g \gets ck_g + cp_s$\Comment{Middle of KV set} \Else \State $ck_g \gets 0$\Comment{End of KV set} \EndIf @@ -640,19 +640,27 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \begin{algorithmic}[1] \Procedure{PutDataEntries}{$th_p,m'_p$} -\State $s_p \gets MaxLastSeqN(MS)$ -\State $max'_p \gets \Call{CheckResize}{MS,th_p,max'_g,m'_p}$ -\State $need_p \gets \Call{CheckNeedSS}{MS,max'_g}$ -\State $DE_p \gets \Call{GetDEPairs}{KV,max'_p,need_p,sl_{last}}$ -\State $hmac_{c_p} \gets Hmac(DE_p,SK)$ -\State $Dat_p \gets CreateDat(s_p,id_{self},hmac_{p_p},DE_p,hmac_{c_p})$ -\State $hmac_{p_p} \gets hmac_{c_p}$ -\State $sv_p \gets Encrypt(Dat_p,SK)$ -\State $\tuple{stat_p,SL_p} \gets \Call{PutSlot}{s_p,sv_p,max'_p}$ -\State $cr_p \gets \Call{HandleCollision}{\tuple{stat_p,SL_p}}$ -\If{$need_p$} - \State $cr_{p_{last}} \gets \Call{ReinsertLastSlot}{sl_{last},max'_p}$ -\EndIf +\State $success \gets false$ +\While{$\neg success$} + \State $s_p \gets MaxLastSeqN(MS)$ + \State $max'_p \gets \Call{CheckResize}{MS,th_p,max'_g,m'_p}$ + \State $need_p \gets \Call{CheckNeedSS}{MS,max'_g}$ + \State $DE_p \gets \Call{GetDEPairs}{KV,max'_p,need_p,sl_{last}}$ + \State $hmac_{c_p} \gets Hmac(DE_p,SK)$ + \State $Dat_p \gets CreateDat(s_p,id_{self},hmac_{p_p},DE_p,hmac_{c_p})$ + \State $hmac_{p_p} \gets hmac_{c_p}$ + \State $sv_p \gets Encrypt(Dat_p,SK)$ + \State $\tuple{stat_p,SL_p} \gets \Call{PutSlot}{s_p,sv_p,max'_p}$ + \State $success \gets stat_p$ + \If{$\neg success$} + \State $cr_p \gets \Call{HandleCollision}{\tuple{stat_p,SL_p}}$ + \EndIf + %\If{$need_p$} + % \State $\tuple{cr_{p_{last}},hmac_{p_p}} \gets + % \Call{ReinsertLastSlot}{MS,SK,sl_{last},max'_p,hmac_{p_p}}$ + %\EndIf +\EndWhile +\State $MS \gets \Call{UpdateLastSeqN}{id_{self},s_p,MS}$ \EndProcedure \end{algorithmic} @@ -661,6 +669,8 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \note{General comments... Work on structuring things to improve readability... This include names of functions/variables, how things are partitioned into functions, adding useful comments,...} + +\note{Also Missing liveness state definition in algorithm...} \subsection{Definitions for Formal Guarantees}