## Distributed algorithms for LCL optimisation problems

Loading...

##### Journal Title

##### Journal ISSN

##### Volume Title

Perustieteiden korkeakoulu |
Master's thesis

Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

##### Author

##### Date

2018-12-10

##### Department

##### Major/Subject

Computer Science

##### Mcode

SCI3042

##### Degree programme

Master’s Programme in Computer, Communication and Information Sciences

##### Language

en

##### Pages

51

##### Series

##### Abstract

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).##### Description

##### Supervisor

Suomela, Jukka##### Thesis advisor

Suomela, Jukka##### Keywords

distributed algorithm, LCL, LOCAL model, optimisation, deterministic, cycle