Fully Lattice-Linear Algorithms Arya Tanmay Gupta Sandeep S Kulkarni Computer Science and Engineering Michigan State University

2025-05-06 0 0 1.17MB 40 页 10玖币

侵权投诉

Fully Lattice-Linear Algorithms∗†‡

Arya Tanmay Gupta Sandeep S Kulkarni

Computer Science and Engineering, Michigan State University

{atgupta,sandeep}@msu.edu

Abstract

Lattice-linearity was introduced as a way to model problems using

predicates that induce a lattice among the global states (Garg, SPAA

2020). A key property of the predicate representing such problems is that

it induces one lattice in the state space. An algorithm that emerges from

such a predicate guarantees the execution to be correct even if nodes exe-

cute asynchronously. However, many interesting problems do not exhibit

lattice-linearity. This issue was somewhat alleviated with the introduction

of eventually lattice-linear algorithms (Gupta and Kulkarni, SSS 2021).

They induce single or multiple lattices in a subset of the state space even

when the problem cannot be deﬁned by a predicate under which the global

states form a lattice.

This paper focuses on analyzing and diﬀerentiating between lattice-

linear problems and algorithms. We introduce fully lattice-linear algo-

rithms. These algorithms partition the entire reachable state space into

one or more lattices, and as a result, ensure that the execution remains

correct even if nodes execute asynchronously. For demonstration, we

present lattice-linear self-stabilizing algorithms for minimal dominating

set (MDS), graph colouring (GC), minimal vertex cover (MVC) and max-

imal independent set (MIS) problems.

The algorithms for MDS, MVC and MIS converge in nmoves and the

algorithm for GC converges in n+ 2mmoves. These algorithms preserve

this time complexity while allowing the nodes to execute asynchronously.

They present an improvement to the existing algorithms present in the

literature.

Our work also demonstrates that to allow asynchrony, a more relaxed

data structure can be allowed (called ≺-lattice in this paper, where the

∗The experiments presented in this paper were supported through computa-

tional resources and services provided by the Institute for Cyber-Enabled Re-

search, Michigan State University.

†Excerpts of this paper were published in a paper that appeared in the 42nd

International Symposium on Reliable Distributed Systems (SRDS 2023) [18].

‡This is an extended abstract of the SRDS 2023 paper. To get the arXiv

version of the SRDS paper, please go to a previous version uploaded on this arXiv

repository (2210.03055v4, uploaded on 30 Jul 2023). This extended abstract is

uploaded to this same arXiv repository due to the policies of arXiv on submissions

with shared content.

arXiv:2210.03055v5 [cs.DC] 27 Nov 2024

meet of a pair of global states may not be deﬁned), rather than a dis-

tributive lattice (where both join and meet for all pairs of global states

are deﬁned, and join and meet distribute over each other) as assumed by

Garg.

Keywords: self-stabilization, lattice-linear problems, lattice-linear algo-

rithms, asynchrony

1 Introduction

Many concurrent algorithms can be viewed as a loop where in each step/iteration,

a node reads the information about other nodes, based on which it decides to

take action and update its own state. As an example, in an algorithm for graph

colouring, in each step, a node reads the colour of all its neighbours and, if

necessary, updates its own colour. Execution of this algorithm in a parallel

or distributed system requires synchronization to ensure correct behaviour. For

example, if two nodes, say iand jchange their colour simultaneously, the result-

ing action may be incorrect. Mutual exclusion, transactions, dining philosopher

and locking are examples of synchronization primitives.

Let us consider that we allow such algorithms to execute in asynchrony:

consider that iand jfrom the above example execute asynchronously. Let us

suppose that ireads the state of jand changes its state. The action of iis

acceptable till now. However, if jreads the value of iconcurrently, it is relying

on inconsistent information about i. This is because iwill have changed its state

in its immediate next step. In other words, jis relying on old information about

i. The synchronization primitives discussed in the previous paragraph aim to

eliminate such behaviour. However, they introduce considerable overhead in

terms of time and computational resources.

Generally, reading values in asynchrony, as described in the example above,

causes the algorithm to fail. However, if the correctness of the algorithm can

be proved even when a node executes based on old information, then such an

algorithm can beneﬁt from asynchronous execution; such execution would not

suﬀer from synchronization overheads and each node can execute independently.

Garg [13] introduced modelling problems such that the entire reachable state

space forms a single lattice. Such induction allows asynchronous executions. We

