F. Araujo, J. Farinha, P. Domingues, G. C. Silaghi, and D. Kondo. A maximum independent set approach for collusion detection in voting pools. Journal of Parallel and Distributed Computing, 71(10):1356 - 1366, 2011.

[ bib | .pdf ]

From agreement problems to replicated software execution, we frequently find scenarios with voting pools. Unfortunately, Byzantine adversaries can join and collude to distort the results of an election. We address the problem of detecting these colluders, in scenarios where they repeatedly participate in voting decisions. We investigate different malicious strategies, such as naïve or colluding attacks, with fixed identifiers or in whitewashing attacks. Using a graph-theoretic approach, we frame collusion detection as a problem of identifying maximum independent sets. We then propose several new graph-based methods and show, via analysis and simulations, their effectiveness and practical applicability for collusion detection.

Keywords: Collusion detection

G. Silaghi, F. Araujo, L. M. Silva, P. Domingues, and A. Arenas. Defeating colluding nodes in desktop grid computing platforms. Journal of Grid Computing, 7(4):555-573, December 2009.

[ bib | .pdf ]

Desktop Grid systems reached a preeminent place among the most powerful computing platforms in the planet. Unfortunately, they are extremely vulnerable to mischief, because computing projects exert no administrative or technical control on volunteers. These can very easily output bad results, due to software or hardware glitches (resulting from over-clocking for instance), to get unfair computational credit, or simply to ruin the project. To mitigate this problem, Desktop Grid servers replicate work units and apply majority voting, typically on 2 or 3 results. In this paper, we observe that simple majority voting is powerless against malicious volunteers that collude to attack the project. We argue that to identify this type of attack and to spot colluding nodes, each work unit needs at least 3 voters. In addition, we propose to post-process the voting pools in two steps. i) In the first step, we use a statistical approach to identify nodes that were not colluding, but submitted bad results; ii) then, we use a rather simple principle to go after malicious nodes which acted together: they might have won conflicting voting pools against nodes that were not identified in step i. We use simulation to show that our heuristic can be quite effective against colluding nodes, in scenarios where honest nodes form a majority.

P. Domingues, B. Sousa, and L. M. Silva. Sabotage-Tolerance and Trust Management in Desktop Grid Computing. Future Generation Computation Systems, 23(7):904-912, August 2007, Elsevier Science Publishers.

[ bib | http ]

The success of grid computing in open environments like the Internet is highly dependent on the adoption of mechanisms to detect failures and malicious sabotage attempts. It is also required to maintain a trust management system that permits one to distinguish the trustable from the non-trustable participants in a global computation. Without these mechanisms, users with data-critical applications will never rely on desktop grids, and will rather prefer to support higher costs to run their computations in closed and secure computing systems. This paper discusses the topics of sabotage-tolerance and trust management. After reviewing the state-of-the-art, we present two novel techniques: a mechanism for sabotage detection and a protocol for distributed trust management. The proposed techniques are targeted at the paradigm of volunteer-based computing commonly used on desktop grids.

P. Domingues. Dependability Mechanisms for Desktop Grids. PhD thesis, University of Coimbra, December 2008.

[ bib | .pdf ]

