[iotcloud.git] / version2 / doc / iotcloud.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
% Short Sectioned Assignment\r
% LaTeX Template\r
% Version 1.0 (5/5/12)\r
%\r
% This template has been downloaded from:\r
% http://www.LaTeXTemplates.com\r
%\r
% Original author:\r
% Frits Wenneker (http://www.howtotex.com)\r
%\r
% License:\r
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)\r
%\r
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
\r
%----------------------------------------------------------------------------------------\r
%   PACKAGES AND OTHER DOCUMENT CONFIGURATIONS\r
%----------------------------------------------------------------------------------------\r
\r
\documentclass[paper=letter, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size\r
\r
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs\r
\usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default\r
\usepackage[english]{babel} % English language/hyphenation\r
\usepackage{amsmath,amsfonts,amsthm} % Math packages\r
\usepackage{graphicx}\r
\usepackage{lipsum} % Used for inserting dummy 'Lorem ipsum' text into the template\r
\usepackage{hyperref}\r
\usepackage{amssymb}\r
\usepackage{listings}\r
\usepackage[]{algorithm2e}\r
\usepackage{algpseudocode}\r
\usepackage{enumerate}\r
\usepackage[table,xcdraw]{xcolor}\r
\usepackage{sectsty} % Allows customizing section commands\r
\usepackage{float}\r
\usepackage{caption}\r
\usepackage{gensymb} % to used degree symbol \r
\usepackage{siunitx} \r
\usepackage{enumitem}\r
\r
\usepackage[sc]{mathpazo}\r
\allsectionsfont{ \normalfont\scshape} % Make all sections the default font and small caps\r
\usepackage{fancyhdr} % Custom headers and footers\r
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers\r
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below\r
\fancyfoot[L]{} % Empty left footer\r
\fancyfoot[C]{} % Empty center footer\r
\fancyfoot[R]{\thepage} % Page numbering for right footer\r
\renewcommand{\headrulewidth}{0pt} % Remove header underlines\r
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines\r
\setlength{\headheight}{13.6pt} % Customize the height of the header\r
\r
\numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)\r
\numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)\r
\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)\r
\r
\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text\r
\r
%----------------------------------------------------------------------------------------\r
%   TITLE SECTION\r
%----------------------------------------------------------------------------------------\r
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height\r
\r
\title{ \r
\normalfont \normalsize \r
\textsc{University of California Irvine} \\  % Your university, school and/or department name(s)\r
\textsc{Prgramming Language Research Group} \\ [25pt]\r
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule\r
\huge IoTCloud Version 2.0\\ % The assignment title\r
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule\r
}\r
\r
\author{Authors} % Your name\r
\r
\r
\date{\normalsize\today} % Today's date or a custom date\r
\r
\begin{document}\r
\r
\maketitle % Print the title\r
\r
\r
\r
\r
%---------------------------------------------------------------------------------------\r
% Custom Stuff\r
%---------------------------------------------------------------------------------------\r
\newcommand{\tab}[1]{\hspace{.2\textwidth}\rlap{#1}}\r
\r
\r
\r
\r
\section{\textbf{Introduction}}\r
\r
\section{\textbf{Approach}}\r
\r
\subsection{\textbf{Records}}\r
Each record has the following information included in it:\r
\begin{itemize}\r
    \item Machine ID of the device creating the record\r
    \item The vector clock using the largest clock values from each device it knows and its own largest clock value incremented by 1.\r
    \item Add a random salt (or nonce) for the encryption safety\r
    \item Data payload\r
    \item HMAC of the record.\r
\end{itemize}\r
    \r
\r
\r
\subsubsection{\textbf{Types of Payloads}}\r
The different types of record payloads are:\r
\begin{itemize}\r
    \item Delete notifications\r
        \begin{itemize}\r
            \item Contains the HMAC of records that were deleted by devices, Their vector clocks and the server sequence numbers.\r
            \item Generated when a device deletes a record.\r
            \item The delete notification with the largest server sequence number in its delete payload is the live one (the one that contains the largest server sequence number of the record deleted to date).  \r
        \end{itemize}\r
    \item Commit notifications\r
        \begin{itemize}\r
            \item Contains list of transactions that are committed in order of commit and the current key-value pair for that key.\r
            \item Generated by the arbitrator of a key and only the for that key (1 arbitrator per key).\r
            \item Used in the case that there is a key value pair that needs reordering.\r
        \end{itemize}\r
    \item Abort notifications\r
        \begin{itemize}\r
            \item Contains a transaction ID of an aborted transaction and the machine ID of the device that created that transaction.\r
            \item Causes a transaction to be aborted.\r
        \end{itemize}\r
    \item Abort acknowledgement notifications\r
        \begin{itemize}\r
            \item Contains a transaction ID of an aborted transaction, the machine ID of the device that created that transaction and the abort notification ID that this is acknowledging.\r
            \item Causes an abort notification to become dead.\r
            \item Is generated by the device that had created an aborted transaction as an acknowledgement that it saw the aborted transaction notification.\r
            \item This payload type immediately becomes dead (not live) upon insertion into the data structure.\r
        \end{itemize}\r
    \item Data structure re-size notifications\r
        \begin{itemize}\r
            \item Contains new size of data structure (number of record allowed in the data structure or something like that).\r
            \item Causes old data Structure re-size notification to no longer be live.\r
        \end{itemize}\r
    \item Server sequence number for a specific record notifications\r
        \begin{itemize}\r
            \item Contains a record HMAC and the server sequence number for that record\r
        \end{itemize}\r
    \item Transactions\r
        \begin{itemize}\r
            \item Contains:\r
            \begin{itemize}\r
                \item Transaction ID\r
                \item A guard condition that can be evaluated\r
                \item A set of key-value pairs that are to be updated if the guard condition is met.\r
            \end{itemize}\r
        \end{itemize}\r
\end{itemize}\r
\r
\r
\subsection{\textbf{Updates (Online Updates)}}\r
Updates take place as follows:\r
\begin{enumerate}\r
    \item A device pulls the latest version of the data structure.  If the device cannot pull the latest version because of network connectivity or some other issues then that device will just work using the local copy of the data structure it has.\r
    \item The device makes a record as follows:\r
        \begin{enumerate}\r
            \item Adds its machine ID.\r
            \item Creates a vector clock using the largest clock values from each device it knows and its own largest clock value incremented by 1.\r
            \item Add a random salt (or nonce) for the encryption safety\r
            \item Fill the record data section with the transactions, key-value pairs, ext.\r
            \item Fill the remainder of the data section with rescued key-value pairs, transactions, ext (Discussed later).\r
            \item Pad the record to be the same size for all records.\r
            \item Calculate the HMAC of the record and add that to the record\r
            \item Encrypt the record.\r
        \end{enumerate}\r
    \item Send the record to the server for insertion into the device's queue.\r
    \item Wait for response from server stating the new records (the one just sent) server sequence number.  Save this server sequence number for when creating the next record.\r
    \item \r
\end{enumerate}\r
\r
\r
\subsection{\textbf{Updates when offline}}\r
When offline and making updates, the devices should use their local copy of the data structure but do no deletes.  When connection is reestablished the following should take place:\r
\r
\begin{enumerate}\r
    \item Pull the latest version of the data structure.\r
    \item Update local copy of the data structure except for own devices device queue (do deletions as needed)\r
    \item Calculate many records are "new" to the data structure and pick the same amount to be deleted\r
    \item Push the updates and the deletes to the server\r
    \item Wait for sequence numbers for the recently pushed records\r
    \item Push the sequence numbers for the recently pushed records (using online updates from the section above)\r
\end{enumerate}\r
\r
This kind of update will result in the latest key-value pair being the last pushed record from this update (if no other updates are occurring at the same time).  The arbitrator can then commit or abort as needed but in the mean time the key-value pair may be an old one (but have the largest server sequence number).\r
\r
\subsection{\textbf{Deletions}}\r
When deciding which records to delete the following is to be done:\r
\begin{enumerate}\r
    \item Order all the records in order based on their server sequence numbers\r
    \item Calculate the difference between the current size of the data structure and the minimum size of the data structure (lets call this $m$)\r
    \item Delete the oldest m records based on the ordering from step 1. \r
    \begin{itemize}\r
        \item If a record to be deleted has live data in it then the whole data structure needs to be resized.\r
    \end{itemize}\r
\end{enumerate}\r
\r
Note this makes that size of the data structure be bounded.\r
If there are $n$ devices and the data structure has a minimum size of $m$.  Then the max size of the data structure is given by $m + n$ for the case when all the devices make an update at the same time.   \r
\r
\subsection{\textbf{Rescuing Transactions, Commits, Aborts, Ext}}\r
Data should be proactively rescued from the "oldest" records currently in the data structure.  Unused space in new records should be used to rescue data from old records so that when it comes time to delete the old records, there are no live pieces of data that need to be rescued.  When a piece of data is rescued, it is rescued with its vector clock as well (so that the time of that data can be saved).\r
\r
When deciding which data to rescue the following is to be done:\r
\begin{enumerate}\r
    \item Order all the records in order based on their server sequence numbers\r
    \item Create an ordered list of currently live transactions, commits, aborts, ext from the oldest $n$ records from step one where the order is based on the age of the data (how old the record .\r
    \item Randomly select from the list of live data to save.  Save as much as can fit in the current new record.  The random selection could give higher probability to data from records that are to be deleted sooner.\r
\end{enumerate}\r
\r
If a record needs to be deleted but still contains live data then the data structure needs to be resized.  \r
\r
\subsection{\textbf{Checking the Data Structure}}\r
Checking the data structure for consistency is done as follows:\r
\begin{enumerate}\r
    \item Verify that each record in the data structure has an HMAC that matches the data in the record.\r
    \item Verify that there are at least as many records in the data structure as stated in the largest data structure size record.\r
    \item Make sure that for each device queue the difference between the vector clock value of the device queues clock is at most 1 between 2 consecutive messages.\r
    \item Verify that no currently live data Structure re-size notification is smaller than the last known data structure size.  Data structure can only grow in size.\r
    \item Verify that all the server sequence numbers for the records that are currently present have unique numbers that have a difference of 1 (no gaps).\r
    \item Verify record server sequence numbers against the stated server sequence numbers in the server sequence number notification payloads (make sure the server is not changing the sequence number on the fly).\r
    \item \r
\end{enumerate}\r
\r
\r
\subsection{\textbf{The Arbitrator}}\r
The arbitrator can:\r
\begin{enumerate}\r
    \item Send Commits\r
    \item Send Aborts\r
\end{enumerate}\r
    \r
\subsubsection{\textbf{Commits}}\r
Commits have the following properties\r
\begin{itemize}\r
    \item Agree with the ordering of the server sequence numbers\r
    \item Once a key-value pair is commited it can not be commited again.\r
    \item Cannot commit an already aborted transaction.\r
    \item Commits state the ordering of key-value pairs.\r
    \item Can disagree with the ordering of server sequence numbers but\r
    \item Should occur frequently as to make sure that the commit order matches the server sequence ordering as closely as possible (prevent large divergence of the 2 orderings)\r
\end{itemize}\r
    \r
\subsubsection{\textbf{Aborts}}\r
Aborts are used to show which transactions have been aborted and will not be used in the total ordering of the transactions.  Aborts are considered live until an abort acknowledgement is presented.\r
When the transaction is aborted then the devices should simply act as if it were never present when evaluating for the latest key-value pair.\r
    \r
\subsection{\textbf{Live Status}}\r
Live Status of entries:\r
\begin{enumerate}\r
    \item Key-Value Entry/Data Entry is dead if either:\r
    \begin{enumerate}\r
        \item There is a newer key-value pair:\r
        \begin{itemize}\r
            \item There is a transaction with a newer vector clock value.\r
            \item There is a commit that for this key-value pair.\r
            \item There is an abort for this key-value pair.\r
        \end{itemize}\r
        \item It is incomplete.\r
        \item It is an abort notification that has an abort notification acknowledgment\r
        \item It is an abort notification acknowledgment (dead on arrival).\r
    \end{enumerate}\r
    \item Data is live if there are multiple versions of the same data (key-value pair) in which the vector clock values show concurrency.  All versions are kept live the arbitrator arbitrates.\r
    \item Multiple versions of the same data (same transaction ID for example) are not all live.  Only the version with the largest server sequence number is live.  \r
    \r
\end{enumerate}\r
\r
    \r
\r
\end{document}