Browsing by Author "Yu, Haifeng"

Now showing 1 - 4 of 4
  • No Thumbnail Available
    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.
  • No Thumbnail Available
    Item
    On the Power of Randomization in Distributed Algorithms in Dynamic Networks with Adaptive Adversaries*
    (2020-09-16) Jahja, Irvan; Yu, Haifeng; Hou, Ruomu
    This paper investigates the power of randomization in general distributed algorithms in dynamic networks where the network’s topology may evolve over time, as determined by some adaptive adversary. In such a context, randomization may help algorithms to better deal with i) “bad” inputs to the algorithm, and ii) evolving topologies generated by “bad” adaptive adversaries. We prove that randomness offers limited power to better deal with “bad” adaptive adversary. We define a simple notion of prophetic adversary for determining the evolving topologies. Such an adversary accurately predicts all randomness in the algorithm beforehand, and hence the randomness will be useless against “bad” prophetic adversaries. Given a randomized algorithm P whose time complexity satisfies some mild conditions, we prove that P can always be converted to a new algorithm Q with comparable time complexity, even when Q runs against prophetic adversaries. This
  • No Thumbnail Available
    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.
  • No Thumbnail Available
    Item
    Sublinear Algorithms in T -interval Dynamic Networks
    (2020-05-20) Jahja, Irvan; Yu, Haifeng
    We consider standard T -interval dynamic networks, under the synchronous timing model and the broadcast CONGEST model. In a T -interval dynamic network, the set of nodes is always fixed and there are no node failures. The edges in the network are always undirected, but the set of edges in the topology may change arbitrarily from round to round, as determined by some adversary and subject to the following constraint: For every T consecutive rounds, the topologies in those rounds must contain a common connected spanning subgraph. Let Hr to be the maximum (in terms of number of edges) such subgraph for round r through r +T − 1. We define the backbone diameter d of a T -interval dynamic network to be the maximum diameter of all such Hr ’s, for r ≥ 1. We use n to denote the number of nodes in the network. Within such a context, we consider a range of fundamental distributed computing problems including zount/Max/Median/Sum/LeaderElect/Consensus/ConfirmedFlood. Existing algorithms for these problems all have time complexity of Ω(n) rounds, even for T = ∞ and even when d is as small as O(1). This paper presents a novel O(d3 log2 n) deterministic algorithm for computing Count, for T -interval dynamic networks with T ≥ c · d2 log2 n. Here c is a (sufficiently large) constant independent of d, n, and T . To our knowledge, our algorithm is the very first such algorithm whose complexity does not contain a Θ(n) term. For d = O(na ) with constant a < 13, our deterministic algorithm has o(n) complexity, which is better than all (both randomized and deterministic) existing Count algorithms in this setting. For d = O(polylog(n)), our algorithm is exponentially faster. Following the frameworkof our Count algorithm, this paper further develops novel algorithms for solving Max/Median/Sum/LeaderElect/ Consensus/ ConfirmedFlood, while incurring either O(d3 log2 n) or O(d3 log3 n) complexity. Again, for all these problems, our algorithms are the first ones whose time complexity does not contain a Θ(n) term.