Journal Articles and Proceedings

Atomic Transactions

2026-03-12T13:19:44Z

Atomic Transactions Lynch, Nancy; Merritt, Michael; Weihl, William; Fekete, Alan

Computational tradeoffs in biological neural networks: Self-stabilizing winner-Take-All networks

2022-07-18T17:56:31Z

Computational tradeoffs in biological neural networks: Self-stabilizing winner-Take-All networks Lynch, Nancy Ann; Musco, Cameron Nicholas; Parter, Merav We initiate a line of investigation into biological neural networks from an algorithmic perspective. We develop a simplified but biologically plausible model for distributed computation in stochastic spiking neural networks and study tradeoffs between computation time and network complexity in this model. Our aim is to abstract real neural networks in a way that, while not capturing all interesting features, preserves high-level behavior and allows us to make biologically relevant conclusions. In this paper, we focus on the important 'winner-Take-All' (WTA) problem, which is analogous to a neural leader election unit: A network consisting of n input neurons and n corresponding output neurons must converge to a state in which a single output corresponding to a firing input (the 'winner') fires, while all other outputs remain silent. Neural circuits for WTA rely on inhibitory neurons, which suppress the activity of competing outputs and drive the network towards a converged state with a single firing winner. We attempt to understand how the number of inhibitors used affects network convergence time. We show that it is possible to significantly outperform naive WTA constructions through a more refined use of inhibition, solving the problem in O(θ) rounds in expectation with just O(log1/θ n) inhibitors for any θ. An alternative construction gives convergence in O(log1/θ n) rounds with O(θ) inhibitors. We complement these upper bounds with our main technical contribution, a nearly matching lower bound for networks using ≥ log log n inhibitors. Our lower bound uses familiar indistinguishability and locality arguments from distributed computing theory applied to the neural setting. It lets us derive a number of interesting conclusions about the structure of any network solving WTA with good probability, and the use of randomness and inhibition within such a network.

ARES: Adaptive, Reconfigurable, Erasure Coded, Atomic Storage

2022-11-22T16:55:11Z

ARES: Adaptive, Reconfigurable, Erasure Coded, Atomic Storage Nicolaou, Nicolas; Cadambe, Viveck; Prakash, N.; Konwar, Kishori; Medard, Muriel; Lynch, Nancy © 2019 IEEE. Emulating a shared atomic, read/write storage system is a fundamental problem in distributed computing. Replicating atomic objects among a set of data hosts was the norm for traditional implementations (e.g., [6]) in order to guarantee the availability and accessibility of the data despite host failures. As replication is highly storage demanding, recent approaches suggested the use of erasure-codes to offer the same fault-tolerance while optimizing storage usage at the hosts. Initial works focused on a fix set of data hosts. To guarantee longevity and scalability, a storage service should be able to dynamically mask hosts failures by allowing new hosts to join, and failed host to be removed without service interruptions. This work presents the first erasure-code based atomic algorithm, called ARES, which allows the set of hosts to be modified in the course of an execution. ARES is composed of three main components: (i) a reconfiguration protocol, (ii) a read/write protocol, and (iii) a set of data access primitives. The design of ARES is modular and is such to accommodate the usage of various erasure-code parameters on a per-configuration basis. We provide bounds on the latency of read/write operations and analyze the storage and communication costs of the ARES algorithm.

RADON: Repairable Atomic Data Object in Networks

2025-07-23T23:19:11Z

RADON: Repairable Atomic Data Object in Networks Lynch, Nancy; Medard, Muriel © Kishori M. Konwar, N. Prakash, Nancy A. Lynch, and Muriel Medard. Erasure codes offer an efficient way to decrease storage and communication costs while implementing atomic memory service in asynchronous distributed storage systems. In this paper, we provide erasure-code-based algorithms having the additional ability to perform background repair of crashed nodes. A repair operation of a node in the crashed state is triggered externally, and is carried out by the concerned node via message exchanges with other active nodes in the system. Upon completion of repair, the node re-enters active state, and resumes participation in ongoing and future read, write, and repair operations. To guarantee liveness and atomicity simultaneously, existing works assume either the presence of nodes with stable storage, or presence of nodes that never crash during the execution. We demand neither of these; instead we consider a natural, yet practical network stability condition N 1 that only restricts the number of nodes in the crashed/repair state during broadcast of any message. We present an erasure-code based algorithm RADONC that is always live, and guarantees atomicity as long as condition N1 holds. In situations when the number of concurrent writes is limited, RADONC has significantly improved storage and communication cost over a replication-based algorithm RADONR, which also works under N1. We further show how a slightly stronger network stability condition N2 can be used to construct algorithms that never violate atomicity. The guarantee of atomicity comes at the expense of having an additional phase during the read and write operations.

The abstract MAC layer

2022-04-29T23:02:31Z

The abstract MAC layer Kuhn, Fabian; Lynch, Nancy Ann; Newport, Calvin Charles A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specific channel behavior. Concrete implementations of the abstract MAC layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specific radio network under consideration. To illustrate this approach, we use the abstract MAC layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast in which multiple messages can originate at different times and locations in the network.We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks. © 2010 Springer-Verlag.

Ant-Inspired Dynamic Task Allocation via Gossiping

2021-11-23T17:20:18Z

Ant-Inspired Dynamic Task Allocation via Gossiping Su, Hsin-Hao; Su, Lili; Dornhaus, Anna; Lynch, Nancy Ann © Springer International Publishing AG 2017. We study the distributed task allocation problem in multi-agent systems, where each agent selects a task in such a way that, collectively, they achieve a proper global task allocation. In this paper, inspired by specialization on division of labor in ant colonies, we propose several scalable and efficient algorithms to dynamically allocate the agents as the task demands change. The algorithms have their own pros and cons, with respect to (1) how fast they react to dynamic demands change, (2) how many agents need to switch tasks, (3) whether extra agents are needed, and (4) whether they are resilient to faults.

Brief announcement: On simple back-off in unreliable radio networks

2021-11-22T20:20:41Z

Brief announcement: On simple back-off in unreliable radio networks Gilbert, Seth; Lynch, Nancy; Newport, Calvin; Pajak, Dominik S © Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. In this paper, we study local broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic communication tasks. We address this apparent paradox by introducing a new set of constraints to the dual graph model that better generalize the slow/fast fading behavior common in real networks. We prove that in the context of these new constraints, simple back-off strategies now provide efficient solutions to local broadcast in the dual graph model. These results provide theoretical foundations for the practical observation that simple back-off algorithms tend to work well even amid the complicated link dynamics of real radio networks.

Brief announcement: Integrating temporal information to spatial information in a neural circuit

2021-11-16T14:41:44Z

Brief announcement: Integrating temporal information to spatial information in a neural circuit Lynch, Nancy Ann; Wang, Mien Brabeeba © Nancy Lynch and Mien Brabeeba Wang. In this paper, we consider networks of deterministic spiking neurons, firing synchronously at discrete times. We consider the problem of translating temporal information into spatial information in such networks, an important task that is carried out by actual brains. Specifically, we define two problems: “First Consecutive Spikes Counting” and “Total Spikes Counting”, which model temporal-coding and rate-coding aspects of temporal-to-spatial translation respectively. Assuming an upper bound of T on the length of the temporal input signal, we design two networks that solve two problems, each using O(log T) neurons and terminating in time T + 1. We also prove that these bounds are tight.

An efficient communication abstraction for dense wireless networks

2023-02-09T18:54:35Z

An efficient communication abstraction for dense wireless networks Halldórsson, Magnús M.; Kuhn, Fabian; Lynch, Nancy Ann; Newport, Calvin © Magnús Halldórsson, Fabian Kuhn, Nancy Lynch, and Calvin Newport. In this paper we study the problem of developing efficient distributed algorithms for dense wireless networks. For many problems in this setting, fast solutions must leverage the reality that radio signals fade with distance, which can be exploited to enable concurrent communication among multiple sender/receiver pairs. To simplify the development of these algorithms we describe a new communication abstraction called FadingMAC which exposes the benefits of this concurrent communication, but also hides the details of the underlying low-level radio signal behavior. This approach splits efforts between those who develop useful algorithms that run on the abstraction, and those who implement the abstraction in concrete low-level wireless models, or on real hardware. After defining FadingMAC, we describe and analyze an efficient implementation of the abstraction in a standard low-level SINR-style network model. We then describe solutions to the following problems that run on the abstraction: max, min, sum, and mean computed over input values; process renaming; consensus and leader election; and optimal packet scheduling. Combining our abstraction implementation with these applications that run on the abstraction, we obtain near-optimal solutions to these problems in our low-level SINR model - significantly advancing the known results for distributed algorithms in this setting. Of equal importance to these concrete bounds, however, is the general idea advanced by this paper: as wireless networks become more dense, both theoreticians and practitioners must explore new communication abstractions that can help tame this density.

RADON: Repairable Atomic Data Object in Networks

2022-05-31T19:13:04Z

A Layered Architecture for Erasure-Coded Consistent Distributed Storage

2023-04-07T19:48:42Z

