Technical Reports

Permanent URI for this collection


Recent Submissions

Now showing 1 - 5 of 417
  • Item
    Using Multi-dimensional Quorums for Optimal Resilience in Multi-resource Blockchains
    (2023-09-01) Yucheng Sun; Ruomu Hao; Haifeng Yu
    Permissionless blockchains commonly use resource challenges to defend against sybil attacks. For example, popular resource challenge designs include Proof-of-Work and Proof-of-Stake. It is well-known that simultaneously exploiting multiple resources can help make a permissionless blockchain more robust. Existing efforts along this direction, however, all fail to provide a complete answer to the central question of how to combine PoW and PoS, or multiple resources in general, to achieve optimal resilience. As our central contribution, this work gives complete answers to this central question.
  • Item
    Optimistic Fast Confirmation While Tolerating Malicious Majority in Blockchains
    (2023-04-06) Hou, Ruomu; Yu, Haifeng
    The robustness of a blockchain against the adversary is often characterized by the maximum fraction (fmax) of adversarial power that it can tolerate. While most existing blockchains can only tolerate fmax < 0.5 or lower, there are some blockchain systems that are able to tolerate a malicious majority, namely fmax >= 0.5. A key price paid by such blockchains, however, is their large confirmation latency. This work aims to significantly reduce the confirmation latency in such blockchains, under the common case where the actual fraction f of adversarial power is relatively small. To this end, we propose a novel blockchain called FLINT. FLINT tolerates fmax >= 0.5 and can give optimistic execution (i.e., fast confirmation) whenever f is relatively small. Our experiments show that the fast confirmation in FLINT only takes a few minutes, as compared to several hours of confirmation latency in prior works.
  • Item
    Achieving Sublinear Complexity under Constant 𝑇 in 𝑇 -interval Dynamic Networks
    (2022-05-26) Hou, Ruomu; Jahja, Irvan; Sun, Yucheng; Wu, Jiyan; Yu, Haifeng
    This paper considers standard {\em $T$-interval dynamic networks}, where the $N$ nodes in the network proceed in lock-step {\em rounds}, and where the topology of the network can change arbitrarily from round to round, as determined by an {\em adversary}. The adversary promises that in every $T$ consecutive rounds, the $T$ (potentially different) topologies in those $T$ rounds contain a common connected subgraph that spans all nodes. Within such a context, we propose novel algorithms for solving some fundamental distributed computing problems such as Count/Consensus/Max. Our algorithms are the first algorithms whose complexities do not contain an $\Omega(N)$ term, under constant $T$ values. Previous sublinear algorithms require significantly larger $T$ values.
  • Item
    Survey on Data Quality and Provenance
    (2021-11) Schmitz, Martin
    This technical report summarizes research on data quality, provenance and truth discovery from the last decades. It examines opportunities to use machine learning methods to enhance data quality and provenance. This report can serve as a starting point to nd the key publications of the topics "provenance" and "data quality" and to do further research in those areas in general as well as in combination with machine learning algorithms.
  • Item
    Temporal Keyword Search with Aggregates and Group-By
    (2021-07) Gao, Qiao; Lee, Mong Li; Ling, Tok Wang
    Abstract. Temporal keyword search enables non-expert users to query temporal relational databases with time conditions. However, aggregates and group-by are currently not supported in temporal keyword search, which hinders querying of statistical information in temporal databases. This work proposes a framework to support aggregate, group-by and time condition in temporal keyword search. We observe that simply combining non-temporal keyword search with aggregates, group-by, and temporal aggregate operators may lead to incorrect and meaningless results as a result of data duplication over time periods. As such, our framework utilizes Object-Relationship-Attribute semantics to identify a unique at-tribute set in the join sequence relation and remove data duplicates from this attribute set to ensure the correctness of aggregate and group-by computation. We also consider the time period in which temporal at-tributes occur when computing aggregate to return meaningful results. Experiment results demonstrate the importance of these steps to retrieve correct results for keyword queries over temporal databases.