From 555a795c48ca508cb06710942fc78ec0284b8025 Mon Sep 17 00:00:00 2001 From: rtrimana Date: Mon, 22 Aug 2016 14:33:13 -0700 Subject: [PATCH] Computing expected size; refactoring code into functions and procedures --- doc/iotcloud.tex | 158 ++++++++++++++++++++++++++++------------------- 1 file changed, 96 insertions(+), 62 deletions(-) diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex index 9d970c4..1016f55 100644 --- a/doc/iotcloud.tex +++ b/doc/iotcloud.tex @@ -205,7 +205,6 @@ $slot_s = \tuple{s, E(Dat_s)} = \textit{$d$ = delta between the last $s$ recorded and the first $s$ received} \\ \textit{$id_{self}$ = machine Id of this client} \\ \textit{$max_g$ = maximum number of slots (initially $max_g > 0$)} \\ -\textit{m = number of slots stored on client (initially $m = 0$)} \\ \textit{$sl_{last}$ = info of last slot in queue = $\tuple{s_{last},sv_{last},id_{last}}$ (initially $\emptyset$)} \\ \textit{DT = set of $\tuple{k,v}$ on client} \\ @@ -244,14 +243,13 @@ $GetLivEntLastS(LV_s,kv_s)= s$ \textit{such that} $\tuple{kv, s} \in LV_s \wedge \forall \tuple{kv_s, s_s} \in LV_s, kv_s = kv$ \\ $GetKV($key-value data entry$)=\tuple{k_s,v_s} = kv_s$ \\ $GetSS($slot-sequence data entry$)=\tuple{id_s,s_{s_{last}}} = ss_s$ \\ -%$GetQS($queue-state data entry$)=qs_s$ \\ $GetCR($de$)=\tuple{s_s,id_s} = cr_s$ \\ $Hmac(Dat_s,SK) = hmac_c$ \textit{value computed from $s$, $id$, $hmac_p$, and $DE$ taken from $Dat_s$} \\ -$IsKV(de) = true$ \textit{if $de$ is a $kv$, false otherwise} \\ -$IsSS(de) = true$ \textit{if $de$ is a $ss$, false otherwise} \\ -$IsQS(de) = true$ \textit{if $de$ is a $qs$, false otherwise} \\ -$IsCR(de) = true$ \textit{if $de$ is a $cr$, false otherwise} \\ +$IsKv(de) = true$ \textit{if $de$ is a $kv$, false otherwise} \\ +$IsSs(de) = true$ \textit{if $de$ is a $ss$, false otherwise} \\ +$IsQs(de) = true$ \textit{if $de$ is a $qs$, false otherwise} \\ +$IsCr(de) = true$ \textit{if $de$ is a $cr$, false otherwise} \\ $GetKey(kv)=k$\Comment{$kv = \tuple{k, v}$} \\ $GetVal(kv)=v$ \\ $GetId(ss)=id$\Comment{$ss = \tuple{id, s_{last}}$} \\ @@ -282,7 +280,7 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s \begin{algorithmic}[1] \Function{GetQueSta}{$DE_s$} \State $qs_{de} \gets qs$ \textit{such that} $qs \in DE_s, - de_s \in D \land IsQS(de_s)$ + de_s \in D \land IsQs(de_s)$ \If{$qs_{de} \neq \emptyset$} \State $qs_{ret} \gets qs_{de})$ \Else @@ -294,14 +292,14 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s \begin{algorithmic}[1] \Function{GetSlotSeq}{$DE_s$} -\State $DE_{ss} \gets \{de | de \in DE_s \land IsSS(de)\}$ +\State $DE_{ss} \gets \{de | de \in DE_s \land IsSs(de)\}$ \State \Return{$DE_{ss}$} \EndFunction \end{algorithmic} \begin{algorithmic}[1] \Function{GetColRes}{$DE_s$} -\State $DE_{cr} \gets \{de | de \in DE_s \land IsCR(de)\}$ +\State $DE_{cr} \gets \{de | de \in DE_s \land IsCr(de)\}$ \State \Return{$DE_{cr}$} \EndFunction \end{algorithmic} @@ -423,11 +421,7 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s \end{algorithmic} \begin{algorithmic}[1] -\Function{ValidSlotsRange}{$|SL_s|,s_{s_{min}},s_{s_{max}}$} -\State $sz_{SL} \gets s_{s_{max}} - s_{s_{min}} + 1$ -\If{$sz_{SL} \neq |SL_s|$} - \State \Call{Error}{'Sequence numbers range does not match actual set'} -\EndIf +\Function{ValidSlotsRange}{$s_{s_{min}}$} \State $s_{s_{last}} \gets MaxSMSeqN(SM)$ \If{$s_{s_{min}} \leq s_{s_{last}}$} \State \Call{Error}{'Server sent old slots'} @@ -437,11 +431,8 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s \end{algorithmic} \begin{algorithmic}[1] -\Procedure{CheckSlotsRange}{$|SL_s|$} -\State $s_{s_{max}} \gets MaxLastSeqN(MS)$ -\State $s_{self} \gets MS[id_{self}]$ -\State $sz_{expected} \gets s_{s_{max}} - s_{self} + 1$ -\If{$|SL_s| \neq sz_{expected}$} +\Procedure{CheckNumSlots}{$|SL_s|,sz_s$} +\If{$|SL_s| \neq sz_s$} \State \Call{Error}{'Actual number of slots does not match expected'} \EndIf \EndProcedure @@ -458,7 +449,7 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s \end{algorithmic} \begin{algorithmic}[1] -\Function{ValidateHmacChain}{$Dat_s,s_s,hmac_{p_s},sl_l$} +\Function{ValidHmacChain}{$Dat_s,s_s,hmac_{p_s},sl_l$} \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_s)$ \If {$ \neg(s_s = 0 \land hmac_{p_s} = 0)$} \State $s_l \gets GetLastS(sl_l)$ @@ -476,7 +467,7 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s \begin{algorithmic}[1] \Function{UpdateDT}{$DT_s,DE_s,LV_s,s_s$} -\State $DE_{s_{kv}} \gets \{de_s | de_s \in DE_s \land IsKV(de_s)\}$ +\State $DE_{s_{kv}} \gets \{de_s | de_s \in DE_s \land IsKv(de_s)\}$ \ForAll{$de_s \in DE_{s_{kv}}$} \State $kv_s \gets GetKV(de_s)$ \State $LV_s \gets \Call{UpdateKVLivEnt}{LV_s,kv_s,s_s}$ @@ -493,12 +484,72 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s \EndFunction \end{algorithmic} +\begin{algorithmic}[1] +\Function{InitExpSize}{$s_{min}$} +\If{$s_{min} < max_g$}\Comment{Check whether $SL$ is full on server} + \State $sz_s \gets s_{min}$ +\Else + \State $sz_s \gets max_g$ +\EndIf +\State \Return{$sz_s$} +\EndFunction +\end{algorithmic} + +\begin{algorithmic}[1] +\Function{UpdateExpSize}{$sz_s$} +\State $sz_s \gets sz_s + 1$ +\If{$sz_s > max_g$}\Comment{Expected size $\leq max_g$} + \State $sz_s \gets max_g$ +\EndIf +\State \Return{$sz_s$} +\EndFunction +\end{algorithmic} + +\begin{algorithmic}[1] +\Function{UpdateQS}{$Dat_s,max_s$} +\State $DE_s \gets GetDatEnt(Dat_s)$ +\State $qs_s \gets \Call{GetQueSta}{DE_s}$\Comment{Handle qs} +\If{$qs_s \neq \emptyset \land qs_s > max_s$} + \State $max_s \gets qs_s$ +\EndIf +\State \Return{$max_s$} +\EndFunction +\end{algorithmic} + +\begin{algorithmic}[1] +\Procedure{UpdateCR}{$DE_s$} +\State $DE_{s_{cr}} \gets \Call{GetColRes}{DE_s}$\Comment{Handle cr} +\If{$DE_{s_{cr}} \neq \emptyset$} + \ForAll{$de_{s_{cr}} \in DE_{s_{cr}}$} + \State $cr_s \gets GetCR(de_{s_{cr}})$ + \State $\Call{CheckCollision}{MS,SM,cr_s}$ + \State $CR_{live} \gets \Call{AddCRLivEnt}{CR_{live},cr_s}$ + \EndFor +\EndIf +\EndProcedure +\end{algorithmic} + +\begin{algorithmic}[1] +\Function{UpdateSS}{$DE_s,MS_s$} +\State $DE_{s_{ss}} \gets \Call{GetSlotSeq}{DE_s}$\Comment{Handle ss} +\If{$DE_{s_{ss}} \neq \emptyset$} + \ForAll{$de_{s_{ss}} \in DE_{s_{ss}}$} + \State $\tuple{id_d,s_{d_{last}}} \gets GetSS(de_{s_{ss}})$ + \State $MS_s \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_s}$ + \State $SS_{live} \gets \Call{AddSSLivEnt}{SS_{live},de_{s_{ss}}}$ + \EndFor +\EndIf +\State \Return{$MS_s$} +\EndFunction +\end{algorithmic} + \begin{algorithmic}[1] \Procedure{ProcessSL}{$SL_g$} \State $MS_g \gets \emptyset$ \State $\tuple{s_{g_{min}},sv_{g_{min}}} \gets MinSlot(SL_g)$ \State $\tuple{s_{g_{max}},sv_{g_{max}}} \gets MaxSlot(SL_g)$ -\State $d \gets \Call{ValidSlotsRange}{|SL_g|,s_{g_{min}},s_{g_{max}}}$ +\State $d \gets \Call{ValidSlotsRange}{s_{g_{min}}}$ +\State $sz \gets \Call{InitExpSize}{s_{g_{min}}}$ \For{$s_g \gets s_{g_{min}}$ \textbf{to} $s_{g_{max}}$}\Comment{Process slots in $SL_g$ in order} \State $\tuple{s_g,sv_g} \gets Slot(SL_g,s_g)$ @@ -509,51 +560,33 @@ $MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s \If{$s_g \neq s_{g_{in}}$} \State \Call{Error}{'Invalid sequence number'} \EndIf - \State $hmac_{p_g} \gets \Call{ValidateHmacChain}{Dat_g,s_g,hmac_{p_g},sl_{last}}$ - -% \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_g)$ -% \If {$ \neg(s_g = 0 \land hmac_{p_g} = 0) \land hmac_{p_{stored}} \neq hmac_{p_g}$} -% \State \Call{Error}{'Invalid previous HMAC value'} -% \EndIf -% \If{$Hmac(Dat_g,SK) \neq GetCurrHmac(Dat_g)$ } -% \State \Call{Error}{'Invalid current HMAC value'} -% \EndIf -% \State $hmac_{p_g} \gets Hmac(Dat_g,SK)$\Comment{Update $hmac_{p_g}$ for next check} - - \State $DE_g \gets GetDatEnt(Dat_g)$ - \State $qs_g \gets \Call{GetQueSta}{DE_g}$\Comment{Handle qs} - \If{$qs_g \neq \emptyset \land qs_g > max_g$} - \State $max_g \gets qs_g$ - \EndIf - %Check for last s in Dat + \State $hmac_{p_g} \gets \Call{ValidHmacChain}{Dat_g,s_g,hmac_{p_g},sl_{last}}$ + \State $sz \gets \Call{UpdateExpSize}{sz}$ + \State $max_g \gets \Call{UpdateQS}{Dat_g,max_g}$\Comment{Handle qs} \State $MS_g \gets \Call{UpdateLastSeqN}{id_g,s_g,MS_g}$\Comment{Handle last s} - %Check for last s in DE in Dat - \State $DE_{g_{ss}} \gets \Call{GetSlotSeq}{DE_g}$\Comment{Handle ss} - \If{$DE_{g_{ss}} \neq \emptyset$} - \ForAll{$de_{g_{ss}} \in DE_{g_{ss}}$} - \State $\tuple{id_d,s_{d_{last}}} \gets GetSS(de_{g_{ss}})$ - \State $MS_g \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_g}$ - \State $SS_{live} \gets \Call{AddSSLivEnt}{SS_{live},de_{g_{ss}}}$ - \EndFor - \EndIf - \State $DE_{g_{cr}} \gets \Call{GetColRes}{DE_g}$\Comment{Handle cr} - \If{$DE_{g_{cr}} \neq \emptyset$} - \ForAll{$de_{g_{cr}} \in DE_{g_{cr}}$} - \State $cr_g \gets GetCR(de_{g_{cr}})$ - \State $\Call{CheckCollision}{MS,SM,cr_g}$ - \State $CR_{live} \gets \Call{AddCRLivEnt}{CR_{live},cr_g}$ - \EndFor - \EndIf + \State $MS_g \gets \Call{UpdateSS}{DE_g,MS_g}$\Comment{Handle ss} + %\State $DE_{g_{ss}} \gets \Call{GetSlotSeq}{DE_g}$\Comment{Handle ss} + %\If{$DE_{g_{ss}} \neq \emptyset$} + % \ForAll{$de_{g_{ss}} \in DE_{g_{ss}}$} + % \State $\tuple{id_d,s_{d_{last}}} \gets GetSS(de_{g_{ss}})$ + % \State $MS_g \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_g}$ + % \State $SS_{live} \gets \Call{AddSSLivEnt}{SS_{live},de_{g_{ss}}}$ + % \EndFor + %\EndIf + \State $\Call{UpdateCR}{DE_g}$\Comment{Handle cr} + %\State $DE_{g_{cr}} \gets \Call{GetColRes}{DE_g}$\Comment{Handle cr} + %\If{$DE_{g_{cr}} \neq \emptyset$} + % \ForAll{$de_{g_{cr}} \in DE_{g_{cr}}$} + % \State $cr_g \gets GetCR(de_{g_{cr}})$ + % \State $\Call{CheckCollision}{MS,SM,cr_g}$ + % \State $CR_{live} \gets \Call{AddCRLivEnt}{CR_{live},cr_g}$ + % \EndFor + %\EndIf \State $sl_{last} \gets \Call{StoreLastSlot}{MS,sl_{last},s_g,sv_g,id_g}$ \State $DT \gets \Call{UpdateDT}{DT,DE_g,LV,s_g}$ \EndFor -\If{$m + |SL_g| \leq max_g$}\Comment{Check actual size against $max_g$} - \State $m \gets m + |SL_g|$ -\Else - \State \Call{Error}{'Actual $SL$ size on server exceeds $max_g$'} -\EndIf \State $\Call{CheckLastSeqN}{MS_g,MS,d}$ -\State $\Call{CheckSlotsRange}{|SL_g|}$ +\State $\Call{CheckNumSlots}{|SL_g|,sz}$ \State $\Call{UpdateSSLivEnt}{SS_{live},MS}$ \State $\Call{UpdateCRLivEnt}{CR_{live},MS}$ \State $\Call{UpdateSM}{SM,CR_{live}}$ @@ -593,6 +626,7 @@ $\Call{PutDataEntries}{}$} \\ \textit{$id_{self}$ = machine Id of this client} \\ \textit{$sl_{last}$ = info of last slot in queue = $\tuple{s_{last},sv_{last},id_{last}}$ (initially $\emptyset$)} \\ +\textit{$sz$ = expected size of received slots from server} \\ \textit{$th_p$ = threshold number of dead slots for a resize to happen} \\ \textit{$m'_p$ = offset added to $max$ for resize} \\ \textit{$reinsert_{qs}$ = boolean to decide $qs$($max_g$) reinsertion} \\ -- 2.34.1