BTSP-MSR

Official implementation of BTSP-MSR for the ICML 2026 paper:

Bottleneck Communication Delay Minimization for Communication-Efficient Decentralized Learning
Nozomi Hata and Kenta Niwa
Proceedings of the 43rd International Conference on Machine Learning (ICML 2026)

BTSP-MSR is an approximation solver for node assignment optimization in decentralized learning under heterogeneous communication delays. Given a target network (NW) topology represented as a circulant digraph and a physical NW with communication delays, the goal is to assign virtual nodes to physical nodes so as to minimize the Bottleneck Communication Delay (BCD).

The method is designed for circulant digraphs, including:

• Ring graph
• Exponential graph
• 1-peer exponential graph
• Sparse exponential graph

Repository structure

.
├── BTSP_MSR.py                  # Main script for BCD minimization
├── BTSP_2approx.py              # 2-approximation solver for BTSP
├── find_hamiltonian_cycle.py    # Hamiltonian-cycle utilities used by BTSP solver
├── requirements.txt             # Python dependencies
└── physical_NWs/                # Physical NW instances including randomly placed nodes and Ebone NW.

Installation

Create a Python environment and install dependencies:

pip install -r requirements.txt

Usage

(T1) Simulated physical NWs

Run BTSP-MSR on randomly placed physical nodes in 8000km x 8000km square:

python3 BTSP_MSR.py \
  --physical_nw_file physical_NWs/n{n}_seed{0-4}_square_8000.npy \
  --nw_topology ring

Available NW topologies:

ring
exponential
one_peer_exp
sparse_exp

Example:

python3 BTSP_MSR.py \
  --physical_nw_file physical_NWs/n64_seed0_square_8000.npy \
  --nw_topology exponential

(T2) Ebone physical NW

Run on the Ebone NW:

python3 BTSP_MSR.py \
  --physical_nw_file physical_NWs/ebone.npy \
  --nw_topology exponential

Solver options

By default, BTSP_MSR.py runs the proposed BTSP-MSR solver.

Optional flags:

--milp_opt       Use the SCIP-based MILP formulation. Requires pyscipopt.
--greedy_opt     Use the greedy heuristic baseline.
--sa_opt         Use the simulated annealing baseline.
--no_opt         Use the identity assignment baseline.
--seed           Fix the random seed. Default: 42.
--verbose        Print detailed logs.
--output_file    Path to the JSON file for saving the result. Default: output.json.

Output

BTSP_MSR.py saves a JSON result file to the path specified by --output_file. By default, the result is saved as output.json.

When --verbose is specified, the script also prints detailed logs to standard output. The verbose output contains the following fields:

n                       = ...
physical_nw_file        = ...
nw_topology             = ...
S_list                  = ...
optimal c               = ...
pi_star                 = [...]
BCD cost (random average) = ...
BCD cost (<method>)       = ...
BCD cost (BTSP-MSR)       = ... (c = ...)

where:

• n is the number of physical/virtual nodes.
• physical_nw_file is the input .npy or .gml file representing communication delays between physical nodes.
• nw_topology is the target NW topology over virtual nodes. It is one of ring, exponential, one_peer_exp, or sparse_exp.
• S_list is the list of skip-width sets corresponding to nw_topology. Each inner list represents the skip widths used in one communication round. For example, for n = 64, exponential gives S_list = [[1, 2, 4, 8, 16, 32]], while one_peer_exp gives S_list = [[1], [2], [4], [8], [16], [32]].
• optimal c is the multiplicative permutation parameter selected by the MSR step. For baseline solvers, c = 1.
• pi_star is the final node assignment. The i-th element is the physical node assigned to virtual node i.
• BCD cost (random average) is the average BCD over five random assignments.
• BCD cost (<method>) is the BCD obtained before the MSR step, where <method> is milp, greedy, no_opt, sa_opt, or BTSP. For BTSP-MSR, this line reports the BCD of the BTSP assignment before MSR.
• BCD cost (BTSP-MSR) is printed only when BTSP-MSR is used. It is the final BCD after applying the MSR step.

The JSON result file has the following structure:

{
  "meta": {
    "timestamp": "...",
    "n": ...,
    "seed": ...,
    "topology": "...",
    "physical_nw_file": "...",
    "method": "...",
    "S_list": [[...]]
  },
  "metrics": {
    "time_sec": ...,
    "BCD": ...,
    "BCD_pi": ...,
    "BCD_initial_avg": ...,
    "c": ...
  },
  "solution": {
    "pi": [...],
    "pi_star": [...]
  }
}

The fields are defined as follows:

• meta.timestamp: local timestamp when the experiment was run.
• meta.n: number of physical/virtual nodes.
• meta.seed: random seed used in the experiment.
• meta.topology: target NW topology.
• meta.physical_nw_file: input physical NW file.
• meta.method: solver used in the experiment. The value is one of btsp_msr, milp, greedy, no_opt, or sa_opt.
• meta.S_list: skip-width sets used to define the target NW topology.
• metrics.time_sec: total running time in seconds.
• metrics.BCD: final BCD. For BTSP-MSR, this is the BCD after MSR; for the baseline solvers, this is the BCD of the baseline assignment.
• metrics.BCD_pi: BCD of solution.pi, i.e., before MSR for BTSP-MSR and identical to metrics.BCD for the baseline solvers.
• metrics.BCD_initial_avg: average BCD over five random assignments.
• metrics.c: selected MSR parameter. This is 1 for the baseline solvers.
• solution.pi: node assignment produced by the selected solver before MSR. The i-th element is the physical node assigned to virtual node i.
• solution.pi_star: final node assignment. For BTSP-MSR, this is obtained from solution.pi by the MSR step; for the baseline solvers, it is the same as solution.pi.

Citation

If you use this code, please cite:

@inproceedings{hata2026btspmsr,
  title     = {Bottleneck Communication Delay Minimization for Communication-Efficient Decentralized Learning},
  author    = {Hata, Nozomi and Niwa, Kenta},
  booktitle = {Proceedings of the 43rd International Conference on Machine Learning},
  year      = {2026}
}

License

See SoftwareLicenseAgreement