Abstract The weighted vertex cover problem revolves around selecting a subset of vertices that covers a target edge set while minimizing the total cost of the selected vertices. We consider a variant of this classic optimization problem where the target edge set is not fully known; rather, it is characterized by a probability distribution. Adhering to the model of two-stage stochastic optimization , the execution is divided into two stages. In the first stage, the decision maker selects a vertex subset based on the probabilistic forecast of the target edge set. In the second stage, the target edge set is revealed, and the decision maker can augment the initial vertex subset with additional vertices to ensure coverage; however, this augmentation is more expensive due to increased vertex costs. This paper initiates the study of the two-stage stochastic vertex cover problem in the realm of distributed graph algorithms , where the decision-making process is distributed among the graph’s vertices. We consider two known stochastic optimization variants: the independent sampling model, where the edges in the target set are drawn independently from some probability distribution; and the finite scenario model, where the probability distribution over the target edge set is provided explicitly. For both variants, we devise efficient distributed algorithms based on a novel adaptation of the distributed primal-dual technique to linear programs resulting from the stochastic optimization problems’ relaxation.

Abstract The f-fault-tolerant connectivity labeling (f-FTC labeling) is a scheme of assigning each vertex and edge with a small-size label such that one can determine the connectivity of two vertices s and t under the presence of at most f faulty edges only from the labels of s, t, and the faulty edges. This paper presents a new deterministic f-FTC labeling scheme attaining $$O(f^2 \textrm{polylog}(n))$$ O ( f 2 polylog ( n ) ) -bit label size and a polynomial construction time, which settles the open problem left by Dory and Parter (in: Proceedings of the 2021 ACM symposium on principles of distributed computing (PODC), pp 445–455, 2021). The key ingredient of our construction is to develop a deterministic counterpart of the graph sketch technique by Ahn et al. (in: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems (PODS), pp 5–14, 2012), via some natural connection with the theory of error-correcting codes. This technique removes one major obstacle in de-randomizing the Dory–Parter scheme. The whole scheme is obtained by combining this technique with a new deterministic graph sparsification algorithm derived from the seminal $$\epsilon $$ ϵ -net theory, which is also of independent interest. As byproducts, our result deduces the first deterministic fault-tolerant approximate distance labeling scheme with a non-trivial performance guarantee and an improved deterministic fault-tolerant compact routing. The authors believe that our new technique is potentially useful in the future exploration of more efficient FTC labeling schemes and other related applications based on graph sketches.

An \emph{$α$-approximate vertex fault-tolerant distance sensitivity oracle} (\emph{$α$-VSDO}) for a weighted input graph $G=(V, E, w)$ and a source vertex $s \in V$ is the data structure answering an $α$-approximate distance from $s$ to $t$ in $G-x$ for any given query $(x, t) \in V \times V$. It is a data structure version of the so-called single-source replacement path problem (SSRP). In this paper, we present a new \emph{nearly linear-time} algorithm of constructing a $(1 + ε)$-VSDO for any directed input graph with polynomially bounded integer edge weights. More precisely, the presented oracle attains $\tilde{O}(m \log (nW)/ ε+ n \log^2 (nW)/ε^2)$ construction time, $\tilde{O}(n \log (nW) / ε)$ size, and $\tilde{O}(1/ε)$ query time, where $n$ is the number of vertices, $m$ is the number of edges, and $W$ is the maximum edge weight. These bounds are all optimal up to polylogarithmic factors. To the best of our knowledge, this is the first non-trivial algorithm for SSRP/VSDO beating $\tilde{O}(mn)$ computation time for directed graphs with general edge weight functions, and also the first nearly linear-time construction breaking approximation factor 3. Such a construction has been unknown even for undirected and unweighted graphs. In addition, our result implies that the known conditional lower bounds for the exact SSRP computation does not apply to the case of approximation.

A self-stabilizing randomized algorithm for mending maximal matching (MM) in synchronous networks is presented. Starting from a legal MM configuration and assuming that the network undergoes k faults or topology changes (that may occur in multiple batches), the algorithm is guaranteed to stabilize back to a legal MM configuration in time O(log k) in expectation and with high probability (in k), using constant size messages. The algorithm is simple to implement and is uniform in the sense that it does not assume unique identifiers, nor does it assume any global knowledge of the communication graph including its size. It relies on a generic probabilistic phase synchronization technique that may be useful for other self-stabilizing problems. The algorithm compares favorably with the existing self-stabilizing MM algorithms in terms of the dependence of its run-time on k, a.k.a. fully adaptive run-time. In fact, this dependence is asymptotically optimal for uniform algorithms that use constant size messages.

