সরাসরি পর্বে যান
পর্ব ৭৭ · ৮৫-এর মধ্যে · মডিউল ১৩

Model checking — Büchi automaton আর temporal logic

Model Checking — Kripke Structures, LTL and CTL, Büchi Automata, Nested DFS, Fairness and a Real NuSMV Run

Taught in Bangla, this lesson models a concurrent system as a Kripke structure, defines safety and liveness, and gives LTL and CTL semantics. It proves Büchi emptiness checking and model checks LTL through the product automaton with nested DFS, then covers state explosion, symbolic methods and SAT-based bounded model checking. In-page Python (Pyodide) and JavaScript find lasso counterexamples, and a real NuSMV 2.7.1 run catches a seeded lock bug, confirms the fix and shows liveness holds only under fairness.

এই পর্বে যা শিখবেন

  • Kripke structure দিয়ে একটি concurrent system-কে গণিতের ভাষায় লেখা, আর safety ও liveness-এর নিখুঁত সংজ্ঞা
  • LTL-এর syntax আর semantics, CTL-এর path quantifier, আর দুটির প্রকাশক্ষমতার পার্থক্য
  • Büchi automaton, তার emptiness পরীক্ষার প্রমাণ, আর product ও nested DFS দিয়ে LTL model checking
  • NuSMV দিয়ে একটি সত্যিকারের bug ধরা, counterexample পড়া, fix করে আবার যাচাই, আর fairness-এর ভূমিকা
  • State explosion কেন হয়, আর symbolic পদ্ধতি, SAT-ভিত্তিক bounded model checking ও অন্যান্য প্রতিকার

১ · Test যে bug দেখে না — কেন model checking

ঈদের sale-এ বাজারঘরের গুদামে একটি জনপ্রিয় পাঞ্জাবির মাত্র একটি পিস বাকি। দুজন গুদাম-কর্মী, w1 আর w2, একই মুহূর্তে দুটি আলাদা অর্ডার প্রসেস করছেন, দুটিতেই টাকা দেওয়া হয়ে গেছে। Stock-এর রেকর্ড একসঙ্গে দুজন ছুঁলে গোলমাল হতে পারে, তাই প্রোগ্রামার একটি lock রেখেছেন। কোডটি এমন: “lock খালি কি না দেখুন; খালি হলে lock নিন; stock দেখুন; থাকলে একটি কমিয়ে ডেলিভারিতে পাঠান, না থাকলে টাকা ফেরত দিন।” হাজারবার test-এ সব ঠিক, তারপর একদিন একই পিস দুজনকে বিক্রি হয়ে যায়।

একটি সরু গলির কথা ভাবুন, যেখানে একবারে একটি রিকশাই ঢুকতে পারে। দুই দিক থেকে দুই রিকশাওয়ালা একই মুহূর্তে মাথা বাড়িয়ে দেখেন, গলি ফাঁকা। দুজনই প্যাডেলে চাপ দেন, আর মাঝপথে মুখোমুখি। “দেখা” আর “ঢোকা” দুটি আলাদা মুহূর্ত, আর তার মাঝের ফাঁকেই দুর্ঘটনা। বাজারঘরের lock-এর bug ঠিক এটিই: “lock খালি” দেখা আর “lock নেওয়া” দুটি আলাদা ধাপ।

Test এই bug সহজে ধরে না, কারণ ফল নির্ভর করে দুই কর্মীর ধাপ কোন ক্রমে মিশল তার ওপর, যাকে বলে interleaving. প্রত্যেকে ৪টি ধাপ করলে মোট interleaving-এর সংখ্যা C(8, 4) = 70; প্রত্যেকে ১০টি ধাপ করলে C(20, 10) = 184,756. Bug দেখা দেয় এদের অল্প কয়েকটিতে, আর কোনটি ঘটবে তা ঠিক করে scheduler, test নয়। এমন bug-কে race condition বলে; Operating Systems কোর্সের পর্ব ২২-এ এর পরিচয় আর পর্ব ২৭-এ এর আত্মীয় deadlock আছে। এখানে প্রশ্নটি অন্য: এমন bug গাণিতিকভাবে নিশ্চিতভাবে খোঁজা যায় কীভাবে?

সংজ্ঞা ১.১ (Model checking problem)

Input: একটি সসীম মডেল M (সিস্টেমের সব সম্ভাব্য আচরণ) আর একটি temporal logic সূত্র φ (যা চাই)। প্রশ্ন: M ⊨ φ, অর্থাৎ M-এর প্রতিটি আচরণ কি φ মানে? উত্তর “না” হলে algorithm একটি counterexample দেয়: M-এর একটি নির্দিষ্ট আচরণ যা φ ভাঙে।

Model checking-এর তিনটি উপাদান: একটি মডেল (এই পর্বে Kripke structure), একটি specification ভাষা (LTL বা CTL) আর একটি algorithm (automata দিয়ে)। পর্ব ২৪-এ বাজারঘরের অর্ডার workflow-এর configuration graph-এ BFS চালিয়ে “খারাপ configuration-এ পৌঁছানো যায় কি না” খুঁজেছিলেন। সেটি ছিল model checking-এর সবচেয়ে সরল রূপ। এই পর্ব তিনটি দিকে এগোয়: concurrency, “একসময় ঘটবেই” ধরনের দাবি, আর দাবি লেখার একটি নিখুঁত ভাষা।

ইতিহাস: Amir Pnueli ১৯৭৭ সালে “The Temporal Logic of Programs” প্রবন্ধে প্রস্তাব করেন যে চলতেই থাকা program (যেমন operating system বা protocol) নিয়ে যুক্তির জন্য temporal logic উপযুক্ত; এ কাজের জন্য তিনি ১৯৯৬ সালের Turing Award পান। Edmund Clarke আর E. Allen Emerson ১৯৮১ সালে, আর স্বাধীনভাবে Jean-Pierre Queille ও Joseph Sifakis ১৯৮২ সালে, সসীম মডেলে temporal সূত্র স্বয়ংক্রিয়ভাবে যাচাইয়ের পদ্ধতি দেন; এই তিনজন ২০০৭ সালের Turing Award পান বলে পরিচিত। আজ hardware, protocol আর নিরাপত্তা-গুরুত্বপূর্ণ software-এ model checker নিয়মিত ব্যবহৃত হয়।

২ · Kripke structure — সিস্টেমের গাণিতিক মডেল

DFA (পর্ব ০৭) একটি input পড়ে থামে। গুদামের কর্মী, ব্যাংকের server বা লিফটের controller থামে না; তারা চিরকাল চলে, আর প্রতিটি মুহূর্তে কিছু তথ্য সত্য বা মিথ্যা (“অর্ডার paid”, “lock নেওয়া”)। এমন সিস্টেমের মডেলের নাম দার্শনিক Saul Kripke-এর নামে।

সংজ্ঞা ২.১ (Kripke structure)

একটি Kripke structure হলো M = (S, S0, R, AP, L), যেখানে

  1. S অবস্থার একটি সসীম সেট, আর S0 ⊆ S শুরুর অবস্থাগুলো;
  2. R ⊆ S × S transition relation, যা total: প্রতিটি s-এর অন্তত একটি পরের অবস্থা s′ আছে, (s, s′) ∈ R;
  3. AP atomic proposition-এর একটি সসীম সেট, যেমন paid, done, crit1;
  4. L: S → P(AP) একটি labelling, যা বলে কোন অবস্থায় কোন proposition সত্য।

M-এর একটি পথ হলো অসীম ক্রম π = s0 s1 s2 …, যেখানে s0 ∈ S0 আর প্রতিটি i-তে (si, si+1) ∈ R. পথটির trace হলো L(s0) L(s1) L(s2) …, alphabet Σ = P(AP)-এর ওপর একটি অসীম word.

R total বলে প্রতিটি পথ অসীম; শেষ অবস্থা (যেমন Delivered) একটি self-loop পায়। কোনো অবস্থার পরের অবস্থা একেবারে না থাকলে সেটি deadlock, যা NuSMV-এর মতো tool আলাদা করে সতর্ক করে। Kripke structure-কে input ছাড়া একটি Moore machine (পর্ব ১২) ভাবা যায়, যার output প্রতিটি অবস্থার label; nondeterminism (পর্ব ০৯) এখানে পরিবেশের পছন্দ, যেমন scheduler কাকে চালাবে।

একটি অর্ডারের মডেল আর একটি Büchi automaton

ওপরে Kripke structure, নিচে “কোনো paid অর্ডার কখনো শেষ হয় না” চেনার automaton. দুই দাগের বৃত্ত accepting.

Kripke structure of one order and the Büchi automaton for its violation Kripke structure M s0s1s2 q0q1 {paid}{ }{done} true¬done paid∧¬done Paidঅপেক্ষাDelivered Büchi automaton A¬φ φ = G(paid → F done) q1 অসীমবার এলে গ্রহণ: অর্ডার কখনো শেষ হয় না
ছবি ৭৭.১ — ওপরে একটি অর্ডারের Kripke structure: s0 (paid), s1 (কুরিয়ারের অপেক্ষা, যেখানে চিরকাল আটকে থাকা সম্ভব) আর s2 (done). নিচে φ-এর অস্বীকৃতি ¬φ-এর Büchi automaton. পথ s0 s1 s1 s1 … φ ভাঙে, আর automaton সেটি q0 q1 q1 q1 … run দিয়ে গ্রহণ করে।

বাজারঘরের দুই কর্মীর সিস্টেমে একটি অবস্থা হলো (pc1, pc2, lock, stock): প্রতিটি কর্মী কোন ধাপে (pc মানে program counter), lock নেওয়া কি না, আর stock-এ কয়টি পিস। প্রতিটি transition-এ একজন কর্মী এক ধাপ এগোন, আর কে, তা scheduler-এর nondeterministic পছন্দ। প্রতিটি কর্মীর ৭টি ধাপ, lock-এর ২টি আর stock-এর ৩টি মান: সর্বোচ্চ ৭ × ৭ × ২ × ৩ = ২৯৪টি অবস্থা। n জন কর্মী হলে সংখ্যাটি 7n-এর হারে বাড়ে: state explosion, যা অংশ ৯-এ ফিরবে।

৩ · Safety আর liveness — দুই ধরনের দাবি

অসীম পথ নিয়ে কথা বলতে অসীম word লাগে। Alphabet Σ-এর ওপর একটি ω-word হলো অসীম ক্রম w = a0 a1 a2 …, আর সব ω-word-এর সেট Σω. একটি property হলো P ⊆ Σω: যে আচরণগুলো “গ্রহণযোগ্য”। Leslie Lamport ১৯৭৭ সালে দুটি শ্রেণির নাম দেন, আর Bowen Alpern ও Fred Schneider ১৯৮৫ সালে তাদের নিখুঁত সংজ্ঞা দেন বলে পরিচিত।

সংজ্ঞা ৩.১ (Safety আর liveness)
  • P একটি safety property, যদি প্রতিটি w ∉ P-এর একটি সসীম prefix u থাকে, যার প্রতিটি অসীম বিস্তার uw′ ∉ P. এমন u-কে বলে bad prefix: ভুলটি একটি সসীম মুহূর্তে ঘটে গেছে, পরে আর শোধরানো যায় না।
  • P একটি liveness property, যদি প্রতিটি সসীম u ∈ Σ∗-কে বাড়িয়ে P-এর একটি সদস্য uw′ বানানো যায়: কোনো সসীম ইতিহাসই আশা শেষ করে না।

প্রস্তাব ৩.২. “দুই কর্মী কখনো একসঙ্গে critical section-এ নন” একটি safety property, আর “paid অর্ডার একসময় done হয়” একটি liveness property.

  1. প্রথমটি ভাঙে এমন যেকোনো আচরণে একটি প্রথম মুহূর্ত i আছে, যখন crit1 ∧ crit2 সত্য। a0 … ai একটি bad prefix: এর পরে যা-ই ঘটুক, একসঙ্গে থাকার ঘটনা মোছে না। — সংজ্ঞা থেকে
  2. দ্বিতীয়টির জন্য যেকোনো সসীম u নিন। u-এর পরে একটি “done” অক্ষর আর তারপর চিরকাল “done” জুড়ে দিলে প্রতিটি paid-এর পরে done আসে। তাই কোনো সসীম prefix আশা শেষ করে না। — বিস্তার নির্মাণ
  3. দ্বিতীয়টি safety নয়: ধরুন সেটি safety. তবে “paid, তারপর চিরকাল অপেক্ষা” আচরণের একটি bad prefix u থাকত, কিন্তু ধাপ ২ দেখায় u-কে বাড়িয়ে সন্তুষ্ট করা যায়, বিরোধ। ∎

