HASLab

Permanent URI for this community

http://localhost:4000/handle/123456789/30
This service produces reliable software systems in contexts where correctness, responsiveness, robustness and security are essential. It develops integrated research in three lines: formal methods for software development, reliable distributed systems and information security.

Browse

Browsing HASLab by Author "5607"
  • Item
    Approaches to Conflict-free Replicated Data Types
    ( 2023) Paulo Sérgio Almeida ; 5607
  • Item
  • Item
    A Case for Partitioned Bloom Filters
    ( 2023) Paulo Sérgio Almeida ; 5607
    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.
  • Item
    A Case for Partitioned Bloom Filters
    ( 2022) Paulo Sérgio Almeida ; 5607
  • Item
    A Case for Partitioned Bloom Filters
    ( 2023) Paulo Sérgio Almeida ; 5607
    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.
  • Item
    Delta State Replicated Data Types
    ( 2018) Paulo Sérgio Almeida ; Ali Shoker ; Carlos Baquero ; 5607 ; 6172 ; 5596
  • Item
    Efficient synchronization of state-based CRDTs
    ( 2019) Paulo Sérgio Almeida ; Leitao,J ; Carlos Baquero ; Vítor Manuel Duarte ; 5607 ; 6704 ; 5596
    To ensure high availability in large scale distributed systems, Conflict-free Replicated Data Types (CRDTs) relax consistency by allowing immediate query and update operations at the local replica, with no need for remote synchronization. State-based CRDTs synchronize replicas by periodically sending their full state to other replicas, which can become extremely costly as the CRDT state grows. Delta-based CRDTs address this problem by producing small incremental states (deltas) to be used in synchronization instead of the full state. However, current synchronization algorithms for delta-based CRDTs induce redundant wasteful delta propagation, performing worse than expected, and surprisingly, no better than state-based. In this paper we: 1) identify two sources of inefficiency in current synchronization algorithms for delta-based CRDTs; 2) bring the concept of join decomposition to state-based CRDTs; 3) exploit join decompositions to obtain optimal deltas and 4) improve the efficiency of synchronization algorithms; and finally, 5) experimentally evaluate the improved algorithms. © 2019 IEEE.
  • Item
    Efficient Synchronization of State-based CRDTs
    ( 2019) Paulo Sérgio Almeida ; Leitao,J ; Carlos Baquero ; Vítor Manuel Duarte ; 5607 ; 6704 ; 5596
  • Item
    Exon: An Oblivious Exactly-Once Messaging Protocol
    ( 2022) Ziad Ali Kassam ; Paulo Sérgio Almeida ; Shoker,A ; 6720 ; 5607
  • Item
    An Experimental Evaluation of Tools for Grading Concurrent Programming Exercises
    ( 2023) José Orlando Pereira ; Paulo Sérgio Almeida ; Alcino Cunha ; 5602 ; 5607 ; 5612
  • Item
    Higher-order patterns in replicated data types
    ( 2019) Paulo Sérgio Almeida ; Leijnse,A ; Carlos Baquero ; 5607 ; 5596
    The design of Conflict-free Replicated Data Types traditionally requires implementing new designs from scratch to meet a desired behavior. Although there are composition rules that can guide the process, there has not been a lot of work explaining how existing data types relate to each other, nor work that factors out common patterns. To bring clarity to the field we explain underlying patterns that are common to flags, sets, and registers. The identified patterns are succinct and composable, which gives them the power to explain both current designs and open up the space for new ones. © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.
  • Item
    An oblivious observed-reset embeddable replicated counter
    ( 2022) Weidner,M ; Paulo Sérgio Almeida ; 5607
    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. © 2022 Owner/Author.
  • Item
    An oblivious observed-reset embeddable replicated counter
    ( 2022) Weidner,M ; Paulo Sérgio Almeida ; 5607
    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. © 2022 Owner/Author.
  • Item
    Time-limited Bloom Filter
    ( 2023) Paulo Sérgio Almeida ; Carlos Baquero ; 5607 ; 5596
  • Item
    Time-limited Bloom Filter
    ( 2023) Paulo Sérgio Almeida ; Carlos Baquero ; 5607 ; 5596