A population protocol
stably elects a leader
if, for all
n
, starting from an initial configuration with
n
agents each in an identical state, with probability 1 it reaches a configuration
y
that is
...correct
(exactly one agent is in a special leader state
ℓ
) and
stable
(every configuration reachable from
y
also has a single agent in state
ℓ
). We show that any population protocol that stably elects a leader requires
Ω
(
n
)
expected “parallel time”—
Ω
(
n
2
)
expected total pairwise interactions—to reach such a stable configuration. Our result also informs the understanding of the time complexity of chemical self-organization by showing an essential difficulty in generating exact quantities of molecular species quickly.
Given any multiset
F
of points in the Euclidean plane and a set
R
of robots such that
|
R
|
=
|
F
|
, the Arbitrary Pattern Formation (
APF
) problem asks for a distributed algorithm that moves ...robots so as to reach a configuration similar to
F
. Similarity means that robots must be disposed as
F
regardless of translations, rotations, reflections, uniform scalings. Initially, each robot occupies a distinct position. When active, a robot operates in standard Look–Compute–Move cycles. Robots are asynchronous, oblivious, anonymous, silent and execute the same distributed algorithm. So far, the problem has been mainly addressed by assuming chirality, that is robots share a common left–right orientation. We are interested in removing such a restriction. While working on the subject, we faced several issues that required close attention. We deeply investigated how such difficulties were overcome in the literature, revealing that crucial arguments for the correctness proof of the existing algorithms have been neglected. The systematic lack of rigorous arguments with respect to necessary conditions required for providing correctness proofs deeply affects the validity as well as the relevance of strategies proposed in the literature. Here we design a new deterministic distributed algorithm that fully characterizes
APF
showing its equivalence with the well-known
Leader Election
problem in the asynchronous model without chirality. Our approach is characterized by the use of logical predicates in order to formally describe our algorithm as well as its correctness. In addition to the relevance of our achievements, our techniques might help in revising previous results. In fact, it comes out that well-established results like (Fujinaga et al. in SIAM J Comput 44(3):740–785,
2015
), more recent approaches like (Bramas and Tixeuil, in: Proceedings of the 35th ACM SIGACT-SIGOPS symposium on principles of distributed computing (PODC),
2016
; Bramas and Tixeuil, in: Proceedings of the 18th international symposium on stabilization, safety, and security of distributed systems (SSS),
2016
) and ‘unofficial’ results like (Dieudonné et al., in: CoRR
arXiv:0902.2851
,
2009
) revealed to be not correct.
Algebraic methods in the congested clique Censor-Hillel, Keren; Kaski, Petteri; Korhonen, Janne H. ...
Distributed computing,
12/2019, Letnik:
32, Številka:
6
Journal Article
Recenzirano
Odprti dostop
In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the
congested clique
model. Specifically, we adapt parallel matrix multiplication ...implementations to the congested clique, obtaining an
O
(
n
1
-
2
/
ω
)
round matrix multiplication algorithm, where
ω
<
2.3728639
is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include:
triangle and 4-cycle counting in
O
(
n
0.158
)
rounds, improving upon the
O
(
n
1
/
3
)
algorithm of Dolev et al. DISC 2012,
a
(
1
+
o
(
1
)
)
-approximation of all-pairs shortest paths in
O
(
n
0.158
)
rounds, improving upon the
O
~
(
n
1
/
2
)
-round
(
2
+
o
(
1
)
)
-approximation algorithm given by Nanongkai STOC 2014, and
computing the girth in
O
(
n
0.158
)
rounds, which is the first non-trivial solution in this model.
In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles.
Shape formation by programmable particles Di Luna, Giuseppe A.; Flocchini, Paola; Santoro, Nicola ...
Distributed computing,
02/2020, Letnik:
33, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Shape formation
(or
pattern formation
) is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been ...investigated in the realm of
programmable matter
, where entities are assumed to be small and with severely limited capabilities. Namely, it has been studied in the geometric
Amoebot
model, where the anonymous entities, called
particles
, operate on a hexagonal tessellation of the plane and have limited computational power (they have constant memory), strictly local interaction and communication capabilities (only with particles in neighboring nodes of the grid), and limited motorial capabilities (from a grid node to an empty neighboring node); their activation is controlled by an adversarial scheduler. Recent investigations have shown how, starting from a well-structured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e.,
chirality
), a
sequential
activation schedule, and
randomization
(i.e., particles can flip coins to elect a leader). In this paper we obtain several results that, among other things, provide a characterization of which shapes can be formed
deterministically
starting from any
simply connected
initial configuration of
n
particles. The characterization is constructive: we provide a
universal shape formation algorithm
that, for each feasible pair of shapes
(
S
0
,
S
F
)
, allows the particles to form the final shape
S
F
(given in input) starting from the initial shape
S
0
, unknown to the particles. The final configuration will be an appropriate scaled-up copy of
S
F
depending on
n
. If
randomization
is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that there are enough particles. Our algorithm works without chirality, proving that
chirality is computationally irrelevant
for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of
O
(
n
2
)
rounds and moves: this number of moves is also asymptotically worst-case optimal.
The Lovász local lemma (LLL), introduced by Erdős and Lovász in 1975, is a powerful tool of the probabilistic method that allows one to prove that a set of
n
“bad” events do not happen with non-zero ...probability, provided that the events have limited dependence. However, the LLL itself does not suggest how to find a point avoiding all bad events. Since the works of Alon (Random Struct Algorithms 2(4):367–378,
1991
) and Beck (Random Struct Algorithms 2(4):343–365,
1991
) there has been a sustained effort to find a constructive proof (i.e. an algorithm) for the LLL or weaker versions of it. In a major breakthrough Moser and Tardos (J ACM 57(2):11,
2010
) showed that a point avoiding all bad events can be found efficiently. They also proposed a distributed/parallel version of their algorithm that requires
O
(
log
2
n
)
rounds of communication in a distributed network. In this paper we provide two new distributed algorithms for the LLL that improve on both the efficiency and simplicity of the Moser–Tardos algorithm. For clarity we express our results in terms of the symmetric LLL though both algorithms deal with the asymmetric version as well. Let
p
bound the probability of any bad event and
d
be the maximum degree in the dependency graph of the bad events. When
e
p
d
2
<
1
we give a truly simple LLL algorithm running in
O
(
log
1
/
e
p
d
2
n
)
rounds. Under the weaker condition
e
p
(
d
+
1
)
<
1
, we give a slightly slower algorithm running in
O
(
log
2
d
·
log
1
/
e
p
(
d
+
1
)
n
)
rounds. Furthermore, we give an algorithm that runs in
sublogarithmic
rounds under the condition
p
·
f
(
d
)
<
1
, where
f
(
d
) is an exponential function of
d
. Although the conditions of the LLL are locally verifiable, we prove that any distributed LLL algorithm requires
Ω
(
log
∗
n
)
rounds. In many graph coloring problems the existence of a valid coloring is established by one or more applications of the LLL. Using our LLL algorithms, we give logarithmic-time distributed algorithms for frugal coloring, defective coloring, coloring girth-4 (triangle-free) and girth-5 graphs, edge coloring, and list coloring.
Consider a set of
n
finite set of simple autonomous mobile robots (asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, ...non-rigid, deterministic) initially in distinct locations, moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of the robots arranging themselves on the vertices of a regular
n
-gon not fixed in advance (
Uniform Circle Formation
). In the literature, the existing algorithmic contributions are limited to conveniently restricted sets of initial configurations of the robots and to more powerful robots. The question of whether such simple robots could deterministically form a uniform circle has remained open. In this paper, we constructively prove that indeed the
Uniform Circle Formation
problem is solvable for any initial configuration in which the robots are in distinct locations, without any additional assumption (if two robots are in the same location, the problem is easily seen to be unsolvable). In addition to closing a long-standing problem, the result of this paper also implies that, for pattern formation, asynchrony is not a computational handicap, and that additional powers such as chirality and rigidity are computationally irrelevant.
The
amoebot model
s active programmable matter as a collection of simple computational elements called
amoebots
that interact locally to collectively achieve tasks of coordination and movement. Since ...its introduction at SPAA 2014, a growing body of literature has adapted its assumptions for a variety of problems; however, without a standardized hierarchy of assumptions, precise systematic comparison of results under the amoebot model is difficult. We propose the
canonical amoebot model
, an updated formalization that distinguishes between core model features and families of assumption variants. A key improvement addressed by the canonical amoebot model is
concurrency
. Much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting where at most one amoebot is active at a time. However, real programmable matter systems are concurrent. The canonical amoebot model formalizes all amoebot communication as message passing, leveraging adversarial activation models of concurrent executions. Under this granular treatment of time, we take two complementary approaches to
concurrent algorithm design
. We first establish a set of
sufficient conditions
for algorithm correctness under any concurrent execution, embedding concurrency control directly in algorithm design. We then present a
concurrency control framework
that uses locks to convert amoebot algorithms that terminate in the sequential setting and satisfy certain conventions into algorithms that exhibit equivalent behavior in the concurrent setting. As a case study, we demonstrate both approaches using a simple algorithm for
hexagon formation
. Together, the canonical amoebot model and these complementary approaches to concurrent algorithm design open new directions for distributed computing research on programmable matter.
Redundancy in distributed proofs Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho ...
Distributed computing,
04/2021, Letnik:
34, Številka:
2
Journal Article
Recenzirano
Odprti dostop
Distributed proofs are mechanisms that enable the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g., having a ...specific diameter), or on objects distributed over the nodes (e.g., a spanning tree). We consider well known mechanisms consisting of two components: a
prover
that assigns a
certificate
to each node, and a distributed algorithm called a
verifier
that is in charge of verifying the distributed proof formed by the collection of all certificates. We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs to establish perfect tradeoffs between the
size of the certificate
stored at every node, and the
number of rounds
of the verification protocol.
We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their known counterparts. ...The common denominator of these results is a
deterministic distributed rounding
method for certain
linear programs
, which is the first such rounding method, to our knowledge. A sampling of our end results is as follows:
An
O
log
2
Δ
·
log
n
-round deterministic distributed algorithm for computing a maximal matching, in
n
-node graphs with maximum degree
Δ
. This is the first improvement in about 20 years over the celebrated
O
(
log
4
n
)
-round algorithm of Hańćkowiak, Karoński, and Panconesi SODA’98, PODC’99.
A deterministic distributed algorithm for computing a
(
2
+
ε
)
-approximation of maximum matching in
O
log
2
Δ
·
log
1
ε
+
log
∗
n
rounds. This is exponentially faster than the classic
O
(
Δ
+
log
∗
n
)
-round 2-approximation of Panconesi and Rizzi DIST’01. With some modifications, the algorithm can also find an almost maximal matching which leaves only an
ε
-fraction of the edges on unmatched nodes.
An
O
log
2
Δ
·
log
1
ε
·
log
1
+
ε
W
+
log
∗
n
-round deterministic distributed algorithm for computing a
(
2
+
ε
)
-approximation of a maximum weighted matching, and also for the more general problem of maximum weighted
b
-matching. Here,
W
denotes the maximum normalized weight. These improve over the
O
log
4
n
·
log
1
+
ε
W
-round
(
6
+
ε
)
-approximation algorithm of Panconesi and Sozio DIST’10.
PDF