ব্যবহারিক মানে বড়। Safety ভাঙার প্রমাণ সসীম, তাই safety যাচাই হলো reachability, পর্ব ২০-এর emptiness-এর মতো BFS দিয়েই। Liveness ভাঙার প্রমাণ একটি অসীম পথ, যা সসীম মডেলে একটি চক্র; তাই চক্র খুঁজতে হয়, আর অসীম word-এর automaton লাগে। Alpern আর Schneider দেখান, প্রতিটি property একটি safety আর একটি liveness property-র ছেদ (প্রমাণ বাদ)।

সাধারণ ভুল: “অর্ডার ৩ দিনের মধ্যে ডেলিভারি হবে” liveness নয়, safety: ৩ দিন পার হয়ে গেলে একটি সসীম bad prefix পাওয়া যায়। Liveness-এ কোনো সময়সীমা থাকে না, শুধু “একসময়”। এজন্যই liveness নিয়ে test একা কিছু প্রমাণ করতে পারে না: test সবসময় সসীম সময় চলে।

৪ · LTL আর CTL — অসীম পথের ওপর যুক্তি

Linear temporal logic (LTL) সাধারণ Boolean যুক্তির সঙ্গে সময়ের চারটি operator যোগ করে। “Linear” কারণ এটি একটি একক পথের ওপর কথা বলে, পথটি একটি রেললাইনের মতো সামনে সোজা চলে।

সংজ্ঞা ৪.১ (LTL-এর syntax আর semantics)

Syntax: φ ::= p ∣ ¬φ ∣ φ ∧ φ ∣ X φ ∣ φ U φ, যেখানে p ∈ AP. বাকিগুলো সংক্ষেপ: φ ∨ ψ, φ → ψ সাধারণ অর্থে; F φ ≡ true U φ; G φ ≡ ¬F ¬φ.

Semantics: w = a0 a1 … ∈ (P(AP))ω, আর wi = ai ai+1 … হলো i-তম অবস্থান থেকে শুরু হওয়া শেষাংশ।

  • w ⊨ p ⇔ p ∈ a0; ¬ আর ∧ সাধারণ অর্থে।
  • w ⊨ X φ ⇔ w1 ⊨ φ (“পরের মুহূর্তে”, next).
  • w ⊨ φ U ψ ⇔ কোনো j ≥ 0-এ wj ⊨ ψ, আর সব i < j-এ wi ⊨ φ (“ψ আসা পর্যন্ত φ”, until).

ফলে w ⊨ F φ ⇔ কোনো j-এ wj ⊨ φ (“একসময়”, eventually), আর w ⊨ G φ ⇔ সব j-এ wj ⊨ φ (“সবসময়”, globally). Kripke structure-এর জন্য M ⊨ φ ⇔ M-এর প্রতিটি পথের trace φ মানে।

কিছু বইয়ে F-কে ◇, G-কে □ আর X-কে ◯ লেখা হয়; অর্থ একই। লক্ষ করুন, M ⊭ φ মানে M ⊨ ¬φ নয়: কিছু পথ φ মানতে পারে আর কিছু না মানতে পারে, তখন দুটিই মিথ্যা। নিচের সারণিতে বাজারঘরের কিছু দাবি LTL-এ।

বাংলায় দাবিLTLধরন
দুই কর্মী কখনো একসঙ্গে critical section-এ ননG ¬(crit1 ∧ crit2)safety
Paid প্রতিটি অর্ডার একসময় delivered বা refundedG(paid → F(delivered ∨ refunded))liveness (response)
Refund হওয়া অর্ডার আর কখনো delivered নয়G(refunded → G ¬delivered)safety
Pack হওয়া পর্যন্ত ship নয়, আর pack একসময় হবেই¬shipped U packedsafety আর liveness মিশ্র
ডেলিভারি অসীমবার ঘটে (সিস্টেম থেমে যায় না)G F deliveredliveness
একসময় থেকে সিস্টেম চিরকাল স্থিরF G stableliveness (persistence)

সসীম মডেলের counterexample সবসময় একটি lasso আকারের: শুরুর একটি সসীম অংশ u, তারপর একটি সসীম অংশ v চিরকাল পুনরাবৃত্ত, অর্থাৎ u v v v … = u vω. কারণটি অংশ ৫-এ প্রমাণ হবে। তাই একটি LTL সূত্র lasso-র ওপর মূল্যায়ন করতে জানলেই counterexample যাচাই করা যায়, আর এই হিসাব সসীম: lasso-তে মাত্র |u| + |v|টি আলাদা অবস্থান। নিচের JavaScript প্রতিটি উপসূত্রের জন্য “কোন অবস্থানে সত্য” সেট বের করে। U-এর জন্য এটি একটি least fixpoint: যেখানে ψ সত্য সেখান থেকে শুরু করে, “φ সত্য আর পরের অবস্থান ইতিমধ্যে সেটে” এমন অবস্থান যোগ করতে থাকে, যতক্ষণ সেট বাড়ে।

// A lasso trace u v v v ...: each position is a string of true propositions
// p = paid, d = delivered. Formula = nested arrays, e.g. ["G", ["->", "p", ["F", "d"]]]
function holds(f, u, v) {
  const w = u.concat(v), n = w.length, next = i => (i + 1 < n ? i + 1 : u.length);
  function sat(f) {                       // the set of positions where f is true
    if (f === "true") return w.map(() => true);
    if (typeof f === "string") return w.map(s => s.includes(f));
    const [op, a, b] = f, A = sat(a), B = b ? sat(b) : null;
    if (op === "!") return A.map(x => !x);
    if (op === "&") return A.map((x, i) => x && B[i]);
    if (op === "->") return A.map((x, i) => !x || B[i]);
    if (op === "X") return A.map((_, i) => A[next(i)]);
    if (op === "U") {                     // least fixpoint: grow until stable
      const S = B.slice(); let grew = true;
      while (grew) { grew = false;
        for (let i = 0; i < n; i++)
          if (!S[i] && A[i] && S[next(i)]) { S[i] = true; grew = true; } }
      return S;
    }
    if (op === "F") return sat(["U", "true", a]);
    if (op === "G") return sat(["!", ["F", ["!", a]]]);
  }
  return sat(f)[0];
}
const traces = { A: [["p", "p"], ["pd"]], B: [["", "p"], ["p"]],
                 C: [[], ["", "d", "pd"]] };
const formulas = [["G(p -> F d)", ["G", ["->", "p", ["F", "d"]]]],
  ["F G d", ["F", ["G", "d"]]], ["G F d", ["G", ["F", "d"]]],
  ["p U d", ["U", "p", "d"]], ["X p", ["X", "p"]]];
for (const [name, f] of formulas)
  console.log(name.padEnd(12), Object.entries(traces)
    .map(([t, [u, v]]) => `${t}:${holds(f, u, v) ? "T" : "F"}`).join("  "));

আসল আউটপুট (ব্রাউজারের JavaScript):

G(p -> F d)  A:T  B:F  C:T
F G d        A:T  B:F  C:F
G F d        A:T  B:F  C:T
p U d        A:T  B:F  C:F
X p          A:T  B:T  C:F

তিনটি trace: A-তে দুবার paid, তারপর চিরকাল paid আর delivered; B-তে paid আসে কিন্তু delivered কখনো নয়; C-তে চক্রে “কিছু না, delivered, paid ও delivered” ঘোরে। G(p → F d) A আর C-তে সত্য, B-তে মিথ্যা: B হলো liveness-এর একটি counterexample, একটি lasso. F G d শুধু A-তে সত্য; C-তে d অসীমবার আসে (G F d সত্য) কিন্তু প্রতি তিন অবস্থানে একবার d মিথ্যা, তাই “একসময় থেকে চিরকাল” নয়। p U d শুধু A-তে সত্য, কারণ B-তে d কখনো আসে না আর C-র শুরুতে p-ও নেই, d-ও নেই। প্রতিটি U-এর fixpoint বড়জোর n = |u| + |v| বার ঘোরে, তাই মোট কাজ O(|φ| · n2).

CTL সংক্ষেপে — “সব পথে” বনাম “কোনো একটি পথে”

LTL প্রতিটি পথকে আলাদা করে দেখে। কিন্তু কখনো প্রশ্নটি সম্ভাবনার: “যেকোনো অবস্থা থেকে কি আবার শুরুর অবস্থায় ফেরা সম্ভব?” এর উত্তর দিতে পথের ওপর quantifier লাগে। Computation tree logic (CTL) Kripke structure-কে একটি অসীম গাছ হিসেবে দেখে, যার প্রতিটি শাখা একটি সম্ভাব্য ভবিষ্যৎ।

সংজ্ঞা ৪.২ (CTL)

Path quantifier A (“সব পথে”) আর E (“অন্তত একটি পথে”), আর প্রতিটির ঠিক পরেই একটি temporal operator: AX, EX, AF, EF, AG, EG, A[φ U ψ], E[φ U ψ]. সূত্র অবস্থার ওপর সত্য বা মিথ্যা: যেমন s ⊨ EF p ⇔ s থেকে কোনো পথে একসময় p; s ⊨ AG p ⇔ s থেকে সব পথে সবসময় p. M ⊨ φ ⇔ প্রতিটি শুরুর অবস্থা φ মানে।

উদাহরণ: AG(pc1 = try → EF pc1 = check) বলে “w1 অপেক্ষায় থাকলে সবসময় এমন একটি ভবিষ্যৎ আছে যেখানে তিনি ঢোকেন”: নিশ্চয়তা নয়, সম্ভাবনা। LTL-এর G(try → F check) চায় প্রতিটি পথে ঢোকা। দুই যুক্তির ক্ষমতা তুলনাযোগ্য নয়।

বিষয়LTLCTL
সূত্র কীসের ওপরএকটি পথ; M ⊨ φ মানে সব পথএকটি অবস্থা আর তার ভবিষ্যৎ-গাছ
শুধু এতে প্রকাশযোগ্যF G p (“একসময় থেকে চিরকাল p”)AG EF p (“সবসময় p-তে ফেরা সম্ভব”)
Model checking-এর সময়O(|M| · 2O(|φ|)), সমস্যাটি PSPACE-completeO(|M| · |φ|), রৈখিক
Fairnessসূত্রের ভেতরেই লেখা যায়আলাদা fair-CTL লাগে

F G p কেন AF AG p নয়: M নিন: s0 ({p}) নিজের ওপর loop করে আর s1-এ যেতে পারে; s1 ({ }) থেকে s2; s2 ({p}) নিজের ওপর loop. প্রতিটি পথ হয় চিরকাল s0-তে, নয় শেষে চিরকাল s2-তে, তাই M ⊨ F G p. কিন্তু s0-তে সবসময় s1-এর শাখা খোলা, তাই s0 কখনো AG p মানে না, আর M ⊭ AF AG p. উল্টো দিকে AG EF p কোনো LTL সূত্রে লেখা যায় না বলে প্রমাণিত। দুটিকে একসঙ্গে ধারণ করে CTL∗ (Emerson ও Halpern, ১৯৮৬)।

৫ · ω-word আর Büchi automaton

LTL সূত্রকে algorithm-এ বদলানোর পথ automata. কিন্তু পর্ব ০৯-এর NFA-র গ্রহণের নিয়ম, “শেষে accepting state-এ”, অসীম word-এ অর্থহীন: অসীম word-এর কোনো শেষ নেই। Julius Richard Büchi ১৯৬২ সালে এর সমাধান দেন: শেষের বদলে “অসীমবার”।

সংজ্ঞা ৫.১ (Büchi automaton)

একটি nondeterministic Büchi automaton (NBA) হলো A = (Q, Σ, δ, q0, F), NFA-র মতোই, δ: Q × Σ → P(Q). ω-word w = a0 a1 …-এর ওপর একটি run হলো অসীম ক্রম r = r0 r1 …, যেখানে r0 = q0 আর ri+1 ∈ δ(ri, ai). Run-টি accepting, যদি F-এর কোনো state r-এ অসীমবার আসে। L(A) = {w : w-এর অন্তত একটি accepting run আছে}. কোনো NBA যে language চেনে, তাকে ω-regular language বলে।

