arXiv Open Access 2021

Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention

Dan Alistarh Rati Gelashvili Giorgi Nadiradze

Lihat Sumber

Abstrak

This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for randomized obstruction-free algorithms. The approach extends to lower bounds for randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case contention incurred by a processor in an execution.

Topik & Kata Kunci

cs.DC

Penulis (3)

Dan Alistarh

Rati Gelashvili

Giorgi Nadiradze

Format Sitasi

APA MLA BibTeX

Alistarh, D., Gelashvili, R., Nadiradze, G. (2021). Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention. https://arxiv.org/abs/2108.02802

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2021
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