Аннотация:
Мы обсудим одну из моделей распределенных вычислений под названием “популяционные протоколы”. С точки зрения логики, популяционные протоколы интересны благодаря своим связям с арифметикой Пресбургера. А именно, в работах Англуина и др. было доказано, что множество предикатов, выразимых в арифметике Пресбургера, совпадает с множеством предикатов, которые можно вычислить популяционными протоколами.
В докладе мы сначала дадим точнее определение этой модели; затем мы сформулируем и обсудим результат Англуина и др.; и наконец, мы дадим обзор того, чем занимаются люди в этой области сейчас.
