There are times when you just try to work out something very simple and see where it leads to.

Consider the following argument about simple graphs, which will lead to some very non-obvious consequences.

Considering that there would be several ways to grow a graph, we now consider all possibilities:

1. Adding an edge that connects to existing vertices, thereby increasing the degree of both vertices by 1
2. Adding an edge that connects to 1 existing vertex and a new node, increasing the degree of the existing vertex by 1 and the new node will have degree 1
3. Adding an edge with two new nodes brought in, increases component size by 1, and adds 2 vertices of degree 1 to the graph
4. Adding a new node implies zero, 1, or more edges are added. For zero, component size increases by 1, 1 is the same as (2) above, and every additional edge added while adding the vertex, increases the degree of both vertices involved in the addition by 1

Starting with one vertex, lets see what happens when edges and vertices are added to the graph, starting with zero edges and one vertex.

Vertex	Degree	Edge	Component
1	0	0	1
2	0	0	2
2	1,1=2 (o + o = e = 2)	1	1
3	1,1,0	1	2
3	1,2,1 = 4 (o + e + o = 4)	2	1
3	2,2,2 = 6 (e + e + e = 6)	3	1
4	2,2,2,0	3	2
4	2,2,2,2 = 8 (e + e + e + e = 8)	4	1

In the above table, when an isolated vertex gets connected into the graph while adding an edge to the graph, produces the following effect:

• If there was an edge connecting two vertices, there may be a split as the edge breaks into two to accommodate the new vertex, and keep the degree of all vertices at a minimum. For example, look at the last row of the above table carefully. We go from (2,2,2,0) -> (2,2,2,2) which converts the triangle into a square shape. We could also have set it up as (2,2,2,0) -> (2,2,3,1) which would have increased the degree of one node above the maximum at the time in the graph. Thus, changing the topology of the graph can have an effect on the creation of hotspots of connectivity and thus information exchange.

This implies:

• We could find the degree of all nodes of the graph and sort them in descending order
• If an edge needs to be added, we could check if
  • Adding the edge to any node, as detailed above, increases the degree of any of them above the maximum. If it does, then there will be a single node with largest degree guaranteed to exist after the edge is added.
  • Else, there are nodes which can absorb this edge without creating a localized hotspot of connectivity.
• Any communication happening along the edges between nodes, whether pairwise or otherwise, can be considered as an issue of even-odd parity. If an even number of nodes are involved in the communication per clock cycle, where the incoming requests are in the same multiple of the number of nodes, then they might get stuck because none of the nodes get the downtime required to be done with background processes. The same applies to an odd number of nodes, where it is better to have even request batches and leave one of the nodes as inactive for some time.

Result

We note that, if the nodes are already present as part of some system, then an edge connection implies that the two nodes are sharing information. In many systems, such edges can appear and disappear as the system processes requests. Common examples are the distributed backend of SaaS applications, or multi-core processing on CPUs. From the above, we saw that as nodes are added to the request processing path, the utilization of nodes can increase in such a way as to create local hotspots on any of the nodes when its degree increases beyond the maximum in the graph of nodes.

When consensus / consistency protocols, which are pairwise coordinated are run against these nodes, then the hotspot creation escalates towards causing latency spikes. Instead, in these cases, the introduction of asymmetric jitter (which is done sometimes by adding sleep statements, as per my reading) can be designed into the system, by a load balancer which dispatches requests in multiples of the internal system’s graph topology and leaves room for at least one free node for maximum efficiency as demonstrated by the code simulation and analysis below. This one free node architecture ensures that for each batch, there is at least one node that gets the downtime to sync up with other nodes while being free of any locks upon it.

Thus, when either designing a backend or db leader / lagger system, or routing requests, or parallelizing code for the cpu, etc, it is helpful to keep in mind the idea that full resource utilization in powers of 2 (as is commonly done) is actually detrimental to the peak latency numbers. Instead of reacting to latency spikes by means of monitoring alerts, there is the possibility of designing the system such that the latency does not spike as often, even during peak request times (for a system already scaled up to a certain number of requests size).

An application to distributed systems

Intuition Consider a 3 lane highway with a toll booth at the beginning of each lane. Now along the highway, there are various lane changes allowed, where there are traffic signals. This slows down the movement of traffic over all the lanes if all lanes are in operation simultaneously.

Now, just imagine that the toll booth and signals at one of the lanes is kept closed for some time, and this continues round-robin every half an hour or so over all the lanes. If the number of incoming vehicles is roughly equal over the few hours of peak traffic time, the advantage of having a single lane free of signals and tolls would work wonders for the overall flow of traffic over the highway. If all 3 lanes are occupied simultaneously, it indicates maximum resource utilization, at the cost of time lost waiting at toll booths and other signals along it. So, jams can occur and the peak flow rate will come down significantly. In the other scenario with a signal free corridor, 33% of the traffic is moving at the fastest possible speed, thereby improving the peak traffic flow rate.

A simple distributed system

The above analogy holds for any system where the maximum resource utilization is measured as the amount of time each resource is processing incoming requests. Now, regardless of whether any of the nodes gets sufficient downtime to process background threads, such as for database synchronization (the signals from the analogy above), in practice, people tend to utilize all the nodes in their request batching from the load balancer. Using the parity behavior explained above and demonstrated below, we introduce an asymmetric gap when increased resource utilization causes performance peaks to drop and which is a quite common issue in modern SaaS backends or other systems.

Demo code I have attempted to simulate the effects of parity based jitter introduction, using the following simulation, which is attempting to run threads on a multi-core CPU.

The following simulation was run on a dual core i5 machine with hyperthreading.

rust
use std::sync::{Arc, Mutex};
use std::thread;
use std::time::{Duration, Instant};

const SIMULATION_LOOPS: usize = 100_000;
const BASE_WORK_US: u64 = 50; // Base processing time inside the lock
const ARRAY_SIZE: usize = 100_000_000; // Numbers to sort in lieu of actual work (if uncommented below)

// Bind native Windows kernel primitives to pin execution frames directly to hardware slots
#[link(name = "kernel32")]
extern "system" {
    fn GetCurrentThread() -> *mut std::ffi::c_void;
    fn SetThreadAffinityMask(h_thread: *mut std::ffi::c_void, dw_thread_affinity_mask: usize) -> usize;
}

// Simple LCG Pseudo-Random Number Generator to avoid external dependencies
#[derive(Clone, Copy)]
struct SimpleRng {
    state: u64,
}

impl SimpleRng {
    fn new(seed: u64) -> Self {
        SimpleRng { state: seed }
    }

    // Returns a random i32 integer
    fn next_i32(&mut self) -> i32 {
        // Standard MMIX parameters by Donald Knuth
        self.state = self.state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        (self.state >> 32) as i32
    }
}

struct SharedResource {
    // Shared processing lanes represented as Mutexes
    lanes: Vec<Mutex<()>>,
}

