Please use this identifier to cite or link to this item:
https://doi.org/10.1145/1993806.1993850
DC Field | Value | |
---|---|---|
dc.title | Optimal-time adaptive strong renaming, with applications to counting | |
dc.contributor.author | Alistarh, D. | |
dc.contributor.author | Aspnes, J. | |
dc.contributor.author | Censor-Hillel, K. | |
dc.contributor.author | Gilbert, S. | |
dc.contributor.author | Zadimoghaddam, M. | |
dc.date.accessioned | 2013-07-04T08:06:08Z | |
dc.date.available | 2013-07-04T08:06:08Z | |
dc.date.issued | 2011 | |
dc.identifier.citation | Alistarh, D.,Aspnes, J.,Censor-Hillel, K.,Gilbert, S.,Zadimoghaddam, M. (2011). Optimal-time adaptive strong renaming, with applications to counting. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing : 239-248. ScholarBank@NUS Repository. <a href="https://doi.org/10.1145/1993806.1993850" target="_blank">https://doi.org/10.1145/1993806.1993850</a> | |
dc.identifier.isbn | 9781450307192 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/40517 | |
dc.description.abstract | We give two new randomized algorithms for strong renaming, both of which work against an adaptive adversary in asynchronous shared memory. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of n processes with step complexity O(log3 n). The second transforms any sorting network into a strong adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a strong adaptive renaming algorithm with step complexity O(log k), where k is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such strong renaming protocol can be used to build a monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor). © 2011 ACM. | |
dc.description.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1145/1993806.1993850 | |
dc.source | Scopus | |
dc.subject | adaptive algorithms | |
dc.subject | distributed computing | |
dc.subject | lower bounds | |
dc.subject | renaming | |
dc.subject | shared memory | |
dc.subject | sorting networks | |
dc.type | Conference Paper | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.doi | 10.1145/1993806.1993850 | |
dc.description.sourcetitle | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing | |
dc.description.page | 239-248 | |
dc.description.coden | 85LRA | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.