רשת פטרי

רשת פטרי היא גרף דו-צדדי המשמש למידול מתמטי של מערכות מבוזרות. הרשת היא גרף מכוון, שבו צמתים מייצגים מעברים (כלומר אירועים שעלולים להתרחש, מסומנים כפסים) ומקומות (כלומר תנאים, מסומנים כעיגולים). הקשתות המכוונות מתארות אילו מקומות הם תנאי קדם של אילו תנאים אוחרים (מסומנות כחצים). יש הטוענים כי רשתות פטרי הומצאו באוגוסט 1939 על ידי קארל אדם פטרי - בגיל 13 - על מנת לתאר תהליכים כימיים.
בדומה לסטנדרטים המקובלים בתעשייה כגון UML, BPMN ו-EPC, רשתות פטרי מציעות סימון גרפי לתהליכים הכוללים בחירה, איטרציות, ביצוע פעולות מקבילות, תקשורת וסנכרון. שלא כמו סטנדרטים אלו, לרשתות פטרי ישנה הגדרה מתמטית מדויקת של סמנטיקת הביצוע, עם תאוריה מתמטית מפותחת לניתוח תהליכים (גרף נגישות, ניתוח ביצועים, איתור בעיות).

יסודות רשת פטרי

רשת פטרי מורכבת ממקומות (places), מעברים (transitions), וקשתות (arcs). קשתות מחברות בין מקום למעבר או להפך, לעולם לא בין מקומות או בין מעברים. מקומות מהם יוצאת קשת למעבר נקראים מקומות הקלט של המעבר; מקומות שאליהם נכנסות קשתות ממעבר נקראים מקומות הפלט של המעבר.
מבחינה גרפית, מקומות ברשת פטרי עשויים להכיל מספר בדיד של סימנים הנקראים אסימונים (tokens). כל חלוקה של אסימונים בין המקומות מייצגת תצורה של הרשת הנקראת סימון (marking). באופן מופשט, מעבר של רשת פטרי עשוי לפעול אם הוא מאופשר (enabled), כלומר יש מספיק אסימונים בכל מקומות הקלט שלו; כאשר המעבר מופעל, הוא צורך את אסימוני הקלט הנדרשים, ויוצר אסימונים במקומות הפלט שלו. הפעלה (firing) היא אטומי, כלומר, צעד שאינו בר-הפרעה.
כל עוד אין מדיניות ביצוע מוגדרת, הביצוע של רשתות פטרי לא דטרמיניסטי: כאשר מספר מעברים מאופשרים באותו הזמן, כל אחד מהם עשוי לפעול.
מאחר שההפעלה לא דטרמיניסטית, ואסימונים עשויים להופיע בכל מקום ברשת (אפילו באותו המקום), רשתות פטרי מתאימות לתיאור התנהגות מקבילית של מערכות מבוזרות.

הגדרות חלופיות

כפי שצוין לעיל, הגדרה חלופית נפוצה היא איסור ריבוי קשתות (משקל כל קשת תמיד 1) והחלפת רב-הקבוצה של קשתות W בקבוצה פשוטה, המכונה רלציית הזרימה, .
זה לא מגביל את כוח ההבעה של רשת הפטרי היות ששתי השיטות מסוגלות לייצג זו את זו.
חלופה נפוצה נוספת, למשל, ב-Desel and Juhás (2001), מאפשרת לסמן קיבולות של מקומות. נושא זה נדון תחת הרחבות בהמשך.

תכונות מתמטיות של רשתות פטרי

אחד הגורמים לכך שרשתות פטרי הן מעניינות הוא שהן מספקות איזון בין כוח המידול ויכולת ניתוח: ניתן לקבוע באופן אוטומטי דברים רבים על מערכות מקביליות ברשתות פטרי, אף על פי שחלק מהדברים הללו "יקר" מאוד לקביעה במקרה הכללי. מספר תת-קבוצות של רשתות פטרי אשר נחקרו מסוגלות למדל קבוצות מעניינות של מערכות מקביליות, ולהקל על בעיות אלה.
ניתן למצוא סקירה על בעיות החלטה כאלו, עם תוצאות כריעות וסיבוכיות של רשתות פטרי ושל מספר תתי-קבוצות, ניתן למצוא בEsparza and Nielsen (1995).
Esparza ונילסן (1995)

נגישות

