Browsing by Author "YU, Haifeng"

Now showing 1 - 7 of 7
  • No Thumbnail Available
    Item
    The Cost of Fault Tolerance in Multi-Party Communication Complexity
    (2012-05-17) CHEN, Binbin; YU, Haifeng; ZHAO, Yuda; GIBBONS, Philip B.
    Multi-party communication complexity involves distributed computation of a function over inputs held by multiple distributed players. A key focus of distributed computing research, since the very beginning, has been to tolerate crash failures. It is thus natural to ask “If we want to compute a certain function in a fault-tolerant way, what will the communication complexity be?” This natural question, interestingly, has not been formally posed and thoroughly studied prior to this work. Whether fault-tolerant communication complexity is interesting to study largely depends on how big a difference failures make. This paper proves that the impact of failures is significant, at least for the SUM aggregation function in general networks: As our central contribution, we prove that there exists (at least) an exponential gap between the non-fault-tolerant and fault-tolerant communication complexity of SUM. Our results also imply the optimality (within polylog factors) of some recent fault-tolerant protocols for computing SUM via duplicate-insensitive techniques, thereby answering an open question as well. Part of our results are obtained via a novel reduction from a new two-party problem UNIONSIZECP that we introduce. UNIONSIZECP comes with a novel cycle promise, which is the key enabler of our reduction. We further prove that this cycle promise and UNIONSIZECP likely play a fundamental role in reasoning about fault-tolerant communication complexity.
  • 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
    DCast: Sustaining Collaboration despite Rational Collusion
    (2011-02-07) YU, Haifeng; GIBBONS, Phillip B.; SHI, Chenwei
    A key and well-known problem in large-scale collaborative distributed systems is how to incentivize the rational/selfish users so that they will properly collaborate. Within such context, this paper focuses on designing incentive mechanisms for overlay multicast systems. A key limitation shared by existing proposals on the problem is that they are no longer able to provide proper incentives and thus will collapse when rational users collude or launch sybil attacks. This work explicitly aims to properly sustain collaboration despite collusion and sybil attacks by rational users. To this end, we propose a new decentralized DCast multicast protocol that uses a novel mechanism with debt-links and circulating debts. We formally prove that the protocol offers a novel concept of safety-net guarantee: A user running the protocol will always obtain a reasonably good utility despite the deviation of any number of rational users that potentially collude or launch sybil attacks. Our prototyping as well as simulation demonstrates the feasibility and safety-net guarantee of our design in practice.
  • No Thumbnail Available
    Item
    Near-Optimal Communication-Time Tradeoff in Fault-Tolerant Computation of Aggregate Functions
    (2014-05-31) ZHAO, Yuda; YU, Haifeng; CHEN, Binbin
    This paper considers the problem of computing general commutative and associative aggregate functions (such as SUM) over distributed inputs held by nodes in a distributed system, while tolerating failures. Specifically, there are N nodes in the system, and the topology among them is modeled as a general undirected graph. Whenever a node sends a message, the message is received by all of its neighbors in the graph. Each node has an input, and the goal is for a special root node (e.g., the base station in wireless sensor networks or the gateway node in wireless ad hoc networks) to learn a certain commutative and associate aggregate of all these inputs. All nodes in the system except the root node may experience crash failures, with the total number of edges incidental to failed nodes being upper bounded by f. The timing model is synchronous where protocols proceed in rounds. Within such a context, we focus on the following question: Under any given constraint on time complexity, what is the lowest communication complexity, in terms of the number of bits sent (i.e., locally broadcast) by each node, needed for computing general commutative and associate aggregate functions? This work, for the first time, reduces the gap between the upper bound and the lower bound for the above question from polynomial to polylog. To achieve this reduction, we present significant improvements over both the existing upper bounds and the existing lower bounds on the problem.
  • 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.
  • No Thumbnail Available
    Item
    SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks
    (2008-02-05) YU, Haifeng; GIBBONS, Phillip B.; XIAO, Feng
    Decentralized distributed systems such as peer-to-peer systems are particularly vulnerable to {\em sybil attacks}, where a malicious user pretends to have multiple identities (called {\em sybil nodes}). Without a trusted central authority, defending against sybil attacks is quite challenging. Among the small number of decentralized approaches, our recent SybilGuard protocol leverages a key insight on social networks to bound the number of sybil nodes accepted. Although its direction is promising, SybilGuard can allow a large number of sybil nodes to be accepted. Furthermore, SybilGuard assumes that social networks are fast mixing, which has never been confirmed in the real world. This paper presents the novel SybilLimit protocol that leverages the same insight as SybilGuard but offers dramatically improved and near-optimal guarantees. The number of sybil nodes accepted is reduced by a factor of $\Theta(\sqrt{n})$, or around 200 times in our experiments for a million-node system. We further prove that SybilLimit's guarantee is at most a $\log n$ factor away from optimal, when considering approaches based on fast-mixing social networks. Finally, based on three large-scale real-world social networks, we provide the first evidence that real-world social networks are indeed fast mixing. This validates the fundamental assumption behind SybilLimit's and SybilGuard's approach.