A Layered Architecture for Erasure-Coded Consistent Distributed Storage Konwar, Kishori M.; Prakash, N.; Lynch, Nancy; Médard, Muriel © 2017 Association for Computing Machinery. Motivated by emerging applications to the edge computing paradigm, we introduce a two-layer erasure-coded fault-tolerant distributed storage system offering atomic access for read and write operations. In edge computing, clients interact with an edge-layer of servers that is geographically near; the edge-layer in turn interacts with a back-end layer of servers. The edge-layer provides low latency access and temporary storage for client operations, and uses the back-end layer for persistent storage. Our algorithm, termed Layered Data Storage (LDS) algorithm, offers several features suitable for edge-computing systems, works under asynchronous message-passing environments, supports multiple readers and writers, and can tolerate f1 < n1/2 and f2 < n2/3 crash failures in the two layers having n1 and n2 servers, respectively. We use a class of erasure codes known as regenerating codes for storage of data in the back-end layer. The choice of regenerating codes, instead of popular choices like Reed-Solomon codes, not only optimizes the cost of back-end storage, but also helps in optimizing communication cost of read operations, when the value needs to be recreated all the way from the back-end. The two-layer architecture permits a modular implementation of atomicity and erasure-code protocols; the implementation of erasurecodes is mostly limited to interaction between the two layers. We prove liveness and atomicity of LDS, and also compute performance costs associated with read and write operations. In a system with n1 = Θ(n2), f1 = Θ(n1), f2 = Θ(n2), the write and read costs are respectively given by Θ(n1) and Θ(1) + n1I(δ > 0). Here δ is a parameter closely related to the number of write operations that are concurrent with the read operation, and I(δ > 0) is 1 if δ > 0, and 0 if δ = 0. The cost of persistent storage in the back-end layer is Θ(1). The impact of temporary storage is minimally felt in a multiobject system running N independent instances of LDS, where only a small fraction of the objects undergo concurrent accesses at any point during the execution. For the multi-object system, we identify a condition on the rate of concurrent writes in the system such that the overall storage cost is dominated by that of persistent storage in the back-end layer, and is given by Θ(N).

Brief announcement: On simple back-off in unreliable radio networks

2021-11-22T20:20:41Z

Brief announcement: On simple back-off in unreliable radio networks Lynch, Nancy © Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. In this paper, we study local broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic communication tasks. We address this apparent paradox by introducing a new set of constraints to the dual graph model that better generalize the slow/fast fading behavior common in real networks. We prove that in the context of these new constraints, simple back-off strategies now provide efficient solutions to local broadcast in the dual graph model. These results provide theoretical foundations for the practical observation that simple back-off algorithms tend to work well even amid the complicated link dynamics of real radio networks.

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation

2022-09-28T11:03:33Z

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation Cadambe, Viveck R.; Wang, Zhiying; Lynch, Nancy © 2016 ACM. The focus of this paper is to understand storage costs of em- ulating an atomic shared memory over an asynchronous, dis- tributed message passing system. Previous literature has de- veloped several shared memory emulation algorithms based on replication and erasure coding techniques, and analyzed the storage costs of the proposed algorithms. In this pa- per, we present the first known information-theoretic lower bounds on the storage costs incurred by shared memory em- ulation algorithms. Our storage cost lower bounds are uni- versally applicable, that is, we make no assumption on the structure of the algorithm or the method of encoding the data. We consider an arbitrary algorithm A that implements an atomic multi-writer-single-reader (MWSR) shared memory variable whose values come from a finite set V over a system of N servers connected by point-to-point asynchronous links. We require that in every fair execution of algorithm A where the number of server failures is smaller than a parameter f, every operation invoked at a non-failing client terminates. We define the storage cost of a server in algorithm A as the logarithm (to base 2) of the number of states it can take on; the total storage cost of algorithm A is the sum of the storage cost of all servers. Previously, it was known that the storage cost cannot be smaller than N/N-f log2 |V|. We develop three new lower bounds on the storage cost of algorithm A. • In our first lower bound, we show that if algorithm A does not use server gossip, then the total storage cost is lower bounded by 2N/N-f+1 log2 |V| - o(log2 |V|). • In our second lower bound we show that the total stor- age cost is at least 2N/N-f+2 log2 |V| - o(log2 |V|) even if the algorithm uses server gossip. • In our third lower bound, we consider algorithms where the write protocol sends information about the value in at most one phase. For such algorithms, we show that the total storage cost is at least v∗ N/N-f+v∗-1 log2(|V|) -o(log2(|V|), where v∗ is the minimum of f + 1 and the number of active write operations of an execution. Our first and second lower bounds are approximately twice as strong as the previously known bound of N/N-f log2 |V|. Furthermore, our first two lower bounds apply even for regu- lar, single-writer-single-reader (SWSR) shared memory em- ulation algorithms. Our third lower bound is much larger than our first and second lower bounds, although it is appli- cable to a smaller class of algorithms where the write proto- col has certain restrictions. In particular, our third bound is comparable to the storage cost achieved by most shared memory emulation algorithms in the literature, which nat- urally fall under the class of algorithms studied. Our proof ideas are inspired by recent results in coding theory.

Ant-Inspired Dynamic Task Allocation via Gossiping

2021-11-23T17:20:19Z

Ant-Inspired Dynamic Task Allocation via Gossiping Su, Hsin-Hao; Su, Lili; Dornhaus, Anna; Lynch, Nancy © Springer International Publishing AG 2017. We study the distributed task allocation problem in multi-agent systems, where each agent selects a task in such a way that, collectively, they achieve a proper global task allocation. In this paper, inspired by specialization on division of labor in ant colonies, we propose several scalable and efficient algorithms to dynamically allocate the agents as the task demands change. The algorithms have their own pros and cons, with respect to (1) how fast they react to dynamic demands change, (2) how many agents need to switch tasks, (3) whether extra agents are needed, and (4) whether they are resilient to faults.

On simple back-off in unreliable radio networks

2023-02-08T21:10:26Z

On simple back-off in unreliable radio networks Gilbert, S; Lynch, N; Newport, C; Pajak, D © Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. In this paper, we study local and global broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic communication tasks. We address this apparent paradox by introducing a new set of constraints to the dual graph model that better generalize the slow/fast fading behavior common in real networks. We prove that in the context of these new constraints, simple back-off strategies now provide efficient solutions to local and global broadcast in the dual graph model. We also precisely characterize how this efficiency degrades as the new constraints are reduced down to non-existent, and prove new lower bounds that establish this degradation as near optimal for a large class of natural algorithms. We conclude with an analysis of a more general model where we propose an enhanced back-off algorithm. These results provide theoretical foundations for the practical observation that simple back-off algorithms tend to work well even amid the complicated link dynamics of real radio networks.

ARES: Adaptive, Reconfigurable, Erasure Coded, Atomic Storage

2022-05-31T20:27:59Z

ARES: Adaptive, Reconfigurable, Erasure Coded, Atomic Storage Nicolaou, Nicolas; Cadambe, Viveck; Prakash, N; Konwar, Kishori; Medard, Muriel; Lynch, Nancy © 2019 IEEE. Emulating a shared atomic, read/write storage system is a fundamental problem in distributed computing. Replicating atomic objects among a set of data hosts was the norm for traditional implementations (e.g., [6]) in order to guarantee the availability and accessibility of the data despite host failures. As replication is highly storage demanding, recent approaches suggested the use of erasure-codes to offer the same fault-tolerance while optimizing storage usage at the hosts. Initial works focused on a fix set of data hosts. To guarantee longevity and scalability, a storage service should be able to dynamically mask hosts failures by allowing new hosts to join, and failed host to be removed without service interruptions. This work presents the first erasure-code based atomic algorithm, called ARES, which allows the set of hosts to be modified in the course of an execution. ARES is composed of three main components: (i) a reconfiguration protocol, (ii) a read/write protocol, and (iii) a set of data access primitives. The design of ARES is modular and is such to accommodate the usage of various erasure-code parameters on a per-configuration basis. We provide bounds on the latency of read/write operations and analyze the storage and communication costs of the ARES algorithm.

How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning

2023-06-22T18:47:17Z

How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning Ancona, B; Bajwa, A; Lynch, N; Mallmann-Trenn, F © 2020, Springer Nature Switzerland AG. In the French flag problem, initially uncolored cells on a grid must differentiate to become blue, white or red. The goal is for the cells to color the grid as a French flag, i.e., a three-colored triband, in a distributed manner. To solve a generalized version of the problem in a distributed computational setting, we consider two models: a biologically-inspired version that relies on morphogens (diffusing proteins acting as chemical signals) and a more abstract version based on reliable message passing between cellular agents. Much of developmental biology research focuses on concentration-based approaches, since morphogen gradients are an underlying mechanism in tissue patterning. We show that both model types easily achieve a French ribbon - a French flag in the 1D case. However, extending the ribbon to the 2D flag in the concentration model is somewhat difficult unless each agent has additional positional information. Assuming that cells are identical, it is impossible to achieve a French flag or even a close approximation. In contrast, using a message-based approach in the 2D case only requires assuming that agents can be represented as logarithmic or constant size state machines. We hope that our insights may lay some groundwork for what kind of message passing abstractions or guarantees, if any, may be useful in analogy to cells communicating at long and short distances to solve patterning problems. We also hope our models and findings may be of interest in the design of nano-robots.

Brief announcement: Integrating temporal information to spatial information in a neural circuit

2021-11-16T14:41:44Z

Brief announcement: Integrating temporal information to spatial information in a neural circuit Lynch, N; Wang, MB © Nancy Lynch and Mien Brabeeba Wang. In this paper, we consider networks of deterministic spiking neurons, firing synchronously at discrete times. We consider the problem of translating temporal information into spatial information in such networks, an important task that is carried out by actual brains. Specifically, we define two problems: “First Consecutive Spikes Counting” and “Total Spikes Counting”, which model temporal-coding and rate-coding aspects of temporal-to-spatial translation respectively. Assuming an upper bound of T on the length of the temporal input signal, we design two networks that solve two problems, each using O(log T) neurons and terminating in time T + 1. We also prove that these bounds are tight.

Fast lean erasure-coded atomic memory object

2023-02-09T20:13:22Z

Fast lean erasure-coded atomic memory object Konwar, KM; Prakash, N; Médard, M; Lynch, N © Kishori M. Konwar, N. Prakash, Muriel Médard, and Nancy Lynch; licensed under Creative Commons License CC-BY 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). In this work, we propose FLECKS, an algorithm which implements atomic memory objects in a multi-writer multi-reader (MWMR) setting in asynchronous networks and server failures. FLECKS substantially reduces storage and communication costs over its replication-based counterparts by employing erasure-codes. FLECKS outperforms the previously proposed algorithms in terms of the metrics that to deliver good performance such as storage cost per object, communication cost a high fault-tolerance of clients and servers, guaranteed liveness of operation, and a given number of communication rounds per operation, etc. We provide proofs for liveness and atomicity properties of FLECKS and derive worst-case latency bounds for the operations. We implemented and deployed FLECKS in cloud-based clusters and demonstrate that FLECKS has substantially lower storage and bandwidth costs, and significantly lower latency of operations than the replication-based mechanisms.