בעיית הנגישות (reachability) של רשתות פטרי היא להכריע, בהינתן רשת הפטרי N והסימון M, האם , האם ניתן להגיע לסימון M על ידי רצף כלשהו של מעברים.
ברור כי זהו עניין של הליכה בגרף הנגישות המוגדר לעיל, עד שנגיע לסימון המבוקש או עד שנדע כי כבר לא ניתן להגיע אליו, אולם זה יותר קשה ממה שזה נראה בהתחלה: גרף הנגישות הוא בדרך כלל אינסופי, וזה לא קל לקבוע מתי זה ניתן לעצור.
למעשה, בעיה זו הוצגה כבעלת קושי EXSPACE שנים לפני שהיא הוצגה בכלל ככריעה (Mayr, 1981). עדיין מתפרסמים מחקרים על כיצד ניתן לבצע זאת ביעילות.
אמנם נדמה כי נגישות היא כלי טוב למציאת מצבים שגויים, אך בדרך כלל הגרף מכיל יותר מדי מצבים מכדי לחשב. על מנת להקל על בעיה זו, משתמשים בדרך כלל בלוגיקה עיתית ליניארית (Linear Temporal Logic) בשילוב עם שיטת התמונה האנליטית כדי להוכיח שלא ניתן להגיע למצבים כאלו. LTL משתמש בטכניקת ההחלטה למחיצה כדי למצוא האם אכן ניתן להגיע למצב, על ידי מציאת קבוצת תנאים הכרחיים על מנת להגיע אליו, ואז מוכיח כי תנאים אלו אינם מספקים.

רשתות פטרי בדידות, רציפות והיברידיות

כמו גם לאירועים בדידים, יש רשתות פטרי לתהליכים רציפים ובדידים-רציפים היברידיים, שהם שימושיים בתורת הבקרה בדידה, רציפה ושליטה, וקשורה לתורת האוטומטים בדידים, רציפים והיברידיים.

רשתות זרימה

רשתות זרימה (Workflow nets או בקיצור WF-nets) הן תת-קבוצה של רשתות פטרי שמטרתן למדל את זרימת פעילויות התהליך. המעברים ברשת זרימה מוקצים עבור משימות או פעילויות, ומקומות מוקצים לתנאי קדם או תנאים אוחרים. לרשתות הזרימה ישנן דרישות מבניות ופעולה נוספות, בעיקר התוספת של מקום קלט יחיד (מקור - source) ללא מעברים קודמים, ומקום פלט (בור - sink) ללא מעברים עוקבים. בהתאם לכך, ניתן להגדיר סימוני התחלה וסוף המייצגים את סטטוס התהליך.
רשתות זרימה הן בעלות תכונת הנאותות, המציינת כי תהליך עם סימון התחלתי של k אסימונים במקור, מסוגל להגיע לסימון הסופי שלו עם k אסימונים בבור (מוגדר כרשת זרימה נאותה-K). בנוסף, כל המעברים בתהליך יכולים לפעול (כלומר עבור כל מעבר ישנו מצב נגיש בו המעבר מאופשר). רשת זרימה נאותה-גנרית (נאותה-G) מוגדרת נאותה-K עבור כל k>0.
מסלול מכוון ברשת פטרי מוגדר כרצף צמתים (מקומות ומעברים) המקושרים באמצעות קשתות מכוונות. מסלול אלמנטרי מכיל כל צומת ברצף פעם אחת בלבד.
רשת פטרי מתוחזקת היטב (well-handled) היא רשת שבה אין מסלולים אלמנטריים שונים-לגמרי בין מקום ומעבר (או מעבר ומקום), כלומר אם ישנם שני מסלולים בין זוג הצמתים, אזי המסלולים הללו חולקים צומת. רשת זרימה מתוחזקת-היטב מעגלית היא נאותה (נאותה-G).
רשת זרימה מורחבת היא רשת פטרי המורכבת מרשת זרימה עם מעבר נוסף t (מעבר משוב). מקום הבור מקושר כמקום הקלט של מעבר t והמקור כמקום הפלט שלו. הפעלה של מעבר זה גורמת לאיטרציה של התהליך (שים לב: רשת זרימה מורחבת אינה רשת זרימה).
רשת זרימה מתוחזקת היטב עם איטרציה רגילה (WRI - well-handled with regular iteration) היא רשת זרימה מורחבת לא מעגלית. רשת זרימה WRI יכולה להיבנות כצירוף של רשתות, כלומר החלפת מעבר ברשת זרימה WRI בתת-רשת זרימה WRI. התוצאה תהיה גם רשת רשת זרימה WRI. רשתות זרימה WRI הן גם נאותות-G, לכן על ידי שימוש באבני בניין מסוג רשת זרימה WRI בלבד, ניתן להשיג רשתות זרימה שהן נאותות-G לפי המבנה.
מטריצת מבנה העיצוב (DSM) (ר"ת של design structure matrix) יכולה למדל יחסי תהליך, ולשמש לתכנון תהליכים. רשתות DSM הן מימושן של תוכניות מבוססות DSM לתהליכי זרימה על ידי רשתות פטרי, ושקולות לרשתות WRI-WF. תהליך בניית רשת ה-DSM מבטיח את תכונת הנאותות של הרשת המתקבלת.

מודלים אחרים של מקביליות

הוצעו דרכים אחרות למידול חישוב במקבילי, כולל אלגברת תהליך, מודל השחקן ותיאורית העקבות. דגמים שונים מספקים פשרות של מושגים כמו קומפוזיציונליות, מודולריות, ולוקליות.
גישה לקישור חלק מהמודלים לעיל מוצע בפרק על ידי ווינסקל ונילסן.