---
_id: '17625'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Brian D.
full_name: Farris, Brian D.
last_name: Farris
- first_name: Paul
full_name: Duffell, Paul
last_name: Duffell
- first_name: Andrew I.
full_name: MacFadyen, Andrew I.
last_name: MacFadyen
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
citation:
ama: 'Farris BD, Duffell P, MacFadyen AI, Haiman Z. Binary black hole accretion
during inspiral and merger. Monthly Notices of the Royal Astronomical Society:
Letters. 2014;447(1):L80-L84. doi:10.1093/mnrasl/slu184'
apa: 'Farris, B. D., Duffell, P., MacFadyen, A. I., & Haiman, Z. (2014). Binary
black hole accretion during inspiral and merger. Monthly Notices of the Royal
Astronomical Society: Letters. Oxford University Press. https://doi.org/10.1093/mnrasl/slu184'
chicago: 'Farris, Brian D., Paul Duffell, Andrew I. MacFadyen, and Zoltán Haiman.
“Binary Black Hole Accretion during Inspiral and Merger.” Monthly Notices of
the Royal Astronomical Society: Letters. Oxford University Press, 2014. https://doi.org/10.1093/mnrasl/slu184.'
ieee: 'B. D. Farris, P. Duffell, A. I. MacFadyen, and Z. Haiman, “Binary black hole
accretion during inspiral and merger,” Monthly Notices of the Royal Astronomical
Society: Letters, vol. 447, no. 1. Oxford University Press, pp. L80–L84, 2014.'
ista: 'Farris BD, Duffell P, MacFadyen AI, Haiman Z. 2014. Binary black hole accretion
during inspiral and merger. Monthly Notices of the Royal Astronomical Society:
Letters. 447(1), L80–L84.'
mla: 'Farris, Brian D., et al. “Binary Black Hole Accretion during Inspiral and
Merger.” Monthly Notices of the Royal Astronomical Society: Letters, vol.
447, no. 1, Oxford University Press, 2014, pp. L80–84, doi:10.1093/mnrasl/slu184.'
short: 'B.D. Farris, P. Duffell, A.I. MacFadyen, Z. Haiman, Monthly Notices of the
Royal Astronomical Society: Letters 447 (2014) L80–L84.'
date_created: 2024-09-05T13:54:34Z
date_published: 2014-12-19T00:00:00Z
date_updated: 2024-09-24T08:50:47Z
day: '19'
doi: 10.1093/mnrasl/slu184
extern: '1'
external_id:
arxiv:
- '1409.5124'
intvolume: ' 447'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.1409.5124'
month: '12'
oa: 1
oa_version: Preprint
page: L80-L84
publication: 'Monthly Notices of the Royal Astronomical Society: Letters'
publication_identifier:
issn:
- 1745-3933
- 1745-3925
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Binary black hole accretion during inspiral and merger
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 447
year: '2014'
...
---
_id: '17637'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Kohei
full_name: Inayoshi, Kohei
last_name: Inayoshi
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
citation:
ama: Inayoshi K, Haiman Z. Does disc fragmentation prevent the formation of supermassive
stars in protogalaxies? Monthly Notices of the Royal Astronomical Society.
2014;445(2):1549-1557. doi:10.1093/mnras/stu1870
apa: Inayoshi, K., & Haiman, Z. (2014). Does disc fragmentation prevent the
formation of supermassive stars in protogalaxies? Monthly Notices of the Royal
Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/stu1870
chicago: Inayoshi, Kohei, and Zoltán Haiman. “Does Disc Fragmentation Prevent the
Formation of Supermassive Stars in Protogalaxies?” Monthly Notices of the Royal
Astronomical Society. Oxford University Press, 2014. https://doi.org/10.1093/mnras/stu1870.
ieee: K. Inayoshi and Z. Haiman, “Does disc fragmentation prevent the formation
of supermassive stars in protogalaxies?,” Monthly Notices of the Royal Astronomical
Society, vol. 445, no. 2. Oxford University Press, pp. 1549–1557, 2014.
ista: Inayoshi K, Haiman Z. 2014. Does disc fragmentation prevent the formation
of supermassive stars in protogalaxies? Monthly Notices of the Royal Astronomical
Society. 445(2), 1549–1557.
mla: Inayoshi, Kohei, and Zoltán Haiman. “Does Disc Fragmentation Prevent the Formation
of Supermassive Stars in Protogalaxies?” Monthly Notices of the Royal Astronomical
Society, vol. 445, no. 2, Oxford University Press, 2014, pp. 1549–57, doi:10.1093/mnras/stu1870.
short: K. Inayoshi, Z. Haiman, Monthly Notices of the Royal Astronomical Society
445 (2014) 1549–1557.
date_created: 2024-09-06T07:15:08Z
date_published: 2014-10-09T00:00:00Z
date_updated: 2024-09-24T11:33:30Z
day: '09'
doi: 10.1093/mnras/stu1870
extern: '1'
intvolume: ' 445'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/mnras/stu1870
month: '10'
oa: 1
oa_version: Published Version
page: 1549-1557
publication: Monthly Notices of the Royal Astronomical Society
publication_identifier:
issn:
- 1365-2966
- 0035-8711
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Does disc fragmentation prevent the formation of supermassive stars in protogalaxies?
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 445
year: '2014'
...
---
_id: '17642'
abstract:
- lang: eng
text: 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
article_processing_charge: No
article_type: original
author:
- first_name: Ricardo
full_name: Fernandez, Ricardo
last_name: Fernandez
- first_name: Greg L.
full_name: Bryan, Greg L.
last_name: Bryan
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
- first_name: Miao
full_name: Li, Miao
last_name: Li
citation:
ama: 'Fernandez R, Bryan GL, Haiman Z, Li M. H2 suppression with shocking inflows:
Testing a pathway for supermassive black hole formation. Monthly Notices of
the Royal Astronomical Society. 2014;439(4):3798-3807. doi:10.1093/mnras/stu230'
apa: 'Fernandez, R., Bryan, G. L., Haiman, Z., & Li, M. (2014). H2 suppression
with shocking inflows: Testing a pathway for supermassive black hole formation.
Monthly Notices of the Royal Astronomical Society. Oxford University Press.
https://doi.org/10.1093/mnras/stu230'
chicago: 'Fernandez, Ricardo, Greg L. Bryan, Zoltán Haiman, and Miao Li. “H2 Suppression
with Shocking Inflows: Testing a Pathway for Supermassive Black Hole Formation.”
Monthly Notices of the Royal Astronomical Society. Oxford University Press,
2014. https://doi.org/10.1093/mnras/stu230.'
ieee: 'R. Fernandez, G. L. Bryan, Z. Haiman, and M. Li, “H2 suppression with shocking
inflows: Testing a pathway for supermassive black hole formation,” Monthly
Notices of the Royal Astronomical Society, vol. 439, no. 4. Oxford University
Press, pp. 3798–3807, 2014.'
ista: 'Fernandez R, Bryan GL, Haiman Z, Li M. 2014. H2 suppression with shocking
inflows: Testing a pathway for supermassive black hole formation. Monthly Notices
of the Royal Astronomical Society. 439(4), 3798–3807.'
mla: 'Fernandez, Ricardo, et al. “H2 Suppression with Shocking Inflows: Testing
a Pathway for Supermassive Black Hole Formation.” Monthly Notices of the Royal
Astronomical Society, vol. 439, no. 4, Oxford University Press, 2014, pp.
3798–807, doi:10.1093/mnras/stu230.'
short: R. Fernandez, G.L. Bryan, Z. Haiman, M. Li, Monthly Notices of the Royal
Astronomical Society 439 (2014) 3798–3807.
date_created: 2024-09-06T07:21:52Z
date_published: 2014-02-26T00:00:00Z
date_updated: 2024-09-24T11:56:43Z
day: '26'
doi: 10.1093/mnras/stu230
extern: '1'
intvolume: ' 439'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/mnras/stu230
month: '02'
oa: 1
oa_version: Published Version
page: 3798-3807
publication: Monthly Notices of the Royal Astronomical Society
publication_identifier:
issn:
- 1365-2966
- 0035-8711
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'H2 suppression with shocking inflows: Testing a pathway for supermassive black
hole formation'
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 439
year: '2014'
...
---
_id: '17643'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Eli
full_name: Visbal, Eli
last_name: Visbal
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
- first_name: Greg L.
full_name: Bryan, Greg L.
last_name: Bryan
citation:
ama: 'Visbal E, Haiman Z, Bryan GL. A no-go theorem for direct collapse black holes
without a strong ultraviolet background. Monthly Notices of the Royal Astronomical
Society: Letters. 2014;442(1):L100-L104. doi:10.1093/mnrasl/slu063'
apa: 'Visbal, E., Haiman, Z., & Bryan, G. L. (2014). A no-go theorem for direct
collapse black holes without a strong ultraviolet background. Monthly Notices
of the Royal Astronomical Society: Letters. Oxford University Press. https://doi.org/10.1093/mnrasl/slu063'
chicago: 'Visbal, Eli, Zoltán Haiman, and Greg L. Bryan. “A No-Go Theorem for Direct
Collapse Black Holes without a Strong Ultraviolet Background.” Monthly Notices
of the Royal Astronomical Society: Letters. Oxford University Press, 2014.
https://doi.org/10.1093/mnrasl/slu063.'
ieee: 'E. Visbal, Z. Haiman, and G. L. Bryan, “A no-go theorem for direct collapse
black holes without a strong ultraviolet background,” Monthly Notices of the
Royal Astronomical Society: Letters, vol. 442, no. 1. Oxford University Press,
pp. L100–L104, 2014.'
ista: 'Visbal E, Haiman Z, Bryan GL. 2014. A no-go theorem for direct collapse black
holes without a strong ultraviolet background. Monthly Notices of the Royal Astronomical
Society: Letters. 442(1), L100–L104.'
mla: 'Visbal, Eli, et al. “A No-Go Theorem for Direct Collapse Black Holes without
a Strong Ultraviolet Background.” Monthly Notices of the Royal Astronomical
Society: Letters, vol. 442, no. 1, Oxford University Press, 2014, pp. L100–04,
doi:10.1093/mnrasl/slu063.'
short: 'E. Visbal, Z. Haiman, G.L. Bryan, Monthly Notices of the Royal Astronomical
Society: Letters 442 (2014) L100–L104.'
date_created: 2024-09-06T07:22:36Z
date_published: 2014-06-10T00:00:00Z
date_updated: 2024-09-24T12:04:03Z
day: '10'
doi: 10.1093/mnrasl/slu063
extern: '1'
intvolume: ' 442'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/mnrasl/slu063
month: '06'
oa: 1
oa_version: Published Version
page: L100-L104
publication: 'Monthly Notices of the Royal Astronomical Society: Letters'
publication_identifier:
issn:
- 1745-3933
- 1745-3925
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: A no-go theorem for direct collapse black holes without a strong ultraviolet
background
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 442
year: '2014'
...
---
_id: '17644'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Brian D.
full_name: Farris, Brian D.
last_name: Farris
- first_name: Paul
full_name: Duffell, Paul
last_name: Duffell
- first_name: Andrew I.
full_name: MacFadyen, Andrew I.
last_name: MacFadyen
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
citation:
ama: 'Farris BD, Duffell P, MacFadyen AI, Haiman Z. Characteristic signatures in
the thermal emission from accreting binary black holes. Monthly Notices of
the Royal Astronomical Society: Letters. 2014;446(1):L36-L40. doi:10.1093/mnrasl/slu160'
apa: 'Farris, B. D., Duffell, P., MacFadyen, A. I., & Haiman, Z. (2014). Characteristic
signatures in the thermal emission from accreting binary black holes. Monthly
Notices of the Royal Astronomical Society: Letters. Oxford University Press.
https://doi.org/10.1093/mnrasl/slu160'
chicago: 'Farris, Brian D., Paul Duffell, Andrew I. MacFadyen, and Zoltán Haiman.
“Characteristic Signatures in the Thermal Emission from Accreting Binary Black
Holes.” Monthly Notices of the Royal Astronomical Society: Letters. Oxford
University Press, 2014. https://doi.org/10.1093/mnrasl/slu160.'
ieee: 'B. D. Farris, P. Duffell, A. I. MacFadyen, and Z. Haiman, “Characteristic
signatures in the thermal emission from accreting binary black holes,” Monthly
Notices of the Royal Astronomical Society: Letters, vol. 446, no. 1. Oxford
University Press, pp. L36–L40, 2014.'
ista: 'Farris BD, Duffell P, MacFadyen AI, Haiman Z. 2014. Characteristic signatures
in the thermal emission from accreting binary black holes. Monthly Notices of
the Royal Astronomical Society: Letters. 446(1), L36–L40.'
mla: 'Farris, Brian D., et al. “Characteristic Signatures in the Thermal Emission
from Accreting Binary Black Holes.” Monthly Notices of the Royal Astronomical
Society: Letters, vol. 446, no. 1, Oxford University Press, 2014, pp. L36–40,
doi:10.1093/mnrasl/slu160.'
short: 'B.D. Farris, P. Duffell, A.I. MacFadyen, Z. Haiman, Monthly Notices of the
Royal Astronomical Society: Letters 446 (2014) L36–L40.'
date_created: 2024-09-06T07:23:36Z
date_published: 2014-11-10T00:00:00Z
date_updated: 2024-09-24T12:07:00Z
day: '10'
doi: 10.1093/mnrasl/slu160
extern: '1'
intvolume: ' 446'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/mnrasl/slu160
month: '11'
oa: 1
oa_version: Published Version
page: L36-L40
publication: 'Monthly Notices of the Royal Astronomical Society: Letters'
publication_identifier:
issn:
- 1745-3933
- 1745-3925
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Characteristic signatures in the thermal emission from accreting binary black
holes
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 446
year: '2014'
...
---
_id: '17645'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Mark
full_name: Dijkstra, Mark
last_name: Dijkstra
- first_name: Stuart
full_name: Wyithe, Stuart
last_name: Wyithe
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
- first_name: Andrei
full_name: Mesinger, Andrei
last_name: Mesinger
- first_name: Laura
full_name: Pentericci, Laura
last_name: Pentericci
citation:
ama: Dijkstra M, Wyithe S, Haiman Z, Mesinger A, Pentericci L. Evolution in the
escape fraction of ionizing photons and the decline in strong Lyα emission from
z > 6 galaxies. Monthly Notices of the Royal Astronomical Society.
2014;440(4):3309-3316. doi:10.1093/mnras/stu531
apa: Dijkstra, M., Wyithe, S., Haiman, Z., Mesinger, A., & Pentericci, L. (2014).
Evolution in the escape fraction of ionizing photons and the decline in strong
Lyα emission from z > 6 galaxies. Monthly Notices of the Royal Astronomical
Society. Oxford University Press. https://doi.org/10.1093/mnras/stu531
chicago: Dijkstra, Mark, Stuart Wyithe, Zoltán Haiman, Andrei Mesinger, and Laura
Pentericci. “Evolution in the Escape Fraction of Ionizing Photons and the Decline
in Strong Lyα Emission from z > 6 Galaxies.” Monthly Notices of the Royal
Astronomical Society. Oxford University Press, 2014. https://doi.org/10.1093/mnras/stu531.
ieee: M. Dijkstra, S. Wyithe, Z. Haiman, A. Mesinger, and L. Pentericci, “Evolution
in the escape fraction of ionizing photons and the decline in strong Lyα emission
from z > 6 galaxies,” Monthly Notices of the Royal Astronomical Society,
vol. 440, no. 4. Oxford University Press, pp. 3309–3316, 2014.
ista: Dijkstra M, Wyithe S, Haiman Z, Mesinger A, Pentericci L. 2014. Evolution
in the escape fraction of ionizing photons and the decline in strong Lyα emission
from z > 6 galaxies. Monthly Notices of the Royal Astronomical Society. 440(4),
3309–3316.
mla: Dijkstra, Mark, et al. “Evolution in the Escape Fraction of Ionizing Photons
and the Decline in Strong Lyα Emission from z > 6 Galaxies.” Monthly Notices
of the Royal Astronomical Society, vol. 440, no. 4, Oxford University Press,
2014, pp. 3309–16, doi:10.1093/mnras/stu531.
short: M. Dijkstra, S. Wyithe, Z. Haiman, A. Mesinger, L. Pentericci, Monthly Notices
of the Royal Astronomical Society 440 (2014) 3309–3316.
date_created: 2024-09-06T07:24:26Z
date_published: 2014-04-17T00:00:00Z
date_updated: 2024-09-24T12:10:12Z
day: '17'
doi: 10.1093/mnras/stu531
extern: '1'
intvolume: ' 440'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/mnras/stu531
month: '04'
oa: 1
oa_version: Published Version
page: 3309-3316
publication: Monthly Notices of the Royal Astronomical Society
publication_identifier:
issn:
- 1365-2966
- 0035-8711
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Evolution in the escape fraction of ionizing photons and the decline in strong
Lyα emission from z > 6 galaxies
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 440
year: '2014'
...
---
_id: '17650'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Eli
full_name: Visbal, Eli
last_name: Visbal
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
- first_name: Greg L.
full_name: Bryan, Greg L.
last_name: Bryan
citation:
ama: Visbal E, Haiman Z, Bryan GL. Direct collapse black hole formation from synchronized
pairs of atomic cooling haloes. Monthly Notices of the Royal Astronomical Society.
2014;445(1):1056-1063. doi:10.1093/mnras/stu1794
apa: Visbal, E., Haiman, Z., & Bryan, G. L. (2014). Direct collapse black hole
formation from synchronized pairs of atomic cooling haloes. Monthly Notices
of the Royal Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/stu1794
chicago: Visbal, Eli, Zoltán Haiman, and Greg L. Bryan. “Direct Collapse Black Hole
Formation from Synchronized Pairs of Atomic Cooling Haloes.” Monthly Notices
of the Royal Astronomical Society. Oxford University Press, 2014. https://doi.org/10.1093/mnras/stu1794.
ieee: E. Visbal, Z. Haiman, and G. L. Bryan, “Direct collapse black hole formation
from synchronized pairs of atomic cooling haloes,” Monthly Notices of the Royal
Astronomical Society, vol. 445, no. 1. Oxford University Press, pp. 1056–1063,
2014.
ista: Visbal E, Haiman Z, Bryan GL. 2014. Direct collapse black hole formation from
synchronized pairs of atomic cooling haloes. Monthly Notices of the Royal Astronomical
Society. 445(1), 1056–1063.
mla: Visbal, Eli, et al. “Direct Collapse Black Hole Formation from Synchronized
Pairs of Atomic Cooling Haloes.” Monthly Notices of the Royal Astronomical
Society, vol. 445, no. 1, Oxford University Press, 2014, pp. 1056–63, doi:10.1093/mnras/stu1794.
short: E. Visbal, Z. Haiman, G.L. Bryan, Monthly Notices of the Royal Astronomical
Society 445 (2014) 1056–1063.
date_created: 2024-09-06T07:28:59Z
date_published: 2014-10-08T00:00:00Z
date_updated: 2024-09-24T13:02:31Z
day: '08'
doi: 10.1093/mnras/stu1794
extern: '1'
intvolume: ' 445'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/mnras/stu1794
month: '10'
oa: 1
oa_version: Published Version
page: 1056-1063
publication: Monthly Notices of the Royal Astronomical Society
publication_identifier:
issn:
- 0035-8711
- 1365-2966
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Direct collapse black hole formation from synchronized pairs of atomic cooling
haloes
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 445
year: '2014'
...
---
_id: '17682'
abstract:
- lang: eng
text: '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.'
article_processing_charge: No
article_type: original
author:
- first_name: Aleksey
full_name: Generozov, Aleksey
last_name: Generozov
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
citation:
ama: 'Generozov A, Haiman Z. Lyman edges in supermassive black hole binaries. Monthly
Notices of the Royal Astronomical Society: Letters. 2014;443(1):L64-L68. doi:10.1093/mnrasl/slu075'
apa: 'Generozov, A., & Haiman, Z. (2014). Lyman edges in supermassive black
hole binaries. Monthly Notices of the Royal Astronomical Society: Letters.
Oxford University Press. https://doi.org/10.1093/mnrasl/slu075'
chicago: 'Generozov, Aleksey, and Zoltán Haiman. “Lyman Edges in Supermassive Black
Hole Binaries.” Monthly Notices of the Royal Astronomical Society: Letters.
Oxford University Press, 2014. https://doi.org/10.1093/mnrasl/slu075.'
ieee: 'A. Generozov and Z. Haiman, “Lyman edges in supermassive black hole binaries,”
Monthly Notices of the Royal Astronomical Society: Letters, vol. 443, no.
1. Oxford University Press, pp. L64–L68, 2014.'
ista: 'Generozov A, Haiman Z. 2014. Lyman edges in supermassive black hole binaries.
Monthly Notices of the Royal Astronomical Society: Letters. 443(1), L64–L68.'
mla: 'Generozov, Aleksey, and Zoltán Haiman. “Lyman Edges in Supermassive Black
Hole Binaries.” Monthly Notices of the Royal Astronomical Society: Letters,
vol. 443, no. 1, Oxford University Press, 2014, pp. L64–68, doi:10.1093/mnrasl/slu075.'
short: 'A. Generozov, Z. Haiman, Monthly Notices of the Royal Astronomical Society:
Letters 443 (2014) L64–L68.'
date_created: 2024-09-06T08:15:56Z
date_published: 2014-07-02T00:00:00Z
date_updated: 2024-09-25T09:10:05Z
day: '02'
doi: 10.1093/mnrasl/slu075
extern: '1'
intvolume: ' 443'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/mnrasl/slu075
month: '07'
oa: 1
oa_version: Published Version
page: L64-L68
publication: 'Monthly Notices of the Royal Astronomical Society: Letters'
publication_identifier:
issn:
- 1745-3933
- 1745-3925
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lyman edges in supermassive black hole binaries
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 443
year: '2014'
...
---
_id: '17689'
abstract:
- lang: eng
text: 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.
article_number: '73'
article_processing_charge: No
article_type: original
author:
- first_name: Ian D.
full_name: McGreer, Ian D.
last_name: McGreer
- first_name: Xiaohui
full_name: Fan, Xiaohui
last_name: Fan
- first_name: Michael A.
full_name: Strauss, Michael A.
last_name: Strauss
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
- first_name: Gordon T.
full_name: Richards, Gordon T.
last_name: Richards
- first_name: Linhua
full_name: Jiang, Linhua
last_name: Jiang
- first_name: Fuyan
full_name: Bian, Fuyan
last_name: Bian
- first_name: Donald P.
full_name: Schneider, Donald P.
last_name: Schneider
citation:
ama: McGreer ID, Fan X, Strauss MA, et al. Close companions to two high-redshift
quasars. The Astronomical Journal. 2014;148(4). doi:10.1088/0004-6256/148/4/73
apa: McGreer, I. D., Fan, X., Strauss, M. A., Haiman, Z., Richards, G. T., Jiang,
L., … Schneider, D. P. (2014). Close companions to two high-redshift quasars.
The Astronomical Journal. American Astronomical Society. https://doi.org/10.1088/0004-6256/148/4/73
chicago: McGreer, Ian D., Xiaohui Fan, Michael A. Strauss, Zoltán Haiman, Gordon
T. Richards, Linhua Jiang, Fuyan Bian, and Donald P. Schneider. “Close Companions
to Two High-Redshift Quasars.” The Astronomical Journal. American Astronomical
Society, 2014. https://doi.org/10.1088/0004-6256/148/4/73.
ieee: I. D. McGreer et al., “Close companions to two high-redshift quasars,”
The Astronomical Journal, vol. 148, no. 4. American Astronomical Society,
2014.
ista: McGreer ID, Fan X, Strauss MA, Haiman Z, Richards GT, Jiang L, Bian F, Schneider
DP. 2014. Close companions to two high-redshift quasars. The Astronomical Journal.
148(4), 73.
mla: McGreer, Ian D., et al. “Close Companions to Two High-Redshift Quasars.” The
Astronomical Journal, vol. 148, no. 4, 73, American Astronomical Society,
2014, doi:10.1088/0004-6256/148/4/73.
short: I.D. McGreer, X. Fan, M.A. Strauss, Z. Haiman, G.T. Richards, L. Jiang, F.
Bian, D.P. Schneider, The Astronomical Journal 148 (2014).
date_created: 2024-09-06T08:24:25Z
date_published: 2014-09-15T00:00:00Z
date_updated: 2024-09-25T09:51:31Z
day: '15'
doi: 10.1088/0004-6256/148/4/73
extern: '1'
intvolume: ' 148'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1088/0004-6256/148/4/73
month: '09'
oa: 1
oa_version: Published Version
publication: The Astronomical Journal
publication_identifier:
issn:
- 1538-3881
publication_status: published
publisher: American Astronomical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Close companions to two high-redshift quasars
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 148
year: '2014'
...
---
_id: '17692'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: B.
full_name: McKernan, B.
last_name: McKernan
- first_name: K. E. S.
full_name: Ford, K. E. S.
last_name: Ford
- first_name: B.
full_name: Kocsis, B.
last_name: Kocsis
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
citation:
ama: 'McKernan B, Ford KES, Kocsis B, Haiman Z. Stars as resonant absorbers of gravitational
waves. Monthly Notices of the Royal Astronomical Society: Letters. 2014;445(1):L74-L78.
doi:10.1093/mnrasl/slu136'
apa: 'McKernan, B., Ford, K. E. S., Kocsis, B., & Haiman, Z. (2014). Stars as
resonant absorbers of gravitational waves. Monthly Notices of the Royal Astronomical
Society: Letters. Oxford University Press. https://doi.org/10.1093/mnrasl/slu136'
chicago: 'McKernan, B., K. E. S. Ford, B. Kocsis, and Zoltán Haiman. “Stars as Resonant
Absorbers of Gravitational Waves.” Monthly Notices of the Royal Astronomical
Society: Letters. Oxford University Press, 2014. https://doi.org/10.1093/mnrasl/slu136.'
ieee: 'B. McKernan, K. E. S. Ford, B. Kocsis, and Z. Haiman, “Stars as resonant
absorbers of gravitational waves,” Monthly Notices of the Royal Astronomical
Society: Letters, vol. 445, no. 1. Oxford University Press, pp. L74–L78, 2014.'
ista: 'McKernan B, Ford KES, Kocsis B, Haiman Z. 2014. Stars as resonant absorbers
of gravitational waves. Monthly Notices of the Royal Astronomical Society: Letters.
445(1), L74–L78.'
mla: 'McKernan, B., et al. “Stars as Resonant Absorbers of Gravitational Waves.”
Monthly Notices of the Royal Astronomical Society: Letters, vol. 445, no.
1, Oxford University Press, 2014, pp. L74–78, doi:10.1093/mnrasl/slu136.'
short: 'B. McKernan, K.E.S. Ford, B. Kocsis, Z. Haiman, Monthly Notices of the Royal
Astronomical Society: Letters 445 (2014) L74–L78.'
date_created: 2024-09-06T08:38:54Z
date_published: 2014-09-18T00:00:00Z
date_updated: 2024-09-25T09:58:34Z
day: '18'
doi: 10.1093/mnrasl/slu136
extern: '1'
intvolume: ' 445'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/mnrasl/slu136
month: '09'
oa: 1
oa_version: Published Version
page: L74-L78
publication: 'Monthly Notices of the Royal Astronomical Society: Letters'
publication_identifier:
issn:
- 1745-3933
- 1745-3925
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Stars as resonant absorbers of gravitational waves
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 445
year: '2014'
...
---
_id: '17703'
abstract:
- lang: eng
text: 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.
article_number: '023515'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jia
full_name: Liu, Jia
last_name: Liu
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
- first_name: Lam
full_name: Hui, Lam
last_name: Hui
- first_name: Jan M.
full_name: Kratochvil, Jan M.
last_name: Kratochvil
- first_name: Morgan
full_name: May, Morgan
last_name: May
citation:
ama: Liu J, Haiman Z, Hui L, Kratochvil JM, May M. Impact of magnification and size
bias on the weak lensing power spectrum and peak statistics. Physical Review
D. 2014;89(2). doi:10.1103/physrevd.89.023515
apa: Liu, J., Haiman, Z., Hui, L., Kratochvil, J. M., & May, M. (2014). Impact
of magnification and size bias on the weak lensing power spectrum and peak statistics.
Physical Review D. American Physical Society. https://doi.org/10.1103/physrevd.89.023515
chicago: Liu, Jia, Zoltán Haiman, Lam Hui, Jan M. Kratochvil, and Morgan May. “Impact
of Magnification and Size Bias on the Weak Lensing Power Spectrum and Peak Statistics.”
Physical Review D. American Physical Society, 2014. https://doi.org/10.1103/physrevd.89.023515.
ieee: J. Liu, Z. Haiman, L. Hui, J. M. Kratochvil, and M. May, “Impact of magnification
and size bias on the weak lensing power spectrum and peak statistics,” Physical
Review D, vol. 89, no. 2. American Physical Society, 2014.
ista: Liu J, Haiman Z, Hui L, Kratochvil JM, May M. 2014. Impact of magnification
and size bias on the weak lensing power spectrum and peak statistics. Physical
Review D. 89(2), 023515.
mla: Liu, Jia, et al. “Impact of Magnification and Size Bias on the Weak Lensing
Power Spectrum and Peak Statistics.” Physical Review D, vol. 89, no. 2,
023515, American Physical Society, 2014, doi:10.1103/physrevd.89.023515.
short: J. Liu, Z. Haiman, L. Hui, J.M. Kratochvil, M. May, Physical Review D 89
(2014).
date_created: 2024-09-06T08:49:04Z
date_published: 2014-01-21T00:00:00Z
date_updated: 2024-09-25T11:33:58Z
day: '21'
doi: 10.1103/physrevd.89.023515
extern: '1'
external_id:
arxiv:
- '1310.7517'
intvolume: ' 89'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.1310.7517'
month: '01'
oa: 1
oa_version: Preprint
publication: Physical Review D
publication_identifier:
issn:
- 1550-7998
- 1550-2368
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Impact of magnification and size bias on the weak lensing power spectrum and
peak statistics
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 89
year: '2014'
...
---
_id: '768'
abstract:
- lang: eng
text: '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.'
acknowledgement: "Dan Alistarh - This author was supported by the SNF Postdoctoral
Fellows Program, NSF grant CCF-1217921, DoE ASCR grant ER26116/DE-SC0008923, and
by grants from the Oracle and Intel corporations.\r\nJames Aspnes - Supported in
part by NSF grant CCF-0916389.\r\nMichael A. Bender - This research was supported
in part by NSF grants CCF 1114809, CCF 1217708, IIS 1247726, and IIS 1251137.\r\nRati
Gelashvili - This work was supported in part by NSF grants CCF-1217921, CCF-1301926,
DoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations.\r\nSeth
Gilbert - Supported by Singapore AcRF-2 MOE2011-T2-2-042.\r\n"
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: James
full_name: Aspnes, James
last_name: Aspnes
- first_name: Michael
full_name: Bender, Michael
last_name: Bender
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Seth
full_name: Gilbert, Seth
last_name: Gilbert
citation:
ama: 'Alistarh D-A, Aspnes J, Bender M, Gelashvili R, Gilbert S. Dynamic task allocation
in asynchronous shared memory. In: SIAM; 2014:416-435. doi:10.1137/1.9781611973402.31'
apa: 'Alistarh, D.-A., Aspnes, J., Bender, M., Gelashvili, R., & Gilbert, S.
(2014). Dynamic task allocation in asynchronous shared memory (pp. 416–435). Presented
at the SODA: Symposium on Discrete Algorithms, SIAM. https://doi.org/10.1137/1.9781611973402.31'
chicago: Alistarh, Dan-Adrian, James Aspnes, Michael Bender, Rati Gelashvili, and
Seth Gilbert. “Dynamic Task Allocation in Asynchronous Shared Memory,” 416–35.
SIAM, 2014. https://doi.org/10.1137/1.9781611973402.31.
ieee: 'D.-A. Alistarh, J. Aspnes, M. Bender, R. Gelashvili, and S. Gilbert, “Dynamic
task allocation in asynchronous shared memory,” presented at the SODA: Symposium
on Discrete Algorithms, 2014, pp. 416–435.'
ista: 'Alistarh D-A, Aspnes J, Bender M, Gelashvili R, Gilbert S. 2014. Dynamic
task allocation in asynchronous shared memory. SODA: Symposium on Discrete Algorithms,
416–435.'
mla: Alistarh, Dan-Adrian, et al. Dynamic Task Allocation in Asynchronous Shared
Memory. SIAM, 2014, pp. 416–35, doi:10.1137/1.9781611973402.31.
short: D.-A. Alistarh, J. Aspnes, M. Bender, R. Gelashvili, S. Gilbert, in:, SIAM,
2014, pp. 416–435.
conference:
name: 'SODA: Symposium on Discrete Algorithms'
date_created: 2018-12-11T11:48:24Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-23T13:13:52Z
day: '01'
doi: 10.1137/1.9781611973402.31
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 416 - 435
publication_status: published
publisher: SIAM
publist_id: '6886'
status: public
title: Dynamic task allocation in asynchronous shared memory
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '769'
abstract:
- lang: eng
text: '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.'
acknowledgement: "The work of J. Aspnes was supported in part by NSF grant CCF-0916389.
The work of S. Gilbert was\r\nsupported by Singapore AcRF-2 MOE 2011-T2-2-042.\r\nK.
Censor-Hillel is a Shalon Fellow. Part of this work was performed while K. Censor-Hillel
was a postdoc at\r\nMIT, supported by the Simons Postdoctoral Fellowship."
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: James
full_name: Aspnes, James
last_name: Aspnes
- first_name: Keren
full_name: Censor Hillel, Keren
last_name: Censor Hillel
- first_name: Seth
full_name: Gilbert, Seth
last_name: Gilbert
- first_name: Rachid
full_name: Guerraoui, Rachid
last_name: Guerraoui
citation:
ama: Alistarh D-A, Aspnes J, Censor Hillel K, Gilbert S, Guerraoui R. Tight bounds
for asynchronous renaming. Journal of the ACM. 2014;61(3). doi:10.1145/2597630
apa: Alistarh, D.-A., Aspnes, J., Censor Hillel, K., Gilbert, S., & Guerraoui,
R. (2014). Tight bounds for asynchronous renaming. Journal of the ACM.
ACM. https://doi.org/10.1145/2597630
chicago: Alistarh, Dan-Adrian, James Aspnes, Keren Censor Hillel, Seth Gilbert,
and Rachid Guerraoui. “Tight Bounds for Asynchronous Renaming.” Journal of
the ACM. ACM, 2014. https://doi.org/10.1145/2597630.
ieee: D.-A. Alistarh, J. Aspnes, K. Censor Hillel, S. Gilbert, and R. Guerraoui,
“Tight bounds for asynchronous renaming,” Journal of the ACM, vol. 61,
no. 3. ACM, 2014.
ista: Alistarh D-A, Aspnes J, Censor Hillel K, Gilbert S, Guerraoui R. 2014. Tight
bounds for asynchronous renaming. Journal of the ACM. 61(3).
mla: Alistarh, Dan-Adrian, et al. “Tight Bounds for Asynchronous Renaming.” Journal
of the ACM, vol. 61, no. 3, ACM, 2014, doi:10.1145/2597630.
short: D.-A. Alistarh, J. Aspnes, K. Censor Hillel, S. Gilbert, R. Guerraoui, Journal
of the ACM 61 (2014).
date_created: 2018-12-11T11:48:24Z
date_published: 2014-05-01T00:00:00Z
date_updated: 2023-02-23T13:14:09Z
day: '01'
doi: 10.1145/2597630
extern: '1'
intvolume: ' 61'
issue: '3'
language:
- iso: eng
month: '05'
oa_version: None
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '6887'
status: public
title: Tight bounds for asynchronous renaming
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2014'
...
---
_id: '7699'
article_processing_charge: No
article_type: original
author:
- first_name: Lora Beatrice Jaeger
full_name: Sweeney, Lora Beatrice Jaeger
id: 56BE8254-C4F0-11E9-8E45-0B23E6697425
last_name: Sweeney
orcid: 0000-0001-9242-5601
- first_name: Darcy B
full_name: Kelley, Darcy B
last_name: Kelley
citation:
ama: Sweeney LB, Kelley DB. Harnessing vocal patterns for social communication.
Current Opinion in Neurobiology. 2014;28(10):34-41. doi:10.1016/j.conb.2014.06.006
apa: Sweeney, L. B., & Kelley, D. B. (2014). Harnessing vocal patterns for social
communication. Current Opinion in Neurobiology. Elsevier. https://doi.org/10.1016/j.conb.2014.06.006
chicago: Sweeney, Lora B., and Darcy B Kelley. “Harnessing Vocal Patterns for Social
Communication.” Current Opinion in Neurobiology. Elsevier, 2014. https://doi.org/10.1016/j.conb.2014.06.006.
ieee: L. B. Sweeney and D. B. Kelley, “Harnessing vocal patterns for social communication,”
Current Opinion in Neurobiology, vol. 28, no. 10. Elsevier, pp. 34–41,
2014.
ista: Sweeney LB, Kelley DB. 2014. Harnessing vocal patterns for social communication.
Current Opinion in Neurobiology. 28(10), 34–41.
mla: Sweeney, Lora B., and Darcy B. Kelley. “Harnessing Vocal Patterns for Social
Communication.” Current Opinion in Neurobiology, vol. 28, no. 10, Elsevier,
2014, pp. 34–41, doi:10.1016/j.conb.2014.06.006.
short: L.B. Sweeney, D.B. Kelley, Current Opinion in Neurobiology 28 (2014) 34–41.
date_created: 2020-04-30T10:35:39Z
date_published: 2014-10-01T00:00:00Z
date_updated: 2024-01-31T10:14:08Z
day: '01'
doi: 10.1016/j.conb.2014.06.006
extern: '1'
intvolume: ' 28'
issue: '10'
language:
- iso: eng
month: '10'
oa_version: None
page: 34-41
publication: Current Opinion in Neurobiology
publication_identifier:
issn:
- 0959-4388
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: Harnessing vocal patterns for social communication
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 28
year: '2014'
...
---
_id: '770'
abstract:
- lang: eng
text: '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.'
acknowledgement: "Dan Alistarh - Part of this work was performed while the
\ author was a Postdoctoral\r\nAssociate a MIT CSAIL, supported in part by NSF
grant CCF-1217921,\r\nDoE ASCR grant ER26116/DE-SC0008923, and by grants from the
Oracle\r\nand Intel corporations.\r\nPatrick Eugester - Supported in part by DARPA
grant N11AP20014 and NSF grant CNS-\r\n1117065.\r\nMaurice Herlihy - Supported by
NSF grant 1301924.\r\nNir Shavit - Supported in part by NSF grants CCF-1217921 and
CCF-1301926, DoE\r\nASCR grant ER26116/DE-SC0008923, and by grants from the Oracle
and\r\nIntel corporations."
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Patrick
full_name: Eugster, Patrick
last_name: Eugster
- first_name: Maurice
full_name: Herlihy, Maurice
last_name: Herlihy
- first_name: Alexander
full_name: Matveev, Alexander
last_name: Matveev
- first_name: Nir
full_name: Shavit, Nir
last_name: Shavit
citation:
ama: 'Alistarh D-A, Eugster P, Herlihy M, Matveev A, Shavit N. StackTrack: An automated
transactional approach to concurrent memory reclamation. In: ACM; 2014. doi:10.1145/2592798.2592808'
apa: 'Alistarh, D.-A., Eugster, P., Herlihy, M., Matveev, A., & Shavit, N. (2014).
StackTrack: An automated transactional approach to concurrent memory reclamation.
Presented at the EuroSys: European Conference on Computer Systems, ACM. https://doi.org/10.1145/2592798.2592808'
chicago: 'Alistarh, Dan-Adrian, Patrick Eugster, Maurice Herlihy, Alexander Matveev,
and Nir Shavit. “StackTrack: An Automated Transactional Approach to Concurrent
Memory Reclamation.” ACM, 2014. https://doi.org/10.1145/2592798.2592808.'
ieee: 'D.-A. Alistarh, P. Eugster, M. Herlihy, A. Matveev, and N. Shavit, “StackTrack:
An automated transactional approach to concurrent memory reclamation,” presented
at the EuroSys: European Conference on Computer Systems, 2014.'
ista: 'Alistarh D-A, Eugster P, Herlihy M, Matveev A, Shavit N. 2014. StackTrack:
An automated transactional approach to concurrent memory reclamation. EuroSys:
European Conference on Computer Systems.'
mla: 'Alistarh, Dan-Adrian, et al. StackTrack: An Automated Transactional Approach
to Concurrent Memory Reclamation. ACM, 2014, doi:10.1145/2592798.2592808.'
short: D.-A. Alistarh, P. Eugster, M. Herlihy, A. Matveev, N. Shavit, in:, ACM,
2014.
conference:
name: 'EuroSys: European Conference on Computer Systems'
date_created: 2018-12-11T11:48:24Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-23T13:14:25Z
day: '01'
doi: 10.1145/2592798.2592808
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
publication_status: published
publisher: ACM
publist_id: '6888'
status: public
title: 'StackTrack: An automated transactional approach to concurrent memory reclamation'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '771'
abstract:
- lang: eng
text: '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.'
acknowledgement: "Dan Alistarh was partially supported by the SNF Post-\r\ndoctoral
Fellows Program, NSF grant CCF-1217921, DoE\r\nASCR grant ER26116/DE-SC0008923,
and by grants from\r\nthe Oracle and Intel corporations.\r\nOksana Denysyuk and
Lu ́ıs Rodrigues were partially supported by Funda ̧c ̃ao para a Ciˆencia e Tecnologia
(FCT) via\r\nthe project PEPITA (PTDC/EEI-SCR/2776/2012) and via\r\nthe INESC-ID
multi-annual funding through the PIDDAC\r\nProgram fund grant, under project PEst-OE/EEI/LA0021/\r\n2013.\r\nNir
Shavit was supported in part by NSF grants CCF-1217921 and CCF-1301926, DoE ASCR
grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations."
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Oksana
full_name: Denysyuk, Oksana
last_name: Denysyuk
- first_name: Luís
full_name: Rodrígues, Luís
last_name: Rodrígues
- first_name: Nir
full_name: Shavit, Nir
last_name: Shavit
citation:
ama: 'Alistarh D-A, Denysyuk O, Rodrígues L, Shavit N. Balls-into-Leaves: Sub-logarithmic
renaming in synchronous message-passing systems. In: ACM; 2014:232-241. doi:10.1145/2611462.2611499'
apa: 'Alistarh, D.-A., Denysyuk, O., Rodrígues, L., & Shavit, N. (2014). Balls-into-Leaves:
Sub-logarithmic renaming in synchronous message-passing systems (pp. 232–241).
Presented at the PODC: Principles of Distributed Computing, ACM. https://doi.org/10.1145/2611462.2611499'
chicago: 'Alistarh, Dan-Adrian, Oksana Denysyuk, Luís Rodrígues, and Nir Shavit.
“Balls-into-Leaves: Sub-Logarithmic Renaming in Synchronous Message-Passing Systems,”
232–41. ACM, 2014. https://doi.org/10.1145/2611462.2611499.'
ieee: 'D.-A. Alistarh, O. Denysyuk, L. Rodrígues, and N. Shavit, “Balls-into-Leaves:
Sub-logarithmic renaming in synchronous message-passing systems,” presented at
the PODC: Principles of Distributed Computing, 2014, pp. 232–241.'
ista: 'Alistarh D-A, Denysyuk O, Rodrígues L, Shavit N. 2014. Balls-into-Leaves:
Sub-logarithmic renaming in synchronous message-passing systems. PODC: Principles
of Distributed Computing, 232–241.'
mla: 'Alistarh, Dan-Adrian, et al. Balls-into-Leaves: Sub-Logarithmic Renaming
in Synchronous Message-Passing Systems. ACM, 2014, pp. 232–41, doi:10.1145/2611462.2611499.'
short: D.-A. Alistarh, O. Denysyuk, L. Rodrígues, N. Shavit, in:, ACM, 2014, pp.
232–241.
conference:
name: 'PODC: Principles of Distributed Computing'
date_created: 2018-12-11T11:48:25Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-23T13:14:49Z
day: '01'
doi: 10.1145/2611462.2611499
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 232 - 241
publication_status: published
publisher: ACM
publist_id: '6884'
status: public
title: 'Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing
systems'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '772'
abstract:
- lang: eng
text: 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.
acknowledgement: "Dan Alistarh - Part of this work was performed while the author
was a Postdoctoral Associate at MIT CSAIL, where he was supported by SNF\r\nPostdoctoral
Fellows Program, NSF grant CCF-1217921, DoE\r\nASCR grant ER26116/DE-SC0008923,
and by grants from the Oracle and Intel corporations.\r\nKeron Censor-Hillel - Shalon
Fellow\r\nNir Shavit - This work was supported in part by NSF grants CCF-1217921
and\r\nCCF-1301926, DoE ASCR grant ER26116/DE-SC0008923, and\r\nby grants from the
Oracle and Intel corporations."
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Keren
full_name: Censor Hillel, Keren
last_name: Censor Hillel
- first_name: Nir
full_name: Shavit, Nir
last_name: Shavit
citation:
ama: 'Alistarh D-A, Censor Hillel K, Shavit N. Are lock-free concurrent algorithms
practically wait-free? In: ACM; 2014:714-723. doi:10.1145/2591796.2591836'
apa: 'Alistarh, D.-A., Censor Hillel, K., & Shavit, N. (2014). Are lock-free
concurrent algorithms practically wait-free? (pp. 714–723). Presented at the STOC:
Symposium on Theory of Computing, ACM. https://doi.org/10.1145/2591796.2591836'
chicago: Alistarh, Dan-Adrian, Keren Censor Hillel, and Nir Shavit. “Are Lock-Free
Concurrent Algorithms Practically Wait-Free?,” 714–23. ACM, 2014. https://doi.org/10.1145/2591796.2591836.
ieee: 'D.-A. Alistarh, K. Censor Hillel, and N. Shavit, “Are lock-free concurrent
algorithms practically wait-free?,” presented at the STOC: Symposium on Theory
of Computing, 2014, pp. 714–723.'
ista: 'Alistarh D-A, Censor Hillel K, Shavit N. 2014. Are lock-free concurrent algorithms
practically wait-free? STOC: Symposium on Theory of Computing, 714–723.'
mla: Alistarh, Dan-Adrian, et al. Are Lock-Free Concurrent Algorithms Practically
Wait-Free? ACM, 2014, pp. 714–23, doi:10.1145/2591796.2591836.
short: D.-A. Alistarh, K. Censor Hillel, N. Shavit, in:, ACM, 2014, pp. 714–723.
conference:
name: 'STOC: Symposium on Theory of Computing'
date_created: 2018-12-11T11:48:25Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-23T13:15:13Z
day: '01'
doi: 10.1145/2591796.2591836
extern: '1'
external_id:
arxiv:
- '1311.3200'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1311.3200
month: '01'
oa: 1
oa_version: Preprint
page: 714 - 723
publication_status: published
publisher: ACM
publist_id: '6885'
status: public
title: Are lock-free concurrent algorithms practically wait-free?
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '773'
abstract:
- lang: eng
text: "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.\r\n\r\nWe
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.\r\n\r\nOur
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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: James
full_name: Aspnes, James
last_name: Aspnes
- first_name: Valerie
full_name: King, Valerie
last_name: King
- first_name: Jared
full_name: Saia, Jared
last_name: Saia
citation:
ama: 'Alistarh D-A, Aspnes J, King V, Saia J. Communication-efficient randomized
consensus. In: Kuhn F, ed. Vol 8784. Springer; 2014:61-75. doi:10.1007/978-3-662-45174-8_5'
apa: 'Alistarh, D.-A., Aspnes, J., King, V., & Saia, J. (2014). Communication-efficient
randomized consensus. In F. Kuhn (Ed.) (Vol. 8784, pp. 61–75). Presented at the
DISC: Distributed Computing, Austin, USA: Springer. https://doi.org/10.1007/978-3-662-45174-8_5'
chicago: Alistarh, Dan-Adrian, James Aspnes, Valerie King, and Jared Saia. “Communication-Efficient
Randomized Consensus.” edited by Fabian Kuhn, 8784:61–75. Springer, 2014. https://doi.org/10.1007/978-3-662-45174-8_5.
ieee: 'D.-A. Alistarh, J. Aspnes, V. King, and J. Saia, “Communication-efficient
randomized consensus,” presented at the DISC: Distributed Computing, Austin, USA,
2014, vol. 8784, pp. 61–75.'
ista: 'Alistarh D-A, Aspnes J, King V, Saia J. 2014. Communication-efficient randomized
consensus. DISC: Distributed Computing, LNCS, vol. 8784, 61–75.'
mla: Alistarh, Dan-Adrian, et al. Communication-Efficient Randomized Consensus.
Edited by Fabian Kuhn, vol. 8784, Springer, 2014, pp. 61–75, doi:10.1007/978-3-662-45174-8_5.
short: D.-A. Alistarh, J. Aspnes, V. King, J. Saia, in:, F. Kuhn (Ed.), Springer,
2014, pp. 61–75.
conference:
end_date: 2014-10-15
location: Austin, USA
name: 'DISC: Distributed Computing'
start_date: 2014-10-12
date_created: 2018-12-11T11:48:25Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-23T13:15:36Z
day: '01'
doi: 10.1007/978-3-662-45174-8_5
editor:
- first_name: Fabian
full_name: Kuhn, Fabian
last_name: Kuhn
extern: '1'
intvolume: ' 8784'
language:
- iso: eng
month: '01'
oa_version: None
page: 61 - 75
publication_status: published
publisher: Springer
publist_id: '6881'
status: public
title: Communication-efficient randomized consensus
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8784
year: '2014'
...
---
_id: '774'
abstract:
- lang: eng
text: 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.
acknowledgement: "Dan Alistarh - Part of this work was performed while the
\ author was a\r\nPostdoctoral Associate at MIT CSAIL, where he was supported
\ by SNF Postdoctoral Fellows Program, NSF grant\r\nCCF-1217921, DoE ASCR
grant ER26116/DE-SC0008923,\r\nand by grants from the Oracle and Intel corporations.\r\nKeren
Censor-Hille - Shalon Fellow\r\nNir Shavit - This work was supported in part
\ by NSF grants CCF-1217921 and CCF-1301926, DoE ASCR grant ER26116/DE-\r\nSC0008923,
and by grants from the Oracle and Intel corporations."
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Keren
full_name: Censor Hille, Keren
last_name: Censor Hille
- first_name: Nir
full_name: Shavit, Nir
last_name: Shavit
citation:
ama: 'Alistarh D-A, Censor Hille K, Shavit N. Brief announcement: Are lock-free
concurrent algorithms practically wait-free? In: ACM; 2014:50-52. doi:10.1145/2611462.2611502'
apa: 'Alistarh, D.-A., Censor Hille, K., & Shavit, N. (2014). Brief announcement:
Are lock-free concurrent algorithms practically wait-free? (pp. 50–52). Presented
at the PODC: Principles of Distributed Computing, ACM. https://doi.org/10.1145/2611462.2611502'
chicago: 'Alistarh, Dan-Adrian, Keren Censor Hille, and Nir Shavit. “Brief Announcement:
Are Lock-Free Concurrent Algorithms Practically Wait-Free?,” 50–52. ACM, 2014.
https://doi.org/10.1145/2611462.2611502.'
ieee: 'D.-A. Alistarh, K. Censor Hille, and N. Shavit, “Brief announcement: Are
lock-free concurrent algorithms practically wait-free?,” presented at the PODC:
Principles of Distributed Computing, 2014, pp. 50–52.'
ista: 'Alistarh D-A, Censor Hille K, Shavit N. 2014. Brief announcement: Are lock-free
concurrent algorithms practically wait-free? PODC: Principles of Distributed Computing,
50–52.'
mla: 'Alistarh, Dan-Adrian, et al. Brief Announcement: Are Lock-Free Concurrent
Algorithms Practically Wait-Free? ACM, 2014, pp. 50–52, doi:10.1145/2611462.2611502.'
short: D.-A. Alistarh, K. Censor Hille, N. Shavit, in:, ACM, 2014, pp. 50–52.
conference:
name: 'PODC: Principles of Distributed Computing'
date_created: 2018-12-11T11:48:26Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-23T13:15:54Z
day: '01'
doi: 10.1145/2611462.2611502
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 50 - 52
publication_status: published
publisher: ACM
publist_id: '6882'
status: public
title: 'Brief announcement: Are lock-free concurrent algorithms practically wait-free?'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '7743'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
author:
- first_name: Matthew Richard
full_name: Robinson, Matthew Richard
id: E5D42276-F5DA-11E9-8E24-6303E6697425
last_name: Robinson
orcid: 0000-0001-8982-8813
- first_name: Anna
full_name: Qvarnström, Anna
last_name: Qvarnström
citation:
ama: 'Robinson MR, Qvarnström A. Influence of the environment on the genetic architecture
of traits involved in sexual selection within wild populations. In: Hunt J, Hosken
D, eds. Genotype-by-Environment Interactions and Sexual Selection. Chichester,
UK: Wiley; 2014:137-168. doi:10.1002/9781118912591.ch6'
apa: 'Robinson, M. R., & Qvarnström, A. (2014). Influence of the environment
on the genetic architecture of traits involved in sexual selection within wild
populations. In J. Hunt & D. Hosken (Eds.), Genotype-by-Environment Interactions
and Sexual Selection (pp. 137–168). Chichester, UK: Wiley. https://doi.org/10.1002/9781118912591.ch6'
chicago: 'Robinson, Matthew Richard, and Anna Qvarnström. “Influence of the Environment
on the Genetic Architecture of Traits Involved in Sexual Selection within Wild
Populations.” In Genotype-by-Environment Interactions and Sexual Selection,
edited by John Hunt and David Hosken, 137–68. Chichester, UK: Wiley, 2014. https://doi.org/10.1002/9781118912591.ch6.'
ieee: 'M. R. Robinson and A. Qvarnström, “Influence of the environment on the genetic
architecture of traits involved in sexual selection within wild populations,”
in Genotype-by-Environment Interactions and Sexual Selection, J. Hunt and
D. Hosken, Eds. Chichester, UK: Wiley, 2014, pp. 137–168.'
ista: 'Robinson MR, Qvarnström A. 2014.Influence of the environment on the genetic
architecture of traits involved in sexual selection within wild populations. In:
Genotype-by-Environment Interactions and Sexual Selection. , 137–168.'
mla: Robinson, Matthew Richard, and Anna Qvarnström. “Influence of the Environment
on the Genetic Architecture of Traits Involved in Sexual Selection within Wild
Populations.” Genotype-by-Environment Interactions and Sexual Selection,
edited by John Hunt and David Hosken, Wiley, 2014, pp. 137–68, doi:10.1002/9781118912591.ch6.
short: M.R. Robinson, A. Qvarnström, in:, J. Hunt, D. Hosken (Eds.), Genotype-by-Environment
Interactions and Sexual Selection, Wiley, Chichester, UK, 2014, pp. 137–168.
date_created: 2020-04-30T10:58:39Z
date_published: 2014-08-29T00:00:00Z
date_updated: 2021-01-12T08:15:13Z
day: '29'
doi: 10.1002/9781118912591.ch6
editor:
- first_name: John
full_name: Hunt, John
last_name: Hunt
- first_name: David
full_name: Hosken, David
last_name: Hosken
extern: '1'
language:
- iso: eng
month: '08'
oa_version: None
page: 137-168
place: Chichester, UK
publication: Genotype-by-Environment Interactions and Sexual Selection
publication_identifier:
eisbn:
- '9781118912591'
isbn:
- '9780470671795'
publication_status: published
publisher: Wiley
quality_controlled: '1'
status: public
title: Influence of the environment on the genetic architecture of traits involved
in sexual selection within wild populations
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...