@article{14663, abstract = {As a bottleneck in the direct synthesis of hydrogen peroxide, the development of an efficient palladium-based catalyst has garnered great attention. However, elusive active centers and reaction mechanism issues inhibit further optimization of its performance. In this work, advanced microkinetic modeling with the adsorbate–adsorbate interaction and nanoparticle size effect based on first-principles calculations is developed. A full mechanism uncovering the significance of adsorbate–adsorbate interaction is determined on Pd nanoparticles. We demonstrate unambiguously that Pd(100) with main coverage species of O2 and H is beneficial to H2O2 production, being consistent with experimental operando observation, while H2O forms on Pd(111) covered by O species and Pd(211) covered by O and OH species. Kinetic analyses further enable quantitative estimation of the influence of temperature, pressure, and particle size. Large-size Pd nanoparticles are found to achieve a high H2O2 reaction rate when the operating conditions are moderate temperature and higher oxygen partial pressure. We reveal that specific facets of the Pd nanoparticles are crucial factors for their selectivity and activity. Consistent with the experiment, the production of H2O2 is discovered to be more favorable on Pd nanoparticles containing Pd(100) facets. The ratio of H2/O2 induces substantial variations in the coverage of intermediates of O2 and H on Pd(100), resulting in a change in product selectivity.}, author = {Zhao, Jinyan and Yao, Zihao and Bunting, Rhys and Hu, P. and Wang, Jianguo}, issn = {2155-5435}, journal = {ACS Catalysis}, number = {22}, pages = {15054--15073}, publisher = {American Chemical Society}, title = {{Microkinetic modeling with size-dependent and adsorbate-adsorbate interactions for the direct synthesis of H₂O₂ over Pd nanoparticles}}, doi = {10.1021/acscatal.3c03893}, volume = {13}, year = {2023}, } @article{14664, abstract = {The architecture of self-assembled host molecules can profoundly affect the properties of the encapsulated guests. For example, a rigid cage with small windows can efficiently protect its contents from the environment; in contrast, tube-shaped, flexible hosts with large openings and an easily accessible cavity are ideally suited for catalysis. Here, we report a “Janus” nature of a Pd6L4 coordination host previously reported to exist exclusively as a tube isomer (T). We show that upon encapsulating various tetrahedrally shaped guests, T can reconfigure into a cage-shaped host (C) in quantitative yield. Extracting the guest affords empty C, which is metastable and spontaneously relaxes to T, and the T⇄C interconversion can be repeated for multiple cycles. Reversible toggling between two vastly different isomers paves the way toward controlling functional properties of coordination hosts “on demand”.}, author = {Hema, Kuntrapakam and Grommet, Angela B. and Białek, Michał J. and Wang, Jinhua and Schneider, Laura and Drechsler, Christoph and Yanshyna, Oksana and Diskin-Posner, Yael and Clever, Guido H. and Klajn, Rafal}, issn = {1520-5126}, journal = {Journal of the American Chemical Society}, number = {45}, pages = {24755--24764}, publisher = {American Chemical Society}, title = {{Guest encapsulation alters the thermodynamic landscape of a coordination host}}, doi = {10.1021/jacs.3c08666}, volume = {145}, year = {2023}, } @article{14667, abstract = {For large dimensional non-Hermitian random matrices X with real or complex independent, identically distributed, centered entries, we consider the fluctuations of f (X) as a matrix where f is an analytic function around the spectrum of X. We prove that for a generic bounded square matrix A, the quantity Tr f (X)A exhibits Gaussian fluctuations as the matrix size grows to infinity, which consists of two independent modes corresponding to the tracial and traceless parts of A. We find a new formula for the variance of the traceless part that involves the Frobenius norm of A and the L2-norm of f on the boundary of the limiting spectrum. }, author = {Erdös, László and Ji, Hong Chang}, issn = {0246-0203}, journal = {Annales de l'institut Henri Poincare (B) Probability and Statistics}, number = {4}, pages = {2083--2105}, publisher = {Institute of Mathematical Statistics}, title = {{Functional CLT for non-Hermitian random matrices}}, doi = {10.1214/22-AIHP1304}, volume = {59}, year = {2023}, } @article{14689, author = {Ing-Simmons, Elizabeth and Machnik, Nick N and Vaquerizas, Juan M.}, issn = {1546-1718}, journal = {Nature Genetics}, number = {12}, pages = {2053--2055}, publisher = {Springer Nature}, title = {{Reply to: Revisiting the use of structural similarity index in Hi-C}}, doi = {10.1038/s41588-023-01595-5}, volume = {55}, year = {2023}, } @article{14690, abstract = {Generalized multifractality characterizes system size dependence of pure scaling local observables at Anderson transitions in all 10 symmetry classes of disordered systems. Recently, the concept of generalized multifractality has been extended to boundaries of critical disordered noninteracting systems. Here we study the generalized boundary multifractality in the presence of electron-electron interaction, focusing on the spin quantum Hall symmetry class (class C). Employing the two-loop renormalization group analysis within the Finkel'stein nonlinear sigma model, we compute the anomalous dimensions of the pure scaling operators located at the boundary of the system. We find that generalized boundary multifractal exponents are twice larger than their bulk counterparts. Exact symmetry relations between generalized boundary multifractal exponents in the case of noninteracting systems are explicitly broken by the interaction.}, author = {Babkin, Serafim and Burmistrov, I}, issn = {2469-9969}, journal = {Physical Review B}, number = {20}, publisher = {American Physical Society}, title = {{Boundary multifractality in the spin quantum Hall symmetry class with interaction}}, doi = {10.1103/PhysRevB.108.205429}, volume = {108}, year = {2023}, } @inproceedings{14692, abstract = {The generic-group model (GGM) aims to capture algorithms working over groups of prime order that only rely on the group operation, but do not exploit any additional structure given by the concrete implementation of the group. In it, it is possible to prove information-theoretic lower bounds on the hardness of problems like the discrete logarithm (DL) or computational Diffie-Hellman (CDH). Thus, since its introduction, it has served as a valuable tool to assess the concrete security provided by cryptographic schemes based on such problems. A work on the related algebraic-group model (AGM) introduced a method, used by many subsequent works, to adapt GGM lower bounds for one problem to another, by means of conceptually simple reductions. In this work, we propose an alternative approach to extend GGM bounds from one problem to another. Following an idea by Yun [EC15], we show that, in the GGM, the security of a large class of problems can be reduced to that of geometric search-problems. By reducing the security of the resulting geometric-search problems to variants of the search-by-hypersurface problem, for which information theoretic lower bounds exist, we give alternative proofs of several results that used the AGM approach. The main advantage of our approach is that our reduction from geometric search-problems works, as well, for the GGM with preprocessing (more precisely the bit-fixing GGM introduced by Coretti, Dodis and Guo [Crypto18]). As a consequence, this opens up the possibility of transferring preprocessing GGM bounds from one problem to another, also by means of simple reductions. Concretely, we prove novel preprocessing bounds on the hardness of the d-strong discrete logarithm, the d-strong Diffie-Hellman inversion, and multi-instance CDH problems, as well as a large class of Uber assumptions. Additionally, our approach applies to Shoup’s GGM without additional restrictions on the query behavior of the adversary, while the recent works of Zhang, Zhou, and Katz [AC22] and Zhandry [Crypto22] highlight that this is not the case for the AGM approach.}, author = {Auerbach, Benedikt and Hoffmann, Charlotte and Pascual Perez, Guillermo}, booktitle = {21st International Conference on Theory of Cryptography}, isbn = {9783031486203}, issn = {1611-3349}, pages = {301--330}, publisher = {Springer Nature}, title = {{Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing}}, doi = {10.1007/978-3-031-48621-0_11}, volume = {14371}, year = {2023}, } @inproceedings{14693, abstract = {Lucas sequences are constant-recursive integer sequences with a long history of applications in cryptography, both in the design of cryptographic schemes and cryptanalysis. In this work, we study the sequential hardness of computing Lucas sequences over an RSA modulus. First, we show that modular Lucas sequences are at least as sequentially hard as the classical delay function given by iterated modular squaring proposed by Rivest, Shamir, and Wagner (MIT Tech. Rep. 1996) in the context of time-lock puzzles. Moreover, there is no obvious reduction in the other direction, which suggests that the assumption of sequential hardness of modular Lucas sequences is strictly weaker than that of iterated modular squaring. In other words, the sequential hardness of modular Lucas sequences might hold even in the case of an algorithmic improvement violating the sequential hardness of iterated modular squaring. Second, we demonstrate the feasibility of constructing practically-efficient verifiable delay functions based on the sequential hardness of modular Lucas sequences. Our construction builds on the work of Pietrzak (ITCS 2019) by leveraging the intrinsic connection between the problem of computing modular Lucas sequences and exponentiation in an appropriate extension field.}, author = {Hoffmann, Charlotte and Hubáček, Pavel and Kamath, Chethan and Krňák, Tomáš}, booktitle = {21st International Conference on Theory of Cryptography}, isbn = {9783031486234}, issn = {1611-3349}, location = {Taipei, Taiwan}, pages = {336--362}, publisher = {Springer Nature}, title = {{(Verifiable) delay functions from Lucas sequences}}, doi = {10.1007/978-3-031-48624-1_13}, volume = {14372}, year = {2023}, } @article{14709, abstract = {Amid the delays due to the global pandemic, in early October 2022, the auxin community gathered in the idyllic peninsula of Cavtat, Croatia. More than 170 scientists from across the world converged to discuss the latest advancements in fundamental and applied research in the field. The topics, from signalling and transport to plant architecture and response to the environment, show how auxin research must bridge from the molecular realm to macroscopic developmental responses. This is mirrored in this collection of reviews, contributed by participants of the Auxin 2022 meeting.}, author = {Del Bianco, Marta and Friml, Jiří and Strader, Lucia and Kepinski, Stefan}, issn = {1460-2431}, journal = {Journal of Experimental Botany}, number = {22}, pages = {6889--6892}, publisher = {Oxford University Press}, title = {{Auxin research: Creating tools for a greener future}}, doi = {10.1093/jxb/erad420}, volume = {74}, year = {2023}, } @article{14710, abstract = {The self-assembly of complex structures from a set of non-identical building blocks is a hallmark of soft matter and biological systems, including protein complexes, colloidal clusters, and DNA-based assemblies. Predicting the dependence of the equilibrium assembly yield on the concentrations and interaction energies of building blocks is highly challenging, owing to the difficulty of computing the entropic contributions to the free energy of the many structures that compete with the ground state configuration. While these calculations yield well known results for spherically symmetric building blocks, they do not hold when the building blocks have internal rotational degrees of freedom. Here we present an approach for solving this problem that works with arbitrary building blocks, including proteins with known structure and complex colloidal building blocks. Our algorithm combines classical statistical mechanics with recently developed computational tools for automatic differentiation. Automatic differentiation allows efficient evaluation of equilibrium averages over configurations that would otherwise be intractable. We demonstrate the validity of our framework by comparison to molecular dynamics simulations of simple examples, and apply it to calculate the yield curves for known protein complexes and for the assembly of colloidal shells.}, author = {Curatolo, Agnese I. and Kimchi, Ofer and Goodrich, Carl Peter and Krueger, Ryan K. and Brenner, Michael P.}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{A computational toolbox for the assembly yield of complex and heterogeneous structures}}, doi = {10.1038/s41467-023-43168-4}, volume = {14}, year = {2023}, } @article{14715, abstract = {We consider N trapped bosons in the mean-field limit with coupling constant λN = 1/(N − 1). The ground state of such systems exhibits Bose–Einstein condensation. We prove that the probability of finding ℓ particles outside the condensate wave function decays exponentially in ℓ.}, author = {Mitrouskas, David Johannes and Pickl, Peter}, issn = {1089-7658}, journal = {Journal of Mathematical Physics}, number = {12}, publisher = {AIP Publishing}, title = {{Exponential decay of the number of excitations in the weakly interacting Bose gas}}, doi = {10.1063/5.0172199}, volume = {64}, year = {2023}, } @article{14716, abstract = {Background: Antimicrobial resistance (AMR) poses a significant global health threat, and an accurate prediction of bacterial resistance patterns is critical for effective treatment and control strategies. In recent years, machine learning (ML) approaches have emerged as powerful tools for analyzing large-scale bacterial AMR data. However, ML methods often ignore evolutionary relationships among bacterial strains, which can greatly impact performance of the ML methods, especially if resistance-associated features are attempted to be detected. Genome-wide association studies (GWAS) methods like linear mixed models accounts for the evolutionary relationships in bacteria, but they uncover only highly significant variants which have already been reported in literature. Results: In this work, we introduce a novel phylogeny-related parallelism score (PRPS), which measures whether a certain feature is correlated with the population structure of a set of samples. We demonstrate that PRPS can be used, in combination with SVM- and random forest-based models, to reduce the number of features in the analysis, while simultaneously increasing models’ performance. We applied our pipeline to publicly available AMR data from PATRIC database for Mycobacterium tuberculosis against six common antibiotics. Conclusions: Using our pipeline, we re-discovered known resistance-associated mutations as well as new candidate mutations which can be related to resistance and not previously reported in the literature. We demonstrated that taking into account phylogenetic relationships not only improves the model performance, but also yields more biologically relevant predicted most contributing resistance markers.}, author = {Yurtseven, Alper and Buyanova, Sofia and Agrawal, Amay Ajaykumar A. and Bochkareva, Olga and Kalinina, Olga V V.}, issn = {1471-2180}, journal = {BMC Microbiology}, number = {1}, publisher = {Springer Nature}, title = {{Machine learning and phylogenetic analysis allow for predicting antibiotic resistance in M. tuberculosis}}, doi = {10.1186/s12866-023-03147-7}, volume = {23}, year = {2023}, } @article{14719, abstract = {Lithium–sulfur batteries are regarded as an advantageous option for meeting the growing demand for high-energy-density storage, but their commercialization relies on solving the current limitations of both sulfur cathodes and lithium metal anodes. In this scenario, the implementation of lithium sulfide (Li2S) cathodes compatible with alternative anode materials such as silicon has the potential to alleviate the safety concerns associated with lithium metal. In this direction, here, we report a sulfur cathode based on Li2S nanocrystals grown on a catalytic host consisting of CoFeP nanoparticles supported on tubular carbon nitride. Nanosized Li2S is incorporated into the host by a scalable liquid infiltration–evaporation method. Theoretical calculations and experimental results demonstrate that the CoFeP–CN composite can boost the polysulfide adsorption/conversion reaction kinetics and strongly reduce the initial overpotential activation barrier by stretching the Li–S bonds of Li2S. Besides, the ultrasmall size of the Li2S particles in the Li2S–CoFeP–CN composite cathode facilitates the initial activation. Overall, the Li2S–CoFeP–CN electrodes exhibit a low activation barrier of 2.56 V, a high initial capacity of 991 mA h gLi2S–1, and outstanding cyclability with a small fading rate of 0.029% per cycle over 800 cycles. Moreover, Si/Li2S full cells are assembled using the nanostructured Li2S–CoFeP–CN cathode and a prelithiated anode based on graphite-supported silicon nanowires. These Si/Li2S cells demonstrate high initial discharge capacities above 900 mA h gLi2S–1 and good cyclability with a capacity fading rate of 0.28% per cycle over 150 cycles.}, author = {Mollania, Hamid and Zhang, Chaoqi and Du, Ruifeng and Qi, Xueqiang and Li, Junshan and Horta, Sharona and Ibáñez, Maria and Keller, Caroline and Chenevier, Pascale and Oloomi-Buygi, Majid and Cabot, Andreu}, issn = {1944-8252}, journal = {ACS Applied Materials and Interfaces}, number = {50}, pages = {58462–58475}, publisher = {American Chemical Society}, title = {{Nanostructured Li₂S cathodes for silicon-sulfur batteries}}, doi = {10.1021/acsami.3c14072}, volume = {15}, year = {2023}, } @unpublished{14732, abstract = {Fragmented landscapes pose a significant threat to the persistence of species as they are highly susceptible to heightened risk of extinction due to the combined effects of genetic and demographic factors such as genetic drift and demographic stochasticity. This paper explores the intricate interplay between genetic load and extinction risk within metapopulations with a focus on understanding the impact of eco-evolutionary feedback mechanisms. We distinguish between two models of selection: soft selection, characterised by subpopulations maintaining carrying capacity despite load, and hard selection, where load can significantly affect population size. Within the soft selection framework, we investigate the impact of gene flow on genetic load at a single locus, while also considering the effect of selection strength and dominance coefficient. We subsequently build on this to examine how gene flow influences both population size and load under hard selection as well as identify critical thresholds for metapopulation persistence. Our analysis employs the diffusion, semi-deterministic and effective migration approximations. Our findings reveal that under soft selection, even modest levels of migration can significantly alleviate the burden of load. In sharp contrast, with hard selection, a much higher degree of gene flow is required to mitigate load and prevent the collapse of the metapopulation. Overall, this study sheds light into the crucial role migration plays in shaping the dynamics of genetic load and extinction risk in fragmented landscapes, offering valuable insights for conservation strategies and the preservation of diversity in a changing world.}, author = {Olusanya, Oluwafunmilola O and Khudiakova, Kseniia and Sachdeva, Himani}, booktitle = {bioRxiv}, title = {{Genetic load, eco-evolutionary feedback and extinction in a metapopulation}}, doi = {10.1101/2023.12.02.569702}, year = {2023}, } @inproceedings{14735, abstract = {Scaling blockchain protocols to perform on par with the expected needs of Web3.0 has been proven to be a challenging task with almost a decade of research. In the forefront of the current solution is the idea of separating the execution of the updates encoded in a block from the ordering of blocks. In order to achieve this, a new class of protocols called rollups has emerged. Rollups have as input a total ordering of valid and invalid transactions and as output a new valid state-transition. If we study rollups from a distributed computing perspective, we uncover that rollups take as input the output of a Byzantine Atomic Broadcast (BAB) protocol and convert it to a State Machine Replication (SMR) protocol. BAB and SMR, however, are considered equivalent as far as distributed computing is concerned and a solution to one can easily be retrofitted to solve the other simply by adding/removing an execution step before the validation of the input. This “easy” step of retrofitting an atomic broadcast solution to implement an SMR has, however, been overlooked in practice. In this paper, we formalize the problem and show that after BAB is solved, traditional impossibility results for consensus no longer apply towards an SMR. Leveraging this we propose a distributed execution protocol that allows reduced execution and storage cost per executor (O(log2n/n)) without relaxing the network assumptions of the underlying BAB protocol and providing censorship-resistance. Finally, we propose efficient non-interactive light client constructions that leverage our efficient execution protocols and do not require any synchrony assumptions or expensive ZK-proofs.}, author = {Stefo, Christos and Xiang, Zhuolun and Kokoris Kogias, Eleftherios}, booktitle = {27th International Conference on Financial Cryptography and Data Security}, isbn = {9783031477539}, issn = {0302-9743}, location = {Bol, Brac, Croatia}, pages = {3--20}, publisher = {Springer Nature}, title = {{Executing and proving over dirty ledgers}}, doi = {10.1007/978-3-031-47754-6_1}, volume = {13950}, year = {2023}, } @inproceedings{14736, abstract = {Payment channel networks (PCNs) are a promising technology to improve the scalability of cryptocurrencies. PCNs, however, face the challenge that the frequent usage of certain routes may deplete channels in one direction, and hence prevent further transactions. In order to reap the full potential of PCNs, recharging and rebalancing mechanisms are required to provision channels, as well as an admission control logic to decide which transactions to reject in case capacity is insufficient. This paper presents a formal model of this optimisation problem. In particular, we consider an online algorithms perspective, where transactions arrive over time in an unpredictable manner. Our main contributions are competitive online algorithms which come with provable guarantees over time. We empirically evaluate our algorithms on randomly generated transactions to compare the average performance of our algorithms to our theoretical bounds. We also show how this model and approach differs from related problems in classic communication networks.}, author = {Bastankhah, Mahsa and Chatterjee, Krishnendu and Maddah-Ali, Mohammad Ali and Schmid, Stefan and Svoboda, Jakub and Yeo, Michelle X}, booktitle = {27th International Conference on Financial Cryptography and Data Security}, isbn = {9783031477539}, issn = {1611-3349}, location = {Bol, Brac, Croatia}, pages = {309--325}, publisher = {Springer Nature}, title = {{R2: Boosting liquidity in payment channel networks with online admission control}}, doi = {10.1007/978-3-031-47754-6_18}, volume = {13950}, year = {2023}, } @article{14737, abstract = {John’s fundamental theorem characterizing the largest volume ellipsoid contained in a convex body $K$ in $\mathbb{R}^{d}$ has seen several generalizations and extensions. One direction, initiated by V. Milman is to replace ellipsoids by positions (affine images) of another body $L$. Another, more recent direction is to consider logarithmically concave functions on $\mathbb{R}^{d}$ instead of convex bodies: we designate some special, radially symmetric log-concave function $g$ as the analogue of the Euclidean ball, and want to find its largest integral position under the constraint that it is pointwise below some given log-concave function $f$. We follow both directions simultaneously: we consider the functional question, and allow essentially any meaningful function to play the role of $g$ above. Our general theorems jointly extend known results in both directions. The dual problem in the setting of convex bodies asks for the smallest volume ellipsoid, called Löwner’s ellipsoid, containing $K$. We consider the analogous problem for functions: we characterize the solutions of the optimization problem of finding a smallest integral position of some log-concave function $g$ under the constraint that it is pointwise above $f$. It turns out that in the functional setting, the relationship between the John and the Löwner problems is more intricate than it is in the setting of convex bodies.}, author = {Ivanov, Grigory and Naszódi, Márton}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, keywords = {General Mathematics}, number = {23}, pages = {20613--20669}, publisher = {Oxford University Press}, title = {{Functional John and Löwner conditions for pairs of log-concave functions}}, doi = {10.1093/imrn/rnad210}, volume = {2023}, year = {2023}, } @article{14739, abstract = {Attempts to incorporate topological information in supervised learning tasks have resulted in the creation of several techniques for vectorizing persistent homology barcodes. In this paper, we study thirteen such methods. Besides describing an organizational framework for these methods, we comprehensively benchmark them against three well-known classification tasks. Surprisingly, we discover that the best-performing method is a simple vectorization, which consists only of a few elementary summary statistics. Finally, we provide a convenient web application which has been designed to facilitate exploration and experimentation with various vectorization methods.}, author = {Ali, Dashti and Asaad, Aras and Jimenez, Maria-Jose and Nanda, Vidit and Paluzo-Hidalgo, Eduardo and Soriano Trigueros, Manuel}, issn = {1939-3539}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, keywords = {Applied Mathematics, Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Software}, number = {12}, pages = {14069--14080}, publisher = {IEEE}, title = {{A survey of vectorization methods in topological data analysis}}, doi = {10.1109/tpami.2023.3308391}, volume = {45}, year = {2023}, } @article{14742, abstract = {Chromosomal rearrangements (CRs) have been known since almost the beginning of genetics. While an important role for CRs in speciation has been suggested, evidence primarily stems from theoretical and empirical studies focusing on the microevolutionary level (i.e., on taxon pairs where speciation is often incomplete). Although the role of CRs in eukaryotic speciation at a macroevolutionary level has been supported by associations between species diversity and rates of evolution of CRs across phylogenies, these findings are limited to a restricted range of CRs and taxa. Now that more broadly applicable and precise CR detection approaches have become available, we address the challenges in filling some of the conceptual and empirical gaps between micro- and macroevolutionary studies on the role of CRs in speciation. We synthesize what is known about the macroevolutionary impact of CRs and suggest new research avenues to overcome the pitfalls of previous studies to gain a more comprehensive understanding of the evolutionary significance of CRs in speciation across the tree of life.}, author = {Lucek, Kay and Giménez, Mabel D. and Joron, Mathieu and Rafajlović, Marina and Searle, Jeremy B. and Walden, Nora and Westram, Anja M and Faria, Rui}, issn = {1943-0264}, journal = {Cold Spring Harbor Perspectives in Biology}, keywords = {General Biochemistry, Genetics and Molecular Biology}, number = {11}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{The impact of chromosomal rearrangements in speciation: From micro- to macroevolution}}, doi = {10.1101/cshperspect.a041447}, volume = {15}, year = {2023}, } @inproceedings{14743, abstract = {Leader-based consensus algorithms are fast and efficient under normal conditions, but lack robustness to adverse conditions due to their reliance on timeouts for liveness. We present QuePaxa, the first protocol offering state-of-the-art normal-case efficiency without depending on timeouts. QuePaxa uses a novel randomized asynchronous consensus core to tolerate adverse conditions such as denial-of-service (DoS) attacks, while a one-round-trip fast path preserves the normal-case efficiency of Multi-Paxos or Raft. By allowing simultaneous proposers without destructive interference, and using short hedging delays instead of conservative timeouts to limit redundant effort, QuePaxa permits rapid recovery after leader failure without risking costly view changes due to false timeouts. By treating leader choice and hedging delay as a multi-armed-bandit optimization, QuePaxa achieves responsiveness to prevalent conditions, and can choose the best leader even if the current one has not failed. Experiments with a prototype confirm that QuePaxa achieves normal-case LAN and WAN performance of 584k and 250k cmd/sec in throughput, respectively, comparable to Multi-Paxos. Under conditions such as DoS attacks, misconfigurations, or slow leaders that severely impact existing protocols, we find that QuePaxa remains live with median latency under 380ms in WAN experiments.}, author = {Tennage, Pasindu and Basescu, Cristina and Kokoris Kogias, Eleftherios and Syta, Ewa and Jovanovic, Philipp and Estrada-Galinanes, Vero and Ford, Bryan}, booktitle = {Proceedings of the 29th Symposium on Operating Systems Principles}, isbn = {9798400702297}, location = {Koblenz, Germany}, pages = {281--297}, publisher = {Association for Computing Machinery}, title = {{QuePaxa: Escaping the tyranny of timeouts in consensus}}, doi = {10.1145/3600006.3613150}, year = {2023}, } @inproceedings{14744, abstract = {Sharding distributed ledgers is a promising on-chain solution for scaling blockchains but lacks formal grounds, nurturing skepticism on whether such complex systems can scale blockchains securely. We fill this gap by introducing the first formal framework as well as a roadmap to robust sharding. In particular, we first define the properties sharded distributed ledgers should fulfill. We build upon and extend the Bitcoin backbone protocol by defining consistency and scalability. Consistency encompasses the need for atomic execution of cross-shard transactions to preserve safety, whereas scalability encapsulates the speedup a sharded system can gain in comparison to a non-sharded system. Using our model, we explore the limitations of sharding. We show that a sharded ledger with n participants cannot scale under a fully adaptive adversary, but it can scale up to m shards where n=c'm log m, under an epoch-adaptive adversary; the constant c' encompasses the trade-off between security and scalability. This is possible only if the sharded ledgers create succinct proofs of the valid state updates at every epoch. We leverage our results to identify the sufficient components for robust sharding, which we incorporate in a protocol abstraction termed Divide & Scale. To demonstrate the power of our framework, we analyze the most prominent sharded blockchains (Elastico, Monoxide, OmniLedger, RapidChain) and pinpoint where they fail to meet the desired properties.}, author = {Avarikioti, Zeta and Desjardins, Antoine and Kokoris Kogias, Eleftherios and Wattenhofer, Roger}, booktitle = {30th International Colloquium on Structural Information and Communication Complexity}, isbn = {9783031327322}, issn = {1611-3349}, location = {Alcalá de Henares, Spain}, pages = {199--245}, publisher = {Springer Nature}, title = {{Divide & Scale: Formalization and roadmap to robust sharding}}, doi = {10.1007/978-3-031-32733-9_10}, volume = {13892}, year = {2023}, }