It is a well-known fact that most of the computing power spread over the Internet simply goes unused, with CPU and other resources sitting idle most of the time: on average less than 5% of the CPU time is effectively used. Desktop grids are software infrastructures that aim to exploit the otherwise idle processing power, making it available to users that require computational resources to solve long-running applications. The outcome of some efforts to harness idle machines can be seen in public projects such as SETI@home and Folding@home that boost impressive performance figures, in the order of several hundreds of TFLOPS each. At the same time, many institutions, both academic and corporate, run their own desktop grid platforms. However, while desktop grids provide free computing power, they need to face important issues like fault tolerance and security, two of the main problems that harden the widespread use of desktop grid computing. In this thesis, we aim to exploit a set of fault tolerance techniques, such as checkpointing and redundant executions, to promote faster turnaround times. We start with an experimental study, where we analyze the availability of the computing resources of an academic institution. We then focus on the benefits of sharing checkpoints in both institutional and wide-scale environments. We also explore hybrid schemes, where the traditional centralized desktop grid organization is complemented with peer-to-peer resources. Another major issue regarding desktop grids is related with the level of trust that can be achieved relatively to the volunteered hosts that carry out the executions. We propose and explore several mechanisms aimed at reducing the waste of computational resources needed to detect incorrect computations. For this purpose, we detail a checkpoint-based scheme for early detection of errors. We also propose and analyze an invitation-based strategy coupled to a credit rewarding scheme, to allow the enrollment and filtering of more trustworthy and more motivated resource donors. To summarize, we propose and study several fault tolerance methodologies oriented toward a more efficient usage of resources, resorting to techniques such as checkpointing, replication and sabotage tolerance to fasten and to make more reliable executions that are carried over desktop grid resources. The usage of techniques like these ones will be of ultimate importance for the wider deployment of applications over desktop grids.

Keywords: Desktop grid, fault tolerance, dependability, BOINC, volunteer computing, checkpoint, scheduling

P. Domingues. Balanceamento de carga para aplicações paralelas com distribuição regular de dados executadas em sistemas distribuídos. Master's thesis, University of Coimbra, May 1999. (in Portuguese).

[ bib ]

P. Domingues. Programação em OpenCL. Revista Programar, (39):21-31, February 2013. (in Portuguese).

[ bib | .pdf ]

A norma OpenCL foi adotada por um vasto conjunto de grandes empresas da área da informática (AMD/ATI, NVIDIA, Intel, IBM, Samsung, Google, entre outras). Deste modo, ao contrário da plataforma CUDA que é uma plataforma proprietária que está apenas disponível para GPUs da NVIDIA, a norma OpenCL é suportada numa vasta gama de dispositivos desde as GPUs da AMD/ATI e da NVIDIA, ao processador Cell e ainda nas mais recentes placas gráficas do tipo HD e CPUs multicoreda Intel. Contudo, o suporte varia, sendo ainda poucos os dispositivos que disponibilizam a versão 1.2 da norma OpenCL publicada em Novembro de 2011 (Khronos Group OpenCL Working Group, 2012). Neste artigo introduzem-se os conceitos básicos de programação paralela na norma OpenCL, focando somente o OpenCL na perspetiva de dispositivos GPUs, dado ser esse o cenário mais comum.

P. Domingues. Introdução à Programação em CUDA. Revista Programar, (38):7-11, December 2012. (in Portuguese).

[ bib | .pdf ]

Nos últimos anos, as placas gráficas (GPU – Graphical Processing Unit) ganharam relevância no âmbito da computação paralela. De facto, os mais recentes modelos da NVIDIA e da AMD/ATI –- dois dos maiores construtores de placas gráficas - têm na ordem do milhar de núcleos de processamento, “core” na designação anglo-saxónica. Exemplo disso é a GPU NVIDIA GTX 680 que tem 1536 núcleos, estando creditada com um desempenho máximo (teórico) de 3.1 TFLOPS em cálculo de vírgula flutuante com precisão simples, sendo que um TFLOPS corresponde a 10^12 operações de vírgula flutuante por segundo.

Contudo, do ponto de vista de computação paralela, de pouco serve a existência de milhares de cores se o seu uso estiver limitado somente à produção e tratamento de gráficos. Foi pois a pensar na comunidade de computação paralela e no potencial mercado que essa representa, que a NVIDIA lançou em Novembro de 2006, a versão 1.0 da plataforma Compute Unified Device Architecture (CUDA). Embora limitado às GPU da NVIDIA, as sucessivas versões de CUDA tornaram possível o uso de GPU para o desenvolvimento e execução de computação paralela de larga escala. Em alguns cenários de computação – tratamento de imagens e video, processamento de dados, aplicações bioinformáticas, etc. – as GPU proporcionam velocidades de execução muito mais rápidas do que as alcançadas pelos processadores (CPU). Neste artigo introduzem-se os conceitos básicos de programação paralela para a plataforma CUDA.