@article{17625, abstract = {We present the results of 2D, moving mesh, viscous hydrodynamical simulations of accretion on to merging supermassive black hole (SMBH) binaries. We include viscous heating, shock heating, and radiative cooling, and simulate the transition from the ‘pre-decoupling’ epoch, where the inspiral time-scale is longer than the viscous time-scale, to the ‘post-decoupling’ epoch, where the inspiral time-scale is shorter than the viscous time-scale. We find that there is no abrupt halt to the accretion at decoupling, but rather the accretion shows a slow decay, with significant accretion well after the expected decoupling. Moreover, we find that the luminosity in X-rays is significantly higher prior to the merger, as orbital energy from the SMBH binary is converted to heat via strong shocks inside the cavity, and radiated away. Following the merger, the cavity refills viscously and the accretion rate relaxes to the Shakura–Sunyaev value, while the X-ray luminosity drops as the shocks quickly dissipate.}, author = {Farris, Brian D. and Duffell, Paul and MacFadyen, Andrew I. and Haiman, Zoltán}, issn = {1745-3933}, journal = {Monthly Notices of the Royal Astronomical Society: Letters}, number = {1}, pages = {L80--L84}, publisher = {Oxford University Press}, title = {{Binary black hole accretion during inspiral and merger}}, doi = {10.1093/mnrasl/slu184}, volume = {447}, year = {2014}, } @article{17637, abstract = {Supermassive stars (SMSs; >10^5 Msun) formed in the first protogalaxies with virial temperature T_vir>10^4 K are expected to collapse into seeds of supermassive black hole (SMBHs) in the high-redshift universe (z>7). Fragmentation of the primordial gas is, however, a possible obstacle to SMS formation. We discuss the expected properties of a compact, metal-free, marginally unstable nuclear protogalactic disk, and the fate of the clumps formed in the disk by gravitational instability. Interior to a characteristic radius R_f=few*10^{-2} pc, the disk fragments into massive clumps with M_c~30 Msun. The clumps grow via accretion and migrate inward rapidly on a timescale of ~10^4 yr, which is comparable or shorter than the Kelvin-Helmholz time >10^4 yr. Some clumps may evolve to zero-age main sequence stars and halt gas accretion by radiative feedback, but most of the clumps can migrate inward and merge with the central protostar before forming massive stars. Moreover, we found that dust-induced-fragmentation in metal-enriched gas does not modify these conclusions unless Z> 3*10^{-4} Zsun, because clump migration below this metallicity remains as rapid as in the primordial case. Our results suggest that fragmentation of a compact, metal--poor disk can not prevent the formation of a SMS.}, author = {Inayoshi, Kohei and Haiman, Zoltán}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {2}, pages = {1549--1557}, publisher = {Oxford University Press}, title = {{Does disc fragmentation prevent the formation of supermassive stars in protogalaxies?}}, doi = {10.1093/mnras/stu1870}, volume = {445}, year = {2014}, } @article{17642, abstract = {The presence of quasars at redshifts z > 6 indicates the existence of supermassive black holes (SMBHs) as massive as a few times 10^9 Msun, challenging models for SMBH formation. One pathway is through the direct collapse of gas in T_{vir} > 10^4 K halos; however, this requires the suppression of H_2 cooling to prevent fragmentation. In this paper, we examine a proposed new mechanism for this suppression which relies on cold-mode accretion flows leading to shocks at high densities (n > 10^4 cm^{-3}) and temperatures (T > 10^4 K). In such gas, H_2 is efficiently collisionally dissociated. We use high-resolution numerical simulations to test this idea, demonstrating that such halos typically have lower temperature progenitors, in which cooling is efficient. Those halos do show filamentary flows; however, the gas shocks at or near the virial radius (at low densities), thus preventing the proposed collisional mechanism from operating. We do find that, if we artificially suppress H_2 formation with a high UV background, so as to allow gas in the halo center to enter the high-temperature, high-density "zone of no return", it will remain there even if the UV flux is turned off, collapsing to high density at high temperature. Due to computational limitations, we simulated only three halos. However, we demonstrate, using Monte Carlo calculations of 10^6 halo merger histories, that a few rare halos could assemble rapidly enough to avoid efficient H_2 cooling in all of their progenitor halos, provided that the UV background exceeds J_{21} ~ few at redshifts as high as z ~ 20}, author = {Fernandez, Ricardo and Bryan, Greg L. and Haiman, Zoltán and Li, Miao}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {4}, pages = {3798--3807}, publisher = {Oxford University Press}, title = {{H2 suppression with shocking inflows: Testing a pathway for supermassive black hole formation}}, doi = {10.1093/mnras/stu230}, volume = {439}, year = {2014}, } @article{17643, abstract = {Explaining the existence of supermassive black holes (SMBHs) larger than ∼10^9M⊙ at redshifts z>∼6 remains an open theoretical question. One possibility is that gas collapsing rapidly in pristine atomic cooling halos (Tvir>∼10^4K) produces 10^4−10^6M⊙ black holes. Previous studies have shown that the formation of such a black hole requires a strong UV background to prevent molecular hydrogen cooling and gas fragmentation. Recently it has been proposed that a high UV background may not be required for halos that accrete material extremely rapidly or for halos where gas cooling is delayed due to a high baryon-dark matter streaming velocity. In this work, we point out that building up a halo with Tvir>∼104K before molecular cooling becomes efficient is not sufficient for forming a direct collapse black hole (DCBH). Though molecular hydrogen formation may be delayed, it will eventually form at high densities leading to efficient cooling and fragmentation. The only obvious way that molecular cooling could be avoided in the absence of strong UV radiation, is for gas to reach high enough density to cause collisional dissociation of molecular hydrogen (∼10^4 cm^−3) before cooling occurs. However, we argue that the minimum core entropy, set by the entropy of the intergalactic medium (IGM) when it decouples from the CMB, prevents this from occurring for realistic halo masses. This is confirmed by hydrodynamical cosmological simulations without radiative cooling. We explain the maximum density versus halo mass in these simulations with simple entropy arguments. The low densities found suggest that DCBH formation indeed requires a strong UV background.}, author = {Visbal, Eli and Haiman, Zoltán and Bryan, Greg L.}, issn = {1745-3933}, journal = {Monthly Notices of the Royal Astronomical Society: Letters}, number = {1}, pages = {L100--L104}, publisher = {Oxford University Press}, title = {{A no-go theorem for direct collapse black holes without a strong ultraviolet background}}, doi = {10.1093/mnrasl/slu063}, volume = {442}, year = {2014}, } @article{17644, abstract = {We present the results of a calculation of the thermal spectrum from a 2D, moving mesh, high-accuracy, viscous hydrodynamical simulation of an accreting supermassive black hole (SMBHs) binary. We include viscous heating, shock heating, and radiative cooling, evolving for longer than a viscous time so that we reach a quasi-steady accretion state. In agreement with previous work, we find that gas is efficiently stripped from the inner edge of the circumbinary disc and enters the cavity along accretion streams, which feed persistent ‘minidiscs’ surrounding each black hole. We also find that emission from the shock-heated minidiscs and accretion streams prevents any deficit in high-energy emission that may be expected inside the circumbinary cavity, and instead leads to a characteristic brightening of the spectrum beginning in soft X-rays.}, author = {Farris, Brian D. and Duffell, Paul and MacFadyen, Andrew I. and Haiman, Zoltán}, issn = {1745-3933}, journal = {Monthly Notices of the Royal Astronomical Society: Letters}, number = {1}, pages = {L36--L40}, publisher = {Oxford University Press}, title = {{Characteristic signatures in the thermal emission from accreting binary black holes}}, doi = {10.1093/mnrasl/slu160}, volume = {446}, year = {2014}, } @article{17645, abstract = {The rapid decline in the number of strong Lyman Alpha (Lya) emitting galaxies at z > 6 provides evidence for neutral hydrogen in the IGM, but is difficult to explain with plausible models for reionization. We demonstrate that the observed reduction in Lya flux from galaxies at z > 6 can be explained by evolution in the escape fraction of ionizing photons, f_esc. We find that the median observed drop in the fraction of galaxies showing strong Lya emission, as well as the observed evolution of the Lya luminosity function both follow from a small increase in f_esc of Delta f_esc ~ 0.1 from f_esc ~ 0.6 at z ~ 6. This high escape fraction may be at odds with current constraints on the ionising photon escape fraction, which favor smaller values of f_esc < 20%. However, models that invoke a redshift evolution of f_ esc that is consistent with these constraints can suppress the z~7 Lya flux to the observed level, if they also include a small evolution in global neutral fraction of Delta x_HI ~ 0.2. Thus, an evolving escape fraction of ionising photons can be a plausible part of the explanation for evolution in the Lya emission of high redshift galaxies. More generally, our analysis also shows that the drop in the Lya fraction is quantitatively consistent with the observed evolution in the Lya luminosity functions of Lya Emitters.}, author = {Dijkstra, Mark and Wyithe, Stuart and Haiman, Zoltán and Mesinger, Andrei and Pentericci, Laura}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {4}, pages = {3309--3316}, publisher = {Oxford University Press}, title = {{Evolution in the escape fraction of ionizing photons and the decline in strong Lyα emission from z > 6 galaxies}}, doi = {10.1093/mnras/stu531}, volume = {440}, year = {2014}, } @article{17650, abstract = {High-redshift quasar observations imply that supermassive black holes (SMBHs) larger than ∼109 M⊙ formed before z=6. That such large SMBHs formed so early in the Universe remains an open theoretical problem. One possibility is that gas in atomic cooling halos exposed to strong Lyman-Werner (LW) radiation forms 104−106 M⊙ supermassive stars which quickly collapse into black holes. We propose a scenario for direct collapse black hole (DCBH) formation based on synchronized pairs of pristine atomic cooling halos. We consider halos at very small separation with one halo being a subhalo of the other. The first halo to surpass the atomic cooling threshold forms stars. Soon after these stars are formed, the other halo reaches the cooling threshold and due to its small distance from the newly formed galaxy, is exposed to the critical LW intensity required to form a DCBH. The main advantage of this scenario is that synchronization can potentially prevent photoevaporation and metal pollution in DCBH-forming halos. Since the halos reach the atomic cooling threshold at nearly the same time, the DCBH-forming halo is only exposed to ionizing radiation for a brief period. Tight synchronization could allow the DCBH to form before stars in the nearby galaxy reach the end of their lives and generate supernovae winds. We use N-body simulations to estimate the abundance of DCBHs formed in this way. The largest source of uncertainty in our estimate is the initial mass function (IMF) of metal free stars formed in atomic cooling halos. We find that even for tight synchronization, the density of DCBHs formed in this scenario could explain the SMBHs implied by z=6 quasar observations. Metal pollution and photoevaporation could potentially reduce the abundance of DCBHs below that required to explain the observations in other models that rely on a high LW flux.}, author = {Visbal, Eli and Haiman, Zoltán and Bryan, Greg L.}, issn = {0035-8711}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {1}, pages = {1056--1063}, publisher = {Oxford University Press}, title = {{Direct collapse black hole formation from synchronized pairs of atomic cooling haloes}}, doi = {10.1093/mnras/stu1794}, volume = {445}, year = {2014}, } @article{17682, abstract = {We propose a new spectral signature for supermassive black hole binaries (SMBHBs) with circumbinary gas discs: a sharp drop in flux bluewards of the Lyman limit. A prominent edge is produced if the gas dominating the emission in the Lyman continuum region of the spectrum is sufficiently cold (T ≲ 20 000 K) to contain significant neutral hydrogen. Circumbinary discs may be in this regime if the binary torques open a central cavity in the disc and clear most of the hot gas from the inner region, and if any residual UV emission from the individual BHs is either dim or intermittent. We model the vertical structure and spectra of circumbinary discs using the radiative transfer code tlusty, and identify the range of BH masses and binary separations producing a Lyman edge. We find that compact supermassive (M ≳ 108 M⊙) binaries with orbital periods of ∼0.1–10 yr, whose gravitational waves are expected to be detectable by pulsar timing arrays, could have prominent Lyman edges. Such strong spectral edge features are not typically present in AGN spectra and could serve as corroborating evidence for the presence of an SMBHB.}, author = {Generozov, Aleksey and Haiman, Zoltán}, issn = {1745-3933}, journal = {Monthly Notices of the Royal Astronomical Society: Letters}, number = {1}, pages = {L64--L68}, publisher = {Oxford University Press}, title = {{Lyman edges in supermassive black hole binaries}}, doi = {10.1093/mnrasl/slu075}, volume = {443}, year = {2014}, } @article{17689, abstract = {We report the serendipitous discoveries of companion galaxies to two high-redshift quasars. SDSS J025617.7+001904 is a z=4.79 quasar included in our recent survey of faint quasars in the SDSS Stripe 82 region. The initial MMT slit spectroscopy shows excess Lyman alpha emission extending well beyond the quasar's light profile. Further imaging and spectroscopy with LBT/MODS1 confirms the presence of a bright galaxy (i_AB = 23.6) located 2arcsec (12 kpc projected) from the quasar with strong Lyman alpha emission (EW_0 ~ 100Ang) at the redshift of the quasar, as well as faint continuum. The second quasar, CFHQS J005006.6+344522 (z=6.25), is included in our recent HST SNAP survey of z~6 quasars searching for evidence of gravitational lensing. Deep imaging with ACS and WFC3 confirms an optical dropout ~4.5 mag fainter than the quasar (Y_AB=25) at a separation of 0.9 arcsec. The red i_775-Y_105 color of the galaxy and its proximity to the quasar (5 kpc projected if at the quasar redshift) strongly favor an association with the quasar. Although it is much fainter than the quasar it is remarkably bright when compared to field galaxies at this redshift, while showing no evidence for lensing. Both systems may represent late-stage mergers of two massive galaxies, with the observed light for one dominated by powerful ongoing star formation and for the other by rapid black hole growth. Observations of close companions are rare; if major mergers are primarily responsible for high-redshift quasar fueling then the phase when progenitor galaxies can be observed as bright companions is relatively short.}, author = {McGreer, Ian D. and Fan, Xiaohui and Strauss, Michael A. and Haiman, Zoltán and Richards, Gordon T. and Jiang, Linhua and Bian, Fuyan and Schneider, Donald P.}, issn = {1538-3881}, journal = {The Astronomical Journal}, number = {4}, publisher = {American Astronomical Society}, title = {{Close companions to two high-redshift quasars}}, doi = {10.1088/0004-6256/148/4/73}, volume = {148}, year = {2014}, } @article{17692, abstract = {Quadrupole oscillation modes in stars can resonate with incident gravitational waves (GWs), and grow non-linear at the expense of GW energy. Stars near massive black hole binaries (MBHBs) can act as GW-charged batteries, discharging radiatively. Mass-loss from these stars can prompt MBHB accretion at near-Eddington rates. GW opacity is independent of amplitude, so distant resonating stars can eclipse GW sources. Absorption by the Sun of GWs from Galactic white dwarf binaries may be detectable with second-generation space-based GW detectors as a shadow within a complex diffraction pattern.}, author = {McKernan, B. and Ford, K. E. S. and Kocsis, B. and Haiman, Zoltán}, issn = {1745-3933}, journal = {Monthly Notices of the Royal Astronomical Society: Letters}, number = {1}, pages = {L74--L78}, publisher = {Oxford University Press}, title = {{Stars as resonant absorbers of gravitational waves}}, doi = {10.1093/mnrasl/slu136}, volume = {445}, year = {2014}, } @article{17703, abstract = {The weak lensing power spectrum is a powerful tool to probe cosmological parameters. Additionally, lensing peak counts contain cosmological information beyond the power spectrum. Both of these statistics can be affected by the preferential selection of source galaxies in patches of the sky with high magnification, as well as by the dilution in the source galaxy surface density in such regions. If not accounted for, these biases introduce systematic errors for cosmological measurements. Here we quantify these systematic errors, using convergence maps from a suite of ray-tracing N-body simulations. At the cut-off magnitude m of on-going and planned major weak lensing surveys, the logarithmic slope of the cumulative number counts s = dlog[n(>m)]/dlog(m) is in the range 0.1 < s < 0.5. At s = 0.2, expected in the I band for LSST, the inferred values of Omega_m, w and sigma_8 are biased by many sigma (where sigma denotes the marginalized error) and therefore the biases will need to be carefully modeled. We also find that the parameters are biased differently in the (Omega_m, w, sigma_8) parameter space when the power spectrum and when the peak counts are used. In particular, w derived from the power spectrum is less affected than w derived from peak counts, while the opposite is true for the best-constrained combination of [sigma_8 Omega_m^gamma] (with gamma=0.62 from the power spectrum and gamma = 0.48 from peak counts). This suggests that the combination of the power spectrum and peak counts can help mitigate the impact of magnification and size biases.}, author = {Liu, Jia and Haiman, Zoltán and Hui, Lam and Kratochvil, Jan M. and May, Morgan}, issn = {1550-7998}, journal = {Physical Review D}, number = {2}, publisher = {American Physical Society}, title = {{Impact of magnification and size bias on the weak lensing power spectrum and peak statistics}}, doi = {10.1103/physrevd.89.023515}, volume = {89}, 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}, pages = {416 -- 435}, publisher = {SIAM}, title = {{Dynamic task allocation in asynchronous shared memory}}, doi = {10.1137/1.9781611973402.31}, 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}, publisher = {ACM}, title = {{Tight bounds for asynchronous renaming}}, doi = {10.1145/2597630}, volume = {61}, year = {2014}, } @article{7699, author = {Sweeney, Lora Beatrice Jaeger and Kelley, Darcy B}, issn = {0959-4388}, journal = {Current Opinion in Neurobiology}, number = {10}, pages = {34--41}, publisher = {Elsevier}, title = {{Harnessing vocal patterns for social communication}}, doi = {10.1016/j.conb.2014.06.006}, volume = {28}, 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}, publisher = {ACM}, title = {{StackTrack: An automated transactional approach to concurrent memory reclamation}}, doi = {10.1145/2592798.2592808}, 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}, 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{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}, pages = {714 -- 723}, publisher = {ACM}, title = {{Are lock-free concurrent algorithms practically wait-free?}}, doi = {10.1145/2591796.2591836}, 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}, editor = {Kuhn, Fabian}, location = {Austin, USA}, pages = {61 -- 75}, publisher = {Springer}, title = {{Communication-efficient randomized consensus}}, doi = {10.1007/978-3-662-45174-8_5}, volume = {8784}, 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}, pages = {50 -- 52}, publisher = {ACM}, title = {{Brief announcement: Are lock-free concurrent algorithms practically wait-free?}}, doi = {10.1145/2611462.2611502}, year = {2014}, } @inbook{7743, abstract = {Experimental studies have demonstrated that environmental variation can create genotype‐environment interactions (GEIs) in the traits involved in sexual selection. Understanding the genetic architecture of phenotype across environments will require statistical tests that can describe both changes in genetic variance and covariance across environments. This chapter outlines the theoretical framework for the processes of sexual selection in the wild, identifying key parameters in wild systems, and highlighting the potential effects of the environment. It describes the proposed approaches for the estimation of these key parameters in a quantitative genetic framework within naturally occurring pedigreed populations. The chapter provides a worked example for a range of analysis methods. It aims to provide an overview of the analytical methods that can be used to model GEIs for traits involved in sexual selection in naturally occurring pedigreed populations.}, author = {Robinson, Matthew Richard and Qvarnström, Anna}, booktitle = {Genotype-by-Environment Interactions and Sexual Selection}, editor = {Hunt, John and Hosken, David}, isbn = {9780470671795}, pages = {137--168}, publisher = {Wiley}, title = {{Influence of the environment on the genetic architecture of traits involved in sexual selection within wild populations}}, doi = {10.1002/9781118912591.ch6}, year = {2014}, }