Abstract done

[mymsc.git] / mscMonografia.tex

\documentclass[10pt]{article}

\usepackage[top=3cm, bottom=3cm, left=3cm, right=3cm]{geometry}
\usepackage{todonotes}
\usepackage{times}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{url}
\usepackage{paralist}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{setspace}
\usepackage{paralist}

\newcommand{\mytitle}{Título do Trabalho de Mestrado} %PT
\newcommand{\f}{$\blacksquare$}

\hypersetup{
     pdftitle={\mytitle},
     pdfauthor={Rodrigo Eduardo Lazo Paz},
     pdfdisplaydoctitle=true,
     pdfborder=0 0 0
}

\title{\mytitle}

\author{
Rodrigo Eduardo Lazo Paz\\%\thanks{Grants.} \\
IC, Unicamp \\
Campinas, Brasil \\
{\small \url{rodrigo.lazo@students.ic.unicamp.br}} \\
\and
Luiz E.  Buzato \\ %\thanks{Identificação de projetos aqui.}\\
IC, Unicamp \\ Campinas, Brasil \\ {\small
\url{buzato@ic.unicamp.br}}
}

\hyphenation{par-ti-cu-lar-men-te}
\hyphenation{su-fi-ci-en-tes}

\begin{document}
\doublespacing

\maketitle

\begin{abstract}
  \noindent A demanda atual por serviços fornecidos pela Internet, com
  a promessa de ubiquidade de aceso físico e temporal à informação, é
  enorme; ainda em redes privadas restringidas a uma organização, o
  volume de informação vital centralizada em serviços compartilhados
  vai em aumento. Ambos cenários tem em comum a necessidade de
  aplicações escaláveis e altamente disponíveis. Os sistemas
  distribuídos replicados, tolerantes a falhas, são uma solução;
  nestos, os processos podem cair, e sua carga de trabalho se
  distribuir aos demais até que voltem, mantendo a aplicação
  disponível durante o tempo todo. Porém, dependendo do tráfego, o
  desempenho pode-se degradar notavelmente. Portanto, é fundamental
  reduzir ao mínimo o tempo da recuperação. O armazenamento da
  informação requerida na memoria volátil de processos remotos é uma
  alternativa atrativa, de melhor desempenho ao uso da memoria estável
  local, mas sacrifica-se a persistência dos dados. Neste sentido, no
  presente projeto propomos a avaliação minuciosa de múltiplas
  configurações de sistemas distribuídos replicados com armazenamento
  híbrido, tal que minimize-se o uso de dispositivos de armazenamento
  de alta latência durante o procedimento de recuperação sem
  sacrificar a consistência. \todo[noline]{Includir implementação do
    detetor de falhas do aguilera?}Os resultados serão aplicados na
  melhora da biblioteca de replicação para a construção de aplicações
  de alta disponibilidade Tréplica, desenvolvida no Laboratório de
  Sistemas Distribuídos do Instituto de Computação da Universidade
  Estadual de Campinas.

\end{abstract}

\newpage

\section{Introdução}
\label{sec:introduction}

Algoritmos distribuídos são aqueles desenhados para se executar em
sistemas compostos por um conjunto interconectado de processos
autônomos que intercambiam informação. O progresso do algoritmo
depende de dois elementos: o progresso individual de cada um dos
processos, e a troca de informação entre eles. Os distintos modelos,
i.e.\ presunções, que descrevem características específicas desses
elementos no sistema são:

\begin{itemize}
\item \textit{Modelo de intercomunicação dos processos}, que pode-se
  realizar através da troca de mensagens (enviando mensagens
  ponto-a-ponto ou um-para-varios, além de se classificar pelo ordem de
  entrega, dependendo se mantem o ordem de envio, i.e.\ FIFO, ou não),
  ou memoria compartilhada (escrevendo e lendo de variáveis comuns).
\item \textit{Modelo temporal}, o qual distingue três possibilidades:
  \begin{inparaenum} [\itshape a\upshape)]
  \item sistemas síncronos, onde todos os processos executam cada
    passo do algoritmo simultaneamente e o tempo de demora é
    conhecido;
  \item sistemas assíncronos, onde cada um dos processos pode tomar
    uma quantidade indeterminada de tempo para executar cada passo do
    algoritmo;
  \item sistemas parcialmente síncronos, onde é possivel fazer algumas
    presunções sobre o tempo de demora de algumas operações, mas não
    se garante que os processos executam simultaneamente os passo do
    algoritmo.
  \end{inparaenum}
%inparablank?
\item \textit{Modelo de falhas}, os processo do sistema podem falhar
  de distintas maneiras, as quais podem se classificar em:
  \textit{falha-e-para}, onde o processo falha e deixa de participar
  do sistema; \textit{falha-e-recuperação}, onde o processo falha,
  mas, em algum momento no futuro, volta ao sistema; \textit{falha de
    omissão}, onde o processo não realiza algumas ações
  arbitrariamente, e.g.\ enviar uma mensagem; e \textit{falha
    bizantina} onde o comportamento do processo é aleatório. Além dos
  processos, os canais de comunicação tambem podem apresentar falhas
  por exemplo, no caso da comunicação por envio de mensagens, perder,
  duplicar ou corromper as mensagens.
\end{itemize}

É claro que, as distintas combinações dos modelos apresentados, da
lugar a uma multiplicidade de ambientes muito amplia e, portanto, não
é possivel, ou ao menos prático, desenhar algoritmos distribuídos que
sejam capaceis de se executar em quaisquer modelo; é por isso que
somente pode se evaluar a correção dos algoritmos se suas presunções
sobre o sistema são válidas. Por exemplo, um algoritmo desenhado para um
sistema de memoria compartilhada, síncrono e sem falhas não vai
funcionar, ainda seja correto, se o sistema é assíncrono, utiliza
troca de mensagens ponto-a-ponto é apresenta falhas bizantinas.

Os modelos supostos pelo algoritmo vão a definir as caraterísticas do
sistema, portanto, se são muito restritivos, a aplicabilidade do
algoritmo é menor. Aqueles modelos que possuam condições mais estritas
fazem o desenvolvimento e as provas de correção dos algoritmos mais
simples, já que eles garantem comportamentos mais predecibles; mas,
construir um sistema que cumpra aquelas condições fortes é muito
complexo ou altamente custoso, além de não ser possível algumas
vezes. Portanto, a eleição de modelos mais relaxados é preferível,
embora introduzam uma maior complexidade, eles apresentam condições
mais próximas das alcançáveis na realidade.

Os algoritmos no modelo temporal assíncrono não dependem do tempo para
a sua correção é, portanto, são preferíveis, já que na prática esta
caraterística temporal é introduzida pelas variações no desempenho do
sistema~\cite{Chandra:1996:WFD:234533.234549}. Além da assincronia, a
tolerância a falhas é outra caraterística importante, já que, seja por
erros no software ou por falhas do hardware, elas vão acontecer. A
dificuldade da assincronia com falhas de processo é que existem
problemas solucionáveis em outros modelos que não são resolvíeis,
e.g.\ consenso no modelo síncrono~\cite{dwork88}. Nestos casos, uma
solução pode-se alcançar só se os requerimentos de correção são
debilitados, o modelo é fortalecido, ou
ambos\cite{Lynch:1996:DA:525656}.

Os detetores de falhas são, informalmente, módulos distribuídos que
fornecem informação (não necessariamente correta) sobre o estado atual
dos processos no sistema, i.e.\ quais são suspeitos de estar
inativos. Os detetores acrescentam o modelo assíncrono, possibilitando
a solução de problemas como o problema de consenso
distribuído~\cite{Chandra:1996:UFD:226643.226647}.