[16] introduced eventually lattice-linear algorithms for problems that cannot be

modelled under the constraints of [13]. These algorithms induce (potentially

multiple) lattices in a subset of the state space. (We investigate these models

comprehensively in Section 3.)

A key property of lattice-linearity is that a total order is induced among the

local states visited by individual nodes. This ensures that the local states of a

node do not form a cycle; and as a consequence, single or multiple lattices are

induced among the global states.

In this paper, we introduce fully lattice-linear algorithms that are capable

of inducing single or multiple lattices in the entire reachable state space. We

show that with fully lattice-linear algorithms, it is possible to combine lattice-

linearity with self-stabilization, which ensures that the system converges to a

legitimate state even if it starts from an arbitrary state.

1.1 Contributions of the paper

•We alleviate the limitations of, and bridge the gap between, [13] and [16]

by introducing fully lattice-linear algorithms (FLLAs). The former creates

a single lattice in the state space and does not allow self-stabilization

whereas the latter creates multiple lattices in a subset of the state space.

FLLAs induce one or more lattices among all the reachable global states

and can enable self-stabilization. This overcomes the limitations of [13]

and [16].

•We provide upper bounds to the convergence time for an arbitrary algo-

rithm traversing a lattice of global states.

•We present fully lattice-linear self-stabilizing algorithms for minimal dom-

inating set (MDS) and graph colouring (GC).

•We show that a direct extension of the design of the algorithms for MDS

and GC to develop an algorithm for minimal vertex cover (MVC) exhibits

cyclic behaviour. However, we exploit the properties of MVC and make

changes to the design choices to obtain an algorithm for MVC. From here,

we straightforwardly obtain an algorithm for maximal independent set

(MIS) as well.

•The algorithms for MDS, MVC, MIS converge in nmoves and the al-

gorithm for GC converges in n+ 2mmoves. These algorithms are fully

tolerant to consistency violations and asynchrony. Thus, they are an im-

provement over the existing algorithms in the literature.

The major focus and beneﬁt of this paper is to study the theory behind the

algorithms, for non-lattice-linear problems, that are tolerant to asynchronous

executions and induce lattices in the state space. Some applications of the

speciﬁc problems studied in this paper are listed as follows. Dominating set is

applied in communication and wireless networks where it is used to compute the

virtual backbone of a network. Graph colouring is applicable in (1) chemistry,

where it is used to design storage of chemicals – a pair of reacting chemicals are

not stored together, (2) communication networks, where it is used in wireless

networks to compute radio frequency assignment, (3) academics, where it is

used to design exam timetables – exams attended by a single student, for each

student, are not conducted at the same time, and (4) economics, where it is used

in team management – people who do not want to work together are not put in

the same team. Vertex cover is applicable in (1) computational biology, where

it is used to eliminate repetitive DNA sequences – providing a set covering all

desired sequences, and (2) economics, where it is used in camera instalments –

it provides a set of locations covering all hallways of a building. Independent

set is applied in computational biology, where it is used in discovering stable

genetic components for designing engineered genetic systems.

1.2 Organization of the paper

In Section 2, we discuss the preliminaries that we utilize in this paper. In

Section 3, we discuss some background results related to lattice-linearity that

are present in the literature. In Section 4, we describe the general structure

of a (fully) lattice-linear algorithm. In Section 5, we present a fully lattice-

linear algorithm for minimal dominating set. We present a fully lattice-linear

algorithm for graph colouring in Section 6.

In Section 7, we discuss how a similar design of algorithms cannot be used to

develop all lattice-linear algorithms. We discuss why the design used to develop

algorithms for minimal dominating set and graph colouring cannot be extended

to develop algorithms for minimal vertex cover in Section 7.1. We present

algorithms for minimal vertex cover and maximal independent set problems in

Section 7.2 and Section 7.3 respectively. We elaborate on the properties similar

in the algorithms for minimal vertex cover and maximal independent set in

Section 7.4.

In Section 8, we provide an upper bound to the number of moves required,

for convergence, by an algorithm that traverses a lattice of states. We discuss

related work in Section 9. Then, in Section 10, we compare the convergence time

of the algorithm presented in Section 5 with other algorithms (for the minimal

dominating set problem) in the literature. Finally, we conclude in Section 11.

2 Preliminaries

In this paper, we are mainly interested in graph algorithms where the input is

a graph G,V(G)is the set of its nodes and E(G)is the set of its edges. For a

node i∈V(G),Adjiis the set of nodes connected to iby an edge, and Adjx

is the set of nodes within xhops from i, excluding i. While writing the time

complexity of the algorithms, we notate nto be |V(G)|and mto be |E(G)|.

For a node i,deg(i) = |Adji|, and Ni=Adji∪ {i}.

Aglobal state sis represented as a vector such that s[i]represents the local

state of node i.s[i]denotes the variables of node i, and is represented in the

form of a vector of the variables of node i. We use Sto denote the state space,

the set of all global states that a system can be in.

Each node in V(G)is associated with rules. Each rule at node ichecks the

values of variables of the nodes in Adjx

i∪ {i}(where the value of xis problem

dependent) and updates the variables of i. A rule at a node iis of the form

g−→ acwhere g, a guard, is a Boolean expression over variables in Adjx

i∪ {i}

and action acis a set of instructions that updates the variables of iif gis true.

A node is enabled iﬀ at least one of its guards is true, otherwise it is disabled.

Algorithms, in this paper, are written as a sequence of rules; the nodes execute

the ﬁrst rule whose guard is true. A move is an event in which an enabled node

updates its variables.

An algorithm Ais self-stabilizing with respect to the subset Soof Siﬀ it

satisﬁes the following properties: (1) convergence: starting from an arbitrary

state, any sequence of computations of Areaches a state in So, and (2) closure:

any computation of Astarting from Soalways stays in So. We assume Soto

be the set of optimal states: the system is deemed converged once it reaches a

state in So.Ais a silent self-stabilizing algorithm if no node is enabled once a

state in Sois reached.

2.1 Execution without synchronization

Typically, we view the computation of an algorithm as a sequence of global

states ⟨s0, s1,· · · ⟩, where st+1, t ≥0,is obtained by executing some rule by one

or more nodes (as decided by the scheduler) in st. For the sake of discussion,

assume that only node iexecutes in state st. The computation preﬁx uptil st

is ⟨s0, s1,· · · , st⟩. The state that the system traverses to after stis st+1. Under

proper synchronization, iwould evaluate its guards on the current local states of

its neighbours in st, and the resultant state st+1 can be computed accordingly.

To understand the execution in asynchrony, let x(s)be the value of some

variable xin state s. If iexecutes in asynchrony, then it views the global state

that it is in to be s′, where x(s′)∈ {x(s0), x(s1),· · · , x(st)}.In this case, st+1

is evaluated as follows. If all guards in ievaluate to false, then the system will

continue to remain in state st, i.e., st+1 =st. If a guard gevaluates to true

then iwill execute its corresponding action ac. Here, we have the following

observations: (1) st+1[i]is the state that iobtains after executing an action in

s′, and (2) ∀j̸=i,st+1[j] = st[j].

The model described in the above paragraph is arbitrary asynchrony, a model

in which a node can read old values of other nodes arbitrarily, requiring that

if some information is sent from a node, it eventually reaches the target node.

In this paper, however, we are interested in asynchrony with monotonous read

(AMR) model. AMR model is arbitrary asynchrony with an additional restric-

tion: when node ireads the state of node j, the reads are monotonic, i.e., if i

reads a newer value of the state of jthen it cannot read an older value of jat

a later time. For example, if the state of jchanges from 0to 1to 2and node i

reads the state of jto be 1then its subsequent read will either return 1or 2, it

cannot return 0.

2.2 Embedding a ≺-lattice in global states.

In this part, we discuss the structure of a lattice in the state space which, under

proper constraints, allows an algorithm to converge in asynchrony. To describe

the embedding, we deﬁne a total order ≺l; all local states of a node iare totally

ordered under ≺l. Using ≺l, we deﬁne a partial order ≺gamong global states

as follows.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

FullyLattice-LinearAlgorithms∗†‡AryaTanmayGuptaSandeepSKulkarniComputerScienceandEngineering,MichiganStateUniversity{atgupta,sandeep}@msu.eduAbstractLattice-linearitywasintroducedasawaytomodelproblemsusingpredicatesthatinducealatticeamongtheglobalstates(Garg,SPAA2020).Akeypropertyofthepredicaterepre...

展开>> 收起<<

Fully Lattice-Linear Algorithms Arya Tanmay Gupta Sandeep S Kulkarni Computer Science and Engineering Michigan State University.pdf

共40页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Fully Lattice-Linear Algorithms Arya Tanmay Gupta Sandeep S Kulkarni Computer Science and Engineering Michigan State University

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: