@article{1979, abstract = {NADH-ubiquinone oxidoreductase (complex I) is the first and largest enzyme in the respiratory chain of mitochondria and many bacteria. It couples the transfer of two electrons between NADH and ubiquinone to the translocation of four protons across the membrane. Complex I is an L-shaped assembly formed by the hydrophilic (peripheral) arm, containing all the redox centres performing electron transfer and the membrane arm, containing proton-translocating machinery. Mitochondrial complex I consists of 44 subunits of about 1 MDa in total, whilst the prokaryotic enzyme is simpler and generally consists of 14 conserved “core” subunits. Recently we have determined the first atomic structure of the entire complex I, using the enzyme from Thermus thermophilus (536 kDa, 16 subunits, 9 Fe-S clusters, 64 TM helices). Structure suggests a unique coupling mechanism, with redox energy of electron transfer driving proton translocation via long-range (up to ~200 Å) conformational changes. It resembles a steam engine, with coupling elements (akin to coupling rods) linking parts of this molecular machine.}, author = {Sazanov, Leonid A}, issn = {1573-6881}, journal = {Journal of Bioenergetics and Biomembranes}, number = {4}, pages = {247 -- 253}, publisher = {Springer Nature}, title = {{The mechanism of coupling between electron transfer and proton translocation in respiratory complex I}}, doi = {10.1007/s10863-014-9554-z}, volume = {46}, year = {2014}, } @article{1761, abstract = {Metal silicides formed by means of thermal annealing processes are employed as contact materials in microelectronics. Control of the structure of silicide/silicon interfaces becomes a critical issue when the characteristic size of the device is reduced below a few tens of nanometers. Here, we report on silicide clustering occurring within the channel of PtSi/Si/PtSi Schottky-barrier transistors. This phenomenon is investigated through atomistic simulations and low-temperature resonant-tunneling spectroscopy. Our results provide evidence for the segregation of a PtSi cluster with a diameter of a few nanometers from the silicide contact. The cluster acts as a metallic quantum dot giving rise to distinct signatures of quantum transport through its discrete energy states.}, author = {Mongillo, Massimo and Spathis, Panayotis and Katsaros, Georgios and De Franceschi, Silvano and Gentile, Pascal and Rurali, Riccardo and Cartoixà, Xavier}, issn = {2160-3308}, journal = {Physical Review X}, number = {4}, publisher = {American Physical Society}, title = {{PtSi clustering in silicon probed by transport spectroscopy}}, doi = {10.1103/PhysRevX.3.041025}, volume = {3}, year = {2014}, } @article{1058, abstract = {Diffraction-unlimited far-field super-resolution fluorescence (nanoscopy) methods typically rely on transiently transferring fluorophores between two states, whereby this transfer is usually laid out as a switch. However, depending on whether this is induced in a spatially controlled manner using a pattern of light (coordinate-targeted) or stochastically on a single-molecule basis, specific requirements on the fluorophores are imposed. Therefore, the fluorophores are usually utilized just for one class of methods only. In this study we demonstrate that the reversibly switchable fluorescent protein Dreiklang enables live-cell recordings in both spatially controlled and stochastic modes. We show that the Dreiklang chromophore entails three different light-induced switching mechanisms, namely a reversible photochemical one, off-switching by stimulated emission, and a reversible transfer to a long-lived dark state from the S1 state, all of which can be utilized to overcome the diffraction barrier. We also find that for the single-molecule- based stochastic GSDIM approach (ground-state depletion followed by individual molecule return), Dreiklang provides a larger number of on-off localization events as compared to its progenitor Citrine. Altogether, Dreiklang is a versatile probe for essentially all popular forms of live-cell fluorescence nanoscopy.}, author = {Jensen, Nickels and Danzl, Johann G and Willig, Katrin and Lavoie Cardinal, Flavie and Brakemann, Tanja and Hell, Stefan and Jakobs, Stefan}, issn = {1439-7641}, journal = {ChemPhysChem}, number = {4}, pages = {756 -- 762}, publisher = {Wiley-Blackwell}, title = {{Coordinate-targeted and coordinate-stochastic super-resolution microscopy with the reversibly switchable fluorescent protein dreiklang}}, doi = {10.1002/cphc.201301034}, volume = {15}, year = {2014}, } @article{1312, abstract = {We derive upper bounds on the waiting time of solutions to the thin-film equation in the regime of weak slippage n ∈ [2, 32\11). In particular, we give sufficient conditions on the initial data for instantaneous forward motion of the free boundary. For n ∈ (2, 32\11), our estimates are sharp, for n = 2, they are sharp up to a logarithmic correction term. Note that the case n = 2 corresponds-with a grain of salt-to the assumption of the Navier slip condition at the fluid-solid interface. We also obtain results in the regime of strong slippage n ∈ (1,2); however, in this regime we expect them not to be optimal. Our method is based on weighted backward entropy estimates, Hardy's inequality and singular weight functions; we deduce a differential inequality which would enforce blowup of the weighted entropy if the contact line were to remain stationary for too long.}, author = {Fischer, Julian L}, issn = {1432-0673}, journal = {Archive for Rational Mechanics and Analysis}, number = {3}, pages = {771 -- 818}, publisher = {Springer Nature}, title = {{Upper bounds on waiting times for the Thin-film equation: The case of weak slippage}}, doi = {10.1007/s00205-013-0690-0}, volume = {211}, year = {2014}, } @article{1309, abstract = {We show that weak solutions of the Derrida-Lebowitz-Speer-Spohn (DLSS) equation display infinite speed of support propagation. We apply our method to the case of the quantum drift-diffusion equation which augments the DLSS equation with a drift term and possibly a second-order diffusion term. The proof is accomplished using weighted entropy estimates, Hardy's inequality and a family of singular weight functions to derive a differential inequality; the differential inequality shows exponential growth of the weighted entropy, with the growth constant blowing up very fast as the singularity of the weight becomes sharper. To the best of our knowledge, this is the first example of a nonnegativity-preserving higher-order parabolic equation displaying infinite speed of support propagation.}, author = {Fischer, Julian L}, issn = {1420-9004}, journal = {Nonlinear Differential Equations and Applications}, number = {1}, pages = {27 -- 50}, publisher = {Birkhäuser}, title = {{Infinite speed of support propagation for the Derrida-Lebowitz-Speer-Spohn equation and quantum drift-diffusion models}}, doi = {10.1007/s00030-013-0235-0}, volume = {21}, year = {2014}, } @article{980, abstract = {Many-body localized (MBL) systems are characterized by the absence of transport and thermalization and, therefore, cannot be described by conventional statistical mechanics. In this paper, using analytic arguments and numerical simulations, we study the behavior of local observables in an isolated MBL system following a quantum quench. For the case of a global quench, we find that the local observables reach stationary, highly nonthermal values at long times as a result of slow dephasing characteristic of the MBL phase. These stationary values retain the local memory of the initial state due to the existence of local integrals of motion in the MBL phase. The temporal fluctuations around stationary values exhibit universal power-law decay in time, with an exponent set by the localization length and the diagonal entropy of the initial state. Such a power-law decay holds for any local observable and is related to the logarithmic in time growth of entanglement in the MBL phase. This behavior distinguishes the MBL phase from both the Anderson insulator (where no stationary state is reached) and from the ergodic phase (where relaxation is expected to be exponential). For the case of a local quench, we also find a power-law approach of local observables to their stationary values when the system is prepared in a mixed state. Quench protocols considered in this paper can be naturally implemented in systems of ultracold atoms in disordered optical lattices, and the behavior of local observables provides a direct experimental signature of many-body localization.}, author = {Serbyn, Maksym and Papić, Zlatko and Abanin, Dmitry}, issn = {1098-0121}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {17}, publisher = {American Physical Society}, title = {{Quantum quenches in the many-body localized phase}}, doi = {10.1103/PhysRevB.90.174302}, volume = {90}, year = {2014}, } @article{978, abstract = {The newly discovered topological crystalline insulators feature a complex band structure involving multiple Dirac cones, and are potentially highly tunable by external electric field, temperature or strain. Theoretically, it has been predicted that the various Dirac cones, which are offset in energy and momentum, might harbour vastly different orbital character. However, their orbital texture, which is of immense importance in determining a variety of a materialâ €™ s properties remains elusive. Here, we unveil the orbital texture of Pb 1â ̂'x Sn x Se, a prototypical topological crystalline insulator. By using Fourier-transform scanning tunnelling spectroscopy we measure the interference patterns produced by the scattering of surface-state electrons. We discover that the intensity and energy dependences of the Fourier transforms show distinct characteristics, which can be directly attributed to orbital effects. Our experiments reveal a complex band topology involving two Lifshitz transitions and establish the orbital nature of the Dirac bands, which could provide an alternative pathway towards future quantum applications.}, author = {Zeljkovic, Ilija and Okada, Yoshinori and Huang, Chengyi and Sankar, Raman and Walkup, Daniel and Zhou, Wenwen and Serbyn, Maksym and Chou, Fangcheng and Tsai, Wei and Lin, Hsin and Bansil, Arun and Fu, Liang and Hasan, Md and Madhavan, Vidya}, issn = {1745-2481}, journal = {Nature Physics}, number = {8}, pages = {572 -- 577}, publisher = {Nature Publishing Group}, title = {{Mapping the unconventional orbital texture in topological crystalline insulators}}, doi = {10.1038/nphys3012}, volume = {10}, year = {2014}, } @article{865, abstract = {Research on existing drugs often discovers novel mechanisms of their action and leads to the expansion of their therapeutic scope and subsequent remarketing. The Wnt signaling pathway is of the immediate therapeutic relevance, as it plays critical roles in cancer development and progression. However, drugs which disrupt this pathway are unavailable despite the high demand. Here we report an attempt to identify antagonists of the Wnt-FZD interaction among the library of the FDA-approved drugs. We performed an in silico screening which brought up several potential antagonists of the ligand-receptor interaction. 14 of these substances were tested using the TopFlash luciferase reporter assay and four of them identified as active and specific inhibitors of the Wnt3a-induced signaling. However, further analysis through GTP-binding and β-catenin stabilization assays showed that the compounds do not target the Wnt-FZD pair, but inhibit the signaling at downstream levels. We further describe the previously unknown inhibitory activity of an anti-leprosy drug clofazimine in the Wnt pathway and provide data demonstrating its efficiency in suppressing growth of Wnt-dependent triple-negative breast cancer cells. These data provide a basis for further investigations of the efficiency of clofazimine in treatment of Wnt-dependent cancers.}, author = {Koval, Alexey and Vlasov, Peter and Shichkova, Polina and Khunderyakova, S and Markov, Yury and Panchenko, J and Volodina, A and Kondrashov, Fyodor and Katanaev, Vladimir}, issn = {1873-2968}, journal = {Biochemical Pharmacology}, number = {4}, pages = {571 -- 578}, publisher = {Elsevier}, title = {{Anti leprosy drug clofazimine inhibits growth of triple-negative breast cancer cells via inhibition of canonical Wnt signaling}}, doi = {10.1016/j.bcp.2013.12.007}, volume = {87}, year = {2014}, } @article{977, abstract = {We propose a method for detecting many-body localization (MBL) in disordered spin systems. The method involves pulsed coherent spin manipulations that probe the dephasing of a given spin due to its entanglement with a set of distant spins. It allows one to distinguish the MBL phase from a noninteracting localized phase and a delocalized phase. In particular, we show that for a properly chosen pulse sequence the MBL phase exhibits a characteristic power-law decay reflecting its slow growth of entanglement. We find that this power-law decay is robust with respect to thermal and disorder averaging, provide numerical simulations supporting our results, and discuss possible experimental realizations in solid-state and cold-atom systems.}, author = {Serbyn, Maksym and Knap, Michael and Gopalakrishnan, Sarang and Papić, Zlatko and Yao, Norman and Laumann, Chris and Abanin, Dmitry and Lukin, Mikhail and Demler, Eugene}, issn = {1079-7114}, journal = {Physical Review Letters}, number = {14}, publisher = {American Physical Society}, title = {{Interferometric probes of many-body localization}}, doi = {10.1103/PhysRevLett.113.147204}, volume = {113}, year = {2014}, } @article{979, abstract = {In the recently discovered topological crystalline insulators SnTe and Pb1-xSnx(Te, Se), crystal symmetry and electronic topology intertwine to create topological surface states with many interesting features including Lifshitz transition, Van-Hove singularity, and fermion mass generation. These surface states are protected by mirror symmetry with respect to the (110) plane. In this work we present a comprehensive study of the effects of different mirror-symmetry-breaking perturbations on the (001) surface band structure. Pristine (001) surface states have four branches of Dirac fermions at low energy. We show that ferroelectric-type structural distortion generates a mass and gaps out some or all of these Dirac points, while strain shifts Dirac points in the Brillouin zone. An in-plane magnetic field leaves the surface state gapless, but introduces asymmetry between Dirac points. Finally, an out-of-plane magnetic field leads to discrete Landau levels. We show that the Landau level spectrum has an unusual pattern of degeneracy and interesting features due to the unique underlying band structure. This suggests that Landau level spectroscopy can detect and distinguish between different mechanisms of symmetry breaking in topological crystalline insulators.}, author = {Serbyn, Maksym and Fu, Liang}, issn = {1098-0121}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {3}, publisher = {American Physical Society}, title = {{Symmetry breaking and Landau quantization in topological crystalline insulators}}, doi = {10.1103/PhysRevB.90.035402}, volume = {90}, year = {2014}, } @article{926, abstract = {The regulation of cell growth in animal tissues is a question of critical importance: most tissues contain different types of cells in interconversion and the fraction of each type has to be controlled in a precise way, by mechanisms that remain unclear. Here, we provide a theoretical framework for the homeostasis of stem-cell-containing epithelial tissues using mechanical equations, which describe the size of the tissue and kinetic equations, which describe the interconversions of the cell populations. We show that several features, such as the evolution of stem cell fractions during intestinal development, the shape of a developing intestinal wall, as well as the increase in the proliferative compartment in cancer initiation, can be studied and understood from generic modelling which does not rely on a particular regulatory mechanism. Finally, inspired by recent experiments, we propose a model where cell division rates are regulated by the mechanical stresses in the epithelial sheet. We show that pressure-controlled growth can, in addition to the previous features, also explain with few parameters the formation of stem cell compartments as well as the morphologies observed when a colonic crypt becomes cancerous. We also discuss optimal strategies of wound healing, in connection with experiments on the cornea.}, author = {Hannezo, Edouard B and Prost, Jacques and Joanny, Jean}, issn = {1742-5662}, journal = {Journal of the Royal Society Interface}, number = {93}, publisher = {Royal Society of London}, title = {{Growth homeostatic regulation and stem cell dynamics in tissues}}, doi = {10.1098/rsif.2013.0895}, volume = {11}, year = {2014}, } @article{925, abstract = {The morphological stability of biological tubes is crucial for the efficient circulation of fluids and gases. Failure of this stability causes irregularly shaped tubes found in multiple pathological conditions. Here, we report that Drosophila mutants of the ESCRT III component Shrub/Vps32 exhibit a strikingly elongated sinusoidal tube phenotype. This is caused by excessive apical membrane synthesis accompanied by the ectopic accumulation and overactivation of Crumbs in swollen endosomes. Furthermore, we demonstrate that the apical extracellular matrix (aECM) of the tracheal tube is a viscoelastic material coupled with the apical membrane. We present a simple mechanical model in which aECM elasticity, apical membrane growth, and their interaction are three vital parameters determining the stability of biological tubes. Our findings demonstrate a mechanical role for the extracellular matrix and suggest that the interaction of the apical membrane and an elastic aECM determines the final morphology of biological tubes independent of cell shape.}, author = {Dong, Bo and Hannezo, Edouard B and Hayashi, Shigeo}, issn = {2211-1247}, journal = {Cell Reports}, number = {4}, pages = {941 -- 950}, publisher = {Cell Press}, title = {{Balance between apical membrane growth and luminal matrix resistance determines epithelial tubule shape}}, doi = {10.1016/j.celrep.2014.03.066}, volume = {7}, year = {2014}, } @article{927, abstract = {Morphogenesis during embryo development requires the coordination of mechanical forces to generate the macroscopic shapes of organs. We propose a minimal theoretical model, based on cell adhesion and actomyosin contractility, which describes the various shapes of epithelial cells and the bending and buckling of epithelial sheets, as well as the relative stability of cellular tubes and spheres. We show that, to understand these processes, a full 3D description of the cells is needed, but that simple scaling laws can still be derived. The morphologies observed in vivo can be understood as stable points of mechanical equations and the transitions between them are either continuous or discontinuous. We then focus on epithelial sheet bending, a ubiquitous morphogenetic process. We calculate the curvature of an epithelium as a function of actin belt tension as well as of cell-cell and and cell-substrate tension. The model allows for a comparison of the relative stabilities of spherical or cylindrical cellular structures (acini or tubes). Finally, we propose a unique type of buckling instability of epithelia, driven by a flattening of individual cell shapes, and discuss experimental tests to verify our predictions.}, author = {Hannezo, Edouard B and Prost, Jacques and Joanny, Jean}, issn = {1091-6490}, journal = {PNAS}, number = {1}, pages = {27 -- 32}, publisher = {National Academy of Sciences}, title = {{Theory of epithelial sheet morphology in three dimensions}}, doi = {10.1073/pnas.1312076111}, volume = {111}, year = {2014}, } @article{892, abstract = {The study of molecular evolution is important because it reveals how protein functions emerge and evolve. Recently, several types of studies indicated that substitutions in molecular evolution occur in a compensatory manner, whereby the occurrence of a substitution depends on the amino acid residues at other sites. However, a molecular or structural basis behind the compensation often remains obscure. Here, we review studies on the interface of structural biology and molecular evolution that revealed novel aspects of compensatory evolution. In many cases structural studies benefit from evolutionary data while structural data often add a functional dimension to the study of molecular evolution.}, author = {Ivankov, Dmitry and Finkelstein, Alexei and Kondrashov, Fyodor}, issn = {1879-033X}, journal = {Current Opinion in Structural Biology}, pages = {104 -- 112}, publisher = {Elsevier}, title = {{A structural perspective of compensatory evolution}}, doi = {10.1016/j.sbi.2014.05.004}, volume = {26}, year = {2014}, } @article{863, abstract = {The origins of neural systems remain unresolved. In contrast to other basal metazoans, ctenophores (comb jellies) have both complex nervous and mesoderm-derived muscular systems. These holoplanktonic predators also have sophisticated ciliated locomotion, behaviour and distinct development. Here we present the draft genome of Pleurobrachia bachei, Pacific sea gooseberry, together with ten other ctenophore transcriptomes, and show that they are remarkably distinct from other animal genomes in their content of neurogenic, immune and developmental genes. Our integrative analyses place Ctenophora as the earliest lineage within Metazoa. This hypothesis is supported by comparative analysis of multiple gene families, including the apparent absence of HOX genes, canonical microRNA machinery, and reduced immune complement in ctenophores. Although two distinct nervous systems are well recognized in ctenophores, many bilaterian neuron-specific genes and genes of 'classical' neurotransmitter pathways either are absent or, if present, are not expressed in neurons. Our metabolomic and physiological data are consistent with the hypothesis that ctenophore neural systems, and possibly muscle specification, evolved independently from those in other animals.}, author = {Moroz, Leonid and Kocot, Kevin and Citarella, Mathew and Dosung, Sohn and Norekian, Tigran and Povolotskaya, Inna and Grigorenko, Anastasia and Dailey, Christopher and Berezikov, Eugene and Buckley, Katherine and Ptitsyn, Andrey and Reshetov, Denis and Mukherjee, Krishanu and Moroz, Tatiana and Bobkova, Yelena and Yu, Fahong and Kapitonov, Vladimir and Jurka, Jerzy and Bobkov, Yuriy and Swore, Joshua and Girardo, David and Fodor, Alexander and Gusev, Fedor and Sanford, Rachel and Bruders, Rebecca and Kittler, Ellen and Mills, Claudia and Rast, Jonathan and Derelle, Romain and Solovyev, Victor and Kondrashov, Fyodor and Swalla, Billie and Sweedler, Jonathan and Rogaev, Evgeny and Halanych, Kenneth and Kohn, Andrea}, issn = {1476-4687}, journal = {Nature}, number = {7503}, pages = {109 -- 114}, publisher = {Nature Publishing Group}, title = {{The ctenophore genome and the evolutionary origins of neural systems}}, doi = {10.1038/nature13400}, volume = {510}, year = {2014}, } @article{845, abstract = {Recombination between double-stranded DNA molecules is a key genetic process which occurs in a wide variety of organisms. Usually, crossing-over (CO) occurs during meiosis between genotypes with 98.0-99.9% sequence identity, because within-population nucleotide diversity only rarely exceeds 2%. However, some species are hypervariable and it is unclear how CO can occur between genotypes with less than 90% sequence identity. Here, we study CO in Schizophyllum commune, a hypervariable cosmopolitan basidiomycete mushroom, a frequently encountered decayer of woody substrates. We crossed two haploid individuals, from the United States and from Russia, and obtained genome sequences for their 17 offspring. The average genetic distance between the parents was 14%, making it possible to study CO at very high resolution. We found reduced levels of linkage disequilibrium between loci flanking the CO sites indicating that they are mostly confined to hotspots of recombination. Furthermore, CO events preferentially occurred in regions under stronger negative selection, in particular within exons that showed reduced levels of nucleotide diversity. Apparently, in hypervariable species CO must avoid regions of higher divergence between the recombining genomes due to limitations imposed by the mismatch repair system, with regions under strong negative selection providing the opportunity for recombination. These patterns are opposite to those observed in a number of less variable species indicating that population genomics of hypervariable species may reveal novel biological phenomena.}, author = {Seplyarskiy, Vladimir and Logacheva, Maria and Penin, Aleksey and Baranová, Maria and Leushkin, Evgeny and Demidenko, Natalia and Klepikova, Anna and Kondrashov, Fyodor and Kondrashov, Alexey and James, Timothy}, issn = {1537-1719}, journal = {Molecular Biology and Evolution}, number = {11}, pages = {3016 -- 3025}, publisher = {Oxford University Press}, title = {{Crossing-over in a hypervariable species preferentially occurs in regions of high local similarity}}, doi = {10.1093/molbev/msu242}, volume = {31}, year = {2014}, } @article{856, abstract = {The emergence of new genes throughout evolution requires rewiring and extension of regulatory networks. However, the molecular details of how the transcriptional regulation of new gene copies evolves remain largely unexplored. Here we show how duplication of a transcription factor gene allowed the emergence of two independent regulatory circuits. Interestingly, the ancestral transcription factor was promiscuous and could bind different motifs in its target promoters. After duplication, one paralogue evolved increased binding specificity so that it only binds one type of motif, whereas the other copy evolved a decreased activity so that it only activates promoters that contain multiple binding sites. Interestingly, only a few mutations in both the DNA-binding domains and in the promoter binding sites were required to gradually disentangle the two networks. These results reveal how duplication of a promiscuous transcription factor followed by concerted cis and trans mutations allows expansion of a regulatory network.}, author = {Pougach, Ksenia and Voet, Arnout and Kondrashov, Fyodor and Voordeckers, Karin and Christiaens, Joaquin and Baying, Bianka and Bénès, Vladimı́R and Sakai, Ryo and Aerts, Jan and Zhu, Bo and Van Dijck, Patrick and Verstrepen, Kevin}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Nature Publishing Group}, title = {{Duplication of a promiscuous transcription factor drives the emergence of a new regulatory network}}, doi = {10.1038/ncomms5868}, volume = {5}, year = {2014}, } @article{852, abstract = {Rapid divergence of gene copies after duplication is thought to determine the fate of the copies and evolution of novel protein functions. However, data on howlong the gene copies continue to experience an elevated rate of evolution remain scarce. Standard theory of gene duplications based on some level of genetic redundancy of gene copies predicts that the period of accelerated evolutionmust end relatively quickly. Using a maximum-likelihood approach we estimate preduplication, initial postduplication, and recent postduplication rates of evolution that occurred in themammalian lineage.Wefind that both gene copies experience a similar in magnitude acceleration in their rate of evolution. The copy located in the original genomic position typically returns to the preduplication rates of evolution in a short period of time. The burst of faster evolution of the copy that is located in a new genomic position typically lasts longer. Furthermore, the fast-evolving copies on average continue to evolve faster than the preduplication rates far longer than predicted by standard theory of gene duplications.We hypothesize that the prolonged elevated rates of evolution are determined by functional properties that were acquired during, or soon after, the gene duplication event. }, author = {Rosello, Oriol and Kondrashov, Fyodor}, issn = {1759-6653}, journal = {Genome Biology and Evolution}, number = {8}, pages = {1949 -- 1955}, publisher = {Oxford University Press}, title = {{Long-Term asymmetrical acceleration of protein evolution after gene duplication}}, doi = {10.1093/gbe/evu159}, volume = {6}, year = {2014}, } @inproceedings{773, abstract = {We describe a new randomized consensus protocol with expected message complexity O(n2log2n) when fewer than n/2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(n2) message lower bound. The protocol further ensures that no process sends more than O(n log3n) messages in expectation, which is again within logarithmic factors of optimal.We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected O(nt + t2log2t) total messages. Our protocol uses messages of size O(log n), and can therefore scale to large networks. We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model.}, author = {Alistarh, Dan-Adrian and Aspnes, James and King, Valerie and Saia, Jared}, booktitle = {28th International Symposium Distributed Computing 2014}, editor = {Kuhn, Fabian}, isbn = {9783662451731}, location = {Austin, TX, United States}, pages = {61 -- 75}, publisher = {Springer}, title = {{Communication-efficient randomized consensus}}, doi = {10.1007/978-3-662-45174-8_5}, volume = {8784}, year = {2014}, } @inproceedings{775, abstract = {The long-lived renaming problem appears in shared-memory systems where a set of threads need to register and deregister frequently from the computation, while concurrent operations scan the set of currently registered threads. Instances of this problem show up in concurrent implementations of transactional memory, flat combining, thread barriers, and memory reclamation schemes for lock-free data structures. In this paper, we analyze a randomized solution for long-lived renaming. The algorithmic technique we consider, called the Level Array, has previously been used for hashing and one-shot (single-use) renaming. Our main contribution is to prove that, in long-lived executions, where processes may register and deregister polynomially many times, the technique guarantees constant steps on average and O (log log n) steps with high probability for registering, unit cost for deregistering, and O (n) steps for collect queries, where n is an upper bound on the number of processes that may be active at any point in time. We also show that the algorithm has the surprising property that it is self-healing: under reasonable assumptions on the schedule, operations running while the data structure is in a degraded state implicitly help the data structure re-balance itself. This subtle mechanism obviates the need for expensive periodic rebuilding procedures. Our benchmarks validate this approach, showing that, for typical use parameters, the average number of steps a process takes to register is less than two and the worst-case number of steps is bounded by six, even in executions with billions of operations. We contrast this with other randomized implementations, whose worst-case behavior we show to be unreliable, and with deterministic implementations, whose cost is linear in n.}, author = {Alistarh, Dan-Adrian and Kopinsky, Justin and Matveev, Alexander and Shavit, Nir}, booktitle = {Proceedings of the 2014 IEEE 34th International Conference on Distributed Computing Systems}, issn = {1063-6927}, location = {Madrid, Spain}, pages = {348 -- 357}, publisher = {IEEE}, title = {{The levelarray: A fast, practical long-lived renaming algorithm}}, doi = {10.1109/ICDCS.2014.43}, year = {2014}, }