SELF-STABILIZATION AND BYZANTINE TOLERANCE FOR MAXIMAL INDEPENDENT SET A P REPRINT

2025-04-26 0 0 374.76KB 17 页 10玖币

侵权投诉

SELF-STABILIZATION AND BYZANTINE TOLERANCE FOR

MAXIMAL INDEPENDENT SET

A PREPRINT

Johanne Cohen

LISN-CNRS, Universit´

e Paris-Saclay, France

johanne.cohen@lri.fr

Laurence Pilard

PaRAD, UVSQ, , Universit´

e Paris-Saclay, France

valentin.dardilhac@ens-paris-saclay.fr

Franc¸ois Pirot

LISN-CNRS, Universit´

e Paris-Saclay, France

Francois.Pirot@lri.fr

Jonas S´

enizergues

LISN-CNRS, Universit´

e Paris-Saclay, France

Jonas.Senizergues@lri.fr

1 Introduction

Maximal independent sets have received a lot of attention in different areas. For instance, in wireless networks,

the maximum independent sets can be used as a black box to perform communication (to collect or to broadcast

information) (see [20, 9] for example). In self-stabilizing distributed algorithms, this problem is also a fundamental

tool to transform an algorithm from one model to another [13, 29].

An independent set Iin a graph is a set of vertices such that no two of them form an edge in the graph. It is called

maximal when it is maximal inclusion-wise (in which case it is also a minimal dominating set).

The maximal independent set (MIS) problem has been extensively studied in parallel and distributed settings, following

the seminal works of [1, 19, 21]. Their idea is based on the fact that a node joins the “MIS under construction” S

according to the neighbors: node vjoins the set Sif it has no neighbor in S, and it leaves the set Sif at least one of its

neighbors is in S. Most algorithms in the literature, including ours, are based on this approach.

The MIS problem has been extensively studied in the LOCAL model, [10, 23, 5] for instance (a synchronous, message-

passing model of distributed computing in which messages can be arbitrarily large) and in the CONGEST model [22]

(synchronous model where messages are O(log n)bits long). In the LOCAL model, Barenboim et al. [3] focus on

identiﬁed system and gave a self-stabilizing algorithm producing a MIS within O(∆ + log∗n)rounds. Balliu et

al [2] prove that the previous algorithm [3] is optimal for a wide range of parameters in the LOCAL model. In the

CONGEST model, Ghaffari et al. [11] prove that there exists a randomized distributed algorithm that computes a

maximal independent set in O(log ∆ ·log log n+ log6log n)rounds with high probability.

Self-stabilizing algorithms for maximal independent set have been designed in various models (anonymous net-

work [25, 29, 28] or not [12, 16]). Up to our knowledge, Shukla et al. [25] present the ﬁrst algorithm designed for

ﬁnding a MIS in a graph using self-stabilization paradigm for anonymous networks. Some other self-stabilizing works

deal with this problem assuming identiﬁers: with a synchronous daemon [12] or distributed one [16]. These two works

require O(n2)moves to converge. Turau [27] improves these results to O(n)moves under the distributed daemon.

Recently, some works improved the results in the synchronous model. For non-anonymous networks, Hedetniemi [15]

designed a self-stabilization algorithm for solving the problem related to dominating sets in graphs in particular for

a maximal independent set which stabilizes in O(n)synchronous rounds. Moreover, for anonymous networks, Tu-

rau [28] design some Randomized self-stabilizing algorithms for maximal independent set w.h.p. in O(log n)rounds.

See the survey [14] for more details on MIS self-stabilizing algorithms.

Some variant of the maximal independent set problem have been investigated, as for example the 1-maximal in-

dependent set problem [26, 24] or Maximal Distance-kIndependent Set [4, 17]. Tanaka et al [26] designed a silent

arXiv:2210.06116v3 [cs.DC] 10 Jun 2024

Self-Stabilization and Byzantine Tolerance for Maximal Independent Set A PREPRINT

self-stabilizing 1-MIS algorithm under the weakly-fair distributed daemon for any identiﬁed network in O(nD)rounds

(where Dis a diameter of the graph).

In this paper, we focus on the construction of a MIS handling both transient and Byzantine faults. On one side,

transient faults can appear in the whole system, possibly impacting all nodes. However, these faults are not permanent,

thus they stop at some point of the execution. Self-stabilization [7] is the classical paradigm to handle transient faults.

Starting from any arbitrary conﬁguration, a self-stabilizing algorithm eventually resumes a correct behavior without

any external intervention. On the other side, (permanent) Byzantine faults [18] are located on some faulty nodes and

so the faults only occur from them. However, these faults can be permanent, i.e., they could never stop during the

whole execution.

In a distributed system, multiple processes can be active at the same time, meaning they are in a state where they could

make a computation. The deﬁnition of self-stabilizing algorithm is centered around the notion of daemon, which

captures the ways the choice of which process to schedule for the next time step by the execution environment can be

made. Two major types of daemon are the sequential and the distributed ones. A sequential daemon only allows one

process to be scheduled for a given time step, while a distributed daemon allows the execution of multiple processes at

the same time. Daemons can also be fair when they have to eventually schedule every process that is always activable,

or adversarial when they are not fair. As being distributed instead of sequential (or adversarial instead of fair) only

allows for more possibilities of execution, it is harder to make an algorithm with the assumption of a distributed (resp.

adversarial) daemon than with the assumption of a sequential (resp. fair) daemon.

We introduce the possibility that some nodes, that we will call Byzantine nodes, are not following the rules of the

algorithm, and may change the values of their attributes at any time step. Here, if we do not work under the assumption

of a fair daemon, one can easily see that we cannot guarantee the convergence of any algorithm as the daemon could

choose to always activate alone the same Byzantine node, again and again.

Under the assumption of a fair daemon, there is a natural way to express complexity, not in the number of moves

performed by the processes, but in the number of rounds, where a round captures the idea that every process that

wanted to be activated at the beginning of the round has either been activated or changed its mind. We give a self-

stabilizing randomized algorithm that, in an anonymous network (which means that processes do not have unique

identiﬁers to identify themselves) with Byzantine nodes under the assumption of a distributed fair daemon, ﬁnds a

maximal independent set of a superset of the nodes at distance 3or more from Byzantine nodes. We show that the

algorithm stabilizes in O(∆n)rounds w.h.p., where nis the size and ∆is the diameter of the underlying graph.

In this paper, we ﬁrst present the model (Section 2).

Then, we give a self-stabilizing randomized algorithm with Byzantine nodes under the fair daemon (Section 3), which

converges in O(∆n)rounds.

Then, in the last part, we give a self-stabilizing randomized algorithm that ﬁnds a maximal independent set in an

anonymous network, under the assumption of a distributed adversarial daemon. We show that our algorithm converge

in O(n2)moves with high probability.

2 Model

A system consists of a set of processes where two adjacent processes can communicate with each other. The com-

munication relation is represented by a graph G= (V, E)where Vis the set of the processes (we will call node any

element of Vfrom now on) and Erepresents the neighbourhood relation between them, i.e.,uv ∈Ewhen uand v

are adjacent nodes. By convention we write |V|=nand |E|=m. If uis a node, N(u) = {v∈V|uv ∈E}denotes

the open neighbourhood, and N[u] = N(u)∪ {u}denotes the closed neighbourhood. We note deg(u) = |N(u)|and

∆ = max {deg(u)|u∈V}.

We assume the system to be anonymous meaning that a node has no identiﬁer. We use the state model, which means

that each node has a set of local variables which make up the local state of the node. A node can read its local variables

and all the local variables of its neighbours, but can only rewrite its own local variables. A conﬁguration is the value

of the local states of all nodes in the system. When uis a node and xa local variable, the x-value of uin conﬁguration

γis the value xγ

An algorithm is a set of rules, where each rule is of the form ⟨guard⟩→⟨command⟩and is parametrized by the

node where it would be applied. The guard is a predicate over the variables of the said node and its neighbours. The

command is a sequence of actions that may change the values of the node’s variables (but not those of its neighbours).

A rule is enabled on a node uin a conﬁguration γif the guard of the rule holds on uin γ. A node is activable on a

Self-Stabilization and Byzantine Tolerance for Maximal Independent Set A PREPRINT

conﬁguration γif at least one rule is enabled on u. We call move any ordered pair (u, r)where uis a node and ris a

rule. A move is said possible in a given conﬁguration γif ris enabled on uin γ.

The activation of a rule on a node may only change the value of variables of that speciﬁc node, but multiple moves

may be performed at the same time, as long as they act on different nodes. To capture this, we say that a set of moves t

is valid in a conﬁguration γwhen it is non-empty, contains only possible moves of γ, and does not contain two moves

concerning the same node. Then, a transition is a triplet (γ, t, γ′)such that: (i) tis a valid set of moves of γand (ii) γ′

is a possible conﬁguration after every node uappearing in tperformed simultaneously the code of the associated rule,

beginning in conﬁguration γ. We will write such a triplet as γt

−→ γ′. We will also write γ→γ′when there exists a

transition from γto γ′.V(t)denotes the set of nodes that appear as ﬁrst member of a couple in t.

We say that a rule ris executed on a node uin a transition γt

−→ γ′(or equivalently that the move (u, r)is executed in

γt

−→ γ′) when the node uhas performed the rule rin this transition, that is when (u, r)∈t. In this case, we say that

uhas been activated in that transition. Then, an execution is an alternate sequence of conﬁgurations and move sets

γ0, t1, γ1···ti, γi,··· where (i) the sequence either is inﬁnite or ﬁnishes by a conﬁguration and (ii) for all i∈Nsuch

that it is deﬁned, (γi, ti+1, γi+1)is a transition. We will write such an execution as γ0

−→ γ1··· ti

−→ γi··· When the

execution is ﬁnite, the last element of the sequence is the last conﬁguration of the execution. An execution is maximal

if it is inﬁnite, or it is ﬁnite and no node is activable in the last conﬁguration. It is called partial otherwise. We say

that a conﬁguration γ′is reachable from a conﬁguration γif there exists an execution starting in conﬁguration γthat

leads to conﬁguration γ′. We say that a conﬁguration is stable if no node is activable in that conﬁguration.

The daemon is the adversary that chooses, from a given conﬁguration, which nodes to activate in the next transition.

Two types are used: the adversarial distributed daemon that allows all possible executions and the fair distributed

daemon that only allows executions where nodes cannot be continuously activable without being eventually activated.

Given a speciﬁcation and Lthe associated set of legitimate conﬁguration,i.e., the set of the conﬁgurations that verify

the speciﬁcation, a probabilistic algorithm is self-stabilizing when these properties are true: (correctness) every con-

ﬁguration of an execution starting by a conﬁguration of Lis in Land (convergence) from any conﬁguration, whatever

the strategy of the daemon, the resulting execution eventually reaches a conﬁguration in Lwith probability 1.

The time complexity of an algorithm that assumes the fair distributed daemon is given as a number of rounds. The

concept of round was introduced by Dolev et al. [8], and reworded by Cournier et al. [6] to take into account activable

nodes. We quote the two following deﬁnitions from Cournier et al. [6]: “

Deﬁnition 1 We consider that a node uexecutes a disabling action in the transition γ1→γ2if u(i) is activable in

γ1, (ii) does not execute any rule in γ1→γ2and (iii) is not activable in γ2.

The disabling action represents the situation where at least one neighbour of uchanges its local state in γ1→γ2, and

this change effectively made the guard of all rules of ufalse in γ2. The time complexity is then computed capturing

the speed of the slowest node in any execution through the round deﬁnition [8].

Given an execution E, the ﬁrst round of E(let us call it R1) is the minimal preﬁx of Econtaining the execution of one

action (the execution of a rule or a disabling action) of every activable nodes from the initial conﬁguration. Let E′be

the sufﬁx of Esuch that E=R1E′. The second round of Eis the ﬁrst round of E′, and so on.”

Observe that Deﬁnition ?? is equivalent to Deﬁnition ??, which is simpler in the sense that it does not refer back to

the set of activable nodes from the initial conﬁguration of the round.

Let Ebe an execution. A round is a sequence of consecutive transitions in E. The ﬁrst round begins at the beginning of

E; successive rounds begin immediately after the previous round has ended. The current round ends once every node

u∈Vsatisﬁes at least one of the following two properties: (i) uhas been activated in at least one transition during

the current round or (ii) uhas been non-activable in at least one conﬁguration during the current round.

Our ﬁrst algorithm is to be executed in the presence of Byzantine nodes; that is, there is a subset B⊆Vof adversarial

nodes that are not bound by the algorithm. Byzantine nodes are always activable. An activated Byzantine node is free

to update or not its local variables. Finally, observe that in the presence of Byzantine nodes all maximal executions are

inﬁnite. We denote by d(u, B)the minimal (graph) distance between node uand a Byzantine node, and we deﬁne for

i∈N:Vi={u∈V|d(u, B)> i}. Note that V0is exactly the set of non-Byzantines nodes, and that Vi+1 is exactly

the set of nodes of Viwhose neighbours are all in Vi.

When i, j are integers, we use the standard mathematical notation for the integer segments: Ji, jKis the set of integers

that are greater than or equal to iand smaller than or equal to j(i.e. Ji, jK= [i, j]∩Z={i, ··· , j}). Rand(x)with

x∈[0,1] represents the random function that outputs 1with probability x, and 0otherwise.

Self-Stabilization and Byzantine Tolerance for Maximal Independent Set A PREPRINT

3 With Byzantines Nodes under the Fair Daemon

3.1 The algorithm

The algorithm builds a maximal independent set represented by a local variable s. The approach of the state of the

art is the following: when two nodes are candidates to be in the independent set, then a local election decides who

will remain in the independent set. To perform a local election, the standard technique is to compare the identiﬁers of

nodes. Unfortunately, this mechanism is not robust to the presence of Byzantine nodes.

Keeping with the approach outlined above, when a node uobserves that its neighbours are not in (or trying to be in)

the independent set , the non-Byzantine node decides to join it with a certain probability. The randomization helps to

reduce the impact of Byzantine nodes. The choice of probability should reduce the impact of Byzantine nodes while

maintaining the efﬁciency of the algorithm.

Algorithm 1 Any node uhas two local variables su∈ {⊥,⊤} and xu∈Nand may make a move according to one

of the following rules:

(Refresh) xu̸=|N(u)| → xu:= |N(u)|(= deg(u))

(Candidacy?) (xu=|N(u)|)∧(su=⊥)∧(∀v∈N(u), sv=⊥)→

if Rand(1

1+max({xv|v∈N[u]})) = 1 then su:= ⊤

(Withdrawal) (xu=|N(u)|)∧(su=⊤)∧(∃v∈N(u), sv=⊤)→su:= ⊥

Observe since we assume an anonymous setting, the only way to break symmetry is randomisation. The value of the

probabilities for changing local variable must carefully be chosen in order to reduce the impact of the Byzantine node.

A node joins the MIS with a probability 1

1+max({xv|v∈N[u]}). The idea to ask the neighbours about their own number

of neighbours (through the use of the xvariable) to choose the probability of a candidacy comes from the mathematical

property ∀k∈N,(1 −1

k+1 )k> e−1, which will allow to have a good lower bound for the probability of the event

“some node made a successful candidacy, but none of its neighbours did”.

3.2 Speciﬁcation

Since Byzantine nodes are not bound to follow the rules, we cannot hope for a correct solution in the entire graph.

What we wish to do is to ﬁnd a solution that works when we are far enough from the Byzantine nodes. One could

think about a ﬁxed containment radius around Byzantine nodes, but as we can see later this is not as simple, and it

does not work with our approach.

Let us deﬁne on any conﬁguration γthe following set of nodes, that represents the already built independent set:

Iγ={u∈V1|(sγ

u=⊤)∧ ∀v∈N(u), sγ

v=⊥}

We say that a node is locally alone if it is candidate to be in the independent set (i.e. its s-value is ⊤) while none of its

neighbours are. In conﬁguration γ,Iγis the set of all locally alone nodes of V1.

Deﬁnition 2 A conﬁguration is said legitimate when Iγis a maximal independent set of V2∪Iγ.

3.2.1 An example:

Figure 1 gives an example of an execution of the algorithm. Figure 1a depicts a network in a given conﬁguration. The

symbol drawn above the node represents the local variable s. Each local variable xcontains the degree of its associated

node. Byzantine node is shown with a square.

In the initial conﬁguration, nodes v1and v2are in the independent set, and then are activable for Withdrawal. In the

ﬁrst step, the daemon activates v1(Withdrawal) and v2(Withdrawal) leading to conﬁguration γ1(Fig. 1b). In the

second step, the daemon activates v1(Candidacy?). Node v1randomly decides whether to set sv1:= ⊤leading to

conﬁguration γ2(Fig. 1c), or sv1:= ⊥leading to conﬁguration γ1(Fig. 1b). Assume that v1chooses sv1:= ⊤. At

this moment, node v1is “locally alone” in the independent set. In the third step, the daemon activates band bmakes a

Byzantine move setting sb:= ⊤, leading to conﬁguration γ3(Fig. 1d).

In the fourth step, the daemon activates v1(Withdrawal) and bthat sets sb:= ⊥. The conﬁguration is now the same

as the ﬁrst conﬁguration (Fig. 1b). The daemon is assumed to be fair, so nodes v2and v3need to be activated before

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

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

10 玖币 0人已下载

立即下载

摘要：

SELF-STABILIZATIONANDBYZANTINETOLERANCEFORMAXIMALINDEPENDENTSETAPREPRINTJohanneCohenLISN-CNRS,Universit´eParis-Saclay,Francejohanne.cohen@lri.frLaurencePilardPaRAD,UVSQ,,Universit´eParis-Saclay,Francevalentin.dardilhac@ens-paris-saclay.frFranc¸oisPirotLISN-CNRS,Universit´eParis-Saclay,FranceFrancois...

展开>> 收起<<

SELF-STABILIZATION AND BYZANTINE TOLERANCE FOR MAXIMAL INDEPENDENT SET A P REPRINT.pdf

共17页,预览4页

还剩页未读，继续阅读

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

SELF-STABILIZATION AND BYZANTINE TOLERANCE FOR MAXIMAL INDEPENDENT SET A P REPRINT

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: