The Lightning Network (LN) utilizes gossip to share network topology, channel announcements and updates, and node announcements among its local constituents. Yet, our measurements show that this flooding-based gossip reconciliation is fundamentally inefficient. We propose, instead, to use set reconciliation protocols for sharing this information, and we systematically evaluate existing approaches under realistic network conditions. We further propose ADAPTIVEIBLT, a novel adaptive IBLT (Invertible Bloom Lookup Table) protocol with a partial-decoding enhancement. By simulating reconciliation in Core-Lightning and evaluating real gossip snapshots, we demonstrate the practical benefits of reconciliation in scaling gossip reconciliation from hours down to a few minutes.

Synchronization of transaction pools (mempools) has shown potential for improving the performance and block propagation delay of state-of-the-art blockchains. Indeed, various heuristics have been proposed in the literature to this end, all of which incorporate exchanges of unconfirmed transactions into their block propagation protocol. In this work, we take a different approach, maintaining transaction synchronization outside (and independently) of the block propagation channel. In the process, we formalize the synchronization problem within a graph theoretic framework and introduce a novel algorithm (SREP - Set Reconciliation-Enhanced Propagation) with quantifiable guarantees. We analyze the algorithm's performance for various realistic network topologies, and show that it converges on any connected graph in a number of steps that is bounded by the diameter of the graph. We confirm our analytical findings through extensive simulations that include comparison with MempoolSync, a recent approach from the literature. Our simulations show that SREP incurs reasonable overall bandwidth overhead and, unlike MempoolSync, scales gracefully with the size of the network.

In the set reconciliation problem, remote parties seek to reconcile similar sets of data according to an efficiency objective, such as minimizing communication or computation. Though investigated for many individual distributed applications, this problem still lacks a holistic treatment, and this is the aim of this work. Specifically, we design and analyze GenSync, a unified set reconciliation framework that incorporates several state-of-the-art set reconciliation protocols with an integrated testbed. We compare and analyze the various protocols and offer general guidelines for selecting a good protocol for a given application. Through extensive experiments, we demonstrate that the optimal choice of protocol is highly sensitive to several parameters, including network properties (e.g., bandwidth and latency) and computing power. Notably, none of our framework’s protocols are universally dominant under diverse conditions, and a poor protocol choice may lead to a 5x hit in performance. To demonstrate our framework, we measure the effects of protocol choice in reconciling memory pools of adjacent Bitcoin nodes.

Block relay protocols play a key role in the performance and security of public blockchains. As a result, several such protocols have been deployed in the context of Bitcoin and its variants (e.g., legacy, compact block relay and Graphene) in an attempt to reduce bandwidth utilization. However, the relative performance of these protocols in realistic networking conditions (e.g., with nodes churning - joining and leaving the network) is still not known. This paper aims to fill this key knowledge gap using an experimental testbed of twelve full nodes connected to the Bitcoin Cash blockchain. With the aid of novel logging tools, we contrast the performance of these three protocols, in realistic scenarios, with respect to communication, delay, and block decoding success. Our main findings are that Graphene generally performs the best when nodes remain connected, boasting an average propagation delay of 190 ms (i.e., 29% lower than compact block and 80% lower than the legacy protocol). However, when nodes churn at a high rate, compact blocks may perform better. Through a careful temporal analysis, we identify some root causes of the protocol inefficiencies, together with potential mitigation. We have made our measurement framework and experimental logs publicly available to the broader research community.

