Thesis (M.S.)--University of Florida, 2004. / Title from title page of source document. Document formatted into pages; contains 104 pages. Includes vita. Includes bibliographical references.

Thesis (M.S.)--Rutgers University, 2008. / "Graduate Program in Electrical and Computer Engineering." Includes bibliographical references (p. 91-96).

Prepared for the Office of Naval Research on ONR Contract no. N00014-77-C-0224. Issued by: M.I.T. Electronic Systems Laboratory, 1977; M.I.T. Laboratory for Information and Decision Systems, 1978-

Prepared for the Office of Naval Research on ONR Contract no. N00014-77-C-0224. Issued by: M.I.T. Electronic Systems Laboratory, 1977; M.I.T. Laboratory for Information and Decision Systems, 1978-

Thesis (Ph. D.)--University of Texas at Austin, 2008. / Vita. Includes bibliographical references and index.

Orientadores: Islene Calciolari Garcia / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-06T15:21:09Z (GMT). No. of bitstreams: 1 Silva_UlissesFurquimFreireda_M.pdf: 705102 bytes, checksum: 5b4ebc6853f67fd40696b21c87297f43 (MD5) Previous issue date: 2005 / Resumo: Um sistema distribuído tolerante a falhas que utilize recuperação por retrocesso de estado deve selecionar os checkpoints dos seus processos que serão gravados. Além dessa seleção, definida por um protocolo de checkpointing, o sistema precisa realizar uma coleta de lixo, para eliminar os checkpoints que se tornam obsoletos à medida que a aplicação executa. Assim, na ocorrência de uma falha, a computação pode ser retrocedida para um estado consistente salvo anteriormente. Esta dissertação discute os aspectos teóricos e práticos de um sistema distribuído tolerante a falhas que utiliza protocolos de checkpointing quase-síncronos e algoritmos para a coleta de lixo e recuperação por retrocesso. Existem vários protocolos de checkpointing na literatura, e nesta dissertação foram estudados os protocolos de checkpointing quase-síncronos. Esses protocols enviam informações de controle juntamente com as mensagens da aplicação, e podem exigir a gravação de checkpoints forçados, mas não necessitam de sincronização ou troca de mensagens de controle entre os processos. Com base nesse estudo, um framework para protocolos de checkpointing quase-sincronos foi implementado numa biblioteca de troca de mensagens chamada LAM/MPI. Além disso, uma arquitetura de software para recuperação de falhas por retrocesso de estado chamada Curupira também foi estudada e implementada naquela biblioteca. O Curupira_e a primeira arquitetura de software que n~ao precisa de troca de mensagens de controle ou qualquer sincronização entre os processos na execução dos protocolos de checkpointing e de coleta de lixo / Abstract: A fault-tolerant distributed system based on rollback-recovery has to checkpoints of its processes are stored. Besides this selection, that is controlled checkpointing protocol, the system has to do garbage collection, in order to eliminate that become obsolete while the application executes. The garbage collection because checkpoints require the use of storage resources and the storage has limited capacity. So, when some fault occurs, the whole distributed be restored to a consistent global state previously stored. This dissertation practical and theoretical aspects of a fault-tolerant distributed system quasisynchronous checkpointing protocols and also garbage collection and algorithms. There are several checkpointing protocols proposed in the literature, quasisynchronous ones were studied in this dissertation. These protocols information in the application's messages and can induce forced checkpoints, need any synchronization or exchanging of control messages among on that study, a framework for quasi-synchronous checkpointing implemented in a message passing library called LAM/MPI. Moreover, a based on rollback-recovery from faults named Curupira was also implemented in that library. Curupira is the _rst software architecture exchanging of control messages or any synchronization among the execution of the checkpointing and garbage collection protocols / Mestrado / Sistemas Distribuidos / Mestre em Ciência da Computação

