An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
2025-04-30
0
0
773.17KB
27 页
10玖币
侵权投诉
An Almost Singularly Optimal Asynchronous
Distributed MST Algorithm
Fabien Dufoulon !
Department of Computer Science, University of Houston, Houston, TX, USA
Shay Kutten !
Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, Haifa,
Israel
William K. Moses Jr. !
Department of Computer Science, University of Houston, Houston, TX, USA
Gopal Pandurangan !
Department of Computer Science, University of Houston, Houston, TX, USA
David Peleg !
Department of Computer Science and Applied Mathematics, Weizmann Institute of Science,
Rehovot, Israel
Abstract
A singularly (near) optimal distributed algorithm is one that is (near) optimal in two criteria, namely,
its time and message complexities. For synchronous
CONGEST
networks, such algorithms are
known for fundamental distributed computing problems such as leader election [Kutten et al., JACM
2015] and Minimum Spanning Tree (MST) construction [Pandurangan et al., STOC 2017, Elkin,
PODC 2017]. However, it is open whether a singularly (near) optimal bound can be obtained for
the MST construction problem in general asynchronous CONGEST networks.
In this paper, we present a randomized distributed MST algorithm that, with high probability,
computes an MST in asynchronous
CONGEST
networks and takes
˜
O
(
D1+ε
+
√n
)time and
˜
O
(
m
)
messages
1
, where
n
is the number of nodes,
m
the number of edges,
D
is the diameter of the network,
and
ε >
0is an arbitrarily small constant (both time and message bounds hold with high probability).
Since
˜
Ω
(
D
+
√n
)and Ω(
m
)are respective time and message lower bounds for distributed MST
construction in the standard
KT0
model, our algorithm is message optimal (up to a
polylog
(
n
)
factor) and almost time optimal (except for a
Dε
factor). Our result answers an open question
raised in Mashregi and King [DISC 2019] by giving the first known asynchronous MST algorithm
that has sublinear time (for all
D
=
O
(
n1−ε
)) and uses
˜
O
(
m
)messages. Using a result of Mashregi
and King [DISC 2019], this also yields the first asynchronous MST algorithm that is sublinear in
both time and messages in the KT1CONGEST model.
A key tool in our algorithm is the construction of a low diameter rooted spanning tree in
asynchronous
CONGEST
that has depth
˜
O
(
D1+ε
)(for an arbitrarily small constant
ε >
0) in
˜
O
(
D1+ε
)time and
˜
O
(
m
)messages. To the best of our knowledge, this is the first such construction
that is almost singularly optimal in the asynchronous setting. This tree construction may be of
independent interest as it can also be used for efficiently performing basic tasks such as verified
broadcast and convergecast in asynchronous networks.
2012 ACM Subject Classification
Theory of computation
→
Distributed algorithms; Mathematics
of computing →Probabilistic algorithms; Mathematics of computing →Discrete mathematics
Keywords and phrases
Asynchronous networks, Minimum Spanning Tree, Distributed Algorithm,
Singularly Optimal
Funding
Fabien Dufoulon: This work was supported in part by NSF grants CCF-1717075, CCF-
1540512, IIS-1633720, and BSF grant 2016419.
1The ˜
Onotation hides a polylog(n)factor and the ˜
Ωnotation hides a 1/polylog(n)factor.
arXiv:2210.01173v1 [cs.DC] 3 Oct 2022
2 An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
Shay Kutten: This work was supported in part by the Bi-national Science Foundation (BSF) grant
2016419 and supported in part by ISF grant 1346/22.
William K. Moses Jr.: This work was supported in part by NSF grants CCF1540512, IIS-1633720,
CCF-1717075, and BSF grant 2016419.
Gopal Pandurangan: This work was supported in part by NSF grants CCF-1717075, CCF-1540512,
IIS-1633720, and BSF grant 2016419.
David Peleg: This work was supported in part by the US-Israel Binational Science Foundation grant
2018043.
1 Introduction
1.1 Background and Motivation
Singularly (near) optimal distributed algorithms are those that are (near) optimal both in
their message complexity and in their time complexity.
2
The current paper is intended as a
step in expanding the study of “which problems admit singularly optimal algorithms” from
the realm of synchronous CONGEST networks to that of asynchronous ones.
An important example of a problem that has been studied in the context of singularly
(near) optimal algorithms is minimum-weight spanning tree (MST) construction. This has
become a rather canonical problem in the sub area of distributed graph algorithms and was
used to demonstrate and study various concepts such as the congested clique model (Lotker
et al. [
40
]), proof labeling schemes (Korman et al. [
36
]), networks with latency and capacity
(Augustine et al. [
3
]), cognitive radio networks (Rohilla et al. [
52
]), distributed applications
of graph sketches (King et al. [
33
]), distributed computing with advice (Fraigniaud et
al. [
22
]), distributed verification and hardness of approximation (Kor et al. [
34
], Korman and
Kutten [
35
] and Das Sarma et al. [
15
]), self-stabilizing algorithms (Gupta and Srimani [
28
]
and many other papers), distributed quantum computing (Elkin et al. [
20
]) and more. The
study of the MST problem in what we now call the
CONGEST
model started more than
forty years ago, see Dalal, and also Spira [13, 14, 56].
The seminal paper of Gallager, Humblet, and Spira (GHS) [
23
] presented a distributed
algorithm for an asynchronous network that constructs an MST in
O
(
nlog n
)time using
O
(
m
+
nlog n
)messages, where
n
and
m
denote the number of nodes and the number of
edges of the network, respectively. The time complexity was later improved by Awerbuch and
by Faloutsos and Moelle to
O
(
n
)[
5
,
21
], while keeping the same order of message complexity.
The message complexity of GHS algorithm is (essentially) optimal, since it can be shown
that for any 1
≤m≤n2
, there exists a graph with Θ(
m
)edges such that Ω(
m
)is a lower
bound on the message complexity of constructing even a spanning tree (even for randomized
algorithms) [
38
].
3
Moreover, the time complexity bound of
O
(
n
)bound is existentially
optimal (in the sense that there exist graphs (of high diameter) for which this is the best
possible). However, the time bound is not optimal if one parameterizes the running time
in terms of the network diameter
D
, which can be much smaller than
n
. In a synchronous
network, Garay, Kutten, and Peleg [
24
] gave the first such distributed algorithm for the MST
problem with running time
˜
O
(
D
+
n0.614
), which was later improved by Kutten and Peleg [
39
]
2
In this paper, henceforth, when we say “near optimal” we mean “optimal up to a
polylog
(
n
)factor”,
where nis the network size.
3
This message lower bound holds in the so-called
KT0
model, which is assumed in this paper. See Section
1.4 for more details.
F. Dufoulon, S. Kutten, W. K. Moses Jr., G. Pandurangan, and D. Peleg 3
to
˜
O
(
D
+
√n
)(again for a synchronous network). However, both these algorithms are not
message-optimal as they exchange O(m+n1.614)and O(m+n1.5)messages, respectively.
Conversely, it was established by Peleg and Rubinovich [
51
] that
˜
Ω
(
D
+
√n
)is a lower
bound on the time complexity of distributed MST construction that applies even to low-
diameter networks (
D
= Ω(
log n
)), and to the synchronous setting. The lower bound of
Peleg and Rubinovich applies to exact, deterministic algorithms. This lower bound was
further extended to randomized (Monte Carlo) algorithms, approximate constructions, MST
verification, and more (see [41, 40, 18, 15]).
Pandurangan, Robinson and Scquizzato [
47
,
49
] showed that MST admits a randomized
singularly near optimal algorithm in synchronous
CONGEST
networks; their algorithm
uses
˜
O
(
m
)messages and
˜
O
(
D
+
√n
)rounds. Subsequently, Elkin [
19
] presented a simpler,
singularly optimal deterministic MST algorithm, again for synchronous networks.
For asynchronous networks, one can obtain algorithms that are separately time optimal
(by combining [
39
] with a synchronizer, see Awerbuch [
4
]) or message optimal [
23
] for the
MST problem, but it is open whether one can obtain an asynchronous distributed MST
algorithm that is singularly (near) optimal. This is one of the main motivations for this work.
An additional motivation is to design tools that can be useful for constructing singularly
optimal algorithms for other fundamental problems in asynchronous networks.
In general, designing singularly optimal algorithms for asynchronous networks seems
harder compared to synchronous networks. In synchronous networks, besides MST con-
struction, singularly (near) optimal algorithms have been shown in recent years for leader
election, (approximate) shortest paths, and several other problems [
38
,
29
]. However, all
these results do not apply to asynchronous networks. Converting synchronous algorithms
to work on asynchronous networks generally incur heavy cost overhead, increasing either
time or message complexity or both substantially. In particular, using synchronizers [
4
] to
convert a singularly optimal algorithm to work in an asynchronous network generally renders
the asynchronous algorithm not singularly optimal. Using a synchronizer can significantly
increase either the time or the message complexity or both far beyond the complexities of
the algorithm presented here. Furthermore, there can be a non-trivial cost associated with
constructing such a synchronizer in the first place.
For example, applying the simple
α
synchronizer [
4
] (which does not require the a
priori existence of a leader or a spanning tree) to the singularly optimal synchronous MST
algorithm of [
47
,
49
] or [
19
] yields an asynchronous algorithm with message complexity of
˜
O
(
m
(
D
+
√n
)) and time complexity of
˜
O
(
D
+
√n
); this algorithm is time optimal, but
not message optimal. Some other synchronizers (see, e.g., Awerbuch and Peleg [
9
]), do
construct efficient synchronizers that can achieve near optimal conversion from synchronous
to asynchronous algorithms with respect to both time and messages, but constructing the
synchronizer itself requires a substantial preprocessing or initialization cost. For example,
the message cost of the synchronizer setup protocol of [9] can be as high as O(mn).
Another rather tempting idea to derive an MST algorithm that would be efficient both in
time and in messages would be to convert a result of Mashreghi and King [
44
] (see also [
43
] and
discussion in Section 1.4), originally designed in the asynchronous
KT1CONGEST
model
4
to the more common
KT0
model assumed here. In particular, they give an asynchronous
MST algorithm that takes
O
(
n
)time and
˜
O
(
n1.5
)messages. Note that one can convert an
algorithm in the
KT1
model to work in the
KT0
model by allowing each node to communicate
4
In
KT1
model it is assumed that nodes know the identities of their neighbors (cf. Section 1.4), unlike
the KT0model, where nodes don’t have that knowledge.
4 An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
with all its neighbors in one round; this takes an additional
˜
O
(
m
)messages. Hence, with such
a conversion the message complexity of the above algorithm would be essentially optimal
(i.e.,
˜
O
(
m
)), but the time complexity would be
O
(
n
)which is only existentially optimal, and
can be significantly higher than the lower bound of
˜
O
(
D
+
√n
). In fact, as we will discuss
later, our result answers an open question posed in [
44
] and gives MST algorithms with
improved bounds in asynchronous KT1model (cf. Section 1.3).
Instead of using a synchronizer, a better approach might be to design an algorithm
directly for an asynchronous network. As an example, consider the fundamental leader
election problem, which is simpler than the MST construction problem. Till recently, a
singularly optimal asynchronous leader election algorithm was not known. Applying a
synchronizer to known synchronous singularly optimal leader election algorithms does not
yield singularly optimal asynchronous algorithms. For example, applying the simple
α
synchronizer to the singularly optimal synchronous leader election algorithm of [
38
] yields an
asynchronous algorithm with message complexity of
O
(
mD log n
)and time complexity of
O
(
D
); this algorithm is not message optimal, especially for large diameter networks. Other
synchronizers such as
β
and
γ
of [
4
] and that of [
9
], require the a priori existence of a leader
or a spanning tree and hence cannot be used for leader election. The work of Kutten et
al. [
37
] presented a singularly (near) optimal leader election for asynchronous networks that
takes ˜
O(m)messages and ˜
O(D)time.5That algorithm did not use a synchronizer and was
directly designed for an asynchronous network. The leader election algorithm of [
37
] is a
useful subroutine in our MST algorithm.
1.2 The Distributed Computing Model
The distributed network is modeled as an arbitrary undirected connected weighted graph
G
= (
V, E, w
), where the node set
V
represent the processors, the edge set
E
represents
the communication links between them, and
w
(
e
)is the weight of edge
e∈E
.
D
denotes
the hop-diameter (that is, the unweighted diameter) of
G
, in this paper, diameter always
means hop-diameter. We also assume that the weights of the edges of the graph are all
distinct. This implies that the MST of the graph is unique. (The definitions and the results
generalize readily to the case where the weights are not necessarily distinct.) We make
the common assumption that each node has a unique identity (this is not essential, but
simplifies presentation), and at the beginning of computation, each node
v
accepts as input
its own identity number (ID) and the weights of the edges incident to it. Thus, a node has
only local knowledge. We assume that each node has ports (each port having a unique port
number); each incident edge is connected to one distinct port. A node does not have any
initial knowledge of the other endpoint of its incident edge (the identity of the node it is
connected to or the port number that it is connected to). This model is referred to as the
clean network model in [
50
] and is also sometimes referred to as the
KT0
model, i.e., the initial
(K)nowledge of all nodes is restricted (T)ill radius 0 (i.e., just the local knowledge) [
50
]. The
KT0
model is extensively used in distributed computing literature including MST algorithms
(see e.g., [
50
,
48
] and the references therein). While we design an algorithm for the
KT0
model, our algorithm also yields an improvement in the
KT1
model [
7
,
50
] where each node
has an initial knowledge of the identities of its neighbors.
We assume that nodes have knowledge of
n
(in fact a constant factor approximation of
n
5
This algorithm is singularly near optimal, since Ω(
m
)and Ω(
D
)are message and lower bounds for
leader election even for randomized Monte Carlo algorithms [38].
F. Dufoulon, S. Kutten, W. K. Moses Jr., G. Pandurangan, and D. Peleg 5
is sufficient), the network size. We note that quite a few prior distributed algorithms require
knowledge of
n
, see e.g. [
6
,
53
,
2
,
37
]. We assume that processors can access private unbiased
random bits.
We assume the standard asynchronous
CONGEST
communication model [
50
], where
messages (each message is of
O
(
log n
)bits) sent over an edge incur unpredictable but finite
delays, in an error-free and FIFO manner (i.e., messages will arrive in sequence). As is
standard, it is assumed that a message takes at most one time unit to be delivered across
an edge. Note that this is just for the sake of the analysis of time complexity, and does
not imply that nodes know an upper bound on the delay of any message. As usual, local
computation within a node is assumed to be instantaneous and free; however, our algorithm
will involve only lightweight local computations.
We assume an adversarial wake-up model, where node wake-up times are scheduled by
an adversary (who may decide to keep some nodes dormant) which is standard in prior
asynchronous protocols (see [
1
,
23
,
55
]). Nodes are initially asleep, and a node enters the
execution when it is woken up by the environment or upon receiving messages from other
nodes.6
The time complexity is measured from the moment the first node wakes up. The adversary
wakes up nodes and delays each message in an adaptive fashion, i.e., when the adversary
makes a decision to wake up a node or delay a message, it has access to the results of all
previous coin flips. In the asynchronous setting, once a node enters execution, it performs
all the computations required of it by the algorithm, and sends out messages to neighbors
as specified by the algorithm. At the end of the computation, we require each node to
know which of its incident edges belong to the MST. When we say that an algorithm has
termination detection, we mean that all nodes detect termination, i.e., each node detects
that its own participation in the algorithm is over.
1.3 Our Contributions
Almost Singularly Optimal Asynchronous MST Algorithm.
Our main contribution
is a randomized distributed MST algorithm that, with high probability, computes an MST
in asynchronous
CONGEST
networks and takes
˜
O
(
D1+ε
+
√n
)time and
˜
O
(
m
)messages,
where
n
is the number of nodes,
m
the number of edges,
D
is the diameter of the network,
and
ε >
0is an arbitrarily small constant (both time and message bounds hold with high
probability) (cf. Theorem 19). Since
˜
Ω
(
D
+
√n
)and Ω(
m
)are respective time and message
lower bounds for distributed MST construction in the
KT0
model, our algorithm is message
optimal (up to a polylog(n)factor) and almost time optimal (except for a ˜
O(Dε)factor).
Asynchronous MST in KT1in Sublinear Messages and Time.
Our result answers
an open problem raised in Mashregi and King [
44
] (see also [
45
,
43
]). They ask if there
exists an asynchronous MST algorithm that takes sublinear time if the diameter of the
network is low, and has
˜
O
(
m
)message complexity. They remark that if such an algorithm
exists, then it would improve their result giving better bounds for asynchronous MST in
KT1CONGEST
. Our result answers their question in the affirmative by giving the first
known asynchronous MST algorithm that has sublinear time (for all
D
=
O
(
n1−δ
), where
6
Although standard, the adversarial wake up model, in our setting, is not more difficult compared to the
alternative simultaneous wake up model where all nodes are assumed to be awake at the beginning of
the computation. Indeed, in the adversarial wake up model, awake nodes can broadcast (by simply
flooding) a “wake up” message which can wake up all nodes; this takes only
O
(
m
)messages and
O
(
D
)
time and hence within the singularly optimal bounds.
摘要：
展开>>
收起<<
AnAlmostSingularlyOptimalAsynchronousDistributedMSTAlgorithmFabienDufoulon!DepartmentofComputerScience,UniversityofHouston,Houston,TX,USAShayKutten!FacultyofIndustrialEngineeringandManagement,Technion-IsraelInstituteofTechnology,Haifa,IsraelWilliamK.MosesJr.!DepartmentofComputerScience,UniversityofH...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
分类：图书资源
价格：10玖币
属性：27 页
大小：773.17KB
格式：PDF
时间：2025-04-30
作者详情
-
Optimal Persistent Monitoring of Mobile Targets in One Dimension Jonas Hall1 Sean Andersson12 Christos G. Cassandras13 Abstract This work shows the existence of opti-10 玖币0人下载
-
Optimal metabolic strategies for microbial growth in stationary random environments Anna Paola Muntoni and Andrea De Martino10 玖币0人下载
相关内容
-
行政事业单位内部控制报告-关于印发编外聘用人员管理制度和编外聘用人员年度考核制度
分类：办公文档
时间：2025-03-03
标签：无
格式：DOC
价格：5.9 玖币
-
行政事业单位内部控制报告-风险评估管理制度
分类：办公文档
时间：2025-03-03
标签：无
格式：DOCX
价格：5.9 玖币
-
行政事业单位内部控制报告-采购管理内部控制制度
分类：办公文档
时间：2025-03-03
标签：无
格式：DOCX
价格：5.9 玖币
-
行政事业单位内部控制报告-部署单位内部控制专题培训和风险评估工作会议纪要
分类：办公文档
时间：2025-03-03
标签：无
格式：DOC
价格：5.9 玖币
-
行政事业单位内部控制报告-关键岗位轮岗及专项审计制度
分类：办公文档
时间：2025-03-03
标签：关键
格式：DOCX
价格：5.9 玖币
渝公网安备50010702506394
