---
_id: '11436'
abstract:
- lang: eng
text: Asynchronous distributed algorithms are a popular way to reduce synchronization
costs in large-scale optimization, and in particular for neural network training.
However, for nonsmooth and nonconvex objectives, few convergence guarantees exist
beyond cases where closed-form proximal operator solutions are available. As training
most popular deep neural networks corresponds to optimizing nonsmooth and nonconvex
objectives, there is a pressing need for such convergence guarantees. In this
paper, we analyze for the first time the convergence of stochastic asynchronous
optimization for this general class of objectives. In particular, we focus on
stochastic subgradient methods allowing for block variable partitioning, where
the shared model is asynchronously updated by concurrent processes. To this end,
we use a probabilistic model which captures key features of real asynchronous
scheduling between concurrent processes. Under this model, we establish convergence
with probability one to an invariant set for stochastic subgradient methods with
momentum. From a practical perspective, one issue with the family of algorithms
that we consider is that they are not efficiently supported by machine learning
frameworks, which mostly focus on distributed data-parallel strategies. To address
this, we propose a new implementation strategy for shared-memory based training
of deep neural networks for a partitioned but shared model in single- and multi-GPU
settings. Based on this implementation, we achieve on average1.2x speed-up in
comparison to state-of-the-art training methods for popular image classification
tasks, without compromising accuracy.
acknowledgement: Vyacheslav Kungurtsev was supported by the OP VVV project CZ.02.1.01/0.0/0.0/16
019/0000765 “Research Center for Informatics. Bapi Chatterjee was supported by the
European Union’s Horizon 2020 research and innovation programme under the Marie
Sklodowska-Curie grant agreement No. 754411 (ISTPlus). Dan Alistarh 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: Vyacheslav
full_name: Kungurtsev, Vyacheslav
last_name: Kungurtsev
- first_name: Malcolm
full_name: Egan, Malcolm
last_name: Egan
- first_name: Bapi
full_name: Chatterjee, Bapi
id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
- 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: 'Kungurtsev V, Egan M, Chatterjee B, Alistarh D-A. Asynchronous optimization
methods for efficient training of deep neural networks with guarantees. In: 35th
AAAI Conference on Artificial Intelligence, AAAI 2021. Vol 35. AAAI Press;
2021:8209-8216.'
apa: 'Kungurtsev, V., Egan, M., Chatterjee, B., & Alistarh, D.-A. (2021). Asynchronous
optimization methods for efficient training of deep neural networks with guarantees.
In 35th AAAI Conference on Artificial Intelligence, AAAI 2021 (Vol. 35,
pp. 8209–8216). Virtual, Online: AAAI Press.'
chicago: Kungurtsev, Vyacheslav, Malcolm Egan, Bapi Chatterjee, and Dan-Adrian Alistarh.
“Asynchronous Optimization Methods for Efficient Training of Deep Neural Networks
with Guarantees.” In 35th AAAI Conference on Artificial Intelligence, AAAI
2021, 35:8209–16. AAAI Press, 2021.
ieee: V. Kungurtsev, M. Egan, B. Chatterjee, and D.-A. Alistarh, “Asynchronous optimization
methods for efficient training of deep neural networks with guarantees,” in 35th
AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual, Online, 2021,
vol. 35, no. 9B, pp. 8209–8216.
ista: 'Kungurtsev V, Egan M, Chatterjee B, Alistarh D-A. 2021. Asynchronous optimization
methods for efficient training of deep neural networks with guarantees. 35th AAAI
Conference on Artificial Intelligence, AAAI 2021. AAAI: Conference on Artificial
Intelligence vol. 35, 8209–8216.'
mla: Kungurtsev, Vyacheslav, et al. “Asynchronous Optimization Methods for Efficient
Training of Deep Neural Networks with Guarantees.” 35th AAAI Conference on
Artificial Intelligence, AAAI 2021, vol. 35, no. 9B, AAAI Press, 2021, pp.
8209–16.
short: V. Kungurtsev, M. Egan, B. Chatterjee, D.-A. Alistarh, in:, 35th AAAI Conference
on Artificial Intelligence, AAAI 2021, AAAI Press, 2021, pp. 8209–8216.
conference:
end_date: 2021-02-09
location: Virtual, Online
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2021-02-02
date_created: 2022-06-05T22:01:52Z
date_published: 2021-05-18T00:00:00Z
date_updated: 2022-06-07T06:53:36Z
day: '18'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '1905.11845'
intvolume: ' 35'
issue: 9B
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.1905.11845'
month: '05'
oa: 1
oa_version: Preprint
page: 8209-8216
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 35th AAAI Conference on Artificial Intelligence, AAAI 2021
publication_identifier:
eissn:
- 2374-3468
isbn:
- '9781713835974'
issn:
- 2159-5399
publication_status: published
publisher: AAAI Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Asynchronous optimization methods for efficient training of deep neural networks
with guarantees
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 35
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: '10432'
abstract:
- lang: eng
text: One key element behind the recent progress of machine learning has been the
ability to train machine learning models in large-scale distributed shared-memory
and message-passing environments. Most of these models are trained employing variants
of stochastic gradient descent (SGD) based optimization, but most methods involve
some type of consistency relaxation relative to sequential SGD, to mitigate its
large communication or synchronization costs at scale. In this paper, we introduce
a general consistency condition covering communication-reduced and asynchronous
distributed SGD implementations. Our framework, called elastic consistency, decouples
the system-specific aspects of the implementation from the SGD convergence requirements,
giving a general way to obtain convergence bounds for a wide variety of distributed
SGD methods used in practice. Elastic consistency can be used to re-derive or
improve several previous convergence bounds in message-passing and shared-memory
settings, but also to analyze new models and distribution schemes. As a direct
application, we propose and analyze a new synchronization-avoiding scheduling
scheme for distributed SGD, and show that it can be used to efficiently train
deep convolutional models for image classification.
acknowledgement: "We would like to thank Christopher De Sa for his feedback on an
earlier draft of this paper, as well as the anonymous AAAI reviewers for their useful
comments. This project has received\r\nfunding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 805223 ScaleML). Bapi\r\nChatterjee was supported by the European
Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie
grant agreement No. 754411 (ISTPlus)."
article_processing_charge: No
arxiv: 1
author:
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
orcid: 0000-0001-5634-0731
- first_name: Ilia
full_name: Markov, Ilia
id: D0CF4148-C985-11E9-8066-0BDEE5697425
last_name: Markov
- first_name: Bapi
full_name: Chatterjee, Bapi
id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-2742-4028
- first_name: 'Vyacheslav '
full_name: 'Kungurtsev, Vyacheslav '
last_name: Kungurtsev
- 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: 'Nadiradze G, Markov I, Chatterjee B, Kungurtsev V, Alistarh D-A. Elastic consistency:
A practical consistency model for distributed stochastic gradient descent. In:
Proceedings of the AAAI Conference on Artificial Intelligence. Vol 35.
; 2021:9037-9045.'
apa: 'Nadiradze, G., Markov, I., Chatterjee, B., Kungurtsev, V., & Alistarh,
D.-A. (2021). Elastic consistency: A practical consistency model for distributed
stochastic gradient descent. In Proceedings of the AAAI Conference on Artificial
Intelligence (Vol. 35, pp. 9037–9045). Virtual.'
chicago: 'Nadiradze, Giorgi, Ilia Markov, Bapi Chatterjee, Vyacheslav Kungurtsev,
and Dan-Adrian Alistarh. “Elastic Consistency: A Practical Consistency Model for
Distributed Stochastic Gradient Descent.” In Proceedings of the AAAI Conference
on Artificial Intelligence, 35:9037–45, 2021.'
ieee: 'G. Nadiradze, I. Markov, B. Chatterjee, V. Kungurtsev, and D.-A. Alistarh,
“Elastic consistency: A practical consistency model for distributed stochastic
gradient descent,” in Proceedings of the AAAI Conference on Artificial Intelligence,
Virtual, 2021, vol. 35, no. 10, pp. 9037–9045.'
ista: 'Nadiradze G, Markov I, Chatterjee B, Kungurtsev V, Alistarh D-A. 2021. Elastic
consistency: A practical consistency model for distributed stochastic gradient
descent. Proceedings of the AAAI Conference on Artificial Intelligence. AAAI:
Association for the Advancement of Artificial Intelligence vol. 35, 9037–9045.'
mla: 'Nadiradze, Giorgi, et al. “Elastic Consistency: A Practical Consistency Model
for Distributed Stochastic Gradient Descent.” Proceedings of the AAAI Conference
on Artificial Intelligence, vol. 35, no. 10, 2021, pp. 9037–45.'
short: G. Nadiradze, I. Markov, B. Chatterjee, V. Kungurtsev, D.-A. Alistarh, in:,
Proceedings of the AAAI Conference on Artificial Intelligence, 2021, pp. 9037–9045.
conference:
end_date: 2021-02-09
location: Virtual
name: 'AAAI: Association for the Advancement of Artificial Intelligence'
start_date: 2021-02-02
date_created: 2021-12-09T09:21:35Z
date_published: 2021-05-18T00:00:00Z
date_updated: 2023-09-07T13:31:39Z
day: '18'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2001.05918'
intvolume: ' 35'
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ojs.aaai.org/index.php/AAAI/article/view/17092
month: '05'
oa: 1
oa_version: Published Version
page: 9037-9045
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the AAAI Conference on Artificial Intelligence
publication_status: published
quality_controlled: '1'
related_material:
record:
- id: '10429'
relation: dissertation_contains
status: public
status: public
title: 'Elastic consistency: A practical consistency model for distributed stochastic
gradient descent'
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 35
year: '2021'
...
---
_id: '9827'
abstract:
- lang: eng
text: 'The Nearest neighbour search (NNS) is a fundamental problem in many application
domains dealing with multidimensional data. In a concurrent setting, where dynamic
modifications are allowed, a linearizable implementation of the NNS is highly
desirable.This paper introduces the LockFree-kD-tree (LFkD-tree ): a lock-free
concurrent kD-tree, which implements an abstract data type (ADT) that provides
the operations Add, Remove, Contains, and NNS. Our implementation is linearizable.
The operations in the LFkD-tree use single-word read and compare-and-swap (Image
1 ) atomic primitives, which are readily supported on available multi-core processors.
We experimentally evaluate the LFkD-tree using several benchmarks comprising real-world
and synthetic datasets. The experiments show that the presented design is scalable
and achieves significant speed-up compared to the implementations of an existing
sequential kD-tree and a recently proposed multidimensional indexing structure,
PH-tree.'
article_processing_charge: No
article_type: original
author:
- first_name: Bapi
full_name: Chatterjee, Bapi
id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-2742-4028
- first_name: Ivan
full_name: Walulya, Ivan
last_name: Walulya
- first_name: Philippas
full_name: Tsigas, Philippas
last_name: Tsigas
citation:
ama: Chatterjee B, Walulya I, Tsigas P. Concurrent linearizable nearest neighbour
search in LockFree-kD-tree. Theoretical Computer Science. 2021;886:27-48.
doi:10.1016/j.tcs.2021.06.041
apa: Chatterjee, B., Walulya, I., & Tsigas, P. (2021). Concurrent linearizable
nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/j.tcs.2021.06.041
chicago: Chatterjee, Bapi, Ivan Walulya, and Philippas Tsigas. “Concurrent Linearizable
Nearest Neighbour Search in LockFree-KD-Tree.” Theoretical Computer Science.
Elsevier, 2021. https://doi.org/10.1016/j.tcs.2021.06.041.
ieee: B. Chatterjee, I. Walulya, and P. Tsigas, “Concurrent linearizable nearest
neighbour search in LockFree-kD-tree,” Theoretical Computer Science, vol.
886. Elsevier, pp. 27–48, 2021.
ista: Chatterjee B, Walulya I, Tsigas P. 2021. Concurrent linearizable nearest neighbour
search in LockFree-kD-tree. Theoretical Computer Science. 886, 27–48.
mla: Chatterjee, Bapi, et al. “Concurrent Linearizable Nearest Neighbour Search
in LockFree-KD-Tree.” Theoretical Computer Science, vol. 886, Elsevier,
2021, pp. 27–48, doi:10.1016/j.tcs.2021.06.041.
short: B. Chatterjee, I. Walulya, P. Tsigas, Theoretical Computer Science 886 (2021)
27–48.
date_created: 2021-08-08T22:01:31Z
date_published: 2021-09-13T00:00:00Z
date_updated: 2023-08-10T14:27:43Z
day: '13'
department:
- _id: DaAl
doi: 10.1016/j.tcs.2021.06.041
external_id:
isi:
- '000694718900004'
intvolume: ' 886'
isi: 1
keyword:
- Concurrent data structure
- kD-tree
- Nearest neighbor search
- Similarity search
- Lock-free
- Linearizability
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://publications.lib.chalmers.se/records/fulltext/232185/232185.pdf
month: '09'
oa: 1
oa_version: Submitted Version
page: 27-48
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Concurrent linearizable nearest neighbour search in LockFree-kD-tree
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 886
year: '2021'
...
---
_id: '7213'
abstract:
- lang: eng
text: Persistent homology is a powerful tool in Topological Data Analysis (TDA)
to capture the topological properties of data succinctly at different spatial
resolutions. For graphical data, the shape, and structure of the neighborhood
of individual data items (nodes) are an essential means of characterizing their
properties. We propose the use of persistent homology methods to capture structural
and topological properties of graphs and use it to address the problem of link
prediction. We achieve encouraging results on nine different real-world datasets
that attest to the potential of persistent homology-based methods for network
analysis.
alternative_title:
- SCI
article_processing_charge: No
author:
- first_name: Sumit
full_name: Bhatia, Sumit
last_name: Bhatia
- first_name: Bapi
full_name: Chatterjee, Bapi
id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-2742-4028
- first_name: Deepak
full_name: Nathani, Deepak
last_name: Nathani
- first_name: Manohar
full_name: Kaul, Manohar
last_name: Kaul
citation:
ama: 'Bhatia S, Chatterjee B, Nathani D, Kaul M. A persistent homology perspective
to the link prediction problem. In: Complex Networks and Their Applications
VIII. Vol 881. Springer Nature; 2020:27-39. doi:10.1007/978-3-030-36687-2_3'
apa: 'Bhatia, S., Chatterjee, B., Nathani, D., & Kaul, M. (2020). A persistent
homology perspective to the link prediction problem. In Complex Networks and
their applications VIII (Vol. 881, pp. 27–39). Lisbon, Portugal: Springer
Nature. https://doi.org/10.1007/978-3-030-36687-2_3'
chicago: Bhatia, Sumit, Bapi Chatterjee, Deepak Nathani, and Manohar Kaul. “A Persistent
Homology Perspective to the Link Prediction Problem.” In Complex Networks and
Their Applications VIII, 881:27–39. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-36687-2_3.
ieee: S. Bhatia, B. Chatterjee, D. Nathani, and M. Kaul, “A persistent homology
perspective to the link prediction problem,” in Complex Networks and their
applications VIII, Lisbon, Portugal, 2020, vol. 881, pp. 27–39.
ista: 'Bhatia S, Chatterjee B, Nathani D, Kaul M. 2020. A persistent homology perspective
to the link prediction problem. Complex Networks and their applications VIII.
COMPLEX: International Conference on Complex Networks and their Applications,
SCI, vol. 881, 27–39.'
mla: Bhatia, Sumit, et al. “A Persistent Homology Perspective to the Link Prediction
Problem.” Complex Networks and Their Applications VIII, vol. 881, Springer
Nature, 2020, pp. 27–39, doi:10.1007/978-3-030-36687-2_3.
short: S. Bhatia, B. Chatterjee, D. Nathani, M. Kaul, in:, Complex Networks and
Their Applications VIII, Springer Nature, 2020, pp. 27–39.
conference:
end_date: 2019-12-12
location: Lisbon, Portugal
name: 'COMPLEX: International Conference on Complex Networks and their Applications'
start_date: 2019-12-10
date_created: 2019-12-29T23:00:45Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2024-02-22T13:16:06Z
day: '01'
ddc:
- '004'
department:
- _id: DaAl
doi: 10.1007/978-3-030-36687-2_3
ec_funded: 1
external_id:
isi:
- '000843927300003'
file:
- access_level: open_access
checksum: 8951f094c8c7dae9ff8db885199bc296
content_type: application/pdf
creator: bchatter
date_created: 2020-10-08T08:16:48Z
date_updated: 2020-10-08T08:16:48Z
file_id: '8625'
file_name: main.pdf
file_size: 310598
relation: main_file
success: 1
file_date_updated: 2020-10-08T08:16:48Z
has_accepted_license: '1'
intvolume: ' 881'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 27-39
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Complex Networks and their applications VIII
publication_identifier:
eissn:
- '18609503'
isbn:
- '9783030366865'
issn:
- 1860949X
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: A persistent homology perspective to the link prediction problem
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 881
year: '2020'
...
---
_id: '5947'
abstract:
- lang: eng
text: Graph algorithms applied in many applications, including social networks,
communication networks, VLSI design, graphics, and several others, require dynamic
modifications - addition and removal of vertices and/or edges - in the graph.
This paper presents a novel concurrent non-blocking algorithm to implement a dynamic
unbounded directed graph in a shared-memory machine. The addition and removal
operations of vertices and edges are lock-free. For a finite sized graph, the
lookup operations are wait-free. Most significant component of the presented algorithm
is the reachability query in a concurrent graph. The reachability queries in our
algorithm are obstruction-free and thus impose minimal additional synchronization
cost over other operations. We prove that each of the data structure operations
are linearizable. We extensively evaluate a sample C/C++ implementation of the
algorithm through a number of micro-benchmarks. The experimental results show
that the proposed algorithm scales well with the number of threads and on an average
provides 5 to 7x performance improvement over a concurrent graph implementation
using coarse-grained locking.
article_processing_charge: No
arxiv: 1
author:
- first_name: Bapi
full_name: Chatterjee, Bapi
id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-2742-4028
- first_name: Sathya
full_name: Peri, Sathya
last_name: Peri
- first_name: Muktikanta
full_name: Sa, Muktikanta
last_name: Sa
- first_name: Nandini
full_name: Singhal, Nandini
last_name: Singhal
citation:
ama: 'Chatterjee B, Peri S, Sa M, Singhal N. A simple and practical concurrent non-blocking
unbounded graph with linearizable reachability queries. In: ACM International
Conference Proceeding Series. ACM; 2019:168-177. doi:10.1145/3288599.3288617'
apa: 'Chatterjee, B., Peri, S., Sa, M., & Singhal, N. (2019). A simple and practical
concurrent non-blocking unbounded graph with linearizable reachability queries.
In ACM International Conference Proceeding Series (pp. 168–177). Bangalore,
India: ACM. https://doi.org/10.1145/3288599.3288617'
chicago: Chatterjee, Bapi, Sathya Peri, Muktikanta Sa, and Nandini Singhal. “A Simple
and Practical Concurrent Non-Blocking Unbounded Graph with Linearizable Reachability
Queries.” In ACM International Conference Proceeding Series, 168–77. ACM,
2019. https://doi.org/10.1145/3288599.3288617.
ieee: B. Chatterjee, S. Peri, M. Sa, and N. Singhal, “A simple and practical concurrent
non-blocking unbounded graph with linearizable reachability queries,” in ACM
International Conference Proceeding Series, Bangalore, India, 2019, pp. 168–177.
ista: 'Chatterjee B, Peri S, Sa M, Singhal N. 2019. A simple and practical concurrent
non-blocking unbounded graph with linearizable reachability queries. ACM International
Conference Proceeding Series. ICDCN: Conference on Distributed Computing and Networking,
168–177.'
mla: Chatterjee, Bapi, et al. “A Simple and Practical Concurrent Non-Blocking Unbounded
Graph with Linearizable Reachability Queries.” ACM International Conference
Proceeding Series, ACM, 2019, pp. 168–77, doi:10.1145/3288599.3288617.
short: B. Chatterjee, S. Peri, M. Sa, N. Singhal, in:, ACM International Conference
Proceeding Series, ACM, 2019, pp. 168–177.
conference:
end_date: 2019-01-07
location: Bangalore, India
name: 'ICDCN: Conference on Distributed Computing and Networking'
start_date: 2019-01-04
date_created: 2019-02-10T22:59:17Z
date_published: 2019-01-04T00:00:00Z
date_updated: 2023-08-24T14:41:53Z
day: '04'
department:
- _id: DaAl
doi: 10.1145/3288599.3288617
external_id:
arxiv:
- '1809.00896'
isi:
- '000484491600019'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1809.00896
month: '01'
oa: 1
oa_version: Preprint
page: 168-177
publication: ACM International Conference Proceeding Series
publication_identifier:
isbn:
- '978-1-4503-6094-4 '
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: A simple and practical concurrent non-blocking unbounded graph with linearizable
reachability queries
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...