ছবি ৭৭.১-এর নিচের automaton-টি দেখুন। q0 প্রতিটি অক্ষরে q0-তে থাকতে পারে, আর “paid কিন্তু done নয়” পড়লে q1-এ যাওয়ার অনুমান করতে পারে: “এই অর্ডারটিই কখনো শেষ হবে না।” q1 শুধু ¬done-এ টিকে থাকে; done এলে ওই run মরে যায়। তাই একটি accepting run আছে ঠিক তখন, যখন কোনো paid-এর পরে done আর কখনো আসে না, অর্থাৎ w ⊨ F(paid ∧ G ¬done) = ¬φ. এখানে nondeterminism অপরিহার্য: কোন paid-টি “চিরকাল অপেক্ষা” করবে, তা automaton আগে থেকে জানে না, তাই অনুমান করে।

NFA থেকে একটি বড় পার্থক্য: nondeterminism এখানে বাড়তি ক্ষমতা দেয়। Deterministic Büchi automaton (DBA) সব ω-regular language চেনে না; F G b এর ক্লাসিক উদাহরণ (অনুশীলন ১)। NBA union, intersection আর complement-এ বন্ধ; complement কঠিন, যা Büchi নিজে প্রমাণ করেন, আর Shmuel Safra ১৯৮৮ সালে প্রায় সর্বোত্তম নির্মাণ দেন বলে পরিচিত।

লেমা ৫.২ (Büchi emptiness)

L(A) ≠ ∅ ⇔ এমন একটি f ∈ F আছে, যা q0 থেকে পৌঁছানো যায় আর যা থেকে অন্তত এক ধাপে আবার f-এ ফেরা যায় (f একটি চক্রের ওপর)। ফলে L(A) ≠ ∅ হলে L(A)-তে একটি lasso word u vω আছে।

প্রমাণ:

  1. (⇐) ধরুন q0 থেকে f-এ u পড়ে আর f থেকে f-এ v (|v| ≥ 1) পড়ে যাওয়া যায়। তাহলে u v v v …-এর একটি run আছে, যা f-এ অসীমবার আসে, তাই u vω ∈ L(A). — run নির্মাণ
  2. (⇒) ধরুন w-এর একটি accepting run r. F-এর state অসীমবার আসে, আর F সসীম, তাই pigeonhole নীতিতে F-এর কোনো একটি f r-এ অসীমবার আসে। — pigeonhole
  3. f-এর প্রথম আগমন দেখায় f পৌঁছানো যায়; পরপর দুটি আগমনের মাঝের অংশ দেখায় f থেকে অন্তত এক ধাপে f-এ ফেরা যায়। — run-এর অংশ
  4. তাই শর্তটি সত্য, আর ধাপ ১-এর নির্মাণ থেকে একটি lasso word পাওয়া যায়। ∎

লেমাটি একটি রৈখিক-সময়ের algorithm দেয়: reachability আর চক্র খোঁজা (strongly connected component দিয়ে, DSA কোর্সের পর্ব ৪৬, অথবা অংশ ৬-এর nested DFS দিয়ে)। এটি পর্ব ২০-এর NFA emptiness-এর অসীম রূপ। নিচের code দুটি automaton-কে lasso word-এ চালায়: ছবির NBA আর “G F done” (অসীমবার ডেলিভারি) চেনা একটি DBA. Lasso-তে (state, অবস্থান) জোড়ের graph সসীম, তাই accepting চক্র খুঁজলেই হয়।

# Letters: "p" = paid (not done), "d" = done, "-" = neither.
# N: nondeterministic Buchi automaton for NOT G(paid -> F done)
N = ({("q0", c): {"q0"} for c in "pd-"} | {("q0", "p"): {"q0", "q1"},
     ("q1", "p"): {"q1"}, ("q1", "-"): {"q1"}}, "q0", {"q1"})
# D: deterministic Buchi automaton for G F done ("infinitely many deliveries")
D = ({(q, c): {"r1" if c == "d" else "r0"} for q in ("r0", "r1") for c in "pd-"},
     "r0", {"r1"})
def accepts(aut, u, v):                    # does aut accept u v v v ... ?
    delta, start, acc = aut
    w = u + v
    nxt = lambda i: i + 1 if i + 1 < len(w) else len(u)
    def succ(x):                           # x = (automaton state, position)
        q, i = x
        return {(q2, nxt(i)) for q2 in delta.get((q, w[i]), ())}
    def reach(x):                          # everything reachable in >= 1 step
        seen, todo = set(), list(succ(x))
        while todo:
            y = todo.pop()
            if y not in seen: seen.add(y); todo += succ(y)
        return seen
    start_node = (start, 0)
    candidates = reach(start_node) | {start_node}
    return any(q in acc and (q, i) in reach((q, i)) for q, i in candidates)
for u, v in [("p-d", "-"), ("p", "-"), ("", "p-d"), ("pd", "p-"), ("-", "pd")]:
    print(f"u={u!r:6} v={v!r:6} N (violation): {accepts(N, u, v)!s:5}"
          f"  D (GF done): {accepts(D, u, v)}")

আসল আউটপুট (ব্রাউজারের Python):

u='p-d'  v='-'    N (violation): False  D (GF done): False
u='p'    v='-'    N (violation): True   D (GF done): False
u=''     v='p-d'  N (violation): False  D (GF done): True
u='pd'   v='p-'   N (violation): True   D (GF done): False
u='-'    v='pd'   N (violation): False  D (GF done): True

দ্বিতীয় word-এ অর্ডার paid হয়ে আর কখনো done হয় না: N গ্রহণ করে। চতুর্থটিতে প্রথম অর্ডার done, কিন্তু চক্রে বারবার নতুন paid আসে আর done আসে না; N চক্রের একটি paid-এ q1-এ যাওয়ার অনুমান করে। “p-d” চক্রে প্রতিটি paid-এর পরে done, তাই N বর্জন করে আর D গ্রহণ করে। দুই automaton-এর সঠিকতা দৈর্ঘ্য ৩ পর্যন্ত সব u আর ১–৩ দৈর্ঘ্যের সব v (১,৫৬০টি lasso) সংজ্ঞার সঙ্গে মিলিয়ে পরীক্ষিত, কোনো অমিল নেই।

LTL থেকে Büchi automaton

উপপাদ্য ৫.৩ (Vardi–Wolper)

প্রতিটি LTL সূত্র φ-এর জন্য একটি NBA Aφ আছে, যার state বড়জোর 2O(|φ|)টি আর L(Aφ) = {w : w ⊨ φ}.

প্রমাণের রূপরেখা: Aφ-এর প্রতিটি state হলো φ-এর উপসূত্রের একটি সামঞ্জস্যপূর্ণ সেট: এই মুহূর্তে কোনগুলো সত্য বলে প্রতিশ্রুতি দেওয়া হলো। Transition প্রতিশ্রুতি স্থানীয়ভাবে মেলায়: X ψ এখন সত্য হলে পরের state-এ ψ; φ U ψ এখন সত্য হলে হয় ψ এখনই, নয় φ এখন আর φ U ψ পরের state-এ। কিন্তু U-এর প্রতিশ্রুতি চিরকাল পিছিয়ে দেওয়া যায়; accepting শর্ত চায় প্রতিটি U-এর “পূরণ হলো” অবস্থা অসীমবার আসুক। উপসূত্র |φ|-এর রৈখিক সংখ্যক, তাই সেট 2O(|φ|)টি। পূর্ণ প্রমাণ Baier ও Katoen-এর “Principles of Model Checking” অধ্যায় ৫-এ।

৬ · Product আর nested DFS — automata দিয়ে LTL যাচাই

উপপাদ্য ৬.১ (Automata-ভিত্তিক model checking)

M ⊨ φ ⇔ L(M) ∩ L(A¬φ) = ∅, যেখানে L(M) হলো M-এর সব পথের trace-এর সেট।

  1. M ⊭ φ ⇔ M-এর কোনো পথের trace w-এ w ⊭ φ, অর্থাৎ w ⊨ ¬φ. — M ⊨ φ-এর সংজ্ঞা
  2. w ⊨ ¬φ ⇔ w ∈ L(A¬φ). — উপপাদ্য ৫.৩, ¬φ-এর জন্য
  3. তাই M ⊭ φ ⇔ L(M) আর L(A¬φ)-এর একটি সাধারণ সদস্য আছে। দুই দিক নিলে উপপাদ্যটি পাওয়া যায়। ∎

লক্ষ করুন, automaton বানানো হয় ¬φ-এর: আমরা খুঁজি একটি খারাপ আচরণ, যা M-এ সম্ভব আর A¬φ গ্রহণ করে। ছেদের উপায় পর্ব ১৬-এর product construction-এর একটি রূপ: state (s, q), আর (s, q) থেকে (s′, q′)-এ তীর ঠিক তখন, যখন (s, s′) ∈ R আর q′ ∈ δ(q, L(s)); শুরু (s0, q0), accepting যাদের q ∈ F. লেমা ৫.২ অনুযায়ী প্রশ্নটি দাঁড়ায়: product-এ পৌঁছানো যায় এমন accepting চক্র আছে কি? নিচের stepper ছবি ৭৭.১-এর M আর A-এর product বানায়।

1(s0, q0) পড়ে {paid}2(s1, q0) পড়ে { }3(s1, q1) পড়ে { }4(s2, q0) পড়ে {done}5(s2, q1) পড়ে {done}6সারকথা
এই ধাপের হিসাব
M-এ পরের
A-তে পরের
নতুন তীর
accepting?
  1. শুরু (s0, q0). s0-এর label {paid}. q0 “paid ∧ ¬done” পড়ে q0 বা q1-এ যেতে পারে, আর M-এ s0-এর পরে শুধু s1. তাই দুটি নতুন product state: (s1, q0) আর (s1, q1).
  2. (s1, q0). Label { }: q0 শুধু q0-তে থাকে। M-এ s1-এর পরে s1 বা s2. তীর (s1, q0)-এ নিজের ওপর আর নতুন (s2, q0)-এ।
  3. (s1, q1). Label-এ done নেই, তাই q1 টিকে থাকে। তীর নিজের ওপর আর (s2, q1)-এ। এটি accepting, আর তার নিজের ওপর একটি তীর আছে।
  4. (s2, q0). Label {done}: q0 থাকে, s2 নিজের ওপর। শুধু নিজের ওপর একটি তীর; চক্র আছে, কিন্তু accepting নয়।
  5. (s2, q1). q1 done পড়লে কোথাও যায় না, তাই এই product state থেকে কোনো তীর নেই: “অর্ডার আটকাবে” অনুমানটি এই শাখায় ভুল প্রমাণিত হলো। Accepting হলেও এর ওপর কোনো চক্র নেই।
  6. সারকথা. সম্ভাব্য ৩ × ২ = ৬টির মধ্যে ৫টি পৌঁছানো যায় ((s0, q1) নয়), তীর ৭টি। (s1, q1) accepting আর একটি চক্রের ওপর, তাই লেমা ৫.২ অনুযায়ী ছেদ ফাঁকা নয়। Counterexample: s0 s1 s1 s1 …, কুরিয়ার কখনো আসে না।

বড় product-এ চক্র খোঁজার একটি memory-সাশ্রয়ী উপায় nested DFS, যা Courcoubetis, Vardi, Wolper আর Yannakakis ১৯৯০-এর দিকে দেন বলে পরিচিত। বাইরের একটি DFS product ঘোরে; একটি accepting state-এর সব উত্তরসূরি দেখা শেষ হলে (postorder) সেখান থেকে একটি ভেতরের DFS খোঁজে আবার সেই state-এ ফেরা যায় কি না। ভেতরের “দেখা” সেট সব seed-এর জন্য একটিই, তাই মোট কাজ রৈখিক; সঠিকতার যুক্তি postorder-এর ওপর নির্ভর করে (প্রমাণ বাদ, Baier–Katoen অধ্যায় ৪)। Product আগে পুরো বানাতে হয় না: state প্রয়োজনমতো (on-the-fly) তৈরি হয়, আর counterexample পেলেই খোঁজ থামে।

