X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=doc%2Fiotcloud.tex;h=4d0c9f491dbc12085ed551a060fe60188663992b;hb=f498aec54ac8672e6b7c5d813f6487b4a57ed5a6;hp=022895726f89f57eb0bd1cad72e71427932e02f2;hpb=d898d09f3fcb23f725628348e7c60f1b7ab33d35;p=iotcloud.git diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex index 0228957..4d0c9f4 100644 --- a/doc/iotcloud.tex +++ b/doc/iotcloud.tex @@ -147,8 +147,8 @@ $MaxSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\ $MinSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\ -$SeqN(\tuple{s, sv})=s$ \\ -$SlotVal(\tuple{s, sv})=sv$ \\ +$SeqN(slot_s = \tuple{s, sv})=s$ \\ +$SlotVal(slot_s = \tuple{s, sv})=sv$ \\ \begin{algorithmic}[1] \Function{GetSlot}{$s_g$} @@ -162,7 +162,7 @@ $SlotVal(\tuple{s, sv})=sv$ \\ \State $max \gets max'$ \EndIf \State $\tuple{s_n,sv_n} \gets MaxSlot(SL)$\Comment{Last sv} -\State $s_n \gets SeqN(\tuple{s_n,sv_n})$ +%\State $s_n \gets SeqN(\tuple{s_n,sv_n})$ \If{$(s_p = s_n + 1)$} \If{$n = max$} \State $\tuple{s_m,sv_m} \gets MinSlot(SL)$\Comment{First sv} @@ -197,9 +197,10 @@ $id$ is a machine ID\\ $hmac_p$ is the HMAC value of the previous slot \\ $hmac_c$ is the HMAC value of the current slot \\ $Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\ -$sv_s = \tuple{s, E(Dat_s)} = +$slot_s = \tuple{s, E(Dat_s)} = \tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\ \textbf{States} \\ +\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$)} \\ @@ -215,18 +216,19 @@ $sv_s = \tuple{s, E(Dat_s)} = \textit{$MS_g$ = set MS to save all $\tuple{id, s_{last}}$ pairs while traversing DT after a request to server (initially empty)} \\ \textit{SK = Secret Key} \\ -\textit{$SM$ = associative array of $\tuple{s, id}$ of all slots in a previous read +\textit{$SM$ = associative array of $\tuple{s, id}$ of all slots in previous reads (initially empty)} \\ \\ \textbf{Helper Functions} \\ $MaxSlot(SL_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv} -\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\ + \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\ $MinSlot(SL_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv} -\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\ + \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\ $Slot(SL_s,s_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv} -\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s = s_s$ \\ + \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s = s_s$ \\ $SeqN(\tuple{s, sv})=s$ \\ $SlotVal(\tuple{s, sv})=sv$ \\ $CreateLastSL(s,sv,id)=\tuple{s,sv,id}=sl_{last}$ \\ +$CreateEntLV(kv_s,s_s)=\tuple{kv_s,s_s}$ \\ $Decrypt(SK_s,sv_s)=Dat_s=\tuple{s,id,hmac_p,DE,hmac_c}$ \\ $GetSeqN(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=s$ \\ $GetMacId(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=id$ \\ @@ -234,25 +236,31 @@ $GetPrevHmac(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=hmac_p$ \\ $GetCurrHmac(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=hmac_c$ \\ $GetDatEnt(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=DE$ \\ $GetLiveSS(SS_{live},ss_s)= ss$ \textit{such that} $ss \in SS_{live} -\wedge \forall ss_s \in SS_{live}, ss = ss_s$ \\ + \wedge \forall ss_s \in SS_{live}, ss = ss_s$ \\ $GetLiveCR(CR_{live},cr_s)= cr$ \textit{such that} $cr \in CR_{live} -\wedge \forall cr_s \in CR_{live}, cr = cr_s$ \\ -$GetLivEntLastS(LV_s,de_s)= s$ \textit{such that} $\tuple{de, s} \in LV_s -\wedge \forall \tuple{de_s, s_s} \in LV_s, de_s = de$ \\ + \wedge \forall cr_s \in CR_{live}, cr = cr_s$ \\ +$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($collision-resolution data entry$)=\tuple{s_s,id_s} = cr_s$ \\ -$GetS(\tuple{s, id})=s$ \\ -$GetId(\tuple{s, id})=id$ \\ -$GetKey(\tuple{k, v})=k$ \\ -$GetVal(\tuple{k, v})=v$ \\ +$GetKey(kv = \tuple{k, v})=k$ \\ +$GetVal(kv = \tuple{k, v})=v$ \\ +$GetId(ss = \tuple{id, s_{last}})=id$ \\ +$GetSLast(ss = \tuple{id, s_{last}})=s_{last}$ \\ +$GetS(cr = \tuple{s, id})=s$ \\ +$GetId(cr = \tuple{s, id})=id$ \\ $GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} -\in DT_s \wedge \forall \tuple{k_s, v_s} \in DT_s, k = k_s$ \\ + \in DT_s \wedge \forall \tuple{k_s, v_s} \in DT_s, k = k_s$ \\ $MaxLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s -\wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \geq s_{s_{last}}$ \\ + \wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \geq s_{s_{last}}$ \\ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s -\wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \leq s_{s_{last}}$ \\ + \wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \leq s_{s_{last}}$ \\ +$MinCRSeqN(CR_s)= s$ \textit{such that} $\tuple{s, id} \in CR_s + \wedge \forall \tuple{s_s, id_s} \in CR_s, s \leq s_s$ \\ +$MaxSMSeqN(SM_s)= s$ \textit{such that} $\tuple{s, id} \in SM_s + \wedge \forall \tuple{s_s, id_s} \in SM_s, s \geq s_s$ \\ \begin{algorithmic}[1] \Procedure{Error}{$msg$} @@ -261,27 +269,10 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \EndProcedure \end{algorithmic} -\begin{algorithmic}[1] -\Function{ValidHmac}{$DE_s,SK_s,hmac_{stored}$} -\State $hmac_{computed} \gets Hmac(DE_s,SK_s)$ -\State \Return {$hmac_{stored} = hmac_{computed}$} -\EndFunction -\end{algorithmic} - -\begin{algorithmic}[1] -\Function{ValidPrevHmac}{$s_s,DE_s,hmac_{p_s},hmac_{p_{sto}}$} -\If{$s_s = 0 \land hmac_{p_s} = \emptyset$}\Comment{First slot - no previous HMAC} - \State \Return $true$ -\Else - \State \Return {$hmac_{p_{sto}} = hmac_{p_s}$} -\EndIf -\EndFunction -\end{algorithmic} - \begin{algorithmic}[1] \Function{GetQueSta}{$DE_s$} -\State $de_{qs} \gets de_s$ \textit{such that} $de_s \in DE_s, - de_s \in D \land de_s = qs$ +\State $de_{qs} \gets ss$ \textit{such that} $ss \in DE_s, + de_s \in D \land type(de_s) = "qs"$ \If{$de_{qs} \neq \emptyset$} \State $qs_{ret} \gets GetQS(de_{qs})$ \Else @@ -293,14 +284,14 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \begin{algorithmic}[1] \Function{GetSlotSeq}{$DE_s$} -\State $DE_{ss} \gets \{de_s | de_s \in DE_s, de_s \in D \land de_s = ss\}$ +\State $DE_{ss} \gets \{de | de \in DE_s \land type(de) = "ss"\}$ \State \Return{$DE_{ss}$} \EndFunction \end{algorithmic} \begin{algorithmic}[1] \Function{GetColRes}{$DE_s$} -\State $DE_{cr} \gets \{de_s | de_s \in DE_s, de_s \in D \land de_s = cr\}$ +\State $DE_{cr} \gets \{de | de \in DE_s \land type(de) = "cr"\}$ \State \Return{$DE_{cr}$} \EndFunction \end{algorithmic} @@ -318,14 +309,14 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \end{algorithmic} \begin{algorithmic}[1] -\Function{UpdateKVLivEnt}{$LV_s,de_s,s_s$} -\State $s_t \gets GetLivEntLastS(LV_s,de_s)$ +\Function{UpdateKVLivEnt}{$LV_s,kv_s,s_s$} +\State $s_t \gets GetLivEntLastS(LV_s,kv_s)$ \If{$s_t = \emptyset$} - \State $LV_s \gets LV_s \cup \{\tuple{de_s,s_s}\}$\Comment{First occurrence} + \State $LV_s \gets LV_s \cup \{\tuple{kv_s,s_s}\}$\Comment{First occurrence} \Else \If{$s_s > s_t$}\Comment{Update entry with a later s} - \State $LV_s \gets (LV_s - \{\tuple{de_s,s_t}\}) \cup - \{\tuple{de_s,s_s}\}$ + \State $LV_s \gets (LV_s - \{\tuple{kv_s,s_t}\}) \cup + \{\tuple{kv_s,s_s}\}$ \EndIf \EndIf \State \Return{$LV_s$} @@ -344,8 +335,7 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \end{algorithmic} \begin{algorithmic}[1] -\Function{AddCRLivEnt}{$CR_{s_{live}},de_s$} -\State $cr_s \gets GetCR(de_s)$ +\Function{AddCRLivEnt}{$CR_{s_{live}},cr_s$} \State $cr_t \gets GetLiveCR(CR_{s_{live}},cr_s)$ \If{$cr_t = \emptyset$} \State $CR_{s_{live}} \gets CR_{s_{live}} \cup \{cr_s\}$\Comment{First occurrence} @@ -358,9 +348,9 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \Function{UpdateSSLivEnt}{$SS_{s_{live}},MS_s$} \State $s_{s_{min}} \gets MinLastSeqN(MS_s)$ \ForAll{$ss_s \in SS_{s_{live}}$} - \State $\tuple{id_s,s_{s_{last}}} \gets GetSS(ss_s)$ + \State $s_{s_{last}} \gets GetSLast(ss_s)$ \If{$s_{s_{min}} > s_{s_{last}}$}\Comment{Remove if dead} - \State $SS_{s_{live}} \gets SS_{s_{live}} - \{\tuple{id_s,s_{s_{last}}}\}$ + \State $SS_{s_{live}} \gets SS_{s_{live}} - \{ss_s\}$ \EndIf \EndFor \State \Return{$SS_{s_{live}}$} @@ -371,9 +361,9 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \Function{UpdateCRLivEnt}{$CR_{s_{live}},MS_s$} \State $s_{s_{min}} \gets MinLastSeqN(MS_s)$ \ForAll{$cr_s \in CR_{s_{live}}$} - \State $\tuple{s_s,id_s} \gets GetCR(cr_s)$ + \State $s_s \gets GetS(cr_s)$ \If{$s_{s_{min}} > s_s$}\Comment{Remove if dead} - \State $SS_{s_{live}} \gets SS_{s_{live}} - \{\tuple{s_s,id_s}\}$ + \State $CR_{s_{live}} \gets CR_{s_{live}} - \{cr_s\}$ \EndIf \EndFor \State \Return{$CR_{s_{live}}$} @@ -381,13 +371,22 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \end{algorithmic} \begin{algorithmic}[1] -\Procedure{CheckLastSeqN}{$MS_s,MS_t$}\Comment{Check $MS_t$ based on the newer $MS_s$} -\For {$\tuple{id, s_t}$ in $MS_t$} +\Function{UpdateSM}{$SM_s,CR_s$}\Comment{Remove if dead} +\State $s_{cr_{min}} \gets MinCRSeqN(CR_s)$ + \State $SM_s \gets SM_s - \{\tuple{s_s,id_s} \mid \tuple{s_s,id_s} + \in SM_s \wedge s_s < s_{cr_{min}}\}$ +\State \Return{$CR_{s_{live}}$} +\EndFunction +\end{algorithmic} + +\begin{algorithmic}[1] +\Procedure{CheckLastSeqN}{$MS_s,MS_t,d$} +\For {$\tuple{id, s_t}$ in $MS_t$}\Comment{Check $MS_t$ based on the newer $MS_s$} \State $s_s \gets MS_s[id]$ - \If{$s_s = \emptyset$} - \Call{Error}{'No $s$ for machine $id$'} + \If{$d \land s_s = \emptyset$} + \State \Call{Error}{'Missing $s$ for machine $id$'} \ElsIf{$id = id_{self}$ and $s_s \neq s_t$} - \State \Call{Error}{'Invalid last $s$ for this machine'} + \State \Call{Error}{'Invalid last $s$ for this machine'} \ElsIf{$id \neq id_{self}$ and $s_{s_{last}} < s_{t_{last}}$} \State \Call{Error}{'Invalid last $s$ for machine $id$'} \Else @@ -398,23 +397,42 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \end{algorithmic} \begin{algorithmic}[1] -\Procedure{CheckCollision}{$MS_s,SM_s,\tuple{s_s,id_s}$} -\If{$\tuple{s_s,id_s} \neq \emptyset$} - \State $s_s \gets GetS(\tuple{s_s,id_s})$ - \State $id_s \gets GetId(\tuple{s_s,id_s})$ +\Procedure{CheckCollision}{$MS_s,SM_s,cr_s$} +\If{$cr_s \neq \emptyset$} + \State $s_s \gets GetS(cr_s)$ + \State $id_s \gets GetId(cr_s)$ \State $s_{s_{last}} \gets GetLastSeqN(MS_s,id_s)$ \If{$s_{s_{last}} < s_s$} - \State $\Call{CheckColRes}{SM_s,\tuple{s_s,id_s}}$ + \State $id_t \gets SM_s[s_s]$ + \If{$id_s \neq id_t$} + \State \Call{Error}{'Invalid $id$ for this slot update'} + \EndIf \EndIf \EndIf \EndProcedure \end{algorithmic} \begin{algorithmic}[1] -\Procedure{CheckColRes}{$SM_s,\tuple{s_t,id_t}$}\Comment{Check $id_s$ in $SM_s$} -\State $id_s \gets SM_s[s_t]$ -\If{$id_s \neq id_t$} - \State \Call{Error}{'Invalid $id_s$ for this slot update'} +\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 +\State $s_{s_{last}} \gets MaxSMSeqN(SM)$ +\If{$s_{s_{min}} \leq s_{s_{last}}$} + \State \Call{Error}{'Server sent old slots'} +\EndIf +\State \Return{$s_{s_{min}} > s_{s_{last}} + 1$} +\EndFunction +\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}$} + \State \Call{Error}{'Actual number of slots does not match expected'} \EndIf \EndProcedure \end{algorithmic} @@ -431,18 +449,18 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_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, type(de_s) = "kv"\}$ \ForAll{$de_s \in DE_s$} - \State $LV_s \gets \Call{UpdateKVLivEnt}{LV_s,de_s,s_s}$ - \If{$de_s$ \textit{such that} $de_s \in D \land de_s = kv$} - \State $\tuple{k_s,v_s} \gets GetKV(de_s)$ - \State $\tuple{k_s,v_t} \gets GetKeyVal(DT_s,k_s)$ - \If{$\tuple{k_s,v_t} = \emptyset$} - \State $DT_s \gets DT_s \cup \{\tuple{k_s,v_s}\}$ - \Else - \State $DT_s \gets (DT_s - \{\tuple{k_s,v_t}\}) \cup + \State $kv_s \gets GetKV(de_s)$ + \State $LV_s \gets \Call{UpdateKVLivEnt}{LV_s,kv_s,s_s}$ + \State $k_s \gets GetKey(kv_s)$ + \State $\tuple{k_s,v_t} \gets GetKeyVal(DT_s,k_s)$ + \If{$\tuple{k_s,v_t} = \emptyset$} + \State $DT_s \gets DT_s \cup \{\tuple{k_s,v_s}\}$ + \Else + \State $DT_s \gets (DT_s - \{\tuple{k_s,v_t}\}) \cup \{\tuple{k_s,v_s}\}$ - \EndIf - \EndIf + \EndIf \EndFor \State \Return{$DT_s$} \EndFunction @@ -451,25 +469,25 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \begin{algorithmic}[1] \Procedure{ProcessSL}{$SL_g$} \State $MS_g \gets \emptyset$ -\State $SM_{curr} \gets \emptyset$ -\State $\tuple{s_{g_{max}},sv_{g_{max}}} \gets MaxSlot(SL_g)$ \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}}}$ \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)$ - \State $SM_{curr} \gets SM_{curr} \cup \{\tuple{s_g,sv_g}\}$ \State $Dat_g \gets Decrypt(SK,sv_g)$ + \State $id_g \gets GetMacId(Dat_g)$ + \State $SM \gets SM \cup \{\tuple{s_g,id_g}\}$ \State $s_{g_{in}} \gets GetSeqN(Dat_g)$ \If{$s_g \neq s_{g_{in}}$} \State \Call{Error}{'Invalid sequence number'} \EndIf \State $DE_g \gets GetDatEnt(Dat_g)$ \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_g)$ - \If{$\neg \Call{ValidPrevHmac}{s_g,DE_g,hmac_{p_g},hmac_{p_{stored}}}$} - \State \Call{ReportError}{'Invalid previous HMAC value'} + \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 - \State $hmac_{c_g} \gets GetCurrHmac(Dat_g)$ - \If{$\neg \Call{ValidHmac}{DE_g,SK,hmac_{c_g}}$} + \If{$\Call{Hmac}{DE_g,SK} \neq GetCurrHmac(Dat_g)$ } \State \Call{Error}{'Invalid current HMAC value'} \EndIf \State $hmac_{p_g} \gets Hmac(DE_g,SK)$\Comment{Update $hmac_{p_g}$ for next check} @@ -492,23 +510,24 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \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 $\tuple{s_e,id_e} \gets GetCR(de_{g_{cr}})$ - \State $\Call{CheckCollision}{MS,SM,\tuple{s_e,id_e}}$ - \State $CR_{live} \gets \Call{AddCRLivEnt}{SS_{live},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 -\State $SM \gets SM_{curr}$ \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 queue size exceeds $max_g$'} + \State \Call{Error}{'Actual $SL$ size on server exceeds $max_g$'} \EndIf -\State $\Call{CheckLastSeqN}{MS_g,MS}$ +\State $\Call{CheckLastSeqN}{MS_g,MS,d}$ +\State $\Call{CheckSlotsRange}{|SL_g|}$ \State $\Call{UpdateSSLivEnt}{SS_{live},MS}$ \State $\Call{UpdateCRLivEnt}{CR_{live},MS}$ +\State $\Call{UpdateSM}{SM,CR_{live}}$ \EndProcedure \end{algorithmic} @@ -521,7 +540,7 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \end{algorithmic} \begin{algorithmic}[1] -\Function{GetValFromKey}{$k_g$} +\Function{Get}{$k_g$} \Comment{Interface function to get a value} \State $\tuple{k_s,v_s} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \in DT \land k = k_g$ \State \Return{$v_s$} @@ -529,21 +548,8 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \end{algorithmic} \subsubsection{Writing Slots} -\textbf{Data Entry} \\ -$k$ is key of entry \\ -$v$ is value of entry \\ -$kv$ is a key-value entry $\tuple{k,v}$\\ -$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{$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 -collision in reinserting the last slot (sent in the following slot)} \\ \textit{$ck_p$ = counter of $kv \in KV$ for putting pairs (initially 0)} \\ \textit{$ck_g$ = counter of $kv \in KV$ for getting pairs (initially 0)} \\ \textit{$cs_p$ = counter of $ss \in SS$ for putting pairs (initially 0)} \\ @@ -580,8 +586,8 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \forall \tuple{ck_s,\tuple{k_s, v_s}} \in KV_s, k = k_s$ \\ \begin{algorithmic}[1] -\Function{PutKVPair}{$KV_s,\tuple{k_s,v_s}$} -\State $\tuple{ck_s,\tuple{k_s,v_t}} \gets GetKVPair(KV,k_s)$ +\Function{Put}{$KV_s,\tuple{k_s,v_s}$} \Comment{Interface function to update a key-value pair} +\State $\tuple{ck_s,\tuple{k_s,v_t}} \gets GetKVPair(KV_s,k_s)$ \If{$\tuple{ck_s,\tuple{k_s,v_t}} = \emptyset$} \State $KV_s \gets KV_s \cup \{\tuple{ck_p, \tuple{k_s,v_s}}\}$ \State $ck_p \gets ck_p + 1$ @@ -593,6 +599,22 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \EndFunction \end{algorithmic} +\begin{algorithmic}[1] +\Function{PutSSPair}{$SS_s,\tuple{id_s,s_{s_{last}}}$}\Comment{Insert a set of $ss$ entries} +\State $SS_s \gets SS_s \cup \{\tuple{cs_p, \tuple{id_s,s_{s_{last}}}}\}$ +\State $cs_p \gets cs_p + 1$ +\State \Return{$SS_s$} +\EndFunction +\end{algorithmic} + +\begin{algorithmic}[1] +\Function{PutCRPair}{$CR_s,\tuple{s_s,id_s}$}\Comment{Insert a set of $cr$ entries} +\State $CR_s \gets CR_s \cup \{\tuple{cc_p, \tuple{s_s,id_s}}\}$ +\State $cc_p \gets cc_p + 1$ +\State \Return{$CR_s$} +\EndFunction +\end{algorithmic} + \begin{algorithmic}[1] \Function{CheckResize}{$MS_s,th_s,max_t,m'_s$} \State $s_{last_{min}} \gets MinLastSeqN(MS_s)$ @@ -609,7 +631,7 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \end{algorithmic} \begin{algorithmic}[1] -\Function{CheckNeedSS}{$MS_s,max_t$}\Comment{Check if $ss$ is needed} +\Function{CheckSLFull}{$MS_s,max_t$}\Comment{Check if $ss$ is needed} \State $s_{last_{min}} \gets MinLastSeqN(MS_s)$ \State $s_{last_{max}} \gets MaxLastSeqN(MS_s)$ \State $n_{live} \gets s_{last_{max}} - s_{last_{min}}$\Comment{Number of live slots} @@ -620,6 +642,9 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \begin{algorithmic}[1] \Function{HandleCollision}{$SL_s,s_s$} +\If{$SL_s = \emptyset$} + \State \Call{Error}{'No slots received from server'} +\EndIf \State $\tuple{s_{col},sv_{col}} \gets GetColSeqN(SL_s,s_s)$ \State $Dat_{col} \gets Decrypt(SK,sv_{col})$ \State $id_{col} \gets GetMacId(Dat_{col})$ @@ -696,49 +721,16 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \EndFunction \end{algorithmic} -%\begin{algorithmic}[1] -%\Function{AddSlotSeq}{$DE_s,SS_s,cp_s$}\Comment{Insert a $ss$} -%\State $DE_{ret} \gets DE_s \cup SS_s$ -%\State $cp_s \gets cp_s - |SS_s|$ -%\State \Return{$\tuple{DE_{ret},cp_s}$} -%\EndFunction -%\end{algorithmic} - -\begin{algorithmic}[1] -\Function{PutSSPair}{$SS_s,\tuple{id_s,s_{s_{last}}}$}\Comment{Insert a set of $ss$ entries} -\State $SS_s \gets SS_s \cup \{\tuple{cs_p, \tuple{id_s,s_{s_{last}}}}\}$ -\State $cs_p \gets cs_p + 1$ -\State \Return{$SS_s$} -\EndFunction -\end{algorithmic} - -\begin{algorithmic}[1] -\Function{PutCRPair}{$CR_s,\tuple{s_s,id_s}$}\Comment{Insert a set of $cr$ entries} -\State $CR_s \gets CR_s \cup \{\tuple{cc_p, \tuple{s_s,id_s}}\}$ -\State $cc_p \gets cc_p + 1$ -\State \Return{$CR_s$} -\EndFunction -\end{algorithmic} - \begin{algorithmic}[1] \Function{AddQueSta}{$DE_s,max'_s,cp_s$}\Comment{Insert a $qs$} \State $DE_{ret} \gets \emptyset$ \State $qs_s \gets max'_s$ -\State $DE_{ret} \gets DE_s \cup qs_s$ +\State $DE_{ret} \gets DE_s \cup \{qs_s\}$ \State $cp_s \gets cp_s - 1$ \State \Return{$\tuple{DE_{ret},cp_s}$} \EndFunction \end{algorithmic} -%\begin{algorithmic}[1] -%\Function{AddColRes}{$DE_s,CR_s,cp_s$}\Comment{Insert a $cr$} -%\State $DE_{ret} \gets \emptyset$ -%\State $DE_{ret} \gets DE_s \cup CR_s$ -%\State $cp_s \gets cp_s - |CR_s|$ -%\State \Return{$\tuple{DE_{ret},cp_s}$} -%\EndFunction -%\end{algorithmic} - \begin{algorithmic}[1] \Function{GetKVPairs}{$DE_s,KV_s,cp_s$} \State $DE_{ret} \gets \emptyset$ @@ -760,12 +752,13 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \If{$|SS_s| \leq cp_s$}\Comment{$SS$ set can span multiple slots} \State $DE_{ret} \gets DE_s \cup \{\tuple{id_s,s_{s_{last}}} \mid \tuple{cs_s,\tuple{id_s,s_{s_{last}}}} \in SS_s\}$ + \State $cp_s \gets cp_s - |SS_s|$ \Else \State $DE_{ret} \gets DE_s \cup \{\tuple{id_s,s_{s_{last}}} \mid \tuple{cs_s,\tuple{id_s,s_{s_{last}}}} \in SS_s, cs_g \leq cs_s < cs_g + cp_s\}$ + \State $cp_s \gets 0$ \EndIf -\State $cp_s \gets cp_s - |SS_s|$ \State \Return{$\tuple{DE_{ret},cp_s}$} \EndFunction \end{algorithmic} @@ -776,12 +769,13 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \If{$|CR_s| \leq cp_s$}\Comment{$CR$ set can span multiple slots} \State $DE_{ret} \gets DE_s \cup \{\tuple{s_s,id_s} \mid \tuple{cc_s,\tuple{s_s,id_s}} \in CR_s\}$ + \State $cp_s \gets cp_s - |CR_s|$ \Else \State $DE_{ret} \gets DE_s \cup \{\tuple{s_s,id_s} \mid \tuple{cc_s,\tuple{s_s,id_s}} \in CR_s, cc_g \leq cc_s < cc_g + cp_s\}$ + \State $cp_s \gets 0$ \EndIf -\State $cp_s \gets cp_s - |CR_s|$ \State \Return{$\tuple{DE_{ret},cp_s}$} \EndFunction \end{algorithmic} @@ -795,8 +789,9 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \State $s_p \gets MaxLastSeqN(MS)$ \State $cp_p \gets cp$ \State $max'_p \gets \Call{CheckResize}{MS,th_p,max_g,m'_p}$ - \If{$max'_p \neq \emptyset$} - \State $\tuple{DE_p,cp_p} \gets \Call{AddQueSta}{DE_p,max'_p,cp_p}$\Comment{Add qs} + \If{$max'_p \neq \emptyset$}\Comment{Add a qs entry} + \State $\tuple{DE_p,cp_p} \gets \Call{AddQueSta}{DE_p,max'_p,cp_p}$ + \State $reinsert_{qs} \gets false$ \Else\Comment{Check if there is $qs$ reinsertion} \If{$reinsert_{qs}$} \State $\tuple{DE_p,cp_p} \gets \Call{AddQueSta}{DE_p,max_g,cp_p}$ @@ -821,8 +816,9 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \State $CR \gets \Call{PutCRPair}{CR,\tuple{s_{p_{col}},id_{p_{col}}}}$ \EndIf \EndWhile -\If{$|DE_p| = cp$}\Comment{Middle of set} - \State $ck_g \gets ck_g + cp_s$ +\State $MS \gets \Call{UpdateLastSeqN}{id_{self},s_p,MS}$ +\If{$|DE_p| = cp$}\Comment{Update set counters} + \State $ck_g \gets ck_g + cp_p$\Comment{Middle of set} \State $cs_g \gets cs_g + |SS|$ \State $cc_g \gets cc_g + |CR|$ \Else\Comment{End of set} @@ -830,10 +826,9 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge \State $cs_g \gets 0$ \State $cc_g \gets 0$ \EndIf -\State $MS \gets \Call{UpdateLastSeqN}{id_{self},s_p,MS}$ -\State $need_p \gets \Call{CheckNeedSS}{MS,max_g}$ -\If{$need_p$} - \State $\Call{CheckLastSlot}{sl_{last}}$\Comment{Get ready to expunge first slot} +\State $need_p \gets \Call{CheckSLFull}{MS,max_g}$ +\If{$need_p$}\Comment{SL on server is full} + \State $\Call{CheckLastSlot}{sl_{last}}$\Comment{Salvage entries from expunged slot} \State $ss_p \gets \Call{CreateSlotSeq}{sl_{last}}$ \State $\tuple{id_p,s_{p_{last}}} \gets GetSS(ss_p)$ \State $SS \gets \Call{PutSSPair}{SS,\tuple{id_p,s_{p_{last}}}}$\Comment{Add ss} @@ -848,85 +843,311 @@ $\tuple{ck,\tuple{k, v}} \in KV_s \wedge %\note{Also Missing liveness state definition in algorithm...} -\subsection{Definitions for Formal Guarantees} - -\begin{enumerate} -\item Equality: Two messages $t$ and $u$ are equal if their sequence numbers, senders, and contents are exactly the same. -\item Message: A message $t$, is the tuple $t = (i(t), s(t), contents(t))$ containing the sequence number, machine ID of the sender, and contents of $t$ respectively. -\item Parent: A parent of a message $t$ is the message $A(t)$, unique by the correctness of HMACs, such that $HMAC_C(t) = HMAC_P(A(t))$. -\item Partial message sequence: A partial message sequence is a sequence of messages, no two with the same sequence number, that can be divided into disjoint chains, where a chain of messages with length $n \ge 1$ is a message sequence $(t_i, t_{i+1}, ..., t_{i+n-1})$ such that for every index $i < k \le i+n-1$, $t_k$ has sequence number $k$ and is the parent of $t_{k-1}$. -\item Total message sequence: A total message sequence $T$ with length $n$ is a chain of messages that starts at $i = 1$. -\item Path: The path of a message $t$ is the total message sequence whose last message is $t$. -\item Consistency: A partial message sequence $P$ is consistent with a total message sequence $T$ of length $n$ if for every message $p \in P$ with $i(p) < n$, $T_{i(p)} = p$. This implies that $\{p \in P | i(p) \le n\}$ is a subsequence of T. -\item Transitive closure set at index $n$: A set $\mathscr{S}$ of clients comprising a connected component of an undirected graph, where two clients are connected by an edge if they both received the same message $t$ with index $i(t) > n$. - -\end{enumerate} - -\subsection{Formal Guarantee} - -\begin{prop} Every client $J$ who sends a message $t$ has $A(t)$ as its latest stored message, and $i(t) = i(A(t)) + 1$. \end{prop} -\begin{proof} True by definition, because $J$ sets $HMAC_P(t) = HMAC_C(A(t))$ and $i(t) = i(A(t)) + 1$ when a message is sent. \end{proof} +\subsection{Formal Guarantees} +\subsubsection{Definitions} + +\begin{defn}[Message] +A message $\mathsf{t}$, is the tuple +\begin{center} +$\mathsf{t = \tuple{s, E(Dat_s)}}$ \\ +$\mathsf{Dat_t = \tuple{s,id,hmac_p, DE,hmac_c}}$ +\end{center} +containing $\mathsf{s}$ as sequence number and $\mathsf{Dat_t}$ as its +encrypted contents. $\mathsf{Dat_t}$ consists of $\mathsf{s}$, +$\mathsf{id}$ as machine ID of the sender, $\mathsf{hmac_p}$ as HMAC +from a previous message, $\mathsf{DE}$ as set of data entries, and +$\mathsf{hmac_c}$ as HMAC from message $\mathsf{t}$ respectively. +\end{defn} + +\begin{defn}[Equality] +Two messages $\mathsf{t}$ and $\mathsf{u}$ are equal if their $\mathsf{s}$, +and $\mathsf{Dat_t}$ are exactly the same. +\end{defn} + +\begin{defn}[Parent] +A parent of a message $\mathsf{t}$ is the message $\mathsf{p_t}$, +unique by the correctness of HMACs in $\mathsf{Dat_t}$, such that +$\mathsf{hmac_p(t) = hmac_c(p_t)}$. +\end{defn} + +\begin{defn}[Chain] +A chain of messages with length $\mathsf{n \ge 1}$ is a message sequence +$\mathsf{R = (r_s, r_{s+1}, ..., r_{s+n-1})}$ such that for every sequence +number $\mathsf{s < k \le s+n-1}$, $\mathsf{r_k}$ has sequence number +$\mathsf{k}$ and is the parent of $\mathsf{r_{k-1}}$. +\end{defn} + +\begin{defn}[Partial sequence] +A partial sequence $\mathsf{P}$ is a sequence of messages, no two +with the same sequence number, that can be divided into disjoint chains. +\end{defn} + +\begin{defn}[Total sequence] +A total sequence $\mathsf{T =}$ $\mathsf{(t_1, t_2, ..., t_n)}$ with +length $\mathsf{n}$ is a chain of messages that starts at $\mathsf{s = 1}$. +\end{defn} + +\begin{defn}[Path] +The path of a message $\mathsf{t}$ is the chain that starts at $\mathsf{s = 1}$ +and whose last message is $\mathsf{t}$. The uniqueness of a path follows +from the uniqueness of a parent. +\end{defn} + +\begin{defn}[Consistency] +A partial sequence $\mathsf{P}$ is consistent with a total sequence +$\mathsf{T}$ of length $\mathsf{n}$ if for every message $\mathsf{p \in P}$ +with $\mathsf{s_p \leq n}$, $\mathsf{t_{s_p} = p}$. This implies that +$\mathsf{\{p \in P | s_p \le n\}}$ is a partial sequence of $\mathsf{T}$. +\end{defn} + +\begin{defn}[Transitive closure] +Transitive closure set at sequence number $\mathsf{s_n}$ is a set +$\mathsf{\mathscr{S}}$ of clients comprising a connected component of an +undirected graph, where two clients are connected by an edge if they both +received the same message $\mathsf{t}$ with sequence number $\mathsf{s_t > s_n}$. +\end{defn} + +\subsubsection{Lemmas and Proofs} + +\begin{prop} +\label{prop:parentmessage} +Every client $\mathsf{J}$ who sends a message $\mathsf{t}$ +has parent $\mathsf{p_t}$ as its latest stored message, and +$\mathsf{s_t = s_{p_t} + 1}$. +\end{prop} +\begin{proof} True by definition, because $J$ sets +$\mathsf{hmac_p(t) = hmac_c(p_t)}$ and +$\mathsf{s_t = }$ $\mathsf{s_{p_t + 1}}$ when a message +is sent. +\end{proof} -\begin{prop} If a rejected message entry is added to the RML at index $i$, the message will remain in the RML until every client has seen it. \end{prop} -\begin{proof} Every RML entry $e$ remains in the queue until it reaches the tail, and is refreshed by the next sender $J$ at that time if $min(MS) > i(e)$; that is, until every client has sent a message with sequence number greater than $i(e)$. Because every client who sends a message with index $i$ has the state of the queue at $i - 1$, this client will have seen the message at $i(e)$. \end{proof} +\begin{prop} +\label{prop:rejectedmessage} +If a rejected message entry is added to the set $\mathsf{CR}$ +at sequence number $\mathsf{s}$, the message will remain in $\mathsf{CR}$ +until every client has seen it. +\end{prop} +\begin{proof} Every $\mathsf{CR}$ entry $\mathsf{cr}$ remains in the queue until it +reaches the tail, and is refreshed by the next sender $\mathsf{J}$ at that time if +$\mathsf{min(MS) > s_{cr}}$; that is, until every client has sent a message with +sequence number greater than $\mathsf{s_{cr}}$. Because every client who sends a +message with sequence number $\mathsf{s}$ has the state of the set $\mathsf{SL}$ at +$\mathsf{s - 1}$, this client will have seen the message at $\mathsf{s_{cr}}$. +\end{proof} \begin{figure}[h] \centering - \xymatrix{ & & S \\ -\dots \ar[r] & q \ar[dr]_{J} \ar[r]^{K} & S_1 \ar[r] & S_2 \ar[r] & \dots \ar[r] & p \ar[r] & \dots \ar[r] & S_n = u \\ -& & R_1 \ar[r] & R_2 \ar[r] & \dots \ar[r] & R_m = t \\ + \xymatrix{ & & L \\ +\dots \ar[r] & q \ar[dr]_{J} \ar[r]^{K} & l_1 \ar[r] & l_2 \ar[r] & \dots \ar[r] & m \ar[r] & \dots \ar[r] & l_n = u \\ +& & r_1 \ar[r] & r_2 \ar[r] & \dots \ar[r] & r_m = t \\ & & R \save "2,3"."2,8"*+\frm{^\}} \save "3,3"."3,6"*+\frm{_\}} \restore \restore } -\caption{By Lemma 1, receiving $u$ after $t$ is impossible.} +\caption{By \textbf{Lemma \ref{lem:twomessages}}, receiving both $t$ and $u$ here is impossible.} \end{figure} -\begin{lem} Two packets are received without errors by a client $C$; call them $t$ and $u$ such that $i(t) \le i(u)$. Then $t$ is in the path of $u$. \end{lem} +\begin{lem} +\label{lem:twomessages} +Two messages are received without errors by a client $\mathsf{C}$; +call them $\mathsf{t}$ and $\mathsf{u}$ such that $\mathsf{s_t \le s_u}$. +Then $\mathsf{t}$ is in the path of $\mathsf{u}$. +\end{lem} \begin{proof} -Clearly $C$ will throw an error if $i(t) = i(u)$. So $i(t) < i(u)$. Additionally, if $C$ receives $u$ before $t$, this will cause it to throw an error, so $t$ is received before $u$. +Assume that there are some pairs of messages $\mathsf{(t,u)}$ that violate this lemma. +Take a specific $\mathsf{(t,u)}$ such that $\mathsf{s_u}$ is minimized, and +$\mathsf{s_t}$ is maximized for this choice of $\mathsf{s_u}$. We will show that $\mathsf{C}$ +cannot receive both $\mathsf{t}$ and $\mathsf{u}$ without throwing an error. + +Clearly $\mathsf{C}$ will throw an error if $\mathsf{s_t = s_u}$. So +$\mathsf{s_t < s_u}$. Additionally, if $\mathsf{C}$ receives $\mathsf{u}$ before +$\mathsf{t}$, this will cause it to throw an error, so $\mathsf{t}$ is received +before $\mathsf{u}$. We will prove that an error occurs upon receipt of $\mathsf{u}$. + +Let $\mathsf{r_1}$ be the earliest member of the path of $\mathsf{t}$ that is +not in the path of $\mathsf{u}$, and $\mathsf{q}$ be its parent. Message +$\mathsf{q}$, the last common ancestor of $\mathsf{t}$ and $\mathsf{u}$, must exist, +since all clients and the server were initialized with the same state. Let +$\mathsf{l_1}$ be the successor of $\mathsf{q}$ that is in the path of $\mathsf{u}$; +we know $\mathsf{l_1 \neq r_1}$. Let $\mathsf{R = (r_1, r_2, \dots, r_{|R|} = t)}$ be +the distinct portion of the path of $\mathsf{t}$, and similarly let $\mathsf{L}$ +be the distinct portion of the path of $\mathsf{l_{|L|} = u}$. + +Let $\mathsf{J}$ be the client who sent $\mathsf{r_1}$; that is, such that +$\mathsf{{id_{self}}_J = GetMacID(r_1)}$, and $\mathsf{K}$ be the client who +sent $\mathsf{l_1}$. Because no client can send two messages with the same sequence number, and +$\mathsf{s_{r_1} = s_{l_1} = s_q + 1}$, $\mathsf{J \neq K}$. + +We also know the following facts: + +\begin{prop} +\label{prop:bothmessages} +No client sends both a message in $\mathsf{(r_2,...,t)}$ and a message in $\mathsf{(l_2,...,u)}$. +\end{prop} -Assume that $t$ is not in the path of $u$. Take $u$ to be the packet of smallest index for which this occurs, and $t$ be the packet with largest index for this $u$. We will prove that an error occurs upon receipt of $u$. +\begin{proof} +To send a message $\mathsf{p}$ that is the parent of some other +message, one must have received the parent of $\mathsf{p}$. Since +$\mathsf{u}$ is the message with smallest sequence number received by any +client that violates Lemma \ref{lem:twomessages}, no client receives both a message +in $\mathsf{r}$ and a message in $\mathsf{l}$. +\end{proof} -Let $R_1$ be the earliest member of the path of $t$ that is not in the path of $u$, and $q$ be its parent. $q$, the last common ancestor of $t$ and $u$, must exist, since all clients and the server were initialized with the same state. Let $S_1$ be the successor of $q$ that is in the path of $u$; we know $S_1 \neq R_1$. Let $R = (R_1, R_2, \dots, R_m = t)$ be the distinct portion of the path of $t$, and similarly let $S$ be the distinct portion of the path of $S_n = u$. +\begin{prop} +\label{prop:seqnumb} +$\mathsf{C}$ does not receive any message with a +sequence number strictly between $\mathsf{s_t}$ and $\mathsf{s_u}$. +\end{prop} -Let $J = s(R_1)$, and $K = s(S_1)$. Because no client can send two messages with the same index, and $i(R_1) = i(S_1) = i(q) + 1$, we know that $J \neq K$. +\begin{proof} If there were such a message with sequence number smaller than +$\mathsf{s_u}$, it would contradict the assumption that $\mathsf{u}$ is the +message with the least sequence number that violates Lemma \ref{lem:twomessages}. +\end{proof} There are two cases: - \begin{itemize} -\item Case 1: $J$ did not send a message in $S$. Then $v_J(t) > v_J(q) = v_J(u)$. +\item Case 1: $\mathsf{J}$ did not send a message in $\mathsf{L}$. Then, where $\mathsf{s_{t_J}}$ +is the greatest sequence number of the messages that client $\mathsf{J}$ sent in +the path of message $\mathsf{t}$, $\mathsf{s_{t_J} > s_{q_J} = s_{u_J}}$. \begin{itemize} -\item Case 1.1: $C$ receives a sequence of messages between $t$ and $u$ with contiguous sequence numbers. In particular, there is some packet $w$ such that $i(w) = i(u) - 1$. If $w$ is the parent of $u$, messages $t$ and $w$ are a violation of this lemma such that $p$ has a smaller sequence number than $u$; but this contradicts our assumption that $u$ had the smallest sequence number. If $t$ is not the parent of $u$, $HMAC_p(u) \neq HMAC_c(t)$, causing $C$ to error. -\item Case 1.2: Case 1.1 does not occur; therefore, $C$ must update its slot sequence list at some point between receiving $t$ and $u$. The latest index of $J$ decreases during this time, which means it must decrease when some message is received, which means C throws an error in the $CheckLastSeqN$ subroutine. +\item Case 1.1: $\mathsf{C}$ never updates its slot sequence list $\mathsf{SS}$ +between receiving $\mathsf{t}$ and receiving $\mathsf{u}$; this can only happen if +$\mathsf{s_t = s_u - 1}$. Since $\mathsf{t}$ is not the parent of $\mathsf{u}$, +$\mathsf{hmac_p(u) \neq hmac_c(t)}$, causing $\mathsf{C}$ to throw an error. +\item Case 1.2: Case 1.1 does not occur; therefore, $\mathsf{C}$ must update +its slot sequence list $\mathsf{SS}$ at some point between receiving $\mathsf{t}$ +and $\mathsf{u}$. +The latest sequence number of $\mathsf{J}$ decreases during this time, which +means it must decrease when some message is received, which means $\mathsf{C}$ +throws an error in the $\mathsf{CheckLastSeqN()}$ subroutine. \end{itemize} -\item Case 2: $J$ sent at least one message in $S$. Call the first one $p$. We know that $i(p) > i(R_1)$, since $J \neq K$ and $p \neq S_1$. $R_1$ must be sent either before or after $p$. +\item Case 2: $\mathsf{J}$ sent at least one message in $\mathsf{L}$. Call the +first one $\mathsf{m}$. We know that $\mathsf{s_m > s_{r_1}}$, since +$\mathsf{J \neq K}$ and $\mathsf{m \neq l_1}$. Message $\mathsf{r_1}$ must be sent +either before or after $\mathsf{m}$. \begin{itemize} -\item Case 2.1: Client $J$ sends $p$, and then $R_1$. Before sending $p$, the greatest sequence number of a message that $J$ has received, ${s_{last}}_j$, must be equal to $i(p) - 1 \ge i(R_1)$. Since ${s_{last}}_j$ never decreases, Client $J$ cannot then send a message with sequence number $i(R_1)$, a contradiction. -\item Case 2.2: Client $J$ sends $R_1$, and then $p$. Let $X = (R_1, \dots )$ be the list of messages $J$ sends starting before $R_1$ and ending before $p$. +\item Case 2.1: Client $\mathsf{J}$ sends $\mathsf{m}$, and then $\mathsf{r_1}$. +Before sending $\mathsf{m}$, the greatest sequence number of a message that +$\mathsf{J}$ has received, $\mathsf{{s_{last}}_J}$, must be equal to +$\mathsf{s_m - 1 \ge s_{r_1}}$. Since $\mathsf{{s_{last}}_J}$ never decreases, +client $\mathsf{J}$ cannot then send a message with sequence number +$\mathsf{s_{r_1}}$, a contradiction. +\item Case 2.2: Client $\mathsf{J}$ sends $\mathsf{r_1}$, and then $\mathsf{m}$. +Let $\mathsf{X = (r_1 = x_1, \dots , x_n)}$ be the list of messages $\mathsf{J}$ sends +starting before $\mathsf{r_1}$ and ending before $m$; clearly these all have sequence +number $\mathsf{s_p = s_q + 1}$. \begin{itemize} -\item Case 2.2.1: Some message in $X$ was accepted. In this case, before sending $p$, $J$'s value for its own latest index would be strictly greater than $v_J(q)$. ($J$ could not have sent a message with index less than $i(q)$ after receiving $q$). When preparing to send $p$, $J$ would have received its own latest index as at most $v_J(q)$. $J$ throws an error before sending $p$, because its own latest index decreases. -\item Case 2.2.2: All messages in $X$ were rejected. Client $J$ will always add the latest rejected message to the rejected-message list in the next update; so for every $i$, $1 \leq i < |X|$, the $i$th element of $X$ will be recorded in the RML of all further elements of $X$; and every element of $X$ will be recorded in $RML(p)$. Since every rejected message in $RML(p)$ will be in $RML(C, u)$, and $u$ is the first message that $C$ sees which does not have $t$ in its path, $R_1$ will be recorded in $RML(C, p)$. When $C$ receives $u$, $C$ will throw an error from the match $(J, iq+1)$ in $RML(C, p)$. +\item Case 2.2.1: Some message in $\mathsf{X}$ was accepted. Before sending $\mathsf{m}$, +$\mathsf{J}$'s value in $\mathsf{MS_J}$ for its own latest sequence number would +be strictly greater than $\mathsf{s_{q_J}}$. If there is a sequence of messages with +contiguous sequence numbers that $\mathsf{J}$ receives between $\mathsf{r_1}$ and +$\mathsf{m}$, $\mathsf{J}$ throws an error for a similar reason as Case 1.1. Otherwise, +when preparing to send $\mathsf{m}$, $\mathsf{J}$ would have received an update of its +own latest sequence number as at most $\mathsf{s_{q_J}}$. $J$ throws an error before +sending $\mathsf{p}$, because its own latest sequence number decreases. +\item Case 2.2.2: All messages in $\mathsf{X}$ were rejected, making $\mathsf{m}$ +the first message of $\mathsf{J}$ that is accepted after $\mathsf{r_1}$. + +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} \geq 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 \ref{prop:bothmessages} and the existence of $\mathsf{m}$. +Since $\mathsf{H \neq J}$, then by Proposition \ref{prop:bothmessages} 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. + +Now that we know that $\mathsf{C}$ sees $\mathsf{r_1}$, note that C receives $\mathsf{u}$ +immediately after $\mathsf{t}$ by Proposition \ref{prop:seqnumb}. Therefore, +$\mathsf{C}$ could not have seen a message after $\mathsf{t}$ with sequence number less +than $\mathsf{s_m}$. In the $\mathsf{PutDataEntries()}$ subroutine, $\mathsf{J}$ adds every +$\mathsf{cr}$ entry that contains sequence number $\mathsf{s}$ and machine ID +$\mathsf{id}$ of the messsages that win in the collisions before $\mathsf{m}$ into +$\mathsf{CR}$; $\mathsf{CR}$ keeps the collection of live $\mathsf{cr}$ entries, namely +those which not all clients have seen. Hence, for every $\mathsf{i}$, $\mathsf{1 \leq i < |X|}$, +the collision winner that has collided with $\mathsf{x_i}$ will be recorded appropriately. Since all the $\mathsf{cr}$ entries that record the results of the collisions before $\mathsf{p}$ will also be seen when $\mathsf{u}$ +is received, and $\mathsf{C}$ sees $\mathsf{r_1}$, ${l_1}$ will be recorded in a $\mathsf{cr}$ entry as the winner in the +collision against ${r_1}$. + +When $\mathsf{C}$ receives $\mathsf{u}$, if $\mathsf{C}$ +has seen the $\mathsf{cr}$ entry that records the collision at index $\mathsf{s_q + 1}$, it will throw +an error from the mismatch of $\mathsf{\tuple{s_q+1, id_J}}$ with +$\mathsf{\tuple{s_q+1, id_K}}$ in the corresponding $\mathsf{cr}$ entry. + \end{itemize} \end{itemize} \end{itemize} \end{proof} +\begin{lem} +\label{lem:pathmessages} +If there are two messages $\mathsf{t}$ and $\mathsf{u}$, with +$\mathsf{s_t \leq s_u}$, such that $\mathsf{t}$ is in the path of $\mathsf{u}$, +then for any message $\mathsf{p}$ with $\mathsf{s_p \leq s_t}$, iff $\mathsf{p}$ is in +the path of $\mathsf{t}$, it is in the path of $\mathsf{u}$. +\end{lem} + +\begin{proof} +If $\mathsf{s_t = s_u}$ or $\mathsf{s_p = s_t}$, then we are done, because the two +relevant messages are the same. If they are different messages, then: +\begin{itemize} +\item Reverse direction: The definition of $\mathsf{t}$ being in the path of +$\mathsf{u}$ is the existence of a message sequence $\mathsf{(\dots, t, \dots, u)}$ +such that each message except $\mathsf{u}$ is the parent of the succeeding message. +The path of $\mathsf{u}$ must contain some message with sequence number $\mathsf{s_p}$; +because $\mathsf{p}$ is in the path of $\mathsf{u}$, this message is $\mathsf{p}$ +itself. The path of $\mathsf{t}$ is then the prefix of this path ending at $\mathsf{t}$, +which clearly contains $\mathsf{p}$. + +\item Forward direction: The path of $\mathsf{t}$ is a substring of the path of +$\mathsf{u}$, so if the path of $\mathsf{t}$ contains $\mathsf{p}$, so does the path +of $\mathsf{u}$. +\end{itemize} +\end{proof} + \begin{theorem} -Suppose that there is a transitive closure set $\mathscr{S}$ of clients, at index $n$. Then there is some total message sequence $T$ of length $n$ such that every client $C$ in $\mathscr{S}$ sees a partial sequence $P_C$ consistent with $T$. \end{theorem} +Suppose that there is a transitive closure set $\mathsf{\mathscr{S}}$ of clients, +at sequence number $\mathsf{s_n}$. Then there is some total sequence $\mathsf{T}$ of +length $\mathsf{n}$ such that every client $\mathsf{C}$ in $\mathsf{\mathscr{S}}$ +sees a partial sequence $\mathsf{P_C}$ consistent with $\mathsf{T}$. +\end{theorem} \begin{proof} -The definition of consistency of $P_C$ with $T$ is that every message $p \in P_C$ with index $i(p) \le n$ is equal to the message in that slot in $T$. Let $C_1$ be some client in the transitive closure set, with partial message sequence $P_{C_1}$, and let $u$ be some message with $i(u) > i$ that $C_1$ shares with another client. Then let $T$ be the portion of the path of $u$ ending at index $i$ and $t$ be the message at that index. Clearly, by Lemma 1, $P_{C_1}$ is consistent with $T$. We will show that, for every other client $D$ with partial sequence $P_D$, $P_D$ has some message whose path includes $t$. Because $D$ is in the transitive closure, there is a sequence of edges from $C_1$ to $D$. Call this $\mathscr{C} = (C_1, C_2, ..., D)$. -We subsequently prove by induction that $D$ has a message whose path includes $t$. +The definition of consistency of $\mathsf{P_C}$ with $\mathsf{T}$ is that every message +$\mathsf{p \in P_C}$ with sequence number $\mathsf{s_p \le s_n}$ is equal to the message +in that slot in $\mathsf{T}$. Let $\mathsf{C_1}$ be some client in the transitive closure +set, with partial sequence $\mathsf{P_{C_1}}$, and let $\mathsf{u}$ be some message with +$\mathsf{s_u > s_n}$ that $\mathsf{C_1}$ shares with another client. Then let $\mathsf{T}$ +be the portion of the path of $\mathsf{u}$ ending at sequence number $\mathsf{s_n}$ and +$\mathsf{t}$ be the message at that sequence number. Clearly, by Lemma \ref{lem:twomessages}, +$\mathsf{P_{C_1}}$ is consistent with $\mathsf{T}$. We will show that, for every other client +$\mathsf{D}$ with partial sequence $\mathsf{P_D}$, $\mathsf{P_D}$ has some message whose path +includes $\mathsf{t}$. Because $\mathsf{D}$ is in the transitive closure, there is a sequence +of clients $\mathsf{\mathscr{C} = (C_1, C_2, ..., D)}$ from $\mathsf{C_1}$ to $\mathsf{D}$, +where each shares an edge with the next. +We prove by induction that $\mathsf{P_D}$ has a message whose path includes $\mathsf{t}$. \begin{itemize} -\item For the base case, $P_{C_1}$ includes $u$, whose path includes $t$. -\item For the inductive step, suppose $P_{C_k}$ has a message $w$ with a path that includes $t$, and shares message $x$ with $P_{C_{k+1}}$ such that $i(x) > i$. If $i(w) = i(x)$, then $w = x$. If $i(w) < i(x)$, then, by Lemma 1, $w$ is in the path of $x$. If $i(w) > i(x)$, $x$ is in the path of $w$; note again that its index is greater than $i$. In any case, $t$ is in the path of $u_k+1$. -\item Let $w$ the message of $D$ whose path includes $t$. By Lemma 1, every message in $P_D$ with index smaller than $i(w)$ is in the path of $w$. Since $t$ is in the path of $w$, every message in $P_D$ with smaller index than $i(t)$ is in $T$. Therefore, $P_D$ is consistent with $T$. +\item Base case: $\mathsf{P_{C_1}}$ includes $\mathsf{u}$, whose path includes $\mathsf{t}$. + +\item Inductive step: Each client in $\mathsf{\mathscr{C}}$ has a partial sequence with a message +that includes $\mathsf{t}$ if the previous client does. Suppose $\mathsf{P_{C_k}}$ has +a message $\mathsf{w}$ with a path that includes $\mathsf{t}$, and shares message $\mathsf{x}$ +with $\mathsf{P_{C_{k+1}}}$ such that $\mathsf{s_x > s_n}$. By Lemma \ref{lem:twomessages}, +$\mathsf{w}$ or $\mathsf{x}$, whichever has the least sequence number, is in the path of the other, +and therefore by Lemma \ref{lem:pathmessages}, $\mathsf{t}$ is in the path of $\mathsf{x}$. + +\item Let $\mathsf{z}$ be the message of $\mathsf{D}$ whose path includes $\mathsf{t}$. +By Lemma \ref{lem:twomessages}, every message in $\mathsf{P_D}$ with sequence number smaller +than $\mathsf{s_w}$ is in the path of $\mathsf{z}$. Since $\mathsf{t}$ is in the path of +$\mathsf{z}$, every message in $\mathsf{P_D}$ with smaller sequence number than +$\mathsf{s_t = s_n}$ is in $\mathsf{T}$. +Therefore, $\mathsf{P_D}$ is consistent with $\mathsf{T}$. + \end{itemize} \end{proof}