ДонНТУ   Портал магістрів

Реферат за темою магістерської роботи


"Оптимізація оптимістичного протоколу – огляд"

Зміст

Вступ

Розподілене дискретно-подієве моделювання здійснюється набором логічних процесів (ЛП), які взаємодіють один з одним шляхом відправки повідомлень з часовими мітками, які представляють модельовані події. Кожен ЛП має свой локальний годинник, який називається локальним віртуальним часом (ЛВЧ), що показує просування процесу моделювання. Час збільшується після обробки події на логічному процесорі. Існує два широко відомих підходи до процесу моделювання – консервативний та оптимістичний. Консервативний протокол дає гарантію, що обробка події не призведе до появи причинно-наслідкової помилки через позачергову обробку. Оптимістичний протокол виконує події жадібно без дотримання обмежень безпеки.

Оптимістичні методи синхронізації допускають появу порушень черговості виконання подій, але вони виявляють і виправляють їх. Оптимістичні підходи пропонують дві важливі переваги порівняно з консервативними методами. По-перше, вони можуть використовувати велику ступінь паралелізму. По-друге, консервативний механізм зазвичай покладаються на застосування конкретної інформації (наприклад, відстані між об'єктами) для того, щоб визначити, які події є безпечними для обробки, оптимістичні алгоритми працюють без такої інформації. З іншого боку, оптимістичні методи можуть зажадати більше накладних витрат для обчислень, ніж консервативні підходи, що призводить до певної деградації продуктивності.

Механізм Time Warp є найбільш відомим оптимістичним алгоритмом. Принцип його роботи полягає у виконанні подій без гарантії дотримання послідовного порядку. Якщо виникає ситуація порушення природного порядку тимчасових міток подій, протокол виробляє відкочування до необхідного стану, використовуючи механізм анти-повідомлень. Анти-повідомлення – це дублікат раніше відправленого повідомлення. Основними недоліками алгоритму Time Warp є надмірне споживання пам'яті, можливість виникнення каскадних відкотів, низька швидкість моделювання в разі частих відкотів. Існуючі алгоритми оптимізації Time Warp намагаються усунути ці недоліки.

1 Зменшення витрат на відкочування

Технологія агресивного скасування намагається скасувати неправильні обчислення якомога раніше, до того, як будь-який з процесів почне використовувати некоректні вихідні дані. Щоб реалізувати це, усі анти-повідомлення генеруються під час відкоту, до того, як відбудеться повторне виконання подій [2]. Технологія ледачого скасування навпроти не поспішає з відкотом подій, очікуючи підтвердження, що вихід неправильний, щоб не викликати каскадний відкот інших фізичних процесів. Цей метод досить ефективний, але він може викликати більший відкот залежних процесів, дозволяючи їм виконувати помилкові обчислення [1,2]. Ледачі переобчислення в деякому роді схожі на ледачий відкот, але використовують затримку відкидання вектора станів замість затримки відправлення анти-повідомлень. Адаптивне скасування призначене для вирішення проблеми з необхідністю визначення стратегії скасування на етапі запуску. Воно дозволяє процесу самому визначати, яку стратегію скасування використовувати, ѓрунтуючись на показниках часу виконання [1,2]. Fujimoto запропонував механізм прямого скасування, який використовує колективну пам'ять для оптимізації відкоту некоректних обчислень. Якщо під час виконання події E1 приходить нове повідомлення Е2, механізм асоціює покажчик на Е2 з подією Е1. Під час відкоту події Е1, покажчик може бути використаний для скасування Е2 із застосуванням ледачого або агресивного скасування [2,3].

Інші підходи були запропоновані для більш раннього обмеження довжини послідовних відкотів. Prakash і Subramanian [2] приєднують до повідомленнями інформацію про стан для запобігання каскадних відкотів, що дозволяє відфільтрувати застарілі повідомлення. Madisetti [2] запропонував механізм, який заморожує просторове поширення некоректних обчислень, заснований на так званій сфері впливу. Недолік цього підходу в тому, що набір моделюючих процесів, які можуть бути піддані впливу некоректних обчислень, значно більше фактичного набору, що призводить до відправки непотрібних керуючих повідомлень [2].

2 Зменшення витрат пам'яті

Механізм обрізання [5] запропонували використовувати для вивільнення використовуваної пам'яті. Він ѓрунтується на відновленні необхідної пам'яті з інформації про збережені стани. Якщо виникає відкочування до відсутнього стану, то проводиться відкот до стану, що є першим до відсутнього, а потім перевиконання подій. Ні фізичні процеси, ні стан ГВЧ не повинні бути видалені [4]. Carothers [4,6] застосував підхід виправлення фізичних процесів як потенційно оборотних. Відкот досягається застосуванням зворотних операцій з використанням поточного стану і збережених вхідних подій.

2.1 Методи, оптимізують збереження станів

Періодичне збереження станів (Periodic State Saving – PSS) зменшує накладні витрати шляхом збільшення інтервалу збереження станів. PSS зберігає внутрішній стан після кожних χ оновлень стану. Якщо виникає відкот і необхідний стан відсутній, проводиться відкот до більш раннього збереженого стану [7]. Інтервал збереження – це ключовий параметр, який визначає ефективність методу PSS: він регулює співвідношення між загальною вартістю збереження станів і кількістю переобчислень у повторній обробці повідомлень. Fleishmann і Wilsey [7] виконали емпіричне дослідження чотирьох адаптивних методів PSS. Вони представили евристику, яка перераховує витрати на збереження станів і повторну обробку повідомлень після кожних N подій. Якщо час виконання значно збільшився, інтервал збереження зменшується на одиницю, інакше – збільшується на одиницю. Sköld і Rönngren стверджували, що оптимальний інтервал збереження залежить від часу виконання або деталізації подій для різних типів подій. Їх подієво чутливий метод збереження станів залежить від того, якого типу подію було оброблено попередньою, і вирішує, чи зберігати вектор подій виходячи з цієї інформації.

Francesco Quaglia був запропонований алгоритм розрідженого збереження станів на базі історії подій [8]. Суть алгоритму полягає в тому, що кожен ЛП намагається спрогнозувати інтервали віртуального часу, в які виникне відкот. Даний підхід також заснований на моніторингу функції вартості контрольних точок і відкоту, перерахунок якої використовується для динамічного перерахунку параметра, що визначає відсоток збережених станів. Механізм інкрементного збереження станів (Incremental State Saving – ISS) зазвичай використовує часткове оновлення стану. Інкрементний запис історії станів ЛП створюється шляхом збереження старого значення змінної до її перезапису і нового значення, що використовується у разі відкоту – відновлюється кожне збережене значення змінної в порядку, що є зворотним збереженню. Для поліпшення роботи методів PSS і ISS були запропоновані гібридні методи, які чергують ці два механізми. Francesco Quaglia [9] пропонує гібридний підхід, заснований на комбінуванні PSS і ISS. Цей підхід пропонує періодично зберігати стан процесу, і зберігати частини зворотних перетворень в період між контрольними точками. Налаштованим параметрами є розмір інтервалу і кількість частково збережених станів за інтервал між двома контрольними точками.

3 Методи, що контролюють оптимізм

3.1 Неадаптивні протоколи

Перший метод контролю надмірного оптимізму використовує часові вікна. Цей підхід обмежує оптимізм, виконуючи події тільки в межах вікна модельного часу. Першим протоколом, що використовуює цю техніку, є Moving Time Window (MTW). Ключова проблема - визначення найбільш відповідного розміру часового вікна. Схожа ідея була вивчена Turner and Xu [10] в протоколі Bounded Time Warp(BTW), де ніякі події не обробляються до тих пір, поки всі процеси не досягли того моменту в часі, коли встановлюється новий кордон.

Алгоритм Breathing Time Bucket використовує оптимістичну обробку з локальними відкотами. Цей метод не потребує анти-повідомлень і, по суті, є безризиковим. Breathing Time Warp [11] є розширенням Breathing Time Bucket, яке дозволяє йому додавати деякий ризик. Ідея полягає в обробці перших N1 подій поза ГВЧ, так само, як у базовому алгоритмі Time Warp. Потім протокол перемикається назад в режим Breathing Time Bucket для обробки наступних N2 подій. Якщо всі процеси досягли своєї межі обробки подій, то починається новий розрахунок ГВЧ і запускається новий цикл.

3.2 Адаптивні протоколи, що ѓрунтуються на локальних станах

Керуючий механізм Adaptive Time Warp [12] використовує метод штрафів для обмеження механізму шляхом блокування ЛП на деякий інтервал реального часу (блокуюче вікно). Блокуюче вікно встановлюється для мінімізації суми загального процесорного часу, витраченого в блокованому стані і в стані відновлення. Логічний процес може прийняти рішення тимчасово призупинити обробку події, якщо він тільки що зазнав аномально високу кількість відкотів.

Hamnes і Tripathi [13] запропонували локальний адаптивний протокол, що призначений для максимізації просування модельного часу (зі швидкістю просування модельного часу α). Цей алгоритм збирає статистику на кожному каналі кожного ЛП і використовує її для максимізації α. Імовірнісний прямий адаптивний протокол контролю оптимізму 14] схожий на розглянутий вище, однак додає імовірнісну компоненту в тому сенсі, що блокування ініціюється з певною ймовірністю.

Параметризований Time Warp [15] поєднує в собі три адаптаційних механізми (періодичне збереження станів, обмежуюче часове вікно, а також пріоритет планування), щоб мінімізувати накладні витрати і збільшити продуктивність паралельного моделювання. Корисна робота є функцією від декількох параметрів (відношення числа скоєних до загальної кількості виконаних подій, число відкотів, кількість анти-повідомлень, довжина відкотів і т.д.). Період збереження станів та межі часового вікна збільшуються при великих значеннях параметра корисної роботи.

3.3 Адаптивні протоколи, що ѓрунтуються на глобальному стані

Протокол Adaptive Memory Managment намагається мінімізувати загальний час виконання, а не концентруватися на одному конкретному критерії. Стверджується, що такий підхід не дозволяє оптимізувати один з параметрів обчислень за рахунок непропорційного збільшення іншого.

Протоколи Near Perfect State Information (NPSI) [16] є класом адаптивних протоколів, що ѓрунтуються на доступності майже ідеальної інформації про глобальний стан паралельного моделювання. NPSI протоколи використовують кількісний потенціал помилки (EPi), пов'язаний з кожним ЛПi, для контролю оптимізму ЛПi. Протокол підтримує кожен EPi в оновленому стані відповідно до просування моделювання. Інший компонент протоколу переводить EPi в контроль над агресивністю й ризиком ЛПi. Одним з NPSI протоколів є Elastic Time Algorithm (ETA). В ЕТА найбільш дальній ЛПi йде тим далі від свого попередника, чим повільніше його хід через стримуюче притягнення еластичних зв'язків, що пов'язують його зі своїм попередником – звідси еластичність часу. Напруженість в еластичних зв'язках відповідає потенціалу помилки ЛПi.

