Fast Nonadaptive Deterministic Algorithm for Conflict Resolution in a Dynamic Multiple-Access Channel
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 11994
- Type
- D - Journal article
- DOI
-
10.1137/140982763
- Title of journal
- SIAM Journal on Computing
- Article number
- -
- First page
- 868
- Volume
- 44
- Issue
- 3
- ISSN
- 0097-5397
- Open access status
- Out of scope for open access requirements
- Month of publication
- May
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 9
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The paper studies a classical problem in resolving conflicts over a decentralised multiple-access channel. It proposes a non-adaptive deterministic algorithm with time complexity almost matching a long standing lower bound from 1985 (Greenberg and Winograd, JACM). Resulting follow-up research includes work on: conflict resolution protocols (De Marco and Stachowiak PODC'17), different network models (Bender et al. JACM'18, Jurdzinski and Rozanski FCT'17, Agrawal et al. SPAA'20), and employing randomisation (Bender et al. SICOMP'18).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -