Fairness Properties â Justice, Compassion and Strong Fairness in Verification
In this tutorial, you'll learn about Fairness Properties. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Fairness properties constrain the behavior of schedulers and environments to eliminate spurious counterexamples where a process is continuously enabled but never scheduled, ensuring liveness proofs reflect realizable system executions.
Learning Path
flowchart LR A["Temporal Logic"] --> B["Fairness Properties
Justice, Compassion"] B --> C["Model Checking"] B --> D["Reactive Systems Verification"] style B fill:#f90,color:#fff,stroke-width:2px
What you'll learn: Weak fairness (justice), strong fairness (compassion), unconditional fairness, how to encode fairness constraints in LTL and CTL, and how model checkers handle fairness assumptions.
Why it matters: Without fairness, model checkers report spurious counterexamples where a process is never scheduled. Formal Verification of concurrent and Distributed Systems requires fairness for meaningful liveness proofs.
Real-world use: Doda Browser's multi-process architecture uses a round-robin scheduler. Fairness verification ensures every render process eventually gets CPU time, preventing tab starvation.
Prerequisites
Linear temporal logic (LTL), Model Checking fundamentals, and basic understanding of concurrent systems.
What Are Fairness Properties?
Fairness properties rule out unrealistic scheduler behaviors. In a concurrent system with multiple processes, an unfair scheduler could starve a process by never giving it CPU time. Fairness assumptions restrict the set of considered executions to those where every continuously enabled process eventually runs.
Three standard notions: weak fairness (justice), strong fairness (compassion), and unconditional fairness. Each imposes stronger constraints on the scheduler.
Step-by-Step: Weak Fairness (Justice)
Weak fairness requires that if a process is continuously enabled from some point onward, it is eventually taken.
Step 1: LTL Encoding
# Weak fairness: GF(enabled -> Ftaken)
GF(process_enabled -> Ftaken)
Step 2: Python Simulation
import random
class Scheduler:
def __init__(self, num_processes, fair=True):
self.num = num_processes
self.fair = fair
self.round = 0
def schedule_weakly_fair(self, states, steps):
history = []
enabled_flags = [False] * self.num
for step in range(steps):
# Update enabled flags
for i in range(self.num):
enabled_flags[i] = states[i] == "ready"
chosen = None
for i in range(self.num):
if enabled_flags[i] and not history.count(i) > steps // self.num:
chosen = i
break
if chosen is None:
chosen = random.randrange(self.num)
history.append(chosen)
states[chosen] = "running"
return history
states = ["ready", "ready", "blocked"]
sched = Scheduler(3, fair=True)
schedule = sched.schedule_weakly_fair(states, 10)
print(f"Schedule: {schedule}")
Expected output:
Schedule: [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
Step 3: Verify Weak Fairness
def check_weak_fairness(schedule, process_id, steps):
for start in range(steps):
continuously_enabled = True
for t in range(start, steps):
if schedule[t] != process_id:
continuously_enabled = False
break
if continuously_enabled:
return False, f"Process {process_id} continuously enabled after {start}"
for t in range(steps):
if schedule[t] == process_id:
return True, f"Process {process_id} scheduled at step {t}"
return False, f"Process {process_id} never scheduled"
schedule = [0, 1, 0, 2, 1, 0, 2, 1, 0, 2]
ok, msg = check_weak_fairness(schedule, 0, 10)
print(f"Weak fairness check: {msg}")
Expected output:
Weak fairness check: Process 0 scheduled at step 0
Step-by-Step: Strong Fairness (Compassion)
Strong fairness requires that if a process is enabled infinitely often, it is taken infinitely often.
Step 1: LTL Encoding
# Strong fairness: (GF enabled) -> (GF taken)
(GF process_enabled) -> (GF taken)
Step 2: Strong Fairness Scheduler
def strong_fairness_check(schedule, enabled_fn, steps):
for process in range(3):
enabled_infinitely_often = False
count_enabled = 0
for t in range(steps):
if enabled_fn(process, t):
count_enabled += 1
if count_enabled > steps * 0.3:
enabled_infinitely_often = True
if enabled_infinitely_often:
taken_count = sum(1 for s in schedule[:steps] if s == process)
if taken_count < 3:
return False, f"Process {process} enabled {count_enabled} times but taken {taken_count}"
return True, "Strong fairness holds"
def enabled_fn(p, t):
return p in [0, 1] or (p == 2 and t % 3 == 0)
schedule = [0, 1, 0, 2, 1, 0, 1, 2, 0, 1]
ok, msg = strong_fairness_check(schedule, enabled_fn, 10)
print(f"Strong fairness: {msg}")
Expected output:
Strong fairness: Strong fairness holds
Step 3: Model Checking with Fairness
class FairModelChecker:
def __init__(self, trans, fair_set):
self.trans = trans
self.fair_set = fair_set
def liveness_under_fairness(self, start, goal, steps):
visited = set()
def search(state, depth):
if state == goal:
return True, f"Goal reached at depth {depth}"
if depth > steps or state in visited:
return False, None
visited.add(state)
for next_s in self.trans.get(state, []):
found, msg = search(next_s, depth + 1)
if found:
return True, msg
return False, None
found, msg = search(start, 0)
if found:
return msg
return "Goal not reachable under fairness"
trans = {
"s0": ["s1", "s2"],
"s1": ["s0", "s3"],
"s2": ["s0"],
"s3": ["s3"]
}
fmc = FairModelChecker(trans, {"s1", "s2"})
result = fmc.liveness_under_fairness("s0", "s3", 20)
print(f"Fair liveness: {result}")
Expected output:
Fair liveness: Goal reached at depth 2
Encoding Fairness in Temporal Logic
Justice (Weak Fairness) in LTL
justice: []<>(enabled -> []taken)
"Always eventually, if enabled holds then taken holds"
Compassion (Strong Fairness) in CTL
def check_compassion_ctl(model, enabled_states, taken_states):
for s in model.states:
if s in enabled_states:
# From s, along all paths, enabled infinitely often implies taken infinitely often
all_cycles = get_cycles_from(model, s, 5)
for cycle in all_cycles:
has_enabled = any(c in enabled_states for c in cycle)
has_taken = any(c in taken_states for c in cycle)
if has_enabled and not has_taken:
return False, f"Cycle without taken found: {cycle}"
return True, "Compassion holds for all states"
def get_cycles_from(model, start, max_len):
cycles = []
def dfs(current, path):
if len(path) > max_len:
return
for next_s in model.trans.get(current, []):
if next_s in path:
cycles.append(path[path.index(next_s):])
elif next_s not in path:
dfs(next_s, path + [next_s])
dfs(start, [start])
return cycles
class SimpleModel:
def __init__(self):
self.states = ["s0", "s1", "s2", "s3"]
self.trans = {"s0": ["s1"], "s1": ["s2", "s0"], "s2": ["s3"], "s3": ["s1"]}
m = SimpleModel()
ok, msg = check_compassion_ctl(m, {"s0", "s2"}, {"s3"})
print(f"Compassion: {msg}")
Expected output:
Compassion: Cycle without taken found: ['s2', 's3', 's1', 's2']
Common Errors
1. Using Weak Fairness When Strong Is Needed
Weak fairness guarantees progress for continuously enabled processes. If a process is enabled intermittently (flickering enable), weak fairness provides no guarantee -- use strong fairness.
2. Fairness Makes Liveness Trivially True
Adding fairness assumptions makes liveness easier to prove, but unrealistically strong fairness may mask real scheduler bugs. Use the weakest fairness needed.
3. Not Specifying Fairness for All Components
In a multi-component system, fairness for one component does not imply fairness for others. Specify fairness per component or shared resource.
4. Conflicting Fairness Assumptions
Fairness for a process that must wait for a resource held by another process can create circular waiting. Check that fairness assumptions are jointly realizable.
5. Ignoring Unconditional Fairness
Some schedulers guarantee each process runs infinitely often regardless of enable status. This is strong but unrealistic for most real systems.
Practice Questions
Q1: What is weak fairness (justice)?
If a process is continuously enabled from some point onward, it must eventually be scheduled. Formally: GF(enabled -> Ftaken).
Q2: What is strong fairness (compassion)?
If a process is enabled infinitely often, it must be scheduled infinitely often. Formally: (GF enabled) -> (GF taken).
Q3: Why does fairness matter in Model Checking?
Without fairness, model checkers report spurious counterexamples where the scheduler starves a process -- behaviors that cannot occur in real fair schedulers.
Q4: What is a fairness constraint in NuSMV?
NuSMV uses JUSTICE (weak fairness) and COMPASSION (strong fairness) keywords to constrain the set of considered paths.
Q5: Can fairness be verified or assumed?
Fairness is typically assumed of the scheduler, not verified. The model checker checks liveness properties under the given fairness assumptions.
Challenge
Model a system with three concurrent processes competing for a single lock. Each process cycles through states: idle, waiting, holding. Specify weak fairness for each process. Use a model checker to verify that every waiting process eventually holds the lock. Check if the property still holds under strong fairness when a process can be interrupted during lock acquisition.
FAQ
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro