Pulse synchronization is the evolution of spontaneous firing action across a network of sensor nodes. In the pulse synchronization model all nodes across a network produce a pulse, or "fire", at regular intervals even without access to a shared global time. Previous researchers have proposed the Reachback Firefly algorithm for pulse synchronization, in which nodes react to the firings of other nodes by changing their period. We propose an extension to this algorithm for tolerating arbitrary or Byzantine faults of nodes. Our algorithm queues up all the firings heard in the current cycle and discards outliers at the end of the cycle. An adjustment is computed with the remaining values and used as a starting point of the next cycle. Through simulation we validate the performance of our algorithm and study the overhead in terms of convergence time and periodicity. The simulation considers two specific kinds of Byzantine faults, the No Jump model where faulty nodes follow their own firing cycle without reacting to firings heard from other nodes and the Random Jump model where faulty nodes fire at any random time in their cycle.

Peer-to-peer technologies have shown a lot of promise in sharing the remote resources effectively. The resources shared by peers are information, bandwidth, storage space or the computing power. When used properly, they can prove to be very advantageous as they scale well, are dynamic, autonomous, fully distributed and can exploit the heterogeneity of peers effectively. They provide an efficient infrastructure for an application seeking to distribute numerical computation. In this thesis, we investigate the feasibility of using a peer-to-peer infrastructure to distribute the computational load of Matlab and similar applications to achieve performance benefits and scalability. We also develop a proof of concept application to distribute the computation of a Matlab style application.

The use of randomness in computer science is ubiquitous. Randomized protocols have turned out to be much more efficient than their deterministic counterparts. In addition, many problems in distributed computing and cryptography are impossible to solve without randomness. However, these applications typically require uniform random bits, while in practice almost all natural random phenomena are biased. Moreover, even originally uniform random bits can be damaged if an adversary learns some partial information about these bits. In this thesis, we study how to run randomized protocols in distributed computing and cryptography with imperfect randomness. We use the most general model for imperfect randomness where the weak random source is only required to have a certain amount of min-entropy. One important tool here is the randomness extractor. A randomness extractor is a function that takes as input one or more weak random sources, and outputs a distribution that is close to uniform in statistical distance. Randomness extractors are interesting in their own right and are closely related to many other problems in computer science. Giving efficient constructions of randomness extractors with optimal parameters is one of the major open problems in the area of pseudorandomness. We construct network extractor protocols that extract private random bits for parties in a communication network, assuming that they each start with an independent weak random source, and some parties are corrupted by an adversary who sees all communications in the network. These protocols imply fault-tolerant distributed computing protocols and secure multi-party computation protocols where only imperfect randomness is available. The probabilistic method shows that there exists an extractor for two independent sources with logarithmic min-entropy, while known constructions are far from achieving these parameters. In this thesis we construct extractors for two independent sources with any linear min-entropy, based on a computational assumption. We also construct the best known extractors for three independent sources and affine sources. Finally we study the problem of privacy amplification. In this model, two parties share a private weak random source and they wish to agree on a private uniform random string through communications in a channel controlled by an adversary, who has unlimited computational power and can change the messages in arbitrary ways. All previous results assume that the two parties have local uniform random bits. We show that this problem can be solved even if the two parties only have local weak random sources. We also improve previous results in various aspects by constructing the first explicit non-malleable extractor and giving protocols based on this extractor.

Automated planning is a field of artificial intelligence that aims at proposing methods to chose and order sets of actions with the objective of reaching a given goal. A sequence of actions solving a planning problem is usually called a plan. In many cases, one does not only have to find a plan but an optimal one. This notion of optimality can be defined by assigning costs to actions. An optimal plan is then a plan minimizing the sum of the costs of its actions. Planning problems are standardly solved using algorithms such as A* that search for minimum cost paths in graphs. In this thesis we focus on a particular approach to planning called factored planning or modular planning. The idea is to consider a decomposition of a planning problem into almost independent sub-problems (or components). One then searches for plans into each component and try to assemble these local plans into a global plan for the original planning problem. The main interest of this approach is that, for some classes of planning problems, the components considered can be planning problems much simpler to solve than the original one. First, we present a study of the use of some message passing algorithms for factored planning. In this case the components of a problem are represented by weighted automata. This allows to handle all plans of a sub-problems, and permits to perform factored cost-optimal planning. Achieving cost-optimality of plans was not possible with previous factored planning methods. This approach is then extended by using approximate resolution techniques ("turbo" algorithms) and by proposing another representation of components for handling actions which read-only in some components. Then we describe another approach to factored planning: a distributed version of the famous A* algorithm. Each component is managed by an agent which is responsible for finding a local plan in it. For that, she uses information about her own component, but also information about the rest of the problem, transmitted by the other agents. The main difference between this approach and the previous one is that it is not only modular but also distributed.

No description available.

No description available.

The design of a parallel and distributed computing system is a very complicated task. It requires a detailed understanding of the design issues and of the theoretical and practical aspects of their solutions. Firstly, this thesis discusses in detail the major concepts and components required to make parallel and distributed computing a reality. A multithreaded and distributed framework capable of analysing the simulation data produced by a pedestrian simulation software was developed. Secondly, this thesis discusses the origins and fundamentals of Grid computing and the motivations for its use in High Energy Physics. Access to the data produced by the Large Hadron Collider (LHC) has to be provided for more than five thousand scientists all over the world. Users who run analysis jobs on the Grid do not necessarily have expertise in Grid computing. Simple, userfriendly and reliable monitoring of the analysis jobs is one of the key components of the operations of the distributed analysis; reliable monitoring is one of the crucial components of the Worldwide LHC Computing Grid for providing the functionality and performance that is required by the LHC experiments. The CMS Dashboard Task Monitoring and the CMS Dashboard Job Summary monitoring applications were developed to serve the needs of the CMS community.

Context. When dealing with large data sets and heavy calculations the common solution is clusters, supercomputers or Grids of these two. However, there are ways of gaining large computational power by utilizing the unused cycles of regular home or office computers, this are referred to as Desktop Grids. Objectives. In this study we review the current field of solutions for open source Desktop Grid computing capable of dealing with a heterogeneous set of clients and dynamic size of the Desktop Grid. We investigate current use, interest of use and priority of key attributes of Desktop Grids. Finally we want to show how time effective Desktop Grids are compared to execution on a single machine and in the process show effort needed to setup a Desktop Grid and start computing. The overall purpose of this study is to provide a path for industry organizations to take when taking the first step into Desktop Grid computing. Methods. We use a systematic review to collect information of existing open source Desktop Grid solutions. Studies are selected based on inclusion criterions and a quality assessment. A survey questioner is used to assess industry usage, interest and prioritization of attributes of Desktop Grids. We will conduct an experiment to show execution speedup as well as setup effort. Results. We found ten open source Desktop Grids fulfilling our requirements. The survey shows that Desktop Grids is used to a very little extent within industry while a majority of the participants state that there is an interest for Desktop Grids. As result of the experiment, we can say that we achieved very high speedup and that effort needed to setup a Desktop Grid is about 40 hours for one person with no prior experience to the selected Desktop Grid system. Conclusions. We conclude that industry organizations have a possible need for Desktop Grids but in order to be more successful, Desktop Grid developers must put more effort into areas as automated testing and code compilation.

As the amount of simultaneous users of distributed systems increase, scalability is becoming an important factor to consider during software development. Without sufficient scalability, systems might have a hard time to manage high loads, and might not be able to support a high amount of users. We have determined how scalability can best be implemented, and what extra costs this leads to. Our research is based on both a literature review, where we have looked at what others in the field of computer engineering thinks about scalability, and by implementing a highly scalable system of our own. In the end we came up with a couple of general pointers which can help developers to determine if they should focus on scalable development, and what they should consider if they choose to do so.

