\r
\section{\textbf{Introduction}}\r
\r
-\section{\textbf{Client}}\r
\r
-\subsection{\textbf{Client Notation Conventions}}\r
+\section{Approach}\r
+\r
+\subsection{Keys}\r
+\r
+Each device has: user id + password\r
+\r
+Server login is:\r
+hash1(user id), hash1(password)\r
+\r
+Symmetric Crypto keys is:\r
+hash2(user id | password)\r
+\r
+Server has finite length queue of entries + max\_entry\_identifier +\r
+server login key\r
+\r
+\subsection{Entry layout}\r
+Each entry has:\r
+\begin{enumerate}\r
+\item Sequence identifier\r
+\item Random IV (if needed by crypto algorithm)\r
+\item Encrypted payload\r
+\end{enumerate}\r
+\r
+Payload has:\r
+\begin{enumerate}\r
+\item Sequence identifier\r
+\item Machine id (most probably something like a 64-bit random number \r
+that is self-generated by client)\r
+\item HMAC of previous slot\r
+\item Data entries\r
+\item HMAC of current slot\r
+\end{enumerate}\r
+\r
+A data entry can be one of these:\r
+\begin{enumerate}\r
+ \item A transaction:\r
+ \begin{itemize}\r
+ \item Contains a sequence number, a set of key value pair updates and a guard condition that can be evaluated.\r
+ \item Must have the same arbitrator for all its key value pair updates and reads within the guard condition\r
+ \end{itemize}\r
+ \r
+ \item A Commit\r
+ \newline{Commits a transaction into the block chain. Until a transaction is committed, no client can be sure if that transaction's key value updates will be used to update the state of the system. Once an arbitrator commits a transaction then that transaction becomes a permanent state change in the system. Transactions should be committed and aborted in order of their sequence numbers.}\r
+ \r
+ \item An Abort\r
+ \newline{An abort is used to show that a transactions key value update should not be used in the state change of the system. This occurs when the guard of a transaction evaluates to false meaning that the conditions under-which this transaction should be committed no longer exists in the system (another transaction could have been committed first that would have changed the system in a way that makes the current transaction invalid).}\r
+ \r
+ \item New Key:\r
+ \newline{This creates a new key and assignes an arbitrator to that key. Only the first new key message for a given key is valid. Once a new key message is inserted into the block chain it is never removed and no other new key entries for the same key name can be inserted into the block chain.}\r
+ \r
+ \item Slot sequence entry: Machine id + last message identifier \r
+ \newline {The purpose of this is to keep the record of the last slot from a certain client if a client's update has to expunge that other client's last entry from the queue. This is kept in the slot until the entry owner inserts a newer update into the queue.}\r
+\r
+ \item Queue state entry: Includes queue size \r
+ \newline {The purpose of this is for the client to tell if the server lies about the number of slots in the queue, e.g. if there are 2 queue state entry in the queue, e.g. 50 and 70, the client knows that when it sees 50, it should expect at most 50 slots in the queue and after it sees 70, it should expect 50 slots before that queue state entry slot 50 and at most 70 slots. The queue state entry slot 70 is counted as slot number 51 in the queue.}\r
+\r
+ \item Collision resolution entry: message identifier + machine id of a collision winner\r
+ \newline {The purpose of this is to keep keep track of the winner of all the collisions until allclients have seen the particular entry.}\r
+\end{enumerate}\r
+\r
+\subsection{Live status}\r
+\r
+Live status of entries:\r
+\begin{enumerate}\r
+ \item Transaction is live if it has not been committed or aborted yet.\r
+ \r
+ \item Abort is live until the machine ID that created the transaction that is being aborted inserts into the block chain a message with a sequence number greater than the abort (that client sees the abort).\r
+ \r
+ \item Commit is dead if for all key value updates in the commit there is a commit with the same key value update that is newer (larger sequence number).\r
+ \r
+ \item New Key messages are always kept alive.\r
+ \r
+ \item Slot sequence number (of either a message version data or user-level data) is dead if there is a newer slot from the same machine.\r
+\r
+ \item Queue state entry is dead if there is a newer queue state entry.\r
+ {In the case of queue state entries 50 and 70, this means that queue state entry 50 is dead and 70 is live. However, not until the number of slots reaches 70 that queue state entry 50 will be expunged from the queue.}\r
+\r
+ \item Collision resolution entry is dead if this entry has been seen by all clients after a collision happens.\r
+\end{enumerate}\r
+\r
+When data is at the end of the queue ready to expunge, if:\r
+\begin{enumerate}\r
+ \item If any entry is not dead it must be reinserted into the queue.\r
+\r
+ \item If the slot sequence number is not dead, then a message sequence entry must be inserted.\r
+\end{enumerate}\r
+\r
+\paragraph{Validation procedure on client:}\r
+\begin{enumerate}\r
+ \item Decrypt each new slot in order.\r
+ \item For each slot:\r
+ (a) check its HMAC, and\r
+ (b) check that the previous entry HMAC field matches the previous entry (in case of a gap do not check for slots on gap margins).\r
+ \item That no slots are slots we have seen before (server trying to pass old slots). \r
+ \r
+ \item For all other machines, check that the latest sequence number is at least as large (never goes backwards).\r
+ \r
+ \item That the queue has a current queue state entry.\r
+ \r
+ \item That the number of entries received is consistent with the size specified in the queue state entry and/or the queue is growing in size.\r
+\end{enumerate}\r
+\r
+\subsection{Resizing Queue}\r
+Client can make a request to resize the queue. This is done as a write that combines:\r
+ (a) a slot with the message, and (b) a request to the server. The queue can only be expanded, never contracted; attempting to decrease the size of the queue will cause future clients to throw an error.\r
+\r
+\r
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
+\r
+\subsection{The Arbitrator}\r
+Each key has an arbitrator that makes the final decision when it comes to whether a specific transaction containing that key updates the state of the system or is aborted. This ensures that clients can make offline updates and then push those updates to the server at a later time. The arbitrator then tries to merge those updates and if possible will commit them into the current working state of the system. If not possible then the arbitrator will abort that transaction. The arbitrator arbitrates on transactions in order of transaction sequence number.\r
+\r
+\r
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
+\section{Server Algorithm}\r
+$s \in SN$ is a sequence number\\\r
+$sv \in SV$ is a slot's value\\\r
+$slot_s = \tuple{s, sv} \in SL \subseteq SN \times SV$ \\ \\\r
+\textbf{State} \\\r
+\textit{SL = set of live slots on server} \\\r
+\textit{max = maximum number of slots (input only for resize message)} \\\r
+\textit{n = number of slots} \\ \\\r
+\textbf{Helper Function} \\\r
+$MaxSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv}\r
+\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
+$MinSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \r
+\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\\r
+$SeqN(slot_s = \tuple{s, sv})=s$ \\\r
+$SlotVal(slot_s = \tuple{s, sv})=sv$ \\\r
+\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get Slot:}\\\r
+Returns to the client the slots that have a sequence number that is greater than or equal to the sequence number that is in the requese.\\\r
+\begin{algorithmic}[1]\r
+\Function{GetSlot}{$s_g$}\r
+\State \Return{$\{\tuple{s, sv} \in SL \mid s \geq s_g\}$}\r
+\EndFunction\r
+\end{algorithmic}\end{varwidth}% \r
+}\r
+\r
+\r
+\noindent\fbox{%\r
+\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}\r
+\textbf{Get Slot:}\\\r
+Puts a slot in the server memory if the slot has the correct sequence number. Also resizes the server memory if needed.\\\r
+\begin{algorithmic}[1]\r
+\Function{PutSlot}{$s_p,sv_p,max'$}\r
+\If{$(max' \neq \emptyset)$} \Comment{Resize}\r
+\State $max \gets max'$\r
+\EndIf\r
+\State $\tuple{s_n,sv_n} \gets MaxSlot(SL)$\Comment{Last sv}\r
+%\State $s_n \gets SeqN(\tuple{s_n,sv_n})$\r
+\If{$(s_p = s_n + 1)$}\r
+ \If{$n = max$}\r
+ \State $\tuple{s_m,sv_m} \gets MinSlot(SL)$\Comment{First sv}\r
+ \State $SL \gets SL - \{\tuple{s_m,sv_m}\}$\r
+ \Else \Comment{$n < max$}\r
+ \State $n \gets n + 1$\r
+ \EndIf\r
+ \State $SL \gets SL \cup \{\tuple{s_p,sv_p}\}$\r
+ \State \Return{$(true,\emptyset)$}\r
+\Else\r
+ \State \Return{$(false,\{\tuple{s,sv}\in SL \mid \r
+ s \geq s_p\})$}\r
+\EndIf\r
+\EndFunction\r
+\end{algorithmic}\end{varwidth}% \r
+}\r
+\r
\r
\r
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
+\section{\textbf{Client}}\r
+\r
+\subsection{\textbf{Client Notation Conventions}}\r
$k$ is key of entry \\\r
$v$ is value of entry \\\r
$size$ is a size (target size of the current block chain) \\\r
projects / iotcloud.git / blobdiff