Prevent deadlocks with consistent lock ordering

Settle account-to-account transfers using worker threads and one mutex per account. Return the final balances in the original account order.

pub fn settle_transfers(
    balances: Vec<i64>,
    transfers: Vec<(usize, usize, i64)>,
    workers: usize,
) -> Vec<i64>

Transfer rules

Each tuple (from, to, amount) subtracts amount from account from and adds it to account to. Amounts may be negative, and balances may go below zero. A transfer from an account to itself is a no-op: skip it before taking any locks or doing arithmetic.

All account indices are valid. Inputs are chosen so every intermediate subtraction and addition fits in i64, regardless of the order in which workers apply transfers. You do not need wrapping arithmetic or overdraft checks. Input sizes and worker counts fit the runtime's resources.

For example, balances [100, 200, 300] with transfers (0, 1, 50), (2, 0, 100) and (1, 2, 25) produce [150, 225, 225].

Keep both accounts locked

Use the starter's Arc<Vec<Mutex<i64>>> structure. For each non-self transfer, hold both account guards until both balances have been updated. This prevents another transfer involving either account from seeing a half-applied update.

Divide the work among at most workers.max(1) threads and join every worker before collecting the result. The starter's chunking can create fewer threads than requested; empty transfers require none. With no transfers, return the original balances. Empty balances are valid when there are no transfers.

The test harness repeats its transfers pattern repeat times before calling your function. repeat == 0 therefore means no transfers. Some cases expand to 20,000 transfers. The grader checks final balances and completion within a time limit; those observations alone cannot prove that an implementation uses parallel workers or holds both locks. Follow the locking design as well as the output contract.

Why the starter can deadlock

The starter locks the source account first, then the destination. Opposite transfers can acquire their first locks before either gets its second:

thread A: transfer 0 -> 1     thread B: transfer 1 -> 0
  holds account 0              holds account 1
  waits for account 1          waits for account 0

Neither thread can finish its transfer and release its guard. This is a circular wait. It depends on the schedule, so a successful run of the starter does not establish that its locking strategy is safe.

Rust's safe synchronization APIs prevent data races when their implementations are sound. They do not guarantee that threads make progress. A program can protect every access with a mutex and still deadlock.

Acquire distinct locks in index order

For every non-self transfer, acquire the lower-indexed account first and the higher-indexed account second. Keep that rule regardless of transfer direction. The source still loses the amount and the destination still gains it: low is not necessarily from.

This complete example transfers 5 from account 1 to account 0:

use std::sync::Mutex;

fn main() {
    let accounts = [Mutex::new(10_i64), Mutex::new(20_i64)];
    {
        let mut low = accounts[0].lock().expect("account poisoned");
        let mut high = accounts[1].lock().expect("account poisoned");
        *high -= 5;
        *low += 5;
    } // Both guards are released here.
    let [low, high] = accounts;
    assert_eq!(low.into_inner().unwrap(), 15);
    assert_eq!(high.into_inner().unwrap(), 15);
}

When every worker acquires distinct account locks in increasing index order, a cycle would require the indices to keep increasing and return to their starting point. That is impossible. This prevents cycles among these account locks; it is not a guarantee against unrelated waits or thread starvation.

Handle self-transfers first. The starter already has this second bug: it tries to lock the same mutex twice in one thread. Rust's Mutex documentation leaves the exact behavior unspecified; the second call may panic or deadlock. Sorting equal indices does not solve it.

Investigating a timeout

Check for opposite lock orders, repeated acquisition of the same mutex, and guards held while joining workers. A timeout is a symptom, not proof of deadlock: excessive work or resource contention can also exhaust the limit. Compiler and lint checks do not prove this program's lock order is safe.

Step through the visualization to compare a circular wait with a consistent lock order. It shows fixed example schedules, not the timing of your run.