skip to main content

Explore Research Products in the NSF-PAR

Title: Stable and Efficient Piece-Selection in Multiple Swarm BitTorrent-like Peer-to-Peer Networks
Recent studies have suggested that the BitTorrent's rarest-first protocol, owing to its work-conserving nature, can become unstable in the presence of non-persistent users. Consequently, in any stable protocol, many peers are at some point endogenously forced to hold off their file-download activity. In this work, we propose a tunable piece-selection policy that minimizes this (undesirable) requisite by combining the (work-conserving) rarest-first protocol with only an appropriate share of the (non-work conserving) mode-suppression protocol. We refer to this policy as "Rarest-First with Probabilistic Mode-Suppression" or simply RFwPMS. We study RFwPMS under a stochastic model of the BitTorrent network that is general enough to capture multiple swarms of non-persistent users - each swarm having its own altruistic preferences that may or may not overlap with those of other swarms. Using a Lyapunov drift analysis, we show that RFwPMS is provably stable for all kinds of inter-swarm behaviors, and that the use of rarest-first instead of random-selection is indeed more justified. Our numerical results suggest that RFwPMS is scalable in the general multi-swarm setting and offers better performance than the existing stabilizing schemes like mode-suppression.  more » « less
Award ID(s):
2008130
NSF-PAR ID:
10253388
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
IEEE INFOCOM 2020 - IEEE Conference on Computer Communications
Page Range / eLocation ID:
1153 to 1162
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ( , IEEE/ACM Transactions on Networking)
    null (Ed.)
    The ability of a P2P network to scale its throughput up in proportion to the arrival rate of peers has recently been shown to be crucially dependent on the chunk sharing policy employed. Some policies can result in low frequencies of a particular chunk, known as the missing chunk syndrome, which can dramatically reduce throughput and lead to instability of the system. For instance, commonly used policies that nominally ``boost'' the sharing of infrequent chunks such as the well-known rarest-first algorithm have been shown to be unstable. We take a complementary viewpoint, and instead consider a policy that simply prevents the sharing of the most frequent chunk(s), that we call mode-suppression. We also consider a more general version that suppresses the mode only if the mode frequency is larger than the lowest frequency by a fixed threshold. We prove the stability of mode-suppression using Lyapunov techniques, and use a Kingman bound argument to show that the total download time does not increase with peer arrival rate. We then design versions of mode-suppression that sample a small number of peers at each time, and construct noisy mode estimates by aggregating these samples over time. We show numerically that mode suppression stabilizes and outperforms all other recently proposed chunk sharing algorithms, and via integration into BitTorrent implementation operating over the ns-3 that it ensures stable, low sojourn time operation in a real-world setting. 
    more » « less
  2. ; ( , Frontiers in Microbiology)
    Introduction

    MrpC, a member of the CRP/Fnr transcription factor superfamily, is necessary to induce and control the multicellular developmental program of the bacterium,Myxococcus xanthus. During development, certain cells in the population first swarm into haystack-shaped aggregates and then differentiate into environmentally resistant spores to form mature fruiting bodies (a specialized biofilm).mrpCtranscriptional regulation is controlled by negative autoregulation (NAR).

     Methods

    Wild type and mutantmrpCpromoter regions were fused to a fluorescent reporter to examine effects onmrpCexpression in the population and in single cellsin situ. Phenotypic consequences of the mutantmrpCpromoter were assayed by deep convolution neural network analysis of developmental movies, sporulation efficiency assays, and anti-MrpC immunoblot. In situ analysis of single cell MrpC levels in distinct populations were assayed with an MrpC-mNeonGreen reporter.

     Results

    Disruption of MrpC binding sites within themrpCpromoter region led to increased and broadened distribution ofmrpCexpression levels between individual cells in the population. Expression ofmrpCfrom the mutant promoter led to a striking phenotype in which cells lose synchronized transition from aggregation to sporulation. Instead, some cells abruptly exit aggregation centers and remain locked in a cohesive swarming state we termed developmental swarms, while the remaining cells transition to spores inside residual fruiting bodies.In situexamination of a fluorescent reporter for MrpC levels in developmental subpopulations demonstrated cells locked in the developmental swarms contained MrpC levels that do not reach the levels observed in fruiting bodies.

     Discussion

    Increased cell-to-cell variation inmrpCexpression upon disruption of MrpC binding sites within its promoter is consistent with NAR motifs functioning to reducing noise. Noise reduction may be key to synchronized transition of cells in the aggregation state to the sporulation state. We hypothesize a novel subpopulation of cells trapped as developmental swarms arise from intermediate levels of MrpC that are sufficient to promote aggregation but insufficient to trigger sporulation. Failure to transition to higher levels of MrpC necessary to induce sporulation may indicate cells in developmental swarms lack an additional positive feedback signal required to boost MrpC levels.

     
    more » « less
  3. ; ( , Catalysts)
    In this study we investigate the Diels–Alder reaction between methyl acrylate and butadiene, which is catalyzed by BF3 Lewis acid in explicit water solution, using URVA and Local Mode Analysis as major tools complemented with NBO, electron density and ring puckering analyses. We considered four different starting orientations of methyl acrylate and butadiene, which led to 16 DA reactions in total. In order to isolate the catalytic effects of the BF3 catalyst and those of the water environment and exploring how these effects are synchronized, we systematically compared the non-catalyzed reaction in gas phase and aqueous solution with the catalyzed reaction in gas phase and aqueous solution. Gas phase studies were performed at the B3LYP/6-311+G(2d,p) level of theory and studies in aqueous solution were performed utilizing a QM/MM approach at the B3LYP/6-311+G(2d,p)/AMBER level of theory. The URVA results revealed reaction path curvature profiles with an overall similar pattern for all 16 reactions showing the same sequence of CC single bond formation for all of them. In contrast to the parent DA reaction with symmetric substrates causing a synchronous bond formation process, here, first the new CC single bond on the CH2 side of methyl acrylate is formed followed by the CC bond at the ester side. As for the parent DA reaction, both bond formation events occur after the TS, i.e., they do not contribute to the energy barrier. What determines the barrier is the preparation process for CC bond formation, including the approach diene and dienophile, CC bond length changes and, in particular, rehybridization of the carbon atoms involved in the formation of the cyclohexene ring. This process is modified by both the BF3 catalyst and the water environment, where both work in a hand-in-hand fashion leading to the lowest energy barrier of 9.06 kcal/mol found for the catalyzed reaction R1 in aqueous solution compared to the highest energy barrier of 20.68 kcal/mol found for the non-catalyzed reaction R1 in the gas phase. The major effect of the BF3 catalyst is the increased mutual polarization and the increased charge transfer between methyl acrylate and butadiene, facilitating the approach of diene and dienophile and the pyramidalization of the CC atoms involved in the ring formation, which leads to a lowering of the activation energy. The catalytic effect of water solution is threefold. The polar environment leads also to increased polarization and charge transfer between the reacting species, similar as in the case of the BF3 catalyst, although to a smaller extend. More important is the formation of hydrogen bonds with the reaction complex, which are stronger for the TS than for the reactant, thus stabilizing the TS which leads to a further reduction of the activation energy. As shown by the ring puckering analysis, the third effect of water is space confinement of the reacting partners, conserving the boat form of the six-member ring from the entrance to the exit reaction channel. In summary, URVA combined with LMA has led to a clearer picture on how both BF3 catalyst and aqueous environment in a synchronized effort lower the reaction barrier. These new insights will serve to further fine-tune the DA reaction of methyl acrylate and butadiene and DA reactions in general. 
    more » « less
  4. ; ( , Thirteenth International Conference on Swarm Intelligence (ANTS 2022))
    The house hunting behavior of the Temnothorax albipennis ant allows the colony to explore several nest choices and agree on the best one. Their behavior serves as the basis for many bio-inspired swarm models to solve the same problem. However, many of the existing site selection models in both insect colony and swarm literature test the model’s accuracy and decision time only on setups where all potential site choices are equidistant from the swarm’s starting location. These models do not account for the geographic challenges that result from site choices with different geometry. For example, although actual ant colonies are capable of consistently choosing a higher quality, further site instead of a lower quality, closer site, existing models are much less accurate in this scenario. Existing models are also more prone to committing to a low quality site if it is on the path between the agents’ starting site and a higher quality site. We present a new model for the site selection problem and verify via simulation that is able to better handle these geographic challenges. Our results provide insight into the types of challenges site selection models face when distance is taken into account. Our work will allow swarms to be robust to more realistic situations where sites could be distributed in the environment in many different ways. 
    more » « less
  5. ; ( , Thirteenth International Conference on Swarm Intelligence (ANTS 2022))
    The house hunting behavior of the Temnothorax albipennis ant allows the colony to explore several nest choices and agree on the best one. Their behavior serves as the basis for many bio-inspired swarm models to solve the same problem. However, many of the existing site selection models in both insect colony and swarm literature test the model’s accuracy and decision time only on setups where all potential site choices are equidistant from the swarm’s starting location. These models do not account for the geographic challenges that result from site choices with different geometry. For example, although actual ant colonies are capable of consistently choosing a higher quality, further site instead of a lower quality, closer site, existing models are much less accurate in this scenario. Existing models are also more prone to committing to a low quality site if it is on the path between the agents’ starting site and a higher quality site. We present a new model for the site selection problem and verify via simulation that is able to better handle these geographic challenges. Our results provide insight into the types of challenges site selection models face when distance is taken into account. Our work will allow swarms to be robust to more realistic situations where sites could be distributed in the environment in many different ways. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email