Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
About

About

Paulo Sérgio Almeida is an Assistant Professor at the Department of Informatics at University of Minho, and a researcher at HASLab / INESC TEC. He obtained a MSc degree from University of Porto in 1994 and a PhD degree in Computer Science from Imperial College London in 1998. His research activities have been in the area of distributed systems, namely in causality tracking mechanisms, eventually consistent non-relational databases, fault-tolerant distributed aggregation algorithms, bloom filters, and distributed algorithms in graphs. In recent years the main focus of research has been on Conflict-free Replicated Data Types.

Interest
Topics
Details

Details

  • Name

    Paulo Sérgio Almeida
  • Role

    Senior Researcher
  • Since

    01st November 2011
001
Publications

2023

An Experimental Evaluation of Tools for Grading Concurrent Programming Exercises

Authors
Barros, M; Ramos, M; Gomes, A; Cunha, A; Pereira, J; Almeida, PS;

Publication
Formal Techniques for Distributed Objects, Components, and Systems - 43rd IFIP WG 6.1 International Conference, FORTE 2023, Held as Part of the 18th International Federated Conference on Distributed Computing Techniques, DisCoTec 2023, Lisbon, Portugal, June 19-23, 2023, Proceedings

Abstract

2023

Time-limited Bloom Filter

Authors
Rodrigues, A; Shtul, A; Baquero, C; Almeida, PS;

Publication
Proceedings of the 38th ACM/SIGAPP Symposium on Applied Computing, SAC 2023, Tallinn, Estonia, March 27-31, 2023

Abstract

2023

A Case for Partitioned Bloom Filters

Authors
Almeida, PS;

Publication
IEEE TRANSACTIONS ON COMPUTERS

Abstract
In a partitioned Bloom Filter (PBF) the bit vector is split into disjoint parts, one per hash function. Contrary to hardware designs, where they prevail, software implementations mostly ignore PBFs, considering them worse than standard Bloom filters (SBF), due to the slightly larger false positive rate (FPR). In this paper, by performing an in-depth analysis, first we show that the FPR advantage of SBFs is smaller than thought; more importantly, by deriving the per-element FPR, we show that SBFs have weak spots in the domain: elements that test as false positives much more frequently than expected. This is relevant in scenarios where an element is tested against many filters. Moreover, SBFs are prone to exhibit extremely weak spots if naive double hashing is used, something occurring in mainstream libraries. PBFs exhibit a uniform distribution of the FPR over the domain, with no weak spots, even using naive double hashing. Finally, we survey scenarios beyond set membership testing, identifying many advantages of having disjoint parts, in designs using SIMD techniques, for filter size reduction, test of set disjointness, and duplicate detection in streams. PBFs are better, and should replace SBFs, in general purpose libraries and as the base for novel designs.

2023

Approaches to Conflict-free Replicated Data Types

Authors
Almeida, PS;

Publication
CoRR

Abstract

2022

An Oblivious Observed-Reset Embeddable Replicated Counter

Authors
Weidner, M; Almeida, PS;

Publication
PAPOC'22: PROCEEDINGS OF THE 9TH PRINCIPLES AND PRACTICE OF CONSISTENCY FOR DISTRIBUTED DATA

Abstract
Embedding CRDT counters has shown to be a challenging topic, since their introduction in Riak Maps. The desire for obliviousness, where all information about a counter is fully removed upon key removal, faces problems due to the possibility of concurrency between increments and key removals. Previous state-based proposals exhibit undesirable reset-wins semantics, which lead to losing increments, unsatisfactorily solved through manual generation management in the API. Previous operation-based approaches depend on causal stability, being prone to unbounded counter growth under network partitions. We introduce a novel embeddable operation-based CRDT counter which achieves both desirable observed-reset semantics and obliviousness upon resets. Moreover, it achieves this while merely requiring FIFO delivery, allowing a tradeoff between causal consistency and faster information propagation, being more robust under network partitions.

Supervised
thesis

2022

Beyong Distributed Transctions through Exactly-once Exchanges

Author
Ziad Ali Kassam

Institution
UM

2022

Fiber Laser Plasma Spectroscopy for Real Time Underwater Element Analysis

Author
Miguel Fernandes Soares Ferreira

Institution
UP-FCUP

2021

Beyong Distributed Transctions through Exactly-once Exchanges

Author
Ziad Ali Kassam

Institution
UM

2020

Implementation and Evaluation of Tagged Causal Multicast as a Rust Library

Author
Carlos Duarte Afonso Pereira

Institution
UM

2020

Beyond Distributed Transactions through Exactly-once Exchanges

Author
Ziad Ali Kassam

Institution
UM