fn run_simulation(batch_size: usize, affinity_masks: Vec<usize>, is_odd_regime: bool, mut baseline_array: Arc<Mutex<Vec<i32>>>, mut rng: SimpleRng) -> Vec<Duration> {
    for index in 0..ARRAY_SIZE {
        baseline_array.lock().unwrap().clear();
        baseline_array.lock().unwrap().push((ARRAY_SIZE - index) as i32);
    }
    
    // 4 underlying processing channels/cores
    let resource = Arc::new(SharedResource {
        lanes: vec![Mutex::new(()), Mutex::new(()), Mutex::new(()), Mutex::new(())],
    });

    let mut handles = vec![];
    let latencies = Arc::new(Mutex::new(Vec::with_capacity(SIMULATION_LOOPS)));

    for thread_id in 0..batch_size {
        let resource_clone = Arc::clone(&resource);
        let latencies_clone = Arc::clone(&latencies);
        let baseline_array_clone = Arc::clone(&baseline_array);
        let mut core_mask = 0;

        if thread_id < batch_size-1 {
            core_mask = affinity_masks[thread_id];
        }

        let handle = thread::spawn(move || {
            // Pin the current OS thread to the exact targeted logical core mask
            unsafe {
                if core_mask > 0 {
                    let current_thread_handle = GetCurrentThread();
                    SetThreadAffinityMask(current_thread_handle, core_mask);
                }
            }

            for loop_idx in 0..(SIMULATION_LOOPS / batch_size) {
                let req_start = Instant::now();

                // DYNAMIC TOPOLOGICAL MAPPING:
                // Determine which locked lanes this specific request needs to acquire.
                let lane_a = thread_id % 4;
                let mut lane_b = (thread_id + 1) % 4;

                // If we are in the odd regime, we intentionally break perfect factorization
                // by dynamically shifting the target node step for specific indices.
                if is_odd_regime && (thread_id == batch_size - 1) {
                    lane_b = (thread_id + 2) % 4; 
                }

                // Ensure strict lock ordering to prevent standard deadlocks
                let (first, second) = if lane_a < lane_b {
                    (lane_a, lane_b)
                } else {
                    (lane_b, lane_a)
                };

                // Execute the synchronized pairwise transaction
                if first != second {
                    let _guard1 = resource_clone.lanes[first].lock().unwrap();
                    let _guard2 = resource_clone.lanes[second].lock().unwrap();
                    
                    // Simulate execution task weight / cache lines modification
                    thread::sleep(Duration::from_micros(BASE_WORK_US));
                    //baseline_array_clone.lock().unwrap().sort();
                } else {
                    let _guard1 = resource_clone.lanes[first].lock().unwrap();
                    thread::sleep(Duration::from_micros(BASE_WORK_US));
                    //baseline_array_clone.lock().unwrap().sort();
                }

                let elapsed = req_start.elapsed();
                latencies_clone.lock().unwrap().push(elapsed);

                // Natural minor phase delay to simulate dynamic packet network arrival
                if loop_idx % 10 == 0 {
                    thread::sleep(Duration::from_micros(5));
                }
            }
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }

    let mut final_latencies = latencies.lock().unwrap().clone();
    final_latencies.sort();
    final_latencies
}

fn analyze_latencies(name: &String, mut latencies: Vec<Duration>) {
    if latencies.is_empty() {
        return;
    }
    
    let sum: Duration = latencies.iter().sum();
    let mean = sum.as_secs_f64() * 1000.0 / (latencies.len() as f64);
    
    // Calculate P95 and P99 indices
    let p95_idx = (latencies.len() as f64 * 0.95) as usize;
    let p99_idx = (latencies.len() as f64 * 0.99) as usize;
    
    let p95 = latencies[p95_idx.min(latencies.len() - 1)].as_secs_f64() * 1000.0;
    let p99 = latencies[p99_idx.min(latencies.len() - 1)].as_secs_f64() * 1000.0;
    let max = latencies.last().unwrap().as_secs_f64() * 1000.0;

    println!("--- Results for {} ---", name);
    println!("Total Requests Processed : {}", latencies.len());
    println!("Mean Latency             : {:.4} ms", mean);
    println!("P95 Latency Tail         : {:.4} ms", p95);
    println!("P99 Latency Tail         : {:.4} ms (Critical Outlier Metric)", p99);
    println!("Max Latency              : {:.4} ms\n", max);
}

fn main() {
    println!("=============================================================");
    println!("STABILIZATION SIMULATION: STRUCTURAL JITTER VS PERFECT PACKING");
    println!("=============================================================\n");


    // Query the OS for logical core availability (including hyperthreading)
    match thread::available_parallelism() {
        Ok(cores) => {
            println!("=============================================================");
            println!("OS Schedulable Compute Lanes (Logical Cores): {}", cores);
            println!("=============================================================\n");
        }
        Err(e) => println!("Failed to read CPU core topology: {}", e),
    }

    // Initialize RNG seed
    let mut rng = SimpleRng::new(42);
    
    // 1. Generate baseline unsorted data array
    let mut baseline_array = Arc::new(Mutex::new(Vec::with_capacity(ARRAY_SIZE)));
    for _ in 0..ARRAY_SIZE {
        baseline_array.lock().unwrap().push(rng.next_i32());
    }

    // Bitmasks for mapping threads to specific logical core lanes:
    // Core 0 (Logical 0) = 1 (0001) | Core 0 (Logical 1) = 2 (0010)
    // Core 1 (Logical 2) = 4 (0100) | Core 1 (Logical 3) = 8 (1000)

    // high max latency
    let mut core_masks = vec![1, 2, 4, 8];
    let even_regime_title = String::from("Symmetric Even Topology (Perfect Packing Lattice)");
    let even_latencies = run_simulation(4, core_masks, false, baseline_array.clone(), rng.clone());
    analyze_latencies(&even_regime_title, even_latencies);

    // least max latency
    core_masks = vec![1, 2, 4];
    let odd_regime_title = String::from("Asymmetric Odd Topology (Structural Jitter Induced)");
    let odd_latencies = run_simulation(3, core_masks, true, baseline_array.clone(), rng.clone());
    analyze_latencies(&odd_regime_title, odd_latencies);

    // roughly between the least and high max latency
    core_masks = vec![1, 2, 4, 8];
    let odd_regime_title = String::from("Asymmetric Odd Topology (Structural Jitter Induced)");
    let odd_latencies = run_simulation(3, core_masks, true, baseline_array.clone(), rng.clone());
    analyze_latencies(&odd_regime_title, odd_latencies);

    // highest max latency
    core_masks = vec![1, 2, 4, 8];
    let odd_regime_title = String::from("Asymmetric Odd Topology (Structural Jitter Induced)");
    let odd_latencies = run_simulation(5, core_masks, true, baseline_array.clone(), rng.clone());
    analyze_latencies(&odd_regime_title, odd_latencies);
}

Simulation output

STABILIZATION SIMULATION: STRUCTURAL JITTER VS PERFECT PACKING

OS Schedulable Compute Lanes (Logical Cores): 4

1. High latency case --- Results for Symmetric Even Topology (Perfect Packing Lattice) --- Total Requests Processed : 100000 Mean Latency : 1.6827 ms P95 Latency Tail : 6.7510 ms P99 Latency Tail : 18.5086 ms (Critical Outlier Metric) Max Latency : 830.1799 ms

2. Minimum latency case --- Results for Asymmetric Odd Topology (Structural Jitter Induced) --- Total Requests Processed : 99999 Mean Latency : 1.5472 ms P95 Latency Tail : 6.2717 ms P99 Latency Tail : 21.1076 ms (Critical Outlier Metric) Max Latency : 267.1479 ms

3. Between minimum and high latency case --- Results for Asymmetric Odd Topology (Structural Jitter Induced) --- Total Requests Processed : 99999 Mean Latency : 1.5372 ms P95 Latency Tail : 6.2586 ms P99 Latency Tail : 21.0793 ms (Critical Outlier Metric) Max Latency : 313.6019 ms

4. Highest latency case --- Results for Asymmetric Odd Topology (Structural Jitter Induced) --- Total Requests Processed : 100000 Mean Latency : 2.2556 ms P95 Latency Tail : 6.2802 ms P99 Latency Tail : 13.3440 ms (Critical Outlier Metric) Max Latency : 2661.0666 ms

Analysis of simulation results

The simulation sets up a set of threads which run with affinity to particular cores (there are 4 in this case). We will note that, in the case of perfect packing, where the number of scheduled threads per batch is equal to the number of cores allocated per batch, the latency is high and is attributed to lockstep resonance. (830 ms)

When hyperthreading is turned off on one of the cores, there are 2 logical and 1 full core available for the threads, which leads to the minimum latency case. (267 ms)

With hyperthreading on, and the number of threads per batch being less than the number of logical cores available (3 threads vs 4 cores, in this case), asymmetric jitter is still introduced, but now, an additional core is being scheduled into by the OS from previous iterations, leading to some cache contention. So the latency is higher than the minimum, but is vastly lesser than the lockstep resonance induced by perfect packing. (313 ms)

Lastly, when 5 threads are scheduled on a machine with only 4 logical cores, we see the highest latency number, since the machine is being overutilized and there are lock contentions which increase the delay significantly. (2661 ms)