Orientador: Edmundo R. M. Madeira, Fernando Pedone / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-13T10:28:10Z (GMT). No. of bitstreams: 1 Camargos_LasaroJonas_D.pdf: 1941705 bytes, checksum: 23f0f1380c7d6262497ec13b43519301 (MD5) Previous issue date: 2008 / Resumo: Problemas de acordo, como Consenso, Terminação Atômica e Difusão Atômica, são abstrações comuns em sistemas distribuídos. Eles ocorrem quando os componentes do sistema precisam concordar em reconfigurações, mudanças de estado ou em linhas de ação em geral. Nesta tese, investigamos estes problemas no contexto do ambiente e aplicações em que serão utilizados. O modelo geral é o assíncrono sujeito a quebras com possível posterior recuperação. Nossa meta é desenvolver protocolos que explorem esta informação contextual para prover maior disponibilidade, e que se mantenham corretos mesmo que algumas das prerrogativas do contexto tornem-se inválidas. Na primeira parte da tese, exploramos a seguinte propriedade: mensagens difundidas em pequenas redes tendem a ser entregues ordenada e confiavelmente. Nós fazemos três contribuições nesta parte da tese. A primeira é a transformação de algoritmos conhecidos para o modelo quebra-e-pára, que utilizam a propriedade de ordenação mencionada, em protocolos práticos. Isto é, protocolos que toleram perda de mensagens e recuperação após a quebra. Nossos protocolos garantem progresso na presença de falhas, contanto que mensagens sejam espontaneamente ordenadas freqüentemente. Na ausência de ordenação expontânea, outras prerrogativas são necessárias para contornar falhas. A segunda contribuição é a generalização de um dos algoritmos citados acima em um modo de execução "multi-coordenado" em um protocolo híbrido de consenso, que usa ou ordenação expontânea ou detecção de falhas para progredir. Em comparação a outros protocolos, o nosso provê maior disponibilidade sem comprometer resiliência. A terceira contribuição é a utilização do modo multi-coordenado para resolver Consenso Generalizado, um problema que generaliza uma série de outros e que, portanto, é de grande interesse prático. Além disso, fizemos diversas considerações sobre aspectos práticos da utilização deste protocolo. Como resultado, nosso protocolo perde desempenho gradualmente no caso de condições desfavoráveis, permite o balanceamento de carga sobre os coordenadores, e acessa a memória estável parcimoniosamente. Na segunda parte da tese, consideramos problemas de acordo no contexto de redes organizadas hierarquicamente. Em específico, nós consideramos uma topologia usada nos data centers de grandes cooporações: grupos de máquinas conectadas internamente por links de baixa latência, mas por links mais lentos entre grupos. Em tais cenários, latência é claramente um fator importante e reconfigurações, onerosas aos protocolos, devem ser evitadas tanto quanto possível. Nossa contribuição neste tópico está em evitar reconfigurações e melhorar a disponibilidade de um protocolo de acordo que é rápido a despeito de colisões. Isto é, um protocolo que consegue chegar a uma decisão em dois passos inter-grupos mesmo quando várias propostas são feitas concorrentementes. Além do uso da técnica de multicoordenação, nós usamos primitivas de multicast e consenso para conter algumas reconfigurações dentro dos grupos, onde seus custos são menores. Na última parte da tese nós estudamos o problema de terminação de transações distribuídas. O problema consiste em garantir que os vários participantes da transação concordem em aplicar ou cancelar de forma consistente as suas operações no contexto da transação. Além disso, é necessário garantir a durabilidade das alterações feitas por transações terminadas com sucesso. Nossa contribuição neste tópico é um serviço de log que abstrai e desassocia a terminação de transações dos processos que executam tais transações. O serviço funciona como uma caixa preta e permite que resource managers lentos ou falhos sejam reiniciados em servidores diferentes, sem dependências na memória estável do servidor em que executava anteriormente. Nós apresentamos e avaliamos experimentalmente duas implementações do serviço. / Abstract: Agreement problems are a common abstraction in distributed systems. They appear when the components of the system must concur on reconfigurations, changes of state, or in lines of action in general. Examples of agreement problems are Consensus, Atomic Commitment, and Atomic Broadcast. In this thesis we investigate these abstractions in the context of the environment in which they will run and the applications that they will serve; in general, we consider the asynchronous crash-recovery model. The goal is to devise protocols that explore the contextual information to deliver improved availability. The correctness of our protocols holds even when the extra assumptions do not. In the first part of this thesis we explore the following property: messages broadcast in small networks tend to be delivered in order and reliably. We make three contributions in this part. The first contribution is to turn known Consensus algorithms that harness this ordering property to reach agreement in the crash-stop model into practical protocols. That is, protocols that tolerate message losses and recovery after crashes, efficiently. Our protocols ensure progress even in the presence of failures, if spontaneous ordering holds frequently. In the absence of spontaneous ordering, some other assumption is required to cope with failures. The second contribution of this thesis is to generalize one of our crash-recovery consensus protocols as a "multicoordinated" mode of a hybrid Consensus protocol, that may use spontaneous ordering or failure detection to progress. Compared to other protocols, ours provide improved availability with no price in resilience. The third contribution is to employ this new mode to solve Generalized Consensus, a problem that generalizes a series of other agreement problems and, hence, is of much practical interest. Moreover, we considered several aspects of solving this problem in practice, which had not been considered before. As a result, our Generalized Consensus protocol features graceful degradation, load balancing, and is parsimonious in accessing stable storage. In the second part of this thesis we have considered agreement problems in wide area networks organized hierarchically. More specifically, we considered a topology that is commonplace in the data centers of large corporations: groups of nodes, with large-bandwidth low-latency links connecting the nodes in the same group, and slow and limited links connecting nodes in different groups. In such environments, latency is clearly a major concern and reconfiguration procedures that render the agreement protocol momentarily unavailable must be avoided as much as possible. Our contribution here is in avoiding reconfigurations and improving the availability of a collision fast agreement protocol. That is, a protocol that can reach agreement in two intergroup communication steps, irrespectively to concurrent proposals. Besides the use of a multicoordinated approach, we employed multicast primitives and consensus to restrict some reconfigurations to within groups, where they are less expensive. In the last part of this thesis we study the problem of terminating distributed transactions. The problem consists of enforcing agreement among the parties on whether to commit or rollback the transaction and ensuring the durability of committed transactions. Our contribution in this topic is an abstract log service that detaches the termination problem from the processes actually performing the transactions. The service works as a black box and abstracts its implementation details from the application utilizing it. Moreover, it allows slow and failed resource managers be re-started on different hosts without relying on the stable storage of the previous host. We provide two implementations of the service, which we evaluated experimentally. / Doutorado / Doutor em Ciência da Computação