No modelo de \textit{falha-e-recuperação} os processos podem voltar ao
sistema e, portanto, precisam de armazenar, com segurança, suficiente
informação para voltar a seu estado anterior se uma falha acontecer;
no caso contrario, se fossem amnésicos, pode-se argumentar que um
processo em recuperação é indistinguível de um processo novo,
i.e.\ \textit{falha-e-para}.

Os processos só podem armazenar, de maneira persistente, os dados
necessária para se recuperar em dois lugares: localmente, em sua
memoria estável, e remotamente, em outro processo. No primeiro caso, o
custo é determinado pela latência do disco; no segundo caso, é
determinado pela latência da rede mais o custo do aceso à informação,
i.e.\ memoria volátil ou memoria estável. Neste contexto, a nossa
questão de pequisa é a seguente:

\begin{quotation}
  \noindent \textit{Qual é o método, ou combinação de métodos, de
    armazenamento e obtenção da informação necessaria para a
    recuperção dos processos após falhas com melhor desempenho e menor
    impacto no sistema?}\todo{pergunta correta?}
\end{quotation}

A recuperação é um procedimento que volta o estado de um processo que
falhou, a um estado anterior à falha. Os dados que permitem aquela
operação, normalmente uma copia do estado anterior, são chamados de
\textit{checkpoints}~\cite{Randell:1978:RIC:356725.356729}. Os
processos precisam ter \textit{checkpoints} regulais, i.e.\ armazenar
os dados de maneira persistente, portanto, o custo da solução
escolhida, tem um impacto no sistema ainda durante os períodos sem
falhas. Além disso, tem se que considerar a robustez: se a informação
é armazenada só na memoria volátil do sistema, não pode-se suportar
uma falha massiva dos processos. Portanto, a adequação da escolha
depende dos cenários assumidos.

O restante do projeto é organizado da seguinte forma. A próxima seção
contextualiza este projeto dentro da pesquisa já realizada no
Laboratório de Sistemas Distribuídos sobre replicação ativa. A
seção~\ref{sec:teoria} apresenta os fundamentos sobre modelos
computacionais para algoritmos distribuídos, com ênfase no aspecto
temporal da computação distribuída. A seção~\ref{sec:treplica}
apresenta a plataforma empregada para testes e a avaliação das
variações de Paxos e Fast Paxos elaboradas, denominada Treplica. Na
seção~\ref{sec:proposta} são discutidos, ainda em caráter inicial, os
argumentos que dão sustentação ao nosso projeto, assim como os modelos
que podem ser empregados para ajudar na resposta da nossa pergunta de
pesquisa. Finalmente, a seção~\ref{sec:metodologia} apresenta
concisamente a metodologia de pesquisa, as etapas a serem cumpridas no
projeto e o seu respectivo conograma. \todo[noline]{corregir
  referencias na versão final}

\section{Contexto da Pesquisa}
\label{sec:contexto}
\todo{Que conteudo é adequado? trabalhos relacionados?}

\section{Fundamentação Teórica}
\label{sec:teoria}
Fornecer um serviço altamente disponível empregando múltiplos
processos replicados é uma técnica bem
conhecida~\cite{Schneider:1990:IFS:98163.98167}. Existem duas formas
de replicação: a ativa, ou de máquina de
estados~\cite{lamport1978implementation}, onde todos os processos
recebem e executam as mesmas solicitações, no mesmo ordem; e a
passiva, onde um único processo recebe todas as solicitações, as
aplica localmente, e depois seu estado é copiado pelas demais
réplicas. Um dos métodos mais utilizados para a implementação da
replicação ativa é a aplicação de algoritmos de
consenso~\cite{Lamport:1998:PP:279227.279229,
  Schneider:1990:IFS:98163.98167,Oki:1988:VRN:62546.62549}.

Nesta seção discute-se a fundamentação teórica da solução de
replicação ativa, baseada em consenso com processos que podem falhar e
voltar ao sistema, sobre a qual nossa proposta de pesquisa é
desenvolvida. \todo{paragrafo ok?}

\subsection{Modelo do sistema e notação}
\label{sec:notacao}
O modelo suposto neste trabalho é assíncrono, portanto não existe
presunção nenhuma acerca do tempo de demora da comunicação e do
processamento. Todos os processos no sistema estão conectados, e a
comunicação é através de mensagens, os quais podem se perder durante o
envio. Os processos podem falhar e voltar ao sistema depois. Após
falhar, os processos perdem seu estado atual, mas eles podem armazenar,
em sua memoria estável, informação de recuperação.

\begin{table}[h]
  \small
  \centering
  \begin{tabular}{|l|p{5cm}|l|p{5cm}|}
    \hline
    \(\Pi\) & Conjunto de processos. &
    \(\mathcal{M}\) & Conjunto de mensagens. \\
    \(sender(m)\) & Processo remitente de \(m\). &
    \(Dest(m)\) & Conjunto destinatario de \(m\).  \\
    \(\Pi_{sender}\) & Conjunto de processos que podem enviar mensagens. &
    \(\Pi_{dest}\) & Conjunto de processos que podem receber mensagens. \\
    \(\mathcal{T}\) & Relógio global. &
    \(F(t)\) & Conjunto de processos caidos no tempo \(t\). \\
    \(Bom(F)\) & Conjunto de processos bons (em F). &
    \(Ruim(F)\) & Conjunto de processos ruins (em F). \\
    \textit{Instável}\((F)\) & Conjunto de processos instáveis (em F).& & \\
    \hline
  \end{tabular}
  \caption{Notação}
  \label{tab:notacao}
\end{table}

Neste trabalho vamos a seguir a notação utilizada por Défago, Schiper
e Úrban~\cite{Defago:2004}, a qual está resumida na
tabela~\ref{tab:notacao}. Seja \(\Pi = \{P_1, \ldots, P_n\}\) um
conjunto de \(n\) processos que conformam o sistema. A comunicação é
baseado no envio de mensagens, onde \(\mathcal{M}\) é o conjunto de
mensagens válidos, \(sender(m) \in \Pi \) designa o processo
originador do mensagem \(m\) e \(Dest(m) \subseteq \Pi \) é o conjunto
de processos não vazio ao qual o mensagem \(m\) e enviado. Além disso,
seja \(\Pi_{sender}\) o conjunto de todos os processos que podem
enviar uma mensagem válida \(m \in \mathcal{M}\), e seja \(\Pi_{dest}
\stackrel{\mathrm{def}}{=} \bigcup_{m \in \mathcal{M}} Dest(m)\) o
conjunto de destinos possíveis para as mensagens válidas.

Para simplifcar a apresentação do modelo, suponhase a existemcia de um
relogio discreto global \(\mathcal{T}\) com rango de valores dos
números naturais; os processos não têm conhecimento ou contato como
ele.

A seguinte classificação dos processos em função a seu comportamento
de falhas é tomada de Aguilera, Chen e
Toueg~\cite{springerlink:aguilera98}. Seja \(F\) uma função de
\(\mathcal{T}\) a \(2^\Pi\), tal que \(F(t)\) representa o conjunto
dos processos que não estão presentes no sistema no tempo \(t\). Um
processo está \textit{ativo no tempo} \(t\) (em \(F\)) se \(p \in
F(t)\), e está \textit{inativo no tempo} \(t\) (em \(F\)) no caso
contrario. Um processo \textit{cai} no tempo \(t\) se está ativo no
tempo \(t-1\) e inativo no tempo \(t\)\footnote{Um processo
  \textit{cai} no tempo \(t=0\) se está inativo no tempo \(t=0\) }. Um
processo se \textit{recupera} no tempo \(t\) se está inativo no tempo
\(t-1\) e está ativo no tempo \(t\). Os processos podem se classificar
(de acordo com \(F\)) como:

