Никитин Илья Сергеевич
Оптимизация случайных процессов путем перезапуска является предметом активных теоретических исследований в статистической физике и уже давно нашла практическое применение в компьютерных науках. Между тем, один из ключевых вопросов остается в значительной степени нерешенным: когда нам следует перезапускать процесс, подробная статистика которого неизвестна, чтобы гарантировать, что наше вмешательство улучшит производительность? Отвечая на этот вопрос, мы предлагаем несколько конструктивных критериев эффективности различных протоколов немедленного перезапуска в задаче о среднем времени завершения и вероятности успеха. Выраженные в терминах небольшого числа легко оцениваемых статистических характеристик исходного процесса (среднее, медиана, MAD, моменты более высоких порядков), эти критерии позволяют принять обоснованное решение о перезапуске, основанное на частичной информации о статистике процесса.