In this paper, we study distributed graph algorithms in networks which the nodes have a limited communication capacity. Many systems are built on top of an underlying networking infrastructure, for example by using virtual topology known as overlay network. Although network might allow each node to directly communicate with large number other nodes, amount that can perform fixed time is typically much more limited. We introduce Node-Capacitated Clique model abstract model, allows us effect...

We initiate the study of network monitoring algorithms in a class hybrid networks which nodes are connected by an external and internal (as short form for externally internally controlled network). While lies outside control (or our case, protocol running them) might be exposed to continuous changes, is fully under nodes. As example, consider group users with mobile devices having access cell phone infrastructure. formed WiFi connections its structure not necessarily protocol), between via...

We envision programmable matter as a system of nanoscale agents (called particles) with very limited computational capabilities that move and compute collectively to achieve desired goal. Motivated by the problem sealing an object using minimal resources, we show how particle can self-organize form object's convex hull. give distributed, local algorithm for hull formation prove it runs in O(B) asynchronous rounds, where B is length boundary. Within same asymptotic runtime, this be extended...

Motivated by the problem of shape recognition nanoscale computing agents, we investigate detecting geometric a structure composed hexagonal tiles finite-state automaton robot. In particular, in this paper consider question recognizing whether are assembled into parallelogram whose longer side has length l = f(h), for given function f(*), where h is shorter side. To determine computational power robot, identify functions that can or cannot be decided when robot certain number pebbles. We show...

We show how to construct an overlay network of constant degree and diameter O(log n) in time starting from arbitrary weakly connected graph. assume a synchronous communication which nodes can send messages they know the identifier establish new connections by sending node identifiers. If initial network's graph is has degree, then our algorithm constructs desired topology with each receiving only round n), w.h.p., beats currently best O(log3/2 [Götte et al., SIROCCO'19]. Since problem cannot...

Abstract This article shows how to construct an overlay network of constant degree and diameter $$O(\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> in time starting from arbitrary weakly connected graph. We assume a synchronous communication which nodes can send messages they know the identifier of, new connections be established by sending...

We consider the problem of computing shortest paths in hybrid networks, which nodes can make use different communication modes. For example, mobile phones may ad-hoc connections via Bluetooth or Wi-Fi addition to cellular network solve tasks more efficiently. Like this case, modes differ considerably range, bandwidth, and flexibility. build upon model Augustine et al. [SODA '20], captures these differences by a local global mode. Specifically, edges fixed O(1) messages size O(log n) be sent...

This paper considers the shape formation problem within 3D hybrid model, where a single agent with strictly limited viewing range and computational capacity of deterministic finite automaton manipulates passive tiles through pick-up, movement, placement actions. The goal is to reconfigure set into specific termed an icicle. icicle, identified as dense, hole-free structure, strategically chosen function intermediate for more intricate tasks. It designed easy exploration by state agent,...

We consider the problem of computing shortest paths in hybrid networks, which nodes can make use different communication modes. For example, mobile phones may ad-hoc connections via Bluetooth or Wi-Fi addition to cellular network solve tasks more efficiently. Like this case, modes differ considerably range, bandwidth, and flexibility. build upon model Augustine et al. [SODA '20], captures these differences by a local global mode. Specifically, edges fixed $O(1)$ messages size $O(\log n)$ be...

Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study such [Augustine et al., SODA'20] introduced the $\mathsf{HYBRID}$ model, which is based on concept synchronous message passing and uses two fundamentally principles communication: a local mode, allows every node to exchange one per round with each neighbor in communication graph; global mode where any pair nodes can messages, but only few exchanges take...

In this brief announcement we summarize our results concerning distributed algorithms for LP-type problems in the well-known gossip model. include many important classes of such as (integer) linear programming, geometric like smallest enclosing ball and polytope distance, set hitting cover. model, a node can only push information to or pull from nodes chosen uniformly at random. Protocols model are usually very practical due their fast convergence, simplicity, stability under stress...

We envision programmable matter as a system of nano-scale agents (called particles) with very limited computational capabilities that move and compute collectively to achieve desired goal. use the geometric amoebot model our framework, which assumes particles on triangular lattice. Motivated by problem sealing an object using minimal resources, we show how particle can self-organize form object's convex hull. give distributed, local algorithm for hull formation prove it runs in...

In this paper, we study distributed graph algorithms in networks which the nodes have a limited communication capacity. Many systems are built on top of an underlying networking infrastructure, for example by using virtual topology known as overlay network. Although network might allow each node to directly communicate with large number other nodes, amount that can perform fixed time is typically much more limited. We introduce Node-Capacitated Clique model abstract model, allows us effect...