\begin{itemize}
\item \textit{Sempre Ativo}: O processo \(p\) nunca cai.
\item \textit{Eventualmente Ativo}: O processo caiu pelo menos uma
  vez, mas após algum momento \(t\), o processo está sempre
  ativo. \todo[noline]{traduções corretas?}
\item \textit{Eventualmente Inativo}: Após algum momento \(t\), o
  processo é está sempre inativo.
\item \textit{Instável}: O processo cai e volta um número infinito de
  vezes.
\end{itemize}

Um processo é \textit{bom}\todo{é bom o termo correto?}~(em \(F\)) se
é sempre ativo ou eventualmente ativo. Um processo é \textit{ruim} (em
\(F\)) se é eventualmente inativo ou instável. Denota-se \(Bom(F)\),
\(Ruim(F)\) \todo{é ruim o termo correto?} e \textit{Instável}\((F)\)
aos conjuntos de processos (em \(F\)) bons, ruins e instáveis,
respetivamente.

\subsection{Consenso}
\label{sec:consenso}
O problema do consenso~\cite{Pease:1980:RAP:322186.322188} é um dos
mais fundamentais da área dos algoritmos distribuídos. Considere um
conjunto \(\Pi = \{p_1,\ldots,p_n\}\) de \(n\) processos; seja \(V =
\{v_1^0, \ldots, v_n^0\}\) o conjunto de estados inicias dos
processos, tal que \(v_i^0\) é o valor inicial do processo
\(p_i\). Eventualmente cada processo \(p_i\) tem que \textit{decidir}
um valor \(decide(p_i) = v_i\), tal que todos os processos corretos
concordem neste, e as seguintes propriedades sejam
satisfeitas~\cite{springerlink:aguilera98}:

\begin{description}
\item[Validade uniforme] se um processo decide $v$, então algum
  processo o propôs, i.e.\ \(\forall p \in \Pi(decide(p) \in V)\).
\item[Consenso] Todos os processos \textit{bons} decidem o mesmo
  valor, i.e.\ \(\exists ! v \in V ~\forall p \in Bom(F) (decide(p_i) = v)\).