1বাইরে: ঢোকা (s0,q0)2বাইরে: (s1,q0), (s2,q0)3শেষ: (s2,q0), (s1,q0)4বাইরে: (s1,q1), (s2,q1)5শেষ (s2,q1): ভেতরের খোঁজ6শেষ (s1,q1): ভেতরের খোঁজ7ফল
দুই খোঁজের অবস্থা
বাইরের stack
বাইরে দেখা
ভেতরের seed
ভেতরের ফল
  1. শুরু. বাইরের DFS (s0, q0)-এ ঢোকে। উত্তরসূরির ক্রম: আগে (s1, q0), তারপর (s1, q1).
  2. গভীরে. (s1, q0)-এ ঢুকে তার self-loop আগেই দেখা পায়, তারপর (s2, q0)-এ যায়; সেখানেও শুধু self-loop. বাইরে দেখা ৩টি state.
  3. Postorder. (s2, q0) আর তারপর (s1, q0)-এর কাজ শেষ। দুটিই accepting নয়, তাই ভেতরের খোঁজ শুরু হয় না। Stack-এ শুধু (s0, q0).
  4. দ্বিতীয় শাখা. (s0, q0)-এর দ্বিতীয় উত্তরসূরি (s1, q1)-এ ঢোকা; self-loop আগেই দেখা, তারপর (s2, q1)-এ, যার কোনো উত্তরসূরি নেই। মোট ৫টি state দেখা হলো।
  5. প্রথম seed. (s2, q1)-এর কাজ শেষ, আর সেটি accepting. ভেতরের DFS সেখান থেকে seed-এ ফেরার পথ খোঁজে, কিন্তু কোনো তীরই নেই। কোনো চক্র নয়।
  6. দ্বিতীয় seed. এবার (s1, q1)-এর কাজ শেষ, accepting. ভেতরের DFS-এর প্রথম তীরই (s1, q1) → (s1, q1), অর্থাৎ seed-এ ফেরা।
  7. ফল. বাইরের stack (s0, q0) (s1, q1) হলো lasso-র শুরু, ভেতরের পথ চক্রটি। M-এর counterexample: s0 s1 s1 s1 …, যা NuSMV-এর “Loop starts here” লেখা trace-এর মতো একই আকারের।

জটিলতা. Product-এর আকার |M| · 2O(|φ|), আর nested DFS এতে রৈখিক; Lichtenstein আর Pnueli ১৯৮৫ সালে এই সীমা দেন বলে পরিচিত। Sistla আর Clarke ১৯৮৫ সালে প্রমাণ করেন LTL model checking PSPACE-complete (পর্ব ৬৪, পর্ব ৬৫)। বাস্তবে φ ছোট, আসল দানব |M|: n-টি উপাদানের ছোট বর্ণনা থেকেও reachability PSPACE-কঠিন হতে পারে, যেমন অনেকগুলো DFA-র ছেদ ফাঁকা কি না (Kozen, ১৯৭৭)।

৭ · সত্যিকারের run — NuSMV দিয়ে বাজারঘরের lock bug

এবার অংশ ১-এর bug একটি সত্যিকারের model checker-এ। NuSMV একটি open source model checker (LGPL v2.1), যা Carnegie Mellon-এর SMV-এর নতুন রূপ হিসেবে ইতালির যে প্রতিষ্ঠানে শুরু হয় বলে পরিচিত, তার বর্তমান নাম Fondazione Bruno Kessler. এখানে NuSMV 2.7.1-এর অফিসিয়াল Windows binary ব্যবহার হয়েছে, প্রকাশিত SHA-256 checksum মিলিয়ে। এতে কোনো usage-reporting বা telemetry নেই; binary খুঁজে দেখা গেছে, network-এর code শুধু XML লাইব্রেরি libxml2-এর অংশ, যা এখানে ব্যবহৃত হয়নি। (একই প্রতিষ্ঠানের nuXmv-এর licence সীমাবদ্ধ, তাই সেটি নেওয়া হয়নি।)

প্রতিটি কর্মীর ধাপ: paid → try (lock-এর অপেক্ষা) → grab → check (stock দেখা) → take → delivered, অথবা check থেকে refunded. run একটি মুক্ত variable, যার সব মান খোঁজা হয়; এটিই scheduler. Bug-টি পরিকল্পিত: try-তে lock খালি দেখা আর grab-এ lock নেওয়া দুটি আলাদা ধাপ।

-- bazarghar: two workers, one last item in stock (buggy lock)
MODULE main
VAR
  run : {w1, w2};                    -- scheduler: who moves now
  pc1 : {paid, try, grab, check, take, delivered, refunded};
  pc2 : {paid, try, grab, check, take, delivered, refunded};
  lock : boolean;
  stock : -1..1;
DEFINE
  crit1 := pc1 in {check, take};
  crit2 := pc2 in {check, take};
  sell := (run = w1 & pc1 = take) | (run = w2 & pc2 = take);
ASSIGN
  init(pc1) := paid;  init(pc2) := paid;
  init(lock) := FALSE;  init(stock) := 1;
  next(pc1) := case
    run != w1 : pc1;
    pc1 = paid : try;
    pc1 = try & !lock : grab;           -- look: lock is free
    pc1 = grab : check;                 -- ...then take it (too late!)
    pc1 = check & stock > 0 : take;
    pc1 = check : refunded;
    pc1 = take : delivered;
    TRUE : pc1;
  esac;
  next(pc2) := case
    run != w2 : pc2;
    pc2 = paid : try;
    pc2 = try & !lock : grab;
    pc2 = grab : check;
    pc2 = check & stock > 0 : take;
    pc2 = check : refunded;
    pc2 = take : delivered;
    TRUE : pc2;
  esac;
  next(lock) := case
    run = w1 & pc1 = grab : TRUE;
    run = w2 & pc2 = grab : TRUE;
    run = w1 & (pc1 = take | (pc1 = check & stock <= 0)) : FALSE;
    run = w2 & (pc2 = take | (pc2 = check & stock <= 0)) : FALSE;
    TRUE : lock;
  esac;
  next(stock) := case
    sell & stock = 1 : 0;
    sell & stock = 0 : -1;               -- the same item sold twice
    TRUE : stock;
  esac;

LTLSPEC G !(crit1 & crit2)              -- mutual exclusion
LTLSPEC G (stock >= 0)                  -- never sell the last item twice

সত্যিকারের run (ডেস্কটপ, NuSMV 2.7.1, BDD-ভিত্তিক সাধারণ engine; প্রতিটি run এক সেকেন্ডের অনেক কম সময় নেয়। Copyright-এর লাইন আর trace-এর মাঝের কিছু অংশ “…” দিয়ে বাদ):

~/bazarghar-toc$ NuSMV orders_buggy.smv
*** This is NuSMV 2.7.1 (compiled on Mon Sep 29 16:07:59 2025)
…
-- specification  G !(crit1 & crit2)  is false
-- as demonstrated by the following execution sequence
Trace Description: LTL Counterexample
Trace Type: Counterexample
  -> State: 1.1 <-
    run = w1
    pc1 = paid
    pc2 = paid
    lock = FALSE
    stock = 1
    …
  -> State: 1.2 <-
    pc1 = try
  -> State: 1.3 <-
    run = w2
    pc1 = grab
  -> State: 1.4 <-
    pc2 = try
  -> State: 1.5 <-
    run = w1
    pc2 = grab
  -> State: 1.6 <-
    run = w2
    pc1 = check
    lock = TRUE
    crit1 = TRUE
  -> State: 1.7 <-
    run = w1
    pc2 = check
    crit2 = TRUE
…
-- specification  G stock >= 0  is false
…
  -> State: 2.11 <-
    run = w1
    pc2 = delivered
    stock = -1
…

দুটি দাবিই মিথ্যা, আর প্রতিটির সঙ্গে একটি পূর্ণ trace. NuSMV প্রতিটি state-এ শুধু বদলে যাওয়া variable ছাপে, আর কোনো state-এর run বলে পরের ধাপে কে চলবে। State 1.7-এ crit1 আর crit2 দুটিই TRUE: দুই কর্মী একসঙ্গে stock দেখছেন। দ্বিতীয় trace সেই একই গল্প শেষ পর্যন্ত চালায়: দুজনই stock = 1 দেখে take-এ যান, প্রথমজন stock 0 করেন, দ্বিতীয়জন −1: একটি পিস দুবার বিক্রি। নিচের stepper প্রথম trace পড়ে।

1.1শুরু1.2w1: paid → try1.3w1: try → grab1.4w2: paid → try1.5w2: try → grab1.6w1: grab → check1.7w2: grab → check
State (pc1, pc2, lock, stock)
pc1
pc2
lock
stock
crit1 ∧ crit2
  1. State 1.1. দুটি অর্ডারই paid, lock খালি, stock-এ একটি পিস। run = w1, তাই পরের ধাপ w1-এর।
  2. State 1.2. w1 try-তে: lock-এর অবস্থা দেখার জন্য প্রস্তুত।
  3. State 1.3. w1 lock খালি দেখে grab-এ গেলেন, কিন্তু lock এখনো নেননি। এটিই বসানো bug-এর ফাঁক। এবার run = w2.
  4. State 1.4. w2 try-তে।
  5. State 1.5. w2-ও lock খালি দেখেন, কারণ w1 এখনো নেননি: দুজনই grab-এ। গলির দুই রিকশাওয়ালা মাথা বাড়িয়ে দেখে ফেলেছেন।
  6. State 1.6. w1 lock নিয়ে check-এ (crit1 = TRUE). কিন্তু w2-এর সিদ্ধান্ত আগেই হয়ে গেছে; তিনি আর lock দেখবেন না।
  7. State 1.7. w2 check-এ: crit1 ∧ crit2 = TRUE, সূত্র G ¬(crit1 ∧ crit2) ভঙ্গ। এটি একটি safety violation, তাই সসীম prefix 1.1–1.7-ই প্রমাণ; NuSMV তবু LTL-এর রীতিতে trace-টি একটি loop দিয়ে অসীম lasso হিসেবে শেষ করে।

Fix আর আবার যাচাই. সমাধান হলো দেখা আর নেওয়াকে একটি অবিভাজ্য (atomic) ধাপে মেলানো, ঠিক hardware-এর test-and-set নির্দেশের মতো (Operating Systems কোর্সের পর্ব ২৩)। মডেলে grab ধাপটি মুছে try থেকে সরাসরি check-এ যাওয়া, আর একই ধাপে lock := TRUE. একই সঙ্গে দুটি নতুন দাবি যোগ হলো: একটি liveness (LTL) আর একটি CTL. পরিবর্তনের মূল অংশ (diff, প্রথম কর্মীর জন্য; দ্বিতীয়জনেরও একই):

-    pc1 = try & !lock : grab;           -- look: lock is free
-    pc1 = grab : check;                 -- ...then take it (too late!)
+    pc1 = try & !lock : check;          -- test-and-set: one step
 ...
-    run = w1 & pc1 = grab : TRUE;
+    run = w1 & pc1 = try & !lock : TRUE;
 ...
+LTLSPEC G (pc1 = paid -> F (pc1 = delivered | pc1 = refunded))
+SPEC AG (pc1 = try -> EF pc1 = check)   -- CTL: entry stays possible

সত্যিকারের run (একই NuSMV 2.7.1; trace-এর শেষ অংশ বাদ):

~/bazarghar-toc$ NuSMV orders_fixed.smv
…
-- specification AG (pc1 = try -> EF pc1 = check)  is true
-- specification  G !(crit1 & crit2)  is true
-- specification  G stock >= 0  is true
-- specification  G (pc1 = paid ->  F (pc1 = delivered | pc1 = refunded))  is false
-- as demonstrated by the following execution sequence
Trace Description: LTL Counterexample
Trace Type: Counterexample
  -> State: 1.1 <-
    run = w2
    pc1 = paid
    pc2 = paid
    lock = FALSE
    stock = 1
    …
  -> State: 1.2 <-
    pc2 = try
  -> State: 1.3 <-
    pc2 = check
    lock = TRUE
    crit2 = TRUE
  -> State: 1.4 <-
    pc2 = take
    sell = TRUE
  -- Loop starts here
  -> State: 1.5 <-
    pc2 = delivered
    lock = FALSE
    stock = 0
    …
  -> State: 1.6 <-

