version2/doc/iotcloud.tex

   1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
   2 % Short Sectioned Assignment\r
   3 % LaTeX Template\r
   4 % Version 1.0 (5/5/12)\r
   5 %\r
   6 % This template has been downloaded from:\r
   7 % http://www.LaTeXTemplates.com\r
   8 %\r
   9 % Original author:\r
  10 % Frits Wenneker (http://www.howtotex.com)\r
  11 %\r
  12 % License:\r
  13 % CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)\r
  14 %\r
  15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
  16 \r
  17 %----------------------------------------------------------------------------------------\r
  18 %   PACKAGES AND OTHER DOCUMENT CONFIGURATIONS\r
  19 %----------------------------------------------------------------------------------------\r
  20 \r
  21 \documentclass[paper=letter, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size\r
  22 \r
  23 \usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs\r
  24 \usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default\r
  25 \usepackage[english]{babel} % English language/hyphenation\r
  26 \usepackage{amsmath,amsfonts,amsthm} % Math packages\r
  27 \usepackage{graphicx}\r
  28 \usepackage{lipsum} % Used for inserting dummy 'Lorem ipsum' text into the template\r
  29 \usepackage{hyperref}\r
  30 \usepackage{amssymb}\r
  31 \usepackage{listings}\r
  32 \usepackage[]{algorithm2e}\r
  33 \usepackage{algpseudocode}\r
  34 \usepackage{enumerate}\r
  35 \usepackage[table,xcdraw]{xcolor}\r
  36 \usepackage{sectsty} % Allows customizing section commands\r
  37 \usepackage{float}\r
  38 \usepackage{caption}\r
  39 \usepackage{gensymb} % to used degree symbol \r
  40 \usepackage{siunitx} \r
  41 \usepackage{enumitem}\r
  42 \r
  43 \usepackage[sc]{mathpazo}\r
  44 \allsectionsfont{ \normalfont\scshape} % Make all sections the default font and small caps\r
  45 \usepackage{fancyhdr} % Custom headers and footers\r
  46 \pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers\r
  47 \fancyhead{} % No page header - if you want one, create it in the same way as the footers below\r
  48 \fancyfoot[L]{} % Empty left footer\r
  49 \fancyfoot[C]{} % Empty center footer\r
  50 \fancyfoot[R]{\thepage} % Page numbering for right footer\r
  51 \renewcommand{\headrulewidth}{0pt} % Remove header underlines\r
  52 \renewcommand{\footrulewidth}{0pt} % Remove footer underlines\r
  53 \setlength{\headheight}{13.6pt} % Customize the height of the header\r
  54 \r
  55 \numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)\r
  56 \numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)\r
  57 \numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)\r
  58 \r
  59 \setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text\r
  60 \r
  61 %----------------------------------------------------------------------------------------\r
  62 %   TITLE SECTION\r
  63 %----------------------------------------------------------------------------------------\r
  64 \newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height\r
  65 \r
  66 \title{ \r
  67 \normalfont \normalsize \r
  68 \textsc{University of California Irvine} \\  % Your university, school and/or department name(s)\r
  69 \textsc{Prgramming Language Research Group} \\ [25pt]\r
  70 \horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule\r
  71 \huge IoTCloud Version 2.0\\ % The assignment title\r
  72 \horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule\r
  73 }\r
  74 \r
  75 \author{Authors} % Your name\r
  76 \r
  77 \r
  78 \date{\normalsize\today} % Today's date or a custom date\r
  79 \r
  80 \begin{document}\r
  81 \r
  82 \maketitle % Print the title\r
  83 \r
  84 \r
  85 \r
  86 \r
  87 %---------------------------------------------------------------------------------------\r
  88 % Custom Stuff\r
  89 %---------------------------------------------------------------------------------------\r
  90 \newcommand{\tab}[1]{\hspace{.2\textwidth}\rlap{#1}}\r
  91 \r
  92 \r
  93 \r
  94 \r
  95 \section{\textbf{Introduction}}\r
  96 \r
  97 \section{\textbf{Approach}}\r
  98 \r
  99 \subsection{\textbf{Records}}\r
 100 Each record has the following information included in it:\r
 101 \begin{itemize}\r
 102     \item Machine ID of the device creating the record\r
 103     \item The vector clock using the largest clock values from each device it knows and its own largest clock value incremented by 1.\r
 104     \item Add a random salt (or nonce) for the encryption safety\r
 105     \item Data payload\r
 106     \item HMAC of the record.\r
 107 \end{itemize}\r
 108     \r
 109 \r
 110 \r
 111 \subsubsection{\textbf{Types of Payloads}}\r
 112 The different types of record payloads are:\r
 113 \begin{itemize}\r
 114     \item Delete notifications\r
 115         \begin{itemize}\r
 116             \item Contains the HMAC of records that were deleted by devices.\r
 117             \item Generated when a device deletes a key from the end of one of the device queues.\r
 118         \end{itemize}\r
 119     \item Commit notifications\r
 120         \begin{itemize}\r
 121             \item Contains list of transactions that are committed in order of commit and the current key-value pair for that key.\r
 122             \item Generated by the arbitrator of a key and only the for that key (1 arbitrator per key).\r
 123             \item \r
 124         \end{itemize}\r
 125     \item Abort notifications\r
 126         \begin{itemize}\r
 127             \item Contains a transaction ID of an aborted transaction and the machine ID of the device that created that transaction.\r
 128         \end{itemize}\r
 129     \item Data structure re-size notifications\r
 130         \begin{itemize}\r
 131             \item Contains new size of data structure (number of record allowed in the data structure).\r
 132             \item Causes old data Structure re-size notification to no longer be live.\r
 133         \end{itemize}\r
 134     \item Server sequence number for a specific record notifications\r
 135         \begin{itemize}\r
 136             \item Contains a record HMAC and the server sequence number for that record\r
 137         \end{itemize}\r
 138     \item Transactions\r
 139         \begin{itemize}\r
 140             \item Contains:\r
 141             \begin{itemize}\r
 142                 \item Transaction ID\r
 143                 \item A guard condition that can be evaluated\r
 144                 \item A set of key-value pairs that are to be updated if the guard condition is met.\r
 145             \end{itemize}\r
 146         \end{itemize}\r
 147 \end{itemize}\r
 148 \r
 149 \r
 150 \subsection{\textbf{Updates}}\r
 151 Updates take place as follows:\r
 152 \begin{enumerate}\r
 153     \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
 154     \item The device makes a record as follows:\r
 155         \begin{enumerate}\r
 156             \item Adds its machine ID.\r
 157             \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
 158             \item Add a random salt (or nonce) for the encryption safety\r
 159             \item Fill the record data section with the transactions, key-value pairs, ext.\r
 160             \item Fill the remainder of the data section with rescued key-value pairs, transactions, ext.\r
 161             \item Pad the record to be the same size for all records.\r
 162             \item Calculate the HMAC of the record and add that to the record\r
 163             \item Encrypt the record\r
 164         \end{enumerate}\r
 165     \item Send the record to the server for insertion into the device's queue.\r
 166     \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
 167     \item \r
 168 \end{enumerate}\r
 169 \r
 170 \r
 171 \subsection{\textbf{Updates}}\r
 172 \subsection{\textbf{Deletions}}\r
 173 \r
 174 \subsection{\textbf{Checking the Graph}}\r
 175 Checking the data structure for consistency is done as follows:\r
 176 \begin{enumerate}\r
 177     \item Verify that each record in the data structure has an HMAC that matches the data in the record.\r
 178     \item Verify that there are at least as many records in the data structure as stated in the largest data structure size record.\r
 179     \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
 180     \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
 181 \end{enumerate}\r
 182 \r
 183     \r
 184 \subsection{\textbf{Live Status}}\r
 185 Live Status of entries:\r
 186 \begin{enumerate}\r
 187     \item Key-Value Entry is dead if either:\r
 188     \begin{enumerate}\r
 189         \item there is a newer key-value pair\r
 190         \item it is incomplete.\r
 191     \end{enumerate}\r
 192     \r
 193     \item If there are $n$ devices in the system then there are $n$ separate queues\r
 194 \end{enumerate}\r
 195     \r
 196 \r
 197 \end{document}