---
_id: '6676'
abstract:
- lang: eng
text: "It is impossible to deterministically solve wait-free consensus in an asynchronous
system. The classic proof uses a valency argument, which constructs an infinite
execution by repeatedly extending a finite execution. We introduce extension-based
proofs, a class of impossibility proofs that are modelled as an interaction between
a prover and a protocol and that include valency arguments.\r\n\r\nUsing proofs
based on combinatorial topology, it has been shown that it is impossible to deterministically
solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However,
it was unknown whether proofs based on simpler techniques were possible. We show
that this impossibility result cannot be obtained by an extension-based proof
and, hence, extension-based proofs are limited in power."
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: James
full_name: Aspnes, James
last_name: Aspnes
- first_name: Faith
full_name: Ellen, Faith
last_name: Ellen
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Leqi
full_name: Zhu, Leqi
last_name: Zhu
citation:
ama: 'Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based
proofs fail. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing. ACM Press; 2019:986-996. doi:10.1145/3313276.3316407'
apa: 'Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2019).
Why extension-based proofs fail. In Proceedings of the 51st Annual ACM SIGACT
Symposium on Theory of Computing (pp. 986–996). Phoenix, AZ, United States:
ACM Press. https://doi.org/10.1145/3313276.3316407'
chicago: Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi
Zhu. “Why Extension-Based Proofs Fail.” In Proceedings of the 51st Annual ACM
SIGACT Symposium on Theory of Computing, 986–96. ACM Press, 2019. https://doi.org/10.1145/3313276.3316407.
ieee: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based
proofs fail,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing, Phoenix, AZ, United States, 2019, pp. 986–996.
ista: 'Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2019. Why extension-based
proofs fail. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of
Computing. STOC: Symposium on Theory of Computing, 986–996.'
mla: Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” Proceedings
of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM Press,
2019, pp. 986–96, doi:10.1145/3313276.3316407.
short: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings
of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM Press, 2019,
pp. 986–996.
conference:
end_date: 2019-06-26
location: Phoenix, AZ, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2019-06-23
date_created: 2019-07-24T09:13:05Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-12-13T12:28:28Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3313276.3316407
external_id:
arxiv:
- '1811.01421'
isi:
- '000523199100089'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1811.01421
month: '06'
oa: 1
oa_version: Preprint
page: 986-996
publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
isbn:
- '9781450367059'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
related_material:
record:
- id: '14364'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Why extension-based proofs fail
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...
---
_id: '6759'
abstract:
- lang: eng
text: "We consider the graph class Grounded-L corresponding to graphs that admit
an intersection representation by L-shaped curves, where additionally the topmost
points of each curve are assumed to belong to a common horizontal line. We prove
that Grounded-L graphs admit an equivalent characterisation in terms of vertex
ordering with forbidden patterns. \r\nWe also compare this class to related intersection
classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max
point-tolerance graphs), or the outer-1-string graphs. We give constructions showing
that these classes are all distinct and satisfy only trivial or previously known
inclusions."
article_number: P3.17
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vít
full_name: Jelínek, Vít
last_name: Jelínek
- first_name: Martin
full_name: Töpfer, Martin
id: 4B865388-F248-11E8-B48F-1D18A9856A87
last_name: Töpfer
citation:
ama: Jelínek V, Töpfer M. On grounded L-graphs and their relatives. Electronic
Journal of Combinatorics. 2019;26(3). doi:10.37236/8096
apa: Jelínek, V., & Töpfer, M. (2019). On grounded L-graphs and their relatives.
Electronic Journal of Combinatorics. Electronic Journal of Combinatorics.
https://doi.org/10.37236/8096
chicago: Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.”
Electronic Journal of Combinatorics. Electronic Journal of Combinatorics,
2019. https://doi.org/10.37236/8096.
ieee: V. Jelínek and M. Töpfer, “On grounded L-graphs and their relatives,” Electronic
Journal of Combinatorics, vol. 26, no. 3. Electronic Journal of Combinatorics,
2019.
ista: Jelínek V, Töpfer M. 2019. On grounded L-graphs and their relatives. Electronic
Journal of Combinatorics. 26(3), P3.17.
mla: Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.”
Electronic Journal of Combinatorics, vol. 26, no. 3, P3.17, Electronic
Journal of Combinatorics, 2019, doi:10.37236/8096.
short: V. Jelínek, M. Töpfer, Electronic Journal of Combinatorics 26 (2019).
date_created: 2019-08-04T21:59:20Z
date_published: 2019-07-19T00:00:00Z
date_updated: 2022-03-18T12:32:02Z
day: '19'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.37236/8096
ec_funded: 1
external_id:
arxiv:
- '1808.04148'
file:
- access_level: open_access
checksum: 20fc366fc6683ef0b074a019b73a663a
content_type: application/pdf
creator: dernst
date_created: 2019-08-05T06:46:55Z
date_updated: 2020-07-14T12:47:39Z
file_id: '6764'
file_name: 2019_eJourCombinatorics_Jelinek.pdf
file_size: 533697
relation: main_file
file_date_updated: 2020-07-14T12:47:39Z
has_accepted_license: '1'
intvolume: ' 26'
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: Electronic Journal of Combinatorics
publication_identifier:
eissn:
- '10778926'
publication_status: published
publisher: Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: On grounded L-graphs and their relatives
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 26
year: '2019'
...
---
_id: '6931'
abstract:
- lang: eng
text: "Consider a distributed system with n processors out of which f can be Byzantine
faulty. In the\r\napproximate agreement task, each processor i receives an input
value xi and has to decide on an\r\noutput value yi such that\r\n1. the output
values are in the convex hull of the non-faulty processors’ input values,\r\n2.
the output values are within distance d of each other.\r\n\r\n\r\nClassically,
the values are assumed to be from an m-dimensional Euclidean space, where m ≥
1.\r\nIn this work, we study the task in a discrete setting, where input values
with some structure\r\nexpressible as a graph. Namely, the input values are vertices
of a finite graph G and the goal is to\r\noutput vertices that are within distance
d of each other in G, but still remain in the graph-induced\r\nconvex hull of
the input values. For d = 0, the task reduces to consensus and cannot be solved
with\r\na deterministic algorithm in an asynchronous system even with a single
crash fault. For any d ≥ 1,\r\nwe show that the task is solvable in asynchronous
systems when G is chordal and n > (ω + 1)f,\r\nwhere ω is the clique number of
G. In addition, we give the first Byzantine-tolerant algorithm for a\r\nvariant
of lattice agreement. For synchronous systems, we show tight resilience bounds
for the exact\r\nvariants of these and related tasks over a large class of combinatorial
structures."
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Thomas
full_name: Nowak, Thomas
last_name: Nowak
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Nowak T, Rybicki J. Byzantine approximate agreement on graphs. In: 33rd
International Symposium on Distributed Computing. Vol 146. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2019:29:1--29:17. doi:10.4230/LIPICS.DISC.2019.29'
apa: 'Nowak, T., & Rybicki, J. (2019). Byzantine approximate agreement on graphs.
In 33rd International Symposium on Distributed Computing (Vol. 146, p.
29:1--29:17). Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICS.DISC.2019.29'
chicago: Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.”
In 33rd International Symposium on Distributed Computing, 146:29:1--29:17.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.DISC.2019.29.
ieee: T. Nowak and J. Rybicki, “Byzantine approximate agreement on graphs,” in 33rd
International Symposium on Distributed Computing, Budapest, Hungary, 2019,
vol. 146, p. 29:1--29:17.
ista: 'Nowak T, Rybicki J. 2019. Byzantine approximate agreement on graphs. 33rd
International Symposium on Distributed Computing. DISC: International Symposium
on Distributed Computing, LIPIcs, vol. 146, 29:1--29:17.'
mla: Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.”
33rd International Symposium on Distributed Computing, vol. 146, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17, doi:10.4230/LIPICS.DISC.2019.29.
short: T. Nowak, J. Rybicki, in:, 33rd International Symposium on Distributed Computing,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17.
conference:
end_date: 2019-10-18
location: Budapest, Hungary
name: 'DISC: International Symposium on Distributed Computing'
start_date: 2019-10-14
date_created: 2019-10-08T12:41:38Z
date_published: 2019-01-01T00:00:00Z
date_updated: 2021-01-12T08:09:38Z
ddc:
- '004'
department:
- _id: DaAl
doi: 10.4230/LIPICS.DISC.2019.29
ec_funded: 1
external_id:
arxiv:
- '1908.02743'
file:
- access_level: open_access
checksum: 2d2202f90c6ac991e50876451627c4b5
content_type: application/pdf
creator: jrybicki
date_created: 2019-10-08T12:47:19Z
date_updated: 2020-07-14T12:47:44Z
file_id: '6934'
file_name: LIPIcs-DISC-2019-29.pdf
file_size: 639378
relation: main_file
file_date_updated: 2020-07-14T12:47:44Z
has_accepted_license: '1'
intvolume: ' 146'
keyword:
- consensus
- approximate agreement
- Byzantine faults
- chordal graphs
- lattice agreement
language:
- iso: eng
oa: 1
oa_version: Published Version
page: 29:1--29:17
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 33rd International Symposium on Distributed Computing
publication_identifier:
eisbn:
- 978-3-95977-126-9
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Byzantine approximate agreement on graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 146
year: '2019'
...
---
_id: '6933'
abstract:
- lang: eng
text: "We design fast deterministic algorithms for distance computation in the CONGESTED
CLIQUE model. Our key contributions include:\r\n\r\n - A (2+ε)-approximation for
all-pairs shortest paths problem in O(log²n / ε) rounds on unweighted undirected
graphs. With a small additional additive factor, this also applies for weighted
graphs. This is the first sub-polynomial constant-factor approximation for APSP
in this model.\r\n - A (1+ε)-approximation for multi-source shortest paths problem
from O(√n) sources in O(log² n / ε) rounds on weighted undirected graphs. This
is the first sub-polynomial algorithm obtaining this approximation for a set of
sources of polynomial size.\r\n\r\nOur main techniques are new distance tools
that are obtained via improved algorithms for sparse matrix multiplication, which
we leverage to construct efficient hopsets and shortest paths. Furthermore, our
techniques extend to additional distance problems for which we improve upon the
state-of-the-art, including diameter approximation, and an exact single-source
shortest paths algorithm for weighted undirected graphs in Õ(n^{1/6}) rounds."
article_processing_charge: No
arxiv: 1
author:
- first_name: Keren
full_name: Censor-Hillel, Keren
last_name: Censor-Hillel
- first_name: Michal
full_name: Dory, Michal
last_name: Dory
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
- first_name: Dean
full_name: Leitersdorf, Dean
last_name: Leitersdorf
citation:
ama: 'Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest
paths in the congested clique. In: Proceedings of the 2019 ACM Symposium on
Principles of Distributed Computin. ACM; 2019:74-83. doi:10.1145/3293611.3331633'
apa: 'Censor-Hillel, K., Dory, M., Korhonen, J., & Leitersdorf, D. (2019). Fast
approximate shortest paths in the congested clique. In Proceedings of the 2019
ACM Symposium on Principles of Distributed Computin (pp. 74–83). Toronto,
ON, Canada: ACM. https://doi.org/10.1145/3293611.3331633'
chicago: Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf.
“Fast Approximate Shortest Paths in the Congested Clique.” In Proceedings of
the 2019 ACM Symposium on Principles of Distributed Computin, 74–83. ACM,
2019. https://doi.org/10.1145/3293611.3331633.
ieee: K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate
shortest paths in the congested clique,” in Proceedings of the 2019 ACM Symposium
on Principles of Distributed Computin, Toronto, ON, Canada, 2019, pp. 74–83.
ista: 'Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2019. Fast approximate
shortest paths in the congested clique. Proceedings of the 2019 ACM Symposium
on Principles of Distributed Computin. PODC: Symposium on Principles of Distributed
Computing, 74–83.'
mla: Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested
Clique.” Proceedings of the 2019 ACM Symposium on Principles of Distributed
Computin, ACM, 2019, pp. 74–83, doi:10.1145/3293611.3331633.
short: K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, in:, Proceedings
of the 2019 ACM Symposium on Principles of Distributed Computin, ACM, 2019, pp.
74–83.
conference:
end_date: 2019-08-02
location: Toronto, ON, Canada
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2019-07-29
date_created: 2019-10-08T12:48:42Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2024-03-07T14:43:38Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3293611.3331633
external_id:
arxiv:
- '1903.05956'
isi:
- '000570442000011'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1903.05956
month: '08'
oa: 1
oa_version: Preprint
page: 74-83
publication: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin
publication_identifier:
isbn:
- '9781450362177'
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
record:
- id: '7939'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Fast approximate shortest paths in the congested clique
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...
---
_id: '6935'
abstract:
- lang: eng
text: "This paper investigates the power of preprocessing in the CONGEST model.
Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to
study the application of distributed algorithms in Software-Defined Networks (SDNs).
In this paper, we show that a large class of lower bounds in the CONGEST model
still hold in the SUPPORTED model, highlighting the robustness of these bounds.
This also raises the question how much does\r\npreprocessing help in the CONGEST
model."
article_processing_charge: No
arxiv: 1
author:
- first_name: Klaus-Tycho
full_name: Foerster, Klaus-Tycho
last_name: Foerster
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Foerster K-T, Korhonen J, Rybicki J, Schmid S. Does preprocessing help under
congestion? In: Proceedings of the 2019 ACM Symposium on Principles of Distributed
Computing. ACM; 2019:259-261. doi:10.1145/3293611.3331581'
apa: 'Foerster, K.-T., Korhonen, J., Rybicki, J., & Schmid, S. (2019). Does
preprocessing help under congestion? In Proceedings of the 2019 ACM Symposium
on Principles of Distributed Computing (pp. 259–261). Toronto, ON, Canada:
ACM. https://doi.org/10.1145/3293611.3331581'
chicago: Foerster, Klaus-Tycho, Janne Korhonen, Joel Rybicki, and Stefan Schmid.
“Does Preprocessing Help under Congestion?” In Proceedings of the 2019 ACM
Symposium on Principles of Distributed Computing, 259–61. ACM, 2019. https://doi.org/10.1145/3293611.3331581.
ieee: K.-T. Foerster, J. Korhonen, J. Rybicki, and S. Schmid, “Does preprocessing
help under congestion?,” in Proceedings of the 2019 ACM Symposium on Principles
of Distributed Computing, Toronto, ON, Canada, 2019, pp. 259–261.
ista: 'Foerster K-T, Korhonen J, Rybicki J, Schmid S. 2019. Does preprocessing help
under congestion? Proceedings of the 2019 ACM Symposium on Principles of Distributed
Computing. PODC: Symposium on Principles of Distributed Computing, 259–261.'
mla: Foerster, Klaus-Tycho, et al. “Does Preprocessing Help under Congestion?” Proceedings
of the 2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019,
pp. 259–61, doi:10.1145/3293611.3331581.
short: K.-T. Foerster, J. Korhonen, J. Rybicki, S. Schmid, in:, Proceedings of the
2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019, pp. 259–261.
conference:
end_date: 2019-08-02
location: Toronto, ON, Canada
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2019-07-29
date_created: 2019-10-08T12:57:14Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-09-08T11:37:22Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3293611.3331581
ec_funded: 1
external_id:
arxiv:
- '1905.03012'
isi:
- '000570442000037'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1905.03012
month: '08'
oa: 1
oa_version: Preprint
page: 259-261
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- '9781450362177'
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: Does preprocessing help under congestion?
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...
---
_id: '6936'
abstract:
- lang: eng
text: "A key challenge for community ecology is to understand to what extent observational
data can be used to infer the underlying community assembly processes. As different
processes can lead to similar or even identical patterns, statistical analyses
of non‐manipulative observational data never yield undisputable causal inference
on the underlying processes. Still, most empirical studies in community ecology
are based on observational data, and hence understanding under which circumstances
such data can shed light on assembly processes is a central concern for community
ecologists. We simulated a spatial agent‐based model that generates variation
in metacommunity dynamics across multiple axes, including the four classic metacommunity
paradigms as special cases. We further simulated a virtual ecologist who analysed
snapshot data sampled from the simulations using eighteen output metrics derived
from beta‐diversity and habitat variation indices, variation partitioning and
joint species distribution modelling. Our results indicated two main axes of variation
in the output metrics. The first axis of variation described whether the landscape
has patchy or continuous variation, and thus was essentially independent of the
properties of the species community. The second axis of variation related to the
level of predictability of the metacommunity. The most predictable communities
were niche‐based metacommunities inhabiting static landscapes with marked environmental
heterogeneity, such as metacommunities following the species sorting paradigm
or the mass effects paradigm. The most unpredictable communities were neutral‐based
metacommunities inhabiting dynamics landscapes with little spatial heterogeneity,
such as metacommunities following the neutral or patch sorting paradigms. The
output metrics from joint species distribution modelling yielded generally the
highest resolution to disentangle among the simulated scenarios. Yet, the different
types of statistical approaches utilized in this study carried complementary information,
and thus our results suggest that the most comprehensive evaluation of metacommunity
structure can be obtained by combining them.\r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Otso
full_name: Ovaskainen, Otso
last_name: Ovaskainen
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Nerea
full_name: Abrego, Nerea
last_name: Abrego
citation:
ama: Ovaskainen O, Rybicki J, Abrego N. What can observational data reveal about
metacommunity processes? Ecography. 2019;42(11):1877-1886. doi:10.1111/ecog.04444
apa: Ovaskainen, O., Rybicki, J., & Abrego, N. (2019). What can observational
data reveal about metacommunity processes? Ecography. Wiley. https://doi.org/10.1111/ecog.04444
chicago: Ovaskainen, Otso, Joel Rybicki, and Nerea Abrego. “What Can Observational
Data Reveal about Metacommunity Processes?” Ecography. Wiley, 2019. https://doi.org/10.1111/ecog.04444.
ieee: O. Ovaskainen, J. Rybicki, and N. Abrego, “What can observational data reveal
about metacommunity processes?,” Ecography, vol. 42, no. 11. Wiley, pp.
1877–1886, 2019.
ista: Ovaskainen O, Rybicki J, Abrego N. 2019. What can observational data reveal
about metacommunity processes? Ecography. 42(11), 1877–1886.
mla: Ovaskainen, Otso, et al. “What Can Observational Data Reveal about Metacommunity
Processes?” Ecography, vol. 42, no. 11, Wiley, 2019, pp. 1877–86, doi:10.1111/ecog.04444.
short: O. Ovaskainen, J. Rybicki, N. Abrego, Ecography 42 (2019) 1877–1886.
date_created: 2019-10-08T13:01:24Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2023-08-30T06:57:25Z
day: '01'
ddc:
- '577'
department:
- _id: DaAl
doi: 10.1111/ecog.04444
ec_funded: 1
external_id:
isi:
- '000486348700001'
file:
- access_level: open_access
checksum: 6c9fbbd5ea8ce10ae93e55ad560a7bf9
content_type: application/pdf
creator: jrybicki
date_created: 2019-10-08T13:07:44Z
date_updated: 2020-07-14T12:47:45Z
file_id: '6937'
file_name: ecog.04444.pdf
file_size: 1682718
relation: main_file
file_date_updated: 2020-07-14T12:47:45Z
has_accepted_license: '1'
intvolume: ' 42'
isi: 1
issue: '11'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 1877-1886
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Ecography
publication_identifier:
eissn:
- 1600-0587
issn:
- 0906-7590
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: What can observational data reveal about metacommunity processes?
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 42
year: '2019'
...
---
_id: '6972'
abstract:
- lang: eng
text: 'We give fault-tolerant algorithms for establishing synchrony in distributed
systems in which each of thennodes has its own clock. Our algorithms operate in
a very strong fault model: we require self-stabilisation, i.e.,the initial state
of the system may be arbitrary, and there can be up to fJournal of the ACM. 2019;66(5). doi:10.1145/3339471
apa: Lenzen, C., & Rybicki, J. (2019). Self-stabilising Byzantine clock synchronisation
is almost as easy as consensus. Journal of the ACM. ACM. https://doi.org/10.1145/3339471
chicago: Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock
Synchronisation Is Almost as Easy as Consensus.” Journal of the ACM. ACM,
2019. https://doi.org/10.1145/3339471.
ieee: C. Lenzen and J. Rybicki, “Self-stabilising Byzantine clock synchronisation
is almost as easy as consensus,” Journal of the ACM, vol. 66, no. 5. ACM,
2019.
ista: Lenzen C, Rybicki J. 2019. Self-stabilising Byzantine clock synchronisation
is almost as easy as consensus. Journal of the ACM. 66(5), 32.
mla: Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock Synchronisation
Is Almost as Easy as Consensus.” Journal of the ACM, vol. 66, no. 5, 32,
ACM, 2019, doi:10.1145/3339471.
short: C. Lenzen, J. Rybicki, Journal of the ACM 66 (2019).
date_created: 2019-10-24T17:12:48Z
date_published: 2019-09-01T00:00:00Z
date_updated: 2023-08-30T07:07:23Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3339471
ec_funded: 1
external_id:
arxiv:
- '1705.06173'
isi:
- '000496514100001'
file:
- access_level: open_access
checksum: 7e5d95c478e0e393f4927fcf7e48194e
content_type: application/pdf
creator: dernst
date_created: 2019-10-25T12:58:38Z
date_updated: 2020-07-14T12:47:46Z
file_id: '6975'
file_name: 2019_JACM_Lenzen.pdf
file_size: 2183085
relation: main_file
file_date_updated: 2020-07-14T12:47:46Z
has_accepted_license: '1'
intvolume: ' 66'
isi: 1
issue: '5'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Journal of the ACM
publication_identifier:
issn:
- 0004-5411
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: Self-stabilising Byzantine clock synchronisation is almost as easy as consensus
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 66
year: '2019'
...
---
_id: '7122'
abstract:
- lang: eng
text: Data-rich applications in machine-learning and control have motivated an intense
research on large-scale optimization. Novel algorithms have been proposed and
shown to have optimal convergence rates in terms of iteration counts. However,
their practical performance is severely degraded by the cost of exchanging high-dimensional
gradient vectors between computing nodes. Several gradient compression heuristics
have recently been proposed to reduce communications, but few theoretical results
exist that quantify how they impact algorithm convergence. This paper establishes
and strengthens the convergence guarantees for gradient descent under a family
of gradient compression techniques. For convex optimization problems, we derive
admissible step sizes and quantify both the number of iterations and the number
of bits that need to be exchanged to reach a target accuracy. Finally, we validate
the performance of different gradient compression techniques in simulations. The
numerical results highlight the properties of different gradient compression algorithms
and confirm that fast convergence with limited information exchange is possible.
article_number: '8619625'
article_processing_charge: No
author:
- first_name: Sarit
full_name: Khirirat, Sarit
last_name: Khirirat
- first_name: Mikael
full_name: Johansson, Mikael
last_name: Johansson
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Khirirat S, Johansson M, Alistarh D-A. Gradient compression for communication-limited
convex optimization. In: 2018 IEEE Conference on Decision and Control.
IEEE; 2019. doi:10.1109/cdc.2018.8619625'
apa: 'Khirirat, S., Johansson, M., & Alistarh, D.-A. (2019). Gradient compression
for communication-limited convex optimization. In 2018 IEEE Conference on Decision
and Control. Miami Beach, FL, United States: IEEE. https://doi.org/10.1109/cdc.2018.8619625'
chicago: Khirirat, Sarit, Mikael Johansson, and Dan-Adrian Alistarh. “Gradient Compression
for Communication-Limited Convex Optimization.” In 2018 IEEE Conference on
Decision and Control. IEEE, 2019. https://doi.org/10.1109/cdc.2018.8619625.
ieee: S. Khirirat, M. Johansson, and D.-A. Alistarh, “Gradient compression for communication-limited
convex optimization,” in 2018 IEEE Conference on Decision and Control,
Miami Beach, FL, United States, 2019.
ista: 'Khirirat S, Johansson M, Alistarh D-A. 2019. Gradient compression for communication-limited
convex optimization. 2018 IEEE Conference on Decision and Control. CDC: Conference
on Decision and Control, 8619625.'
mla: Khirirat, Sarit, et al. “Gradient Compression for Communication-Limited Convex
Optimization.” 2018 IEEE Conference on Decision and Control, 8619625, IEEE,
2019, doi:10.1109/cdc.2018.8619625.
short: S. Khirirat, M. Johansson, D.-A. Alistarh, in:, 2018 IEEE Conference on Decision
and Control, IEEE, 2019.
conference:
end_date: 2018-12-19
location: Miami Beach, FL, United States
name: 'CDC: Conference on Decision and Control'
start_date: 2018-12-17
date_created: 2019-11-26T15:07:49Z
date_published: 2019-01-21T00:00:00Z
date_updated: 2023-09-06T11:14:55Z
day: '21'
department:
- _id: DaAl
doi: 10.1109/cdc.2018.8619625
external_id:
isi:
- '000458114800023'
isi: 1
language:
- iso: eng
month: '01'
oa_version: None
publication: 2018 IEEE Conference on Decision and Control
publication_identifier:
isbn:
- '9781538613955'
issn:
- 0743-1546
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Gradient compression for communication-limited convex optimization
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...
---
_id: '7201'
abstract:
- lang: eng
text: Applying machine learning techniques to the quickly growing data in science
and industry requires highly-scalable algorithms. Large datasets are most commonly
processed "data parallel" distributed across many nodes. Each node's contribution
to the overall gradient is summed using a global allreduce. This allreduce is
the single communication and thus scalability bottleneck for most machine learning
workloads. We observe that frequently, many gradient values are (close to) zero,
leading to sparse of sparsifyable communications. To exploit this insight, we
analyze, design, and implement a set of communication-efficient protocols for
sparse input data, in conjunction with efficient machine learning algorithms which
can leverage these primitives. Our communication protocols generalize standard
collective operations, by allowing processes to contribute arbitrary sparse input
data vectors. Our generic communication library, SparCML1, extends MPI to support
additional features, such as non-blocking (asynchronous) operations and low-precision
data representations. As such, SparCML and its techniques will form the basis
of future highly-scalable machine learning frameworks.
article_number: a11
article_processing_charge: No
arxiv: 1
author:
- first_name: Cedric
full_name: Renggli, Cedric
last_name: Renggli
- first_name: Saleh
full_name: Ashkboos, Saleh
id: 0D0A9058-257B-11EA-A937-9341C3D8BC8A
last_name: Ashkboos
- first_name: Mehdi
full_name: Aghagolzadeh, Mehdi
last_name: Aghagolzadeh
- 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: Torsten
full_name: Hoefler, Torsten
last_name: Hoefler
citation:
ama: 'Renggli C, Ashkboos S, Aghagolzadeh M, Alistarh D-A, Hoefler T. SparCML: High-performance
sparse communication for machine learning. In: International Conference for
High Performance Computing, Networking, Storage and Analysis, SC. ACM; 2019.
doi:10.1145/3295500.3356222'
apa: 'Renggli, C., Ashkboos, S., Aghagolzadeh, M., Alistarh, D.-A., & Hoefler,
T. (2019). SparCML: High-performance sparse communication for machine learning.
In International Conference for High Performance Computing, Networking, Storage
and Analysis, SC. Denver, CO, Unites States: ACM. https://doi.org/10.1145/3295500.3356222'
chicago: 'Renggli, Cedric, Saleh Ashkboos, Mehdi Aghagolzadeh, Dan-Adrian Alistarh,
and Torsten Hoefler. “SparCML: High-Performance Sparse Communication for Machine
Learning.” In International Conference for High Performance Computing, Networking,
Storage and Analysis, SC. ACM, 2019. https://doi.org/10.1145/3295500.3356222.'
ieee: 'C. Renggli, S. Ashkboos, M. Aghagolzadeh, D.-A. Alistarh, and T. Hoefler,
“SparCML: High-performance sparse communication for machine learning,” in International
Conference for High Performance Computing, Networking, Storage and Analysis, SC,
Denver, CO, Unites States, 2019.'
ista: 'Renggli C, Ashkboos S, Aghagolzadeh M, Alistarh D-A, Hoefler T. 2019. SparCML:
High-performance sparse communication for machine learning. International Conference
for High Performance Computing, Networking, Storage and Analysis, SC. SC: Conference
for High Performance Computing, Networking, Storage and Analysis, a11.'
mla: 'Renggli, Cedric, et al. “SparCML: High-Performance Sparse Communication for
Machine Learning.” International Conference for High Performance Computing,
Networking, Storage and Analysis, SC, a11, ACM, 2019, doi:10.1145/3295500.3356222.'
short: C. Renggli, S. Ashkboos, M. Aghagolzadeh, D.-A. Alistarh, T. Hoefler, in:,
International Conference for High Performance Computing, Networking, Storage and
Analysis, SC, ACM, 2019.
conference:
end_date: 2019-11-19
location: Denver, CO, Unites States
name: 'SC: Conference for High Performance Computing, Networking, Storage and Analysis'
start_date: 2019-11-17
date_created: 2019-12-22T23:00:42Z
date_published: 2019-11-17T00:00:00Z
date_updated: 2023-09-06T14:37:55Z
day: '17'
department:
- _id: DaAl
doi: 10.1145/3295500.3356222
ec_funded: 1
external_id:
arxiv:
- '1802.08021'
isi:
- '000545976800011'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1802.08021
month: '11'
oa: 1
oa_version: Preprint
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: International Conference for High Performance Computing, Networking,
Storage and Analysis, SC
publication_identifier:
eissn:
- '21674337'
isbn:
- '9781450362290'
issn:
- '21674329'
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'SparCML: High-performance sparse communication for machine learning'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...
---
_id: '7214'
abstract:
- lang: eng
text: "Background: Many cancer genomes are extensively rearranged with highly aberrant
chromosomal karyotypes. Structural and copy number variations in cancer genomes
can be determined via abnormal mapping of sequenced reads to the reference genome.
Recently it became possible to reconcile both of these types of large-scale variations
into a karyotype graph representation of the rearranged cancer genomes. Such a
representation, however, does not directly describe the linear and/or circular
structure of the underlying rearranged cancer chromosomes, thus limiting possible
analysis of cancer genomes somatic evolutionary process as well as functional
genomic changes brought by the large-scale genome rearrangements.\r\n\r\nResults:
Here we address the aforementioned limitation by introducing a novel methodological
framework for recovering rearranged cancer chromosomes from karyotype graphs.
For a cancer karyotype graph we formulate an Eulerian Decomposition Problem (EDP)
of finding a collection of linear and/or circular rearranged cancer chromosomes
that are determined by the graph. We derive and prove computational complexities
for several variations of the EDP. We then demonstrate that Eulerian decomposition
of the cancer karyotype graphs is not always unique and present the Consistent
Contig Covering Problem (CCCP) of recovering unambiguous cancer contigs from the
cancer karyotype graph, and describe a novel algorithm CCR capable of solving
CCCP in polynomial time. We apply CCR on a prostate cancer dataset and demonstrate
that it is capable of consistently recovering large cancer contigs even when underlying
cancer genomes are highly rearranged.\r\n\r\nConclusions: CCR can recover rearranged
cancer contigs from karyotype graphs thereby addressing existing limitation in
inferring chromosomal structures of rearranged cancer genomes and advancing our
understanding of both patient/cancer-specific as well as the overall genetic instability
in cancer."
article_number: '641'
article_processing_charge: No
article_type: original
author:
- first_name: Sergey
full_name: Aganezov, Sergey
last_name: Aganezov
- first_name: Ilya
full_name: Zban, Ilya
last_name: Zban
- first_name: Vitalii
full_name: Aksenov, Vitalii
id: 2980135A-F248-11E8-B48F-1D18A9856A87
last_name: Aksenov
- first_name: Nikita
full_name: Alexeev, Nikita
last_name: Alexeev
- first_name: Michael C.
full_name: Schatz, Michael C.
last_name: Schatz
citation:
ama: Aganezov S, Zban I, Aksenov V, Alexeev N, Schatz MC. Recovering rearranged
cancer chromosomes from karyotype graphs. BMC Bioinformatics. 2019;20.
doi:10.1186/s12859-019-3208-4
apa: Aganezov, S., Zban, I., Aksenov, V., Alexeev, N., & Schatz, M. C. (2019).
Recovering rearranged cancer chromosomes from karyotype graphs. BMC Bioinformatics.
BMC. https://doi.org/10.1186/s12859-019-3208-4
chicago: Aganezov, Sergey, Ilya Zban, Vitalii Aksenov, Nikita Alexeev, and Michael
C. Schatz. “Recovering Rearranged Cancer Chromosomes from Karyotype Graphs.” BMC
Bioinformatics. BMC, 2019. https://doi.org/10.1186/s12859-019-3208-4.
ieee: S. Aganezov, I. Zban, V. Aksenov, N. Alexeev, and M. C. Schatz, “Recovering
rearranged cancer chromosomes from karyotype graphs,” BMC Bioinformatics,
vol. 20. BMC, 2019.
ista: Aganezov S, Zban I, Aksenov V, Alexeev N, Schatz MC. 2019. Recovering rearranged
cancer chromosomes from karyotype graphs. BMC Bioinformatics. 20, 641.
mla: Aganezov, Sergey, et al. “Recovering Rearranged Cancer Chromosomes from Karyotype
Graphs.” BMC Bioinformatics, vol. 20, 641, BMC, 2019, doi:10.1186/s12859-019-3208-4.
short: S. Aganezov, I. Zban, V. Aksenov, N. Alexeev, M.C. Schatz, BMC Bioinformatics
20 (2019).
date_created: 2019-12-29T23:00:46Z
date_published: 2019-12-17T00:00:00Z
date_updated: 2023-09-06T14:51:06Z
day: '17'
ddc:
- '570'
department:
- _id: DaAl
doi: 10.1186/s12859-019-3208-4
external_id:
isi:
- '000511618800007'
file:
- access_level: open_access
checksum: 7a30357efdcf8f66587ed495c0927724
content_type: application/pdf
creator: dernst
date_created: 2020-01-02T16:10:58Z
date_updated: 2020-07-14T12:47:54Z
file_id: '7221'
file_name: 2019_BMCBioinfo_Aganezov.pdf
file_size: 1917374
relation: main_file
file_date_updated: 2020-07-14T12:47:54Z
has_accepted_license: '1'
intvolume: ' 20'
isi: 1
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: BMC Bioinformatics
publication_identifier:
eissn:
- '14712105'
publication_status: published
publisher: BMC
quality_controlled: '1'
scopus_import: '1'
status: public
title: Recovering rearranged cancer chromosomes from karyotype graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 20
year: '2019'
...
---
_id: '7228'
abstract:
- lang: eng
text: "Traditional concurrent programming involves manipulating shared mutable state.
Alternatives to this programming style are communicating sequential processes
(CSP) and actor models, which share data via explicit communication. These models
have been known for almost half a century, and have recently had started to gain
significant traction among modern programming languages. The common abstraction
for communication between several processes is the channel. Although channels
are similar to producer-consumer data structures, they have different semantics
and support additional operations, such as the select expression. Despite their
growing popularity, most known implementations of channels use lock-based data
structures and can be rather inefficient.\r\n\r\nIn this paper, we present the
first efficient lock-free algorithm for implementing a communication channel for
CSP programming. We provide implementations and experimental results in the Kotlin
and Go programming languages. Our new algorithm outperforms existing implementations
on many workloads, while providing non-blocking progress guarantee. Our design
can serve as an example of how to construct general communication data structures
for CSP and actor models. "
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- 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: Roman
full_name: Elizarov, Roman
last_name: Elizarov
citation:
ama: 'Koval N, Alistarh D-A, Elizarov R. Scalable FIFO channels for programming
via communicating sequential processes. In: 25th Anniversary of Euro-Par.
Vol 11725. Springer Nature; 2019:317-333. doi:10.1007/978-3-030-29400-7_23'
apa: 'Koval, N., Alistarh, D.-A., & Elizarov, R. (2019). Scalable FIFO channels
for programming via communicating sequential processes. In 25th Anniversary
of Euro-Par (Vol. 11725, pp. 317–333). Göttingen, Germany: Springer Nature.
https://doi.org/10.1007/978-3-030-29400-7_23'
chicago: Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. “Scalable FIFO
Channels for Programming via Communicating Sequential Processes.” In 25th Anniversary
of Euro-Par, 11725:317–33. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-29400-7_23.
ieee: N. Koval, D.-A. Alistarh, and R. Elizarov, “Scalable FIFO channels for programming
via communicating sequential processes,” in 25th Anniversary of Euro-Par,
Göttingen, Germany, 2019, vol. 11725, pp. 317–333.
ista: 'Koval N, Alistarh D-A, Elizarov R. 2019. Scalable FIFO channels for programming
via communicating sequential processes. 25th Anniversary of Euro-Par. Euro-Par:
European Conference on Parallel Processing, LNCS, vol. 11725, 317–333.'
mla: Koval, Nikita, et al. “Scalable FIFO Channels for Programming via Communicating
Sequential Processes.” 25th Anniversary of Euro-Par, vol. 11725, Springer
Nature, 2019, pp. 317–33, doi:10.1007/978-3-030-29400-7_23.
short: N. Koval, D.-A. Alistarh, R. Elizarov, in:, 25th Anniversary of Euro-Par,
Springer Nature, 2019, pp. 317–333.
conference:
end_date: 2019-08-30
location: Göttingen, Germany
name: 'Euro-Par: European Conference on Parallel Processing'
start_date: 2019-08-26
date_created: 2020-01-05T23:00:46Z
date_published: 2019-08-13T00:00:00Z
date_updated: 2023-09-06T14:53:59Z
day: '13'
department:
- _id: DaAl
doi: 10.1007/978-3-030-29400-7_23
external_id:
isi:
- '000851061400023'
intvolume: ' 11725'
isi: 1
language:
- iso: eng
month: '08'
oa_version: None
page: 317-333
publication: 25th Anniversary of Euro-Par
publication_identifier:
eissn:
- 1611-3349
isbn:
- 978-3-0302-9399-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Scalable FIFO channels for programming via communicating sequential processes
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 11725
year: '2019'
...
---
_id: '7437'
abstract:
- lang: eng
text: 'Most of today''s distributed machine learning systems assume reliable networks:
whenever two machines exchange information (e.g., gradients or models), the network
should guarantee the delivery of the message. At the same time, recent work exhibits
the impressive tolerance of machine learning algorithms to errors or noise arising
from relaxed communication or synchronization. In this paper, we connect these
two trends, and consider the following question: Can we design machine learning
systems that are tolerant to network unreliability during training? With this
motivation, we focus on a theoretical problem of independent interest-given a
standard distributed parameter server architecture, if every communication between
the worker and the server has a non-zero probability p of being dropped, does
there exist an algorithm that still converges, and at what speed? The technical
contribution of this paper is a novel theoretical analysis proving that distributed
learning over unreliable network can achieve comparable convergence rate to centralized
or distributed learning over reliable networks. Further, we prove that the influence
of the packet drop rate diminishes with the growth of the number of parameter
servers. We map this theoretical result onto a real-world scenario, training deep
neural networks over an unreliable network layer, and conduct network simulation
to validate the system improvement by allowing the networks to be unreliable.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Chen
full_name: Yu, Chen
last_name: Yu
- first_name: Hanlin
full_name: Tang, Hanlin
last_name: Tang
- first_name: Cedric
full_name: Renggli, Cedric
last_name: Renggli
- first_name: Simon
full_name: Kassing, Simon
last_name: Kassing
- first_name: Ankit
full_name: Singla, Ankit
last_name: Singla
- 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: Ce
full_name: Zhang, Ce
last_name: Zhang
- first_name: Ji
full_name: Liu, Ji
last_name: Liu
citation:
ama: 'Yu C, Tang H, Renggli C, et al. Distributed learning over unreliable networks.
In: 36th International Conference on Machine Learning, ICML 2019. Vol 2019-June.
IMLS; 2019:12481-12512.'
apa: 'Yu, C., Tang, H., Renggli, C., Kassing, S., Singla, A., Alistarh, D.-A., …
Liu, J. (2019). Distributed learning over unreliable networks. In 36th International
Conference on Machine Learning, ICML 2019 (Vol. 2019–June, pp. 12481–12512).
Long Beach, CA, United States: IMLS.'
chicago: Yu, Chen, Hanlin Tang, Cedric Renggli, Simon Kassing, Ankit Singla, Dan-Adrian
Alistarh, Ce Zhang, and Ji Liu. “Distributed Learning over Unreliable Networks.”
In 36th International Conference on Machine Learning, ICML 2019, 2019–June:12481–512.
IMLS, 2019.
ieee: C. Yu et al., “Distributed learning over unreliable networks,” in 36th
International Conference on Machine Learning, ICML 2019, Long Beach, CA, United
States, 2019, vol. 2019–June, pp. 12481–12512.
ista: 'Yu C, Tang H, Renggli C, Kassing S, Singla A, Alistarh D-A, Zhang C, Liu
J. 2019. Distributed learning over unreliable networks. 36th International Conference
on Machine Learning, ICML 2019. ICML: International Conference on Machine Learning
vol. 2019–June, 12481–12512.'
mla: Yu, Chen, et al. “Distributed Learning over Unreliable Networks.” 36th International
Conference on Machine Learning, ICML 2019, vol. 2019–June, IMLS, 2019, pp.
12481–512.
short: C. Yu, H. Tang, C. Renggli, S. Kassing, A. Singla, D.-A. Alistarh, C. Zhang,
J. Liu, in:, 36th International Conference on Machine Learning, ICML 2019, IMLS,
2019, pp. 12481–12512.
conference:
end_date: 2019-06-15
location: Long Beach, CA, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2019-06-10
date_created: 2020-02-02T23:01:06Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-06T15:21:48Z
day: '01'
department:
- _id: DaAl
external_id:
arxiv:
- '1810.07766'
isi:
- '000684034307036'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1810.07766
month: '06'
oa: 1
oa_version: Preprint
page: 12481-12512
publication: 36th International Conference on Machine Learning, ICML 2019
publication_identifier:
isbn:
- '9781510886988'
publication_status: published
publisher: IMLS
quality_controlled: '1'
scopus_import: '1'
status: public
title: Distributed learning over unreliable networks
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2019-June
year: '2019'
...
---
_id: '7542'
abstract:
- lang: eng
text: We present a novel class of convolutional neural networks (CNNs) for set functions,i.e.,
data indexed with the powerset of a finite set. The convolutions are derivedas
linear, shift-equivariant functions for various notions of shifts on set functions.The
framework is fundamentally different from graph convolutions based on theLaplacian,
as it provides not one but several basic shifts, one for each element inthe ground
set. Prototypical experiments with several set function classificationtasks on
synthetic datasets and on datasets derived from real-world hypergraphsdemonstrate
the potential of our new powerset CNNs.
article_processing_charge: No
arxiv: 1
author:
- first_name: Chris
full_name: Wendler, Chris
last_name: Wendler
- 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: Markus
full_name: Püschel, Markus
last_name: Püschel
citation:
ama: 'Wendler C, Alistarh D-A, Püschel M. Powerset convolutional neural networks.
In: Vol 32. Neural Information Processing Systems Foundation; 2019:927-938.'
apa: 'Wendler, C., Alistarh, D.-A., & Püschel, M. (2019). Powerset convolutional
neural networks (Vol. 32, pp. 927–938). Presented at the NIPS: Conference on Neural
Information Processing Systems, Vancouver, Canada: Neural Information Processing
Systems Foundation.'
chicago: Wendler, Chris, Dan-Adrian Alistarh, and Markus Püschel. “Powerset Convolutional
Neural Networks,” 32:927–38. Neural Information Processing Systems Foundation,
2019.
ieee: 'C. Wendler, D.-A. Alistarh, and M. Püschel, “Powerset convolutional neural
networks,” presented at the NIPS: Conference on Neural Information Processing
Systems, Vancouver, Canada, 2019, vol. 32, pp. 927–938.'
ista: 'Wendler C, Alistarh D-A, Püschel M. 2019. Powerset convolutional neural networks.
NIPS: Conference on Neural Information Processing Systems vol. 32, 927–938.'
mla: Wendler, Chris, et al. Powerset Convolutional Neural Networks. Vol.
32, Neural Information Processing Systems Foundation, 2019, pp. 927–38.
short: C. Wendler, D.-A. Alistarh, M. Püschel, in:, Neural Information Processing
Systems Foundation, 2019, pp. 927–938.
conference:
end_date: 2019-12-14
location: Vancouver, Canada
name: 'NIPS: Conference on Neural Information Processing Systems'
start_date: 2019-12-08
date_created: 2020-02-28T10:03:24Z
date_published: 2019-12-01T00:00:00Z
date_updated: 2023-09-08T11:13:52Z
day: '01'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '1909.02253'
isi:
- '000534424300084'
intvolume: ' 32'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://papers.nips.cc/paper/8379-powerset-convolutional-neural-networks
month: '12'
oa: 1
oa_version: Published Version
page: 927-938
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication_identifier:
issn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
status: public
title: Powerset convolutional neural networks
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 32
year: '2019'
...
---
_id: '5947'
abstract:
- lang: eng
text: Graph algorithms applied in many applications, including social networks,
communication networks, VLSI design, graphics, and several others, require dynamic
modifications - addition and removal of vertices and/or edges - in the graph.
This paper presents a novel concurrent non-blocking algorithm to implement a dynamic
unbounded directed graph in a shared-memory machine. The addition and removal
operations of vertices and edges are lock-free. For a finite sized graph, the
lookup operations are wait-free. Most significant component of the presented algorithm
is the reachability query in a concurrent graph. The reachability queries in our
algorithm are obstruction-free and thus impose minimal additional synchronization
cost over other operations. We prove that each of the data structure operations
are linearizable. We extensively evaluate a sample C/C++ implementation of the
algorithm through a number of micro-benchmarks. The experimental results show
that the proposed algorithm scales well with the number of threads and on an average
provides 5 to 7x performance improvement over a concurrent graph implementation
using coarse-grained locking.
article_processing_charge: No
arxiv: 1
author:
- first_name: Bapi
full_name: Chatterjee, Bapi
id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-2742-4028
- first_name: Sathya
full_name: Peri, Sathya
last_name: Peri
- first_name: Muktikanta
full_name: Sa, Muktikanta
last_name: Sa
- first_name: Nandini
full_name: Singhal, Nandini
last_name: Singhal
citation:
ama: 'Chatterjee B, Peri S, Sa M, Singhal N. A simple and practical concurrent non-blocking
unbounded graph with linearizable reachability queries. In: ACM International
Conference Proceeding Series. ACM; 2019:168-177. doi:10.1145/3288599.3288617'
apa: 'Chatterjee, B., Peri, S., Sa, M., & Singhal, N. (2019). A simple and practical
concurrent non-blocking unbounded graph with linearizable reachability queries.
In ACM International Conference Proceeding Series (pp. 168–177). Bangalore,
India: ACM. https://doi.org/10.1145/3288599.3288617'
chicago: Chatterjee, Bapi, Sathya Peri, Muktikanta Sa, and Nandini Singhal. “A Simple
and Practical Concurrent Non-Blocking Unbounded Graph with Linearizable Reachability
Queries.” In ACM International Conference Proceeding Series, 168–77. ACM,
2019. https://doi.org/10.1145/3288599.3288617.
ieee: B. Chatterjee, S. Peri, M. Sa, and N. Singhal, “A simple and practical concurrent
non-blocking unbounded graph with linearizable reachability queries,” in ACM
International Conference Proceeding Series, Bangalore, India, 2019, pp. 168–177.
ista: 'Chatterjee B, Peri S, Sa M, Singhal N. 2019. A simple and practical concurrent
non-blocking unbounded graph with linearizable reachability queries. ACM International
Conference Proceeding Series. ICDCN: Conference on Distributed Computing and Networking,
168–177.'
mla: Chatterjee, Bapi, et al. “A Simple and Practical Concurrent Non-Blocking Unbounded
Graph with Linearizable Reachability Queries.” ACM International Conference
Proceeding Series, ACM, 2019, pp. 168–77, doi:10.1145/3288599.3288617.
short: B. Chatterjee, S. Peri, M. Sa, N. Singhal, in:, ACM International Conference
Proceeding Series, ACM, 2019, pp. 168–177.
conference:
end_date: 2019-01-07
location: Bangalore, India
name: 'ICDCN: Conference on Distributed Computing and Networking'
start_date: 2019-01-04
date_created: 2019-02-10T22:59:17Z
date_published: 2019-01-04T00:00:00Z
date_updated: 2023-08-24T14:41:53Z
day: '04'
department:
- _id: DaAl
doi: 10.1145/3288599.3288617
external_id:
arxiv:
- '1809.00896'
isi:
- '000484491600019'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1809.00896
month: '01'
oa: 1
oa_version: Preprint
page: 168-177
publication: ACM International Conference Proceeding Series
publication_identifier:
isbn:
- '978-1-4503-6094-4 '
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: A simple and practical concurrent non-blocking unbounded graph with linearizable
reachability queries
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...
---
_id: '6485'
abstract:
- lang: eng
text: Traditional concurrent programming involves manipulating shared mutable state.
Alternatives to this programming style are communicating sequential processes
(CSP) [1] and actor [2] models, which share data via explicit communication. Rendezvous
channelis the common abstraction for communication between several processes,
where senders and receivers perform a rendezvous handshake as a part of their
protocol (senders wait for receivers and vice versa). Additionally to this, channels
support the select expression. In this work, we present the first efficient lock-free
channel algorithm, and compare it against Go [3] and Kotlin [4] baseline implementations.
article_processing_charge: No
author:
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- 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: Roman
full_name: Elizarov, Roman
last_name: Elizarov
citation:
ama: Koval N, Alistarh D-A, Elizarov R. Lock-Free Channels for Programming via
Communicating Sequential Processes. ACM Press; 2019:417-418. doi:10.1145/3293883.3297000
apa: 'Koval, N., Alistarh, D.-A., & Elizarov, R. (2019). Lock-free channels
for programming via communicating sequential processes. Proceedings of
the 24th Symposium on Principles and Practice of Parallel Programming (pp.
417–418). Washington, NY, United States: ACM Press. https://doi.org/10.1145/3293883.3297000'
chicago: Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. Lock-Free Channels
for Programming via Communicating Sequential Processes. Proceedings of
the 24th Symposium on Principles and Practice of Parallel Programming. ACM
Press, 2019. https://doi.org/10.1145/3293883.3297000.
ieee: N. Koval, D.-A. Alistarh, and R. Elizarov, Lock-free channels for programming
via communicating sequential processes. ACM Press, 2019, pp. 417–418.
ista: Koval N, Alistarh D-A, Elizarov R. 2019. Lock-free channels for programming
via communicating sequential processes, ACM Press,p.
mla: Koval, Nikita, et al. “Lock-Free Channels for Programming via Communicating
Sequential Processes.” Proceedings of the 24th Symposium on Principles and
Practice of Parallel Programming, ACM Press, 2019, pp. 417–18, doi:10.1145/3293883.3297000.
short: N. Koval, D.-A. Alistarh, R. Elizarov, Lock-Free Channels for Programming
via Communicating Sequential Processes, ACM Press, 2019.
conference:
end_date: 2019-02-20
location: Washington, NY, United States
name: 'PPoPP: Principles and Practice of Parallel Programming'
start_date: 2019-02-16
date_created: 2019-05-24T10:09:12Z
date_published: 2019-02-01T00:00:00Z
date_updated: 2023-08-25T10:41:20Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3293883.3297000
external_id:
isi:
- '000587604600044'
isi: 1
language:
- iso: eng
month: '02'
oa_version: None
page: 417-418
publication: Proceedings of the 24th Symposium on Principles and Practice of Parallel
Programming
publication_identifier:
isbn:
- '9781450362252'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
status: public
title: Lock-free channels for programming via communicating sequential processes
type: conference_poster
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...
---
_id: '7812'
abstract:
- lang: eng
text: Deep neural networks (DNNs) continue to make significant advances, solving
tasks from image classification to translation or reinforcement learning. One
aspect of the field receiving considerable attention is efficiently executing
deep models in resource-constrained environments, such as mobile or embedded devices.
This paper focuses on this problem, and proposes two new compression methods,
which jointly leverage weight quantization and distillation of larger teacher
networks into smaller student networks. The first method we propose is called
quantized distillation and leverages distillation during the training process,
by incorporating distillation loss, expressed with respect to the teacher, into
the training of a student network whose weights are quantized to a limited set
of levels. The second method, differentiable quantization, optimizes the location
of quantization points through stochastic gradient descent, to better fit the
behavior of the teacher model. We validate both methods through experiments on
convolutional and recurrent architectures. We show that quantized shallow students
can reach similar accuracy levels to full-precision teacher models, while providing
order of magnitude compression, and inference speedup that is linear in the depth
reduction. In sum, our results enable DNNs for resource-constrained environments
to leverage architecture and accuracy advances developed on more powerful devices.
article_processing_charge: No
arxiv: 1
author:
- first_name: Antonio
full_name: Polino, Antonio
last_name: Polino
- first_name: Razvan
full_name: Pascanu, Razvan
last_name: Pascanu
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Polino A, Pascanu R, Alistarh D-A. Model compression via distillation and
quantization. In: 6th International Conference on Learning Representations.
; 2018.'
apa: Polino, A., Pascanu, R., & Alistarh, D.-A. (2018). Model compression via
distillation and quantization. In 6th International Conference on Learning
Representations. Vancouver, Canada.
chicago: Polino, Antonio, Razvan Pascanu, and Dan-Adrian Alistarh. “Model Compression
via Distillation and Quantization.” In 6th International Conference on Learning
Representations, 2018.
ieee: A. Polino, R. Pascanu, and D.-A. Alistarh, “Model compression via distillation
and quantization,” in 6th International Conference on Learning Representations,
Vancouver, Canada, 2018.
ista: 'Polino A, Pascanu R, Alistarh D-A. 2018. Model compression via distillation
and quantization. 6th International Conference on Learning Representations. ICLR:
International Conference on Learning Representations.'
mla: Polino, Antonio, et al. “Model Compression via Distillation and Quantization.”
6th International Conference on Learning Representations, 2018.
short: A. Polino, R. Pascanu, D.-A. Alistarh, in:, 6th International Conference
on Learning Representations, 2018.
conference:
end_date: 2018-05-03
location: Vancouver, Canada
name: 'ICLR: International Conference on Learning Representations'
start_date: 2018-04-30
date_created: 2020-05-10T22:00:51Z
date_published: 2018-05-01T00:00:00Z
date_updated: 2023-02-23T13:18:41Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
external_id:
arxiv:
- '1802.05668'
file:
- access_level: open_access
checksum: a4336c167978e81891970e4e4517a8c3
content_type: application/pdf
creator: dernst
date_created: 2020-05-26T13:02:00Z
date_updated: 2020-07-14T12:48:03Z
file_id: '7894'
file_name: 2018_ICLR_Polino.pdf
file_size: 308339
relation: main_file
file_date_updated: 2020-07-14T12:48:03Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
publication: 6th International Conference on Learning Representations
publication_status: published
quality_controlled: '1'
scopus_import: 1
status: public
title: Model compression via distillation and quantization
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '85'
abstract:
- lang: eng
text: Concurrent accesses to shared data structures must be synchronized to avoid
data races. Coarse-grained synchronization, which locks the entire data structure,
is easy to implement but does not scale. Fine-grained synchronization can scale
well, but can be hard to reason about. Hand-over-hand locking, in which operations
are pipelined as they traverse the data structure, combines fine-grained synchronization
with ease of use. However, the traditional implementation suffers from inherent
overheads. This paper introduces snapshot-based synchronization (SBS), a novel
hand-over-hand locking mechanism. SBS decouples the synchronization state from
the data, significantly improving cache utilization. Further, it relies on guarantees
provided by pipelining to minimize synchronization that requires cross-thread
communication. Snapshot-based synchronization thus scales much better than traditional
hand-over-hand locking, while maintaining the same ease of use.
acknowledgement: Trevor Brown was supported in part by the ISF (grants 2005/17 & 1749/14)
and by a NSERC post-doctoral fellowship.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Eran
full_name: Gilad, Eran
last_name: Gilad
- first_name: Trevor A
full_name: Brown, Trevor A
id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
last_name: Brown
- first_name: Mark
full_name: Oskin, Mark
last_name: Oskin
- first_name: Yoav
full_name: Etsion, Yoav
last_name: Etsion
citation:
ama: 'Gilad E, Brown TA, Oskin M, Etsion Y. Snapshot based synchronization: A fast
replacement for Hand-over-Hand locking. In: Vol 11014. Springer; 2018:465-479.
doi:10.1007/978-3-319-96983-1_33'
apa: 'Gilad, E., Brown, T. A., Oskin, M., & Etsion, Y. (2018). Snapshot based
synchronization: A fast replacement for Hand-over-Hand locking (Vol. 11014, pp.
465–479). Presented at the Euro-Par: European Conference on Parallel Processing,
Turin, Italy: Springer. https://doi.org/10.1007/978-3-319-96983-1_33'
chicago: 'Gilad, Eran, Trevor A Brown, Mark Oskin, and Yoav Etsion. “Snapshot Based
Synchronization: A Fast Replacement for Hand-over-Hand Locking,” 11014:465–79.
Springer, 2018. https://doi.org/10.1007/978-3-319-96983-1_33.'
ieee: 'E. Gilad, T. A. Brown, M. Oskin, and Y. Etsion, “Snapshot based synchronization:
A fast replacement for Hand-over-Hand locking,” presented at the Euro-Par: European
Conference on Parallel Processing, Turin, Italy, 2018, vol. 11014, pp. 465–479.'
ista: 'Gilad E, Brown TA, Oskin M, Etsion Y. 2018. Snapshot based synchronization:
A fast replacement for Hand-over-Hand locking. Euro-Par: European Conference on
Parallel Processing, LNCS, vol. 11014, 465–479.'
mla: 'Gilad, Eran, et al. Snapshot Based Synchronization: A Fast Replacement
for Hand-over-Hand Locking. Vol. 11014, Springer, 2018, pp. 465–79, doi:10.1007/978-3-319-96983-1_33.'
short: E. Gilad, T.A. Brown, M. Oskin, Y. Etsion, in:, Springer, 2018, pp. 465–479.
conference:
end_date: 2018-08-31
location: Turin, Italy
name: 'Euro-Par: European Conference on Parallel Processing'
start_date: 2018-08-27
date_created: 2018-12-11T11:44:33Z
date_published: 2018-08-01T00:00:00Z
date_updated: 2023-09-18T09:32:36Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/978-3-319-96983-1_33
external_id:
isi:
- '000851042300031'
file:
- access_level: open_access
checksum: 13a3f250be8878405e791b53c19722ad
content_type: application/pdf
creator: dernst
date_created: 2019-02-12T07:40:40Z
date_updated: 2020-07-14T12:48:14Z
file_id: '5954'
file_name: 2018_Brown.pdf
file_size: 665372
relation: main_file
file_date_updated: 2020-07-14T12:48:14Z
has_accepted_license: '1'
intvolume: ' 11014'
isi: 1
language:
- iso: eng
month: '08'
oa: 1
oa_version: Preprint
page: 465 - 479
project:
- _id: 26450934-B435-11E9-9278-68D0E5697425
name: NSERC Postdoctoral fellowship
publication_identifier:
issn:
- '03029743'
publication_status: published
publisher: Springer
publist_id: '7969'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Snapshot based synchronization: A fast replacement for Hand-over-Hand locking'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 11014
year: '2018'
...
---
_id: '7116'
abstract:
- lang: eng
text: 'Training deep learning models has received tremendous research interest recently.
In particular, there has been intensive research on reducing the communication
cost of training when using multiple computational devices, through reducing the
precision of the underlying data representation. Naturally, such methods induce
system trade-offs—lowering communication precision could de-crease communication
overheads and improve scalability; but, on the other hand, it can also reduce
the accuracy of training. In this paper, we study this trade-off space, and ask:Can
low-precision communication consistently improve the end-to-end performance of
training modern neural networks, with no accuracy loss?From the performance point
of view, the answer to this question may appear deceptively easy: compressing
communication through low precision should help when the ratio between communication
and computation is high. However, this answer is less straightforward when we
try to generalize this principle across various neural network architectures (e.g.,
AlexNet vs. ResNet),number of GPUs (e.g., 2 vs. 8 GPUs), machine configurations(e.g.,
EC2 instances vs. NVIDIA DGX-1), communication primitives (e.g., MPI vs. NCCL),
and even different GPU architectures(e.g., Kepler vs. Pascal). Currently, it is
not clear how a realistic realization of all these factors maps to the speed up
provided by low-precision communication. In this paper, we conduct an empirical
study to answer this question and report the insights.'
article_processing_charge: No
author:
- first_name: Demjan
full_name: Grubic, Demjan
last_name: Grubic
- first_name: Leo
full_name: Tam, Leo
last_name: Tam
- 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: Ce
full_name: Zhang, Ce
last_name: Zhang
citation:
ama: 'Grubic D, Tam L, Alistarh D-A, Zhang C. Synchronous multi-GPU training for
deep learning with low-precision communications: An empirical study. In: Proceedings
of the 21st International Conference on Extending Database Technology. OpenProceedings;
2018:145-156. doi:10.5441/002/EDBT.2018.14'
apa: 'Grubic, D., Tam, L., Alistarh, D.-A., & Zhang, C. (2018). Synchronous
multi-GPU training for deep learning with low-precision communications: An empirical
study. In Proceedings of the 21st International Conference on Extending Database
Technology (pp. 145–156). Vienna, Austria: OpenProceedings. https://doi.org/10.5441/002/EDBT.2018.14'
chicago: 'Grubic, Demjan, Leo Tam, Dan-Adrian Alistarh, and Ce Zhang. “Synchronous
Multi-GPU Training for Deep Learning with Low-Precision Communications: An Empirical
Study.” In Proceedings of the 21st International Conference on Extending Database
Technology, 145–56. OpenProceedings, 2018. https://doi.org/10.5441/002/EDBT.2018.14.'
ieee: 'D. Grubic, L. Tam, D.-A. Alistarh, and C. Zhang, “Synchronous multi-GPU training
for deep learning with low-precision communications: An empirical study,” in Proceedings
of the 21st International Conference on Extending Database Technology, Vienna,
Austria, 2018, pp. 145–156.'
ista: 'Grubic D, Tam L, Alistarh D-A, Zhang C. 2018. Synchronous multi-GPU training
for deep learning with low-precision communications: An empirical study. Proceedings
of the 21st International Conference on Extending Database Technology. EDBT: Conference
on Extending Database Technology, 145–156.'
mla: 'Grubic, Demjan, et al. “Synchronous Multi-GPU Training for Deep Learning with
Low-Precision Communications: An Empirical Study.” Proceedings of the 21st
International Conference on Extending Database Technology, OpenProceedings,
2018, pp. 145–56, doi:10.5441/002/EDBT.2018.14.'
short: D. Grubic, L. Tam, D.-A. Alistarh, C. Zhang, in:, Proceedings of the 21st
International Conference on Extending Database Technology, OpenProceedings, 2018,
pp. 145–156.
conference:
end_date: 2018-03-29
location: Vienna, Austria
name: 'EDBT: Conference on Extending Database Technology'
start_date: 2018-03-26
date_created: 2019-11-26T14:19:11Z
date_published: 2018-03-26T00:00:00Z
date_updated: 2023-02-23T12:59:17Z
day: '26'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.5441/002/EDBT.2018.14
file:
- access_level: open_access
checksum: ec979b56abc71016d6e6adfdadbb4afe
content_type: application/pdf
creator: dernst
date_created: 2019-11-26T14:23:04Z
date_updated: 2020-07-14T12:47:49Z
file_id: '7118'
file_name: 2018_OpenProceedings_Grubic.pdf
file_size: 1603204
relation: main_file
file_date_updated: 2020-07-14T12:47:49Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '03'
oa: 1
oa_version: Published Version
page: 145-156
publication: Proceedings of the 21st International Conference on Extending Database
Technology
publication_identifier:
isbn:
- '9783893180783'
issn:
- 2367-2005
publication_status: published
publisher: OpenProceedings
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Synchronous multi-GPU training for deep learning with low-precision communications:
An empirical study'
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '7123'
abstract:
- lang: eng
text: "Population protocols are a popular model of distributed computing, in which
n agents with limited local state interact randomly, and cooperate to collectively
compute global predicates. Inspired by recent developments in DNA programming,
an extensive series of papers, across different communities, has examined the
computability and complexity characteristics of this model. Majority, or consensus,
is a central task in this model, in which agents need to collectively reach a
decision as to which one of two states A or B had a higher initial count. Two
metrics are important: the time that a protocol requires to stabilize to an output
decision, and the state space size that each agent requires to do so. It is known
that majority requires Ω(log log n) states per agent to allow for fast (poly-logarithmic
time) stabilization, and that O(log2 n) states are sufficient. Thus, there is
an exponential gap between the space upper and lower bounds for this problem.
This paper addresses this question.\r\n\r\nOn the negative side, we provide a
new lower bound of Ω(log n) states for any protocol which stabilizes in O(n1–c)
expected time, for any constant c > 0. This result is conditional on monotonicity
and output assumptions, satisfied by all known protocols. Technically, it represents
a departure from previous lower bounds, in that it does not rely on the existence
of dense configurations. Instead, we introduce a new generalized surgery technique
to prove the existence of incorrect executions for any algorithm which would contradict
the lower bound. Subsequently, our lower bound also applies to general initial
configurations, including ones with a leader. On the positive side, we give a
new algorithm for majority which uses O(log n) states, and stabilizes in O(log2
n) expected time. Central to the algorithm is a new leaderless phase clock technique,
which allows agents to synchronize in phases of Θ(n log n) consecutive interactions
using O(log n) states per agent, exploiting a new connection between population
protocols and power-of-two-choices load balancing mechanisms. We also employ our
phase clock to build a leader election algorithm with a state space of size O(log
n), which stabilizes in O(log2 n) expected time."
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: James
full_name: Aspnes, James
last_name: Aspnes
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
citation:
ama: 'Alistarh D-A, Aspnes J, Gelashvili R. Space-optimal majority in population
protocols. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete
Algorithms. ACM; 2018:2221-2239. doi:10.1137/1.9781611975031.144'
apa: 'Alistarh, D.-A., Aspnes, J., & Gelashvili, R. (2018). Space-optimal majority
in population protocols. In Proceedings of the 29th Annual ACM-SIAM Symposium
on Discrete Algorithms (pp. 2221–2239). New Orleans, LA, United States: ACM.
https://doi.org/10.1137/1.9781611975031.144'
chicago: Alistarh, Dan-Adrian, James Aspnes, and Rati Gelashvili. “Space-Optimal
Majority in Population Protocols.” In Proceedings of the 29th Annual ACM-SIAM
Symposium on Discrete Algorithms, 2221–39. ACM, 2018. https://doi.org/10.1137/1.9781611975031.144.
ieee: D.-A. Alistarh, J. Aspnes, and R. Gelashvili, “Space-optimal majority in population
protocols,” in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete
Algorithms, New Orleans, LA, United States, 2018, pp. 2221–2239.
ista: 'Alistarh D-A, Aspnes J, Gelashvili R. 2018. Space-optimal majority in population
protocols. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms.
SODA: Symposium on Discrete Algorithms, 2221–2239.'
mla: Alistarh, Dan-Adrian, et al. “Space-Optimal Majority in Population Protocols.”
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms,
ACM, 2018, pp. 2221–39, doi:10.1137/1.9781611975031.144.
short: D.-A. Alistarh, J. Aspnes, R. Gelashvili, in:, Proceedings of the 29th Annual
ACM-SIAM Symposium on Discrete Algorithms, ACM, 2018, pp. 2221–2239.
conference:
end_date: 2018-01-10
location: New Orleans, LA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2018-01-07
date_created: 2019-11-26T15:10:55Z
date_published: 2018-01-30T00:00:00Z
date_updated: 2023-09-19T15:03:16Z
day: '30'
department:
- _id: DaAl
doi: 10.1137/1.9781611975031.144
external_id:
arxiv:
- '1704.04947'
isi:
- '000483921200145'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1704.04947
month: '01'
oa: 1
oa_version: Preprint
page: 2221-2239
publication: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- '9781611975031'
publication_status: published
publisher: ACM
quality_controlled: '1'
status: public
title: Space-optimal majority in population protocols
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '76'
abstract:
- lang: eng
text: 'Consider a fully-connected synchronous distributed system consisting of n
nodes, where up to f nodes may be faulty and every node starts in an arbitrary
initial state. In the synchronous C-counting problem, all nodes need to eventually
agree on a counter that is increased by one modulo C in each round for given C>1.
In the self-stabilising firing squad problem, the task is to eventually guarantee
that all non-faulty nodes have simultaneous responses to external inputs: if a
subset of the correct nodes receive an external “go” signal as input, then all
correct nodes should agree on a round (in the not-too-distant future) in which
to jointly output a “fire” signal. Moreover, no node should generate a “fire”
signal without some correct node having previously received a “go” signal as input.
We present a framework reducing both tasks to binary consensus at very small cost.
For example, we obtain a deterministic algorithm for self-stabilising Byzantine
firing squads with optimal resilience f<n/3, asymptotically optimal stabilisation
and response time O(f), and message size O(log f). As our framework does not restrict
the type of consensus routines used, we also obtain efficient randomised solutions.'
article_processing_charge: Yes (via OA deal)
author:
- first_name: Christoph
full_name: Lenzen, Christoph
last_name: Lenzen
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: Lenzen C, Rybicki J. Near-optimal self-stabilising counting and firing squads.
Distributed Computing. 2018. doi:10.1007/s00446-018-0342-6
apa: Lenzen, C., & Rybicki, J. (2018). Near-optimal self-stabilising counting
and firing squads. Distributed Computing. Springer. https://doi.org/10.1007/s00446-018-0342-6
chicago: Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting
and Firing Squads.” Distributed Computing. Springer, 2018. https://doi.org/10.1007/s00446-018-0342-6.
ieee: C. Lenzen and J. Rybicki, “Near-optimal self-stabilising counting and firing
squads,” Distributed Computing. Springer, 2018.
ista: Lenzen C, Rybicki J. 2018. Near-optimal self-stabilising counting and firing
squads. Distributed Computing.
mla: Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting
and Firing Squads.” Distributed Computing, Springer, 2018, doi:10.1007/s00446-018-0342-6.
short: C. Lenzen, J. Rybicki, Distributed Computing (2018).
date_created: 2018-12-11T11:44:30Z
date_published: 2018-09-12T00:00:00Z
date_updated: 2023-09-13T09:01:06Z
day: '12'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/s00446-018-0342-6
external_id:
isi:
- '000475627800005'
file:
- access_level: open_access
checksum: 872db70bba9b401500abe3c6ae2f1a61
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T14:21:22Z
date_updated: 2020-07-14T12:48:01Z
file_id: '5711'
file_name: 2018_DistributedComputing_Lenzen.pdf
file_size: 799337
relation: main_file
file_date_updated: 2020-07-14T12:48:01Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Distributed Computing
publication_status: published
publisher: Springer
publist_id: '7978'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Near-optimal self-stabilising counting and firing squads
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...