~/bazarghar-toc$ NuSMV -r orders_buggy.smv | grep reachable
reachable states: 80 (2^6.32193) out of 588 (2^9.19967)
~/bazarghar-toc$ NuSMV -r orders_fixed.smv | grep reachable
reachable states: 40 (2^5.32193) out of 432 (2^8.75489)

Safety-র দুটি দাবি এখন সত্য, আর এটি কিছু test পাস করার চেয়ে বড় কথা: মডেলের সব ৪০টি পৌঁছানো অবস্থা আর সব পথ খোঁজা হয়েছে। CTL দাবিটিও সত্য: w1-এর ঢোকা সবসময় সম্ভব. কিন্তু liveness মিথ্যা: শুরু থেকে run সবসময় w2, তাই w2 নিজের অর্ডার শেষ করে State 1.5 থেকে চিরকাল একই জায়গায় ঘোরেন, আর w1 একটি ধাপও পান না। এটি অংশ ৪-এর B-এর মতো একটি lasso.

একই কাজ নিজের হাতে লেখা একটি explicit-state checker দিয়েও করা যায়, আর এতে model checking-এর ভেতরটা দেখা যায়। নিচের code কর্মীর একটি ধাপকে একটি function হিসেবে লেখে, শুরু থেকে BFS চালায়, প্রতিটি নতুন অবস্থার “কোথা থেকে, কার ধাপে” মনে রাখে, আর খারাপ অবস্থা পেলে পেছনে হেঁটে সবচেয়ে ছোট counterexample ছাপে। এর পরের code (অংশ ৮) এই function-গুলোই ব্যবহার করবে, তাই আগে এটি চালান।

from collections import deque
START = ("paid", "paid", False, 1)        # (pc of w1, pc of w2, lock, stock)
def step(s, i, atomic):                   # worker i (0 or 1) makes one move
    pc, lock, stock = list(s[:2]), s[2], s[3]
    p = pc[i]
    if p == "paid": pc[i] = "try"
    elif p == "try" and not lock:         # lock looks free
        if atomic: pc[i], lock = "check", True     # test-and-set, one step
        else: pc[i] = "grab"                       # bug: take it next step
    elif p == "grab": pc[i], lock = "check", True
    elif p == "check" and stock > 0: pc[i] = "take"
    elif p == "check": pc[i], lock = "refunded", False
    elif p == "take": pc[i], lock, stock = "delivered", False, stock - 1
    return (pc[0], pc[1], lock, stock)    # otherwise: nothing changes
def bad(s):
    both = s[0] in ("check", "take") and s[1] in ("check", "take")
    return both or s[3] < 0
def check(atomic):
    parent, q, hit = {START: None}, deque([START]), None
    while q:                              # breadth-first search
        s = q.popleft()
        if bad(s) and hit is None: hit = s
        for i in (0, 1):
            t = step(s, i, atomic)
            if t not in parent: parent[t] = (s, i); q.append(t)
    print(f"atomic={atomic}: {len(parent)} reachable states,",
          "safe" if hit is None else "VIOLATION")
    trace = []
    while hit is not None and parent[hit]:
        prev, i = parent[hit]; trace.append(f"w{i+1}: {prev[i]}->{hit[i]}")
        hit = prev
    for k, line in enumerate(reversed(trace), 1): print(f"  {k}. {line}")
check(atomic=False)
check(atomic=True)

আসল আউটপুট (ব্রাউজারের Python):

atomic=False: 40 reachable states, VIOLATION
  1. w1: paid->try
  2. w1: try->grab
  3. w2: paid->try
  4. w2: try->grab
  5. w1: grab->check
  6. w2: grab->check
atomic=True: 20 reachable states, safe

নিজের checker NuSMV-এর সঙ্গে মেলে: ৪০ আর ২০টি অবস্থা; NuSMV দ্বিগুণ গোনে, কারণ সেখানে run-ও একটি দুই-মানের variable. Counterexample-টিও একই ছয় ধাপের, আর BFS স্তরে স্তরে খোঁজে বলে এর চেয়ে ছোট কোনোটি নেই। এটি পর্ব ২৪-এর মতো safety-র reachability; liveness-এর জন্য চক্র লাগবে।

একই bug, SAT দিয়ে. NuSMV-এর -bmc option একটি ভিন্ন engine চালায়: bounded model checking. প্রতিটি k = 0, 1, 2, …-এর জন্য “k ধাপে একটি খারাপ পথ আছে” দাবিটি একটি Boolean সূত্রে লেখা হয় আর একটি SAT solver (এখানে NuSMV-এর সঙ্গে আসা MiniSat) সেটি সমাধান করে। এটি পর্ব ৬০-এর Cook–Levin tableau-র ধারণার সরাসরি প্রয়োগ: সময়ের প্রতিটি ধাপের জন্য এক সারি variable. SAT solver বাস্তবে কীভাবে এত বড় সূত্র সামলায়, তা পর্ব ৭৩-এ আছে; ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৭ software যাচাইয়ে SAT আর SMT-এর ব্যবহার দেখায়।

সত্যিকারের run (NuSMV 2.7.1, SAT engine, k ≤ 10):

~/bazarghar-toc$ NuSMV -bmc -bmc_length 10 orders_buggy.smv
…
-- no counterexample found with bound 0
-- no counterexample found with bound 1
…
-- no counterexample found with bound 5
-- specification  G !(crit1 & crit2)    is false
…
-- no counterexample found with bound 9
-- specification  G stock >= 0    is false

Mutual exclusion-এর ভঙ্গ k = 6-এ প্রথম পাওয়া যায়, ঠিক BFS-এর ছয় ধাপ; দ্বিগুণ বিক্রি k = 10-এ (দুজনের পাঁচটি করে ধাপ)। Fix-করা মডেলে BMC বলে “bound 10 পর্যন্ত counterexample নেই”, যা নিজে প্রমাণ নয়: ১১তম ধাপে bug থাকতে পারত। এখানে নিশ্চয়তা আসে অন্য তথ্য থেকে: NuSMV-এর হিসাবে fix-করা মডেলের diameter (শুরু থেকে যেকোনো পৌঁছানো অবস্থার সবচেয়ে ছোট পথের সর্বোচ্চ দৈর্ঘ্য) ৮. সাধারণভাবে diameter জানা কঠিন, তাই BMC মূলত bug খোঁজার যন্ত্র।

৮ · Liveness আর fairness — “কেউ চিরকাল অপেক্ষায় থাকবেন না”

অংশ ৭-এর liveness counterexample একটি ন্যায্য প্রশ্ন তোলে: এমন scheduler কি বাস্তব, যে একজন কর্মীকে কখনো সুযোগ দেয় না? বেশিরভাগ বাস্তব scheduler-এর কাছে আমরা অন্তত এটুকু আশা করি যে প্রতিটি কাজ একসময় চলবে। এই অনুমানকে বলে fairness, আর liveness দাবি প্রায় সবসময় কোনো না কোনো fairness অনুমানের অধীনে সত্য।

সংজ্ঞা ৮.১ (Fair পথ)

Fairness শর্তের একটি সেট {c1, …, ck} দেওয়া থাকলে একটি পথ fair, যদি প্রতিটি ci পথে অসীমবার সত্য হয়; NuSMV-এ এর নাম JUSTICE. M ⊨fair φ ⇔ M-এর প্রতিটি fair পথ φ মানে। LTL-এ এটি একটি সাধারণ সূত্রেই লেখা যায়: M ⊨ (G F c1 ∧ … ∧ G F ck) → φ.

বাজারঘরে শর্ত দুটি: G F (run = w1) আর G F (run = w2), অর্থাৎ প্রতিটি কর্মী অসীমবার এক ধাপ পান। এর চেয়ে শক্ত একটি রূপ আছে, strong fairness (NuSMV-এ COMPASSION): “যে কাজ অসীমবার সম্ভব, তা অসীমবার ঘটে”। Fairness শর্ত মডেলের অংশ নয়, একটি অনুমান; তাই সেটি স্পষ্ট লিখে রাখা দরকার, কারণ অবাস্তব শক্ত অনুমান আসল bug লুকিয়ে ফেলতে পারে।

সত্যিকারের run: fix-করা মডেলের শেষে দুটি লাইন যোগ, JUSTICE run = w1 আর JUSTICE run = w2, তারপর NuSMV 2.7.1:

~/bazarghar-toc$ NuSMV orders_fair.smv
…
-- specification AG (pc1 = try -> EF pc1 = check)  is true
-- specification  G !(crit1 & crit2)  is true
-- specification  G stock >= 0  is true
-- specification  G (pc1 = paid ->  F (pc1 = delivered | pc1 = refunded))  is true

এবার চারটি দাবিই সত্য। হাতের যুক্তি: প্রতিটি কর্মী অসীমবার ধাপ পান; যিনি lock নেন, তিনি সসীম ধাপে সেটি ছাড়েন; প্রত্যেকে একটিই অর্ডার নেন, তাই lock একসময় চিরকাল খালি, আর w1 ঢোকেন। শেষ পিস একজন পান, অন্যজন stock = 0 দেখে refunded.

নিজের checker-এ fairness যোগ করতে একটি পরিচিত কৌশল লাগে। Nested DFS একটি accepting সেট চেনে, কিন্তু এখন তিনটি শর্ত একসঙ্গে অসীমবার চাই: A¬φ-এর q1, w1-এর ধাপ, আর w2-এর ধাপ। তাই product state-এ একটি counter k যোগ হয়: k = 0 অপেক্ষা করে q1-এর জন্য, তারপর k = 1 অপেক্ষা করে w1-এর একটি ধাপের জন্য, k = 2 w2-এর জন্য, তারপর আবার 0. Accepting হলো q1 আর k = 0: এমন state-এ ফেরা চক্র অবশ্যই তিনটি শর্তই পূরণ করেছে। এই রূপান্তরের নাম degeneralization.

# Buchi automaton for NOT G(paid -> F done), done = delivered or refunded
def nba(q, s):
    done = s[0] in ("delivered", "refunded")
    if q == "q1": return () if done else ("q1",)
    return ("q0", "q1") if s[0] == "paid" else ("q0",)
def succ(v, fair):                     # product state v = (system, q, k)
    s, q, k = v                        # k: 0 wait for q1, 1 wait w1, 2 wait w2
    for i in (0, 1):
        k2 = 0
        if fair: k2 = (1 if k == 0 and q == "q1" else 2 if k == 1 and i == 0
                       else 0 if k == 2 and i == 1 else k)
        for q2 in nba(q, s): yield (step(s, i, True), q2, k2)
def accepting(v): return v[1] == "q1" and v[2] == 0
def nested_dfs(fair):
    outer, inner = set(), set()
    def dfs2(v, seed):                 # inner search: back to the seed?
        for w in succ(v, fair):
            if w == seed: return [w]
            if w not in inner:
                inner.add(w)
                if r := dfs2(w, seed): return [w] + r
    def dfs1(v):                       # outer search; seeds in postorder
        outer.add(v)
        for w in succ(v, fair):
            if w not in outer and (r := dfs1(w)): return r
        if accepting(v) and (c := dfs2(v, v)): return [v] + c
    cyc = dfs1((START, "q0", 0))
    print(f"fair={fair}: {len(outer)} product states visited,",
          "accepting cycle:" if cyc else "no accepting cycle, property holds")
    if cyc: print("  ", " -> ".join(f"{v[0][0]}/{v[0][1]}" for v in cyc))
nested_dfs(fair=False)
nested_dfs(fair=True)

আসল আউটপুট (ব্রাউজারের Python; আগের ব্লকের step আর START ব্যবহার করে):

fair=False: 22 product states visited, accepting cycle:
   take/try -> take/try
fair=True: 55 product states visited, no accepting cycle, property holds

Fairness ছাড়া nested DFS একটি accepting চক্র পায়: w1 take-এ (lock তাঁর হাতে), w2 try-তে, আর চক্রটি শুধু w2-এর বৃথা অপেক্ষা; w1 কখনো সুযোগ পান না। NuSMV-এর counterexample আলাদা (w1 শুরু থেকেই আটকে), কিন্তু রোগ একই। Fairness দিলে ৫৫টি product state ঘুরে কোনো fair accepting চক্র নেই, NuSMV-এর মতোই। সতর্কতা: এখানে প্রত্যেকে একটিই অর্ডার নেন। কর্মীরা বারবার অর্ডার নিলে এই scheduler-fairness থাকলেও সাধারণ test-and-set lock-এ একজন চিরকাল বঞ্চিত হতে পারেন, যদি তাঁর প্রতিটি সুযোগ আসে ঠিক যখন lock অন্যের হাতে; এর নাম starvation, আর Peterson-এর algorithm বা ticket lock তা ঠেকায় (OS কোর্সের পর্ব ২২)।

৯ · State explosion আর তার প্রতিকার

দুই কর্মীতে ২০টি অবস্থা। আরও কর্মী যোগ করলে কী হয়? নিচের সত্যিকারের run একই fix-করা মডেল n জন কর্মী আর একটি পিস নিয়ে BFS চালায় (ডেস্কটপ, Python 3.14.4, নিজের লেখা ২০ লাইনের script):

~/bazarghar-toc$ python explode.py
workers=1: reachable states       5  (0.00 s)
workers=2: reachable states      20  (0.00 s)
workers=3: reachable states      77  (0.00 s)
workers=4: reachable states     296  (0.00 s)
workers=5: reachable states    1137  (0.00 s)
workers=6: reachable states    4336  (0.01 s)
workers=7: reachable states   16333  (0.04 s)
workers=8: reachable states   60624  (0.19 s)

প্রতিটি নতুন কর্মী অবস্থার সংখ্যা মোটামুটি চার গুণ করে: ৮ জনে ৬০,৬২৪টি। একই হারে ২০ জনে সংখ্যাটি দশ হাজার কোটি ছাড়াবে। সিস্টেমের বর্ণনা রৈখিক হারে বাড়ে, অবস্থা সূচকীয় হারে: এটিই state explosion.

এই বিস্ফোরণের বিরুদ্ধে মূল অস্ত্রগুলো:

কৌশলমূল ধারণাকোথায় দেখবেন
Symbolic model checkingঅবস্থাগুলো একটি একটি নয়, সেট হিসেবে একটি BDD-তে রাখা; একসঙ্গে পুরো সেটের পরের ধাপ হিসাবNuSMV-এর সাধারণ engine; Randal Bryant ১৯৮৬ (BDD), Burch, Clarke, McMillan ও অন্যরা ১৯৯০ সালের দিকে
Bounded model checkingk ধাপের পথ একটি SAT সূত্রে; bug খোঁজায় খুব দ্রুতNuSMV-এর -bmc; Biere, Cimatti, Clarke ও Zhu ১৯৯৯ সালে প্রস্তাব করেন বলে পরিচিত
Partial order reductionস্বাধীন ধাপের সব ক্রম না খুঁজে একটি প্রতিনিধি ক্রমExplicit-state checker যেমন SPIN; Godefroid, Peled, Valmari ১৯৯০-এর দশকের শুরুতে
Symmetry reductionএকই রকম কর্মীদের নাম অদলবদল করা অবস্থাকে একটি ধরাআমাদের মডেলে (A, B) আর (B, A) একই গল্প
Abstraction ও refinementবিস্তারিত বাদ দিয়ে ছোট মডেল; ভুল counterexample এলে মডেল একটু সূক্ষ্ম করাClarke ও সহকর্মীদের ২০০০ সালের কাজ; software model checker-এ প্রচলিত

একটি গভীরতর সীমাও আছে। মডেল অসীম হলে (সীমাহীন counter, queue বা ইচ্ছেমতো program) সাধারণ প্রশ্নটি undecidable, পর্ব ৫৫-এর কারণেই। তাই software model checker হয় একটি সসীম abstraction যাচাই করে, নয় bounded থাকে, নয় কখনো “জানি না” বলে। আর যাচাই হয় মডেলের, code-এর নয়।

আরও গভীরে: Symbolic আর SAT-ভিত্তিক পদ্ধতির পরে IC3 বা PDR নামের একটি কৌশল (Aaron Bradley, ২০১১ সালের দিকে) bounded নয় এমন প্রমাণ দিতে পারে, ধাপে ধাপে একটি inductive invariant গড়ে; আজ hardware যাচাইয়ে এটি একটি প্রধান engine বলে জানা যায়। Probabilistic model checking (যেমন PRISM tool) “৯৯.৯% সম্ভাবনায় ডেলিভারি” ধরনের দাবি যাচাই করে, আর timed automata (Alur ও Dill, ১৯৯০-এর দশক) “৩ সেকেন্ডের মধ্যে উত্তর” ধরনের সময়-সীমা। Distributed protocol-এর নকশা যাচাইয়ে Leslie Lamport-এর TLA+ আর তার TLC model checker শিল্পে ব্যবহৃত হয় বলে জানা যায়; System Design কোর্সের পর্ব ৪২-এর Raft-এর মতো protocol এমন যাচাইয়ের সাধারণ লক্ষ্য।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • Safety আর liveness-এর পার্থক্য? Safety ভাঙার প্রমাণ একটি সসীম bad prefix (reachability দিয়ে যাচাই); liveness ভাঙার প্রমাণ একটি অসীম পথ, সসীম মডেলে একটি lasso (চক্র খুঁজে যাচাই)।
  • Büchi automaton কখন একটি word গ্রহণ করে? যখন কোনো run-এ accepting state অসীমবার আসে; L(A) ≠ ∅ ⇔ একটি পৌঁছানো যায় এমন accepting state একটি চক্রের ওপর।
  • LTL model checking-এর মূল ধাপ? ¬φ-এর NBA বানানো, M-এর সঙ্গে product, আর product-এ accepting চক্র খোঁজা (nested DFS বা SCC); চক্র থাকলে সেটিই counterexample.
  • LTL আর CTL-এর একটি করে সূত্র দিন যা অন্যটিতে লেখা যায় না। LTL-এ F G p; CTL-এ AG EF p.

১০ · AI-এর যুগে model checking

AI assistant আজ concurrent code লেখে আর বলে, এই code “thread-safe”; এমন দাবি test দিয়ে যাচাই করা কঠিন, model checking দিয়ে সহজ। Temporal logic নিয়ে AI-এর উত্তরে কিছু ভুল প্রায়ই দেখা যায়।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“এই lock-এ race নেই” বিনা প্রমাণে, বা “check তারপর set” ধাঁচের lockদুই কর্মীর একটি ছোট মডেল বানিয়ে BFS বা NuSMV চালান; counterexample এলে দাবিটি ভুল
Safety আর liveness গুলিয়ে ফেলা, বা “৩ দিনের মধ্যে” দাবিকে liveness বলাপ্রশ্ন করুন: ভাঙার প্রমাণ কি একটি সসীম prefix? হ্যাঁ হলে safety
LTL সূত্রে ভুল operator: G(paid → F done)-এর বদলে G(paid → X done) বা F(paid → done)অংশ ৪-এর evaluator-এ কয়েকটি lasso trace-এ দুটি সূত্র মিলিয়ে দেখুন
Büchi automaton-কে NFA-র নিয়মে পড়া (“শেষে accepting”), বা φ-এর automaton-এর সঙ্গে product বানানোসংজ্ঞা ৫.১ আর উপপাদ্য ৬.১ মিলিয়ে নিন: অসীমবার, আর ¬φ-এর automaton
Fairness ছাড়া liveness “প্রমাণ”, বা fairness অনুমান লুকিয়ে রাখাকোন scheduler অনুমান করা হলো, স্পষ্ট লিখতে বলুন; fairness সরিয়ে আবার যাচাই করুন
Complexity বা ইতিহাসে ভুল: “LTL model checking polynomial”, বানানো সাল বা লেখকসময় |M|-এ রৈখিক কিন্তু |φ|-এ সূচকীয়, সমস্যা PSPACE-complete; Baier–Katoen বা Clarke–Grumberg–Peled-এর বইয়ে মিলিয়ে নিন

AI-কে কাজে লাগানোর ভালো উপায়: তাকে দিয়ে মডেল আর সূত্রের খসড়া লেখানো, তারপর নিজে tool-এ চালিয়ে যাচাই।

আমি গণনার তত্ত্ব শিখছি, এখন model checking নিয়ে কাজ করছি। ১. দুটি কর্মী আর একটি shared lock-এর একটি ছোট NuSMV মডেল লেখো, যেখানে প্রতিটি কর্মী lock নেয়, একটি কাজ করে আর lock ছাড়ে। ইচ্ছে করে একটি bug রাখো, যাতে mutual exclusion ভাঙে, আর bug-টি কোন লাইনে তা আলাদা করে বলো। ২. Mutual exclusion-এর জন্য একটি LTL safety সূত্র আর "প্রতিটি কর্মী একসময় কাজ শেষ করে" এর জন্য একটি liveness সূত্র লেখো। কোনটি safety, কোনটি liveness, সংজ্ঞা দিয়ে ব্যাখ্যা করো। ৩. Liveness সত্য হতে কোন fairness অনুমান লাগে, তা JUSTICE লাইন হিসেবে লেখো, আর কেন লাগে এক অনুচ্ছেদে বলো। ৪. কোনো সাল, লেখক বা complexity ফল নিয়ে নিশ্চিত না হলে স্পষ্ট বলো; বানানো রেফারেন্স দিও না।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Concurrency bug কেন test-কে এত সহজে ফাঁকি দেয়, আর model checking এখানে ঠিক কী বাড়তি দেয়? Model checking কি test-এর বিকল্প?

একটি sequential program-এ একই input সবসময় একই ফল দেয়, তাই একটি test একটি নির্দিষ্ট আচরণকে নিশ্চিতভাবে ধরে। Concurrent program-এ একই input-এ ফল নির্ভর করে interleaving-এর ওপর, যা ঠিক করে scheduler, hardware-এর গতি, cache, এমনকি অন্য program-এর চাপ। দুই কর্মীর প্রত্যেকে মাত্র ১০টি ধাপ করলেও interleaving এক লাখ আশি হাজারের বেশি; বাস্তব code-এ ধাপ হাজার হাজার। একটি test একবারে একটি interleaving দেখে, আর কোনটি দেখবে তা নিয়ন্ত্রণও করে না।

ইতিহাসে এর দাম চড়া। ১৯৮০-এর দশকের মাঝামাঝি Therac-25 নামের একটি বিকিরণ-চিকিৎসা যন্ত্রে কয়েকজন রোগী মাত্রাতিরিক্ত বিকিরণ পান, আর Nancy Leveson ও Clark Turner-এর ১৯৯৩ সালের বিশ্লেষণে অন্যতম কারণ হিসেবে race condition চিহ্নিত হয় বলে পরিচিত: অপারেটর খুব দ্রুত নির্দিষ্ট কিছু কী চাপলে একটি নির্দিষ্ট ক্রম তৈরি হতো।

Model checking তিনটি জিনিস দেয়। প্রথম, পূর্ণতা: মডেলের সব interleaving খোঁজা হয়, তাই “সত্য” উত্তর মানে মডেলের কোনো আচরণই দাবি ভাঙে না। দ্বিতীয়, counterexample: “মিথ্যা” উত্তরের সঙ্গে একটি নির্দিষ্ট ক্রম আসে, যা দিয়ে bug আবার ঘটানো যায়; অংশ ৭-এর ছয় ধাপের trace এর উদাহরণ। তৃতীয়, অসীম আচরণ নিয়ে দাবি: “একসময় ঘটবে” ধরনের liveness কোনো test-ই প্রমাণ করতে পারে না।

তবে এটি test-এর বিকল্প নয়। Model checking যাচাই করে একটি হাতে লেখা, সরলীকৃত মডেল, আর বড় system-এ state explosion পুরো code-কে মডেল করা অসম্ভব করে। তাই protocol বা lock-এর মতো ছোট কিন্তু জটিল অংশ model checking-এ যায়, বাকিটা test, property-based test (Software Testing কোর্সের পর্ব ৫৮) আর code review-তে।

মূল উপলব্ধি: Test একটি interleaving-এর নমুনা দেখে, model checking একটি সসীম মডেলের সব interleaving আর অসীম আচরণ দেখে; তাই ছোট, জটিল concurrent অংশে model checking অমূল্য, কিন্তু মডেল আর code-এর ফাঁক থাকায় এটি test-এর সঙ্গী, বিকল্প নয়।

প্র ০২Program থামলেই তো কাজ শেষ। তাহলে model checking অসীম word আর Büchi automaton নিয়ে এত ব্যস্ত কেন? সসীম trace-এর DFA কি যথেষ্ট নয়?

