ASelf-StabilizingAlgorithmforMaximalMatchinginAnonymousNetworks资源-CSDN文库

需积分: 9 44 浏览量 2016-12-30 11:38:20 上传评论收藏 247KB PDF 举报

资源推荐

资源详情

资源评论

December 9, 2016 15:13 PPL S012962641650016X page 1

Parallel Processing Letters

Vol. 26, No. 4 (2016) 1650016 (17 pages)

 World Scientiﬁc Publishing Company

DOI: 10.1142/S012962641650016X

A Self-Stabilizing Algorithm for Maximal Matching

in Anonymous Networks

Johanne Cohen

LRI, CNRS, Universit´e Paris Sud, Universit´e Paris-Saclay, Franc e

johanne.cohen@lri.fr

Jonas Lef`evre

LIX, CNRS,

Ecole Polytechnique, Universit´e Paris-Saclay, France

jlefevre@lix.polytechnique.fr

Khaled Maˆamra

∗

, Laurence Pilard

†

and Devan Sohier

‡

LI-PaRAD, Universit´e Versailles-St. Quentin, Universit´e Paris-Saclay, France

∗

khaled.maamra@uvsq.fr

†

laurence.pilard@uvsq.fr

‡

devan.sohier@uvsq.fr

Received January 2014

Revised July 2016

Communicated by P. Spirakis

Published 21 December 2016

ABSTRACT

We propose a self-stabilizing algorithm for computing a maximal matching in an anony-

mous network. The complexity is O(n

) moves with high probability, under the ad-

versarial distributed daemon. Among all adversarial distributed daemons and with the

anonymous assumption, our algorithm provides the best known complexity. Moreover,

the previous best known algorithm working under the same daemon and using identity

has a O(m) complexity leading to the same order of growth than our anonymous al-

gorithm. Finally, we do not make the common assumption that a node can determine

whether one of its neighbors points to it or to another node, and still we present a

solution with the same asymptotic behavior.

Keywords: Randomized algorithm; self-stabilization; maximal matching; anonymous

network.

1. Introduction

A matching M in a graph is a set of edges without common vertices. A matching

is maximal if no proper superset of M is also a matching. Matching problems have

∗

This work was partially funding by DIGITEO, project RI2Aˆ2.

1650016-1

Parallel Process. Lett. 2016.26. Downloaded from www.worldscientific.com

by RUTGERS UNIVERSITY on 12/27/16. For personal use only.

December 9, 2016 15:13 PPL S012962641650016X page 2

J. Cohen et al.

received a lot of attention in diﬀerent areas. In context of dynamic load balancing,

job scheduling in parallel and distributed systems can be solved by algorithms

using a maximal matching set of communication links [1, 8] as a basic and black-

box function. In this paper, we present a self-stabilizing algorithm for ﬁnding a

maximal matching in anonymous network.

Self-stabilizing algorithms [3, 4], are distributed algorithms that recover after

any transient failure without external intervention, i.e., starting from any arbitrary

initial state, the system eventually converges to a correct behavior. The environment

of self-stabilizing algorithms is modeled by the notion of daemon.Adaemon allows

to capture the diﬀerent behaviors of such algorithms accordingly to the execution

environment. Two major types of daemons exist: the sequential and the distributed

ones. The se quential daemon means that exactly one eligible process is scheduled

for execution at a time. The distributed daemon means that any non empty subset

of eligible processes is scheduled for execution at a time. In an orthogonal way, a

daemon can be fair (meaning that every eligible process is eventually scheduled

for execution) or adversarial (meaning that the daemon only guarantees global

progress, i.e., at any time, at least one eligible process is scheduled for execution).

We can compare the strength of daemons by comparing the possible executions un-

der each daemon. For instance, the adversarial sequential daemon is more powerful

than the fair sequential one since every execution that is possible under the fair

sequential daemon is also possible under the adversarial sequential one, but there

exists some executions that are possible under the adversarial sequential daemon

but not under the fair sequential daemon. As a matter of fact, the only daemon

that does not give any constraint on the execution is the adversarial distributed

one. Thus this daemon is the most powerful among all daemons and then it is more

diﬃcult to design a self-stabilizing algorithm under this daemon than under any

other daemons.

In this paper we provide a self-stabilizing algorithm called AnonyMatch,that

is a randomized algorithm for ﬁnding a maximal matching in an anonymous net-

work. We show the algorithm stabilizes in O(n

) moves with high probability un-

der the adversarial distributed daemon. Among all algorithms for adversarial dis-

tributed daemons and under the anonymous assumption, our algorithm provides

the best complexity as far as we know. Moreover, the previous best known algo-

rithm working under the same daemon and using identities has a O(m) complexity

leading to the same order of complexity than our anonymous algorithm.

AnonyMatch is our main contribution. We provide other results concerning

the anonymous assumption. In all previous papers dealing with self-stabilizing max-

imal matching in anonymous systems [2, 9, 11, 13, 14], authors make the assumption

that nodes can determine whether its neighbor points to itself or to some other node.

But, this assumption is not that simple to achieve in anonymous systems since the

usual way to do it is using identiﬁers. In this paper, we investigate this question and

present a classical algorithm [4], called LinkN ame, that gives unique local names

to all neighbors of a node in an anonymous system. This algorithm is deﬁned under

1650016-2

Parallel Process. Lett. 2016.26. Downloaded from www.worldscientific.com

by RUTGERS UNIVERSITY on 12/27/16. For personal use only.

December 9, 2016 15:13 PPL S012962641650016X page 3

A Self-Stabilizing Algorithm for Maximal Matching in Anonymous Networks

the link-register model and allows to build a system in which this assumption holds.

Then we give a slight modiﬁcation of AnonyMatch, called AnonyMatch2, lead-

ing to a solution that does not need this assumption anymore. AnonyMatch is

deﬁned under the state model while its modiﬁed version has to be speciﬁed un-

der the link-register model. We ﬁnally show that this method can be used in all

previous anonymous matching algorithms, leading to the following conclusion: the

assumption that a node can know if a neighbor points to itself or to some other

node in an anonymous system is meaningful.

In Section 2, we present related works. In Section 3, we give the model

used in this paper. In particular we present the state model used in algorithm

AnonyMatch and the link-register model used in AnonyMatch2. In Section 4,

we present AnonyMatch with its complexity computation. Finally, the issue of

determining if an adjacent node points to oneself is investigated in Section 5.

2. Related works

Several self-stabilizing algorithms have been proposed to compute maximal match-

ing in unweighted or weighted general graphs. For an unweighted graph, Hsu and

Huang [14] gave the ﬁrst algorithm and proved a bound of O(n

)onthenum-

ber of moves under a sequential adversarial daemon. The complexity analysis is

completed by Hedetniemi et al. [13]toO(m) moves. Manne et al. [17]presenteda

self-stabilizing algorithm for ﬁnding a maximal matching. The complexity of this

algorithm is proved to be O(m) moves under a distributed adversarial daemon. In

a weighted graph, Manne and Mjelde [16] presented the ﬁrst self-stabilizing algo-

rithm for computing a weighted matching of a graph with an 1/2-approximation of

the optimal solution. They established their algorithm stabilizes after at most an

exponential number of moves under any adversarial daemon (i.e., sequential or dis-

tributed). Turau and Hauck [20] gave a modiﬁed version of the previous algorithm

that stabilizes after O(nm) moves under any adversarial daemon.

All algorithms presented above, but the Hsu and Huang [14], assume nodes

have unique identity. The Hsu and Huang’s algorithm is the ﬁrst one working in an

anonymous network. This algorithm operates under a sequential daemon (fair or

adversarial) in order to achieve symmetry breaking. Indeed, Manne et al. [17]proved

that in an anonymous general network there exists no deterministic self-stabilizing

solution to the maximal matching problem under a synchronous daemon. This is

a general result that holds whatever the communication and atomicity model (the

state model with guarded rule atomicity or the link-register model with read/write

atomicity). Goddard et al. [9] proposed a generalized scheme that can convert any

anonymous and deterministic algorithm that stabilizes under an adversarial se-

quential daemon into a randomized one that stabilizes under a distributed daemon,

using only constant extra space and without identity. The expected slowdown is

bounded by O(n

) moves. The composition of these two algorithms can compute a

maximal matching in O(mn

) expected moves in an anonymous network under a

distributed daemon.

1650016-3

Parallel Process. Lett. 2016.26. Downloaded from www.worldscientific.com

by RUTGERS UNIVERSITY on 12/27/16. For personal use only.

剩余16页未读，继续阅读

评论收藏

内容反馈

hekang01

粉丝: 1
资源: 3

A Self-Stabilizing Algorithm for Maximal Matching in Anonymous N...

最新资源

A Self-Stabilizing Algorithm for Maximal Matching in Anonymous N...

Stabilization analysis and modified KdV equation of a car-following model with consideration of self-stabilizing control in historical traffic data

帕金森氏症患者的自稳定汤匙-项目开发

网络化系统的事件触发控制研究.zip

Stabilizing an Tracking Control of Multiple Pendulum-Cart Systems over a Shared Wireless Network

TOWARDS STABILIZING BATCH STATISTICS

40篇ICLR2020计算机视觉开源论文合集.zip

自稳定的分布式事务内存模型及算法.pdf

Stabilizing-GANs-with-Octave-Convolutions:论文代码

Stabilizing High-Dimensional Prediction Models.pdf

不可压缩Stokes流动的PSPG无网格法 (2007年)

Design of digital Pound-Drever-Hall frequency stabilizing system for two-cavity dual-frequency Nd:YAG laser

Frequency stabilization of a 214.5-nm ultraviolet laser

Simulation of stabilizing process of dielectric nanoparticle in optical trap using counter-propagating pulsed laser beams

Designing Control Loops for Linear and Switching Power Supplies

Asynchronous Methods for Deep Reinforcement Learning

Stabilization of probabilistic Boolean networks via pinning control strategy

基于Arduino的MPU6050 DMP6自稳定平台

Subnatural-Linewidth Polarization-Entangled Photon Pairs with Controllable Temporal Length

The role of humic acid in stabilizing fullerene (C60) suspension

Visual Media Processing Using MATLAB Beginner's Guide

Nonlinear Model Predictive Control For Autonomous Vehicles

lcd.zip_Delay-dependent_T-S FUZZY_T-S with time delay_time-depen

Intelligent Adaptive Control: Industrial Applications

Computing and Combinatorics

最新资源