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

^*Kontaktforfatter

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

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.

Originalsprog	Engelsk
Tidsskrift	Journal of Applied Probability
Vol/bind	61
Udgave nummer	3
Sider (fra-til)	1075-1105
Antal sider	31
ISSN	0021-9002
DOI	https://doi.org/10.1017/jpr.2023.107
Status	Udgivet - 1 sep. 2024

Bibliografisk note

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

Adgang til dokumentet

10.1017/jpr.2023.107Licens: CC BY 4.0

Open Access articleForlagets udgivne version, 446 KBLicens: CC BY 4.0

AUB Link

Søg efter materialet i Aalborg Universitetsbiblioteks søgemaskine

Andre filer og links

Link to publication in Scopus

Citationsformater

@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

Bibliografisk note

Adgang til dokumentet

AUB Link

Andre filer og links

Fingeraftryk

Citationsformater