\todo[noline]{expresões matemáticas corretas?}
\item[Terminação] Se todos os processos \textit{bons} propõem um
  valor, eventualmente um daqueles é escolhido, i.e.\ \(\exists ! v
  \in V~\forall p \in Bom(F)~\exists T \in \mathcal{T}~\forall t, t' > T
  (v^0 \in V \wedge t < t' \Rightarrow decide(p) = v)\).
\end{description}

Existe uma variação mais estrita, o consenso
uniforme~\cite{Neiger:1990:AIF:83334.83337}, que impõe restrições às
escolhas dos processos \textit{ruins}:

\begin{description}
\item[Consenso uniforme] Os processos não \textit{decidem} valores
  distintos, i.e.\ \(\exists ! v \in V ~\forall p \in \Pi (decide(p_i) = v)\).
\end{description}

No caso síncrono sem falhas, o problema é facilmente
resolvible~\cite{Lynch:1996:DA:525656}, porém, o resultado de
impossibilidade obtido por Fischer, Lynch e Patterson~\cite{fischer85}
mostra que o problema não pode-se resolver de maneira determinista num
sistema distribuído assíncrono com apenas um processo falho. Existem
distintas soluções propostas: o uso de randomização~\cite{Chor89},
definição de problemas mais débeis e suas soluções~\cite{dolev87},
detetores de falhas não
confiáveis~\cite{Chandra:1996:WFD:234533.234549,
  Chandra:1996:UFD:226643.226647}, etc.

\paragraph{Algoritmo de consenso Paxos}
O algoritmo de consenso Paxos, originalmente proposto por
Lamport~\cite{Lamport:1998:PP:279227.279229}, é um dos mais utilizados
na prática~\cite{Burrows:2006:CLS:1298455.1298487,
  Camargos:2007:SMH:1272998.1273036,
  MacCormick:2004:BAF:1251254.1251262,
  Saito:2004:FBD:1024393.1024400}. Neste algoritmo, os processos podem
assumir um o mais dos seguintes papéis:
\begin{inparaenum}[\itshape a\upshape)]
\item \textit{proponente}, que propor valores;
\item \textit{receptor}, que escolhe um único valor; e
\item \textit{aprendiz}, que aprende o valor escolhido.
\end{inparaenum}
O algoritmo pode precisar uma ou varias rodadas para alcançar o
consenso, cada uma identificada pelo número de rodada \(r\). No começo
de cada rodada os proponentes eligem um coordenador, o qual avalia se
a maioria \(\lfloor n/2 \rfloor +1\) dos \(n\) receptores participou
da rodada anterior \(r-1\), e, portanto, o consenso foi alcançado. No
caso contrario, o algoritmo continua em duas fases com dois passos
cada um:

\begin{itemize}
\item \textit{Fase 1a}, o coordenador invita aos receptores a
  participar da rodada \(r\), os quais aceitam somente se não
  participam de uma rodada \(r' \geq r\). A partir desse momento, os
  receptores que aceitaram o convite \textit{prometem} não participar
  em outra rodada menor, \(r'' < r\).
\item \textit{Fase 1b}, os receptores que aceitaram o convite enviam
  ao coordenador o valor da última proposta que votaram e o número de
  rodada na qual aquelo aconteceu, ou \textit{nulo} no caso contrario.
\item \textit{Fase 2a}, se suficientes respostas forem recebidas pelo
  coordenador dos receptores, \(\lfloor n/2 \rfloor +1\), ele escolhe
  dentro dos valores retornados um que poderia ter sido
  \textit{decidido} em uma rodada \(r' < r\), ou no caso seja
  \textit{nulo}, ele escolhe a proposta feita pelos proponentes. Logo,
  ele pede aos receptores que votem na proposta escolhida.
\item \textit{Fase 2b}, após receber o pedido de votar do coordenador,
  e sempre que não houveram \textit{prometido} participar na rodada
  \(r\), os receptores votam enviando o número de rodada \(r\) e o
  valor aos aprendizes.
\item O consenso é alcançado no momento que suficientes receptores,
  \(\lfloor n/2 \rfloor +1\), votam na fase 2b.
\end{itemize}

\todo[noline]{Multipaxos? Fast Paxos? devo incluir?}Uma caraterística
interessante do Paxos é que sua tolerância a falhas fundamenta-se no
uso de \textit{quorum} de processos, e não no conhecimento do estado
atual dos outros processos, como no caso dos detetores de falhas. O
algoritmo garante que se um valor é eleito, a escolha não muda,
portanto um processo que caiu e volta, pode aprendê-lo. Para que isso
aconteça, cada participante do algoritmo tem que armazenar
persistentemente as rodadas nas quais ele participou e os valores que
votou.

\subsection{Broadcast de ordem total}
\label{sec:broadcast}
% seção muito longa?
O \textit{broadcast} de ordem total, ou \textit{broadcast} atômico, é
uma primitiva de comunicação assíncrona de alto nível que garanta que
as mensagens enviadas a um conjunto de processos sejam recebidas, no
mesmo ordem, por os membros todos~\cite{Defago:2004}. O problema é
definido formalmente em função de duas primitivas,
\textit{TO-broadcast}\((m)\) e \textit{TO-deliver}\((m)\), onde \(m
\in \mathcal{M}\) e uma mensagem. Quando um processo \(p\) executa
\textit{TO-broadcast}\((m)\) (respectivamente,
\textit{TO-deliver}\((m)\)) diz-se que o processo \(p\)
\textit{TO-broadcasts} \(m\) (respectivamente, \textit{TO-delivers}
\(m\)) \todo{tem se que incluir esta aclaração, não?}. Todas as
mensagens têm identificadores únicos, e levam consigo a identidade de
seu remetente, denotado \textit{sender}\((m)\). Além disso, supomos
que para quaisquer mensagem \(m\), e em quaisquer execução, a chamada
\textit{TO-broadcasts}\((m)\) e feita uma vez só. Neste contexto, o
\textit{broadcast} de ordem total é definido pelas seguintes
propriedades~\cite{Chandra:1996:WFD:234533.234549,hadzilacos94}:

\begin{itemize}
\item \textit{Validade} Se um processo bom \textit{TO-broadcasts} a
  mensagen \(m\), então ele eventualmente \textit{TO-delivers} \(m\).
\item \textit{Acordo uniforme} Se um processo \textit{TO-delivers} uma
  mensagem \(m\), então todos os processos bons eventualmente
  \textit{TO-deliver} \(m\).
\item \textit{Integridade uniforme} Para quaisquer mensagem \(m\),
  cada processo \textit{TO-delivers} \(m\) no máximo uma vez, se
  somente se \(m\) foi \textit{TO-broadcast} por
  \textit{sender}\((m)\) anteriormente.
\item \textit{Ordem total uniforme} Se os processos \(p\) e \(q\)
  \textit{TO-deliver} as mensagens \(m\) e \(m'\), então \(p\)
  \textit{TO-delivers} \(m\) antes de \(m'\), se somente se \(q\)
  \textit{TO-delivers}\(m\) antes de \(m'\).
\end{itemize}

Se a primitiva de comunicação não satisfaz todas ordem total uniforme,
portanto não garanta ordem nenhum, e chamada \textit{broadcast} confiável. No
caso que a primitiva cumpra todas as propriedades prévias, é chamada
uniforme, i.e.\ impõe restrições ao comportamento de todos os
processos, bons e ruins; mas se as propriedades de acordo e
integridade são não uniformes, elas só se aplica aos processos
bons. \todo{e preciso incluir as definições das propriedades não
  uniformes?}

% Não gosto do paragrafo, é uma simples enumeração, não é muito
% legível.
A relação entre o conjunto destino das mensagens enviadas pelo
\textit{broadcast} de ordem total e o conjunto de processos do
sistema, gera a seguinte classificação:
\begin{inparaenum}[\itshape a\upshape)]
\item Se o conjunto destino é igual ao total dos processos no sistema,
  i.e \(\forall m \in \mathcal{M} (Dest(m) = \Pi)\), a primitiva e
  chamada de \textit{broadcast};
\item Se o conjunto destino e um subconjunto dos processos, onde
  distintas mensagens têm distintos conjuntos destinos e o remetente
  pode não ser destinatario, i.e.\ \(\exists m \in \mathcal{M}
  (sender(m) \notin Dest(m)) \wedge \exists m_i,m_j \in \mathcal{M}
  (Dest(m_i) \neq Dest(m_j))\), a primitiva e chamada de multicast.
\end{inparaenum}
Além da distinção anterior, a presença do remetente no conjunto
destino, gera uma classificação adicional:
\begin{inparaenum}[\itshape a\upshape)]
\item Se o remitente é membro dos destinatários, i.e.\ \(\forall m \in
  \mathcal{M} (sender(m) \in Dest(m))\), o grupo é chamado
  \textit{fechado};
\item Se o remitente não precisa pertencer ao grupo destino,
  i.e.\ \(\exists m \in \mathcal{M}(sender(m) \notin Dest(m))\), o
  grupo e chamado \textit{aberto}.
\end{inparaenum}

A conformação do conjunto de processos do sistema não precisa ser
fixa. Se os processos podem entrar, sair e ser removidos dele, é
chamado de grupo dinâmico, contraposto ao grupo estático no qual os
membros não podem mudar durante a execução. Às distintas configurações
do grupo ao longo do tempo são chamadas
\textit{vistas}~\cite{Chockler:2001:GCS:503112.503113}. A primitiva de
comunicação equivalente ao \textit{broadcast} confiável nos grupos
dinâmicos é a sincronia de vista, a qual cumpre as mesmas regras de
validade, integridade uniforme e uma versão de acordo relaxada aos
membros atuais. Uma sincronia de vista que cumpre adicionalmente a
propriedade de ordem total é o equivalente ao \textit{broadcast} de
ordem total nos grupos estáticos.

Existem diversos mecanismos pelos quais pode-se definir a ordem na
qual as mensagens debem ser entregues~\cite{Defago:2004} mas, em todos
eles, são distinguíveis três papéis que os processos podem assumir:
remetente (i.e.\ \(p \in \Pi_{sender}\)), destinatário (i.e.\ \(p \in
\Pi_{dest}\)) e o sequenciador, o qual define o ordem de entrega das
mensagens. Existem as seguintes cinco classes:

\begin{itemize}
\item \textit{Sequenciador fixo} Neste caso, um sequenciador único é
  escolhido e tem a tarefa de ordenar todas as mensagens enviadas pelo
  \textit{broadcast} de ordem total. Possui três variantes:
  \begin{inparaenum}[\itshape a\upshape)]
  \item \textit{unicast-broadcast}, onde o remetente envia as
    mensagens ao sequenciador, e logo ele faz o envio ao destinatários
    na ordem correta;
  \item \textit{broadcast-broadcast}, onde o remetente envia as
    mensagens diretamente aos destinatários, incluindo ao
    sequenciador, e logo ele envia aos destinatários a ordenação de
    entrega das mensagens que eles já armazenam;
  \item \textit{unicast-unicast-broadcast}, onde o remetente envia as
    mensagens ao sequenciador, logo ele envia ao remetente os
    identificador de sequencia das mensagens, i.e.\ sua ordenação, e
    finalmente o remetente envia diretamente as mensagens aos
    destinatários.
  \end{inparaenum}. O algoritmo proposto por Garcia-Molina e
  Spauster~\cite{garcia2002message} é um exemplo.\todo{Os exemplos são
    bons o inecessários?}
\item \textit{Sequenciador móvel} É muito similar ao sequenciador
  fixo, mas o papel de sequenciador é transferível entre um conjunto
  de processos. Na literatura, o principio utilizado pelos
  sequenciadores móveis é equivalente ao \textit{broadcast-broadcast}
  dos sequenciadores fixos~\cite{Defago:2004}. O algoritmo Pinwheel de
  Cristian et al.~\cite{cristian97:high_performance} é um exemplo.
\item \textit{Baseados em privilégios} A diferença das classes
  anteriores, os papéis do sequenciador e do remetente são
  desenvolvidos pelo mesmo processo. O principio é que só o processo
  que possui o privilegio, e.g.\ token, pode enviar mensagens mas este
  privilegio é circulado pelos processos \(p \in \Pi_{sender}\) que
  podem enviar mensagens. O algoritmo proposto por Gopal e
  Toueg~\cite{Gopal:1989:RBS:645946.675018} é um exemplo.
\item \textit{Baseados na historia da comunicação} Nesta classe, são
  os destinatários os que definem a ordem de entrega das mensagens,
  i.e.\ os destinatários são os sequenciadores, baseando-se na historia
  deles. Os dois métodos utilizados são:
  \begin{inparaenum}[\itshape a\upshape)]
  \item \textit{historia causal}, onde algoritmos de ordem causal
    parcial~\cite{Lamport:1978_clocks} são aumentados com políticas
    comuns, para a ordenação de mensagens concorrentes, e o ordem
    total resultante é utilizado para ordenação das mensagens;
  \item \textit{união determinista}, onde não existe uma ordenação
    causal das mensagens, i.e.\ cada remetente ordena suas mensagens
    independentemente, sinão uma política determinista de união dos
    fluxos de mensagens de cada remetente.
  \end{inparaenum}
  O algoritmo Atom apresentado por Bar-Joseph et
  al.~\cite{Bar-Joseph:2002:EDA:645959.676132} é um exemplo.
\item \textit{Acordo dos destinatários} Como o nome o indica, os
  destinatários acordam a ordem das mensagens a ser entregues. As
  variantes são:
  \begin{inparaenum}[\itshape a\upshape)]
  \item acordo na sequencia da mensagem;
  \item acordo no conjunto de mensagens; onde, por exemplo, são
    utilizados algoritmos de consenso para determinar um subconjunto
    de mensagens a ser entregues simultaneamente por todos os
    processos (a ordem das mensagens do subconjunto é definida por
    algum parâmetro predefinido, por exemplo a ordem lexicográfica dos
    identificadores dos processos remetentes)
  \item um processo propõe uma ordem das mensagens e os demais
    destinatários acordam se é aceitado o não, portante é utilizado
    algum protocolo de \textit{commit} atômico.
  \end{inparaenum}
  O algoritmo proposto por Chandra e
  Toueg~\cite{Chandra:1996:UFD:226643.226647} é um exemplo.
\end{itemize}

Foi mostrado por Chandra e Toueg~\cite{Chandra:1996:UFD:226643.226647}
que o problema do consenso uniforme e o \textit{broadcast} de ordem
total em sistemas assíncronos com falhas de parada são equivalentes,
i.e.\ quaisquer algoritmo que possa resolver um deles também pode-se
adaptar para resolver o outro. Portanto, o \textit{broadcast} de ordem
total é sujeito ao mesmo resultado de impossibilidade de Fischer,
Lynch e Patterson.

Existem múltiplos mecanismos pelos quais pode-se prover alguma
tolerância a falhas ao \textit{broadcast} de ordem total. Na prática, os
algoritmos implementam vários mecanismos simultaneamente. Os mecanismos
são:

\begin{itemize}
\item \textit{Detecção de falhas} Baseados nos detetores de falhas não
  confiáveis propostos inicialmente por Chandra e
  Toueg~\cite{Chandra:1996:UFD:226643.226647}, os quais são discutidos
  com detalhe na seção~\ref{sec:detetores}
\item \textit{Serviço de configuração do grupo}\todo{é configuração o
    termo adecuado?}, profundamente relacionado com os grupos
  dinâmicos. No evento de um processo cai, o serviço gera uma nova
  vista do grupo e a envia aos processos ativos, portanto, eles podem
  assumir, que na vista atual todos os processos estão ativos. Se um
  processo foi excluído erroneamente, é forçado a cair para manter a
  correção. A diferença dos detetores de falhas, provê notificações de
  falhas consistentes.
% a descrição é correta o e só um exemplo dos distintos patroes?
\item \textit{Patrões de comunicação resistentes}, são aqueles patrões
  que consideram, dentro do número \(n\) total de processos, um número
  \(f\) máximo de processos que podem falhar, e trabalham sob a
  pressuposto que sempre vão receber pelo menos \(n-f\) mensagens de
  resposta.
\item \textit{Estabilidade das mensagens}. Além da possibilidade que
  um processo fique bloqueado esperando a resposta de outro processo
  que caiu, a qual é tratada pelos mecanismos anteriores, tem se que
  considerar a estabilidade das mensagens. Uma mensagem \(m\) é
  \(k\)-estável se \(m\) e recebida por \(k\) processos. Num sistema
  onde podem cair ao mais \(f\) processos, é importante detetar que as
  mensagens são \(f+1\)-estáveis, também chamadas estáveis, já que
  isso permite que os algoritmos garantem que, eventualmente, as
  mensagens são recebidas por todos os processos bons.
\item \textit{Consenso} O \textit{broadcast} de ordem total pode se reduzir a
  uma série de execuções do problema do consenso, portanto é possível
  delegar, e abstrair, toda a responsabilidade da tolerância a falhas
  ao algoritmo de consenso.
\end{itemize}

% relacao do broadcast confiavel com a replicacao ativa? paragrafo de
% fim de seção ?
\subsection{Detetores de falhas }
\label{sec:detetores}
Os detetores de falhas não confiáveis, propostos inicialmente por
Chandra e Toueg~\cite{Chandra:1996:WFD:234533.234549,
  Chandra:1996:UFD:226643.226647}, são, informalmente, um conjunto de
módulos distribuídos, um por processo do sistema, que possuem uma
visão deste, i.e.\ uma listagem dos processos que são suspeitos de ter
falhado, mas não precisasse garantir que a visão seja correta,
e.g.\ pode-se incluir na lista de suspeitos processos que não falharam.

Formalmente, a \textit{historia de um detetor de falhas} \(H\) é uma
função de \(\Pi \times \mathcal{T}\) a \(2^\Pi\), onde \(H(p,t)\) é o
valor do detetor de falhas do processo \(p\) ao tempo \(t\). Se o
processo \(q \in H(p,t)\) diz-se que o processo \(p\) suspeita \(q\)
ao tempo \(t\). Já que os detetores não são confiáveis, e possível que
dois processos distintos \(p \neq q\) possuam informação distinta,
i.e.\ \(H(p,t) \neq H(q,t)\). Um detetor de falhas \(\mathcal{D}\) é
uma função que mapeia cada patrão de falhas \(F\) a um conjunto de
historias de detetores de falhas \(D(F)\), sendo este o conjunto de
todas as historias do detetor de falhas \(D\) que podem acontecer em
execuções com o patrão de falhas \(F\).

Na proposta original de Chandra e
Toueg~\cite{Chandra:1996:UFD:226643.226647,
  Chandra:1996:WFD:234533.234549}, se definiam duas propriedades de
completude e quatro de precisão que podiam cumprir os detetores de
falhas:
\begin{inparaenum}[\itshape a\upshape)]
\item \textit{completude forte}, eventualmente todo processo que caiu é
  suspeito permanentemente por \textit{todos} os processos bons;