Протокол, що ѓрунтуються на механізмі рухомого вікна в комп'ютерних мережах, де одержувач і відправник регулюють за допомогою спеціальних повідомлень розмір вікна, був запропонований Kiran і Fujimoto [17]. Оцінюється число запланованих необроблених повідомленнь для кожного процесора, ці оцінки використовуються для визначення рухомого вікна, яке визначає верхню межу числа необроблених повідомлень, яке ЛП може запланувати в один час. Просування ГВЧ робить повідомлення підтвердженим, таким чином дозволяючи відправити більше повідомлень. Застосовуються три етапи оцінки розміру вікна. Перший – це миттєвий розмір вікна, необхідний для відповідного послідовного виконання. Другий – вікно, необхідне до обчислення наступного ГВЧ. Третя частина – вікно для оптимістичних розрахунків.

3.4 Адаптивні протоколи, що ѓрунтуються на імовірнісних обчисленнях

Система MIMDIX використовує ідеї ймовірнісної повторної синхронізації для усунення надмірно оптимістичної поведінки. Спеціальний процес ймовірнісно посилає синхронізаційні повідомлення всім ЛП, змушуючи їх синхронізувати мітку повідомлення. Підтримуючи мітку синхронізації повідомлення близької до ГВЧ, логічні процеси можна тримати близько один до одного за часом, тим самим зменшуючи ризик каскадних відкотів.

Damani, Wang і Garg [18] запропонували параметричний алгоритм відновлення станів, де K – це деякий параметр, який визначає ступінь оптимізму, використовувану для налаштування оптимального співвідношення між накладними витратами та ефективністю відновлення. K – це ціле число в інтервалі від 0 до N, де N – загальне число процесів. Воно визначається як максимальне число процесів, чия відмова може анулювати деяке повідомлення m.

3.5 Інші адаптивні протоколи

Damani і співавтори в [19] запропонували оптимістичний алгоритм для швидкої зупинки помилкових обчислень. Цей алгоритм є модифікацією Distributed recovery with K-optimistic logging [18]. Схема не вимагає черги вихідних повідомлень і анти-повідомлень. Це призводить до зменшення накладних витрат пам'яті і простим алгоритмам управління пам'яттю. Схема також усуває проблему каскадних відкотів, що призводить до прискорення моделювання. Використовується агресивне скасування.

Концепція алгоритму – створення й підтримка транзитивної інформаційної залежності між процесами. Підтримується таблиця номерів інкарнації – число відкотів, зроблених процесом. У таблиці також зберігається часова мітка повідомлення, що викликав відкот. Якщо процес виявляє, що він отримав запізніле повідомлення, він розсилає повідомлення, що містять поточний інкарнаціонний номер k і тимчасову мітку повідомлення t, а потім блокує свою роботу. Розіслані повідомлення показують, що всі стани інкарнації k з віртуальним часом, більшим за t, є некоректними. Стани, що залежать від них, теж є некоректними.

Smith, Johnson, і Tygar [20] запропонували повністю асинхронний оптимістичний протокол відновлення з мінімальними відкотами, що ѓрунтуються на методі Optimistic Message Logging. Протокол не вимагає відправки жодних повідомлень і зменшує максимальну кількість відкотів для кожного процесу до одного. Існують два типи повідомлень, кожен зі своїм інтервалом збереження – користувальницькі (повідомлення моделювання) і системні. Журналюются тільки призначені для користувача повідомлення. Також використовується вектор станів для швидкого завантаження потрібного стану.

4 Еволюційні підходи

Еволюційні підходи є відносно новими серед технік оптимізації алгоритму Time Warp. Алгоритми, які ѓрунтуються на теорії еволюції, знаходять оптимальне рішення методом проб і помилок. Еволюційні алгоритми починаються з вибору довільного рішення з простору рішень. Оцінюється придатність кожного кандидата в популяції і відбираються кандидати для розмноження. Потім вибираються пари кандидатів, і здійснюється рекомбінаційна операція – створення потомства. Після оцінки дітей процес відбору повторюється і створюється наступне покоління.

Алгоритм GMA (Genetic Modifying Algorithm) [21] вирішує задачу адаптивної настройки параметрів, які визначають режим роботи запису і відновлення. Зазначені параметри відповідають поточному режиму журналювання (інкрементний або неінкрементний) та поточному інтервалу журналювання. Режими журналювання та інтервали пов'язані з набором об'єктів моделювання – генотипом. Потомство оцінюється за допомогою функції виживання, яка ѓрунтуються на кількості здійснених подій. Коли спостерігається підвищення продуктивності, мутації застосовуються до тих частин генотипу, яких не торкнулися кроки еволюції. Коли виявляється погіршення, відновлюється знімок генотипу до останньої мутації, і поновлюються мутації на ньому. Генотип стартує з випадковою конфігурації.

Інший генетичний алгоритм запропонували Wang і Tropper [22] для обмеження оптимізму. Алгоритм ітераційним способом визначає оптимальний розмір вікна, в межах якого можуть виконуватися події на процесорах. Кожен процесор має свій розмір вікна. Оцінка вікон проводиться виходячи з просування моделювання. Вікна оцінюються в десяти послідовних інтервалах ГВЧ і коефіцієнт виживання - середнє з десяти оцінок. Батьки вибираються або методом генерації випадкових чисел в діапазоні [0,1], або методом стохастичної універсальної вибірки, де генерується одне випадкове число в діапазоні [0, 1/с], де с – загальне число кандидатів.

5 Алгоритми обчислення глобального віртуального часу

Глобальний віртуальний час (ГВЧ) використовується в Time Warp для визначення прогресу в моделюванні. Значення ГВЧ не зменшується з плином реального часу. Дві важливі проблеми, які вирішуються ГВВ, – звільнення пам'яті і підтвердження операцій, які неможна відмінити.

5.1 Централізоване обчислення глобального віртуального часу

У централізованих алгоритмах ГВЧ розраховується центральним ГВЧ-менеджером, який розсилає запити всім ЛП про їх поточний ЛВЧ та обчислює мінімальне значення. У цьому підході є дві проблеми. По-перше, повідомлення в дорозі, які потенційно можуть викликати відкот врахованого ЛВЧ, не беруться в розрахунок (проблема нестаціонарності повідомлень). По-друге, значення ЛВЧ, які були отримані від ЛП у різний реальний час, що називається проблемою одночасної звітності.

Один з перших ГВЧ-алгоритмів (Minimum Simulation Time (GVT) Algorithm) був запропонований Samadi [23]. ГВЧ-менеджер посилає вихідне початкове повідомлення ГВЧ. Після того, як усі ЛП прислали відповідь на запит, ГВЧ-менеджер обчислює і розсилає нове значення ГВЧ. Проблема нестаціонарності повідомлень вирішується підтвердженням кожного повідомлення та звіту ГВЧ-менеджеру про мінімум серед усіх міток непідтверджених повідомлень і ЛВЧ логічного процесу. Lin і Lazowska [24] представили деякі поліпшення цього алгоритму. В їх алгоритмі немає підтверджень для повідомлень, але заголовки повідомлень містять порядковий номер. ЛП-отримувач може ідентифікувати втрачене повідомлення як пропуск з отриманого порядкового номера. Проблема одночасної звітності вирішується встановленням меж на реальний час звітності на кожному ЛП таким, що набір інтервалів має загальний реальний час. Кожен ЛП може передавати інформацію на ГВЧ-менеджер, як тільки залишає інтервал.

Для зменшення комунікаційної складності обчислення ГВЧ Bellenot [25] використовує граф маршрутизації повідомлень. Обчислення ГВЧ вимагає двох циклів – один для запуску обчислення ГВЧ, другий – для отримання локального мінімуму та обчислення глобального мінімуму. The multi-level token passing algorithm [26] застосовує ієрархічний метод для розпаралелювання обчислення ГВЧ. Багаторівневе розкладання дозволяє паралельно визначати мінімальний час серед менеджерів кожного рівня.

Bauerr і співавтори [27] запропонували алгоритм, в якому нумеруються всі повідомлення про події, що проходять через певний канал. Логічні процеси враховують номера відправлених та отриманих повідомлень, та мінімальні позначки повідомлень про подію з моменту останнього звіту про ГВЧ.

Алгоритм пасивної реакції GVT (pGVT) [28] може працювати в середовищі з ненадійними каналами зв'язку. У ньому ЛП обчислюе час затримки повідомлення, щоб вирішити, коли відправляти нову інформацію про глобальний віртуальний часу ГВЧ-менеджеру. Ключовим поліпшенням є те, що модельовані за критичним шляхом ЛП будуть повідомляти ГВЧ-інформацію частіше, ніж інші.

Ефективний асинхронний алгоритм був представлений Fujimotoo і Hybinette [29]. Він використовує колективну мультипроцесорну пам'ять, яка гарантує, що ніякі два процесори не побачать набір операцій з пам'яттю, що виникають в різному порядку. Алгоритм не вимагає підтвердження повідомлень, FIFO-доставку повідомлень або спеціальні GVT-повідомлення.

5.2 Розподілене обчислення глобального віртуального часу

Розподілені алгоритми ГВЧ не вимагають ані централізованого менеджера, ані наявності загальної пам'яті між процесами. Mattern [30] представив ефективний розподілений алгоритм моментального знімка для не-FIFO каналів зв'язку, який не потребує підтвердження повідомлень. Алгоритм визначає два знімки, і другий проштовхується вперед так, що всі перехідні повідомлення укладені між двома знімками. Проблема знання, коли знімок повний, вирішується розподіленої схемою припинення виявлення.

Srinivasan and Reynolds [31] розробили паралельну мережу скорочення (PRN). ЛП пересилають деякі відомості про стани в PRN, яка підтримується розподіленим ГВЧ-алгоритмом. Підтвердження прийому повідомлення також відправляються на мережу. PRN використовується для обчислення і поширення мінімальних ЛВЧ всіх ЛП і мінімумів міток всіх неотриманих повідомлень. ГВЧ стає доступним для кожного ЛП асинхронно.

ГВЧ-алгоритм у середовищі моделювання SPEEDES оптимізований для підтримки інтерактивного розподіленого оптимістичного моделювання. Проблема нестаціонарності повідомлень вирішується за допомогою очищення всіх повідомлень на етапі поновлення ГВЧ. Алгоритм SPEEDES GVT продовжує обробляти події під час цієї фази, але й нові повідомлення, які можуть бути згенеровані, видаляються не відразу.

6 Класифікація алгоритмів оптимізації оптимістичного протоколу

Розглянуті методи оптимізації можна умовно розділити на кілька груп згідно з проблемою оптимістичного протоколу, яку вони вирішують, та способам досягнення результату (рис. 1).

Классифікація методів оптимізації оптимістичного протоколу

Рисунок 1 – Классифікація методів оптимізації оптимістичного протоколу

Проте, не можна чітко розбити алгоритми на класи, оскільки багато з них, хоча і спрямовані на поліпшення будь-якого показника ефективності, одночасно впливають і на інші аспекти моделювання. На рис. 2 показані причинно-наслідкові зв'язки між методами та алгоритмами оптимізації, а також між характеристиками моделюючої системи.

Причинно-наслідкові зв'яки між алгоритмами классифікації

Рисунок 2 – Причинно-наслідкові зв'яки між алгоритмами классифікації

Висновки

Результатом досліджень є класифікація алгоритмів за типом оптимізованої характеристики і методами, що застосовуються для цієї мети, а також аналіз алгоритмів з точки зору їх переваг та недоліків та їх впливу на оптимізацію інших параметрів моделюючої системи.

На момент написання даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2012 року. Повний текст роботи і матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

Список ждерел

  1. Radharamanan Radhakrishnan, Timothy J. McBrayer, Krishnan Subramani, Malolan Chetlur, Vijay Balakrishnan and Philip A. Wilsey. A Comparative Analysis of Various TimeWarp Algorithms Implemented in the WARPED Simulation Kernel. – 1998.
  2. Voon-Yee Vee, Wen-Jing Hsu. Parallel Discrete Event Simulation: A Survey.
  3. Richard M. Fujimoto. Parallel discrete event simulation – 1990.
  4. Bruce Jones, Vanessa Wallace. Time-Event based processing, a Survey.
  5. Bruno R. Preiss, Wayne M. Loucks. Memory Management Techniques for Time Warp on a Distributed Memory Machine. – 1995.
  6. C. Carothers, K. Perumalla, R. M. Fujimoto. Efficient Optimistic Parallel Simulations using Reverse Computation. – 2000.
  7. Josef Fleischmann, Philip A. Wilsey. Comparative Analysis of Periodic State Saving Techniques in Time Warp Simulators. – 1995.
  8. Francesco Quaglia. Event History Based Sparse State Saving in Time Warp. – 1998.
  9. Francesco Quaglia. Rollback-based parallel discrete event simulation by using hybrid state saving. – 1997.
  10. S.J. Turner and M. Q. Xu. Performance evaluation of the bounded Time Warp algorithm. – 1992.
  11. Jeff S. Steinman. Breathing Time Warp. – 1992.
  12. D. Ball and S. Hoyt. The adaptive Time-Warp concurrency control algorithm. – 1990.
  13. D. O. Hamnes and A. Tripathi. Investigations in adaptive distributed simulation. – 1994.
  14. Alois Ferscha. Probabilistic Adaptive Direct Optimism Control in Time Warp.
  15. Avinash C. Palaniswamy, Philip A. Wilsey: Parameterized Time Warp (PTW): An Integrated Adaptive Solution to Optimistic PDES. – 1996.
  16. S. Srinivasan, P. Reynolds, Elastic Time. – 1998.
  17. Kiran S. Panesar, Richard M. Fujimoto. Adaptive Flow Control in Time Warp. – 1997.
  18. Om P. Damani, Yi-Min Wang, Vijay K. Garg. Distributed Recovery with K-Optimistic Logging.
  19. Om P. Damani, Yi-Min Wang, Vijay K. Garg. Optimistic Distributed Simulation Based on Transitive Dependency Tracking.
  20. Sean W. Smith, David B. Johnson, and J. D. Tygar. Completely Asynchronous Optimistic Recovery with Minimal Rollbacks. – 1995.
  21. Alessandro Pellegrini, Roberto Vitali, Francesco Quaglia. An Evolutionary Algorithm to Optimize Log/Restore Operations within Optimistic Simulation Platforms. – 2011.
  22. Jun Wang, Carl Tropper. Using Genetic Algorithm to Limit the Optimism in Time Warp. – 2009.
  23. Samadi, B. Distributed simulation, algorithms and performance analysis. – 1985, 226 c.
  24. Yi-Bing Lin, Edward D. Lazowska. Determining the Global Virtual Time in a Distributed Simulation. – 1990.
  25. Bellenot, S. Global Virtual Time Algorithms. – 1990.
  26. Conception, A.I., Kelly, S.G., Computing global virtual time using the Multiple-Level Token Passing algorithm. – 1991.
  27. Bauer, H., Sporrer, C., Distributed logic simulation and an approach to asynchronous GVT-calculation. – 1992.
  28. L.M. D'Souza, X. Fan, P.A. Wilsey. pGvt: An Algorithm for Accurate GVT Estimation. – 1994.
  29. Richard Fujimoto, Maria Hybinette: Computing Global Virtual Time in Shared-Memory Multiprocessors. – 1997.
  30. F. Mattern. Efficient algorithms for distributed snapshots and global virtual time approximation. – 1993.
  31. S. Srinivasan, P.F. Reynolgs. Hardware support for aggressive parallel discrete event simulations. – 1992.