Orphan transactions are those whose parental income sources are missing at the time that they are processed. These transactions typically languish in a local buffer until they are evicted or all their parents are discovered, at which point they may be propagated further. To date, there has been little work in the literature on characterizing the nature and impact of such orphans, and yet it is intuitive that they should affect the performance of the Bitcoin network. This work thus seeks to methodically research such effects through a measurement campaign on live Bitcoin nodes. Our data show that about 45% of orphan transactions end up being included in the blockchain. Surprisingly, orphan transactions tend to have fewer parents on average than non-orphan transactions, and their missing parents have a lower fee, larger size, and lower transaction fee per byte than all other received transactions. Moreover, the network overhead incurred by these orphan transactions can be significant, exceeding 17% when using the default orphan memory pool size (i.e., 100 transactions), although this overhead can be made negligible, without significant computational or memory demands, if the pool size is simply increased to 1000 transactions. Finally, we show that when a node with an empty mempool first joins the network, 25% of the transactions that it receives become orphan, whereas in steady-state this quantity drops to about 1%.

Efficient and reliable propagation of blocks is vital to the scalability of the Bitcoin network. As a result, several schemes, such as the compact block protocol (BIP 152), have been proposed over the last few years to speed up the block propagation. Even so, we provide experimental evidence that (i) the vast majority (97%) of Bitcoin nodes exhibit only intermittent network connectivity (i.e., churn), and (ii) this churn results in significant number of unsuccessful compact blocks, roughly three times the statistic for continuously connected nodes. We conduct experiments on the Bitcoin network that show that churn results in a roughly five fold increase in block propagation time (i.e., 566.89 ms vs. 109.31 ms) on average. To effect our analysis, we develop a statistical model for churn, based on empirical network data, and use this model to actuate live test nodes on the Bitcoin network. The performance of the system is measured within a novel framework that we developed for logging the internal behavior of a Bitcoin node, and which we share for public use. Finally, to mitigate the problem of missing transactions in churning nodes, we propose and implement into Bitcoin Core a new synchronization protocol, dubbed MempoolSync. Our measurements show that churning nodes implementing MempoolSync experience significantly better performance than standard nodes not implementing MempoolSync, including average block propagation delay reduced by over 50%.

We present a new side-channel attack that targets one of the most fundamental software caches in modern computer systems: the operating system page cache. The page cache is a pure software cache that contains all disk-backed pages, including program binaries, shared libraries, and other files. On Windows, dynamic pages are also part of this cache and can be attacked as well, e.g., data, heap, and stacks. Our side channel permits unprivileged monitoring of accesses to these pages of other processes, with a spatial resolution of 4kB and a temporal resolution of 2µs on Linux (≤6.7 measurements per second), and 466ns on Windows 10 (≤223 measurements per second). We systematically analyze the side channel by demonstrating different hardware-agnostic local attacks, including a sandbox-bypassing high-speed covert channel, an ASLR break on Windows 10, and various information leakages that can be used for targeted extortion, spam campaigns, and more directly for UI redressing attacks. We also show that, as with hardware cache attacks, we can attack the generation of temporary passwords on vulnerable cryptographic implementations. Our hardware-agnostic attacks can be mitigated with our proposed security patches, but the basic side channel remains exploitable via timing measurements. We demonstrate this with a remote covert channel exfiltrating information from a colluding process through innocuous server requests.

We consider the disk cache (file-system cache) information channel, and show how it can be exploited on various systems to yield potentially sensitive information. Our approach can be used locally by an unprivileged adversary to detect whether another user is writing to disk, and if so, the rate at which data is being written. Further, we also show how an attacker can detect whether specific files have been recently accessed by the victim. We then extend this attack to remote access through a web server, using timing analysis to identify recent access of chosen pages.

Abstract Modern mobile devices place a wide variety of sensors and services within the personal space of their users. As a result, these devices are capable of transparently monitoring many sensitive aspects of these users’ lives (e.g., location, health, or correspondences). Users typically trade access to this data for convenient applications and features, in many cases without a full appreciation of the nature and extent of the information that they are exposing to a variety of third parties. Nevertheless, studies show that users remain concerned about their privacy and vendors have similarly been increasing their utilization of privacy-preserving technologies in these devices. Still, despite significant efforts, these technologies continue to fail in fundamental ways, leaving users’ private data exposed. In this work, we survey the numerous components of mobile devices, giving particular attention to those that collect, process, or protect users’ private data. Whereas the individual components have been generally well studied and understood, examining the entire mobile device ecosystem provides significant insights into its overwhelming complexity. The numerous components of this complex ecosystem are frequently built and controlled by different parties with varying interests and incentives. Moreover, most of these parties are unknown to the typical user. The technologies that are employed to protect the users’ privacy typically only do so within a small slice of this ecosystem, abstracting away the greater complexity of the system. Our analysis suggests that this abstracted complexity is the major cause of many privacy-related vulnerabilities, and that a fundamentally new, holistic, approach to privacy is needed going forward. We thus highlight various existing technology gaps and propose several promising research directions for addressing and reducing this complexity.

One key requirement for fountain (rateless) coding schemes is to achieve a high intermediate symbol recovery rate. Recent coding schemes have incorporated the use of a feedback channel to improve the intermediate performance of traditional rateless codes; however, these codes with feedback are designed based on uniformly at random selection of input symbols. In this paper, on the other hand, we develop feedback-based fountain codes with dynamically adjusted nonuniform symbol selection distributions, and show that this characteristic can enhance the intermediate decoding rate. We provide an analysis of our codes, including bounds on computational complexity and failure probability for a maximum likelihood decoder; the latter is tighter than bounds known for classical rateless codes. Through numerical simulations, we also show that the feedback information paired with a nonuniform selection distribution can highly improve the symbol recovery rate, and that the amount of feedback sent can be tuned to the specific transmission properties of a given feedback channel.

We propose a novel transport protocol that incorporates a light-weight acknowledgment (ACK) into a rateless coding framework, resulting in a protocol that provides more reliability than the User Datagram Protocol (UDP) and higher throughput than the Transmission Control Protocol (TCP) under lossy and dynamic channel conditions. Unlike traditional ACKs, which acknowledge the reception of individual (possibly encoded) symbols, our ACKs acknowledge the complete decoding of the symbols. This subtle modification permits us to dynamically adjust rateless encoding in order to naturally track decoder progress, regardless of channel conditions. We provide simulation and an analysis of our protocol, including an upper bound on failure probability for a maximum likelihood decoder, which is tighter than bounds known for classical rateless codes. Our protocol can be implemented directly on top of UDP, without requiring changes to the underlying network stack implementations.

We present TeaCP, a prototype toolkit for the evaluation and analysis of collection protocols in both simulation and experimental environments running on TinyOS. Our toolkit consists of a testing system, which runs a collection protocol of choice, and an optional SD card-based logging system, which stores the logs generated by the testing system. The SD card datalogger allows a wireless sensor network (WSN) to be deployed flexibly in various environments, especially where wired transfer of data is difficult. Using the saved logs, TeaCP evaluates a wide range of performance metrics, such as reliability, throughput, and delay. TeaCP further allows visualization of packet routes and the topology evolution of the network, under both static and dynamic conditions, even in the face of transient disconnections. Through simulation of an intra-car WSN and real lab experiments, we demonstrate the functionality of TeaCP for comparing the performance of two prominent collection protocols, the Collection Tree Protocol (CTP) and the Backpressure Collection Protocol (BCP). We also present the usage of TeaCP as a high level diagnosis tool, through which an inconsistency of the BCP implementation for the CC2420 radio chips is identified and resolved.

Determining whether an unordered collection of overlapping substrings (called shingles) can be uniquely decoded into a consistent string is a problem common to a broad assortment of disciplines ranging from networking and information theory through cryptography and even genetic engineering and linguistics. We present a new insight that yields an efficient streaming algorithm for determining whether a string of n characters over the alphabet Σ can be uniquely decoded from its two-character shingles; our online algorithm achieves an overall time complexity Θ(n+|Σ|) and space complexity O(|Σ|). As a motivating application, we demonstrate how this algorithm can be adapted to larger, varying-size shingles for (empirically) efficient string reconciliation.

We experimentally investigate the benefits of multi- hop networking for intra-car data aggregation under the current state-of-the-art Collection Tree Protocol (CTP). We show how this protocol actively adjusts collection routes according to channel dynamics in various practical car environments, resulting in performance gains over single-hop aggregation. Throughout our experiments, we target traditional performance metrics such as delivery rate, number of transmissions per packet, and delay, and our results confirm, both qualitatively and quantitatively, that multi-hop communication can provide a reliable and robust approach for data collection within a car.

We consider the problem of reconciling two remote strings of arbitrary and unknown similarity using minimum communication, which is at the core of some important problems in networking, cryptography, genetic engineering, and even linguistics. Though this problem is efficiently convertible into a set reconciliation instance, for which efficient solutions exist, this conversion may introduce ambiguity in the decoding process, which may require significant communication and computational resources to resolve. We leverage some recent advances in efficient unique decodability of strings to reduce decoding ambiguity, and thus pave the way for a practical implementation of this string reconciler. For certain random strings and in some ideal cases, our approach reconciles two length n strings that differ in α edits (with α not known a priori) using O (α log2(n)) communication.

We consider the problem of generating a connected identifying code for an arbitrary graph. After a brief motivation, we show that the decision problem regarding the existence of such a code is NP-complete, and we propose a novel polynomial-time approximation ConnectID that transforms any identifying code into a connected version of at most twice the size, thus leading to an asymptotically optimal approximation bound. When the input identifying code to is robust to graph distortions, we show that the size of the resulting connected code is related to the best error-correcting code of a given minimum distance, permitting the use of known coding bounds. In addition, we show that the size of the input and output codes converge for increasing robustness, meaning that highly robust identifying codes are almost connected. Finally, we evaluate the performance ConnectID of on various random graphs. Simulations for Erdos-Rényi random graphs show that the connected codes generated are actually at most 25% larger than their unconnected counterparts, while simulations with robust input identifying codes confirm that robustness often provides connectivity for free.

We examine the problem of minimizing feedback in reliable wireless broadcasting by pairing rateless coding with extreme value theory. Our key observation is that, in a broadcast environment, this problem resolves into estimating the maximum number of packets dropped among many receivers rather than for each individual receiver. With rateless codes, this estimation relates to the number of redundant transmissions needed at the source in order for all receivers to correctly decode a message with high probability. We develop and analyze two new data dissemination protocols, called Random Sampling (RS) and Full Sampling with Limited Feedback (FSLF), based on the moment and maximum likelihood estimators in extreme value theory. Both protocols rely on a single-round learning phase, requiring the transmission of a few feedback packets from a small subset of receivers. With fixed overhead, we show that FSLF has the desirable property of becoming more accurate as the receivers' population gets larger. Our protocols are channel-agnostic, in that they do not require a priori knowledge of (i.i.d.) packet loss probabilities, which may vary among receivers. We provide simulations and an improved full-scale implementation of the Rateless Deluge over-the-air programming protocol on sensor motes as a demonstration of the practical benefits of our protocols, which translate into about 30% latency and energy consumption savings. Furthermore, we apply our protocols to real-time (RT) oblivious rateless codes in broadcast settings. Through simulations, we demonstrate a 100-fold reduction in the amount of feedback packets while incurring an increase of only 10%–20% in the number of encoded packets transmissions.

No abstract available.

Our project demonstrates the capabilities of a symbiotic phone-robot hybrid device, wherein the robot provides gross motor control and the phone provides fine course corrections and sensing capability. The crude robot generates movement subject to mechanical wheel asymmetries and non-linear motor effects; the inexpensive phone provides a variety of on-board sensors and a reasonably powerful CPU/memory. We demonstrate the utility of the combined device to provide a reasonably accurate autonomous signal mapping on an untrained floor plan in our building.

Identifying codes have been proposed as an abstraction for implementing monitoring tasks such as indoor localization using wireless sensor networks. In this approach, sensors' radio coverage overlaps in unique ways over each identifiable region, according to the codewords of an identifying code. While connectivity of the underlying identifying code is necessary for routing data to a sink, existing algorithms that produce identifying codes do not guarantee such a property. As such, we propose a novel polynomial-time algorithm called ConnectID that transforms any identifying code into a connected version that is also an identifying code and is provably at most twice the size of the original. We evaluate the performance of ConnectID on various random graphs, and our simulations show that the connected codes generated are actually at most 25% larger than their non-connected counterparts.

We examine the problem of minimizing feedbacks in reliable wireless broadcasting, by pairing rateless coding with extreme value theory. Our key observation is that, in a broadcast environment, this problem resolves into estimating the maximum number of packets dropped among many receivers rather than for each individual receiver. With rateless codes, this estimation relates to the number of redundant transmissions needed at the source in order for all receivers to correctly decode a message with high probability. We develop and analyze two new data dissemination protocols, called Random Sampling (RS) and Full Sampling with Limited Feedback (FSLF), based on the moment and maximum likelihood estimators in extreme value theory. Both protocols rely on a single-round learning phase, requiring the transmission of a few feedback packets from a small subset of receivers. With fixed overhead, we show that FSLF has the desirable property of becoming more accurate as the receivers's population gets larger. Our protocols are channel agnostic, in that they do not require a-priori knowledge of (i.i.d.) packet loss probabilities, which may vary among receivers. We provide simulations and an improved full-scale implementation of the Rateless Deluge over-the-air programming protocol on sensor motes as a demonstration of the practical benefits of our protocols, which translate into about 30% latency and energy consumption savings.

The erasure resilience of rateless codes, such as Luby-Transform (LT) codes, makes them particularly suitable to a wide variety of loss-prone wireless and sensor network applications, ranging from digital video broadcast to software updates. Yet, traditional rateless codes usually make no use of a feedback communication channel, a feature available in many wireless settings. As such, we generalize LT codes to situations where receiver(s) provide feedback to the broadcaster. Our approach, referred to as Shifted LT (SLT) code, modifies the robust soliton distribution of LT codes at the broadcaster, based on the number of input symbols already decoded at the receivers. While implementing this modification entails little change to the LT encoder and decoder, we show both analytically and through real experiments, that it achieves significant savings in communication complexity, memory usage, and overall energy consumption. Furthermore, we show that significant savings can be even achieved with a low number of feedback messages (on the order of the square root of the total number of input symbols) transmitted at a uniform rate. The practical benefits of Shifted LT codes are demonstrated through the implementation of a real over-the-air programming application for sensor networks, based on the Deluge protocol.

Over-the-air programming (OAP) is a fundamental service in sensor networks that relies upon reliable broadcast for efficient dissemination. As such, existing OAP protocols become decidedly inefficient (with respect to energy, communication or delay) in unreliable broadcast environments, such as those with relatively high node density or noise. In this paper, we consider OAP approaches based on rateless codes, which significantly improve OAP in such environments by drastically reducing the need for packet rebroadcasting. We thus design and implement two rateless OAP protocols, rateless Deluge and ACKless Deluge, both of which replace the data transfer mechanism of the established OAP Deluge protocol with rateless analogs. Experiments with Tmote Sky motes on single-hop networks with packet loss rates of 7% show these protocols to save significantly in communication over regular Deluge (roughly 15-30% savings in the data plane, and 50-80% in the control plane), and multi-hop experiments reveal similar trends. Simulations further shows that our new protocols scale better than standard Deluge (in terms of communication and energy) to high network density. TinyOS code for our implementation can be found at http://nislab.bu.edu.

The identifying code problem for a given graph involves finding a minimum set of vertices whose neighborhoods uniquely overlap at any given graph vertex. Initially introduced in 1998, this problem has demonstrated its fundamental nature through a wide variety of applications, such as fault diagnosis, location detection, and environmental monitoring, in addition to deep connections to information theory, superimposed and covering codes, and tilings. This work establishes efficient reductions between the identifying code problem and the well-known set-covering problem, resulting in a tight hardness of approximation result and novel, provably tight polynomial-time approximations. The main results are also extended to$r$-robustidentifying codes and analogousset$(2r+1)$-multicoverproblems. Finally, empirical support is provided for the effectiveness of the proposed approximations, including good constructions for well-known topologies such as infinite two-dimensional grids.

Wireless Sensor Networks (WSNs) provide an important means of monitoring the physical world, but their limitations present challenges to fundamental network services such as routing. In this work we utilize an abstraction of WSNs based on the theory of identifying codes. This abstraction has been useful in recent literature for a number of important monitoring problems, such as localization and contamination detection. In our case, we use it to provide a joint infrastructure for efficient and robust monitoring and routing in WSNs. Specifically, we provide an efficient and distributed algorithm for generating robust identifying codes with a logarithmic performance guarantee based on a novel reduction to the set k-multicover problem; to the best of our knowledge, this is the first such guarantee for the robust identifying codes problem, which is known to be NP-hard. We also show how this same identifying-code infrastructure provides a natural labeling that can be used for near-optimal routing with very small routing tables. We provide experimental results for various topologies that illustrate the superior performance of our approximation algorithms over previous identifying code heuristics.

We analyze the performance limits of data dissemination with multi-channel, single radio sensors. We formulate the problem of minimizing the average delay of data dissemination as a stochastic shortest path problem and show that, for an arbitrary topology network, an optimal control policy can be found in a finite number of steps, using value iteration or Dijsktra's algorithm. However, the computational complexity of this solution is generally prohibitive. We thus focus on two special classes of network topologies of practical interest, namely single-hop clusters and multi-hop cluster trees. For these topologies, we derive the structure of policies that achieve an average delay within a factor 1 + e of the optimal average delay, in networks with large number of nodes. Through simulation, we show that these policies perform close to optimal even for networks with small and moderate numbers of nodes. Our analysis and simulations reveal that multichannel data dissemination policies lead to a drastic reduction in the average delay, up to a factor as large as the total number of channels available, even though each node can communicate over only one channel at any point of time. Finally, we present the foundations of a methodology, based on extreme value theory, allowing the implementation of our near-optimal dissemination policies with minimal overhead.

We consider the problem of efficiently broadcasting incremental updates to multiple terminals that contain outdated (and possibly different) initial copies of the data. This situation occurs, for example, with the broadcast of Short Messaging Service [SMS] or Multimedia Messaging Service [MMS] cellphone messages to various clients whose phones are sometimes unavailable. We propose an efficient protocol for effecting such broadcast based on a novel combination of recent work on rate less coding and set reconciliation. Our approach is non-interactive, in that terminal nodes need not send any messages to the source, and stateless, in that the source need not know (or store) any information about the terminals. It also minimizes communication complexity and energy expenditure at the terminal nodes, at the expense of added computation. In support of our work, we provide several energy usage measurements on MICA2 sensor motes that clearly highlight the advantages of random linear decoding over wholesale data transfer.

We propose a peer-to-peer architecture designed to overcome asymmetries in upload/download speeds that are typical in end-user dialup, broadband and cellular wireless Internet connections. Our approach allows users at remote locations to access information stored on their home computers at rates often exceeding their home connection’s upload capacity. The key to this approach is to share file data when communications are idle using random linear coding, so that, when needed, an end-user can download a file from several sources at a higher data rate than his home computer’s upload capacity. We prove that our proposed system is asymptotically fair, in that (even malicious) users are proportionally assigned idle bandwidth depending on how much bandwidth they contribute, and that there is a natural incentive to join and cooperate fairly in the system. In addition, our approach provides cryptographic security and geographic data robustness to the participating peers.