কারণ যে সিস্টেমগুলো সবচেয়ে বেশি যাচাই দরকার, সেগুলো থামার জন্য তৈরিই নয়। Operating system, ব্যাংকের server বা network protocol-এর কাজ চিরকাল চলা আর পরিবেশে সাড়া দেওয়া। Amir Pnueli ১৯৭৭ সালে এদের “reactive” system হিসেবে দেখার পক্ষে যুক্তি দেন: এমন program-এর সঠিকতা “শেষে কী output” নয়, বরং “চলতে চলতে কী সবসময় সত্য থাকে আর কী একসময় ঘটে”। সেই প্রশ্ন বলার স্বাভাবিক ভাষা temporal logic, আর তার স্বাভাবিক বস্তু অসীম আচরণ।

Safety-র জন্য সসীম trace সত্যিই প্রায় যথেষ্ট: প্রতিটি ভঙ্গের একটি সসীম bad prefix আছে, আর bad prefix-গুলো একটি সসীম automaton দিয়ে চেনা যায় এমন ক্ষেত্রে সমস্যাটি reachability. কিন্তু liveness-এ এটি ভেঙে পড়ে। “Paid অর্ডার একসময় শেষ হবে” কোনো সসীম trace-এ মিথ্যা প্রমাণ হয় না, কারণ আরেকটু অপেক্ষা করলেই হয়তো শেষ হতো। মিথ্যা প্রমাণ হয় শুধু এমন অসীম আচরণে, যেখানে সেটি কখনো ঘটে না। তাই অসীম word-এর automaton লাগে, আর তার গ্রহণের শর্ত হতে হয় “অসীমবার”, কারণ “শেষে” বলে কিছু নেই।

Büchi-র ১৯৬২ সালের আসল লক্ষ্য ছিল আরও তাত্ত্বিক: পূর্ণসংখ্যার ক্রমের ওপর একটি monadic second-order যুক্তি (S1S) decidable কি না। তিনি দেখান প্রতিটি সূত্রকে এমন একটি automaton-এ বদলানো যায়, আর তাই প্রশ্নটি automaton-এর emptiness-এ নামে। প্রায় দুই দশক পরে Vardi আর Wolper একই কৌশল LTL-এ প্রয়োগ করেন, আর একটি বিশুদ্ধ গাণিতিক ফল হয়ে ওঠে শিল্পের যাচাই-যন্ত্রের ভিত্তি। এর মধ্যে একটি সুন্দর সরলতা আছে: সসীম মডেলে প্রতিটি অসীম counterexample একটি lasso, তাই অসীমকে সসীম তথ্যে (u আর v) ধরা যায়; লেমা ৫.২ এটিই বলে।

মূল উপলব্ধি: চিরকাল চলা সিস্টেমের সঠিকতা অসীম আচরণের ধর্ম, আর liveness-এর ভঙ্গ শুধু অসীম পথে দেখা যায়; Büchi-র “অসীমবার” শর্ত এই অসীমকে চক্র খোঁজার একটি সসীম সমস্যায় নামিয়ে আনে।

প্র ০৩Explicit-state (একটি একটি অবস্থা) আর symbolic (BDD) model checking-এর মধ্যে আপস কী? SAT-ভিত্তিক পদ্ধতি কেন ১৯৯৯-এর পরে এত জনপ্রিয় হলো?

Explicit-state checker, যেমন অংশ ৭-৮-এর নিজের লেখা code বা SPIN, প্রতিটি অবস্থা আলাদা করে তৈরি করে আর একটি hash table-এ রাখে। সুবিধা: সরল, on-the-fly, আর software-ধাঁচের মডেলে partial order reduction ভালো কাজ করে। অসুবিধা: প্রতিটি পৌঁছানো অবস্থার জন্য memory লাগে।

Symbolic পদ্ধতি অবস্থাকে bit-এর vector হিসেবে দেখে, আর অবস্থার একটি সেটকে একটি Boolean function হিসেবে রাখে। Randal Bryant ১৯৮৬ সালে দেখান, একটি নির্দিষ্ট variable-ক্রমে reduced ordered binary decision diagram (BDD) একটি Boolean function-এর অনন্য আর প্রায়ই খুব ছোট রূপ, আর তার ওপর ∧, ∨, ∃ দ্রুত করা যায়। ১৯৯০ সালের দিকে Burch, Clarke, McMillan, Dill আর Hwang-এর “1020 states and beyond” ধাঁচের কাজ দেখায়, নিয়মিত কাঠামোর hardware-এ এভাবে কল্পনাতীত সংখ্যক অবস্থা যাচাই করা যায়। দুর্বলতা: BDD-র আকার variable-এর ক্রমের ওপর ভয়ানকভাবে নির্ভর করে, আর কিছু function-এর (Bryant নিজেই দেখান, যেমন পূর্ণসংখ্যার গুণফলের মাঝের bit) প্রতিটি ক্রমেই সূচকীয় আকার।

১৯৯০-এর দশকের শেষে SAT solver-গুলো নাটকীয়ভাবে দ্রুত হয় (conflict-driven clause learning; Discrete Mathematics কোর্সের পর্ব ৭৭)। Armin Biere আর সহকর্মীরা ১৯৯৯ সালে bounded model checking প্রস্তাব করেন: “k ধাপের মধ্যে খারাপ পথ” একটি SAT সূত্র, যার আকার k আর মডেলের বর্ণনায় রৈখিক। এতে BDD-র variable-ক্রমের সমস্যা নেই, আর অনেক বাস্তব bug অল্প ধাপেই ধরা পড়ে, যেমন আমাদের ছয় ধাপের trace. দাম: সাধারণভাবে এটি প্রমাণ দেয় না, শুধু k পর্যন্ত। পরে k-induction, interpolation আর IC3-এর মতো কৌশল SAT দিয়েই পূর্ণ প্রমাণের পথ খোলে।

Reachability-ই succinct মডেলে PSPACE-কঠিন হতে পারে, তাই প্রতিটি পদ্ধতির কিছু ভয়ানক উদাহরণ থাকবেই; শিল্পের tool তাই কয়েকটি engine পালা করে চালায়, যেমন NuSMV-এর BDD আর SAT.

মূল উপলব্ধি: Explicit পদ্ধতি অবস্থা গোনে, symbolic পদ্ধতি অবস্থার সেটকে সূত্রে রাখে, SAT-ভিত্তিক পদ্ধতি পথকে সূত্রে রাখে; প্রত্যেকে আলাদা ধরনের মডেলে জেতে, আর কোনোটিই complexity-র দেয়াল পেরোয় না।

প্র ০৪Fairness অনুমান কতটা যুক্তিসংগত? Weak আর strong fairness-এর পার্থক্য কোথায়, আর ভুল fairness কীভাবে bug লুকাতে পারে?

Fairness হলো পরিবেশ সম্পর্কে একটি প্রতিশ্রুতি, সিস্টেম সম্পর্কে নয়। অংশ ৮-এ “প্রতিটি কর্মী অসীমবার এক ধাপ পান” ধরে নেওয়া হয়েছে; একটি যুক্তিসংগত operating system scheduler সাধারণত এটুকু নিশ্চিত করে, তাই অনুমানটি বাস্তবসম্মত। এটি unconditional বা weak ধাঁচের: যে কাজ চলতে পারে, সে অসীমবার চলে। Weak fairness-এর প্রচলিত রূপ আরেকটু সূক্ষ্ম: “যে কাজ একসময় থেকে চিরকাল সম্ভব, তা অসীমবার ঘটে”। Strong fairness চায় আরও বেশি: “যে কাজ অসীমবার সম্ভব (মাঝে মাঝে অসম্ভবও), তা অসীমবার ঘটে”।

পার্থক্যটি lock-এর ক্ষেত্রেই ধরা পড়ে। ধরুন কর্মীরা বারবার অর্ডার নেন। w2-এর কাছে lock নেওয়ার কাজটি কখনো সম্ভব (lock খালি), কখনো নয় (w1-এর হাতে)। Weak fairness বলে, “চিরকাল সম্ভব” না হলে কোনো প্রতিশ্রুতি নেই, তাই scheduler w2-কে ঠিক সেই মুহূর্তগুলোতে চালাতে পারে যখন lock নেওয়া, আর w2 চিরকাল বঞ্চিত থাকেন: starvation. Strong fairness বলে, lock অসীমবার খালি হলে w2 অসীমবার নেবেন, তাই starvation নেই। কিন্তু কোনো সত্যিকারের scheduler strong fairness দেয় বলে ধরে নেওয়া ঝুঁকিপূর্ণ; এজন্যই Gary Peterson-এর ১৯৮১ সালের algorithm বা ticket lock-এর মতো নকশা, যা নিজেই পালা ঠিক রাখে, শুধু weak fairness-এর ওপর starvation-মুক্তি দেয় (Operating Systems কোর্সের পর্ব ২২)।

ভুল fairness দুইভাবে বিপদ ঘটায়। প্রথম, অবাস্তব শক্ত অনুমান: যাচাই সফল হয়, কিন্তু আসল scheduler-এ bug থেকে যায়। দ্বিতীয়, অসংগত অনুমান: fairness শর্ত এমন যে মডেলের কোনো পথই fair নয়; তখন “প্রতিটি fair পথ φ মানে” ফাঁকা সত্য, যেকোনো φ “প্রমাণিত”! ভালো tool এমন ক্ষেত্রে সতর্ক করে, আর নিজেও যাচাই করা যায়: fairness সহ একটি ইচ্ছে করে মিথ্যা সূত্র, যেমন G FALSE, যাচাই করুন; fair পথ থাকলে সেটি মিথ্যা আসবেই।

তাই প্রতিটি liveness ফলের সঙ্গে fairness অনুমান লিখে রাখুন, আর fairness সরিয়ে counterexample দেখুন (অংশ ৭-এর মতো)।

মূল উপলব্ধি: Fairness পরিবেশের ওপর একটি অনুমান; weak fairness সাধারণত বাস্তবসম্মত, strong fairness প্রায়ই নয়, আর অসংগত বা অবাস্তব অনুমান একটি সফল যাচাইকে অর্থহীন করে দিতে পারে।

প্র ০৫Model checking ২০০৭ সালের Turing Award পেয়েছে, অথচ undecidability বলে নিখুঁত program-যাচাইকারী অসম্ভব। দুটি কথা একসঙ্গে সত্য কীভাবে?

দুটি কথা আলাদা প্রশ্ন নিয়ে। Rice-এর theorem (পর্ব ৫৩) বলে, Turing-complete ভাষার সব program-এর আচরণ নিয়ে non-trivial প্রশ্নের এমন কোনো algorithm নেই যা সবসময় থামে আর সবসময় ঠিক বলে। Model checking এই দাবি করে না। এটি একটি সসীম মডেল নিয়ে কাজ করে, যেখানে সব আচরণ একটি সসীম graph-এ ধরা যায়, আর সেখানে প্রশ্নটি decidable: লেমা ৫.২ আর উপপাদ্য ৬.১ মিলে একটি পূর্ণ algorithm দেয়। Clarke, Emerson আর Sifakis-এর মূল অন্তর্দৃষ্টি ছিল যে অনেক গুরুত্বপূর্ণ সিস্টেম, বিশেষত hardware circuit আর communication protocol, স্বভাবতই সসীম অবস্থার, বা তাদের গুরুত্বপূর্ণ অংশ সসীম মডেলে ধরা যায়।

যেখানে সিস্টেম অসীম, সেখানে undecidability সত্যিই ফিরে আসে, আর প্রকৌশলীরা পর্ব ৫৫-এর কৌশলগুলোই নেন: সসীম abstraction (যেমন একটি integer-কে শুধু “শূন্য, ধনাত্মক, ঋণাত্মক” হিসেবে দেখা), bounded যাচাই (k ধাপ পর্যন্ত), বা “জানি না” উত্তর রাখা। Abstraction-refinement পদ্ধতি এই দুই জগতের মাঝে সেতু: একটি মোটা মডেলে counterexample এলে সেটি আসল program-এ সম্ভব কি না দেখা হয়; না হলে মডেল একটু সূক্ষ্ম করা হয়। এই loop থামবে কি না, তা সাধারণভাবে নিশ্চিত নয়, আর এটিই undecidability-র চিহ্ন।

