Lo­­ca­l­­ly Checka­­ble La­­be­­lings for Lea­­der Elec­ti­on in Pro­­gram­m­a­­ble Mat­ter and Beyond

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