We consider the problem of approximating the number of differences between sets held on remote hosts using minimum communication. Efficient solutions to this problem are important for streamlining a variety of communication sensitive network applications, including data synchronization in mobile networks, gossip protocols and content delivery networks. Using tools from the field of interactive communication, we show that this problem requires about as much communication as the problem of exactly determining such differences. As a result, we propose a heuristic solution based on the counting Bloom filter. We provide analytic bounds on the expected performance of our protocol and also experimental evidence that they can outperform existing difference approximation techniques.

This paper discusses the use of rateless codes to increase performance in wireless sensor networks.

Of considerable interest in recent years has been the problem of exchanging correlated data with minimum communication. We thus consider the problem of exchanging two similar strings held by different hosts. Our approach involves transforming a string into a multiset of substrings that are reconciled efficiently using known multiset reconciliation algorithms, and then put back together on a remote host using tools from graph theory. We present analyses, experiments, and results to show that the communication complexity of our approach for high-entropy data compares favorably to existing algorithms including rsync, a widely-used string reconciliation engine. We also quantify the trade-off between communication and the computation complexity of our approach

Identifying codes have been used in a variety of applications, including sensor-based wireless location detection in harsh environments. In such applications, a user determines his location through a unique signature (i.e. a codeword in an identifying code) based on sensor transmissions that he can hear. Adding sensors to such a system can increase its robustness at the expense of added signal interference and, consequently, decreased reliability. In this work we propose and develop an alternate approach to maintaining robustness and reliability through the use of "disjoint identifying codes", which reduces inter-sensor interference by dividing a system into physically separate and independent location determining sub-systems. We provide information-theoretic upper and lower bounds on the number of such sub-systems for a given connectivity graph, and we show that these bounds are asymptotically tight for a modification of Hadamard matrices

We consider the problem of exchanging two similar strings held by different hosts with a minimum amount of communication. We reduce the problem of string reconciliation to a problem of multi-set reconciliation, for which nearly optimal solutions exist. Our approach involves transforming a string into a multi-set of substrings, which are reconciled efficiently and then put back together on a remote host using recent graph-theoretic results. We present an analysis of our algorithm to show that its communication complexity compares favorably to two existing methods for string reconciliation.

We propose a novel framework for location detection with sensor networks, based on the theory of identifying codes. The key idea of this approach is to allow sensor coverage areas to overlap so that each resolvable position is covered by a unique set of sensors. In this setting, determining a sensor-placement with a minimum number of sensors is equivalent to constructing an optimal identifying code, an NP-complete problem in general. We, thus, propose and analyze new polynomial-time algorithms for generating irreducible (but not necessarily optimal) codes for arbitrary topologies. Our algorithms incorporate robustness properties that are critically needed in harsh environments. We further introduce distributed versions of these algorithms, allowing sensors to self-organize and determine a (robust) identifying code without any central coordination. Through analysis and simulation, we show that our algorithms produce nearly optimal solutions for a wide range of parameters. In addition, we demonstrate a tradeoff between system robustness and the number of active sensors (which is related to the expected lifetime of the system). Finally, we present experimental results, obtained on a small testbed, that demonstrate the feasibility of our approach.

We propose a new framework for providing robust location detection in emergency response systems, based on the theory of identifying codes. The key idea of this approach is to allow sensor coverage areas to overlap in such a way that each resolvable position is covered by a unique set of sensors. In this setting, determining a sensor-placement with a minimum number of sensors is equivalent to constructing an optimal identifying code, an NP-complete problem in general. We thus propose and analyze a new polynomial-time algorithm for generating irreducible codes for arbitrary topologies. We also generalize the concept of identifying codes to incorporate robustness properties that are critically needed in emergency networks and provide a polynomial-time algorithm to compute irreducible robust identifying codes. Through analysis and simulation, we show that our approach typically requires significantly fewer sensors than existing proximity-based schemes. Alternatively, for a fixed number of sensors, our scheme can provide robustness in the face of sensor failures or physical damage to the system.

We show that there are no full-rank tilings of $\mathbb{F}^8_{\kern -1pt 2}$, using a carefully designed exhaustive search. This solves an open problem posed in [T. Etzion and A. Vardy, SIAM J. Discrete Math., 11 (1998), pp. 205--233]. This also implies that a full-rank perfect binary code of length 15 with a kernel of dimension 7 does not exist.

We consider the problem of data reconciliation, which we model as two separate multisets of data that must be reconciled with minimum communication. Under this model, we show that the problem of reconciliation is equivalent to a variant of the graph coloring problem and provide consequent upper and lower bounds on the communication complexity of reconciliation. Further, we show by means of an explicit construction that the problem of reconciliation is, under certain general conditions, equivalent to the problem of finding error-correcting codes for a general class of errors. Under this equivalence, reconciling with little communication is linked to codes with large size, and vice versa. We show analogous results for the problem of multiset verification, in which we wish to determine whether two multisets are equal using minimum communication. As a result, a wide body of literature in coding theory may be applied to the problems of reconciliation and verification.

We consider the problem of efficiently reconciling two similar sets held by different hosts while minimizing the communication complexity, which we call the set reconciliation problem. We describe an approach to set reconciliation based on a polynomial encoding of sets. The resulting protocols exhibit tractable computational complexity and nearly optimal communication complexity when the sets being reconciled are sparse. Also, these protocols can be adapted to work over a broadcast channel, allowing many clients to reconcile with one host based on a single broadcast, even if each client is missing a different subset.

Modern personal digital assistant (PDA) architectures often utilize a wholesale data transfer protocol known as "slow sync" for synchronizing PDAs with personal computers (PCs). This approach is markedly inefficient with respect to bandwidth usage, latency, and energy consumption since the PDA and PC typically share many common records. We propose, analyze, and implement a novel PDA synchronization scheme (CPIsync) predicated upon previous information-theoretic research. The salient property of this scheme is that its communication complexity depends on the number of differences between the PDA and PC, and is essentially independent of the overall number of records. Moreover, our implementation shows that the computational complexity and energy consumption of CPIsync is practical and that the-overall latency is typically much smaller than that of slow sync or alternative synchronization approaches based on Bloom (1970) filters. Thus, CPIsync has potential for significantly improving synchronization protocols for PDAs and, more generally, for heterogeneous networks of many machines.

Modern personal digital assistant (PDA) architectures often utilize a wholesale data transfer protocol known as "slow sync" for synchronizing PDAs with personal computers (PCs). This approach is markedly inefficient with respect to bandwidth usage and latency, since the PDA and PC typically share many common records. We propose, analyze, and implement a novel PDA synchronization scheme (CPIsync - characteristic polynomial interpolation-based synchronization) predicated upon recent information-theoretic research. The salient property of this scheme is that its communication complexity depends on the number of differences between the PDA and PC, and is essentially independent of the overall number of records. Moreover, our implementation shows that the computational complexity of CPIsync is practical, and that the overall latency is typically much smaller than that of slow sync. Thus, CPIsync has potential for significantly improving synchronization protocols for PDAs and, more generally, for heterogeneous networks of many machines.

We generalize constructions of lexicographic codes to produce locally optimal codes with a desired trellis decoding complexity. These constructions are efficient for high-rate codes and provide a means for automated code design. As a byproduct, we improve known bounds on the parameters of lexicodes.

If a linear block code C of length n has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes. Specifically, let C be an (n,k,d) linear code of rate R=k/n that can be represented by a Tanner graph without cycles. We prove that if R/spl ges/0.5 then d/spl les/2, while if R<0.5 then C is obtained from a code of rate /spl ges/0.5 and distance /spl les/2 by simply repeating certain symbols. In the latter case, we prove that d/spl les/[n/k+1]+[n+1/k+1]<2/R. Furthermore, we show by means of an explicit construction that this bound is tight for all values of n and k. We also prove that binary codes which have cycle-free Tanner graphs belong to the class of graph-theoretic codes, known as cut-set codes of a graph. Finally, we discuss the asymptotics for Tanner graphs with cycles, and present a number of open problems for future research.