CoreSource checked

Lottery Scheduling

Allocates CPU time by randomly drawing tickets assigned to competing jobs.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Scheduling
Difficulty: Beginner
Family: Probabilistic Scheduling
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 1
Code example: Ready
Visualization: Ready

Overview

Lottery scheduling gives each job tickets proportional to its share, then uses random selection to approximate proportional fairness over time.

Core Concepts

ticket sharerandom drawproportional fairnessscheduler queue

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(n)

Worst

O(n)

Space

O(n)

When to Use

Use when ordering jobs needs ticket share.
Use when the input matches the assumptions behind probabilistic Scheduling.

When Not to Use

Avoid when the real constraints are not represented in the scheduling model.
Avoid when a simpler algorithm gives the required result with less setup.

What It Does

Allocates CPU time by randomly drawing tickets assigned to competing jobs
Uses ticket share and random draw to guide the work.
Produces schedule.

Use Cases

Ordering jobs
Allocating compute time
Planning constrained work

Inputs

Jobs or tasks
Durations, deadlines, or priorities

Outputs

Schedule
Start and finish times
Queue decisions

Key Formulas (1)

Selection probability

P(job) = tickets(job) / total_tickets

P(job) = tickets(job) / total_tickets

Gives each job a chance proportional to its ticket count.

Pseudocode

1.Collect ready tasks and their release times, durations, priorities, or deadlines
2.Choose the next task according to the scheduling rule
3.Advance time, update remaining work, and add newly ready tasks
4.Repeat until every task is completed or no feasible schedule remains

Canonical Example

Input: tasks = A(duration=2, deadline=5), B(duration=1, deadline=3), C(duration=3, deadline=8)
Output: Schedule
Explanation: Lottery Scheduling applies ticket share to produce schedule.

Implementation Notes

Keep the scheduling objective explicit so tie-breaking rules are consistent.
Keep the ticket share step separate enough to test independently.
State whether the policy is preemptive and what fairness, latency, or deadline objective it optimizes.

Common Pitfalls

Optimizing one metric can harm fairness, latency, or deadline behavior.
Test edge cases, not only clean examples.
Ignoring preemption cost, release times, or starvation can make a schedule look correct only in toy cases.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show jobs on a timeline with queue order, start times, and constraints.

Step 1 of 4: Collect ready tasks and their release times, durations, priorities, or deadlines

scheduling-mechanism

Notes

Lottery Scheduling should be used with the assumptions and tradeoffs of probabilistic Scheduling in mind.

Sources (1)

What each reference supports for this entry.