\item \textit{completude fraca}, eventualmente todo processo que caiu
  é suspeito permanentemente por \textit{alguns} processos bons;
\item \textit{precisão forte}, nenhum processo é suspeito antes de cair;
\item \textit{precisão débil}, alguns processos bons não são
  suspeitos nunca;
\item \textit{precisão forte eventual}, após algum tempo \(t \in
  \mathcal{T}\), nenhum processo bom é suspeito por nenhum outro
  processo bon.
\item \textit{precisão franca eventual}, após algum tempo \(t \in
  \mathcal{T}\), alguns processos bons não são suspeitos por nenhum
  outro processo bom.
\end{inparaenum}
Dos possíveis oito classes de detetores de falhas que podem-se criar
baseando-se nas combinações daquelas propriedades, os autores mostram
que são \textit{reduzíveis} só a quatro, onde \(\mathcal{D'}\) e
reduzível a \(\mathcal{D}\) se existe um algoritmo distribuído que
possa transformar \(D\) em \(D'\). Eles mostram que é possível
resolver o problema do consenso cada uma das classes de detetores de
falhas resultantes: perfeito \(\mathcal{P}\) (completude forte,
precisão forte), forte \(\mathcal{S}\) (completude forte, precisão
fraca), eventualmente perfeito \(\diamond \mathcal{P}\) (completude
forte, precisão forte eventual), e eventualmente forte \(\diamond
\mathcal{S}\) (completude forte, precisão fraca).

O modelo de falhas utilizado por Chandra e Toueg não permitia a
recuperação dos processos, portanto, a diferença da definição dada na
seção~\ref{sec:notacao}, os processos bons eram aqueles que nunca
falhavam e os ruins aqueles que caiam e não voltavam. Oliveira et
al.~\cite{oliveira97:consensus} e Hurfin et
al.\cite{Hurfin:1998:CAS:829523.830974} apresentaram soluções para o
modelo de falha e recuperação, mas Aguilera et
al.~\cite{springerlink:aguilera98} mostraram que a propriedade de
completude forte, da qual elas dependiam, pode gerar comportamento
indesejável onde, para satisfazer aquela, os detetores de falhas debem
de suspeitar de processos bons eventualmente para sempre. A raiz deste
comportamento é o fato que a abordagem tradicional tenta pronosticar
se um processo que caiu e volto, vai volver a cair ou não. Este erro
não impide que o algoritmo progresse, mas pode ter um efeito negativo
no seu desempenho.

Aguilera et al.~\cite{springerlink:aguilera98} propõem um novo tipo de
detetores de falhas que não exibem este comportamento e, portanto, são
mais apropriados ao modelo de falha e recuperação. Cada detetor produz
como saída dois elementos \(\langle trustlist, epoch \rangle\):
\(trustlist\) é um conjunto de processos, onde \(q \in trustlist\) se
\(p\) suspeita que \(q\) está ativo, e \(epoch\) é um vector de
inteiros indexado pelos elementos de \(trustlist\), onde \(epoch[q]\)
é o estimado de \(p\) do número de vezes que o \(q\) caiu e
voltou. Existem duas classes de detetores de falhas descritas por
Aguilera et al.\
\begin{itemize}
\item \(\diamond S_e\), na qual os detetores satisfazem as
  propriedades de:
  \begin{inparaenum}[\itshape a\upshape)]
  \item \textit{monotonicidade}, os valores de \(epoch\) produzidos
    pelos detetores dos processos \textit{bons} são eventualmente no
    decrescentes;
  \item \textit{completude}, por cada processo ruim \(r\), e por cada
    processo bom \(b\), ou eventualmente \(b\) suspeita
    permanentemente de \(r\) ou o \(epoch\) de \(b\) aumenta sem
    limites.
  \item \textit{precisão}, algum processo bom \(K\) e cada processo
    bom \(b\), eventualmente \(g\) permanentemente confia em \(K\) e o
    valor \(epoch\) de \(K\) em \(g\) para de cambiar.
  \end{inparaenum}
\item \(\diamond S_u\), a qual aumenta a classe \(\diamond S_e\) a com
  a propriedade de precisão forte que inclui processos instáveis, a
  qual permite-lhes suspeitar todos os processos bons:
  \textit{precisão forte}, algum processo bom \(K\):
  \begin{inparaenum}[\itshape a\upshape)]
  \item por cada processo bom \(g\), eventualmente \(g\) confia
    permanentemente de \(K\) e o \(epoch\) de \(K\) em \(g\) para de
    cambiar; e
  \item por cada processo instável \(u\), eventualmente quando \(u\)
    está ativo, \(u\) confia em \(K\) e o \(epoch\) de \(K\) em \(u\)
    para de cambiar.
  \end{inparaenum}
\end{itemize}

\section{Treplica}
\label{sec:treplica}
E melhor utilizar os relatório técnico~\cite{vieira08a-tr,
  vieira10:implementing-tr} ou o artigo~\cite{vieira08:_trepl}
\todo{Vou incluir aspectos gerais do treplica, ou algum em
  particular?}

\section{Proposta de pesquisa}
\label{sec:proposta}
Pesquisas anteriores~\cite{gray07:empirical,
  Schroeder:2007:DFR:1267903.1267904, 10.1109/SRDS.2008.9,
  Pinheiro:2007:FTL:1267903.1267905} mostraram que, na prática, as
falhas dos componentes de hardware dos sistemas distribuídos de
produção são maiores às reportadas pelos fabricantes; além disso,
erros no software também causam quedas nos processos, portanto, a
tolerância a falhas é vital.

A proposta de pesquisa vai-se focar nos sistemas distribuídos de
replicação ativa no modelo de maquina de
estados~\cite{Schneider:1990:IFS:98163.98167}, com \textit{broadcast}
de ordem total uniforme \todo{é uniforme, certo?}. Os processos têm as
seguintes caraterísticas:
\begin{inparaenum}[\itshape a\upshape)]
\item aceso à memória estável e à memória volátil local;
\item participação no \textit{broadcast} como remetentes e
  destinatários, i.e.\ \(\forall p,j \in \Pi~\exists m \in \mathcal{M}
  (sender(m) = p \wedge j \in Dest(m))\);
\item suscetíbilidade às falhas de software ou hardware, as quais
  causam que, os processos, perderam o conteúdo de sua memória volátil e
  não participem do sistema por um tempo limitado mas desconhecido,
  após o qual eles se \textit{recuperam} e voltam à atividade.
\end{inparaenum}
As propriedades da comunicação pelo \textit{broadcast} uniforme, que
foram definidas na seção~\ref{sec:broadcast}, que caracterizam o
modelo são:
\begin{inparaenum}[\itshape a\upshape)]
\item o grupo de processos é fechado e estático;
\item a sequencia das mensagens é decidida por acordo dos
  destinatários, utilizando o algoritmo de consenso Paxos.
\end{inparaenum}

O mecanismo de tolerância a falhas do sistema é fornecido pelo
\textit{broadcast} de ordem total uniforme, o qual garante que ainda
os processos com falhas vão receber todas as mensagens no mesmo
ordem. É possível, porém não prático, que sejam armazenadas todas as
mensagens enviadas pelo \textit{broadcast} e, no caso de falhas, estas
sejam entregues novamente ao processo recuperado. Ao invés, cada nó
vai armazenar \textit{checkpoints} em períodos regulais. Não
precisasse utilizar protocolos de \textit{checkpoint} distribuídos
tais como os apresentados em~\cite{Chandy:1985:DSD:214451.214456,
  Koo:1986:CRD:324493.325074} já que, a principal motivação do uso
deles, é garantir a consistência dos estados armazenados através do
sistema, mas neste caso não precisa; o \textit{broadcast} garanta a
consistência das mensagens entregues às replicas, e o algoritmo de
consenso fornece o mecanismo de coordenação e sincronização dos
estados.

\begin{table}[h]
  \small
  \centering
  \begin{tabular}{|l|p{5cm}|l|p{5cm}|}
    \hline
    \(\Pi\) & Conjunto de processos do sistema. &
    \(\Pi_{local}\) & Conjunto de processos que armazenam localmente seus \textit{checkpoints}. \\
    \(\Pi_{remote}\) & Conjunto de processos que armazenam remotamente seus \textit{checkpoints}. &
    \(\Pi_{storage}\) & Conjunto de processos que armazenam localmente \textit{checkpoints} remotos, além dos próprios. \\
    \(\Pi'_{storage}\) & Conjunto de processos externos que armazenam localmente \textit{checkpoints} remotos. &
    \(P_{storage}\) & \(\Pi_{storage} \cup \Pi'_{storage}\). \\
    \(States_i\) & Conjunto de estados do processo \(p_i\). &
    \(S_i(t)\) & Estado do processo \(p_i\) no tempo \(t\). \\
    \(\mathcal{M}_b\) & Conjunto das mensagens dos algoritmos (\textit{broadcast} e consenso). &
    \(\mathcal{M}_s\) & Conjunto das mensagens de armazenamento dos \textit{checkpoints}. \\
    \hline
  \end{tabular}
  \caption{Notação adicional.}
  \label{tab:notacion_proposta}
\end{table}

Vamos definir mais formalmente o sistema; a
tabela~\ref{tab:notacion_proposta} contém o resumo da notação
utilizada adicional à já definida na tabela~\ref{tab:notacao}. Seja
\(\Pi = \{p_1, \ldots, p_n\}\) um conjunto de \(n\) processos que
conformam o sistema, i.e.\ participam do \textit{broadcast} de ordem
total. Cada processo do sistema é modelado como uma maquina de
estados, onde \(States_i\) é o conjunto (não necessariamente finito)
de estados do processo \(p_i\). Seja \(S_i\) uma função de
\(\mathcal{T}\) a \(States_i\), tal que \(S_i(t)\) representa o estado
do processo \(i\) ao tempo \(t\); o estado especial \(\bot\)
representa inatividade, e.g.\ \(S_i(t) = \bot \iff p_i \in F(t)\). Os
processos só mudam de estado pelo intercambio de mensagens \(m \in
\mathcal{M}\), ou pelos eventos de falha e recuperação.

O \textit{checkpoint} do processo \(p_i\) no tempo \(t\) é definido
como a copia não modificável do estado \(S_i(t)\). A operação que os
gera é atômica~\cite{Randell:1978:RIC:356725.356729} e só pode-se
executar no tempo \(t\) se \(S_i(t) \neq \bot\). Formalmente, a
recuperação, ou reconstrução~\cite{Okun:2002:NSR:829526.831119}, no
tempo \(t'\) do processo \(p_i\) é uma operação especial, executável
se \(p_i \in F(t')\), que transforma do estado inicial \(S_i(0)\) ao
estado \(S_i(t)\) armazenado pelo \textit{checkpoint} gerado no tempo
\(t\), tal que \(t'> t\). O procedimento descrito só volta o processo
a seu último estado armazenado; a responsabilidade da atualização
deste até o estado atual das demais réplicas é delegada ao algoritmo
de consenso. Os \textit{checkpoints} são gerados a intervalos
regulais.

Sejam \(\Pi_{local}\), \(\Pi_{remote}\) e \(\Pi_{storage}\), três
subconjuntos disjuntos do \(\Pi\) tais que sua união é igual a
este. Se \(p \in \Pi_{local}\), o processo \(p\) armazena seus
\textit{checkpoints} em sua memoria estável local. Se \(p \in
\Pi_{remote}\), o processo \(p\) delega a responsabilidade do
armazenamento a outros processos, enviando-lhes os
\textit{checkpoints}. Se \(p \in \Pi_{storage}\), o processo \(p\)
armazena seus \textit{checkpoints} em sua memoria estável local, além
de armazenar \textit{checkpoints} de processos remotos em suas duas
memórias: a estável e a volátil. Além dos processos já definidos,
existem um conjunto de processos \(\Pi'_{storage}\) que não participam
do \textit{broadcast} de ordem total, e portanto não são replicas do
sistema, i.e.\ \(\Pi_{storage} \cap \Pi = \emptyset\): se \(p \in
\Pi'_{storage}\), o processo \(p\) é um repositorio, e tem a única
função de armazenar \textit{checkpoints} de processos remotos em suas
duas memorias: a estável é a volátil. Existe uma relação entre os
processos que delegam o armazenamento de seus \textit{checkpoints},
\(\Pi_{remote}\), e aqueles que assumem a responsabilidade,
representados pelo conjunto de processos \(P_{storage} = \Pi_{storage}
\cup \Pi'_{storage}\)~: seja \(Store\) uma relação de \(\Pi_{remote}\)
a \(2^{P_{storage}}\), tal que \(Store(p)\) representa o conjunto de
processos em \(P_{storage}\) que armazenam os \textit{checkpoints} de
\(p\); diz-se que \(j\) é um \textit{store} de \(p\) se somente se \(j
\in Store(p)\). Todos os processos de armazenamento devem de ser o
\textit{store} de pelo menos um processo remoto, i.e.\ \(\forall j \in
P_{storage} \exists p \in \Pi_{remote} (j \in Store(p))\), e todo
processo remoto tem que armazenar seus \textit{checkpoints} em pelo
menos um \textit{store}, i.e.\ \(\forall p \in \Pi_{remote} (Store(p)
\neq \emptyset)\).

As mensagens válidas são de dois classes: sejam \(\mathcal{M}_b\) e
\(\mathcal{M}_s\) dois subconjuntos disjuntos de \(\mathcal{M}\), tais
que \(\mathcal{M}_b \cap \mathcal{M}_s = \emptyset \wedge
\mathcal{M}_b \cup \mathcal{M}_s = \mathcal{M}\). \(\mathcal{M}_b\) é
o conjunto de todas as mensagens válidas do sistema que estão
relacionadas com o progresso dos algoritmos de consenso e de
\textit{broadcast} de ordem total uniforme; os remetentes e
destinatários destas mensagens são processos que participam do
consenso, i.e.\ \(\forall m \in \mathcal{M}_b (sender(m) \in \Pi \wedge
Dest(m) \subseteq \Pi)\).  \(\mathcal{M}_s\) é o conjunto de todas as
mensagens válidas do sistema que transmitem valores de
\textit{checkpoint} entre os processos que participam do armazenamento
remoto de dados, i.e.\ \(\forall m \in \mathcal{M}_s(sender(m) \in
(\Pi_{remote} \cup P_{storage}) \wedge Dest(m) \in (\Pi_{remote} \cup
P_{storage}))\).

\begin{figure}[h]
  \centering
   \includegraphics[width=120mm]{images/system_arch}
  \caption{Arquitetura do sistema}
  \label{fig:arquitetura}
\end{figure}

O objetivo desta pesquisa é encontrar a melhor configuração em termos
de desempenho num sistema com as caraterísticas do descrito na
figura~\ref{fig:arquitetura}. As medidas de desempenho utilizadas são:
\begin{inparaenum}[\itshape a\upshape)]
\item \textit{disponibilidade}, ratio entre o tempo que a aplicação
  está operacional e o tempo total de execução;
\item \textit{perfomability}, é o ratio entre o desempenho promédio da
  aplicação (AWIPS) durante o período sem falhas e o desempenho
  promédio durante o período de recuperação; está medida quantifica o
  impacto das falhas no desempenho da aplicação;
\item \textit{precisão}, ratio entre o número de solicitações com erro
  e o total destas durante a execução;
\item \textit{autonomia}, ratio entre o número de intervenções humanas
  precisadas para o reinicio das replicas e o número de falhas no
  sistema.
\end{inparaenum}
\todo{Os parâmetros de desempenho supostos são os mesmos que no
  trabalho de tréplica do 2009\cite{buzato09}}

As possiveis configurações do sistema são:

\begin{itemize}
\item \(\Pi_{local} = \Pi\), está é a configuração atual de
  Treplica. Todos os processo armazenam seus
  \textit{checkpoints}, portanto o custo de recuperação do estado é
  dominado pela latência da memoria estável, e o procedimento não gera
  trafego de rede ou carga nos nós vizinhos adicional\footnote{É claro
    que a falha de um processo vai gerar uma carga de trabalho
    adicional aos demais membro do sistema, devido à redistribuição de
    tarefas, mas é considerado um custo inerente ao modelo e portanto
    não considerado nos cálculos.}
\item \(\Pi_{local} \neq \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} \neq \emptyset \wedge \Pi'_{storage} =
  \emptyset \), alguns processos armazenam seus estados em processos
  remotos que participam do \textit{broadcast}, portanto o custo de recuperação
  desses processos é dominado pela latência de rede, e o procedimento
  gera trafego de rede e carga adicional aos vizinhos, mas é uma
  quantidade limitada aos processos que utilizam armazenamento remoto.
\item \(\Pi_{local} \neq \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} \neq \emptyset \wedge \Pi'_{storage} \neq
  \emptyset \), alguns processos armazenam seus estados em processos
  remotos que participam ou não do \textit{broadcast}, portanto o custo de
  recuperação desses processos é dominado pela latência de rede, e o
  procedimento gera trafego de rede e carga adicional aos vizinhos,
  mas é uma quantidade menor à opção anterior, já que o tráfego e a
  carga gerada aos nós repositório não tem impacto sob o desempenho do
  sistema.
\item \(\Pi_{local} \neq \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} = \emptyset \wedge \Pi'_{storage} \neq
  \emptyset \), alguns processos armazenam seus estados em processos remotos
  que não participam do \textit{broadcast}, portanto o custo de recuperação
  desses processos é dominado pela latência de rede, e o procedimento
  não gera trafego de rede ou carga adicional aos vizinhos.
\item \(\Pi_{local} = \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} \neq \emptyset \wedge \Pi'_{storage} =
  \emptyset \), todos os processos armazenam seus estados em processos
  remotos que participam do \textit{broadcast}, portanto o custo de recuperação
  está dominado pela latência de rede, e o procedimento gera trafego
  de rede e carga adicional aos vizinhos.
\item \(\Pi_{local} = \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} \neq \emptyset \wedge \Pi'_{storage} \neq
  \emptyset \), todos os processos armazenam seus estados em processos
  remotos que participam ou não do \textit{broadcast}, portanto o
  custo de recuperação está dominado pela latência de rede, e o
  procedimento gera trafego de rede e carga adicional aos vizinhos,
  mas é uma quantidade menor à proposta anterior.
\item \(\Pi_{local} = \emptyset \wedge \Pi_{remoto} \neq \emptyset
  \wedge \Pi_{storage} = \emptyset \wedge \Pi'_{storage} \neq
  \emptyset \), todos os processos armazenam seus estados em processos
  remotos que não participam do \textit{broadcast}, portanto o custo
  de recuperação está dominado pela latência de rede, e o procedimento
  não gera trafego de rede ou carga adicional aos vizinhos.
\end{itemize}

A avaliação das opções tem que considerar não só a melhor opção, sinão
qual é a proporção de cada conjunto de processo que gera o resulta
mais ótimo. Um aspecto importante a se considerar é o desempenho das
soluções sob as distintas classes de processos em relação as falhas:
ativo, eventualmente ativo, eventualmente inativo e intestável (ver
seção~\ref{sec:notacao}). Portanto, além de implementar os mecanismos
necessários para dar suporte às distintas classes de processos, é
preciso a implementação de detetores de falhas no modelo proposto por
Aguilera et al.~\cite{springerlink:aguilera98} (ver
seção~\ref{sec:detetores}), que possam fornecer melhor informação
sobre os processos bons, ruins é instáveis.

% LAS TECNICAS PROPUESTAS TAMBIEN HAN SIDO HECHAS PARA EL AMBIENTE
% HPC. [ver paper de Bautista Gomez] REVISAR ARTICULO DE ISLENE

% As alternativas a avaliar são as seguintes:

% % hay que tener en consideracion que en este caso no se asume las
% % fallas de disco dentro de la evaluacion. El metodo necesario para
% % soportar esa situacion seria, por ejemplo, el uso de un sistema de
% % archivos distribuido con replicacion, como hdfs. Aunque el impacto
% % sobre el desempenho del sistema no es, necesariamente, despreciable,
% % puede asumirse que afecta de manera uniforme a todos los nodos del
% % sistema que utilizan la memoria estable.


\section{Metodologia Científica}
\label{sec:metodologia}

\todo{qual é o conteúdo apropiado para esta seção?}

\subsection{Tarefas e cronograma}
\label{sec:planodetrabalho}

Esta seção detalha as tarefas planejadas para o desenvolvimento do
Mestrado e o conograma proposto (Tabela~\ref{projtimetable}):
\todo[noline]{o conteudo é correcto e completo? o calendário de
  atividades?}

\begin{enumerate}
\addtolength{\itemsep}{-0.35\baselineskip}

% Ago-Julho 2010
\item \label{t1} Créditos em disciplinas

% Abril-Julho 2010
\item \label{t2} Revisão bibliográfica

% Maio-Ago 2010
\item \label{t3} Estudo dirigido

% Jul-Ago 2010
\item \label{t4} Elaboração do projeto de mestrado

% Ago 2010 - Jul 2011
\item \label{t5} Estudo comparativo de algoritmos

% Jan 2011 - Dez 2011
\item \label{t6} Proposta, análise e prova de algoritmos.

% Dez 2011 - Dez 2011
\item \label{t7} Implementação da solução sobre a plataforma
Tréplica~\cite{vieira08a}. Testes de desempenho da solução com
diversas cargas de trabalho, tanto na presença como na ausência de
falhas de processos.

% Mai 2011 - Jan 2012
\item \label{t8} Escrita da Dissertação de Mestrado

% Fev 2012 - Mar 2012
\item \label{t9} Defesa da Dissertação de Mestrado

% Dez 2010 - Mar 2012
\item \label{t10} Escrita e submissão de artigos para publicação

\end{enumerate}

\begin{table}[h]
\begin{center}
\setlength{\tabcolsep}{1.5pt}
\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
  &  \multicolumn{5}{c|}{\scriptsize 2010} & \multicolumn{12}{c|}{\scriptsize 2011} & \multicolumn{7}{c|}{\scriptsize 2012} \\ \cline{2-25}
{\small Tarefas } &
\rotatebox{90}{\scriptsize ago } &
\rotatebox{90}{\scriptsize set } &
\rotatebox{90}{\scriptsize out } &
\rotatebox{90}{\scriptsize nov } &
\rotatebox{90}{\scriptsize dez } &
\rotatebox{90}{\scriptsize jan } &
\rotatebox{90}{\scriptsize fev } &
\rotatebox{90}{\scriptsize mar } &
\rotatebox{90}{\scriptsize abr } &
\rotatebox{90}{\scriptsize mai } &
\rotatebox{90}{\scriptsize jun } &
\rotatebox{90}{\scriptsize jul } &
\rotatebox{90}{\scriptsize ago } &
\rotatebox{90}{\scriptsize set } &
\rotatebox{90}{\scriptsize out } &
\rotatebox{90}{\scriptsize nov } &
\rotatebox{90}{\scriptsize dez } &
\rotatebox{90}{\scriptsize jan } &
\rotatebox{90}{\scriptsize fev } &
\rotatebox{90}{\scriptsize mar } &
\rotatebox{90}{\scriptsize abr } &
\rotatebox{90}{\scriptsize mai } &
\rotatebox{90}{\scriptsize jun } &
\rotatebox{90}{\scriptsize jul } \\ \hline

\ \~ref{t1}  & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
\ \~ref{t2}  &    & \f & \f & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
\ \~ref{t3}  &    &    &    & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
\ \~ref{t4}  &    &    &    & \f & \f & \f & \f &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    \\ \hline
\ \~ref{t5}  &    &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f &    &    &    &    &    &    &    \\ \hline
\ \~ref{t6}  &    &    &    &    &    &    &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f &    &    \\ \hline
\ \~ref{t7}  &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    & \f & \f & \f & \f & \f & \f &    &    \\ \hline
\ \~ref{t8}  &    &    &    &    &    &    &    &    &    &    &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f   &    \\ \hline
\ \~ref{t9}  &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &    & \f & \f \\ \hline
\ \~ref{t10} &    &    &    &    & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f & \f \\ \hline
\end{tabular}
\caption{Cronograma do projeto}
\label{projtimetable}
\end{center}
\end{table}


\begin{small}
\phantomsection
\addcontentsline{toc}{section}{\bibname}
\bibliographystyle{plain}
\bibliography{mscMonografia,bibliography}
\end{small}

\end{document}