Seminar Announcement: Prof. L. A. Gąsieniec @ GSSI

Abstract: We study space-optimal population protocols for several variants of the majority and plurality consensus problems. We start with an important amendment allowing majority population protocols to report equality if neither of the original colours dominates the others in the population. Further we study space efficient plurality consensus protocols in populations with an arbitrary number C of colours represented by k-bit labels, where k = log C. In particular we present: (1) an asymptotically space-optimal O(k)-bit protocol for the absolute majority, i.e., a protocol which decides whether a single colour dominates all other colours considered together, (2) an asymptotically space-optimal O(k)-bit protocol for the relative majority where colours declare their volume superiority versus other individual colours. The new population protocols rely on a novel dynamic formulation of the majority problem in which the colours originally present in the population can be changed during the communication process by an external force. The new dynamic formulation of the majority and plurality protocols provides a novel framework for multi-stage population protocols.