Lo­c­al­ly Check­a­ble La­be­lings for Lea­der Elec­ti­on in Pro­­gram­m­a­ble Mat­ter and Bey­ond

A Locally Checkable Labeling (LCL) is a specification describing a set of labels that are valid with respect to a set of conditions that characterize a local part of a solution to a global problem. Conditions can only refer to nodes and labels within a constant radius neighborhood of each node. In this talk, we will discuss local labeling schemes whose global consistency implies solutions to leader election which is a classical problem in distributed computing. Contrary to previous LCLs for leader election we assume that nodes do not have unique identifiers (i.e., nodes are anonymous) and we give (i) a labeling scheme of constant size per node for simply connected induced subgraphs of the triangular grid for nodes that can check conditions at distance one, (ii) a labeling scheme of constant size per node for meshed graphs assuming that nodes can check conditions at distance two and (iii) a labeling scheme of constant size per edge for chordal and K_4-free dismantlable graphs for nodes that can check conditions at distance two. 

This talk is based on joint work with Jérémie Chalopin, Victor Chepoi and Shantanu Das