সসীম হলেও মডেল বিশাল হতে পারে, তাই Turing Award-এর স্বীকৃতি শুধু একটি algorithm-এর জন্য নয়, বরং সেই কাজের জন্য, যা সূচকীয় সংখ্যক অবস্থার মডেলকেও বাস্তবে যাচাইযোগ্য করেছে, আর hardware ও software শিল্পে ব্যাপকভাবে ব্যবহৃত হয়েছে।

এখানে এই কোর্সের একটি বড় শিক্ষা আবার দেখা যায়: যত কম শক্তিশালী মডেল, তত বেশি প্রশ্ন decidable. DFA-র ক্ষেত্রে equivalence decidable (পর্ব ২০), Turing machine-এর ক্ষেত্রে নয়। Model checking ইচ্ছে করে সসীম মডেলে নামে, আর বিনিময়ে পায় স্বয়ংক্রিয়, পূর্ণ আর counterexample-সহ উত্তর।

মূল উপলব্ধি: Undecidability সব program নিয়ে একটি সাধারণ algorithm নিষেধ করে; model checking সসীম মডেলে নেমে decidability কিনে নেয়, আর সেই দামের, অর্থাৎ state explosion আর মডেল-code ফাঁকের, মোকাবিলাই এর সাফল্যের গল্প।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। ltl_lasso.js আর buchi_lasso.py-তে নিজের trace বসিয়ে উত্তর যাচাইও করতে পারেন।

  1. নকশা: Σ = {a, b}. “a শুধু সসীমবার আসে”, অর্থাৎ F G ¬a (একসময় থেকে চিরকাল b), এই language-এর জন্য একটি NBA নকশা করুন। তারপর ব্যাখ্যা করুন কেন কোনো deterministic Büchi automaton এটি চেনে না (রূপরেখা যথেষ্ট)।

    NBA: state q0 (শুরু) আর q1 (accepting). δ(q0, a) = {q0}, δ(q0, b) = {q0, q1}, δ(q1, b) = {q1}, δ(q1, a) = ∅. q0 অপেক্ষা করে, আর কোনো b-তে অনুমান করে “এখন থেকে আর a নেই” এবং q1-এ যায়; q1-এ a এলে run মরে। Accepting run আছে ⇔ কোনো এক মুহূর্তের পরে শুধু b ⇔ a সসীমবার। buchi_lasso.py-র accepts() দিয়ে দৈর্ঘ্য ৩ পর্যন্ত সব u আর ১–৩ দৈর্ঘ্যের সব v (মোট ২১০টি lasso) সংজ্ঞার সঙ্গে মিলিয়ে দেখা হয়েছে, কোনো অমিল নেই।

    DBA নেই, প্রমাণের রূপরেখা: ধরুন একটি DBA D এটি চেনে। bω ∈ L, তাই D-এর run কোনো সসীম bn1-এর পরে accepting state-এ আসে। bn1 a bω-ও L-এ, তাই আরও কিছু bn2-এর পরে আবার accepting. এভাবে bn1 a bn2 a bn3 a … word পাওয়া যায়; D deterministic বলে এর একমাত্র run প্রতিটি ব্লকের শেষে accepting state-এ আসে, অর্থাৎ অসীমবার, তাই D এটি গ্রহণ করে। কিন্তু এতে a অসীমবার, তাই word-টি L-এ নেই: বিরোধ। ∎ Nondeterminism এখানে অপরিহার্য।

  2. প্রমাণ ও counterexample: প্রমাণ করুন, প্রতিটি ω-word w-এ w ⊨ F G p হলে w ⊨ G F p. তারপর একটি lasso word দিন, যেখানে G F p সত্য কিন্তু F G p মিথ্যা, আর ltl_lasso.js-এর রীতিতে লিখুন।

    প্রমাণ: (১) w ⊨ F G p, তাই কোনো k আছে যেখানে সব j ≥ k-এ p ∈ aj. — F আর G-এর সংজ্ঞা (২) যেকোনো i নিন। m = max(i, k) নিলে m ≥ i আর m ≥ k, তাই p ∈ am; অর্থাৎ wi ⊨ F p. — সাক্ষী m (৩) i ইচ্ছেমতো, তাই w ⊨ G F p. ∎

    উল্টোটি মিথ্যা: w = (p, ∅)ω, অর্থাৎ p আর “কিছু না” পালা করে। p অসীমবার আসে, তাই G F p সত্য; কিন্তু প্রতিটি k-এর পরে একটি ∅ আছে, তাই F G p মিথ্যা। ltl_lasso.js-এর রীতিতে trace [[], ["p", ""]]; সেখানে ["F", ["G", "p"]] দিলে F, আর ["G", ["F", "p"]] দিলে T আসবে।

  3. আউটপুট অনুমান: buchi_lasso.py-র দুটি automaton N (violation: কোনো paid কখনো done হয় না) আর D (G F done) নিন। নিচের তিনটি lasso-তে accepts() কী ফেরত দেবে, কারণসহ বলুন: (ক) u = "pp", v = "d-"; (খ) u = "", v = "p"; (গ) u = "d", v = "-p".

    (ক) word: p p d - d - d - …. দুটি paid-এর পরেই done আসে, আর পরে নতুন paid নেই: N → False. done অসীমবার: D → True.

    (খ) word: p p p …. প্রথম paid-এর পরে done কখনো নয়; N প্রথম অক্ষরেই q1-এ গিয়ে চিরকাল থাকতে পারে: N → True. done কখনো নয়: D → False.

    (গ) word: d - p - p - p …. প্রথম done-এর পরে চক্রে paid বারবার আসে কিন্তু done আর আসে না: N → True (চক্রের একটি p-তে q1-এ অনুমান)। done একবারই: D → False. তিনটি উত্তরই code চালিয়ে মেলানো হয়েছে।

  4. সূত্র লেখা: বাজারঘরের অর্ডার মডেলে proposition paid, packed, shipped, delivered, cancelled, refunded. লিখুন: (ক) LTL-এ “refund হওয়া অর্ডার কখনো ship হয় না”; (খ) LTL-এ “cancel হওয়া প্রতিটি paid অর্ডার একসময় refunded”; (গ) CTL-এ “ship হওয়ার আগে যেকোনো মুহূর্ত থেকে cancel করা সম্ভব”। (গ) কেন LTL-এ লেখা যায় না, এক লাইনে বলুন। কোনটি safety, কোনটি liveness?

    (ক) G(refunded → G ¬shipped): safety; ভাঙলে একটি সসীম prefix (refunded তারপর shipped) যথেষ্ট। (খ) G((cancelled ∧ paid) → F refunded): liveness, সময়সীমা নেই। (গ) AG(¬shipped → EF cancelled): “সম্ভব” মানে কোনো একটি ভবিষ্যৎ-শাখা, যা path quantifier E চায়।

    LTL শুধু পথের সেট দেখে; একই পথের সেটের দুটি মডেলের একটিতে cancel-এর শাখা থাকতে পারে আর অন্যটিতে না থাকতে পারে, তাই “সম্ভব” LTL-এ লেখা যায় না। Safety আর liveness পথের সেটের ধর্ম, তাই (গ) এই দুই ছকের কোনোটিতে পড়ে না।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমএকটি সিস্টেমে LTL দাবি φ যাচাইয়ের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. সিস্টেমকে একটি Kripke structure M হিসেবে মডেল করা
  2. দাবিটির অস্বীকৃতি ¬φ নেওয়া
  3. ¬φ-এর Büchi automaton A¬φ বানানো
  4. M আর A¬φ-এর product তৈরি করা
  5. Product-এ nested DFS দিয়ে পৌঁছানো যায় এমন accepting চক্র খোঁজা
  6. চক্র পেলে সেটি counterexample lasso, না পেলে M ⊨ φ

একটি অনলাইন দোকানের order system নিয়ে নিচের কোন দাবিটি একটি safety property?

  • প্রতিটি paid অর্ডার একসময় delivered বা refunded হয়
  • একটি পিস কখনো দুজনকে বিক্রি হয় না
  • ডেলিভারি অসীমবার ঘটে
  • একসময় থেকে সিস্টেম চিরকাল স্থির থাকে

একটি nondeterministic Büchi automaton কখন একটি অসীম word w গ্রহণ করে?

  • w পড়া শেষে automaton একটি accepting state-এ থাকলে
  • w-এর কোনো run-এ একটি accepting state অন্তত একবার এলে
  • w-এর অন্তত একটি run-এ কোনো accepting state অসীমবার এলে
  • w-এর প্রতিটি run-এ accepting state অসীমবার এলে

Kripke structure M আর LTL সূত্র φ দেওয়া। Automata-ভিত্তিক পদ্ধতিতে M ⊨ φ যাচাইয়ের সঠিক শর্ত কোনটি?

  • M আর A¬φ-এর product-এ পৌঁছানো যায় এমন কোনো accepting চক্র নেই
  • M আর Aφ-এর product-এ অন্তত একটি accepting চক্র আছে
  • M আর A¬φ-এর product-এ কোনো accepting state-এ পৌঁছানো যায়
  • Aφ প্রতিটি ω-word গ্রহণ করে

দুই কর্মীর একটি সঠিক lock-এর মডেলে G(paid1 → F done1) যাচাই করা হলো fairness ছাড়া, আর model checker একটি counterexample দিল। এর সবচেয়ে সম্ভাব্য আকার কী?

  • একটি সসীম trace, যার শেষ state-এ done1 মিথ্যা
  • একটি trace, যেখানে দুজন একসঙ্গে critical section-এ
  • একটি deadlock state, যেখান থেকে কোনো transition নেই
  • একটি lasso, যার চক্রে scheduler শুধু কর্মী ২-কে চালায়

“যেকোনো অবস্থা থেকে শুরুর অবস্থায় ফেরা সম্ভব” দাবিটি সম্পর্কে কোনটি সঠিক?

  • LTL-এ G F start হিসেবে লেখা যায়
  • CTL-এ AG EF start হিসেবে লেখা যায়, LTL-এ নয়
  • CTL-এ AF AG start হিসেবে লেখা যায়
  • এটি কোনো temporal logic-এ লেখা যায় না

একটি মডেলে bounded model checking k = 20 পর্যন্ত চালিয়ে “no counterexample found with bound 20” পাওয়া গেল। নিশ্চিতভাবে কী জানা গেল?

  • মডেলে কোনো পথেই দাবিটি ভাঙে না
  • শুধু কিছু এলোমেলো পথ পরীক্ষা করা হয়েছে
  • ২০ ধাপ পর্যন্ত কোনো counterexample নেই, এর বেশি কিছু নয়
  • SAT solver-এ ভুল আছে

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Model checking: সসীম মডেল M আর সূত্র φ দিলে M ⊨ φ কি না স্বয়ংক্রিয়ভাবে বলা, আর না হলে একটি counterexample দেওয়া। মডেল হলো Kripke structure (S, S0, R, AP, L), যেখানে R total.
  2. Safety ভাঙে একটি সসীম bad prefix-এ (reachability দিয়ে যাচাই); liveness ভাঙে একটি অসীম পথে, যা সসীম মডেলে একটি lasso u vω.
  3. LTL: X, F, G, U একটি পথের ওপর; CTL: A আর E path quantifier সহ। F G p শুধু LTL-এ, AG EF p শুধু CTL-এ।
  4. Büchi automaton গ্রহণ করে যদি কোনো run-এ accepting state অসীমবার আসে; L(A) ≠ ∅ ⇔ পৌঁছানো যায় এমন accepting state একটি চক্রের ওপর। M ⊨ φ ⇔ M × A¬φ-এ এমন চক্র নেই; nested DFS এটি রৈখিক সময়ে খোঁজে, আর সমস্যাটি |φ|-এ PSPACE-complete.
  5. NuSMV বাজারঘরের “দেখা তারপর নেওয়া” lock-এর bug ছয় ধাপের trace-এ ধরে; test-and-set fix-এর পরে safety সত্য, liveness শুধু fairness-এর অধীনে। State explosion-এর বিরুদ্ধে BDD, SAT-ভিত্তিক BMC, partial order reduction আর abstraction.

পরের পর্বে: পর্ব ৭৮ — Program analysis-এর সীমা: abstract interpretation আর type system. অসীম অবস্থার program-এ সসীম abstraction কীভাবে sound উত্তর দেয়, interval আর sign domain, widening, আর type checker কোন প্রশ্ন decidable করে নেয়।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান