mscTemplate.tex

   1 \documentclass[10pt]{article}
   2
   3 \usepackage[top=3cm, bottom=3cm, left=3cm, right=3cm]{geometry}
   4 \usepackage{todonotes}
   5 \usepackage{times}
   6 \usepackage[brazil]{babel}
   7 \usepackage[utf8]{inputenc}
   8 \usepackage{graphicx}
   9 \usepackage{url}
  10 \usepackage{paralist}
  11 \usepackage{hyperref}
  12 \usepackage{amssymb}
  13 \usepackage{setspace}
  14 \usepackage{paralist}
  15
  16 \newcommand{\mytitle}{Título do Trabalho de Mestrado} %PT
  17 \newcommand{\f}{$\blacksquare$}
  18
  19 \hypersetup{
  20      pdftitle={\mytitle},
  21      pdfauthor={Rodrigo Eduardo Lazo Paz},
  22      pdfdisplaydoctitle=true,
  23      pdfborder=0 0 0
  24 }
  25
  26 \title{\mytitle}
  27
  28 \author{
  29 Rodrigo Eduardo Lazo Paz\\%\thanks{Grants.} \\
  30 IC, Unicamp \\
  31 Campinas, Brasil \\
  32 {\small \url{rodrigo.lazo@students.ic.unicamp.br}} \\
  33 \and
  34 Luiz E.  Buzato \\ %\thanks{Identificação de projetos aqui.}\\
  35 IC, Unicamp \\ Campinas, Brasil \\ {\small
  36 \url{buzato@ic.unicamp.br}}
  37 }
  38
  39 \hyphenation{par-ti-cu-lar-men-te}
  40 \hyphenation{su-fi-ci-en-tes}
  41
  42 \begin{document}
  43 \doublespacing
  44
  45 \newpage
  46
  47 \section{Introdução}
  48 \label{sec:introduction}
  49
  50 Algoritmos distribuídos são aqueles desenhados para se executar em
  51 sistemas compostos por um conjunto interconectado de processos
  52 autônomos que intercambiam informação. O progresso do algoritmo
  53 depende de dois elementos: o progresso individual de cada um dos
  54 processos, e a troca de informação entre eles. Os distintos modelos,
  55 i.e. presunções, que descrevem características específicas desses
  56 elementos no sistema são:
  57
  58 \begin{itemize}
  59 \item \textit{Modelo de intercomunicação dos processos}, que pode-se
  60   realizar através da troca de mensagens (enviando mensagens
  61   ponto-a-ponto ou um-para-varios, além de se classificar pelo ordem de
  62   entrega, dependendo se mantem o ordem de envio, i.e. FIFO, ou não),
  63   ou memoria compartilhada (escrevendo e lendo de variáveis comuns).
  64 \item \textit{Modelo temporal}, o qual distingue três possibilidades:
  65   \begin{inparaenum} [\itshape a\upshape)]
  66   \item sistemas síncronos, onde todos os processos executam cada
  67     passo do algoritmo simultaneamente e o tempo de demora é
  68     conhecido;
  69   \item sistemas assíncronos, onde cada um dos processos pode tomar
  70     uma quantidade indeterminada de tempo para executar cada passo do
  71     algoritmo;
  72   \item sistemas parcialmente síncronos, onde é possivel fazer algumas
  73     presunções sobre o tempo de demora de algumas operações mas não se
  74     garante que os processos executam simultaneamente os passo do
  75     algoritmo.
  76   \end{inparaenum}
  77 \item \textit{Modelo de falhas}, os processo do sistema podem falhar
  78   de distintas maneiras, as quais podem se classificar em:
  79   \textit{falha-e-para}, onde o processo falha e deixa de participar
  80   no sistema; \textit{falha-e-recuperação}, onde o processo falha mas
  81   em algum momento no futuro volta ao sistema; \textit{falha de
  82     omissão}, onde o processo não realiza algumas ações
  83   arbitrariamente, e.g. enviar uma mensagem; e \textit{falha
  84     bizantina} onde o comportamento do processo é aleatório. Além dos
  85   processos, os canais de comunicação tambem podem apresentar falhas
  86   por exemplo, no caso da comunicação por envio de mensagens, perder,
  87   duplicar ou corromper as mensagens.
  88 \end{itemize}
  89
  90 É claro que, as distintas combinações dos modelos apresentados, da
  91 lugar a uma multiplicidade de ambientes muito amplia e, portanto, não
  92 é possivel, ou ao menos prático, desenhar algoritmos distribuídos que
  93 sejam capaceis de se executar em quaisquer modelo; é por isso que
  94 somente pode se evaluar a correção dos algoritmos se suas presunções
  95 sob o sistema são válidas. Por exemplo, um algoritmo desenhado para um
  96 sistema de memoria compartilhada, síncrono e sem falhas não vai
  97 funcionar, ainda seja correto, se o sistema é assíncrono, utiliza
  98 troca de mensagens ponto-a-ponto é apresenta falhas bizantinas.
  99
 100 Os modelos supostos pelo algoritmo vão a definir as caraterísticas do
 101 sistema, portanto se são muito restritivos, a aplicabilidade do
 102 algoritmo é menor. Aqueles modelos que possuam condições mais estritas
 103 fazem o desenvolvimento e as provas de correção dos algoritmos mais
 104 simples, já que eles garantem comportamentos mais predecibles; mas,
 105 construir um sistema que cumpra aquelas condições fortes é muito
 106 complexo ou altamente custoso, além de não ser possível algumas
 107 vezes. Portanto a eleição de modelos mais relaxados é preferível,
 108 embora introduzam uma maior complexidade, eles apresentam condições
 109 mais próximas das alcançáveis na realidade.
 110
 111 Os algoritmos no modelo temporal assíncrono não dependem do tempo para
 112 a sua correção, é portanto são preferíveis, já que na prática esta
 113 caraterística temporal é introducida pelas variações no desempenho do
 114 sistema \cite{chandra96c}. Além da assincronia, a tolerancia a falhas
 115 é outra caraterística importante, já que seja por errors no software
 116 ou por falhas do hardware, elas vão ocurrir. A dificultade da
 117 assincronia com falhas de processo é que existem problemas,
 118 e.g. acordo, solucionaveis em outros modelos, e.g. síncrono, que não
 119 possuim solução direita \cite{dwork88}. Neste caso, um dos método
 120 utilizados para fazer solucionavel o problema é acrecentar o modelo,
 121 por exemplo com o uso de detetores de falhas. Informalmente, um
 122 detetor de falhas é um módulo que fornece informação (não
 123 necessariamente correta) sob o estado atual dos processos, e.g. se
 124 estão ativos ou não.
 125
 126 Neste projeto tem-se interesse no comportamento dos detetores de
 127 falhas nos sistemas assíncronos com modelo de falhas com
 128 recuperação. Para um processo se recuperar, ele tem que executar os
 129 seguentes passos:
 130 \begin{inparaenum}[\itshape a\upshape)]
 131 \item recuperação do estado antes da falha, e
 132 \item atualização do estado ao atual do sistema.
 133 \end{inparaenum}
 134 Dependendo das carateristicas do sistema, um processo pode obter a
 135 informação necessaria para realizar aqueles passos da propia memoria
 136 estável ou dos outros processos. Neste contexto, a nossa questão de
 137 pequisa é a seguente:
 138
 139 \begin{quotation}
 140   \noindent \textit{Qual é o método de obtenção da informação
 141     necessaria para a recuperção de processos após falhas com melhor
 142     desempenho e menor impacto no sistema?}
 143 \end{quotation}
 144
 145 O uso da memoria estável requiere que os processos, regularmente,
 146 fazam \textit{checkpoints}, o qual é uma carga constante para o
 147 sistema e, além disso o tempo de recuperação vai depender da
 148 velocidade da memoria estável. Outra opção é a utilização dos demais
 149 componentes do sistema como repositorios da data gerada pelos
 150 checkpoints, o qual substitue a latencia da memoria estável pela
 151 latencia da rede que pode ser menor. O problema é que a solução
 152 anterior é menos robusta, já que o número de falhas tem um impato
 153 direito na quantidade de mensagems enviados é, alem disso, não é
 154 possível suportar uma falha massiva dos processos. Por isso é
 155 necessario evaluar qual método tem melhores resultados e em quais
 156 escenarios.
 157
 158 O restante do projeto é organizado da seguinte forma. \todo[noline]{Atualizar}
 159 A próxima seção contextualiza este projeto dentro da pesquisa já
 160 realizada no Laboratório de Sistemas Distribuídos sobre replicação
 161 ativa.  A seção~\ref{sec:teoria} apresenta os fundamentos sobre
 162 modelos computacionais para algoritmos distribuídos, com ênfase no
 163 aspecto temporal da computação distribuída.  A
 164 seção~\ref{sec:treplica} apresenta a plataforma empregada para testes
 165 e a avaliação das variações de Paxos e Fast Paxos elaboradas,
 166 denominada Treplica.  Na seção~\ref{sec:proposta} são discutidos,
 167 ainda em caráter inicial, os argumentos que dão sustentação ao nosso
 168 projeto, assim como os modelos que podem ser empregados para ajudar na
 169 resposta da nossa pergunta de pesquisa.  Finalmente, a
 170 seção~\ref{sec:metodologia} apresenta concisamente a metodologia de
 171 pesquisa, as etapas a serem cumpridas no projeto e o seu respectivo
 172 conograma.
 173
 174 \section{Contexto da Pesquisa}
 175 \label{sec:contexto}
 176 % O problema foi descrito por Aguilera,
 177 % Chen e Toueg \cite{springerlink:aguilera98} e pode-se descrever,
 178 % informalmente, assim: os detetores de falhas tradicionais não são
 179 % adecuados para o modelo de falhas no qual os processos podem-se
 180 % recuperar já que eles, pela sua definição, devem de
 181 % \textit{suspeitar}, i.e. supoer que o processo caiu, permanentemente
 182 % dos processos com falhas, ainda se eles voltam ao sistema,
 183 % excluindo-lhes.
 184
 185 O problema do obter consenso é um dos mais fundamentais da área de
 186 algoritmos distribuídos. Informalmente, resolver o problema do
 187 consenso exige que todos os processos corretos do sistema
 188 \textit{decidam} um único valor a partir de valores iniciais propostos
 189 por cada um deles. Fisher et al. \cite{fischer85} mostraram que o
 190 problema não pode-se resolver de maneira determinista em um sistema
 191 distribuído assíncrono com apenas um processo falhado.
 192
 193 O \textit{broadcast} confiável é, informalmente, uma primitiva de
 194 comunicação assíncrona de alto nível que garanta as seguentes três
 195 propriedades \cite{chandra96}:
 196 \begin{inparaenum}[\itshape a\upshape)]
 197 \item todos os processos corretos entregam o mesmo conjunto de
 198   mensagens,
 199 \item todas as mensagens enviadas por um processo correto são
 200   entregues,
 201 \item mensagens falsas nunca são entregues.
 202 \end{inparaenum}
 203 Além disso, no caso possa-se garantir que os mensagens são entregues
 204 no mesmo ordem por todos os processos, a primitiva chama-se
 205 \textit{broadcast} com ordenação total ou \textit{broadcast} atômico
 206 \cite{Defago:2004}. Foi mostrado por Chandra e Toueg \cite{chandra96}
 207 que o problema do consenso uniforme e o \textit{broadcast} atômico em
 208 sistemas assíncronos com falhas de parada são equivalentes,
 209 i.e. quaisquer algoritmo que possa resolver um deles também pode-se
 210 adaptar para resolver o outro. Portanto, o \textit{broadcast} atômico
 211 é sujeito ao mesmo resultado de impossibilidade de Fischer et al.
 212
 213 Existem distintas soluções para evitar o resultado de impossibilidade:
 214 o uso de randomização \cite{Chor89}, definição de problemas mais
 215 deveis e suas soluções \cite{dolev87}, entre outros. Nós vamos a
 216 centrar em detetores de falhas não confiáveis
 217 \cite{chandra96c,chandra96}. Informalmente, os detetores de falhas são
 218 um conjunto de módulos distribuídos, um por processo do sistema, que
 219 possuem uma visão do sistema, i.e. uma listagem dos processos que são
 220 suspeitos de ter falhado, mas não precisasse garantir que a visão
 221 seja correta, e.g. pode-se incluir na lista de suspeitos processos que
 222 não falharam. Os detetores de falhas aumentam o modelo do sistema assíncrono
 223 e permitem resolver o problema do consenso (\textit{broadcast}
 224 atômico) em sistemas com falhas de processo.
 225
 226 Uma das deficiências da proposta de Chandra e Toueg
 227 \cite{chandra96c,chandra96}, é que consideram as falhas como
 228 permanentes, i.e. os processos não podem-se recuperar. É claro que na
 229 prática os processos podem falhar e se recuperar múltiplas vezes,
 230 Aguilera et al. \cite{springerlink:aguilera98} propõe um novo tipo
 231 de detetores de falhas que não retornam uma lista de processos
 232 suspeitos de ter falhado mas uma lista dos processos que podem estar
 233 funcionando corretamente mais uma estimativa do número de vezes que
 234 ele falho até o momento.
 235
 236 \section{Fundamentação Teórica}
 237 \label{sec:teoria}
 238
 239 \section{Treplica}
 240 \label{sec:treplica}
 241
 242 \section{Proposta de pesquisa}
 243 \label{sec:proposta}
 244
 245 \section{Metodologia Científica}
 246 \label{sec:metodologia}
 247
 248 \todo[noline]{Fill}Esta seção traz a metodolodia de pesquisa: teoria, experimentos, etc.
 249
 250 \subsection{Tarefas e cronograma}
 251 \label{sec:planodetrabalho}
 252
 253 Esta seção detalha as tarefas planejadas para o desenvolvimento do
 254 Mestrado e o conograma proposto (Tabela~\ref{projtimetable}):
 255 \todo[noline]{check times and items}
 256
 257 \begin{enumerate}
 258 \addtolength{\itemsep}{-0.35\baselineskip}
 259
 260 % Ago-Julho 2010
 261 \item \label{t1} Créditos em disciplinas
 262
 263 % Abril-Julho 2010
 264 \item \label{t2} Revisão bibliográfica
 265
 266 % Maio-Ago 2010
 267 \item \label{t3} Estudo dirigido
 268
 269 % Jul-Ago 2010
 270 \item \label{t4} Elaboração do projeto de mestrado
 271
 272 % Ago 2010 - Jul 2011
 273 \item \label{t5} Estudo comparativo de algoritmos
 274
 275 % Jan 2011 - Dez 2011
 276 \item \label{t6} Proposta, análise e prova de algoritmos.
 277
 278 % Dez 2011 - Dez 2011
 279 \item \label{t7} Implementação da solução sobre a plataforma
 280 Tréplica~\cite{vieira08a}.  Testes de desempenho da solução com
 281 diversas cargas de trabalho, tanto na presença como na ausência de
 282 falhas de processos.
 283
 284 % Mai 2011 - Jan 2012
 285 \item \label{t8} Escrita da Dissertação de Mestrado
 286
 287 % Fev 2012 - Mar 2012
 288 \item \label{t9} Defesa da Dissertação de Mestrado
 289
 290 % Dez 2010 - Mar 2012
 291 \item \label{t10} Escrita e submissão de artigos para publicação
 292
 293 \end{enumerate}
 294
 295 \begin{table}[h]
 296 \begin{center}
 297 \setlength{\tabcolsep}{1.5pt}
 298 \begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
 299   &  \multicolumn{5}{c|}{\scriptsize 2010} & \multicolumn{12}{c|}{\scriptsize 2011} & \multicolumn{7}{c|}{\scriptsize 2012} \\ \cline{2-25}
 300 {\small Tarefas } &
 301 \rotatebox{90}{\scriptsize ago } &
 302 \rotatebox{90}{\scriptsize set } &
 303 \rotatebox{90}{\scriptsize out } &
 304 \rotatebox{90}{\scriptsize nov } &
 305 \rotatebox{90}{\scriptsize dez } &
 306 \rotatebox{90}{\scriptsize jan } &
 307 \rotatebox{90}{\scriptsize fev } &
 308 \rotatebox{90}{\scriptsize mar } &
 309 \rotatebox{90}{\scriptsize abr } &
 310 \rotatebox{90}{\scriptsize mai } &
 311 \rotatebox{90}{\scriptsize jun } &
 312 \rotatebox{90}{\scriptsize jul } &
 313 \rotatebox{90}{\scriptsize ago } &
 314 \rotatebox{90}{\scriptsize set } &
 315 \rotatebox{90}{\scriptsize out } &
 316 \rotatebox{90}{\scriptsize nov } &
 317 \rotatebox{90}{\scriptsize dez } &
 318 \rotatebox{90}{\scriptsize jan } &
 319 \rotatebox{90}{\scriptsize fev } &
 320 \rotatebox{90}{\scriptsize mar } &
 321 \rotatebox{90}{\scriptsize abr } &
 322 \rotatebox{90}{\scriptsize mai } &
 323 \rotatebox{90}{\scriptsize jun } &
 324 \rotatebox{90}{\scriptsize jul } \\ \hline
 325
 326 \ \ \ref{t1}  & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
 327 \ \ \ref{t2}  &    & \f & \f & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
 328 \ \ \ref{t3}  &    &    &    & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
 329 \ \ \ref{t4}  &    &    &    & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
 330 \ \ \ref{t5}  &    &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f &    &    &    &    &    &    &    \\ \hline
 331 \ \ \ref{t6}  &    &    &    &    &    &    &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f &    &    \\ \hline
 332 \ \ \ref{t7}  &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    & \f & \f & \f & \f & \f & \f &    &    \\ \hline
 333 \ \ \ref{t8}  &    &    &    &    &    &    &    &    &    &    &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f   &    \\ \hline
 334 \ \ \ref{t9}  &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    & \f & \f \\ \hline
 335 \ \ \ref{t10} &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f \\ \hline
 336 \end{tabular}
 337 \caption{Cronograma do projeto}
 338 \label{projtimetable}
 339 \end{center}
 340 \end{table}
 341
 342
 343 \begin{small}
 344 \phantomsection
 345 \addcontentsline{toc}{section}{\bibname}
 346 \bibliographystyle{plain}
 347 \bibliography{mscTemplate}
 348 \end{small}
 349
 350 \end{document}