1,721,001 research outputs found
Capturing Multiparty Communication: Extending Notions of Information Theory to Topology-Dependent Multiparty Problems
No full textMultiparty communication is a natural paradigm for many applications in computer science
and engineering, including distributed computing, smart robot communication, and data streaming
algorithms. Two-party communication in the message passing model is fairly well understood;
however, strong definitions of multiparty communication have been more elusive. Multiparty
communication is further complicated by the existence of a network topology which defines how
and when parties can communicate.
In this project, we approach the problem of k-party communication over a network topology by
reasoning about the relationship between the information complexity and communication complexity
of the multiparty problem. In order to make information complexity and communication complexity
of multiparty problems over graph networks more relatable and manipulable, we define them with
respect to vertex cuts on the network graph, which induces two-party instances over the graph. We
find that many of the notions of information complexity that are useful in the two-party setting also
apply in multiparty settings. However, it seems that in relying on cuts for our reduction, we lose an
inherent gap of O(log k) in a lower bound on communication complexity of the multiparty problem
Security Analysis of Ripple Consensus
Full text linkThe Ripple network is one of the most prominent blockchain platforms and its native XRP token currently has one of the highest cryptocurrency market capitalizations. The Ripple consensus protocol powers this network and is generally considered to a Byzantine fault-tolerant agreement protocol, which can reach consensus in the presence of faulty or malicious nodes. In contrast to traditional Byzantine agreement protocols, there is no global knowledge of all participating nodes in Ripple consensus; instead, each node declares a list of other nodes that it trusts and from which it considers votes.
Previous work has brought up concerns about the liveness and safety of the consensus protocol under the general assumptions stated initially by Ripple, and there is currently no appropriate understanding of its workings and its properties in the literature. This paper closes this gap and makes two contributions. It first provides a detailed, abstract description of the protocol, which has been derived from the source code. Second, the paper points out that the abstract protocol may violate safety and liveness in several simple executions under relatively benign network assumptions
Distributed Computation in Dynamic Networks
Full text linkIn this report we investigate distributed computation in dynamic networks in which the network topology changes from round to round. We consider a worst-case model in which the communication links for each round are chosen by an adversary, and nodes do not know who their neighbors for the current round are before they broadcast their messages. The model is intended to capture mobile networks and wireless networks, in which mobility and interference render communication unpredictable. The model allows the study of the fundamental computation power of dynamic networks. In particular, it captures mobile networks and wireless networks, in which mobility and interference render communication unpredictable. In contrast to much of the existing work on dynamic networks, we do not assume that the network eventually stops changing; we require correctness and termination even in networks that change continually. We introduce a stability property called T-interval connectivity (for T >= 1), which stipulates that for every T consecutive rounds there exists a stable connected spanning subgraph. For T = 1 this means that the graph is connected in every round, but changes arbitrarily between rounds. Algorithms for the dynamic graph model must cope with these unceasing changes. We show that in 1-interval connected graphs it is possible for nodes to determine the size of the network and compute any computable function of their initial inputs in O(n^2) rounds using messages of size O(log n + d), where d is the size of the input to a single node. Further, if the graph is T-interval connected for T > 1, the computation can be sped up by a factor of T, and any function can be computed in O(n + n^2 / T) rounds using messages of size O(log n + d). We also give two lower bounds on the gossip problem, which requires the nodes to disseminate k pieces of information to all the nodes in the network. We show an Omega(n log k) bound on gossip in 1-interval connected graphs against centralized algorithms, and an Omega(n + nk / T) bound on exchanging k pieces of information in T-interval connected graphs for a restricted class of randomized distributed algorithms. The T-interval connected dynamic graph model is a novel model, which we believe opens new avenues for research in the theory of distributed computing in wireless, mobile and dynamic networks
LIPIcs, Volume 281, DISC 2023, Complete Volume
No full textLIPIcs, Volume 281, DISC 2023, Complete Volum
The Role of Communication Complexity in Distributed Computing
No full textNon UBCUnreviewedAuthor affiliation: Princeton UniversityPostdoctora
CONGEST lower bounds : beyond two-party reductions
No full textMost CONGEST lower bounds are proven by reduction from two-party communication complexity. In this tutorial/talk we will discuss some limitations of existing reductions, and ways in which they might potentially be overcome. In particular, we'll cover:
- The two-party pointer-chasing lower bound of Nisan-Widgerson
- A connection between the broadcast congested clique and number-on-forehead communication complexity
- The basics of multi-party number-in - hand communication complexity.Non UBCUnreviewedAuthor affiliation: Tel-Aviv UniversityFacult
On The Communication Complexity of Property Testing in Graphs
No full textI will describe recent work on the multi-party (number-in-hand) communication complexity of property testing in graphs, particularly testing triangle-freeness.
I will also discuss open problems in this area arising from distributed computing.
Based on joint work with Orr Fischer and Shay Gershtein.Non UBCUnreviewedAuthor affiliation: Tel-Aviv UniversityFacult
Front Matter, Table of Contents, Preface, Conference Organization
No full textFront Matter, Table of Contents, Preface, Conference Organizatio
Fast Reconfiguration for Programmable Matter
Full text linkThe concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material. Even though the particles are restricted to local communication, local movement, and simple computation, their actions can nevertheless result in the global change of the material’s physical properties and geometry.
A fundamental algorithmic task for programmable matter is to achieve global shape reconfiguration by specifying local behavior of the particles. In this paper we describe a new approach for shape reconfiguration in the amoebot model. The amoebot model is a distributed model which significantly restricts memory, computing, and communication capacity of the individual particles. Thus the challenge lies in coordinating the actions of particles to produce the desired behavior of the global system.
Our reconfiguration algorithm is the first algorithm that does not use a canonical intermediate configuration when transforming between arbitrary shapes. We introduce new geometric primitives for amoebots and show how to reconfigure particle systems, using these primitives, in a linear number of activation rounds in the worst case. In practice, our method exploits the geometry of the symmetric difference between input and output shape: it minimizes unnecessary disassembly and reassembly of the particle system when the symmetric difference between the initial and the target shapes is small. Furthermore, our reconfiguration algorithm moves the particles over as many parallel shortest paths as the problem instance allows
The Communication Complexity of Set Intersection Under Product Distributions
Full text linkWe consider a multiparty setting where k parties have private inputs X_1,…,X_k ⊆ [n] and wish to compute the intersection ⋂_{ =1}^k X_ of their sets, using as little communication as possible. This task generalizes the well-known problem of set disjointness, where the parties are required only to determine whether the intersection is empty or not. In the worst-case, it is known that the communication complexity of finding the intersection is the same as that of solving set disjointness, regardless of the size of the intersection: the cost of both problems is Ω(n log k + k) bits in the shared blackboard model, and Ω (nk) bits in the coordinator model.
In this work we consider a realistic setting where the parties' inputs are independent of one another, that is, the input is drawn from a product distribution. We show that this makes finding the intersection significantly easier than in the worst-case: only Θ̃((n^{1-1/k} (H(S) + 1)^{1/k}) + k) bits of communication are required, where {H}(S) is the Shannon entropy of the intersection S. We also show that the parties do not need to know the exact underlying input distribution; if we are given in advance O(n^{1/k}) samples from the underlying distribution μ, we can learn enough about μ to allow us to compute the intersection of an input drawn from μ using expected communication Θ̃((n^{1-1/k}[|S|]^{1/k}) + k), where |S| is the size of the intersection
- …