Escrever aplicações concorrentes é comumente tido como uma tarefa difícil e propensa a erros. Isso é particularmente verdade para aplicações escritas nas linguagens de uso mais disseminado, como C++ e Java, que oferecem um modelo de programação concorrente baseado em memória compartilhada e travas. Muitos consideram que o modo de se programar concorrentemente nessas linguagens é inadequado e dificulta a construção de sistemas livres de problemas como condições de corrida e deadlocks. Por conta disso e da popularização de processadores com múltiplos núcleos, nos últimos anos intensificou-se a busca por ferramentas mais adequadas para o desenvolvimento de aplicações concorrentes. Uma alternativa que vem ganhando atenção é o modelo de atores, proposto inicialmente na década de 1970 e voltado especificamente para a computação concorrente. Nesse modelo, cada ator é uma entidade isolada, que não compartilha memória com outros atores e se comunica com eles somente por meio de mensagens assíncronas. A implementação mais bem sucedida do modelo de atores é a oferecida por Erlang, a linguagem que (provavelmente) explorou esse modelo de forma mais eficiente. A linguagem Scala, surgida em 2003, roda na JVM e possui muitas semelhanças com Java. No entanto, no que diz respeito à programação concorrente, os criadores de Scala buscaram oferecer uma solução mais adequada. Assim, essa linguagem oferece uma biblioteca que implementa o modelo de atores e é fortemente inspirada nos atores de Erlang. O objetivo deste trabalho é explorar o uso do modelo de atores na linguagem Scala, especificamente no caso de aplicações distribuídas. Aproveitando o encapsulamento imposto pelos atores e a concorrência inerente ao modelo, propomos uma plataforma que gerencie a localização dos atores de modo totalmente transparente ao desenvolvedor e que tem o potencial de promover o desenvolvimento de aplicações eficientes e escaláveis. Nossa infraestrutura oferece dois serviços principais, ambos voltados ao gerenciamento da localização de atores: distribuição automática e migração. O primeiro deles permite que o programador escreva sua aplicação pensando apenas nos atores que devem ser instanciados e na comunicação entre esses atores, sem se preocupar com a localização de cada ator. É responsabilidade da infraestrutura definir onde cada ator será executado, usando algoritmos configuráveis. Já o mecanismo de migração permite que a execução de um ator seja suspensa e retomada em outro computador. A migração de atores possibilita que as aplicações se adaptem a mudanças no ambiente de execução. Nosso sistema foi construído tendo-se em mente possibilidades de extensão, em particular por algoritmos que usem o mecanismo de migração para melhorar o desempenho de uma aplicação. / Writing concurrent applications is generally seen as a dificult and error-prone task. This is particularly true for applications written in the most widely used languages, such as C++ and Java, which offer a concurrent programming model based upon shared memory and locks. Many claim that the way concurrent programming is done in these languages is inappropriate and makes it harder to build systems free from problems such as race conditions and deadlocks. For that reason, and also due to the popularization of multi-core processors, the pursuit for tools better suited to the development of concurrent applications has increased in recent years. An alternative that is gaining attention is the actor model, originally proposed in the 1970s and focused specifically in concurrent computing. In this model, each actor is an isolated entity, which does not share memory with other actors and communicates with them only by asynchronous message passing. The most successful implementation of the actor model is likely to be the one provided by Erlang, a language that supports actors in a very efficient way. The Scala language, which appeared in 2003, runs in the JVM and has many similarities with Java. Its creators, however, sought to provide a better solution for concurrent programming. So the language has a library that implements the actor model and is heavily inspired by Erlang actors. The goal of this work is to explore the usage of the actor model in Scala, speciffically for distributed applications. Taking advantage of the encapsulation imposed by actors and of the concurrency inherent to their model, we propose a platform that manages actor location in a way that is fully transparent to the developer. Our proposed platform has the potential of promoting the development of efficient and scalable applications. Our infrastructure offers two major services, both aimed at managing actor location: automatic distribution and migration. The first one allows the programmer to write his application thinking only about the actors that must be instantiated and about the communication among these actors, without being concerned with where each actor will be located. The infrastructure has the responsibility of defining where each actor will run. It accomplishes this task by using some configurable algorithm. The migration mechanism allows the execution of an actor to be suspended and resumed in another computer. Actor migration allows applications to adapt to changes in the execution environment. Our system has been built with extension possibilities in mind, and particularly to be extended by algorithms that use the migration mechanism to improve application performance.