Random sketching, clustering, and short-term memory in spiking neural networks

2023-08-11T17:57:00Z

Random sketching, clustering, and short-term memory in spiking neural networks Hitron, Y; Lynch, N; Musco, C; Parter, M © Yael Hitron, Nancy Lynch, Cameron Musco, and Merav Parter. We study input compression in a biologically inspired model of neural computation. We demonstrate that a network consisting of a random projection step (implemented via random synaptic connectivity) followed by a sparsification step (implemented via winner-take-all competition) can reduce well-separated high-dimensional input vectors to well-separated low-dimensional vectors. By augmenting our network with a third module, we can efficiently map each input (along with any small perturbations of the input) to a unique representative neuron, solving a neural clustering problem. Both the size of our network and its processing time, i.e., the time it takes the network to compute the compressed output given a presented input, are independent of the (potentially large) dimension of the input patterns and depend only on the number of distinct inputs that the network must encode and the pairwise relative Hamming distance between these inputs. The first two steps of our construction mirror known biological networks, for example, in the fruit fly olfactory system [9, 29, 17]. Our analysis helps provide a theoretical understanding of these networks and lay a foundation for how random compression and input memorization may be implemented in biological neural networks. Technically, a contribution in our network design is the implementation of a short-term memory. Our network can be given a desired memory time tm as an input parameter and satisfies the following with high probability: any pattern presented several times within a time window of tm rounds will be mapped to a single representative output neuron. However, a pattern not presented for c · tm rounds for some constant c > 1 will be “forgotten”, and its representative output neuron will be released, to accommodate newly introduced patterns.

Self-Stabilizing Task Allocation In Spite of Noise

2022-11-22T17:11:25Z

Self-Stabilizing Task Allocation In Spite of Noise Dornhaus, Anna; Lynch, Nancy; Mallmann-Trenn, Frederik; Pajak, Dominik; Radeva, Tsvetomira © 2020 ACM. We study the problem of distributed task allocation by workers in an ant colony in a setting of limited capabilities and noisy environment feedback. We assume that each task has a demand that should be satisfied but not exceeded, i.e., there is an optimal number of ants that should be working on this task at a given time. The goal is to assign a near-optimal number of workers to each task in a distributed manner without explicit access to the value of the demand nor to the number of ants working on the task. We seek to answer the question of how the quality of task allocation depends on the accuracy of assessing by the ants whether too many (overload) or not enough (lack) ants are currently working on a given task. In our model, each ant receives a binary feedback that depends on the deficit, defined as the difference between the demand and the current number of workers in the task. The feedback is modeled as a random variable that takes values lack or overload with probability given by a sigmoid function of the deficit. The higher the overload or lack of workers for a task, the more likely it is that an ant receives the correct feedback from this task; the closer the deficit is to zero, the less reliable the feedback becomes. Each ant receives the feedback independently about one chosen task. We measure the performance of task allocation algorithms using the notion of inaccuracy, defined as the number of steps in which the deficit of some task is beyond certain threshold. We propose a simple, constant-memory, self-stabilizing, distributed algorithm that converges from any initial assignment to a near-optimal assignment under noisy feedback and keeps the deficit small for all tasks in almost every step. We also prove a lower bound for any constant-memory algorithm, which matches, up to a constant factor, the accuracy achieved by our algorithm.

Neuro-RAM unit with applications to similarity testing and compression in spiking neural networks

2023-02-13T20:43:55Z

Neuro-RAM unit with applications to similarity testing and compression in spiking neural networks Lynch, Nancy; Parter, Merav; Musco, Cameron © Nancy Lynch, Cameron Musco, and Merav Parter;. We study distributed algorithms implemented in a simplified biologically inspired model for stochastic spiking neural networks. We focus on tradeoffs between computation time and network complexity, along with the role of noise and randomness in efficient neural computation. It is widely accepted that neural spike responses, and neural computation in general, is inherently stochastic. In recent work, we explored how this stochasticity could be leveraged to solve the 'winner-take-all' leader election task. Here, we focus on using randomness in neural algorithms for similarity testing and compression. In the most basic setting, given two n-length patterns of firing neurons, we wish to distinguish if the patterns are equal or ϵ-far from equal. Randomization allows us to solve this task with a very compact network, using O (√n log n/ϵ) auxiliary neurons, which is sublinear in the input size. At the heart of our solution is the design of a t-round neural random access memory, or indexing network, which we call a neuro-RAM. This module can be implemented with O(n/t) auxiliary neurons and is useful in many applications beyond similarity testing - e.g., we discuss its application to compression via random projection. Using a VC dimension-based argument, we show that the tradeoff between runtime and network size in our neuro-RAM is near optimal. To the best of our knowledge, we are the first to apply these techniques to stochastic spiking networks. Our result has several implications - since our neuro-RAM can be implemented with deterministic threshold gates, it shows that, in contrast to similarity testing, randomness does not provide significant computational advantages for this problem. It also establishes a separation between feedforward networks whose gates spike with sigmoidal probabilities, and well-studied deterministic sigmoidal networks, whose gates output real number sigmoidal values, and which can implement a neuro-RAM much more efficiently.

Spike-Based Winner-Take-All Computation: Fundamental Limits and Order-Optimal Circuits

2023-09-27T20:58:59Z

Spike-Based Winner-Take-All Computation: Fundamental Limits and Order-Optimal Circuits Su, Lili; Chang, Chia-Jung; Lynch, Nancy © 2019 Massachusetts Institute of Technology. Winner-take-all (WTA) refers to the neural operation that selects a (typ-ically small) group of neurons from a large neuron pool. It is conjectured to underlie many of the brain’s fundamental computational abilities. However, not much is known about the robustness of a spike-based WTA network to the inherent randomness of the input spike trains. In this work, we consider a spike-based k–WTA model wherein n randomly generated input spike trains compete with each other based on their underlying firing rates and k winners are supposed to be selected. We slot the time evenly with each time slot of length 1 ms and model the n input spike trains as n independent Bernoulli processes. We analytically characterize the minimum waiting time needed so that a target minimax decision accuracy (success probability) can be reached. We first derive an information-theoretic lower bound on the waiting time. We show that to guarantee a (minimax) decision error ≤ δ (where ≤ δ (0, 1)), the waiting time of any WTA circuit is at least ((1 − δ) log(k(n − k) + 1) − 1)TR, where R c (0, 1) is a finite set of rates and TR is a difficulty parameter of a WTA task with respect to set R for independent input spike trains. Additionally, TR is independent of δ, n, and k. We then design a simple WTA circuit whose waiting time is (Formula presented) 1 O log + log k(n − k) TR, δ provided that the local memory of each output neuron is sufficiently long. It turns out that for any fixed δ, this decision time is order-optimal (i.e., it matches the above lower bound up to a multiplicative constant factor) in terms of its scaling in n, k, and TR.

Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory

2023-11-08T21:36:09Z

Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory Su, Lili; Zubeldia, Martin; Lynch, Nancy We consider multi-armed bandit problems in social groups wherein each individual has bounded memory and shares the common goal of learning the best arm/option. We say an individual learns the best option if eventually (as $t\diverge$) it pulls only the arm with the highest expected reward. While this goal is provably impossible for an isolated individual due to bounded memory, we show that, in social groups, this goal can be achieved easily with the aid of social persuasion (i.e., communication) as long as the communication networks/graphs satisfy some mild conditions. In this work, we model and analyze a type of learning dynamics which are well-observed in social groups. Specifically, under the learning dynamics of interest, an individual sequentially decides on which arm to pull next based on not only its private reward feedback but also the suggestion provided by a randomly chosen neighbor. To deal with the interplay between the randomness in the rewards and in the social interaction, we employ the \em mean-field approximation method. Considering the possibility that the individuals in the networks may not be exchangeable when the communication networks are not cliques, we go beyond the classic mean-field techniques and apply a refined version of mean-field approximation: Using coupling we show that, if the communication graph is connected and is either regular or has doubly-stochastic degree-weighted adjacency matrix, with probability → 1 as the social group size N → ∞, every individual in the social group learns the best option. If the minimum degree of the graph diverges as N → ∞, over an arbitrary but given finite time horizon, the sample paths describing the opinion evolutions of the individuals are asymptotically independent. In addition, the proportions of the population with different opinions converge to the unique solution of a system of ODEs. Interestingly, the obtained system of ODEs are invariant to the structures of the communication graphs. In the solution of the obtained ODEs, the proportion of the population holding the correct opinion converges to 1 exponentially fast in time. Notably, our results hold even if the communication graphs are highly sparse.

Task-structured probabilistic I/O automata

2023-03-01T21:54:27Z

Task-structured probabilistic I/O automata Canetti, Ran; Cheung, Ling; Kaynar, Dilsun; Liskov, Moses; Lynch, Nancy; Pereira, Olivier; Segala, Roberto © 2017 Elsevier Inc. Modeling frameworks such as Probabilistic I/O Automata (PIOA) and Markov Decision Processes permit both probabilistic and nondeterministic choices. In order to use these frameworks to express claims about probabilities of events, one needs mechanisms for resolving nondeterministic choices. For PIOAs, nondeterministic choices have traditionally been resolved by schedulers that have perfect information about the past execution. However, these schedulers are too powerful for certain settings, such as cryptographic protocol analysis, where information must sometimes be hidden. In this paper, we propose a new, less powerful nondeterminism-resolution mechanism for PIOAs, consisting of tasks and local schedulers. Tasks are equivalence classes of system actions that are scheduled by oblivious, global task sequences. Local schedulers resolve nondeterminism within system components, based on local information only. The resulting task-PIOA framework yields simple notions of external behavior and implementation, a new kind of simulation relation that is sound for proving implementation, and supports simple compositionality results.

