Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userReactive Proof Labeling Schemes for Distributed Decision
157
0
0.0
(
0
)
Added by
Jiaqi Chen
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We generalize the definition of Proof Labeling Schemes to reactive systems, that is, systems where the configuration is supposed to keep changing forever. As an example, we address the main classical test case of reactive tasks, namely, the task of token passing. Different RPLSs are given for the cases that the network is assumed to be a tree or an anonymous ring, or a general graph, and the sizes of RPLSs labels are analyzed. We also address the question of whether an RPLS exists. First, on the positive side, we show that there exists an RPLS for any distributed task for a family of graphs with unique identities. For the case of anonymous networks (even for the special case of rings), interestingly, it is known that no token passing algorithm is possible even if the number n of nodes is known. Nevertheless, we show that an RPLS is possible. On the negative side, we show that if one drops the assumption that n is known, then the construction becomes impossible.
rate research
Read More
Broadcast is one of the fundamental network communication primitives. One node of a network, called the $mathit{source}$, has a message that has to be learned by all other nodes. We consider the feasibility of deterministic broadcast in radio networks. If nodes of the network do not have any labels, deterministic broadcast is impossible even in the four-cycle. On the other hand, if all nodes have distinct labels, then broadcast can be carried out, e.g., in a round-robin fashion, and hence $O(log n)$-bit labels are sufficient for this task in $n$-node networks. In fact, $O(log Delta)$-bit labels, where $Delta$ is the maximum degree, are enough to broadcast successfully. Hence, it is natural to ask if very short labels are sufficient for broadcast. Our main result is a positive answer to this question. We show that every radio network can be labeled using 2 bits in such a way that broadcast can be accomplished by some universal deterministic algorithm that does not know the network topology nor any bound on its size. Moreover, at the expense of an extra bit in the labels, we get the additional strong property that there exists a common round in which all nodes know that broadcast has been completed. Finally, we show that 3-bit labels are also sufficient to solve bo
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees. We study the deterministic time complexity of solving a given binary labeling problem in trees, in the usual LOCAL model of distributed computing. We show that the complexity of any such problem is in one of the following classes: $O(1)$, $Theta(log n)$, $Theta(n)$, or unsolvable. In particular, a problem that can be represented in the binary labeling formalism cannot have time complexity $Theta(log^* n)$, and hence we know that e.g. any encoding of maximal matchings has to use at least three labels (which is tight). Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it. Hence the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.
Partitioning large matrices is an important problem in distributed linear algebra computing (used in ML among others). Briefly, our goal is to perform a sequence of matrix algebra operations in a distributed manner (whenever possible) on these large matrices. However, not all partitioning schemes work well with different matrix algebra operations and their implementations (algorithms). This is a type of data tiling problem. In this work we consider a theoretical model for a version of the matrix tiling problem in the setting of hypergraph labeling. We prove some hardness results and give a theoretical characterization of its complexity on random instances. Additionally we develop a greedy algorithm and experimentally show its efficacy.
Erasure coding techniques are getting integrated in networked distributed storage systems as a way to provide fault-tolerance at the cost of less storage overhead than traditional replication. Redundancy is maintained over time through repair mechanisms, which may entail large network resource overheads. In recent years, several novel codes tailor-made for distributed storage have been proposed to optimize storage overhead and repair, such as Regenerating Codes that minimize the per repair traffic, or Self-Repairing Codes which minimize the number of nodes contacted per repair. Existing studies of these coding techniques are however predominantly theoretical, under the simplifying assumption that only one object is stored. They ignore many practical issues that real systems must address, such as data placement, de/correlation of multiple stored objects, or the competition for limited network resources when multiple objects are repaired simultaneously. This paper empirically studies the repair performance of these novel storage centric codes with respect to classical erasure codes by simulating realistic scenarios and exploring the interplay of code parameters, failure characteristics and data placement with respect to the trade-offs of bandwidth usage and speed of repairs.
We present a family of p-enrichment schemes. These schemes may be separated into two basic classes: the first, called emph{fixed tolerance schemes}, rely on setting global scalar tolerances on the local regularity of the solution, and the second, called emph{dioristic schemes}, rely on time-evolving bounds on the local variation in the solution. Each class of $p$-enrichment scheme is further divided into two basic types. The first type (the Type I schemes) enrich along lines of maximal variation, striving to enhance stable solutions in areas of highest interest. The second type (the Type II schemes) enrich along lines of maximal regularity in order to maximize the stability of the enrichment process. Each of these schemes are tested over a pair of model problems arising in coastal hydrology. The first is a contaminant transport model, which addresses a declinature problem for a contaminant plume with respect to a bay inlet setting. The second is a multicomponent chemically reactive flow model of estuary eutrophication arising in the Gulf of Mexico.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
