Show simple item record

dc.contributor.author
Ghaffari, Mohsen
dc.contributor.author
Kuhn, Fabian
dc.contributor.editor
Schmid, Ulrich
dc.contributor.editor
Widder, Josef
dc.date.accessioned
2019-02-04T07:45:39Z
dc.date.available
2019-01-14T06:29:42Z
dc.date.available
2019-02-04T07:45:39Z
dc.date.issued
2018
dc.identifier.isbn
978-3-95977-092-7
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.DISC.2018.29
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/315335
dc.identifier.doi
10.3929/ethz-b-000315335
dc.description.abstract
This paper presents improved deterministic distributed algorithms, with O(log n)-bit messages, for some basic graph problems. The common ingredient in our results is a deterministic distributed algorithm for computing a certain hitting set, which can replace the random part of a number of standard randomized distributed algorithms. This deterministic hitting set algorithm itself is derived using a simple method of conditional expectations. As one main end-result of this derandomized hitting set, we get a deterministic distributed algorithm with round complexity 2^O(sqrt{log n * log log n}) for computing a (2k-1)-spanner of size O~(n^{1+1/k}). This improves considerably on a recent algorithm of Grossman and Parter [DISC'17] which needs O(n^{1/2-1/k} * 2^k) rounds. We also get a 2^O(sqrt{log n * log log n})-round deterministic distributed algorithm for computing an O(log^2 n)-approximation of minimum dominating set; all prior algorithms for this problem were either randomized or required large messages.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Distributed Algorithms
en_US
dc.subject
Derandomization
en_US
dc.subject
Spanners
en_US
dc.subject
Dominating Set
en_US
dc.title
Derandomizing distributed algorithms with small messages: Spanners and dominating set
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
32nd International Symposium on Distributed Computing (DISC 2018)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
121
en_US
ethz.journal.abbreviated
LIPIcs
ethz.pages.start
29:1
en_US
ethz.pages.end
29:17
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
32nd International Symposium on Distributed Computing (DISC 2018)
en_US
ethz.event.location
New Orleans, LA, USA
en_US
ethz.event.date
October 15-19, 2018
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09587 - Ghaffari, Mohsen / Ghaffari, Mohsen
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09587 - Ghaffari, Mohsen / Ghaffari, Mohsen
ethz.date.deposited
2019-01-14T06:29:43Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2019-02-04T07:45:59Z
ethz.rosetta.lastUpdated
2019-02-04T07:45:59Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Derandomizing%20distributed%20algorithms%20with%20small%20messages:%20Spanners%20and%20dominating%20set&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2018&rft.volume=121&rft.spage=29:1&rft.epage=29:17&rft.issn=1868-8969&rft.au=Ghaffari,%20Mohsen&Kuhn,%20Fabian&rft.isbn=978-3-95977-092-7&rft.genre=proceeding&rft_id=info:doi/978-3-95977-092-7&rft.btitle=32nd%20International%20Symposium%20on%20Distributed%20Computing%20(DISC%202018)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record