BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T211827Z
UID:Seminar-networks-1134@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Giorgos Christodoulou:MAILTO:G.Christodoulou@liverpool.ac.uk
DTSTART:20210527T120000
DTEND:20210527T130000
SUMMARY:Networks and Distributed Computing Series
DESCRIPTION:P. Uznanski: Comparison Dynamics in Population Protocols\n\nThere has recently been a surge of interest in the computational and complexity properties of the population model, which assumes n anonymous, computationally-bounded nodes, interacting at random, with the goal of jointly computing global predicates. Significant work has gone towards investigating majority or consensus dynamics in this model: that is, assuming that every node is initially in one of two states X or Y , determine which state had higher initial count.\n\nIn this work, we consider a natural generalization of majority/consensus, which we call comparison:\nin its simplest formulation, we are given two baseline states, X_0 and Y_0, present in any initial configuration in fixed, but possibly small counts. One of these states has higher count than the other: we will assume |X_0| ? C|Y_0|, for some constant C > 1. The challenge is to design a protocol by which nodes can quickly and reliably decide on which of the baseline states X_0 and Y_0 has higher initial count. We begin by analysing a simple and general dynamics solving the above comparison problem, which uses O(log n) states per node, and converges in O(log n) parallel time, with high probability, to a state where the whole population votes on opinions X or Y at rates proportional to the initial concentrations of |X_0| vs |Y_0|. We then describe how this procedure can be bootstrapped to solve comparison, i.e. have every node in the population reach the “correct” decision, with probability 1 ? o(1), at the cost of O(log log n) additional states. Further, we prove that this dynamics is self-stabilizing, in the sense that it converges to the correct decision from arbitrary initial states, and leak-robust, in the sense that it can withstand spurious faulty reactions, which are known to occur in practical implementations of population protocols.\n\nOur analysis is based on a new martingale concentration result relating the discrete-time evolution of a population protocol to its expected (steady-state) analysis, which should be a useful tool when analysing opinion dynamics and epidemic dissemination in the population model.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1134
LOCATION:
END:VEVENT
END:VCALENDAR