BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Nancy Lynch

Nancy Lynch appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingInformation Theorymath.ITData Structures and Algorithmsmath.CONetworking and Internet ArchitectureNeural and Evolutionary ComputingComputational Complexitycond-mat.supr-conEmerging TechnologiesMultiagent SystemsNeurons and Cognitionphysics.app-ph

Catalog footprint

What is connected

18works
13topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

18 published item(s)

preprint2022arXiv

A Geometry-Sensitive Quorum Sensing Algorithm for the Best-of-N Site Selection Problem

The house hunting behavior of the Temnothorax albipennis ant allows the colony to explore several nest choices and agree on the best one. Their behavior serves as the basis for many bio-inspired swarm models to solve the same problem. However, many of the existing site selection models in both insect colony and swarm literature test the model's accuracy and decision time only on setups where all potential site choices are equidistant from the swarm's starting location. These models do not account for the geographic challenges that result from site choices with different geometry. For example, although actual ant colonies are capable of consistently choosing a higher quality, further site instead of a lower quality, closer site, existing models are much less accurate in this scenario. Existing models are also more prone to committing to a low quality site if it is on the path between the agents' starting site and a higher quality site. We present a new model for the site selection problem and verify via simulation that is able to better handle these geographic challenges. Our results provide insight into the types of challenges site selection models face when distance is taken into account. Our work will allow swarms to be robust to more realistic situations where sites could be distributed in the environment in many different ways.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Superconducting Nanowire-based Architecture for Neuromorphic Computing

Neuromorphic computing is poised to further the success of software-based neural networks by utilizing improved customized hardware. However, the translation of neuromorphic algorithms to hardware specifications is a problem that has been seldom explored. Building superconducting neuromorphic systems requires extensive expertise in both superconducting physics and theoretical neuroscience. In this work, we aim to bridge this gap by presenting a tool and methodology to translate algorithmic parameters into circuit specifications. We first show the correspondence between theoretical neuroscience models and the dynamics of our circuit topologies. We then apply this tool to solve linear systems by implementing a spiking neural network with our superconducting nanowire-based hardware.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Symbolic Knowledge Structures and Intuitive Knowledge Structures

This paper proposes that two distinct types of structures are present in the brain: Symbolic Knowledge Structures (SKSs), used for formal symbolic reasoning, and Intuitive Knowledge Structures (IKSs), used for drawing informal associations. The paper contains ideas for modeling and analyzing these structures in an algorithmic style based on Spiking Neural Networks, following the paradigm used in earlier work by Lynch, Musco, Parter, and co-workers. The paper also contains two examples of use of these structures, involving counting through a memorized sequence, and understanding simple stylized sentences. The ideas presented here are preliminary and speculative, and do not (yet) comprise a complete, coherent, algorithmic theory. I hope that posting this preliminary version will help the ideas to evolve into such a theory.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Integrating Temporal Information to Spatial Information in a Neural Circuit

In this paper, we consider networks of deterministic spiking neurons, firing synchronously at discrete times; such spiking neural networks are inspired by networks of neurons and synapses that occur in brains. 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 (FCSC)" and "Total Spikes Counting (TSC)", which model spike and rate coding aspects of translating temporal information into spatial information respectively. Assuming an upper bound of $T$ on the length of the temporal input signal, we design two networks that solve these two problems, each using $O(\log T)$ neurons and terminating in time $1$. We also prove that there is no network with less than $T$ neurons that solves either question in time $0$.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Ant-Inspired Density Estimation via Random Walks

Many ant species employ distributed population density estimation in applications ranging from quorum sensing [Pra05], to task allocation [Gor99], to appraisal of enemy colony strength [Ada90]. It has been shown that ants estimate density by tracking encounter rates -- the higher the population density, the more often the ants bump into each other [Pra05,GPT93]. 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 new 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 and density estimation for robot swarms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks

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(\log^{1/θ} n)$ inhibitors for any $θ$. An alternative construction gives convergence in $O(\log^{1/θ} n)$ rounds with $O(θ)$ inhibitors. We compliment these upper bounds with our main technical contribution, a nearly matching lower bound for networks using $\ge \log\log n$ inhibitors. Our lower bound uses familiar indistinguishability and locality arguments from distributed computing theory. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

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

The focus of this paper is to understand storage costs of emulating an atomic shared memory over an asynchronous, distributed message passing system. Previous literature has developed several shared memory emulation algorithms based on replication and erasure coding techniques. In this paper, we present information-theoretic lower bounds on the storage costs incurred by shared memory emulation algorithms. Our storage cost lower bounds are universally 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 $\mathcal{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 number of states it can take on; the total-storage cost of algorithm $A$ is the sum of the storage cost of all servers. Our results are as follows. (i) We show that if algorithm $A$ does not use server gossip, then the total storage cost is lower bounded by $2 \frac{N}{N-f+1}\log_2|\mathcal{V}|-o(\log_2|\mathcal{V}|)$. (ii) The total storage cost is at least $2 \frac{N}{N-f+2} \log_{2}|\mathcal{V}|-o(\log_{2}|\mathcal{V}|)$ even if the algorithm uses server gossip. (iii) We consider algorithms where the write protocol sends information about the value in at most one phase. We show that the total storage cost is at least $ν^* \frac{N}{N-f+ν^*-1} \log_2( |\mathcal{V}|)- o(\log_2(|\mathcal{V}|),$ where $ν^*$ is the minimum of $f+1$ and the number of active write operations of an execution.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

RADON: Repairable Atomic Data Object in Networks

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 $N1$ that only restricts the number of nodes in the crashed/repair state during broadcast of any message. We present an erasure-code based algorithm $RADON_C$ that is always live, and guarantees atomicity as long as condition $N1$ holds. In situations when the number of concurrent writes is limited, $RADON_C$ has significantly improved storage and communication cost over a replication-based algorithm $RADON_R$, 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

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

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 $\frac{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^2)$ and $\frac{n}{n-f}(δ_w+1)$, where $δ_w$ denotes the number of writes that are concurrent with the particular read. In comparison with the recent CASGC algorithm, 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$_{\text{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 SODA$_{\text{err}}$ algorithm uses an $[n, k]$ MDS code such that $k=n-2e-f$. SODA$_{\text{err}}$ also guarantees liveness and atomicity, while maintaining an optimized total storage cost of $\frac{n}{n-f-2e}$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Local Broadcast Layer for the SINR Network Model

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_{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 a known algorithm 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 known high-level algorithms, we obtain an improved algorithm for global single-message broadcast in the SINR model, and the first efficient algorithm for multi-message broadcast in that model.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computing in Additive Networks with Bounded-Information Codes

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 \emph{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 \emph{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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Distributed House-Hunting in Ant Colonies

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 must relocate to a new nest. The task of identifying and evaluating the quality of potential new nests is distributed among all ants. The ants must additionally reach consensus on a final nest choice and the full colony must be transported 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 Ω(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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Coded Shared Atomic Memory Algorithm for Message Passing Architectures

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 a 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 $\frac{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 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. (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 $\frac{N}{N-f}$ measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links

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 {\em 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 {\em 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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication

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 {\em time complexity} of solutions it is also important to study the {\em selection complexity}, a measure of how likely a given algorithmic strategy is to arise in nature due to selective pressures. In more detail, we propose a new selection complexity metric $χ$, defined for algorithm ${\cal A}$ such that $χ({\cal A}) = b + \log \ell$, where $b$ is the number of memory bits used by each agent and $\ell$ bounds the fineness of available probabilities (agents use probabilities of at least $1/2^\ell$). 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. In particular, consider $n$ agents searching for a treasure located at (unknown) distance $D$ from the origin (where $n$ is sub-exponential in $D$). For this problem, we identify $\log \log D$ as a crucial threshold for our selection complexity metric. We first prove a new upper bound that achieves a near-optimal speed-up of $(D^2/n +D) \cdot 2^{O(\ell)}$ for $χ({\cal A}) \leq 3 \log \log D + O(1)$. In particular, for $\ell \in 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 $χ({\cal A}) = Ω(\log D)$. We then show that this threshold is tight by describing a lower bound showing that if $χ({\cal A}) < \log \log D - ω(1)$, then with high probability the target is not found within $D^{2-o(1)}$ moves per agent. Hence, there is a sizable gap to the straightforward $Ω(D^2/n + D)$ lower bound in this setting.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

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

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 l bits each within O(a log n + al) bits of communication with full-duplex radios, and O((a log n + al)(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 + l)) 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Bounds on Contention Management in Radio Networks

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.

0 citations0 reviewsNo code linkedOpen access
preprint1994arXiv

Proving time bounds for randomized distributed algorithms

A method of analyzing time bounds for randomized distributed algorithms is presented, in the context of a new and general framework for describing and reasoning about randomized algorithms. The method consists of proving auxiliary statements of the form U (t)->(p) U', which means that whenever the algorithm begins in a state in set U, with probability p, it will reach a state in set U' within time t. The power of the method is illustrated by its use in proving a constant upper bound on the expected time for some process to reach its critical region, in Lehmann and Rabin's Dining Philosophers algorithm.

0 citations0 reviewsNo code linkedOpen access