日時：8月10日（水）10:00-12:00
場所：九州大学 伊都キャンパス ウェスト2号館 7階 720
Speaker：Prof. Leszek Gasieniec (University of Liverpool)

10:00-11:00
Deterministic Majority/Plurality Consensus Protocols

Leszek Gasieniec, University of Liverpool
Joint work with D. Hamilton, R. Martin, P. Spirakis, and G. Stachowiak

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.

11:00-12:00
Perpetual maintenance of machines with different attendance urgency factors

Leszek Gasieniec, University of Liverpool
Joint work with R. Klasing, Ch. Levcopoulos, A. Lingas, J. Min, and T. Radzik

A garden G is populated by n \leq 1 bamboos b_1, b_2, ..., b_n with the
respective daily growth rates h_1, h_2, ..., h_n. It is assumed that the
initial height of each bamboo is null. The gardener maintaining the garden
is attending bamboos and trimming them to null height according to some
schedule. The Bamboo Garden Trimming (BGT) problem is to design a perpetual
schedule of cuts with the goal of keeping the highest bamboo in the garden
as low as possible. The bamboo metaphor refers to a system of machines which
needs to be serviced with different frequencies by a robot which can service
only one machine a day. The main objective is to design a perpetual schedule
of servicing the machines which minimizes the maximum weighted waiting time.
We consider two variants of the BGT problem.

In the discrete variant the gardener is allowed to trim only one bamboo at
the end of each day and is not allowed to trim bamboos at any other time.
In the continuous variant the bamboos can be cut at any time. However, the
gardener needs time to move some distance across from one bamboo to the next
one and this time is defined by a weighted network of connections. We show a
close relationship between the BGT problem and the classical Pinwheel
scheduling problem, which is known to be intractable and present several
approximation algorithms for both variants of BGT.

ホスト：来嶋(B01)