Distributed algorithms for LCL optimisation problems

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Computer Science
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
In distributed computing, nodes of a network process information algorithmically while sending and receiving data via connections. Time complexity in LOCAL model algorithms is measured in rounds of synchronous message-passing, where in one round a message traverses from one node to an adjacent node. Local processing power or message size is not limited, and each node has a unique identifier. Locally checkable labelling (LCL) problems on distributed networks rely on small local neighbourhoods together forming a globally correct output configuration. In cycle networks, locally verifiable non-trivial problems such as 3-colouring are solvable using a number t of rounds, where t has order of a very slow-growing function (i.e. iterated logarithm, or ``log-star'') of the network node count n. Cycle LCLs can be divided to three distinct time complexity classes, with the other two being constant time and linear time w.r.t. n. In this thesis we establish a pair of classes for certain LCL optimisation problems -- binary LCL packing and covering. For them, both possible and impossible factors of approximation are derived w.r.t. time t used when not allowing randomisation. The classes contain problems in which the aim is to either maximise or minimise (respectively) the size of the solution set. In particular, relaxing the requirement of maximality or minimality of an existing LCL set problem, e.g. maximal independent set or minimal dominating set, brings forth a maximisation or minimisation variant with measurable approximation quality. In cycles, binary LCL packing problems cannot be alpha-approximated in constant time with alpha=o(log exp * n). However, if the problem is not a global one, it can be (1 + epsilon)-approximated in O(k exp 3 + klog exp * n) time in a directed cycle, where epsilon g 0 is any small positive constant and k=O(epsilon exp -1). The presented algorithms for directed cycles can be further optimised, and similar algorithms exist for undirected cycles. Binary LCL covering problems can be alpha-approximated in O(1) rounds in cycles, for constant alpha. Constant time algorithms cannot do better than (1-epsilon)beta-approximate the optimal, where epsilon g 0 is arbitrarily small and beta g 1 is the inverse of the asymptotically optimal ratio of solution nodes to the node count n. Similarly to the packing problems, using O(epsilon exp -3 + epsilon exp -1 log exp * n) rounds is sufficient for approximating non-global problems with factor (1+epsilon).
Suomela, Jukka
Thesis advisor
Suomela, Jukka
distributed algorithm, LCL, LOCAL model, optimisation, deterministic, cycle
Other note