On the hardness of the strongly dependent decision problem

Martin Biely; Peter Robinson

doi:10.1145/3288599.3288614

On the hardness of the strongly dependent decision problem

Martin Biely, Peter Robinson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

We present necessary and sufficient conditions for solving the strongly dependent decision (SDD) problem in various distributed systems. Our main contribution is a novel characterization of the SDD problem based on point-set topology. For partially synchronous systems, we show that any algorithm that solves the SDD problem induces a set of executions that is closed with respect to the point-set topology. We also show that the SDD problem is not solvable in the asynchronous system augmented with any arbitrarily strong failure detectors.

Original language	English (US)
Title of host publication	ICDCN 2019 - Proceedings of the 2019 International Conference on Distributed Computing and Networking
Publisher	Association for Computing Machinery
Pages	120-123
Number of pages	4
ISBN (Electronic)	9781450360944
DOIs	https://doi.org/10.1145/3288599.3288614
State	Published - Jan 4 2019
Externally published	Yes
Event	20th International Conference on Distributed Computing and Networking, ICDCN 2019 - Bangalore, India Duration: Jan 4 2019 → Jan 7 2019

Publication series

Name	ACM International Conference Proceeding Series

Conference

Conference	20th International Conference on Distributed Computing and Networking, ICDCN 2019
Country/Territory	India
City	Bangalore
Period	1/4/19 → 1/7/19

ASJC Scopus subject areas

Software
Human-Computer Interaction
Computer Vision and Pattern Recognition
Computer Networks and Communications

Access to Document

10.1145/3288599.3288614

Cite this

On the hardness of the strongly dependent decision problem. / Biely, Martin; Robinson, Peter.
ICDCN 2019 - Proceedings of the 2019 International Conference on Distributed Computing and Networking. Association for Computing Machinery, 2019. p. 120-123 (ACM International Conference Proceeding Series).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Biely, M & Robinson, P 2019, On the hardness of the strongly dependent decision problem. in ICDCN 2019 - Proceedings of the 2019 International Conference on Distributed Computing and Networking. ACM International Conference Proceeding Series, Association for Computing Machinery, pp. 120-123, 20th International Conference on Distributed Computing and Networking, ICDCN 2019, Bangalore, India, 1/4/19. https://doi.org/10.1145/3288599.3288614

@inproceedings{433d795bd98140e9b5720170e5c0e9f4,

title = "On the hardness of the strongly dependent decision problem",

abstract = "We present necessary and sufficient conditions for solving the strongly dependent decision (SDD) problem in various distributed systems. Our main contribution is a novel characterization of the SDD problem based on point-set topology. For partially synchronous systems, we show that any algorithm that solves the SDD problem induces a set of executions that is closed with respect to the point-set topology. We also show that the SDD problem is not solvable in the asynchronous system augmented with any arbitrarily strong failure detectors.",

author = "Martin Biely and Peter Robinson",

note = "Funding Information: ∗Peter Robinson acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). Publisher Copyright: {\textcopyright} 2019 Association for Computing Machinery.; 20th International Conference on Distributed Computing and Networking, ICDCN 2019 ; Conference date: 04-01-2019 Through 07-01-2019",

year = "2019",

month = jan,

day = "4",

doi = "10.1145/3288599.3288614",

language = "English (US)",

series = "ACM International Conference Proceeding Series",

publisher = "Association for Computing Machinery",

pages = "120--123",

booktitle = "ICDCN 2019 - Proceedings of the 2019 International Conference on Distributed Computing and Networking",

}

TY - GEN

T1 - On the hardness of the strongly dependent decision problem

AU - Biely, Martin

AU - Robinson, Peter

N1 - Funding Information: ∗Peter Robinson acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). Publisher Copyright: © 2019 Association for Computing Machinery.

PY - 2019/1/4

Y1 - 2019/1/4

N2 - We present necessary and sufficient conditions for solving the strongly dependent decision (SDD) problem in various distributed systems. Our main contribution is a novel characterization of the SDD problem based on point-set topology. For partially synchronous systems, we show that any algorithm that solves the SDD problem induces a set of executions that is closed with respect to the point-set topology. We also show that the SDD problem is not solvable in the asynchronous system augmented with any arbitrarily strong failure detectors.

AB - We present necessary and sufficient conditions for solving the strongly dependent decision (SDD) problem in various distributed systems. Our main contribution is a novel characterization of the SDD problem based on point-set topology. For partially synchronous systems, we show that any algorithm that solves the SDD problem induces a set of executions that is closed with respect to the point-set topology. We also show that the SDD problem is not solvable in the asynchronous system augmented with any arbitrarily strong failure detectors.

UR - http://www.scopus.com/inward/record.url?scp=85060953709&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85060953709&partnerID=8YFLogxK

U2 - 10.1145/3288599.3288614

DO - 10.1145/3288599.3288614

M3 - Conference contribution

AN - SCOPUS:85060953709

T3 - ACM International Conference Proceeding Series

SP - 120

EP - 123

BT - ICDCN 2019 - Proceedings of the 2019 International Conference on Distributed Computing and Networking

PB - Association for Computing Machinery

T2 - 20th International Conference on Distributed Computing and Networking, ICDCN 2019

Y2 - 4 January 2019 through 7 January 2019

ER -

On the hardness of the strongly dependent decision problem

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this