Non-FCFS Algorithms for Multiple Access

Code and data for the paper:

S. Datta, S. S. Panwar and R. Budhiraja, "Non-FCFS Algorithms for Multiple Access," 2025 National Conference on Communications (NCC), New Delhi, India, 2025. DOI: 10.1109/NCC63735.2025.10983549

The paper revisits the maximum achievable throughput of an ideal multi-access channel. It provides a more precise computation of the throughput of the Moseley-Humblet first-come-first-served (FCFS) algorithm, develops the first Markov decision process (MDP)-based model of the Vvedenskaya-Pinsker algorithm, and quantifies the further improvement obtainable with non-FCFS scheduling.

Contents

Source file	Algorithm	Output file(s)
moseley_half_res.c	Moseley-Humblet FCFS algorithm (value iteration)	out_moseley_2.txt
vvep_half_res.c	Vvedenskaya-Pinsker algorithm (MDP value iteration)	out_vvep_2.txt
vvep_half_res_new.c	Streamlined version of the Vvedenskaya-Pinsker value iteration	out_vvep_new.txt
new_nfcfs_try.c	Non-FCFS variant, exploratory search disabled	out_nfcfs.txt
new_nfcfs_try_search.c	Non-FCFS variant with exploratory search over the extra delta decision	out_nfcfs_search.txt, out_nfcfs_search_delta.txt

Each out_*.txt row is x, V1(x), alpha(x): the state grid point, the converged value-function estimate, and the corresponding optimal decision. out_nfcfs_search_delta.txt additionally records the searched delta decisions.

• results/ — reference outputs from the runs used for the paper.
• plots/ — the throughput plots from the paper (.fig xfig sources plus exported .eps/.png).

Building and running

Each program is a standalone C file; build everything with:

make

or a single program directly with, e.g.:

gcc -O2 -o moseley_half_res moseley_half_res.c -lm

Run the executables from the repository root (e.g. ./moseley_half_res). Each program prints per-iteration progress to stdout and writes its out_*.txt result file(s) to the current directory, which can be compared against the reference copies in results/.

Precision parameters (grid resolution del, fine-search step delf, and NUM_ITERATIONS) are set near the top of each main().

Citation

@inproceedings{datta2025nonfcfs,
  author    = {Datta, Soumyadeep and Panwar, Shivendra S. and Budhiraja, Rohit},
  title     = {Non-{FCFS} Algorithms for Multiple Access},
  booktitle = {2025 National Conference on Communications (NCC)},
  year      = {2025},
  doi       = {10.1109/NCC63735.2025.10983549}
}