In this paper, we propose a randomized Õ(µ(G))-round algorithm for the maximum cardinality matching problem in the CONGEST model, where µ(G) means the maximum size of a matching of the input graph G. The proposed algorithm substantially improves the current best worst-case running time. The key technical ingredient is a new randomized algorithm of finding an augmenting path of length ℓ with high probability within Õ(ℓ) rounds, which positively settles an open problem left in the prior work by Ahmadi and Kuhn [DISC’20].

This paper proposes a retransmission or 2-shot method using the cross-slot SIC for the grant-free power-domain non-orthogonal multiple access (GF-NOMA) in the massive machine-type communications (mMTC). The proposed method allows only the users experiencing power collisions to retransmit their packets in a quasi-coordinated fashion by order of IDs of pilot sequences. Our second-shot mechanism enhances the impacts of cross-slot SIC to recover packet errors in the first transmission due to power collisions. Our simulation results highlight that the proposed method provides 32% higher throughput than the baseline method retransmitting all the error packets.

The f-fault-tolerant connectivity labeling (f-FTC labeling) is a scheme of assigning each vertex and edge with a small-size label such that one can determine the connectivity of two vertices s and t under the presence of at most f faulty edges only from the labels of s, t, and the faulty edges. This paper presents a new deterministic f-FTC labeling scheme attaining O(f2 polylog(n))-bit label size and a polynomial construction time, which settles the open problem left by Dory and Parter [18]. The key ingredient of our construction is to develop a deterministic counterpart of the graph sketch technique by Ahn, Guha, and McGreger [4], via some natural connection with the theory of error-correcting codes. This technique removes one major obstacle in de-randomizing the Dory-Parter scheme. The whole scheme is obtained by combining this technique with a new deterministic graph sparsification algorithm derived from the seminal ϵ-net theory, which is also of independent interest. As byproducts, our result deduces the first deterministic fault-tolerant approximate distance labeling scheme with a non-trivial performance guarantee and an improved deterministic fault-tolerant compact routing. The authors believe that our new technique is potentially useful in the future exploration of more efficient FTC labeling schemes and other related applications based on graph sketches.

We consider global problems, i.e. problems that take at least diameter time, even when the bandwidth is not restricted. We show that all problems considered admit efficient solutions in low-treewidth graphs.

We consider the leader election problem in population protocol models. In pragmatic settings of population protocols, self-stabilization is a highly desired feature owing to its fault resilience and the benefit of initialization freedom. However, the design of self-stabilizing leader election is possible only under a strong assumption (i.e. the knowledge of the \emph{exact} size of a network) and rich computational resources (i.e. the number of states). Loose-stabilization, introduced by Sudo et al [Theoretical Computer Science, 2012], is a promising relaxed concept of self-stabilization to address the aforementioned issue. Loose-stabilization guarantees that starting from any configuration, the network will reach a safe configuration where a single leader exists within a short time, and thereafter it will maintain the single leader for a long time, but not forever. The main contribution of the paper is a time-optimal loosely-stabilizing leader election protocol. While the shortest convergence time achieved so far in loosely-stabilizing leader election is $O(\log^3 n)$ parallel time, the proposed protocol with design parameter $τ\ge 1$ attains $O(τ\log n)$ parallel convergence time and $Ω(n^τ)$ parallel holding time (i.e. the length of the period keeping the unique leader), both in expectation. This protocol is time-optimal in the sense of both the convergence and holding times in expectation because any loosely-stabilizing leader election protocol with the same length of the holding time is known to require $Ω(τ\log n)$ parallel time.

Abstract Distributed graph algorithms in the standard CONGEST model often exhibit the time-complexity lower bound of $${\tilde{\Omega }}(\sqrt{n} + D)$$ Ω ~ ( n + D ) rounds for several global problems, where n denotes the number of nodes and D the diameter of the input graph. Because such a lower bound is derived from special “hard-core” instances, it does not necessarily apply to specific popular graph classes such as planar graphs. The concept of low-congestion shortcuts was initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologies. In particular, given a graph class $${\mathcal {C}}$$ C , an f-round algorithm for constructing shortcuts of quality q for any instance in $${\mathcal {C}}$$ C results in $${\tilde{O}}(q + f)$$ O ~ ( q + f ) -round algorithms for solving several fundamental graph problems such as minimum spanning tree and minimum cut, for $${\mathcal {C}}$$ C . The main interest on this line is to identify the graph classes allowing the shortcuts that are efficient in the sense of breaking $${\tilde{O}}(\sqrt{n}+D)$$ O ~ ( n + D ) -round general lower bounds. In this study, we consider the relationship between the quality of low-congestion shortcuts and the following four major graph parameters: doubling dimension, chordality, diameter, and clique-width. The key ingredient of the upper-bound side is a novel shortcut construction technique known as short-hop extension, which might be of independent interest.

The lexicographic depth-first search (Lex-DFS) is one of the first basic graph problems studied in the context of space-efficient algorithms. It is shown independently by Asano et al. [ISAAC 2014] and Elmasry et al. [STACS 2015] that Lex-DFS admits polynomial-time algorithms that run with O(n)-bit working memory, where n is the number of vertices in the graph. Lex-DFS is known to be P-complete under logspace reduction, and giving or ruling out polynomial-time sublinear-space algorithms for Lex-DFS on general graphs is quite challenging. In this paper, we study Lex-DFS on graphs of bounded treewidth. We first show that given a tree decomposition of width O(n^(1-ε)) with ε > 0, Lex-DFS can be solved in sublinear space. We then complement this result by presenting a space-efficient algorithm that can compute, for w ≤ √n, a tree decomposition of width O(w √nlog n) or correctly decide that the graph has a treewidth more than w. This algorithm itself would be of independent interest as the first space-efficient algorithm for computing a tree decomposition of moderate (small but non-constant) width. By combining these results, we can show in particular that graphs of treewidth O(n^(1/2 - ε)) for some ε > 0 admits a polynomial-time sublinear-space algorithm for Lex-DFS. We can also show that planar graphs admit a polynomial-time algorithm with O(n^(1/2+ε))-bit working memory for Lex-DFS.

In the rendezvous problem, two computing entities (called agents) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous neighborhood rendezvous problem, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in O(Δ) rounds (Δ is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in o(Δ) rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of O(√n) rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, and accessibility to neighborhood IDs. The first algorithm runs within Õ(√(nΔ/δ) + n/δ) rounds for graphs of the minimum degree larger than √n, where n is the number of vertices in the graph, and δ is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is O(n), and achieves Õ(n/√δ)-round time complexity without using whiteboards. These algorithms attain o(Δ)-round complexity in the case of δ = ω(√n log n) and δ = ω(n2/3log4/3n) respectively. We also prove that three unconventional assumptions of our algorithm, bounded minimum degree, accessibility to neighborhood IDs, and initial distance one, are all inherently necessary for attaining fast rendezvous. That is, one can obtain the Ω(n)-round lower bound if either one of them is removed.

This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and Chang and Saranurak (PODC'19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound O(n) to Õ(n^{1/3}), where n denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in Õ(n^{1/4}) rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now Õ(n^{1/4}) and Θ~(n^{1/3}), respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.

Pachinko is a Japanese mechanical gambling game similar to pinball. Recently, several mathematical models of Pachinko have been proposed. A number of pins are spiked in a field. A ball drops from the top of the playfield and the ball falls down. In the 50-50 model, if the ball hits a pin, it moves to the left or right passage of the pin with an equal probability. An arrangement of pins generates a distribution of the drop probability for all of the columns. This problem was considered by generating uniform distributions. Previous studies have demonstrated that the (1/2a)-uniform distribution is possible for a∈{0,1,2,3,4} and is conjectured so that it is possible for any positive integer a. This study describes the constructive proof for this conjecture. This study also formalizes a natural decision problem yielded by this model while investigating its computational complexity. More precisely, given any drop-probability distribution A and any partial drop-probability distribution B, this study uses non-deterministic polynomial-time (NP) hardness to determine if there exists a pin arrangement that transforms A into B.

In this article, we present the first leader election protocol in the population protocol model that stabilizes within O(logn) parallel time in expectation with O(logn) states per agent, where n is the number of agents. Given a rough knowledge m of lg n such that m ≥ lg n and m = O(logn), the proposed protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter. This protocol is time-optimal because it was recently proven that any leader election protocol requires Ω(logn) parallel time.

A new spanner construction algorithm is presented, working under the LOCAL model assuming unique edge IDs. Given an n-node communication graph, a spanner with a constant stretch and Õ(n1 + c) edges (for any small constant c > 0) is constructed efficiently --- i.e., in a constant number of rounds and a message complexity of Õ (n1 + 2c) whp.

The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree T for graph G, such that the maximum degree of T is the smallest among all spanning trees of G. Let d be this MDST degree for a given graph. In this paper, we present a randomized distributed approximation algorithm for the MDST problem that constructs a spanning tree with maximum degree in O(d+log n ). With high probability in n, the algorithm runs in O((D + √n) log4 n) rounds, in the broadcast-CONGEST model, where D is the graph diameter and n is the graph size. We then show how to derandomize this algorithm, obtaining the same asymptotic guarantees on degree and time complexity, but now requiring the standard CONGEST model. Although efficient approximation algorithms for the MDST problem have been known in the sequential setting since the 1990's (finding an exact solution is NP-hard), our algorithms are the first efficient distributed solutions. We conclude by proving a lower bound that establishes that any randomized MDST algorithm that guarantees a maximum degree in ∼Ω (d) requires &Ø#8764;Ω (n1/3) rounds, and any deterministic solution requires ∼Ω (n1/2) rounds. These bounds proves our deterministic algorithm to be asymptotically optimal, and eliminates the possibility of significantly more efficient randomized solutions.

The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(łog n) bits in synchronous rounds, the best known general algorithm for APSP uses Õ(n1/3) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a Õ(n1/4)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.

In this paper, we present a leader election protocol in the population protocol model that stabilizes within O(log n) parallel time in expectation with O(log n) states per agent, where n is the number of agents. Given a rough knowledge m of the population size n such that m ≥ = log2 n and m=O(log n), this protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter.

A new \emph{spanner} construction algorithm is presented, working under the \emph{LOCAL} model with unique edge IDs. Given an $n$-node communication graph, a spanner with a constant stretch and $O (n^{1 + \varepsilon})$ edges (for an arbitrarily small constant $\varepsilon > 0$) is constructed in a constant number of rounds sending $O (n^{1 + \varepsilon})$ messages whp. Consequently, we conclude that every $t$-round LOCAL algorithm can be transformed into an $O (t)$-round LOCAL algorithm that sends $O (t \cdot n^{1 + \varepsilon})$ messages whp. This improves upon all previous message-reduction schemes for LOCAL algorithms that incur a $\log^{Ω(1)} n$ blow-up of the round complexity.

Algorithmic meta-theorems, stating that graph properties expressible in some particular logic can be decided efficiently in graph classes having some specific structural properties, are now standard in sequential graph algorithms. One of the most classic examples is Courcelle's theorem: all properties expressible in Monadic Second-Order logic (MSO) are decidable in linear time in graphs of bounded treewidth. We provide here a distributed version of Courcelle's theorem, in the standard CONGEST model for distributed computing: For any MSO formula $φ$ and any constant $k$, there is a CONGEST algorithm that, given an input communication network $G$ of treewidth at most $k$ and of diameter $D$, decides if $G$ satisfies property $φ$ in $\tilde O(D)$ rounds. Simple examples show that the dependency on $D$ is unavoidable. Also, if we drop the assumption of bounded treewidth, deciding MSO properties such as 3-colorability are known to require $\tildeΩ(n^2)$ rounds in the CONGEST model. Our results extend to optimization problems (e.g., computing a maximum size independent set, or a minimum dominating set) and counting (e.g. triangle counting). As usual, the $\tilde{O}$ notation hides polylogarithmic factors in $n$; here it also hides a constant factor depending on $k$ and on the MSO formula $φ$. We also give a distributed algorithm producing a linear approximation for treewidth: For any $k$, it decides that the treewidth of the input network $G$ is larger than $k$ or computes a tree decomposition of width $O(k)$ and depth $O(\log n)$, in $\tilde O(k^{O(k)} D)$ rounds in CONGEST. Our algorithms make use of the low-congestion shortcuts framework introduced by Ghaffari and Haeupler [SODA 2016], and our main technical tool is an $\tilde O(k^4 D)$ algorithm for computing $(s,t)$-vertex separators of size at most $k+1$ in graphs of treewidth at most $k$.

In this paper we investigate the computational power of population protocols under some unreliable or weaker interaction models. More precisely, we focus on two features related to the power of interactions: omission failures and one-way communications. We start our investigation by providing a complete classification of all the possible models arising from the aforementioned weaknesses, and establishing the computational hierarchy of these models. We then address for each model the fundamental question of what additional power is necessary and sufficient to completely overcome the model's weakness and make it able to simulate faultless two-way protocols. We answer this question by presenting simulators that work under certain assumptions and by proving that simulation is impossible without such assumptions.

Triangle-free graphs play a central role in graph theory, and triangle detection (or triangle finding) as well as triangle enumeration (triangle listing) play central roles in the field of graph algorithms. In distributed computing, algorithms with sublinear round complexity for triangle finding and listing have recently been developed in the powerful CONGEST clique model, where communication is allowed between any two nodes of the network. In this paper we present the first algorithms with sublinear complexity for triangle finding and triangle listing in the standard CONGEST model, where the communication topology is the same as the topology of the network. More precisely, we give randomized algorithms for triangle finding and listing with round complexity O(n2/3(log n)2/3) and O(n3/4log n), respectively, where n denotes the number of nodes of the network. We also show a lower bound Ω(n1/3/log n) on the round complexity of triangle listing, which also holds for the CONGEST clique model.

The coalescence protocol plays an important role in the population protocol model. The conceptual structure of the protocol is for two agents holding two non-zero values a, b respectively to take a transition (a,b) -> (a+b, 0), where + is an arbitrary commutative binary operation. Obviously, it eventually aggregates the sum of all initial values. In this paper, we present a fast coalescence protocol that converges in O(sqrt(n) log^2 n) parallel time with high probability in the model with an initial leader (equivalently, the model with a base station), which achieves an substantial speed-up compared with the naive implementation taking Omega(n) time.

In order to prevent capacitive crosstalk in on-chip buses, several types of capacitive crosstalk avoidance codes have been devised. These codes are designed to prohibit transition patterns prone to capacitive crosstalk from any consecutive two words transmitted to on-chip buses. This paper provides a rigorous analysis of the asymptotic rate of (p, q)-transition free word sequences under the assumption that coding is based on a pair of a stateful encoder and a stateless decoder. The symbols p and q represent k-bit transition patterns that should not appear in any consecutive two words at the same adjacent k-bit positions. It is proved that the maximum rate of the sequences is equal to the subgraph domatic number of (p, q)-transition free graph. Based on the theoretical results on the subgraph domatic partition problem, a lower and an upper bound on the asymptotic rate is derived. We also show that the asymptotic rate 0.8325 is achievable for p = 01 and q = 10 transition free word sequences.

Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. Recent work by [Ghaffari and Hauepler; SODA'16] showed that this phenomenon can be seen as the broad underlying reason for the pervasive Omega(√n + D) lower bounds that apply to most optimization problems in the CONGEST model. On the positive side, this work also introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exist good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast O(DlogO(1)n) distributed optimization algorithms on such topologies, e.g., for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner.

The main contribution of this paper is a non-trivial expression, that is called dual expression, of the posterior values for a non-adaptive group testing problem. The dual expression is useful for exact bitwise MAP estimation. We assume a simplest non-adaptive group testing scenario including N-objects with binary status and M-disjunctive tests. If a group contains a positive object, the test result for the group is assumed to be one; otherwise, the test result becomes zero. Our inference problem is to evaluate the posterior probabilities of the objects from the observation of M-test results and from our knowledge on the prior probabilities for objects. The derivation of the dual expression of posterior values can be naturally described based on a holographic transformation to the normal factor graph (NFG) representing the inference problem. In order to handle OR constraints in the NFG, we introduce a novel holographic transformation that converts an OR function to a function similar to an EQUAL function.

A code design problem for memory devices with restricted state transitions is formulated as a combinatorial optimization problem that is called a subgraph domatic partition (subDP) problem. If any neighbor set of a given state transition graph contains all the colors, then the coloring is said to be valid. The goal of a subDP problem is to find the valid coloring that has the largest number of colors for a subgraph of a given directed graph. The number of colors in an optimal valid coloring indicates the writing capacity of that state transition graph. The subDP problems are computationally hard; it is proved to be NP-complete in this paper. One of our main contributions in this paper is to show the asymptotic behavior of the writing capacity C(G) for sequences of dense bidirectional graphs; this is given by C(G) = Ω(n/ ln n), where n is the number of nodes. A probabilistic method, Lovász local lemma (LLL), plays an essential role in deriving the asymptotic expression.

We present the first self-healing architecture for recovering semantic DR-tree overlays in response to physical nodes failures (crash). Our work builds on two of our recent results: the overlay virtualization and churn tolerant design of constant expanders for distributed R-trees. That is, the proposed self-healing strategy, in order to recover the searchability and the semantic organization of the original overlay, exploits both the randomly uniform distribution of the logical nodes on top of the physical network and the additional virtual links of the expander. The convergence time of our scheme is O(log(n)) and the height of the recovered tree is increased only by Ω(log f) with respect to the original overlay (n is the size of the network and f are the number of crashed nodes). We validate our scheme via simulations including measures of the recovery time, the recovery extra cost and finally the impact of the recovery scheme on the distributed R-tree connectivity and semantics.

We consider the problem of gathering n anonymous and oblivious mobile robots, which requires that all robots meet in finite time at a nonpredefined point. While the gathering problem cannot be solved deterministically without assuming any additional capabilities for the robots, randomized approaches easily allow it to be solvable. However, the randomized solutions currently known have a time complexity that is exponential in n with no additional assumption. This fact yields the following two questions: Is it possible to construct a randomized gathering algorithm with polynomial expected time? If it is not possible, what is the minimal additional assumption necessary to obtain such an algorithm? In this paper, we address these questions from the aspect of multiplicity-detection capabilities. We newly introduce two weaker variants of multiplicity detection, called local-strong and local-weak multiplicity, and investigate whether those capabilities permit a gathering algorithm with polynomial expected time or not. The contribution of this paper is to show that any algorithm only assuming local-weak multiplicity detection takes exponential number of rounds in expectation. On the other hand, we can obtain a constant-round gathering algorithm using local-strong multiplicity detection. These results imply that the two models of multiplicity detection are significantly different in terms of their computational power. Interestingly, these differences disappear if we take one more assumption that all robots are scattered (i.e., no two robots stay at the same location) initially. We can obtain a gathering algorithm that takes a constant number of rounds in expectation, assuming local-weak multiplicity detection and scattered initial configurations.

In this paper, we present a new exact algorithm for counting perfect matchings, which relies on neither inclusion-exclusion principle nor tree-decompositions. For any bipartite graph of 2n nodes and Δn edges such that Δ ≥ 3, our algorithm runs with O*(2(1-1/O(Δ log Δ))n) time and exponential space. Compared to the previous algorithms, it achieves a better time bound in the sense that the performance degradation to the increase of Δ is quite slower. The main idea of our algorithm is a new reduction to the problem of computing the cut-weight distribution of the input graph. The primary ingredient of this reduction is MacWilliams Identity derived from elementary coding theory. The whole of our algorithm is designed by combining that reduction with a non-trivial fast algorithm computing the cut-weight distribution. To the best of our knowledge, the approach posed in this paper is new and may be of independent interest.

Anonymous mobile robots are often classified into synchronous, semi-synchronous, and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with the single exception of forming a point (i.e., the gathering) by two robots. (All patterns formable with memory are formable without memory for synchronous robots, and little is known for asynchronous robots.) However, the gathering problem for two semi-synchronous robots without memory (called oblivious robots in this paper) is trivially solvable when their local coordinate systems are consistent, and the impossibility proof essentially uses the inconsistencies in their coordinate systems. Motivated by this, this paper investigates the magnitude of consistency between the local coordinate systems necessary and sufficient to solve the gathering problem for two oblivious robots under semi-synchronous and asynchronous models. To discuss the magnitude of consistency, we assume that each robot is equipped with an unreliable compass, the bearings of which may deviate from an absolute reference direction, and that the local coordinate system of each robot is determined by its compass. We consider two families of unreliable compasses, namely, static compasses with (possibly incorrect) constant bearings and dynamic compasses the bearings of which can change arbitrarily (immediately before a new look-compute-move cycle starts and after the last cycle ends). For each of the combinations of robot and compass models, we establish the condition on deviation $\phi$ that allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the x-axis of a compass and the reference direction of the global coordinate system: $\phi < \pi/2$ for semi-synchronous and asynchronous robots with static compasses, $\phi < \pi/4$ for semi-synchronous robots with dynamic compasses, and $\phi < \pi/6$ for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.

It is known that Byzantine consensus algorithms guarantee one-step decision only in favorable situations (e.g. when all processes propose the same value) and no one-step algorithm can support two-step decision. This paper presents DEX, a novel one-step Byzantine algorithm that circumvents these impossibilities using the condition-based approach. Algorithm DEX has two distinguished features: Adaptiveness and Double-expedition property. Adaptiveness makes it sensitive to only actual number of failures so that it provides fast termination for more number of inputs when there are fewer failures (a common case in practice). The double-expedition property facilitates two-step decision in addition to one-step decision by running two condition-based mechanisms in parallel. To the best of our knowledge, double-expedition property is the new concept introduced by this paper, and DEX is the first algorithm having such a feature. Although DEX takes four steps at worst in well-behaved runs while existing one-step algorithms take only three, it is expected to work efficiently because the worst-case does not occur so often in practice.

We consider the parallel computing environment where m organizations provide machines and several jobs to be executed. While cooperation of organizations is required to minimize the global makespan, each organization also expects the faster completion of its own jobs primarily and thus it is not necessarily cooperative. To handle the situations, we formulate the ¿-cooperative multi-organization scheduling problem (¿-MOSP), where ¿ ¿ 1 is a parameter representing the degree of cooperativeness. ¿-MOSP minimizes the makespan under the cooperation constraint that each organization does not allow the completion time of its own jobs to be delayed ¿ times of that in the case where those jobs are executed by itself. In this paper, we aim to reveal the relation between the makespan and the degree of cooperativeness. First, we investigate the relation between ¿ and the quality of the global makespan. For ¿ = 1 (i.e., each organization never sacrifices its completion time), we show an instance where the cooperation constraint degrades the optimal makespan by m times. In contrast, for ¿ > 1, we can construct an algorithm transforming any unconstrained schedule to one satisfying the cooperation constraint. This algorithm bounds the degradation ratio by ¿/(¿ - 1), which implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of ¿-MOSP. We show its strongly NPhardness and inapproximability for the approximation factor less than max{(¿ + l)/¿, 3/2}. We also show the hardness of transformation: Even if an optimal schedule under no cooperation constraint is given, no polynomial-time algorithm finds an optimal schedule for ¿-MOSP. This result is a witness for inexistence of general polynomial-time transformation algorithms that preserve the approximation ratio.

The condition-based approach is one of the sophisticated methods used to overcome several impossibility results in the distributed consensus problem (e.g., impossibility of fault tolerance in asynchronous consensus or time complexity lower bounds in synchronous consensus). It introduces conditions on input vectors to specify subsets of all possible input vectors to consensus algorithms and condition-based algorithms can circumvent the impossibility if actual input vectors satisfy a particular condition. In this paper, we present a new condition-based paradigm for synchronous consensus. We introduce the new concept of adaptation on the time complexity of condition-based algorithms and present the adaptive condition-based approach to synchronous consensus. In our approach, all possible input vectors are classified into hierarchical conditions according to their difficulty called the legality level. The execution time of adaptive condition-based algorithms depends on the legality level of input vectors. We propose two adaptive condition-based algorithms for synchronous consensus. The first algorithm requires that the majority of processes be correct, and terminates within min{f+2, t+1} l rounds if lf holds.

/spl Delta/-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: The correct process terminates its execution within a constant time /spl Delta/ (/spl Delta/-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the /spl Delta/-timed uniform consensus problem in presence of f/sub t/ crash processes and f/sub c/ timing-faulty processes. This paper proposes a /spl Delta/-timed uniform consensus algorithms. The proposed algorithm is adaptive in the following sense: It solves the /spl Delta/-timed uniform consensus when at least f/sub t/ + 1 correct processes exist in the system. If the system has less than f/sub t/ + 1 correct processes, the algorithm cannot solve the /spl Delta/-timed uniform consensus. However, as long as f/sub t/ + 1 processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any /spl Delta/-timed uniform consensus algorithm tolerating up to f/sub t/ timing-faulty processes requires that the system has at least f/sub t/ + 1 correct processes. This impossibility result implies that the proposed algorithm attains the maximal resilience about the number of faulty processes. We also show that any /spl Delta/-timed uniform consensus algorithm tolerating up to f/sub t/ timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than f/sub t/ + 1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness.