From ddf190ae1cb8e066f4fb9d942c5fd63d52680d4f Mon Sep 17 00:00:00 2001 From: Rodrigo Lazo Date: Mon, 31 Jan 2011 14:33:13 -0200 Subject: [PATCH] Further progress in the introduction section. --- mscTemplate.tex | 74 +++++++++++++++++++++++++++++++-------------------------- 1 file changed, 40 insertions(+), 34 deletions(-) diff --git a/mscTemplate.tex b/mscTemplate.tex index 6c037d3..3940da8 100644 --- a/mscTemplate.tex +++ b/mscTemplate.tex @@ -109,16 +109,20 @@ 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 é introducida pelas variações no desempenho do -sistema \cite{chandra96c}. Além da assincronia, a tolerancia a falhas -é outra caraterística importante, já que seja por errors no software -ou por falhas do hardware, elas vão ocurrir. A dificultade da -assincronia com falhas de processo é que existem problemas, -e.g. acordo, solucionaveis em outros modelos, e.g. síncrono, que não -possuim solução direita \cite{dwork88}. Neste caso, um dos método -utilizados para fazer solucionavel o problema é acrecentar o modelo, -por exemplo com o uso de detetores de falhas. Informalmente, um +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{chandra96c}. 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 possuem solução, e.g. acordo +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}. + +Neste caso, um dos método utilizados para fazer solucionavel o +problema é acrecentar o modelo, por exemplo com o uso de detetores de +falhas \cite{Chandra:1996:UFD:226643.226647}. Informalmente, um detetor de falhas é um módulo que fornece informação (não necessariamente correta) sob o estado atual dos processos, e.g. se estão ativos ou não. @@ -192,7 +196,7 @@ distribuído assíncrono com apenas um processo falhado. O \textit{broadcast} confiável é, informalmente, uma primitiva de comunicação assíncrona de alto nível que garanta as seguentes três -propriedades \cite{chandra96}: +propriedades \cite{Chandra:1996:UFD:226643.226647}: \begin{inparaenum}[\itshape a\upshape)] \item todos os processos corretos entregam o mesmo conjunto de mensagens, @@ -203,35 +207,37 @@ propriedades \cite{chandra96}: Além disso, no caso possa-se garantir que os mensagens são entregues no mesmo ordem por todos os processos, a primitiva chama-se \textit{broadcast} com ordenação total ou \textit{broadcast} atômico -\cite{Defago:2004}. Foi mostrado por Chandra e Toueg \cite{chandra96} -que o problema do consenso uniforme e o \textit{broadcast} atômico 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} atômico -é sujeito ao mesmo resultado de impossibilidade de Fischer et al. +\cite{Defago:2004}. Foi mostrado por Chandra e Toueg +\cite{Chandra:1996:UFD:226643.226647} que o problema do consenso +uniforme e o \textit{broadcast} atômico 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} atômico é sujeito ao mesmo +resultado de impossibilidade de Fischer et al. Existem distintas soluções para evitar o resultado de impossibilidade: o uso de randomização \cite{Chor89}, definição de problemas mais deveis e suas soluções \cite{dolev87}, entre outros. Nós vamos a centrar em detetores de falhas não confiáveis -\cite{chandra96c,chandra96}. Informalmente, os detetores de falhas são -um conjunto de módulos distribuídos, um por processo do sistema, que -possuem uma visão do sistema, 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. Os detetores de falhas aumentam o modelo do sistema assíncrono -e permitem resolver o problema do consenso (\textit{broadcast} -atômico) em sistemas com falhas de processo. +\cite{chandra96c,Chandra:1996:UFD:226643.226647}. Informalmente, os +detetores de falhas são um conjunto de módulos distribuídos, um por +processo do sistema, que possuem uma visão do sistema, 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. Os detetores de falhas +aumentam o modelo do sistema assíncrono e permitem resolver o problema +do consenso (\textit{broadcast} atômico) em sistemas com falhas de +processo. Uma das deficiências da proposta de Chandra e Toueg -\cite{chandra96c,chandra96}, é que consideram as falhas como -permanentes, i.e. os processos não podem-se recuperar. É claro que na -prática os processos podem falhar e se recuperar múltiplas vezes, -Aguilera et al. \cite{springerlink:aguilera98} propõe um novo tipo -de detetores de falhas que não retornam uma lista de processos -suspeitos de ter falhado mas uma lista dos processos que podem estar -funcionando corretamente mais uma estimativa do número de vezes que -ele falho até o momento. +\cite{chandra96c,Chandra:1996:UFD:226643.226647}, é que consideram as +falhas como permanentes, i.e. os processos não podem-se recuperar. É +claro que na prática os processos podem falhar e se recuperar +múltiplas vezes, Aguilera et al. \cite{springerlink:aguilera98} propõe +um novo tipo de detetores de falhas que não retornam uma lista de +processos suspeitos de ter falhado mas uma lista dos processos que +podem estar funcionando corretamente mais uma estimativa do número de +vezes que ele falho até o momento. \section{Fundamentação Teórica} \label{sec:teoria} @@ -344,7 +350,7 @@ falhas de processos. \phantomsection \addcontentsline{toc}{section}{\bibname} \bibliographystyle{plain} -\bibliography{mscTemplate} +\bibliography{mscTemplate,bibliography} \end{small} \end{document} -- 2.11.4.GIT