@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}, } @inproceedings{772, abstract = {Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.}, author = {Alistarh, Dan-Adrian and Censor Hillel, Keren and Shavit, Nir}, booktitle = {Proceedings of the forty-sixth annual ACM symposium on Theory of computing}, isbn = {9781450327107}, location = {New York, NY, United States}, pages = {714 -- 723}, publisher = {ACM}, title = {{Are lock-free concurrent algorithms practically wait-free?}}, doi = {10.1145/2591796.2591836}, year = {2014}, } @article{809, abstract = {The assembly of HIV-1 is mediated by oligomerization of the major structural polyprotein, Gag, into a hexameric protein lattice at the plasma membrane of the infected cell. This leads to budding and release of progeny immature virus particles. Subsequent proteolytic cleavage of Gag triggers rearrangement of the particles to form mature infectious virions. Obtaining a structural model of the assembled lattice of Gag within immature virus particles is necessary to understand the interactions that mediate assembly of HIV-1 particles in the infected cell, and to describe the substrate that is subsequently cleaved by the viral protease. An 8-Å resolution structure of an immature virus-like tubular array assembled from a Gag-derived protein of the related retrovirus Mason-Pfizer monkey virus (M-PMV) has previously been reported, and a model for the arrangement of the HIV-1 capsid (CA) domains has been generated based on homology to this structure. Here we have assembled tubular arrays of a HIV-1 Gag-derived protein with an immature-like arrangement of the C-terminal CA domains and have solved their structure by using hybrid cryo-EM and tomography analysis. The structure reveals the arrangement of the C-terminal domain of CA within an immature-like HIV-1 Gag lattice, and provides, to our knowledge, the first high-resolution view of the region immediately downstream of CA, which is essential for assembly, and is significantly different from the respective region in M-PMV. Our results reveal a hollow column of density for this region in HIV-1 that is compatible with the presence of a six-helix bundle at this position.}, author = {Bharata, Tanmay and Menendez, Luis and Hagena, Wim and Luxd, Vanda and Igonete, Sebastien and Schorba, Martin and Schur, Florian and Kraüsslich, Hans and Briggsa, John}, issn = {1091-6490}, journal = {PNAS}, number = {22}, pages = {8233 -- 8238}, publisher = {National Academy of Sciences}, title = {{Cryo electron microscopy of tubular arrays of HIV-1 Gag resolves structures essential for immature virus assembly}}, doi = {10.1073/pnas.1401455111}, volume = {111}, year = {2014}, } @inproceedings{771, abstract = {We consider the following natural problem: n failure-prone servers, communicating synchronously through message passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of ©(logn) communication rounds is known. Second, model the scenario as an instance of randomized load-balancing, for which elegant sub-logarithmic solutions exist. However, careful examination reveals that known load-balancing schemes do not apply to our scenario, because they either do not tolerate faults or do not ensure one-to-one allocation. It is thus natural to ask if sublogarithmic solutions exist for this apparently simple but intriguing problem. In this paper, we combine the two approaches to provide a new randomized solution for tight renaming, which terminates in O (log log n) communication rounds with high probability, against a strong adaptive adversary. Our solution, called Balls-into-Leaves, combines the deterministic approach with a new randomized scheme to obtain perfectly balanced allocations. The algorithm arranges the items as leaves of a tree, and participants repeatedly perform random choices among the leaves. The algorithm exchanges information in each round to split the participants into progressively smaller groups whose random choices do not conflict. We then extend the algorithm to terminate early in O(log log) rounds w.h.p., where is the actual number of failures. These results imply an exponential separation between deterministic and randomized algorithms for the tight renaming problem in message-passing systems.}, author = {Alistarh, Dan-Adrian and Denysyuk, Oksana and Rodrígues, Luís and Shavit, Nir}, booktitle = {Proceedings of the 2014 ACM symposium on Principles of distributed computing}, isbn = {9781450329446}, location = {Paris, France}, pages = {232 -- 241}, publisher = {ACM}, title = {{Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems}}, doi = {10.1145/2611462.2611499}, year = {2014}, } @inproceedings{774, abstract = {Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers would prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is in general a complex undertaking, and the resulting algorithms are not always efficient, so most non-blocking commercial code is only lock-free, and the design of efficient wait-free algorithms has been left to the academic community. In [2], we suggest a solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a broad subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes.}, author = {Alistarh, Dan-Adrian and Censor Hille, Keren and Shavit, Nir}, booktitle = {Proceedings of the 2014 ACM symposium on Principles of distributed computing}, isbn = {9781450329446}, location = {Paris, France}, pages = {50 -- 52}, publisher = {ACM}, title = {{Brief announcement: Are lock-free concurrent algorithms practically wait-free?}}, doi = {10.1145/2611462.2611502}, year = {2014}, } @inproceedings{768, abstract = {Task allocation is a classic distributed problem in which a set of p potentially faulty processes must cooperate to perform a set of tasks. This paper considers a new dynamic version of the problem, in which tasks are injected adversarially during an asynchronous execution. We give the first asynchronous shared-memory algorithm for dynamic task allocation, and we prove that our solution is optimal within logarithmic factors. The main algorithmic idea is a randomized concurrent data structure called a dynamic to-do tree, which allows processes to pick new tasks to perform at random from the set of available tasks, and to insert tasks at random empty locations in the data structure. Our analysis shows that these properties avoid duplicating work unnecessarily. On the other hand, since the adversary controls the input as well the scheduling, it can induce executions where lots of processes contend for a few available tasks, which is inefficient. However, we prove that every algorithm has the same problem: given an arbitrary input, if OPT is the worst-case complexity of the optimal algorithm on that input, then the expected work complexity of our algorithm on the same input is O(OPT log3 m), where m is an upper bound on the number of tasks that are present in the system at any given time.}, author = {Alistarh, Dan-Adrian and Aspnes, James and Bender, Michael and Gelashvili, Rati and Gilbert, Seth}, booktitle = {Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms}, isbn = {9781611973389}, location = {Portland, OR, United States}, pages = {416 -- 435}, publisher = {SIAM}, title = {{Dynamic task allocation in asynchronous shared memory}}, doi = {10.1137/1.9781611973402.31}, year = {2014}, } @inproceedings{770, abstract = {Dynamic memory reclamation is arguably the biggest open problem in concurrent data structure design: All known solutions induce high overhead, or must be customized to the specific data structure by the programmer, or both. This paper presents StackTrack, the first concurrent memory reclamation scheme that can be applied automatically by a compiler, while maintaining efficiency. StackTrack eliminates most of the expensive bookkeeping required for memory reclamation by leveraging the power of hardware transactional memory (HTM) in a new way: it tracks thread variables dynamically, and in an atomic fashion. This effectively makes all memory references visible without having threads pay the overhead of writing out this information. Our empirical results show that this new approach matches or outperforms prior, non-automated, techniques.}, author = {Alistarh, Dan-Adrian and Eugster, Patrick and Herlihy, Maurice and Matveev, Alexander and Shavit, Nir}, booktitle = {Proceedings of the Ninth European Conference on Computer Systems}, isbn = {9781450327046}, location = {Amsterdam, The Netherlands}, publisher = {ACM}, title = {{StackTrack: An automated transactional approach to concurrent memory reclamation}}, doi = {10.1145/2592798.2592808}, year = {2014}, } @article{769, abstract = {This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual lower bound of ω(k) process steps for deterministic renaming into any namespace of size subexponential in k, where k is the number of participants. The bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic concurrent fetch-and-increment counters, queues, and stacks. The proof is based on a new reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement this individual bound with a global lower bound of ω(klog(k/c)) on the total step complexity of renaming into a namespace of size ck, for any c = 1. This result applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter implementations, that are tight within logarithmic factors. On the algorithmic side, we give a protocol that transforms any sorting network into a randomized strong adaptive renaming algorithm, with expected cost equal to the depth of the sorting network. This gives a tight adaptive renaming algorithm with expected step complexity O(log k), where k is the contention in the current execution. This algorithm is the first to achieve sublinear time, and it is time-optimal as per our randomized lower bound. Finally, we use this renaming protocol to build monotone-consistent counters with logarithmic step complexity and linearizable fetch-and-increment registers with polylogarithmic cost.}, author = {Alistarh, Dan-Adrian and Aspnes, James and Censor Hillel, Keren and Gilbert, Seth and Guerraoui, Rachid}, journal = {Journal of the ACM}, number = {3}, pages = {1--51}, publisher = {ACM}, title = {{Tight bounds for asynchronous renaming}}, doi = {10.1145/2597630}, volume = {61}, year = {2014}, } @article{451, abstract = {We introduce algorithms for the computation of homology, cohomology, and related operations on cubical cell complexes, using the technique based on a chain contraction from the original chain complex to a reduced one that represents its homology. This work is based on previous results for simplicial complexes, and uses Serre’s diagonalization for cubical cells. An implementation in C++ of the introduced algorithms is available at http://www.pawelpilarczyk.com/chaincon/ together with some examples. The paper is self-contained as much as possible, and is written at a very elementary level, so that basic knowledge of algebraic topology should be sufficient to follow it.}, author = {Pilarczyk, Pawel and Real, Pedro}, issn = {1572-9044}, journal = {Advances in Computational Mathematics}, number = {1}, pages = {253 -- 275}, publisher = {Kluwer}, title = {{Computation of cubical homology, cohomology, and (co)homological operations via chain contraction}}, doi = {10.1007/s10444-014-9356-1}, volume = {41}, year = {2014}, }