Analysis of d-ary tree algorithms with successive interference cancellation

Quirin Vogel; Yash Deshpande; Cedomir Stefanović; Wolfgang Kellerer

doi:10.1017/jpr.2023.107

Analysis of d-ary tree algorithms with successive interference cancellation

Quirin Vogel^*, Yash Deshpande, Cedomir Stefanović, Wolfgang Kellerer

^*Corresponding author for this work

Research output: Contribution to journal › Journal article › Research › peer-review

16 Downloads (Pure)

Abstract

We calculate the mean throughput, number of collisions, successes, and idle slots for random tree algorithms with successive interference cancellation. Except for the case of the throughput for the binary tree, all the results are new. We furthermore disprove the claim that only the binary tree maximizes throughput. Our method works with many observables and can be used as a blueprint for further analysis.

Original language	English
Journal	Journal of Applied Probability
Volume	61
Issue number	3
Pages (from-to)	1075-1105
Number of pages	31
ISSN	0021-9002
DOIs	https://doi.org/10.1017/jpr.2023.107
Publication status	Published - 1 Sept 2024

Bibliographical note

Publisher Copyright:
© The Author(s), 2024.

Keywords

asymptotic analysis
functional equation
Random access
splitting algorithms

Access to Document

10.1017/jpr.2023.107Licence: CC BY 4.0

Open Access articleFinal published version, 446 KBLicence: CC BY 4.0

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

@article{c2901fde8fcc480385beb334830b2c50,

title = "Analysis of d-ary tree algorithms with successive interference cancellation",

abstract = "We calculate the mean throughput, number of collisions, successes, and idle slots for random tree algorithms with successive interference cancellation. Except for the case of the throughput for the binary tree, all the results are new. We furthermore disprove the claim that only the binary tree maximizes throughput. Our method works with many observables and can be used as a blueprint for further analysis.",

keywords = "asymptotic analysis, functional equation, Random access, splitting algorithms",

author = "Quirin Vogel and Yash Deshpande and Cedomir Stefanovi{\'c} and Wolfgang Kellerer",

note = "Publisher Copyright: {\textcopyright} The Author(s), 2024.",

year = "2024",

month = sep,

day = "1",

doi = "10.1017/jpr.2023.107",

language = "English",

volume = "61",

pages = "1075--1105",

journal = "Journal of Applied Probability",

issn = "0021-9002",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

T1 - Analysis of d-ary tree algorithms with successive interference cancellation

AU - Vogel, Quirin

AU - Deshpande, Yash

AU - Stefanović, Cedomir

AU - Kellerer, Wolfgang

N1 - Publisher Copyright: © The Author(s), 2024.

PY - 2024/9/1

Y1 - 2024/9/1

N2 - We calculate the mean throughput, number of collisions, successes, and idle slots for random tree algorithms with successive interference cancellation. Except for the case of the throughput for the binary tree, all the results are new. We furthermore disprove the claim that only the binary tree maximizes throughput. Our method works with many observables and can be used as a blueprint for further analysis.

AB - We calculate the mean throughput, number of collisions, successes, and idle slots for random tree algorithms with successive interference cancellation. Except for the case of the throughput for the binary tree, all the results are new. We furthermore disprove the claim that only the binary tree maximizes throughput. Our method works with many observables and can be used as a blueprint for further analysis.

KW - asymptotic analysis

KW - functional equation

KW - Random access

KW - splitting algorithms

UR - http://www.scopus.com/inward/record.url?scp=85186102334&partnerID=8YFLogxK

U2 - 10.1017/jpr.2023.107

DO - 10.1017/jpr.2023.107

M3 - Journal article

AN - SCOPUS:85186102334

SN - 0021-9002

VL - 61

SP - 1075

EP - 1105

JO - Journal of Applied Probability

JF - Journal of Applied Probability

IS - 3

ER -

Analysis of d-ary tree algorithms with successive interference cancellation

Abstract

Bibliographical note

Keywords

Access to Document

AUB Link

Other files and links

Fingerprint

Cite this