---
_id: '12780'
abstract:
- lang: eng
text: "The ability to scale out training workloads has been one of the key performance
enablers of deep learning. The main scaling approach is data-parallel GPU-based
training, which has been boosted by hardware and software support for highly efficient
point-to-point communication, and in particular via hardware bandwidth over-provisioning.
Overprovisioning comes at a cost: there is an order of magnitude price difference
between \"cloud-grade\" servers with such support, relative to their popular \"consumer-grade\"
counterparts, although single server-grade and consumer-grade GPUs can have similar
computational envelopes.\r\n\r\nIn this paper, we show that the costly hardware
overprovisioning approach can be supplanted via algorithmic and system design,
and propose a framework called CGX, which provides efficient software support
for compressed communication in ML applications, for both multi-GPU single-node
training, as well as larger-scale multi-node training. CGX is based on two technical
advances: At the system level, it relies on a re-developed communication stack
for ML frameworks, which provides flexible, highly-efficient support for compressed
communication. At the application level, it provides seamless, parameter-free
integration with popular frameworks, so that end-users do not have to modify training
recipes, nor significant training code. This is complemented by a layer-wise adaptive
compression technique which dynamically balances compression gains with accuracy
preservation. CGX integrates with popular ML frameworks, providing up to 3X speedups
for multi-GPU nodes based on commodity hardware, and order-of-magnitude improvements
in the multi-node setting, with negligible impact on accuracy."
acknowledgement: The authors sincerely thank Nikoli Dryden, Tal Ben-Nun, Torsten Hoefler
and Bapi Chatterjee for useful discussions throughout the development of this project.
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Ilia
full_name: Markov, Ilia
id: D0CF4148-C985-11E9-8066-0BDEE5697425
last_name: Markov
- first_name: Hamidreza
full_name: Ramezanikebrya, Hamidreza
last_name: Ramezanikebrya
- 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: 'Markov I, Ramezanikebrya H, Alistarh D-A. CGX: Adaptive system support for
communication-efficient deep learning. In: Proceedings of the 23rd ACM/IFIP
International Middleware Conference. Association for Computing Machinery;
2022:241-254. doi:10.1145/3528535.3565248'
apa: 'Markov, I., Ramezanikebrya, H., & Alistarh, D.-A. (2022). CGX: Adaptive
system support for communication-efficient deep learning. In Proceedings of
the 23rd ACM/IFIP International Middleware Conference (pp. 241–254). Quebec,
QC, Canada: Association for Computing Machinery. https://doi.org/10.1145/3528535.3565248'
chicago: 'Markov, Ilia, Hamidreza Ramezanikebrya, and Dan-Adrian Alistarh. “CGX:
Adaptive System Support for Communication-Efficient Deep Learning.” In Proceedings
of the 23rd ACM/IFIP International Middleware Conference, 241–54. Association
for Computing Machinery, 2022. https://doi.org/10.1145/3528535.3565248.'
ieee: 'I. Markov, H. Ramezanikebrya, and D.-A. Alistarh, “CGX: Adaptive system support
for communication-efficient deep learning,” in Proceedings of the 23rd ACM/IFIP
International Middleware Conference, Quebec, QC, Canada, 2022, pp. 241–254.'
ista: 'Markov I, Ramezanikebrya H, Alistarh D-A. 2022. CGX: Adaptive system support
for communication-efficient deep learning. Proceedings of the 23rd ACM/IFIP International
Middleware Conference. Middleware: International Middleware Conference, 241–254.'
mla: 'Markov, Ilia, et al. “CGX: Adaptive System Support for Communication-Efficient
Deep Learning.” Proceedings of the 23rd ACM/IFIP International Middleware Conference,
Association for Computing Machinery, 2022, pp. 241–54, doi:10.1145/3528535.3565248.'
short: I. Markov, H. Ramezanikebrya, D.-A. Alistarh, in:, Proceedings of the 23rd
ACM/IFIP International Middleware Conference, Association for Computing Machinery,
2022, pp. 241–254.
conference:
end_date: 2022-11-11
location: Quebec, QC, Canada
name: 'Middleware: International Middleware Conference'
start_date: 2022-11-07
date_created: 2023-03-31T06:17:00Z
date_published: 2022-11-01T00:00:00Z
date_updated: 2023-04-03T06:21:04Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3528535.3565248
external_id:
arxiv:
- '2111.08617'
file:
- access_level: open_access
checksum: 1a397746235f245da5468819247ff663
content_type: application/pdf
creator: dernst
date_created: 2023-04-03T06:17:58Z
date_updated: 2023-04-03T06:17:58Z
file_id: '12795'
file_name: 2022_ACMMiddleware_Markov.pdf
file_size: 1514169
relation: main_file
success: 1
file_date_updated: 2023-04-03T06:17:58Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '11'
oa: 1
oa_version: Published Version
page: 241-254
publication: Proceedings of the 23rd ACM/IFIP International Middleware Conference
publication_identifier:
isbn:
- '9781450393409'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: 'CGX: Adaptive system support for communication-efficient deep learning'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '13076'
abstract:
- lang: eng
text: "The source code for replicating experiments presented in the paper.\r\n\r\nThe
implementation of the designed priority schedulers can be found in Galois-2.2.1/include/Galois/WorkList/:\r\nStealingMultiQueue.h
is the StealingMultiQueue.\r\nMQOptimized/ contains MQ Optimized variants.\r\n\r\nWe
provide images that contain all the dependencies and datasets. Images can be pulled
from npostnikova/mq-based-schedulers repository, or downloaded from Zenodo. See
readme for more detail."
article_processing_charge: No
author:
- first_name: Anastasiia
full_name: Postnikova, Anastasiia
last_name: Postnikova
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
- 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: Postnikova A, Koval N, Nadiradze G, Alistarh D-A. Multi-queues can be state-of-the-art
priority schedulers. 2022. doi:10.5281/ZENODO.5733408
apa: Postnikova, A., Koval, N., Nadiradze, G., & Alistarh, D.-A. (2022). Multi-queues
can be state-of-the-art priority schedulers. Zenodo. https://doi.org/10.5281/ZENODO.5733408
chicago: Postnikova, Anastasiia, Nikita Koval, Giorgi Nadiradze, and Dan-Adrian
Alistarh. “Multi-Queues Can Be State-of-the-Art Priority Schedulers.” Zenodo,
2022. https://doi.org/10.5281/ZENODO.5733408.
ieee: A. Postnikova, N. Koval, G. Nadiradze, and D.-A. Alistarh, “Multi-queues can
be state-of-the-art priority schedulers.” Zenodo, 2022.
ista: Postnikova A, Koval N, Nadiradze G, Alistarh D-A. 2022. Multi-queues can be
state-of-the-art priority schedulers, Zenodo, 10.5281/ZENODO.5733408.
mla: Postnikova, Anastasiia, et al. Multi-Queues Can Be State-of-the-Art Priority
Schedulers. Zenodo, 2022, doi:10.5281/ZENODO.5733408.
short: A. Postnikova, N. Koval, G. Nadiradze, D.-A. Alistarh, (2022).
date_created: 2023-05-23T17:05:40Z
date_published: 2022-01-03T00:00:00Z
date_updated: 2023-08-03T06:48:34Z
day: '03'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.5281/ZENODO.5733408
main_file_link:
- open_access: '1'
url: https://doi.org/10.5281/zenodo.5813846
month: '01'
oa: 1
oa_version: Published Version
publisher: Zenodo
related_material:
link:
- relation: software
url: https://github.com/npostnikova/mq-based-schedulers/tree/v1.1
record:
- id: '11180'
relation: used_in_publication
status: public
status: public
title: Multi-queues can be state-of-the-art priority schedulers
type: research_data_reference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '11180'
abstract:
- lang: eng
text: "Designing and implementing efficient parallel priority schedulers is an active
research area. An intriguing proposed design is the Multi-Queue: given n threads
and m ≥ n distinct priority queues, task insertions are performed uniformly at
random, while, to delete, a thread picks two queues uniformly at random, and removes
the observed task of higher priority. This approach scales well, and has probabilistic
rank guarantees: roughly, the rank of each task removed, relative to remaining
tasks in all other queues, is O (m) in expectation. Yet, the performance of this
pattern is below that of well-engineered schedulers, which eschew theoretical
guarantees for practical efficiency.\r\n\r\nWe investigate whether it is possible
to design and implement a Multi-Queue-based task scheduler that is both highly-efficient
and has analytical guarantees. We propose a new variant called the Stealing Multi-Queue
(SMQ), a cache-efficient variant of the Multi-Queue, which leverages both queue
affinity---each thread has a local queue, from which tasks are usually removed;
but, with some probability, threads also attempt to steal higher-priority tasks
from the other queues---and task batching, that is, the processing of several
tasks in a single insert / remove step. These ideas are well-known for task scheduling
without priorities; our theoretical contribution is showing that, despite relaxations,
this design can still provide rank guarantees, which in turn implies bounds on
total work performed. We provide a general SMQ implementation which can surpass
state-of-the-art schedulers such as OBIM and PMOD in terms of performance on popular
graph-processing benchmarks. Notably, the performance improvement comes mainly
from the superior rank guarantees provided by our scheduler, confirming that analytically-reasoned
approaches can still provide performance improvements for priority task scheduling."
acknowledgement: We would like to thank the anonymous reviewers for their useful comments.
This project has received funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (grant agreement
No 805223 ScaleML).
article_processing_charge: No
arxiv: 1
author:
- first_name: Anastasiia
full_name: Postnikova, Anastasiia
last_name: Postnikova
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
- 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: 'Postnikova A, Koval N, Nadiradze G, Alistarh D-A. Multi-queues can be state-of-the-art
priority schedulers. In: Proceedings of the 27th ACM SIGPLAN Symposium on Principles
and Practice of Parallel Programming. Association for Computing Machinery;
2022:353-367. doi:10.1145/3503221.3508432'
apa: 'Postnikova, A., Koval, N., Nadiradze, G., & Alistarh, D.-A. (2022). Multi-queues
can be state-of-the-art priority schedulers. In Proceedings of the 27th ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp.
353–367). Seoul, Republic of Korea: Association for Computing Machinery. https://doi.org/10.1145/3503221.3508432'
chicago: Postnikova, Anastasiia, Nikita Koval, Giorgi Nadiradze, and Dan-Adrian
Alistarh. “Multi-Queues Can Be State-of-the-Art Priority Schedulers.” In Proceedings
of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
353–67. Association for Computing Machinery, 2022. https://doi.org/10.1145/3503221.3508432.
ieee: A. Postnikova, N. Koval, G. Nadiradze, and D.-A. Alistarh, “Multi-queues can
be state-of-the-art priority schedulers,” in Proceedings of the 27th ACM SIGPLAN
Symposium on Principles and Practice of Parallel Programming, Seoul, Republic
of Korea, 2022, pp. 353–367.
ista: 'Postnikova A, Koval N, Nadiradze G, Alistarh D-A. 2022. Multi-queues can
be state-of-the-art priority schedulers. Proceedings of the 27th ACM SIGPLAN Symposium
on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles
and Practice of Parallel Programming, 353–367.'
mla: Postnikova, Anastasiia, et al. “Multi-Queues Can Be State-of-the-Art Priority
Schedulers.” Proceedings of the 27th ACM SIGPLAN Symposium on Principles and
Practice of Parallel Programming, Association for Computing Machinery, 2022,
pp. 353–67, doi:10.1145/3503221.3508432.
short: A. Postnikova, N. Koval, G. Nadiradze, D.-A. Alistarh, in:, Proceedings of
the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
Association for Computing Machinery, 2022, pp. 353–367.
conference:
end_date: 2022-04-06
location: Seoul, Republic of Korea
name: 'PPoPP: Sympopsium on Principles and Practice of Parallel Programming'
start_date: 2022-04-02
date_created: 2022-04-17T22:01:46Z
date_published: 2022-04-02T00:00:00Z
date_updated: 2023-08-03T06:48:35Z
day: '02'
department:
- _id: DaAl
doi: 10.1145/3503221.3508432
ec_funded: 1
external_id:
arxiv:
- '2109.00657'
isi:
- '000883318200025'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2109.00657'
month: '04'
oa: 1
oa_version: Preprint
page: 353-367
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice
of Parallel Programming
publication_identifier:
isbn:
- '9781450392044'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '13076'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Multi-queues can be state-of-the-art priority schedulers
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2022'
...
---
_id: '11181'
abstract:
- lang: eng
text: 'To maximize the performance of concurrent data structures, researchers have
often turned to highly complex fine-grained techniques, resulting in efficient
and elegant algorithms, which can however be often difficult to understand and
prove correct. While simpler techniques exist, such as transactional memory, they
can have limited performance or portability relative to their fine-grained counterparts.
Approaches at both ends of this complexity-performance spectrum have been extensively
explored, but relatively less is known about the middle ground: approaches that
are willing to sacrifice some performance for simplicity, while remaining competitive
with state-of-the-art handcrafted designs. In this paper, we explore this middle
ground, and present PathCAS, a primitive that combines ideas from multi-word CAS
(KCAS) and transactional memory approaches, while carefully avoiding overhead.
We show how PathCAS can be used to implement efficient search data structures
relatively simply, using an internal binary search tree as an example, then extending
this to an AVL tree. Our best implementations outperform many handcrafted search
trees: in search-heavy workloads, it rivals the BCCO tree [5], the fastest known
concurrent binary tree in terms of search performance [3]. Our results suggest
that PathCAS can yield concurrent data structures that are relatively easy to
build and prove correct, while offering surprisingly high performance.'
acknowledgement: "This work was supported by: the Natural Sciences and Engineering
Research Council of Canada (NSERC) Collaborative Research and Development grant:
CRDPJ 539431-19, the\r\nCanada Foundation for Innovation John R. Evans Leaders Fund
with equal support from the Ontario Research Fund CFI Leaders Opportunity Fund:
38512, Waterloo Huawei Joint Innovation Lab project “Scalable Infrastructure for
Next Generation Data Management Systems”, NSERC Discovery Launch Supplement: DGECR-2019-00048,
NSERC Discovery\r\nProgram under the grants: RGPIN-2019-04227 and RGPIN04512-2018,
and the University of Waterloo. We would also like to thank the reviewers for their
insightful comments."
article_processing_charge: No
author:
- first_name: Trevor A
full_name: Brown, Trevor A
id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
last_name: Brown
- first_name: William
full_name: Sigouin, William
last_name: Sigouin
- 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: 'Brown TA, Sigouin W, Alistarh D-A. PathCAS: An efficient middle ground for
concurrent search data structures. In: Proceedings of the 27th ACM SIGPLAN
Symposium on Principles and Practice of Parallel Programming. Association
for Computing Machinery; 2022:385-399. doi:10.1145/3503221.3508410'
apa: 'Brown, T. A., Sigouin, W., & Alistarh, D.-A. (2022). PathCAS: An efficient
middle ground for concurrent search data structures. In Proceedings of the
27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
(pp. 385–399). Seoul, Republic of Korea: Association for Computing Machinery.
https://doi.org/10.1145/3503221.3508410'
chicago: 'Brown, Trevor A, William Sigouin, and Dan-Adrian Alistarh. “PathCAS: An
Efficient Middle Ground for Concurrent Search Data Structures.” In Proceedings
of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
385–99. Association for Computing Machinery, 2022. https://doi.org/10.1145/3503221.3508410.'
ieee: 'T. A. Brown, W. Sigouin, and D.-A. Alistarh, “PathCAS: An efficient middle
ground for concurrent search data structures,” in Proceedings of the 27th ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming, Seoul,
Republic of Korea, 2022, pp. 385–399.'
ista: 'Brown TA, Sigouin W, Alistarh D-A. 2022. PathCAS: An efficient middle ground
for concurrent search data structures. Proceedings of the 27th ACM SIGPLAN Symposium
on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles
and Practice of Parallel Programming, 385–399.'
mla: 'Brown, Trevor A., et al. “PathCAS: An Efficient Middle Ground for Concurrent
Search Data Structures.” Proceedings of the 27th ACM SIGPLAN Symposium on Principles
and Practice of Parallel Programming, Association for Computing Machinery,
2022, pp. 385–99, doi:10.1145/3503221.3508410.'
short: T.A. Brown, W. Sigouin, D.-A. Alistarh, in:, Proceedings of the 27th ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association
for Computing Machinery, 2022, pp. 385–399.
conference:
end_date: 2022-04-06
location: Seoul, Republic of Korea
name: 'PPoPP: Sympopsium on Principles and Practice of Parallel Programming'
start_date: 2022-04-02
date_created: 2022-04-17T22:01:46Z
date_published: 2022-04-02T00:00:00Z
date_updated: 2023-08-03T06:49:20Z
day: '02'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3503221.3508410
external_id:
isi:
- '000883318200027'
file:
- access_level: open_access
checksum: 8ceea411fa133795cd4903529498eb6b
content_type: application/pdf
creator: dernst
date_created: 2022-08-05T09:19:29Z
date_updated: 2022-08-05T09:19:29Z
file_id: '11731'
file_name: 2022_PPoPP_Brown.pdf
file_size: 1128343
relation: main_file
success: 1
file_date_updated: 2022-08-05T09:19:29Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 385-399
publication: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice
of Parallel Programming
publication_identifier:
isbn:
- '9781450392044'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'PathCAS: An efficient middle ground for concurrent search data structures'
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2022'
...
---
_id: '11183'
abstract:
- lang: eng
text: "Subgraph detection has recently been one of the most studied problems in
the CONGEST model of distributed computing. In this work, we study the distributed
complexity of problems closely related to subgraph detection, mainly focusing
on induced subgraph detection. The main line of this work presents lower bounds
and parameterized algorithms w.r.t structural parameters of the input graph:\r\n-
On general graphs, we give unconditional lower bounds for induced detection of
cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions
from centralized parameterized complexity, we prove lower bounds in CONGEST for
detecting patterns with a 4-clique, and for induced path detection conditional
on the hardness of triangle detection in the congested clique.\r\n- On graphs
of bounded degeneracy, we show that induced paths can be detected fast in CONGEST
using techniques from parameterized algorithms, while detecting cycles and patterns
of treewidth 2 is hard.\r\n- On graphs of bounded vertex cover number, we show
that induced subgraph detection is easy in CONGEST for any pattern graph. More
specifically, we adapt a centralized parameterized algorithm for a more general
maximum common induced subgraph detection problem to the distributed setting.
In addition to these induced subgraph detection results, we study various related
problems in the CONGEST and congested clique models, including for multicolored
versions of subgraph-detection-like problems."
acknowledgement: "Amir Nikabadi: Supported by the LABEX MILYON (ANR-10-LABX-0070)
of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007)
operated by the French National Research Agency (ANR). Janne H. Korhonen: Supported
by the European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme (grant agreement No 805223 ScaleML).\r\nWe thank François
Le Gall and Masayuki Miyamoto for sharing their work on lower bounds for induced
subgraph detection [36]."
alternative_title:
- LIPIcs
article_number: '15'
article_processing_charge: No
author:
- first_name: Amir
full_name: Nikabadi, Amir
last_name: Nikabadi
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
citation:
ama: 'Nikabadi A, Korhonen J. Beyond distributed subgraph detection: Induced subgraphs,
multicolored problems and graph parameters. In: Bramas Q, Gramoli V, Milani A,
eds. 25th International Conference on Principles of Distributed Systems.
Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.OPODIS.2021.15'
apa: 'Nikabadi, A., & Korhonen, J. (2022). Beyond distributed subgraph detection:
Induced subgraphs, multicolored problems and graph parameters. In Q. Bramas, V.
Gramoli, & A. Milani (Eds.), 25th International Conference on Principles
of Distributed Systems (Vol. 217). Strasbourg, France: Schloss Dagstuhl -
Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.15'
chicago: 'Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection:
Induced Subgraphs, Multicolored Problems and Graph Parameters.” In 25th International
Conference on Principles of Distributed Systems, edited by Quentin Bramas,
Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.15.'
ieee: 'A. Nikabadi and J. Korhonen, “Beyond distributed subgraph detection: Induced
subgraphs, multicolored problems and graph parameters,” in 25th International
Conference on Principles of Distributed Systems, Strasbourg, France, 2022,
vol. 217.'
ista: 'Nikabadi A, Korhonen J. 2022. Beyond distributed subgraph detection: Induced
subgraphs, multicolored problems and graph parameters. 25th International Conference
on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 15.'
mla: 'Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection:
Induced Subgraphs, Multicolored Problems and Graph Parameters.” 25th International
Conference on Principles of Distributed Systems, edited by Quentin Bramas
et al., vol. 217, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
doi:10.4230/LIPIcs.OPODIS.2021.15.'
short: A. Nikabadi, J. Korhonen, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th
International Conference on Principles of Distributed Systems, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2021-12-15
location: Strasbourg, France
name: OPODIS
start_date: 2021-12-13
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2022-05-02T07:56:35Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.15
ec_funded: 1
editor:
- first_name: Quentin
full_name: Bramas, Quentin
last_name: Bramas
- first_name: Vincent
full_name: Gramoli, Vincent
last_name: Gramoli
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
file:
- access_level: open_access
checksum: 626551c14de5d4091573200ed0535752
content_type: application/pdf
creator: dernst
date_created: 2022-05-02T07:53:00Z
date_updated: 2022-05-02T07:53:00Z
file_id: '11345'
file_name: 2022_LIPICs_Nikabadi.pdf
file_size: 790396
relation: main_file
success: 1
file_date_updated: 2022-05-02T07:53:00Z
has_accepted_license: '1'
intvolume: ' 217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
isbn:
- '9783959772198'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Beyond distributed subgraph detection: Induced subgraphs, multicolored problems
and graph parameters'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 217
year: '2022'
...
---
_id: '11184'
abstract:
- lang: eng
text: "Let G be a graph on n nodes. In the stochastic population protocol model,
a collection of n indistinguishable, resource-limited nodes collectively solve
tasks via pairwise interactions. In each interaction, two randomly chosen neighbors
first read each other’s states, and then update their local states. A rich line
of research has established tight upper and lower bounds on the complexity of
fundamental tasks, such as majority and leader election, in this model, when G
is a clique. Specifically, in the clique, these tasks can be solved fast, i.e.,
in n polylog n pairwise interactions, with high probability, using at most polylog
n states per node.\r\nIn this work, we consider the more general setting where
G is an arbitrary regular graph, and present a technique for simulating protocols
designed for fully-connected networks in any connected regular graph. Our main
result is a simulation that is efficient on many interesting graph families: roughly,
the simulation overhead is polylogarithmic in the number of nodes, and quadratic
in the conductance of the graph. As a sample application, we show that, in any
regular graph with conductance φ, both leader election and exact majority can
be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability,
using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast
and space-efficient population protocols for leader election and exact majority
on graphs with good expansion properties. We believe our results will prove generally
useful, as they allow efficient technology transfer between the well-mixed (clique)
case, and the under-explored spatial setting."
acknowledgement: "Dan Alistarh: This project has received funding from the European
Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation
programme (grant agreement No.805223 ScaleML).\r\nJoel Rybicki: This project has
received from the European Union’s Horizon 2020 research and\r\ninnovation programme
under the Marie Skłodowska-Curie grant agreement No. 840605.\r\nAcknowledgements
We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock
construction to non-regular graphs. We also thank anonymous reviewers for their
useful comments on earlier versions of this manuscript."
alternative_title:
- LIPIcs
article_number: '14'
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: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Alistarh D-A, Gelashvili R, Rybicki J. Fast graphical population protocols.
In: Bramas Q, Gramoli V, Milani A, eds. 25th International Conference on Principles
of Distributed Systems. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2022. doi:10.4230/LIPIcs.OPODIS.2021.14'
apa: 'Alistarh, D.-A., Gelashvili, R., & Rybicki, J. (2022). Fast graphical
population protocols. In Q. Bramas, V. Gramoli, & A. Milani (Eds.), 25th
International Conference on Principles of Distributed Systems (Vol. 217).
Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14'
chicago: Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Fast Graphical
Population Protocols.” In 25th International Conference on Principles of Distributed
Systems, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol.
217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14.
ieee: D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Fast graphical population
protocols,” in 25th International Conference on Principles of Distributed Systems,
Strasbourg, France, 2022, vol. 217.
ista: Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols.
25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs,
vol. 217, 14.
mla: Alistarh, Dan-Adrian, et al. “Fast Graphical Population Protocols.” 25th
International Conference on Principles of Distributed Systems, edited by Quentin
Bramas et al., vol. 217, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022, doi:10.4230/LIPIcs.OPODIS.2021.14.
short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, Q. Bramas, V. Gramoli, A.
Milani (Eds.), 25th International Conference on Principles of Distributed Systems,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2021-12-15
location: Strasbourg, France
name: OPODIS
start_date: 2021-12-13
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2022-05-02T08:09:39Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.14
ec_funded: 1
editor:
- first_name: Quentin
full_name: Bramas, Quentin
last_name: Bramas
- first_name: Vincent
full_name: Gramoli, Vincent
last_name: Gramoli
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
external_id:
arxiv:
- '2102.08808'
file:
- access_level: open_access
checksum: 2c7c982174c6f98c4ca6e92539d15086
content_type: application/pdf
creator: dernst
date_created: 2022-05-02T08:06:33Z
date_updated: 2022-05-02T08:06:33Z
file_id: '11346'
file_name: 2022_LIPICs_Alistarh.pdf
file_size: 959406
relation: main_file
success: 1
file_date_updated: 2022-05-02T08:06:33Z
has_accepted_license: '1'
intvolume: ' 217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
isbn:
- '9783959772198'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast graphical population protocols
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 217
year: '2022'
...
---
_id: '11420'
abstract:
- lang: eng
text: 'Understanding the properties of neural networks trained via stochastic gradient
descent (SGD) is at the heart of the theory of deep learning. In this work, we
take a mean-field view, and consider a two-layer ReLU network trained via noisy-SGD
for a univariate regularized regression problem. Our main result is that SGD with
vanishingly small noise injected in the gradients is biased towards a simple solution:
at convergence, the ReLU network implements a piecewise linear map of the inputs,
and the number of “knot” points -- i.e., points where the tangent of the ReLU
network estimator changes -- between two consecutive training inputs is at most
three. In particular, as the number of neurons of the network grows, the SGD dynamics
is captured by the solution of a gradient flow and, at convergence, the distribution
of the weights approaches the unique minimizer of a related free energy, which
has a Gibbs form. Our key technical contribution consists in the analysis of the
estimator resulting from this minimizer: we show that its second derivative vanishes
everywhere, except at some specific locations which represent the “knot” points.
We also provide empirical evidence that knots at locations distinct from the data
points might occur, as predicted by our theory.'
acknowledgement: "We would like to thank Mert Pilanci for several exploratory discussions
in the early stage\r\nof the project, Jan Maas for clarifications about Jordan et
al. (1998), and Max Zimmer for\r\nsuggestive numerical experiments. A. Shevchenko
and M. Mondelli are partially supported\r\nby the 2019 Lopez-Loreta Prize. V. Kungurtsev
acknowledges support to the OP VVV\r\nproject CZ.02.1.01/0.0/0.0/16 019/0000765
Research Center for Informatics.\r\n"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Aleksandr
full_name: Shevchenko, Aleksandr
id: F2B06EC2-C99E-11E9-89F0-752EE6697425
last_name: Shevchenko
- first_name: Vyacheslav
full_name: Kungurtsev, Vyacheslav
last_name: Kungurtsev
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: Shevchenko A, Kungurtsev V, Mondelli M. Mean-field analysis of piecewise linear
solutions for wide ReLU networks. Journal of Machine Learning Research.
2022;23(130):1-55.
apa: Shevchenko, A., Kungurtsev, V., & Mondelli, M. (2022). Mean-field analysis
of piecewise linear solutions for wide ReLU networks. Journal of Machine Learning
Research. Journal of Machine Learning Research.
chicago: Shevchenko, Aleksandr, Vyacheslav Kungurtsev, and Marco Mondelli. “Mean-Field
Analysis of Piecewise Linear Solutions for Wide ReLU Networks.” Journal of
Machine Learning Research. Journal of Machine Learning Research, 2022.
ieee: A. Shevchenko, V. Kungurtsev, and M. Mondelli, “Mean-field analysis of piecewise
linear solutions for wide ReLU networks,” Journal of Machine Learning Research,
vol. 23, no. 130. Journal of Machine Learning Research, pp. 1–55, 2022.
ista: Shevchenko A, Kungurtsev V, Mondelli M. 2022. Mean-field analysis of piecewise
linear solutions for wide ReLU networks. Journal of Machine Learning Research.
23(130), 1–55.
mla: Shevchenko, Aleksandr, et al. “Mean-Field Analysis of Piecewise Linear Solutions
for Wide ReLU Networks.” Journal of Machine Learning Research, vol. 23,
no. 130, Journal of Machine Learning Research, 2022, pp. 1–55.
short: A. Shevchenko, V. Kungurtsev, M. Mondelli, Journal of Machine Learning Research
23 (2022) 1–55.
date_created: 2022-05-29T22:01:54Z
date_published: 2022-04-01T00:00:00Z
date_updated: 2024-09-10T13:03:17Z
day: '01'
ddc:
- '000'
department:
- _id: MaMo
- _id: DaAl
external_id:
arxiv:
- '2111.02278'
file:
- access_level: open_access
checksum: d4ff5d1affb34848b5c5e4002483fc62
content_type: application/pdf
creator: cchlebak
date_created: 2022-05-30T08:22:55Z
date_updated: 2022-05-30T08:22:55Z
file_id: '11422'
file_name: 21-1365.pdf
file_size: 1521701
relation: main_file
success: 1
file_date_updated: 2022-05-30T08:22:55Z
has_accepted_license: '1'
intvolume: ' 23'
issue: '130'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 1-55
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Journal of Machine Learning Research
publication_identifier:
eissn:
- 1533-7928
issn:
- 1532-4435
publication_status: published
publisher: Journal of Machine Learning Research
quality_controlled: '1'
related_material:
link:
- relation: other
url: https://www.jmlr.org/papers/v23/21-1365.html
scopus_import: '1'
status: public
title: Mean-field analysis of piecewise linear solutions for wide ReLU networks
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 23
year: '2022'
...
---
_id: '11707'
abstract:
- lang: eng
text: 'In this work we introduce the graph-theoretic notion of mendability: for
each locally checkable graph problem we can define its mending radius, which captures
the idea of how far one needs to modify a partial solution in order to “patch
a hole.” We explore how mendability is connected to the existence of efficient
algorithms, especially in distributed, parallel, and fault-tolerant settings.
It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds
in the LOCAL model of distributed computing. One of the surprises is that in paths
and cycles, a converse also holds in the following sense: if a problem Π can be
solved in O(log∗n), there is always a restriction Π′⊆Π that is still efficiently
solvable but that is also O(1)-mendable. We also explore the structure of the
landscape of mendability. For example, we show that in trees, the mending radius
of any locally checkable problem is O(1), Θ(logn), or Θ(n), while in general graphs
the structure is much more diverse.'
acknowledgement: This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 840605. This work was supported in part by the Academy of Finland, Grants 314888
and 333837. The authors would also like to thank David Harris, Neven Villani, and
the anonymous reviewers for their very helpful comments and feedback on previous
versions of this work.
article_processing_charge: No
arxiv: 1
author:
- first_name: Alkida
full_name: Balliu, Alkida
last_name: Balliu
- first_name: Juho
full_name: Hirvonen, Juho
last_name: Hirvonen
- first_name: Darya
full_name: Melnyk, Darya
last_name: Melnyk
- first_name: Dennis
full_name: Olivetti, Dennis
last_name: Olivetti
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
citation:
ama: 'Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. Local mending.
In: Parter M, ed. International Colloquium on Structural Information and Communication
Complexity. Vol 13298. LNCS. Springer Nature; 2022:1-20. doi:10.1007/978-3-031-09993-9_1'
apa: 'Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., & Suomela,
J. (2022). Local mending. In M. Parter (Ed.), International Colloquium on Structural
Information and Communication Complexity (Vol. 13298, pp. 1–20). Paderborn,
Germany: Springer Nature. https://doi.org/10.1007/978-3-031-09993-9_1'
chicago: Balliu, Alkida, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki,
and Jukka Suomela. “Local Mending.” In International Colloquium on Structural
Information and Communication Complexity, edited by Merav Parter, 13298:1–20.
LNCS. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-09993-9_1.
ieee: A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, and J. Suomela,
“Local mending,” in International Colloquium on Structural Information and
Communication Complexity, Paderborn, Germany, 2022, vol. 13298, pp. 1–20.
ista: 'Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. 2022. Local
mending. International Colloquium on Structural Information and Communication
Complexity. SIROCCO: Structural Information and Communication ComplexityLNCS vol.
13298, 1–20.'
mla: Balliu, Alkida, et al. “Local Mending.” International Colloquium on Structural
Information and Communication Complexity, edited by Merav Parter, vol. 13298,
Springer Nature, 2022, pp. 1–20, doi:10.1007/978-3-031-09993-9_1.
short: A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, J. Suomela, in:,
M. Parter (Ed.), International Colloquium on Structural Information and Communication
Complexity, Springer Nature, 2022, pp. 1–20.
conference:
end_date: 2022-06-29
location: Paderborn, Germany
name: 'SIROCCO: Structural Information and Communication Complexity'
start_date: 2022-06-27
date_created: 2022-07-31T22:01:49Z
date_published: 2022-06-25T00:00:00Z
date_updated: 2023-08-03T12:16:29Z
day: '25'
department:
- _id: DaAl
doi: 10.1007/978-3-031-09993-9_1
ec_funded: 1
editor:
- first_name: Merav
full_name: Parter, Merav
last_name: Parter
external_id:
arxiv:
- '2102.08703'
isi:
- '000876977400001'
intvolume: ' 13298'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2102.08703
month: '06'
oa: 1
oa_version: Preprint
page: 1-20
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: International Colloquium on Structural Information and Communication
Complexity
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031099922'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Local mending
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13298
year: '2022'
...
---
_id: '11844'
abstract:
- lang: eng
text: "In the stochastic population protocol model, we are given a connected graph
with n nodes, and in every time step, a scheduler samples an edge of the graph
uniformly at random and the nodes connected by this edge interact. A fundamental
task in this model is stable leader election, in which all nodes start in an identical
state and the aim is to reach a configuration in which (1) exactly one node is
elected as leader and (2) this node remains as the unique leader no matter what
sequence of interactions follows. On cliques, the complexity of this problem has
recently been settled: time-optimal protocols stabilize in Θ(n log n) expected
steps using Θ(log log n) states, whereas protocols that use O(1) states require
Θ(n2) expected steps.\r\n\r\nIn this work, we investigate the complexity of stable
leader election on general graphs. We provide the first non-trivial time lower
bounds for leader election on general graphs, showing that, when moving beyond
cliques, the complexity landscape of leader election becomes very diverse: the
time required to elect a leader can range from O(1) to Θ(n3) expected steps. On
the upper bound side, we first observe that there exists a protocol that is time-optimal
on many graph families, but uses polynomially-many states. In contrast, we give
a near-time-optimal protocol that uses only O(log2n) states that is at most a
factor log n slower. Finally, we show that the constant-state protocol of Beauquier
et al. [OPODIS 2013] is at most a factor n log n slower than the fast polynomial-state
protocol. Moreover, among constant-state protocols, this protocol has near-optimal
average case complexity on dense random graphs."
acknowledgement: We thank the anonymous reviewers for their helpful comments. We gratefully
acknowledge funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No 805223
ScaleML).
article_processing_charge: Yes (via OA deal)
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: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Sasha
full_name: Voitovych, Sasha
last_name: Voitovych
citation:
ama: 'Alistarh D-A, Rybicki J, Voitovych S. Near-optimal leader election in population
protocols on graphs. In: Proceedings of the Annual ACM Symposium on Principles
of Distributed Computing. Association for Computing Machinery; 2022:246-256.
doi:10.1145/3519270.3538435'
apa: 'Alistarh, D.-A., Rybicki, J., & Voitovych, S. (2022). Near-optimal leader
election in population protocols on graphs. In Proceedings of the Annual ACM
Symposium on Principles of Distributed Computing (pp. 246–256). Salerno, Italy:
Association for Computing Machinery. https://doi.org/10.1145/3519270.3538435'
chicago: Alistarh, Dan-Adrian, Joel Rybicki, and Sasha Voitovych. “Near-Optimal
Leader Election in Population Protocols on Graphs.” In Proceedings of the Annual
ACM Symposium on Principles of Distributed Computing, 246–56. Association
for Computing Machinery, 2022. https://doi.org/10.1145/3519270.3538435.
ieee: D.-A. Alistarh, J. Rybicki, and S. Voitovych, “Near-optimal leader election
in population protocols on graphs,” in Proceedings of the Annual ACM Symposium
on Principles of Distributed Computing, Salerno, Italy, 2022, pp. 246–256.
ista: 'Alistarh D-A, Rybicki J, Voitovych S. 2022. Near-optimal leader election
in population protocols on graphs. Proceedings of the Annual ACM Symposium on
Principles of Distributed Computing. PODC: Symposium on Principles of Distributed
Computing, 246–256.'
mla: Alistarh, Dan-Adrian, et al. “Near-Optimal Leader Election in Population Protocols
on Graphs.” Proceedings of the Annual ACM Symposium on Principles of Distributed
Computing, Association for Computing Machinery, 2022, pp. 246–56, doi:10.1145/3519270.3538435.
short: D.-A. Alistarh, J. Rybicki, S. Voitovych, in:, Proceedings of the Annual
ACM Symposium on Principles of Distributed Computing, Association for Computing
Machinery, 2022, pp. 246–256.
conference:
end_date: 2022-07-29
location: Salerno, Italy
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2022-07-25
date_created: 2022-08-14T22:01:46Z
date_published: 2022-07-21T00:00:00Z
date_updated: 2023-06-14T12:06:01Z
day: '21'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3519270.3538435
ec_funded: 1
external_id:
arxiv:
- '2205.12597'
file:
- access_level: open_access
checksum: 4c6b29172b8e355b4fbc364a2e0827b2
content_type: application/pdf
creator: cchlebak
date_created: 2022-08-16T08:05:15Z
date_updated: 2022-08-16T08:05:15Z
file_id: '11854'
file_name: 2022_PODC_Alistarh.pdf
file_size: 1593474
relation: main_file
success: 1
file_date_updated: 2022-08-16T08:05:15Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 246-256
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the Annual ACM Symposium on Principles of Distributed
Computing
publication_identifier:
isbn:
- '9781450392624'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Near-optimal leader election in population protocols 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '13147'
abstract:
- lang: eng
text: "We investigate fast and communication-efficient algorithms for the classic
problem of minimizing a sum of strongly convex and smooth functions that are distributed
among n\r\n different nodes, which can communicate using a limited number of bits.
Most previous communication-efficient approaches for this problem are limited
to first-order optimization, and therefore have \\emph{linear} dependence on the
condition number in their communication complexity. We show that this dependence
is not inherent: communication-efficient methods can in fact have sublinear dependence
on the condition number. For this, we design and analyze the first communication-efficient
distributed variants of preconditioned gradient descent for Generalized Linear
Models, and for Newton’s method. Our results rely on a new technique for quantizing
both the preconditioner and the descent direction at each step of the algorithms,
while controlling their convergence rate. We also validate our findings experimentally,
showing faster convergence and reduced communication relative to previous methods."
acknowledgement: The authors would like to thank Janne Korhonen, Aurelien Lucchi,
Celestine MendlerDunner and Antonio Orvieto for helpful discussions. FA ¨and DA
were supported during this work by the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant agreement
No 805223 ScaleML). PD was supported by the European Union’s Horizon 2020 programme
under the Marie Skłodowska-Curie grant agreement No. 754411.
article_processing_charge: No
arxiv: 1
author:
- first_name: Foivos
full_name: Alimisis, Foivos
last_name: Alimisis
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- 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: 'Alimisis F, Davies P, Alistarh D-A. Communication-efficient distributed optimization
with quantized preconditioners. In: Proceedings of the 38th International Conference
on Machine Learning. Vol 139. ML Research Press; 2021:196-206.'
apa: 'Alimisis, F., Davies, P., & Alistarh, D.-A. (2021). Communication-efficient
distributed optimization with quantized preconditioners. In Proceedings of
the 38th International Conference on Machine Learning (Vol. 139, pp. 196–206).
Virtual: ML Research Press.'
chicago: Alimisis, Foivos, Peter Davies, and Dan-Adrian Alistarh. “Communication-Efficient
Distributed Optimization with Quantized Preconditioners.” In Proceedings of
the 38th International Conference on Machine Learning, 139:196–206. ML Research
Press, 2021.
ieee: F. Alimisis, P. Davies, and D.-A. Alistarh, “Communication-efficient distributed
optimization with quantized preconditioners,” in Proceedings of the 38th International
Conference on Machine Learning, Virtual, 2021, vol. 139, pp. 196–206.
ista: Alimisis F, Davies P, Alistarh D-A. 2021. Communication-efficient distributed
optimization with quantized preconditioners. Proceedings of the 38th International
Conference on Machine Learning. International Conference on Machine Learning vol.
139, 196–206.
mla: Alimisis, Foivos, et al. “Communication-Efficient Distributed Optimization
with Quantized Preconditioners.” Proceedings of the 38th International Conference
on Machine Learning, vol. 139, ML Research Press, 2021, pp. 196–206.
short: F. Alimisis, P. Davies, D.-A. Alistarh, in:, Proceedings of the 38th International
Conference on Machine Learning, ML Research Press, 2021, pp. 196–206.
conference:
end_date: 2021-07-24
location: Virtual
name: International Conference on Machine Learning
start_date: 2021-07-18
date_created: 2023-06-18T22:00:48Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2023-06-19T10:44:38Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2102.07214'
file:
- access_level: open_access
checksum: 7ec0d59bac268b49c76bf2e036dedd7a
content_type: application/pdf
creator: dernst
date_created: 2023-06-19T10:41:05Z
date_updated: 2023-06-19T10:41:05Z
file_id: '13154'
file_name: 2021_PMLR_Alimisis.pdf
file_size: 429087
relation: main_file
success: 1
file_date_updated: 2023-06-19T10:41:05Z
has_accepted_license: '1'
intvolume: ' 139'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 196-206
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 38th International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
isbn:
- '9781713845065'
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Communication-efficient distributed optimization with quantized preconditioners
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 139
year: '2021'
...
---
_id: '8286'
abstract:
- lang: eng
text: "We consider the following dynamic load-balancing process: given an underlying
graph G with n nodes, in each step t≥ 0, one unit of load is created, and placed
at a randomly chosen graph node. In the same step, the chosen node picks a random
neighbor, and the two nodes balance their loads by averaging them. We are interested
in the expected gap between the minimum and maximum loads at nodes as the process
progresses, and its dependence on n and on the graph structure. Variants of the
above graphical balanced allocation process have been studied previously by Peres,
Talwar, and Wieder [Peres et al., 2015], and by Sauerwald and Sun [Sauerwald and
Sun, 2015]. These authors left as open the question of characterizing the gap
in the case of cycle graphs in the dynamic case, where weights are created during
the algorithm’s execution. For this case, the only known upper bound is of \U0001D4AA(n
log n), following from a majorization argument due to [Peres et al., 2015], which
analyzes a related graphical allocation process. In this paper, we provide an
upper bound of \U0001D4AA (√n log n) on the expected gap of the above process
for cycles of length n. We introduce a new potential analysis technique, which
enables us to bound the difference in load between k-hop neighbors on the cycle,
for any k ≤ n/2. We complement this with a \"gap covering\" argument, which bounds
the maximum value of the gap by bounding its value across all possible subsets
of a certain structure, and recursively bounding the gaps within each subset.
We provide analytical and experimental evidence that our upper bound on the gap
is tight up to a logarithmic factor. "
acknowledgement: The authors sincerely thank Thomas Sauerwald and George Giakkoupis
for insightful discussions, and Mohsen Ghaffari, Yuval Peres, and Udi Wieder for
feedback on earlier versions of this draft. We also thank the ICALP anonymous reviewers
for their very useful comments. Open access funding provided by Institute of Science
and Technology (IST Austria). Funding was provided by European Research Council
(Grant No. PR1042ERC01).
article_processing_charge: Yes (via OA deal)
article_type: original
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: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
orcid: 0000-0001-5634-0731
- first_name: Amirmojtaba
full_name: Sabour, Amirmojtaba
id: bcc145fd-e77f-11ea-ae8b-80d661dbff67
last_name: Sabour
citation:
ama: Alistarh D-A, Nadiradze G, Sabour A. Dynamic averaging load balancing on cycles.
Algorithmica. 2021. doi:10.1007/s00453-021-00905-9
apa: 'Alistarh, D.-A., Nadiradze, G., & Sabour, A. (2021). Dynamic averaging
load balancing on cycles. Algorithmica. Virtual, Online; Germany: Springer
Nature. https://doi.org/10.1007/s00453-021-00905-9'
chicago: Alistarh, Dan-Adrian, Giorgi Nadiradze, and Amirmojtaba Sabour. “Dynamic
Averaging Load Balancing on Cycles.” Algorithmica. Springer Nature, 2021.
https://doi.org/10.1007/s00453-021-00905-9.
ieee: D.-A. Alistarh, G. Nadiradze, and A. Sabour, “Dynamic averaging load balancing
on cycles,” Algorithmica. Springer Nature, 2021.
ista: Alistarh D-A, Nadiradze G, Sabour A. 2021. Dynamic averaging load balancing
on cycles. Algorithmica.
mla: Alistarh, Dan-Adrian, et al. “Dynamic Averaging Load Balancing on Cycles.”
Algorithmica, Springer Nature, 2021, doi:10.1007/s00453-021-00905-9.
short: D.-A. Alistarh, G. Nadiradze, A. Sabour, Algorithmica (2021).
conference:
end_date: 2020-07-11
location: Virtual, Online; Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming '
start_date: 2020-07-08
date_created: 2020-08-24T06:24:04Z
date_published: 2021-12-24T00:00:00Z
date_updated: 2024-03-05T07:35:53Z
day: '24'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/s00453-021-00905-9
ec_funded: 1
external_id:
arxiv:
- '2003.09297'
isi:
- '000734004600001'
file:
- access_level: open_access
checksum: 21169b25b0c8e17b21e12af22bff9870
content_type: application/pdf
creator: cchlebak
date_created: 2021-12-27T10:36:40Z
date_updated: 2021-12-27T10:36:40Z
file_id: '10577'
file_name: 2021_Algorithmica_Alistarh.pdf
file_size: 525950
relation: main_file
success: 1
file_date_updated: 2021-12-27T10:36:40Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
link:
- relation: earlier_version
url: https://doi.org/10.4230/LIPIcs.ICALP.2020.7
record:
- id: '15077'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Dynamic averaging load balancing on cycles
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
year: '2021'
...
---
_id: '8723'
abstract:
- lang: eng
text: Deep learning at scale is dominated by communication time. Distributing samples
across nodes usually yields the best performance, but poses scaling challenges
due to global information dissemination and load imbalance across uneven sample
lengths. State-of-the-art decentralized optimizers mitigate the problem, but require
more iterations to achieve the same accuracy as their globally-communicating counterparts.
We present Wait-Avoiding Group Model Averaging (WAGMA) SGD, a wait-avoiding stochastic
optimizer that reduces global communication via subgroup weight exchange. The
key insight is a combination of algorithmic changes to the averaging scheme and
the use of a group allreduce operation. We prove the convergence of WAGMA-SGD,
and empirically show that it retains convergence rates similar to Allreduce-SGD.
For evaluation, we train ResNet-50 on ImageNet; Transformer for machine translation;
and deep reinforcement learning for navigation at scale. Compared with state-of-the-art
decentralized SGD variants, WAGMA-SGD significantly improves training throughput
(e.g., 2.1× on 1,024 GPUs for reinforcement learning), and achieves the fastest
time-to-solution (e.g., the highest score using the shortest training time for
Transformer).
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Hori-\r\nzon 2020 programme under Grant DAPP, Grant
678880; EPi-GRAM-HS, Grant 801039; and ERC Starting Grant ScaleML, Grant 805223.
The work of Tal Ben-Nun is supported by the Swiss National Science Foundation (Ambizione
Project No. 185778). The work of Nikoli Dryden is supported by the ETH Postdoctoral
Fellowship. The authors would like to thank the Swiss National Supercomputing Center
for providing the computing resources and technical support."
article_number: '9271898'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Shigang
full_name: Li, Shigang
last_name: Li
- first_name: Tal Ben-Nun
full_name: Tal Ben-Nun, Tal Ben-Nun
last_name: Tal Ben-Nun
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
- first_name: Salvatore Di
full_name: Girolamo, Salvatore Di
last_name: Girolamo
- first_name: Nikoli
full_name: Dryden, Nikoli
last_name: Dryden
- 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: Li S, Tal Ben-Nun TB-N, Nadiradze G, et al. Breaking (global) barriers in parallel
stochastic optimization with wait-avoiding group averaging. IEEE Transactions
on Parallel and Distributed Systems. 2021;32(7). doi:10.1109/TPDS.2020.3040606
apa: Li, S., Tal Ben-Nun, T. B.-N., Nadiradze, G., Girolamo, S. D., Dryden, N.,
Alistarh, D.-A., & Hoefler, T. (2021). Breaking (global) barriers in parallel
stochastic optimization with wait-avoiding group averaging. IEEE Transactions
on Parallel and Distributed Systems. IEEE. https://doi.org/10.1109/TPDS.2020.3040606
chicago: Li, Shigang, Tal Ben-Nun Tal Ben-Nun, Giorgi Nadiradze, Salvatore Di Girolamo,
Nikoli Dryden, Dan-Adrian Alistarh, and Torsten Hoefler. “Breaking (Global) Barriers
in Parallel Stochastic Optimization with Wait-Avoiding Group Averaging.” IEEE
Transactions on Parallel and Distributed Systems. IEEE, 2021. https://doi.org/10.1109/TPDS.2020.3040606.
ieee: S. Li et al., “Breaking (global) barriers in parallel stochastic optimization
with wait-avoiding group averaging,” IEEE Transactions on Parallel and Distributed
Systems, vol. 32, no. 7. IEEE, 2021.
ista: Li S, Tal Ben-Nun TB-N, Nadiradze G, Girolamo SD, Dryden N, Alistarh D-A,
Hoefler T. 2021. Breaking (global) barriers in parallel stochastic optimization
with wait-avoiding group averaging. IEEE Transactions on Parallel and Distributed
Systems. 32(7), 9271898.
mla: Li, Shigang, et al. “Breaking (Global) Barriers in Parallel Stochastic Optimization
with Wait-Avoiding Group Averaging.” IEEE Transactions on Parallel and Distributed
Systems, vol. 32, no. 7, 9271898, IEEE, 2021, doi:10.1109/TPDS.2020.3040606.
short: S. Li, T.B.-N. Tal Ben-Nun, G. Nadiradze, S.D. Girolamo, N. Dryden, D.-A.
Alistarh, T. Hoefler, IEEE Transactions on Parallel and Distributed Systems 32
(2021).
date_created: 2020-11-05T15:25:43Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2023-08-04T11:08:52Z
day: '01'
department:
- _id: DaAl
doi: 10.1109/TPDS.2020.3040606
ec_funded: 1
external_id:
arxiv:
- '2005.00124'
isi:
- '000621405200019'
intvolume: ' 32'
isi: 1
issue: '7'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2005.00124
month: '07'
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: IEEE Transactions on Parallel and Distributed Systems
publication_identifier:
issn:
- '10459219'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Breaking (global) barriers in parallel stochastic optimization with wait-avoiding
group averaging
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 32
year: '2021'
...
---
_id: '7939'
abstract:
- lang: eng
text: "We design fast deterministic algorithms for distance computation in the Congested
Clique model. Our key contributions include:\r\n A (2+ϵ)-approximation for
all-pairs shortest paths in O(log2n/ϵ) 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 from O(n−−√)
sources in O(log2n/ϵ) 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 O~(n1/6) rounds. "
acknowledgement: Open access funding provided by Institute of Science and Technology
(IST Austria). We thank Mohsen Ghaffari, Michael Elkin and Merav Parter for fruitful
discussions. This project has received funding from the European Union’s Horizon
2020 Research And Innovation Program under Grant Agreement No. 755839.
article_processing_charge: Yes (via OA deal)
article_type: original
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. Distributed Computing. 2021;34:463-487.
doi:10.1007/s00446-020-00380-5
apa: Censor-Hillel, K., Dory, M., Korhonen, J., & Leitersdorf, D. (2021). Fast
approximate shortest paths in the congested clique. Distributed Computing.
Springer Nature. https://doi.org/10.1007/s00446-020-00380-5
chicago: Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf.
“Fast Approximate Shortest Paths in the Congested Clique.” Distributed Computing.
Springer Nature, 2021. https://doi.org/10.1007/s00446-020-00380-5.
ieee: K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate
shortest paths in the congested clique,” Distributed Computing, vol. 34.
Springer Nature, pp. 463–487, 2021.
ista: Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2021. Fast approximate
shortest paths in the congested clique. Distributed Computing. 34, 463–487.
mla: Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested
Clique.” Distributed Computing, vol. 34, Springer Nature, 2021, pp. 463–87,
doi:10.1007/s00446-020-00380-5.
short: K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, Distributed Computing
34 (2021) 463–487.
date_created: 2020-06-07T22:00:54Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2024-03-07T14:43:39Z
day: '01'
department:
- _id: DaAl
doi: 10.1007/s00446-020-00380-5
external_id:
arxiv:
- '1903.05956'
isi:
- '000556444600001'
intvolume: ' 34'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s00446-020-00380-5
month: '12'
oa: 1
oa_version: Published Version
page: 463-487
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Distributed Computing
publication_identifier:
eissn:
- 1432-0452
issn:
- 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '6933'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Fast approximate shortest paths in the congested clique
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2021'
...
---
_id: '10049'
abstract:
- lang: eng
text: While messaging systems with strong security guarantees are widely used in
practice, designing a protocol that scales efficiently to large groups and enjoys
similar security guarantees remains largely open. The two existing proposals to
date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer
Security Protocol, draft). TreeKEM is the currently considered candidate by the
IETF MLS working group, but dynamic group operations (i.e. adding and removing
users) can cause efficiency issues. In this paper we formalize and analyze a variant
of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying
TTKEM was suggested by Millican (MLS mailing list, February 2018). This version
is more efficient than TreeKEM for some natural distributions of group operations,
we quantify this through simulations.Our second contribution is two security proofs
for TTKEM which establish post compromise and forward secrecy even against adaptive
attackers. The security loss (to the underlying PKE) in the Random Oracle Model
is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs
can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like
protocol establishing tight security against an adversary who can adaptively choose
the sequence of operations was known. We also are the first to prove (or even
formalize) active security where the server can arbitrarily deviate from the protocol
specification. Proving fully active security – where also the users can arbitrarily
deviate – remains open.
acknowledgement: The first three authors contributed equally to this work. Funded
by the European Research Council (ERC) under the European Union’s Horizon2020 research
and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No.665385.
article_processing_charge: No
author:
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Margarita
full_name: Capretto, Margarita
last_name: Capretto
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
- first_name: Ilia
full_name: Markov, Ilia
id: D0CF4148-C985-11E9-8066-0BDEE5697425
last_name: Markov
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM,
adaptively and actively secure continuous group key agreement. In: 2021 IEEE
Symposium on Security and Privacy . IEEE; 2021:268-284. doi:10.1109/sp40001.2021.00035'
apa: 'Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M.,
Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively
and actively secure continuous group key agreement. In 2021 IEEE Symposium
on Security and Privacy (pp. 268–284). San Francisco, CA, United States:
IEEE. https://doi.org/10.1109/sp40001.2021.00035'
chicago: 'Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath
Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo,
Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively
and Actively Secure Continuous Group Key Agreement.” In 2021 IEEE Symposium
on Security and Privacy , 268–84. IEEE, 2021. https://doi.org/10.1109/sp40001.2021.00035.'
ieee: 'K. Klein et al., “Keep the dirt: tainted TreeKEM, adaptively and actively
secure continuous group key agreement,” in 2021 IEEE Symposium on Security
and Privacy , San Francisco, CA, United States, 2021, pp. 268–284.'
ista: 'Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval
M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM,
adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium
on Security and Privacy . SP: Symposium on Security and Privacy, 268–284.'
mla: 'Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively
Secure Continuous Group Key Agreement.” 2021 IEEE Symposium on Security and
Privacy , IEEE, 2021, pp. 268–84, doi:10.1109/sp40001.2021.00035.'
short: K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M.
Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium
on Security and Privacy , IEEE, 2021, pp. 268–284.
conference:
end_date: 2021-05-27
location: San Francisco, CA, United States
name: 'SP: Symposium on Security and Privacy'
start_date: 2021-05-24
date_created: 2021-09-27T13:46:27Z
date_published: 2021-08-26T00:00:00Z
date_updated: 2023-09-07T13:32:11Z
day: '26'
department:
- _id: KrPi
- _id: DaAl
doi: 10.1109/sp40001.2021.00035
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/1489
month: '08'
oa: 1
oa_version: Preprint
page: 268-284
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: '2021 IEEE Symposium on Security and Privacy '
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '10035'
relation: dissertation_contains
status: public
status: public
title: 'Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous
group key agreement'
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10180'
abstract:
- lang: eng
text: The growing energy and performance costs of deep learning have driven the
community to reduce the size of neural networks by selectively pruning components.
Similarly to their biological counterparts, sparse networks generalize just as
well, sometimes even better than, the original dense networks. Sparsity promises
to reduce the memory footprint of regular networks to fit mobile devices, as well
as shorten training time for ever growing networks. In this paper, we survey prior
work on sparsity in deep learning and provide an extensive tutorial of sparsification
for both inference and training. We describe approaches to remove and add elements
of neural networks, different training strategies to achieve model sparsity, and
mechanisms to exploit sparsity in practice. Our work distills ideas from more
than 300 research papers and provides guidance to practitioners who wish to utilize
sparsity today, as well as to researchers whose goal is to push the frontier forward.
We include the necessary background on mathematical methods in sparsification,
describe phenomena such as early structure adaptation, the intricate relations
between sparsity and the training process, and show techniques for achieving acceleration
on real hardware. We also define a metric of pruned parameter efficiency that
could serve as a baseline for comparison of different sparse networks. We close
by speculating on how sparsity can improve future workloads and outline major
open problems in the field.
acknowledgement: "We thank Doug Burger, Steve Scott, Marco Heddes, and the respective
teams at Microsoft for inspiring discussions on the topic. We thank Angelika Steger
for uplifting debates about the connections to biological brains, Sidak Pal Singh
for his support regarding experimental results, and Utku Evci as well as Xin Wang
for comments on previous versions of this\r\nwork. Special thanks go to Bernhard
Schölkopf, our JMLR editor Samy Bengio, and the three anonymous reviewers who provided
excellent comprehensive, pointed, and deep review comments that improved the quality
of our manuscript significantly."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Torsten
full_name: Hoefler, Torsten
last_name: Hoefler
- 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: Tal
full_name: Ben-Nun, Tal
last_name: Ben-Nun
- first_name: Nikoli
full_name: Dryden, Nikoli
last_name: Dryden
- first_name: Elena-Alexandra
full_name: Peste, Elena-Alexandra
id: 32D78294-F248-11E8-B48F-1D18A9856A87
last_name: Peste
citation:
ama: 'Hoefler T, Alistarh D-A, Ben-Nun T, Dryden N, Peste E-A. Sparsity in deep
learning: Pruning and growth for efficient inference and training in neural networks.
Journal of Machine Learning Research. 2021;22(241):1-124.'
apa: 'Hoefler, T., Alistarh, D.-A., Ben-Nun, T., Dryden, N., & Peste, E.-A.
(2021). Sparsity in deep learning: Pruning and growth for efficient inference
and training in neural networks. Journal of Machine Learning Research.
Journal of Machine Learning Research.'
chicago: 'Hoefler, Torsten, Dan-Adrian Alistarh, Tal Ben-Nun, Nikoli Dryden, and
Elena-Alexandra Peste. “Sparsity in Deep Learning: Pruning and Growth for Efficient
Inference and Training in Neural Networks.” Journal of Machine Learning Research.
Journal of Machine Learning Research, 2021.'
ieee: 'T. Hoefler, D.-A. Alistarh, T. Ben-Nun, N. Dryden, and E.-A. Peste, “Sparsity
in deep learning: Pruning and growth for efficient inference and training in neural
networks,” Journal of Machine Learning Research, vol. 22, no. 241. Journal
of Machine Learning Research, pp. 1–124, 2021.'
ista: 'Hoefler T, Alistarh D-A, Ben-Nun T, Dryden N, Peste E-A. 2021. Sparsity in
deep learning: Pruning and growth for efficient inference and training in neural
networks. Journal of Machine Learning Research. 22(241), 1–124.'
mla: 'Hoefler, Torsten, et al. “Sparsity in Deep Learning: Pruning and Growth for
Efficient Inference and Training in Neural Networks.” Journal of Machine Learning
Research, vol. 22, no. 241, Journal of Machine Learning Research, 2021, pp.
1–124.'
short: T. Hoefler, D.-A. Alistarh, T. Ben-Nun, N. Dryden, E.-A. Peste, Journal of
Machine Learning Research 22 (2021) 1–124.
date_created: 2021-10-24T22:01:34Z
date_published: 2021-09-01T00:00:00Z
date_updated: 2022-05-13T09:36:08Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
external_id:
arxiv:
- '2102.00554'
file:
- access_level: open_access
checksum: 3389d9d01fc58f8fb4c1a53e14a8abbf
content_type: application/pdf
creator: cziletti
date_created: 2021-10-27T15:34:18Z
date_updated: 2021-10-27T15:34:18Z
file_id: '10192'
file_name: 2021_JMachLearnRes_Hoefler.pdf
file_size: 3527521
relation: main_file
success: 1
file_date_updated: 2021-10-27T15:34:18Z
has_accepted_license: '1'
intvolume: ' 22'
issue: '241'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.jmlr.org/papers/v22/21-0366.html
month: '09'
oa: 1
oa_version: Published Version
page: 1-124
publication: Journal of Machine Learning Research
publication_identifier:
eissn:
- 1533-7928
issn:
- 1532-4435
publication_status: published
publisher: Journal of Machine Learning Research
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Sparsity in deep learning: Pruning and growth for efficient inference and
training in neural networks'
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: 22
year: '2021'
...
---
_id: '10216'
abstract:
- lang: eng
text: 'This paper reports a new concurrent graph data structure that supports updates
of both edges and vertices and queries: Breadth-first search, Single-source shortest-path,
and Betweenness centrality. The operations are provably linearizable and non-blocking.'
acknowledgement: "This work was partially funded by National Supercomputing Mission,
Govt. of India under the project “Concurrent and Distributed Programming primitives
and algorithms for Temporal Graphs”(DST/NSM/R&D_Exascale/2021/16).\r\n"
alternative_title:
- LIPIcs
article_number: '52'
article_processing_charge: No
arxiv: 1
author:
- first_name: Bapi
full_name: Chatterjee, Bapi
id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
- first_name: Sathya
full_name: Peri, Sathya
last_name: Peri
- first_name: Muktikanta
full_name: Sa, Muktikanta
last_name: Sa
citation:
ama: 'Chatterjee B, Peri S, Sa M. Brief announcement: Non-blocking dynamic unbounded
graphs with worst-case amortized bounds. In: 35th International Symposium on
Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik;
2021. doi:10.4230/LIPIcs.DISC.2021.52'
apa: 'Chatterjee, B., Peri, S., & Sa, M. (2021). Brief announcement: Non-blocking
dynamic unbounded graphs with worst-case amortized bounds. In 35th International
Symposium on Distributed Computing (Vol. 209). Freiburg, Germany: Schloss
Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.52'
chicago: 'Chatterjee, Bapi, Sathya Peri, and Muktikanta Sa. “Brief Announcement:
Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” In 35th
International Symposium on Distributed Computing, Vol. 209. Schloss Dagstuhl
- Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.52.'
ieee: 'B. Chatterjee, S. Peri, and M. Sa, “Brief announcement: Non-blocking dynamic
unbounded graphs with worst-case amortized bounds,” in 35th International Symposium
on Distributed Computing, Freiburg, Germany, 2021, vol. 209.'
ista: 'Chatterjee B, Peri S, Sa M. 2021. Brief announcement: Non-blocking dynamic
unbounded graphs with worst-case amortized bounds. 35th International Symposium
on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 52.'
mla: 'Chatterjee, Bapi, et al. “Brief Announcement: Non-Blocking Dynamic Unbounded
Graphs with Worst-Case Amortized Bounds.” 35th International Symposium on Distributed
Computing, vol. 209, 52, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021, doi:10.4230/LIPIcs.DISC.2021.52.'
short: B. Chatterjee, S. Peri, M. Sa, in:, 35th International Symposium on Distributed
Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.
conference:
end_date: 2021-10-08
location: Freiburg, Germany
name: 'DISC: Distributed Computing'
start_date: 2021-10-04
date_created: 2021-11-07T23:01:23Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2021-11-12T09:42:55Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.52
external_id:
arxiv:
- '2003.01697'
file:
- access_level: open_access
checksum: 76546df112a0ba1166c864d33d7834e2
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T09:23:22Z
date_updated: 2021-11-12T09:23:22Z
file_id: '10276'
file_name: 2021_LIPIcsDISC_BChatterjee.pdf
file_size: 795860
relation: main_file
success: 1
file_date_updated: 2021-11-12T09:23:22Z
has_accepted_license: '1'
intvolume: ' 209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
publication: 35th International Symposium on Distributed Computing
publication_identifier:
isbn:
- 9-783-9597-7210-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Non-blocking dynamic unbounded graphs with worst-case
amortized bounds'
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 209
year: '2021'
...
---
_id: '10217'
abstract:
- lang: eng
text: This paper gives tight logarithmic lower bounds on the solo step complexity
of leader election in an asynchronous shared-memory model with single-writer multi-reader
(SWMR) registers, for both deterministic and randomized obstruction-free algorithms.
The approach extends to lower bounds for deterministic and randomized obstruction-free
algorithms using multi-writer registers under bounded write concurrency, showing
a trade-off between the solo step complexity of a leader election algorithm, and
the worst-case number of stalls incurred by a processor in an execution.
acknowledgement: "Dan Alistarh: Supported in part by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 805223 ScaleML). Giorgi Nadiradze: Supported in part by the
European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme (grant agreement No 805223 ScaleML). The authors would
like to thank the DISC anonymous reviewers for their useful\r\nfeedback and comments."
alternative_title:
- LIPIcs
article_number: '4'
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: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
citation:
ama: 'Alistarh D-A, Gelashvili R, Nadiradze G. Lower bounds for shared-memory leader
election under bounded write contention. In: 35th International Symposium on
Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik;
2021. doi:10.4230/LIPIcs.DISC.2021.4'
apa: 'Alistarh, D.-A., Gelashvili, R., & Nadiradze, G. (2021). Lower bounds
for shared-memory leader election under bounded write contention. In 35th International
Symposium on Distributed Computing (Vol. 209). Freiburg, Germany: Schloss
Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.4'
chicago: Alistarh, Dan-Adrian, Rati Gelashvili, and Giorgi Nadiradze. “Lower Bounds
for Shared-Memory Leader Election under Bounded Write Contention.” In 35th
International Symposium on Distributed Computing, Vol. 209. Schloss Dagstuhl
- Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.4.
ieee: D.-A. Alistarh, R. Gelashvili, and G. Nadiradze, “Lower bounds for shared-memory
leader election under bounded write contention,” in 35th International Symposium
on Distributed Computing, Freiburg, Germany, 2021, vol. 209.
ista: 'Alistarh D-A, Gelashvili R, Nadiradze G. 2021. Lower bounds for shared-memory
leader election under bounded write contention. 35th International Symposium on
Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 4.'
mla: Alistarh, Dan-Adrian, et al. “Lower Bounds for Shared-Memory Leader Election
under Bounded Write Contention.” 35th International Symposium on Distributed
Computing, vol. 209, 4, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021, doi:10.4230/LIPIcs.DISC.2021.4.
short: D.-A. Alistarh, R. Gelashvili, G. Nadiradze, in:, 35th International Symposium
on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.
conference:
end_date: 2021-10-08
location: Freiburg, Germany
name: 'DISC: Distributed Computing'
start_date: 2021-10-04
date_created: 2021-11-07T23:01:23Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2022-08-19T07:23:28Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.4
ec_funded: 1
file:
- access_level: open_access
checksum: b4cdc6668c899a601c5e6a96b8ca54d9
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T09:33:26Z
date_updated: 2021-11-12T09:33:26Z
file_id: '10277'
file_name: 2021_LIPIcsDISC_Alistarh.pdf
file_size: 706791
relation: main_file
success: 1
file_date_updated: 2021-11-12T09:33:26Z
has_accepted_license: '1'
intvolume: ' 209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 35th International Symposium on Distributed Computing
publication_identifier:
isbn:
- 9-783-9597-7210-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds for shared-memory leader election under bounded write contention
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 209
year: '2021'
...
---
_id: '10218'
abstract:
- lang: eng
text: 'Let G be a graph on n nodes. In the stochastic population protocol model,
a collection of n indistinguishable, resource-limited nodes collectively solve
tasks via pairwise interactions. In each interaction, two randomly chosen neighbors
first read each other’s states, and then update their local states. A rich line
of research has established tight upper and lower bounds on the complexity of
fundamental tasks, such as majority and leader election, in this model, when G
is a clique. Specifically, in the clique, these tasks can be solved fast, i.e.,
in n polylog n pairwise interactions, with high probability, using at most polylog
n states per node. In this work, we consider the more general setting where G
is an arbitrary graph, and present a technique for simulating protocols designed
for fully-connected networks in any connected regular graph. Our main result is
a simulation that is efficient on many interesting graph families: roughly, the
simulation overhead is polylogarithmic in the number of nodes, and quadratic in
the conductance of the graph. As an example, this implies that, in any regular
graph with conductance φ, both leader election and exact majority can be solved
in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at
most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient
population protocols for leader election and exact majority on graphs with good
expansion properties.'
acknowledgement: This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 840605.
alternative_title:
- LIPIcs
article_number: '43'
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: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Alistarh D-A, Gelashvili R, Rybicki J. Brief announcement: Fast graphical
population protocols. In: 35th International Symposium on Distributed Computing.
Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.43'
apa: 'Alistarh, D.-A., Gelashvili, R., & Rybicki, J. (2021). Brief announcement:
Fast graphical population protocols. In 35th International Symposium on Distributed
Computing (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.43'
chicago: 'Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Brief Announcement:
Fast Graphical Population Protocols.” In 35th International Symposium on Distributed
Computing, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
https://doi.org/10.4230/LIPIcs.DISC.2021.43.'
ieee: 'D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Brief announcement: Fast
graphical population protocols,” in 35th International Symposium on Distributed
Computing, Freiburg, Germany, 2021, vol. 209.'
ista: 'Alistarh D-A, Gelashvili R, Rybicki J. 2021. Brief announcement: Fast graphical
population protocols. 35th International Symposium on Distributed Computing. DISC:
Distributed Computing , LIPIcs, vol. 209, 43.'
mla: 'Alistarh, Dan-Adrian, et al. “Brief Announcement: Fast Graphical Population
Protocols.” 35th International Symposium on Distributed Computing, vol.
209, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.DISC.2021.43.'
short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, 35th International Symposium
on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
conference:
end_date: 2021-10-08
location: Freiburg, Germany
name: 'DISC: Distributed Computing '
start_date: 2021-10-04
date_created: 2021-11-07T23:01:24Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2023-02-21T09:24:08Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.43
ec_funded: 1
external_id:
arxiv:
- '2102.08808'
file:
- access_level: open_access
checksum: fd2a690f6856d21247e9aa952b0e2885
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T08:16:44Z
date_updated: 2021-11-12T08:16:44Z
file_id: '10274'
file_name: 2021_LIPIcsDISC_Alistarh.pdf
file_size: 534219
relation: main_file
success: 1
file_date_updated: 2021-11-12T08:16:44Z
has_accepted_license: '1'
intvolume: ' 209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 35th International Symposium on Distributed Computing
publication_identifier:
isbn:
- 9-783-9597-7210-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Fast graphical population protocols'
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 209
year: '2021'
...
---
_id: '10219'
abstract:
- lang: eng
text: We show that any algorithm that solves the sinkless orientation problem in
the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported
LOCAL is at least as strong as the usual LOCAL model, and as a corollary this
also gives a new, short and elementary proof that shows that the round complexity
of the sinkless orientation problem in the deterministic LOCAL model is Ω(log
n).
acknowledgement: "Janne H. Korhonen: Project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement No 805223 ScaleML). Ami Paz: We acknowledge the Austrian
Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Stefan Schmid: Research
supported by the Austrian Science Fund (FWF) project ADVISE, I 4800-N, 2020-2023.\r\n"
alternative_title:
- LIPIcs
article_number: '58'
article_processing_charge: No
arxiv: 1
author:
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
- first_name: Ami
full_name: Paz, Ami
last_name: Paz
- 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
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
citation:
ama: 'Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless
orientation is hard also in the supported LOCAL model. In: 35th International
Symposium on Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum
für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.58'
apa: 'Korhonen, J., Paz, A., Rybicki, J., Schmid, S., & Suomela, J. (2021).
Brief announcement: Sinkless orientation is hard also in the supported LOCAL model.
In 35th International Symposium on Distributed Computing (Vol. 209). Freiburg,
Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.58'
chicago: 'Korhonen, Janne, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela.
“Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL
Model.” In 35th International Symposium on Distributed Computing, Vol.
209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.58.'
ieee: 'J. Korhonen, A. Paz, J. Rybicki, S. Schmid, and J. Suomela, “Brief announcement:
Sinkless orientation is hard also in the supported LOCAL model,” in 35th International
Symposium on Distributed Computing, Freiburg, Germany, 2021, vol. 209.'
ista: 'Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. 2021. Brief announcement:
Sinkless orientation is hard also in the supported LOCAL model. 35th International
Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol.
209, 58.'
mla: 'Korhonen, Janne, et al. “Brief Announcement: Sinkless Orientation Is Hard
Also in the Supported LOCAL Model.” 35th International Symposium on Distributed
Computing, vol. 209, 58, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021, doi:10.4230/LIPIcs.DISC.2021.58.'
short: J. Korhonen, A. Paz, J. Rybicki, S. Schmid, J. Suomela, in:, 35th International
Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021.
conference:
end_date: 2021-10-08
location: Freiburg, Germany
name: 'DISC: Distributed Computing '
start_date: 2021-10-04
date_created: 2021-11-07T23:01:24Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2021-11-12T09:37:18Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.58
ec_funded: 1
external_id:
arxiv:
- '2108.02655'
file:
- access_level: open_access
checksum: c43188dc2070bbd2bf5fd6fdaf9ce36d
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T08:27:42Z
date_updated: 2021-11-12T08:27:42Z
file_id: '10275'
file_name: 2021_LIPIcsDISC_Korhonen.pdf
file_size: 474242
relation: main_file
success: 1
file_date_updated: 2021-11-12T08:27:42Z
has_accepted_license: '1'
intvolume: ' 209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 35th International Symposium on Distributed Computing
publication_identifier:
isbn:
- 9-783-9597-7210-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Sinkless orientation is hard also in the supported LOCAL
model'
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 209
year: '2021'
...
---
_id: '10429'
abstract:
- lang: eng
text: "The scalability of concurrent data structures and distributed algorithms
strongly depends on\r\nreducing the contention for shared resources and the costs
of synchronization and communication. We show how such cost reductions can be
attained by relaxing the strict consistency conditions required by sequential
implementations. In the first part of the thesis, we consider relaxation in the
context of concurrent data structures. Specifically, in data structures \r\nsuch
as priority queues, imposing strong semantics renders scalability impossible,
since a correct implementation of the remove operation should return only the
element with highest priority. Intuitively, attempting to invoke remove operations
concurrently creates a race condition. This bottleneck can be circumvented by
relaxing semantics of the affected data structure, thus allowing removal of the
elements which are no longer required to have the highest priority. We prove that
the randomized implementations of relaxed data structures provide provable guarantees
on the priority of the removed elements even under concurrency. Additionally,
we show that in some cases the relaxed data structures can be used to scale the
classical algorithms which are usually implemented with the exact ones. In the
second part, we study parallel variants of the stochastic gradient descent (SGD)
algorithm, which distribute computation among the multiple processors, thus reducing
the running time. Unfortunately, in order for standard parallel SGD to succeed,
each processor has to maintain a local copy of the necessary model parameter,
which is identical to the local copies of other processors; the overheads from
this perfect consistency in terms of communication and synchronization can negate
the speedup gained by distributing the computation. We show that the consistency
conditions required by SGD can be relaxed, allowing the algorithm to be more
flexible in terms of tolerating quantized communication, asynchrony, or even crash
faults, while its convergence remains asymptotically the same."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
orcid: 0000-0001-5634-0731
citation:
ama: Nadiradze G. On achieving scalability through relaxation. 2021. doi:10.15479/at:ista:10429
apa: Nadiradze, G. (2021). On achieving scalability through relaxation. Institute
of Science and Technology Austria. https://doi.org/10.15479/at:ista:10429
chicago: Nadiradze, Giorgi. “On Achieving Scalability through Relaxation.” Institute
of Science and Technology Austria, 2021. https://doi.org/10.15479/at:ista:10429.
ieee: G. Nadiradze, “On achieving scalability through relaxation,” Institute of
Science and Technology Austria, 2021.
ista: Nadiradze G. 2021. On achieving scalability through relaxation. Institute
of Science and Technology Austria.
mla: Nadiradze, Giorgi. On Achieving Scalability through Relaxation. Institute
of Science and Technology Austria, 2021, doi:10.15479/at:ista:10429.
short: G. Nadiradze, On Achieving Scalability through Relaxation, Institute of Science
and Technology Austria, 2021.
date_created: 2021-12-08T21:52:28Z
date_published: 2021-12-09T00:00:00Z
date_updated: 2023-10-17T11:48:55Z
day: '09'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: GradSch
- _id: DaAl
doi: 10.15479/at:ista:10429
ec_funded: 1
file:
- access_level: open_access
checksum: 6bf14e9a523387328f016c0689f5e10e
content_type: application/pdf
creator: gnadirad
date_created: 2021-12-09T17:47:49Z
date_updated: 2021-12-09T17:47:49Z
file_id: '10436'
file_name: Thesis_Final_09_12_2021.pdf
file_size: 2370859
relation: main_file
success: 1
- access_level: closed
checksum: 914d6c5ca86bd0add471971a8f4c4341
content_type: application/zip
creator: gnadirad
date_created: 2021-12-09T17:47:49Z
date_updated: 2022-03-28T12:55:12Z
file_id: '10437'
file_name: Thesis_Final_09_12_2021.zip
file_size: 2596924
relation: source_file
file_date_updated: 2022-03-28T12:55:12Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '132'
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '10432'
relation: part_of_dissertation
status: public
- id: '6673'
relation: part_of_dissertation
status: public
- id: '5965'
relation: part_of_dissertation
status: public
- id: '10435'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
title: On achieving scalability through relaxation
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2021'
...