WebRTC enables browsers to exchange data directly but the number of possible concurrent connections to a single source is limited. We overcome the limitation by organizing participants in a fat-tree overlay: when the maximum number of connections of a tree node is reached, the new participants connect to the node's children. Our design quickly scales when a large number of participants join in a short amount of time, by relying on a novel scheme that only requires local information to route connection messages: the destination is derived from the hash value of the combined identifiers of the message's source and of the node that is holding the message. The scheme provides deterministic routing of a sequence of connection messages from a single source and probabilistic balancing of newer connections among the leaves. We show that this design puts at least 83 of nodes at the same depth as a deterministic algorithm, can connect a thousand browser windows in 21-55 seconds in a local network, and can be deployed for volunteer computing to tap into 320 cores in less than 30 seconds on a local network to increase the total throughput on the Collatz application by two orders of magnitude compared to a single core.
@cite_41: Live video streaming applications have gained great popularity among users but exert great pressure on video servers and the Internet. Peer-to-Peer (P2P) networks provide an attractive solution due to their low cost and high scalability. A large number of P2P live video streaming schemes have been proposed and many deployments have appeared on the Internet. These schemes pursue vastly diverse directions, from mimicking IP multicast to BitTorrent-like swarming to distributed hash tables. In this paper, we provide a comprehensive and in-depth survey of P2P live video streaming schemes from an algorithmic perspective. Our purpose is to acquaint future designers with the critical design choices and their impacts on system performance. The primary objective of a P2P live video streaming system is to distribute packets from the video source to peers, and the collective paths through which a packet traverses form a tree. We focus on three aspects of how these trees are formed: determining the supplier-receiver relationships for each packet, handling the departure of the supplier or receiver before their relationship expires, and handling lost packets. We identify critical design choices in each aspect and propose a taxonomy according to these choices. Because the surveyed papers use different performance metrics and the reported results are heavily influenced by their experimental settings, we consider two measures to identify the impact of each design choice: we use a set of "internal" metrics in addition to the commonly used "external" metrics, and we examine performance metrics of schemes that have made the same design choice. For better understanding of how the design choices interact with one another and exposing future designers to the design choices specific to each individual scheme, we also provide systematic summaries for a large number of schemes.
@cite_36: Distributed computing using PCs volunteered by the public can provide high computing capacity at low cost. However, computational results from volunteered PCs have a non-negligible error rate, so result validation is needed to ensure overall correctness. A generally applicable technique is "redundant computing", in which each computation is done on several separate computers, and results are accepted only if there is a consensus. Variations in numerical processing between computers (due to a variety of hardware and software factors) can lead to different results for the same task. In some cases, this can be addressed by doing a "fuzzy comparison" of results, so that two results are considered equivalent if they agree within given tolerances. However, this approach is not applicable to applications that are "divergent", that is, for which small numerical differences can produce large differences in the results. In this paper we examine the problem of validating results of divergent applications. We present a novel approach called homogeneous redundancy (HR), in which the redundant instances of a computation are dispatched to numerically identical computers, allowing strict equality comparison of the results. HR has been deployed in Predictor@home, a world-wide community effort to predict protein structure from sequence.
@cite_12: The large penetration and continued growth in ownership of personal electronic devices represents a freely available and largely untapped source of computing power. Moreover, the large environmental and social impact of producing these devices suggests we should better use those that already exist. We aim to make these devices available for parallel computations to both scientists and other programmers of the general public, for their personal projects, and in the simplest way possible to program and to deploy. We named our approach to distributed computing personal volunteer computing. We designed, implemented, and tested Pando, a new distributed computing tool based on a declarative concurrent programming model, organized around the pull-stream design pattern, and implemented using JavaScript, WebRTC, and WebSockets. This tool enables a dynamically varying number of failure-prone personal devices contributed by volunteers to parallelize the application of a function on a stream of values, by using the devices' browsers. To illustrate Pando's capabilities, to show its benefits as well as its limitations, we implemented a variety of applications including crypto-currency mining, hyper-parameter optimization in machine learning, crowd computing, and open data processing and tested it using diverse devices we have accumulated over the years. Pando, both as a tool and a reference design, should therefore be a useful addition to the parallel toolbox of a multitude of users and a complementary approach to existing parallel and distributed computing alternatives.
Extensive work on tree overlays for multicast applications has been done since the 90s @cite_41 , in which the same data is disseminated from a single source to tens and up to millions of participants. Typical applications of volunteer computing have different data transfer patterns because each participant receives a different sub-set of data. BOINC submits the same computation to a small number of participants (at least three) until a majority agrees @cite_36 , while the current version of Pando @cite_12 does not use redundancy because the code is executed on trusted devices. In addition, in both cases, each participant will return different results to the root.