Show simple item record

dc.contributor.author
Chang, Yi-Jun
dc.contributor.author
Duan, Ran
dc.contributor.author
Jiang, Shunhua
dc.date.accessioned
2021-08-02T10:58:45Z
dc.date.available
2021-07-18T02:37:25Z
dc.date.available
2021-08-02T10:58:45Z
dc.date.issued
2021-07
dc.identifier.isbn
978-1-4503-8070-6
en_US
dc.identifier.other
10.1145/3409964.3461830
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/495628
dc.description.abstract
We consider the energy complexity of the leader election problem in the single-hop radio network model, where each device ν has a unique identifier ID(ν) {1, 2, ..., N}. Energy is a scarce resource for small battery-powered devices. For such devices, most of the energy is often spent on communication, not on computation. To approximate the actual energy cost, the energy complexity of an algorithm is defined as the maximum over all devices of the number of time slots where the device transmits or listens. Much progress has been made in understanding the energy complexity of leader election in radio networks, but very little is known about the trade-off between time and energy. Chang et al. [STOC 2017] showed that the optimal deterministic energy complexity of leader election is (log log N) if each device can simultaneously transmit and listen, but still leaving the problem of determining the optimal time complexity under any given energy constraint.
en_US
dc.language.iso
en
en_US
dc.publisher
Association for Computing Machinery
en_US
dc.subject
Leader election
en_US
dc.subject
Radio network
en_US
dc.subject
Time-energy trade off
en_US
dc.title
Near-optimal time-energy trade-offs for deterministic leader election
en_US
dc.type
Conference Paper
dc.date.published
2021-07-06
ethz.book.title
Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '21)
en_US
ethz.pages.start
162
en_US
ethz.pages.end
172
en_US
ethz.event
33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2001)
en_US
ethz.event.location
Online
en_US
ethz.event.date
July 6-8, 2021
en_US
ethz.identifier.scopus
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.date.deposited
2021-07-18T02:37:28Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-08-02T10:58:52Z
ethz.rosetta.lastUpdated
2021-08-02T10:58:52Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Near-optimal%20time-energy%20trade-offs%20for%20deterministic%20leader%20election&rft.date=2021-07&rft.spage=162&rft.epage=172&rft.au=Chang,%20Yi-Jun&Duan,%20Ran&Jiang,%20Shunhua&rft.isbn=978-1-4503-8070-6&rft.genre=proceeding&rft_id=info:doi/10.1145/3409964.3461830&rft.btitle=Proceedings%20of%20the%2033rd%20ACM%20Symposium%20on%20Parallelism%20in%20Algorithms%20and%20Architectures%20(SPAA%20'21)
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record