Orientador: Islene Calciolari Garcia / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T07:37:22Z (GMT). No. of bitstreams: 1 Sakata_TiemiChristine_D.pdf: 843635 bytes, checksum: 7f950e8bee6e5c7a1dfb19c6212897c2 (MD5) Previous issue date: 2007 / Resumo: Protocolos de checkpointing são responsáveis pelo armazenamento de estados dos processos de um sistema distribuído em memória estável para tolerar falhas. Os protocolos síncronos minimais induzem apenas um número minimal de processos a salvarem checkpoints durante uma execução do protocolo bloqueando os processos envolvidos. Uma versão não-bloqueante desta abordagem garante a minimalidade no número de checkpoints salvos em memória estável com o uso de checkpoints mutáveis, checkpoints que podem ser salvos em memória não-estável. Porém, a complexidade deste protocolo e o fato de ele tolerar apenas a presença de uma execução de checkpointing a cada instante nos motivou a procurar soluções para estes problemas na teoria desenvolvida para os protocolos quase-síncronos. A nova abordagem nos permitiu fazer uma revisão de alguns protocolos síncronos bloqueantes existentes na literatura que até então eram considerados minimais. Nesta mesma linha, obtivemos novos resultados na análise de minimalidade dos protocolos síncronos não-bloqueantes, ao considerarmos a aplicação como um todo e também a existência de execuções concorrentes de checkpointing. Ao estabelecermos esta ponte entre as abordagens para checkpointing, conseguimos desenvolver dois novos protocolos síncronos não-bloqueantes. Ambos fazem uso de checkpoints mutáveis, permitem execuções concorrentes de checkpointing e possuem um mecanismo simples de coleta de lixo. No entanto, o fato de cada um dos protocolos derivar de classes diferentes de protocolos quase-síncronos leva a comportamentos distintos, como evidenciado por resultados de simulação / Abstract: Checkpointing protocols are responsible for the selection of checkpoints in fault-tolerant distributed systems. Minimal checkpointing protocols minimize the number of checkpoints blocking processes during checkpointing. A non-blocking version of this approach assures a minimal number of checkpoints saved in stable memory using mutable checkpoints, those checkpoints can be saved in a non-stable storage. However, the complexity of this protocol and the absence of concurrent checkpointing executions have motivated us to find new solutions in the quasi-synchronous theory. The new approach has allowed us to review some blocking synchronous protocols existent in the literature which were, until now, considered as minimals. In the same way, we present new results analysing the minimality on the number of checkpoints in nonblocking synchronous protocols, considering the whole application and also the existence of concurrent checkpointing executions. On bridging the gap between the checkpointing approaches we could develop two new non-blocking synchronous protocols. Both use mutable checkpoints, allow concurrent checkpointing executions and have a simple mechanism of garbage collection. However, since each protocol derives from a diferent class of quasi-synchronous protocols, they present distinct behaviours, which are evident in the simulation results / Doutorado / Sistemas Distribuidos / Doutor em Ciência da Computação

No description available.

No description available.