הקורס עוסק בתכנון אלגוריתמים למערכות מרובות מעבדים, ניתוח סיבוכיות והבעיות הבסיסיות במערכות אלה, חסמים תחתונים ותוצאות אי-אפשרות. בעיות ספציפיות כוללות: מניעה הדדית והקצאת משאבים, בעיות הסכמה (בעיית הגנרלים הביזנטיים, הסכמה מקורבת), סנכרון שעונים ושעונים לוגיים, בעיות הפצה סנכרון ללא מנעולים ומבני נתונים מבוזרים.
The course deals with design of algorithms for multi-processor systems, and analysis of their complexity;study of basic problems in such systems; lower bounds and impossibility results. Specific topics include: Mutual exclusion and resource allocation, agreement problems(Byzantine generals’ problem, approximate agreement, etc.), clock synchronization and logical clocks, broadcast and multicast, lock-free synchronization and concurrent data structures.
Credit points: 3.0
Grading Policy:
- Homeworks - 50-60%
- Final assignment - 40-50%
- Submission of homeworks and final assignment can be in pairs.