The abstract MAC layer

2022-04-29T23:02:31Z

The abstract MAC layer Kuhn, Fabian; Lynch, Nancy; Newport, Calvin A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specific channel behavior. Concrete implementations of the abstract MAC layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specific radio network under consideration. To illustrate this approach, we use the abstract MAC layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast in which multiple messages can originate at different times and locations in the network.We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks. © 2010 Springer-Verlag.

Superconducting Nanowire Spiking Element for Neural Networks

2023-03-01T19:32:18Z

Superconducting Nanowire Spiking Element for Neural Networks Toomey, E; Segall, K; Castellani, M; Colangelo, M; Lynch, N; Berggren, KK © 2020 American Chemical Society. All rights reserved. As the limits of traditional von Neumann computing come into view, the brain's ability to communicate vast quantities of information using low-power spikes has become an increasing source of inspiration for alternative architectures. Key to the success of these largescale neural networks is a power-efficient spiking element that is scalable and easily interfaced with traditional control electronics. In this work, we present a spiking element fabricated from superconducting nanowires that has pulse energies on the order of â 10 aJ. We demonstrate that the device reproduces essential characteristics of biological neurons, such as a refractory period and a firing threshold. Through simulations using experimentally measured device parameters, we show how nanowire-based networks may be used for inference in image recognition and that the probabilistic nature of nanowire switching may be exploited for modeling biological processes and for applications that rely on stochasticity.

Searching without communicating: tradeoffs between performance and selection complexity

2023-12-14T15:21:57Z

Searching without communicating: tradeoffs between performance and selection complexity Lenzen, Christoph; Lynch, Nancy; Newport, Calvin; Radeva, Tsvetomira © 2016, Springer-Verlag Berlin Heidelberg. We consider the ANTS problem (Feinerman et al.) in which a group of agents collaboratively search for a target in a two-dimensional plane. Because this problem is inspired by the behavior of biological species, we argue that in addition to studying the time complexity of solutions it is also important to study the selection complexity, a measure of how likely a given algorithmic strategy is to arise in nature due to selective pressures. Intuitively, the larger the χ value, the more complicated the algorithm, and therefore the less likely it is to arise in nature. In more detail, we propose a new selection complexity metric χ, defined for algorithm A such that χ(A) = b+ log ℓ, where b is the number of memory bits used by each agent and ℓ bounds the fineness of available probabilities (agents use probabilities of at least 1 / 2 ℓ). In this paper, we study the trade-off between the standard performance metric of speed-up, which measures how the expected time to find the target improves with n, and our new selection metric. Our goal is to determine the thresholds of algorithmic complexity needed to enable efficient search. In particular, consider n agents searching for a treasure located within some distance D from the origin (where n is sub-exponential in D). For this problem, we identify the threshold log log D to be crucial for our selection complexity metric. We first prove a new upper bound that achieves a near-optimal speed-up for χ(A) ≈ log log D+ O(1). In particular, for ℓ∈ O(1) , the speed-up is asymptotically optimal. By comparison, the existing results for this problem (Feinerman et al.) that achieve similar speed-up require χ(A) = Ω(log D). We then show that this threshold is tight by describing a lower bound showing that if χ(A) < log log D- ω(1) , then with high probability the target is not found in D2-o(1) moves per agent. Hence, there is a sizable gap with respect to the straightforward Ω(D2/ n+ D) lower bound in this setting.

Modeling radio networks

2022-09-27T19:46:17Z

Modeling radio networks Newport, Calvin Charles; Lynch, Nancy Ann We describe a modeling framework and collection of foundational composition results for the study of probabilistic distributed algorithms in synchronous radio networks. Though the radio setting has been studied extensively by the distributed algorithms community, their results rely on informal descriptions of the channel behavior and therefore lack easy comparability and are prone to error caused by definition subtleties. Our framework rectifies these issues by providing: (1) a method to precisely describe a radio channel as a probabilistic automaton; (2) a mathematical notion of implementing one channel using another channel, allowing for direct comparisons of channel strengths and a natural decomposition of problems into implementing a more powerful channel and solving the problem on the powerful channel; (3) a mathematical definition of a problem and solving a problem; (4) a pair of composition results that simplify the tasks of proving properties about channel implementation algorithms and combining problems with channel implementations. Our goal is to produce a model streamlined for the needs of the radio network algorithms community.

Leader election using loneliness detection

2022-09-29T18:14:58Z

Leader election using loneliness detection Ghaffari, Mohsen; Lynch, Nancy Ann; Sastry, Srikanth We consider the problem of leader election (LE) in single-hop radio networks with synchronized time slots for transmitting and receiving messages. We assume that the actual number n of processes is unknown, while the size u of the ID space is known, but is possibly much larger. We consider two types of collision detection: strong (SCD), whereby all processes detect collisions, and weak (WCD), whereby only non-transmitting processes detect collisions. We introduce loneliness detection (LD) as a key subproblem for solving LE in WCD systems. LD informs all processes whether the system contains exactly one process or more than one. We show that LD captures the difference in power between SCD and WCD, by providing an implementation of SCD over WCD and LD. We present two algorithms that solve deterministic and probabilistic LD in WCD systems with time costs of O(log u/n and O(min(log u/n, log (1/ε)/n)), respectively, where ε is the error probability. We also provide matching lower bounds. Assuming LD is solved, we show that SCD systems can be emulated in WCD systems with factor-2 overhead in time. We present two algorithms that solve deterministic and probabilistic LE in SCD systems with time costs of O(log u) and O(min (log u/, log log + log(1/ε), respectively, where ε is the error probability. We provide matching lower bounds. Keywords: Collision Detection, Safety Property, Leader Election, Liveness Property, Virtual Process

Dynamic input/output automata: A formal and compositional model for dynamic systems

2022-10-01T05:47:03Z

Dynamic input/output automata: A formal and compositional model for dynamic systems Attie, Paul C.; Lynch, Nancy Ann We present dynamic I/O automata (DIOA), a compositional model of dynamic systems. In DIOA, automata can be created and destroyed dynamically, as computation proceeds, and an automaton can dynamically change its signature, i.e., the set of actions in which it can participate. DIOA features operators for parallel composition, action hiding, action renaming, a notion of automaton creation, and a notion of behavioral subtyping by means of trace inclusion. DIOA can model mobility, using signature modification, and is hierarchical: a dynamically changing system of interacting automata is itself modeled as a single automaton. We also show that parallel composition, action hiding, action renaming, and (subject to some technical conditions) automaton creation are all monotonic with respect to trace inclusion: if one component is replaced by another whose traces are a subset of the former, then the set of traces of the system as a whole can only be reduced. Keywords: Dynamic systems; Formal methods; Semantics; Automata; Process creation; Mobility

Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems

2022-09-28T08:13:58Z

Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems Dornhaus, Anna; Nagpal, Radhika; Radeva, Tsvetomira T.; Lynch, Nancy Ann; Su, Hsin-Hao Adaptive collective systems are common in biology and beyond. Typically, such systems require a task allocation algorithm: a mechanism or rule-set by which individuals select particular roles. Here we study the performance of such task allocation mechanisms measured in terms of the time for individuals to allocate to tasks. We ask: (1) Is task allocation fundamentally difficult, and thus costly? (2) Does the performance of task allocation mechanisms depend on the number of individuals? And (3) what other parameters may affect their efficiency? We use techniques from distributed computing theory to develop a model of a social insect colony, where workers have to be allocated to a set of tasks; however, our model is generalizable to other systems. We show, first, that the ability of workers to quickly assess demand for work in tasks they are not currently engaged in crucially affects whether task allocation is quickly achieved or not. This indicates that in social insect tasks such as thermoregulation, where temperature may provide a global and near instantaneous stimulus to measure the need for cooling, for example, it should be easy to match the number of workers to the need for work. In other tasks, such as nest repair, it may be impossible for workers not directly at the work site to know that this task needs more workers. We argue that this affects whether task allocation mechanisms are under strong selection. Second, we show that colony size does not affect task allocation performance under our assumptions. This implies that when effects of colony size are found, they are not inherent in the process of task allocation itself, but due to processes not modeled here, such as higher variation in task demand for smaller colonies, benefits of specialized workers, or constant overhead costs. Third, we show that the ratio of the number of available workers to the workload crucially affects performance. Thus, workers in excess of those needed to complete all tasks improve task allocation performance. This provides a potential explanation for the phenomenon that social insect colonies commonly contain inactive workers: these may be a ‘surplus’ set of workers that improves colony function by speeding up optimal allocation of workers to tasks. Overall our study shows how limitations at the individual level can affect group level outcomes, and suggests new hypotheses that can be explored empirically.

Ant-inspired density estimation via random walks

2022-10-01T22:19:20Z

Ant-inspired density estimation via random walks Musco, Cameron Nicholas; Su, Hsin-Hao; Lynch, Nancy Ann Many ant species use distributed population density estimation in applications ranging from quorum sensing, to task allocation, to appraisal of enemy colony strength. It has been shown that ants estimate local population density by tracking encounter rates: The higher the density, the more often the ants bump into each other. We study distributed density estimation from a theoretical perspective. We prove that a group of anonymous agents randomly walking on a grid are able to estimate their density within a small multiplicative error in few steps by measuring their rates of encounter with other agents. Despite dependencies inherent in the fact that nearby agents may collide repeatedly (and, worse, cannot recognize when this happens), our bound nearly matches what would be required to estimate density by independently sampling grid locations. From a biological perspective, our work helps shed light on how ants and other social insects can obtain relatively accurate density estimates via encounter rates. From a technical perspective, our analysis provides tools for understanding complex dependencies in the collision probabilities of multiple random walks. We bound the strength of these dependencies using local mixing properties of the underlying graph. Our results extend beyond the grid to more general graphs, and we discuss applications to size estimation for social networks, density estimation for robot swarms, and random walk-based sampling for sensor networks. Keywords: population density estimation; random walk sampling; network exploration; ant colony; algorithms; biological distributed algorithms

Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems

2022-09-30T14:17:25Z

Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems Kantor, Erez; Schwarzmann, Alexander A.; Konwar, Kishori Mohan; Prakash, N.; Lynch, Nancy Ann; Medard, Muriel Erasure codes are increasingly being studied in the context of implementing atomic memory objects in large scale asynchronous distributed storage systems. When compared with the traditional replication based schemes, erasure codes have the potential of significantly lowering storage and communication costs while simultaneously guaranteeing the desired resiliency levels. In this work, we propose the Storage-Optimized Data-Atomic (SODA) algorithm for implementing atomic memory objects in the multi-writer multi-reader setting. SODA uses Maximum Distance Separable (MDS) codes, and is specifically designed to optimize the total storage cost for a given fault-tolerance requirement. For tolerating f server crashes in an n-server system, SODA uses an [n, k] MDS code with k = n - f, and incurs a total storage cost of n/n-f. SODA is designed under the assumption of reliable point-to-point communication channels. The communication cost of a write and a read operation are respectively given by O(f[superscript 2]) and n/n-f(δ[subscript w]+1), where δ[subscript w] denotes the number of writes that are concurrent with the particular read. In comparison with the recent CASGC algorithm [1], which also uses MDS codes, SODA offers lower storage cost while pays more on the communication cost. We also present a modification of SODA, called SODA[subscript err], to handle the case where some of the servers can return erroneous coded elements during a read operation. Specifically, in order to tolerate f server failures and e error-prone coded elements, the SODAerr algorithm uses an [n, k] MDS code such that k = n - 2e - f. SODAerr also guarantees liveness and atomicity, while maintaining an optimized total storage cost of n/n-f-2e.

Computing in Additive Networks with Bounded-Information Codes

2022-09-28T16:20:02Z

Computing in Additive Networks with Bounded-Information Codes Censor-Hillel, Keren; Kantor, Erez; Lynch, Nancy Ann; Parter, Merav This paper studies the theory of the additive wireless network model, in which the received signal is abstracted as an addition of the transmitted signals. Our central observation is that the crucial challenge for computing in this model is not high contention, as assumed previously, but rather guaranteeing a bounded amount of information in each neighborhood per round, a property that we show is achievable using a new random coding technique. Technically, we provide efficient algorithms for fundamental distributed tasks in additive networks, such as solving various symmetry breaking problems, approximating network parameters, and solving an asymmetry revealing problem such as computing a maximal input. The key method used is a novel random coding technique that allows a node to successfully decode the received information, as long as it does not contain too many distinct values. We then design our algorithms to produce a limited amount of information in each neighborhood in order to leverage our enriched toolbox for computing in additive networks.

Task Allocation in Ant Colonies

2022-10-01T12:20:13Z

Task Allocation in Ant Colonies Cornejo, Alejandro; Dornhaus, Anna; Nagpal, Radhika; Lynch, Nancy Ann In this paper we propose a mathematical model for studying the phenomenon of division of labor in ant colonies. Inside this model we investigate how simple task allocation mechanisms can be used to achieve an optimal division of labor. We believe the proposed model captures the essential biological features of division of labor in ant colonies and is general enough to study a variety of different task allocation mechanisms. Within this model we propose a distributed randomized algorithm for task allocation that imposes only minimal requirements on the ants; it uses a constant amount of memory and relies solely on a primitive binary feedback function to sense the current labor allocation. We show that with high probability the proposed algorithm converges to a near-optimal division of labor in time which is proportional to the logarithm of the colony size.

A coded shared atomic memory algorithm for message passing architectures

2022-10-01T21:41:40Z

A coded shared atomic memory algorithm for message passing architectures Musial, Peter; Cadambe, Viveck R.; Medard, Muriel; Lynch, Nancy Ann This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains three main contributions: (1) we present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with N servers that is resilient to f server failures, we show that the communication cost of CAS is N/(N−2f). The storage cost of CAS is unbounded. (2) We present a modification of the CAS algorithm known as CAS with garbage collection (CASGC). The CASGC algorithm is parameterized by an integer δ and has a bounded storage cost. We show that the CASGC algorithm satisfies atomicity. In every execution of CASGC where the number of server failures is no bigger than f, we show that every write operation invoked at a non-failing client terminates. We also show that in an execution of CASGC with parameter δ where the number of server failures is no bigger than f, a read operation terminates provided that the number of write operations that are concurrent with the read is no bigger than δ. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS. (3) We describe an algorithm known as the Communication Cost Optimal Atomic Storage (CCOAS) algorithm that achieves a smaller communication cost than CAS and CASGC. In particular, CCOAS incurs read and write communication costs of N/(N−2f) measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC.

Special issue on DISC 2010

2022-10-02T07:20:44Z

Special issue on DISC 2010 Shvartsman, Alexander A.; Lynch, Nancy Ann This special issue of Distributed Computing is based on papers that originally appeared as extended abstracts in the Proceedings of the 24th International Symposium on Distributed Computing (DISC2010), held in Cambridge, Massachusetts on August 13–15, 2010. The papers for the Special Issue were chosen by the Program Committee from the 32 regular papers presented at the Symposium, based on their quality and representation of the spectrum of topics encompassed by the Symposium. In addition to being reviewed, in preliminary form, by the Program Committee, the full papers submitted for the Special Issue were refereed according to the standard practices of Distributed Computing (due to time constrains, some papers could not appear in this volume). We thank the Members of the Editorial Board for their work in editing this issue, and the referees and the authors of these papers for their respective contributions.

Multi-message broadcast with abstract MAC layers and unreliable links

2022-09-29T09:43:04Z

Multi-message broadcast with abstract MAC layers and unreliable links Ghaffari, Mohsen; Kantor, Erez; Newport, Calvin Charles; Lynch, Nancy Ann We study the multi-message broadcast problem using abstract MAC layer models of wireless networks. These models capture the key guarantees of existing MAC layers while abstracting away low-level details such as signal propagation and contention.We begin by studying upper and lower bounds for this problem in a standard abstract MAC layer model---identifying an interesting dependence between the structure of unreliable links and achievable time complexity. In more detail, given a restriction that devices connected directly by an unreliable link are not too far from each other in the reliable link topology, we can (almost) match the efficiency of the reliable case. For the related restriction, however, that two devices connected by an unreliable link are not too far from each other in geographic distance, we prove a new lower bound that shows that this efficiency is impossible. We then investigate how much extra power must be added to the model to enable a new order of magnitude of efficiency. In more detail, we consider an enhanced abstract MAC layer model and present a new multi-message broadcast algorithm that (under certain natural assumptions) solves the problem in this model faster than any known solutions in an abstract MAC layer setting.

Trade-offs between selection complexity and performance when searching the plane without communication

2022-09-27T15:16:26Z

Trade-offs between selection complexity and performance when searching the plane without communication Lenzen, Christoph; Newport, Calvin Charles; Lynch, Nancy Ann; Radeva, Tsvetomira T. We argue that in the context of biology-inspired problems in computer science, in addition to studying the time complexity of solutions it is also important to study the selection complexity, a measure of how likely a given algorithmic strategy is to arise in nature. In this spirit, we propose a selection complexity metric χ for the ANTS problem [Feinerman et al.]. For algorithm A, we define χ(A) = b + log l, where b is the number of memory bits used by each agent and l bounds the fineness of available probabilities (agents use probabilities of at least 1/2[superscript l]). We consider n agents searching for a target in the plane, within an (unknown) distance D from the origin. We identify log log D as a crucial threshold for our selection complexity metric. We prove a new upper bound that achieves near-optimal speed-up of (D[superscript 2]/n +D) ⋅ 2[superscript O(l)] for χ(A) ≤ 3 log log D + O(1), which is asymptotically optimal if l∈ O(1). By comparison, previous algorithms achieving similar speed-up require χ(A) = Ω(log D). We show that this threshold is tight by proving that if χ(A) < log log D - ω(1), then with high probability the target is not found if each agent performs D[superscript 2-o(1)] moves. This constitutes a sizable gap to the straightforward Ω(D[superscript 2]/n + D) lower bound.

Bounded-Contention Coding for wireless networks in the high SNR regime

2022-10-01T07:20:05Z

Bounded-Contention Coding for wireless networks in the high SNR regime Censor-Hillel, Keren; Haeupler, Bernhard; Lynch, Nancy Ann; Medard, Muriel Efficient communication in wireless networks is typically challenged by the possibility of interference among several transmitting nodes. Much important research has been invested in decreasing the number of collisions in order to obtain faster algorithms for communication in such networks. This paper proposes a novel approach for wireless communication, which embraces collisions rather than avoiding them, over an additive channel. It introduces a coding technique called Bounded-Contention Coding (BCC) that allows collisions to be successfully decoded by the receiving nodes into the original transmissions and whose complexity depends on a bound on the contention among the transmitters. BCC enables deterministic local broadcast in a network with n nodes and at most a transmitters with information of ℓ bits each within O(a log n + aℓ) bits of communication with full-duplex radios, and O((a log n + aℓ)(log n)) bits, with high probability, with half-duplex radios. When combined with random linear network coding, BCC gives global broadcast within O((D + a + log n)(a log n + ℓ)) bits, with high probability. This also holds in dynamic networks that can change arbitrarily over time by a worst-case adversary. When no bound on the contention is given, it is shown how to probabilistically estimate it and obtain global broadcast that is adaptive to the true contention in the network.

Distributed House-Hunting in Ant Colonies

2022-09-30T13:42:57Z

Distributed House-Hunting in Ant Colonies Ghaffari, Mohsen; Musco, Cameron Nicholas; Radeva, Tsvetomira T.; Lynch, Nancy Ann We introduce the study of the ant colony house-hunting problem from a distributed computing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony relocates to a new nest. The task of identifying and evaluating the quality of potential new nests is distributed among all ants. They must additionally reach consensus on a final nest choice and transport the full colony to this single new nest. Our goal is to use tools and techniques from distributed computing theory in order to gain insight into the house-hunting process. We develop a formal model for the house-hunting problem inspired by the behavior of the Temnothorax genus of ants. We then show a Omega(log n) lower bound on the time for all n ants to agree on one of k candidate nests. We also present two algorithms that solve the house-hunting problem in our model. The first algorithm solves the problem in optimal O(log n) time but exhibits some features not characteristic of natural ant behavior. The second algorithm runs in O(k log n) time and uses an extremely simple and natural rule for each ant to decide on the new nest.

A Local Broadcast Layer for the SINR Network Model

2022-09-29T12:26:58Z

A Local Broadcast Layer for the SINR Network Model Halldorsson, Magnus M.; Holzer, Stephan Sebastian; Lynch, Nancy Ann We present the first algorithm that implements an abstract MAC (absMAC) layer in the Signal-to-Interference-plus-Noise-Ratio (SINR) wireless network model. We first prove that efficient SINR implementations are not possible for the standard absMAC specification. We modify that specification to an "approximate" version that better suits the SINR model. We give an efficient algorithm to implement the modified specification, and use it to derive efficient algorithms for higher-level problems of global broadcast and consensus. In particular, we show that the absMAC progress property has no efficient implementation in terms of the SINR strong connectivity graph G[subscript 1-ε], which contains edges between nodes of distance at most (1-ε) times the transmission range, where ε>0 is a small constant that can be chosen by the user. This progress property bounds the time until a node is guaranteed to receive some message when at least one of its neighbors is transmitting. To overcome this limitation, we introduce the slightly weaker notion of approximate progress into the absMAC specification. We provide a fast implementation of the modified specification, based on decomposing the algorithm of [10] into local and global parts. We analyze our algorithm in terms of local parameters such as node degrees, rather than global parameters such as the overall number of nodes. A key contribution is our demonstration that such a local analysis is possible even in the presence of global interference. Our absMAC algorithm leads to several new, efficient algorithms for solving higher-level problems in the SINR model. Namely, by combining our algorithm with high-level algorithms from [26], we obtain an improved (compared to [10]) algorithm for global single-message broadcast in the SINR model, and the first efficient algorithm for multi-message broadcast in that model. We also derive the first efficient algorithm for network-wide consensus, using a result of [32]. This work demonstrates that one can develop efficient algorithms for solving high-level problems in the SINR model, using graph-based algorithms over a local broadcast abstraction layer that hides the technicalities of the SINR platform such as global interference. Our algorithms do not require bounds on the network size, nor the ability to measure signal strength, nor carrier sensing, nor synchronous wakeup.

A (Truly) Local Broadcast Layer for Unreliable Radio Networks

2022-10-03T09:53:47Z

A (Truly) Local Broadcast Layer for Unreliable Radio Networks Newport, Calvin Charles; Lynch, Nancy Ann In this paper, we implement an efficient local broadcast service for the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Our local broadcast service offers probabilistic latency guarantees for: (1) message delivery to all reliable neighbors (i.e., neighbors connected by reliable links), and (2) receiving some message when one or more reliable neighbors are broadcasting. This service significantly simplifies the design and analysis of algorithms for the otherwise challenging dual graph model. To this end, we also note that our solution can be interpreted as an implementation of the abstract MAC layer specification---therefore translating the growing corpus of algorithmic results studied on top of this layer to the dual graph model. At the core of our service is a seed agreement routine which enables nodes in the network to achieve "good enough" coordination to overcome the difficulties of unpredictable link behavior. Because this routine has potential application to other problems in this setting, we capture it with a formal specification---simplifying its reuse in other algorithms. Finally, we note that in a break from much work on distributed radio network algorithms, our problem definitions (including error bounds), implementation, and analysis do not depend on global network parameters such as the network size, a goal which required new analysis techniques. We argue that breaking the dependence of these algorithms on global parameters makes more sense and aligns better with the rise of ubiquitous computing, where devices will be increasingly working locally in an otherwise massive network. Our push for locality, in other words, is a contribution independent of the specific radio network model and problem studied here.

Coded Emulation of Shared Atomic Memory for Message Passing Architectures

2022-10-01T08:44:18Z

Coded Emulation of Shared Atomic Memory for Message Passing Architectures Cadambe, Viveck R.; Lynch, Nancy Ann; Medard, Muriel; Musial, Peter This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains two main contributions: (1) We present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with N servers that is resilient to f server failures, we show that the communication 0cost of CAS is [N over N−2f]. The storage cost of CAS is unbounded. (2) We present a variant of CAS known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer δ and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than δ, the CASGC algorithm with parameter δ satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS.

Bounds on Contention Management in Radio Networks

2022-09-28T08:03:41Z

Bounds on Contention Management in Radio Networks Ghaffari, Mohsen; Haeupler, Bernhard; Newport, Calvin Charles; Lynch, Nancy Ann The local broadcast problem assumes that processes in a wireless network are provided messages, one by one, that must be delivered to their neighbors. In this paper, we prove tight bounds for this problem in two well-studied wireless network models: the classical model, in which links are reliable and collisions consistent, and the more recent dual graph model, which introduces unreliable edges. Our results prove that the Decay strategy, commonly used for local broadcast in the classical setting, is optimal. They also establish a separation between the two models, proving that the dual graph setting is strictly harder than the classical setting, with respect to this primitive.

The cost of radio network broadcast for different models of unreliable links

2022-09-30T00:41:14Z

The cost of radio network broadcast for different models of unreliable links Ghaffari, Mohsen; Lynch, Nancy Ann; Newport, Calvin Charles We study upper and lower bounds for the global and local broadcast problems in the dual graph model combined with different strength adversaries. The dual graph model is a generalization of the standard graph-based radio network model that includes unreliable links controlled by an adversary. It is motivated by the ubiquity of unreliable links in real wireless networks. Existing results in this model [11, 12, 3, 8] assume an offline adaptive adversary - the strongest type of adversary considered in standard randomized analysis. In this paper, we study the two other standard types of adversaries: online adaptive and oblivious. Our goal is to find a model that captures the unpredictable behavior of real networks while still allowing for efficient broadcast solutions. For the online adaptive dual graph model, we prove a lower bound that shows the existence of constant-diameter graphs in which both types of broadcast require Ω(n/ log n) rounds, for network size n. This result is within log-factors of the (near) tight upper bound for the offline adaptive setting. For the oblivious dual graph model, we describe a global broadcast algorithm that solves the problem in O(Dlog n + log[superscript 2] n) rounds for network diameter D, but prove a lower bound of Ω(√n= log n) rounds for local broadcast in this same setting. Finally, under the assumption of geographic constraints on the network graph, we describe a local broadcast algorithm that requires only O(log[superscript 2] n logΔ) rounds in the oblivious model, for maximum degree Δ. In addition to the theoretical interest of these results, we argue that the oblivious model (with geographic constraints) captures enough behavior of real networks to render our efficient algorithms useful for real deployments.

Bounded-Contention Coding for Wireless Networks in the High SNR Regime

2022-09-27T17:26:24Z

Bounded-Contention Coding for Wireless Networks in the High SNR Regime Censor-Hillel, Keren; Haeupler, Bernhard; Lynch, Nancy Ann; Medard, Muriel Efficient communication in wireless networks is typically challenged by the possibility of interference among several transmitting nodes. Much important research has been invested in decreasing the number of collisions in order to obtain faster algorithms for communication in such networks. This paper proposes a novel approach for wireless communication, which embraces collisions rather than avoiding them, over an additive channel. It introduces a coding technique called Bounded-Contention Coding (BCC) that allows collisions to be successfully decoded by the receiving nodes into the original transmissions and whose complexity depends on a bound on the contention among the transmitters. BCC enables deterministic local broadcast in a network with n nodes and at most a transmitters with information of ℓ bits each within O(alogn + aℓ) bits of communication with full-duplex radios, and O((alogn + aℓ)(logn)) bits, with high probability, with half-duplex radios. When combined with random linear network coding, BCC gives global broadcast within O((D + a + logn)(alogn + ℓ)) bits, with high probability. This also holds in dynamic networks that can change arbitrarily over time by a worst-case adversary. When no bound on the contention is given, it is shown how to probabilistically estimate it and obtain global broadcast that is adaptive to the true contention in the network.

Perspectives on the CAP Theorem

2022-10-02T05:50:13Z

Perspectives on the CAP Theorem Gilbert, Seth; Lynch, Nancy Ann Almost twelve years ago, in 2000, Eric Brewer introduced the idea that there is a fundamental trade-off between consistency, availability, and partition tolerance. This trade-off, which has become known as the CAP Theorem, has been widely discussed ever since. In this paper, we review the CAP Theorem and situate it within the broader context of distributed computing theory. We then discuss the practical implications of the CAP Theorem, and explore some general techniques for coping with the inherent trade-offs that it implies.

Engineering the Virtual Node Layer for Reactive MANET Routing

2022-10-02T02:16:58Z

Engineering the Virtual Node Layer for Reactive MANET Routing Wu, Jiang; Griffeth, Nancy; Newport, Calvin Charles; Lynch, Nancy Ann The VNLayer approach simplifies software development for MANET by providing the developers an abstraction of a network divided into fixed geographical regions, each containing a virtual server for network services. In this paper, we present our study on reactive MANET routing over the VNLayer. During this research, we identified in our initial VNLayer implementation three major limitations that lead to heavy control traffic, long forwarding paths and frequent message collisions in MANET routing. To address the problems, we changed the assumptions made by the VNLayer on the link layer and extended the operations allowed by VNLayer. This results in a VNLayer implementation that can be tuned to optimize the performance of traffic intensive applications (such as routing) while maintaining their simplicity and robustness. Simulation results showed that VNAODV, a VNLayer based routing protocol adapted from AODV, delivers more packets, generates less routing traffic and creates more stable routes than AODV in a dense MANET with high node motion rates. This research validated that the VNLayer approach makes software development for MANET easier and improves the performance of MANET protocols.

Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration

2022-09-30T22:26:57Z

Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration Volkov, Mikhail; Cornejo Collado, Alex; Lynch, Nancy Ann; Rus, Daniela L. This paper addresses the problem of obtaining a concise description of a physical environment for robotic exploration. We aim to determine the number of robots required to clear an environment using non-recontaminating exploration. We introduce the medial axis as a configuration space and derive a mathematical representation of a continuous environment that captures its underlying topology and geometry. We show that this representation provides a concise description of arbitrary environments, and that reasoning about points in this representation is equivalent to reasoning about robots in physical space. We leverage this to derive a lower bound on the number of required pursuers. We provide a transformation from this continuous representation into a symbolic representation. Finally, we present a generalized pursuit-evasion algorithm. Given an environment we can compute how many pursuers we need, and generate an optimal pursuit strategy that will guarantee the evaders are detected with the minimum number of pursuers.

Structuring Unreliable Radio Networks

2022-09-27T16:32:42Z

Structuring Unreliable Radio Networks Censor-Hillel, Keren; Lynch, Nancy Ann; Newport, Calvin Charles In this paper we study the problem of building a connected dominating set with constant degree (CCDS) in the dual graph radio network model [4,9,10]. This model includes two types of links: reliable, which always deliver messages, and unreliable, which sometimes fail to deliver messages. Real networks compensate for this differing quality by deploying low-layer detection protocols to filter unreliable from reliable links. With this in mind, we begin by presenting an algorithm that solves the CCDS problem in the dual graph model under the assumption that every process u is provided a local link detector set consisting of every neighbor connected to u by a reliable link. The algorithm solves the CCDS problem in O(Δ\log[superscript 2] n/b + log[superscript 3] n) rounds, with high probability, where Δ is the maximum degree in the reliable link graph, n is the network size, and b is an upper bound in bits on the message size. The algorithm works by first building a Maximal Independent Set (MIS) in log[superscript 3] n time, and then leveraging the local topology knowledge to efficiently connect nearby MIS processes. A natural follow up question is whether the link detector must be perfectly reliable to solve the CCDS problem. With this in mind, we first describe an algorithm that builds a CCDS in O(Δpolylog(n)) time under the assumption of O(1) unreliable links included in each link detector set. We then prove this algorithm to be (almost) tight by showing that the possible inclusion of only a single unreliable link in each process's local link detector set is sufficient to require Ω(Δ) rounds to solve the CCDS problem, regardless of message size. We conclude by discussing how to apply our algorithm in the setting where the topology of reliable and unreliable links can change over time.

Brief Announcement: Partial Reversal Acyclicity

2022-09-30T01:22:11Z

Brief Announcement: Partial Reversal Acyclicity Radeva, Tsvetomira; Lynch, Nancy Ann Partial Reversal (PR) is a link reversal algorithm which ensures that an initially directed acyclic graph (DAG) is eventually a destination-oriented DAG. While proofs exist to establish the acyclicity property of PR, they rely on assigning labels to either the nodes or the edges in the graph. In this work we show that such labeling is not necessary and outline a simpler direct proof of the acyclicity property.

Automated Formal Verification of the DHCP Failover Protocol Using Timeout Order Abstraction

2022-09-30T00:03:03Z

Automated Formal Verification of the DHCP Failover Protocol Using Timeout Order Abstraction Umeno, Shinya; Lynch, Nancy Ann In this paper, we present automated formal verification of the DHCP Failover protocol. We conduct bounded model-checking for the protocol using Timeout Order Abstraction (TO-Abstraction), a technique to abstract a given timed model in a certain sub-class of loosely synchronized real-time distributed systems into an untimed model. A resulting untimed model from TO-abstraction is a finite state machine, and therefore one can verify the model using a conventional model-checker. We have verified the protocol by bounded model-checking up to depth 20. We also experimented with "mutating" the original code to examine the efficiency of bug-finding using TO-Abstraction. We used two mutated pieces of the original code. The first one represents a model that uses a stronger failure assumption. The second one represents a model that the protocol implementer has forgot to add a certain check of a received message. We found one counterexample for each of two pieces of mutated code. In particular, the counterexample that was found for the second mutated code had a complex scenario, and we believe that it is considerably difficult to find the counterexample by human or simulations.

MAC Design for Analog Network Coding

2022-09-28T08:05:06Z

MAC Design for Analog Network Coding Khabbazian, Majid; Kuhn, Fabian; Lynch, Nancy Ann; Medard, Muriel; Parandehgheibi, Ali Most medium access control (MAC) mechanisms discard collided packets and consider interference harmful. Recent work on Analog Network Coding (ANC) suggests a different approach, in which multiple interfering transmissions are strategically scheduled. Receiving nodes collect the results of collisions and then use a decoding process, such as ZigZag decoding, to extract the packets involved in the collisions. In this paper, we present an algebraic representation of collisions and describe a general approach to recovering collisions using ANC. To study the effects of using ANC on the performance of MAC layers, we develop an ANC-based MAC algorithm, CMAC, and analyze its performance in terms of probabilistic latency guarantees for local packet delivery. Specifically, we prove that CMAC implements an abstract MAC layer service, as defined in [14, 13]. This study shows that ANC can significantly improve the performance of the abstract MAC layer service compared to conventional probabilistic transmission approaches. We illustrate how this improvement in the MAC layer can translate into faster higher-level algorithms, by analyzing the time complexity of a multi-message network-wide broadcast algorithm that uses CMAC.

Decomposing broadcast algorithms using abstract mac layers

2022-09-30T22:39:21Z

Decomposing broadcast algorithms using abstract mac layers Khabbazian, Majid; Kowalski, Dariusz R.; Kuhn, Fabian; Lynch, Nancy Ann In much of the theoretical literature on wireless algorithms, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, and makes it difficult to extend the work to harder communication problems. In this paper, we present results of a current project aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifi cations to encapsulate the contention management. We use two di erent abstract MAC layers: the basic one of [14, 15] and a new probabilistic layer. We show that it implements both abstract MAC layers. We combine this algorithm with greedy algorithms for single- message and multi-message global broadcast and analyze the combination, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of ... for the time to deliver a single message everywhere with probability 1 -epsilon , where D is the network diameter, n is the number of nodes, and Delta is the maximum node degree. Using the probabilistic layer, we prove a bound of ..., which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of ... using the basic layer and ... using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages.

The abstract MAC layer

2022-09-29T11:08:20Z

The abstract MAC layer Kuhn, Fabian; Lynch, Nancy Ann; Newport, Calvin Charles A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an Abstract MAC Layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specific channel behavior. Concrete implementations of the Abstract MAC Layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specific radio network under consideration. To illustrate this approach, we use the Abstract MAC Layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast, in which any number of messages arrive at any processes at any times. We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks.

Timeout Order Abstraction for Time-Parametric Verification of Loosely Synchronized Real-Time Distributed Systems

2022-09-28T09:58:56Z

Timeout Order Abstraction for Time-Parametric Verification of Loosely Synchronized Real-Time Distributed Systems Umeno, Shinya; Lynch, Nancy Ann We present timeout order abstraction (TO-abstraction), a technique to systematically abstract a given loosely synchronized real-time distributed system (LSRTDS) into an untimed model. We define the subclass of LSRTDS’s that we can apply TO-abstraction using a syntax template that represents a restriction to Tempo, the primary modeling language of TIOA [7]. The untimed model obtained from the abstraction is a classical finite state machine, and thus one can automatically verify temporal properties of the model using a conventional model-checker. We prove the soundness of the abstraction using simulation relation. From this result, we guarantee that any untimed safety property of the untimed model also holds for the original TIOA model. We have applied TO-abstraction to a resource-sharing protocol and the DHCP Failover protocol. We verified untimed abstractions of them by bounded model-checking up to depth 20. We have also experimented with effectiveness of bug-finding using our technique by mutating particular parts of the original code. From this experiment, we found a complex bad execution that would have been very difficult to find by human or simulations. URL to paper listed on conference site.

Broadcasting in unreliable radio networks

2022-09-29T20:18:20Z

Broadcasting in unreliable radio networks Kuhn, Fabian; Lynch, Nancy Ann; Newport, Calvin Charles; Oshman, Rotem; Richa, Andrea Practitioners agree that unreliable links, which sometimes deliver messages and sometime do not, are an important characteristic of wireless networks. In contrast, most theoretical models of radio networks fix a static set of links and assume that these links are reliable. This gap between theory and practice motivates us to investigate how unreliable links affect theoretical bounds on broadcast in radio networks. To that end we consider a model that includes two types of links: reliable links, which always deliver messages, and unreliable links, which sometimes fail to deliver messages. We assume that the reliable links induce a connected graph, and that unreliable links are controlled by a worst-case adversary. In the new model we show an Ω(n log n) lower bound on deterministic broadcast in undirected graphs, even when all processes are initially awake and have collision detection, and an Ω(n) lower bound on randomized broadcast in undirected networks of constant diameter. This separates the new model from the classical, reliable model. On the positive side, we give two algorithms that tolerate unreliability: an O(n3/2 √log n)-time deterministic algorithm and a randomized algorithm which terminates in O(n log2 n) rounds with high probability.

Self-stabilizing robot formations over unreliable networks

2022-09-30T00:22:00Z

Self-stabilizing robot formations over unreliable networks Gilbert, Seth; Lynch, Nancy Ann; Mitra, Sayan; Nolte, Tina We describe how a set of mobile robots can arrange themselves on any specified curve on the plane in the presence of dynamic changes both in the underlying ad hoc network and in the set of participating robots. Our strategy is for the mobile robots to implement a self-stabilizing virtual layer consisting of mobile client nodes, stationary Virtual Nodes (VNs), and local broadcast communication. The VNs are associated with predetermined regions in the plane and coordinate among themselves to distribute the client nodes relatively uniformly among the VNs' regions. Each VN directs its local client nodes to align themselves on the local portion of the target curve. The resulting motion coordination protocol is self-stabilizing, in that each robot can begin the execution in any arbitrary state and at any arbitrary location in the plane. In addition, self-stabilization ensures that the robots can adapt to changes in the desired target formation.

Reliably Detecting Connectivity Using Local Graph Traits

2022-10-02T06:24:03Z

Reliably Detecting Connectivity Using Local Graph Traits Cornejo Collado, Alex; Lynch, Nancy Ann Local distributed algorithms can only gather sufficient information to identify local graph traits, that is, properties that hold within the local neighborhood of each node. However, it is frequently the case that global graph properties (connectivity, diameter, girth, etc) have a large influence on the execution of a distributed algorithm. This paper studies local graph traits and their relationship with global graph properties. Specifically, we focus on graph k-connectivity. First we prove a negative result that shows there does not exist a local graph trait which perfectly captures graph k-connectivity. We then present three different local graph traits which can be used to reliably predict the k-connectivity of a graph with varying degrees of accuracy. As a simple application of these results, we present upper and lower bounds for a local distributed algorithm which determines if a graph is k-connected. As a more elaborate application of local graph traits, we describe, and prove the correctness of, a local distributed algorithm that preserves k-connectivity in mobile ad hoc networks while allowing nodes to move independently whenever possible.

Distributed computation in dynamic networks

2022-09-27T09:38:07Z

Distributed computation in dynamic networks Kuhn, Fabian; Lynch, Nancy Ann; Oshman, Rotem In this paper 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 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. We show that in 1-interval connected graphs it is possible for nodes to determine the size of the network and compute any com- putable function of their initial inputs in O(n2) [O (n superscript 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 + n2/T) [(n + n superscript 2 /T)] rounds using messages of size O(log n + d). We also give two lower bounds on the token dissemination problem, which requires the nodes to disseminate k pieces of information to all the nodes in the network. 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.

Rambo: a robust, reconfigurable atomic memory service for dynamic networks

2022-10-01T10:23:21Z

Rambo: a robust, reconfigurable atomic memory service for dynamic networks Gilbert, Seth; Lynch, Nancy Ann; Shvartsman, Alexander A. n this paper, we present Rambo, an algorithm for emulating a read/write distributed shared memory in a dynamic, rapidly changing environment. Rambo provides a highly reliable, highly available service, even as participants join, leave, and fail. In fact, the entire set of participants may change during an execution, as the initial devices depart and are replaced by a new set of devices. Even so, Rambo ensures that data stored in the distributed shared memory remains available and consistent. There are two basic techniques used by Rambo to tolerate dynamic changes. Over short intervals of time, replication suffices to provide fault-tolerance. While some devices may fail and leave, the data remains available at other replicas. Over longer intervals of time, Rambo copes with changing participants via reconfiguration, which incorporates newly joined devices while excluding devices that have departed or failed. The main novelty of Rambo lies in the combination of an efficient reconfiguration mechanism with a quorum-based replication strategy for read/write shared memory. The Rambo algorithm can tolerate a wide variety of aberrant behavior, including lost and delayed messages, participants with unsynchronized clocks, and, more generally, arbitrary asynchrony. Despite such behavior, Rambo guarantees that its data is stored consistency. We analyze the performance of Rambo during periods when the system is relatively well-behaved: messages are delivered in a timely fashion, reconfiguration is not too frequent, etc. We show that in these circumstances, read and write operations are efficient, completing in at most eight message delays.

Neighbor discovery in mobile ad hoc networks using an abstract MAC layer

2022-10-02T05:03:43Z

Neighbor discovery in mobile ad hoc networks using an abstract MAC layer Viqar, Saira; Welch, Jennifer L.; Cornejo Collado, Alex; Lynch, Nancy Ann We explore the problem of neighbor discovery in a mobile ad hoc network environment. We describe a protocol for learning about neighboring nodes in such an environment. The protocol is used for establishing and tearing down communication links with neighboring nodes as they move from one region of the network to another. The protocol is implemented on top of the abstract MAC layer service, which provides reliable message delivery within the local neighborhood and also provides the sender with an acknowledgment when all neighboring nodes have received a message. There is an upper bound, guaranteed by the abstract MAC layer service, on the worst case delay that a message can experience before it is received or acknowledged. We determine the time complexity of the neighbor discovery protocol in terms of the bounded delays provided by the underlying abstract MAC layer.

Simulating fixed virtual nodes for adapting wireline protocols to MANET

2022-10-02T03:12:06Z

Simulating fixed virtual nodes for adapting wireline protocols to MANET Wu, Jiang; Griffeth, Nancy; Droms, Ralph; Lynch, Nancy Ann; Newport, Calvin Charles The virtual node layer (VNLayer) is a programming abstraction for mobile ad hoc networks (MANETs). It defines simple virtual servers at fixed locations in a network, addressing a central problem for MANETs, which is the absence of fixed infrastructure. Advantages of this abstraction are that persistent state is maintained in each region, even when mobile nodes move or fail, and that simple wireline protocols can be deployed on the infrastructure, thereby taming the difficulties inherent in MANET setting. The major disadvantage is the messaging overhead for maintaining the persistent state. In this paper, we use simulation to determine the magnitude of the messaging overhead and the impact on the performance of the protocol. The overhead of maintaining the servers and the persistent state is small in bytes, but the number of messages required is relatively large. In spite of this, the latency of address allocation is relatively small and almost all mobile nodes have an address for 99 percent of their lifetime. Our ns-2 based simulation package (VNSim) implements the VNLayer using a leader-based state replication strategy to emulate the virtual nodes. VNSim efficiently simulates a virtual node system with up to a few hundred mobile nodes. VNSim can be used to simulate any VNLayer-based application.

On the weakest failure detector ever

2022-10-01T04:59:12Z

On the weakest failure detector ever Kuznetsov, Petr; Herlihy, Maurice; Newport, Calvin Charles; Lynch, Nancy Ann; Guerraoui, Rachid Many problems in distributed computing are impossible to solve when no information about process failures is available. It is common to ask what information about failures is necessary and sufficient to circumvent some specific impossibility, e.g., consensus, atomic commit, mutual exclusion, etc. This paper asks what information about failures is necessary to circumvent any impossibility and sufficient to circumvent some impossibility. In other words, what is the minimal yet non-trivial failure information. We present an abstraction, denoted $${\Upsilon}$$ , that provides very little information about failures. In every run of the distributed system, $${\Upsilon}$$ eventually informs the processes that some set of processes in the system cannot be the set of correct processes in that run. Although seemingly weak, for it might provide random information for an arbitrarily long period of time, and it eventually excludes only one set of processes (among many) that is not the set of correct processes in the current run, $${\Upsilon}$$ still captures non-trivial failure information. We show that $${\Upsilon}$$ is sufficient to circumvent the fundamental wait-free set-agreement impossibility. While doing so, (a) we disprove previous conjectures about the weakest failure detector to solve set-agreement and (b) we prove that solving set-agreement with registers is strictly weaker than solving n + 1-process consensus using n-process consensus. We show that $${\Upsilon}$$ is the weakest stable non-trivial failure detector: any stable failure detector that circumvents some wait-free impossibility provides at least as much information about failures as $${\Upsilon}$$ does. Our results are generalized, from the wait-free to the f-resilient case, through an abstraction $${\Upsilon^f}$$ that we introduce and prove minimal to solve any problem that cannot be solved in an f-resilient manner, and yet sufficient to solve f-resilient f-set-agreement.

Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication

2022-09-26T14:19:38Z

Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication Newport, Calvin Charles; Kuhn, Fabian; Lynch, Nancy Ann We prove two broadcast lower bounds for a wireless network model that includes unreliable links. For deterministic algorithms, we show n − 1 rounds are required, where n is the number of processes. For randomized algorithms, ε(n − 1) rounds are required for success probability ε. In both cases, the bounds are proved for a network in which constant-time broadcast is possible.

Brief announcement: Minimum spanning trees and cone-based topology control

2022-09-29T08:59:41Z

Brief announcement: Minimum spanning trees and cone-based topology control Cornejo Collado, Alex; Lynch, Nancy Ann Consider a setting where nodes can vary their transmission power thereby changing the network topology, the goal of topology control is to reduce the transmission power while ensuring the communication graph remains connected. Wattenhofer et al. [6] introduced the distributed cone-based topology control algorithm with parameter α (CBTC(α)) and proved it correct if α ≤ 2π/3. Li et al. [4] proposed performing asymmetric edge removal or increasing α to 5π/6, and proved that when applied separately these minimizations preserve connectivity. Bahramgiri et al. [1] proved that when α ≤ 2π/3 it was possible to extend the algorithm to work in three dimensions and described a variation to preserve k-connectivity. We give a short self-contained proof that when α ≤ 2π/3 the minimum spanning tree is contained in the graph produced by CBTC(α). Its interesting to note that by comparison, other popular topology control algorithms are variations of the Gabriel Graph [5], the Relative Neighbor Graph [2] or the Delaunay Triangulation [3]; all of which are structures known to contain the minimum spanning tree. The proof is essentially an application of a lemma proved by Yao [7]. As a consequence of this proof we get as corollaries new short proofs of some of the main results of Wattenhofer et al. [6], Li et al. [4] and Bahramgiri et al. [1]. (1) When α ≤ 2π/3 the algorithm CBTC(α) preserves connectivity [6]. (2) The asymmetric edge removal operation preserves connectivity [4]. (3) The algorithm can be extended to three dimensions [1], and generally to n-dimensional space.