Browsing by Author "JAHJA, Irvan"

Now showing 1 - 3 of 3
  • No Thumbnail Available
    Item
    The Cost of Unknown Diameter in Dynamic Networks *
    (2016-04-25) YU, Haifeng; ZHAO, Yuda; JAHJA, Irvan
    For dynamic networks with unknown diameter, we prove novel lower bounds on the time complexity of a range of basic distributed computing problems. Together with trivial upper bounds under dynamic networks with known diameter for these problems, our lower bounds show that the complexitiesof all these problems are sensitive to whether the diameter is known to the protocol beforehand: Not knowing the diameter increases the time complexities by a large poly(N) factor as compared to when the diameter is known, resulting in an exponential gap. Our lower bounds are obtained via communication complexity arguments and by reducing from the two-party DisjointnessCP problem. We further prove that sometimes this large poly(N) cost can be completely avoided if the protocol is given a good estimate on N. In other words, having such an estimate makes some problems no longer sensitive to unknown diameter.
  • No Thumbnail Available
    Item
    Randomized View Reconciliation in Permissionless Distributed Systems
    HOU, Ruomu; JAHJA, Irvan; LUU, Loi; SAXENA, Prateek; YU, Haifeng
    In a sybil attack, an adversary creates a large number of fake identities/nodes and have them join the system. Computational puzzles have long been investigated as a possible sybil defense: If a node fails to solve the puzzle in a timely fashion, it will no longer be accepted by other nodes. However, it is still possible for a malicious node to behave in such a way that it is accepted by some honest nodes but not other honest nodes. This results in different honest nodes having different views on which set of nodes should form the system. Such view divergence, unfortunately, breaks the overarching assumption required by many existing security protocols. Partly spurred by the growing popularity of Bitcoin, researchers have recently formalized the above view divergence problem and proposed interesting solutions (which we call view reconciliation protocols). For example, in CRYPTO 2015, Andrychowicz and Dziembowski proposed a view reconciliation protocol with O (N) time complexity, with N being the number of honest nodes in the system. All existing view reconciliation protocols so far have a similar O(N) time complexity. As this paper’s main contribution, we propose a novel view reconciliation protocol with a time complexity of only O( ln N/ ln ln N ). To achieve such an exponential improvement, we aggressively exploit randomization.
  • No Thumbnail Available
    Item
    Some Lower Bounds in Dynamic Networks with Oblivious Adversaries*
    JAHJA, Irvan; YU, Haifeng; ZHAO, Yuda
    This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel (d + poly(m)) lower bounds on their time complexity (in terms of rounds). Here d is the dynamic diameter of the dynamic network andmis the total number of nodes. Before this work, the only known lower bounds on these problems under oblivious adversaries were the trivial (d) lower bounds. Our novel lower bounds are hence the first non-trivial lower bounds and also the first lower bounds with a poly(m) term. Our proof relies on a novel reduction from a certain two-party communication complexity problem. Our central proof technique is unique in the sense that we consider the communication complexity with a special leaker. The leaker helps Alice and Bob in the two-party problem, by disclosing to Alice and Bob certain “non-critical” information about the problem instance that they are solving.