We present inner bounds to the broadcast capacity region of two classes of information networks: Networks of Multiple Access Channels (MACs) and Networks of Deterministic Broadcast Channels (DBCs). Our achievability scheme is a separation based scheme consisting of a physical layer that involves “cleaning up” the constituent channels in the network to create a point-to-point wired overlay, and a network layer that involves routing over this wired overlay. It is shown that finding the optimal way to “clean-up” is equivalent to the problem of finding maximal flows in “polymatroidal” flow networks, an already solved problem. The resulting inner bounds are cut-set bounds evaluated over product input distributions and are tight for Networks of DBCs.

We define the “reordering channel” which approximates packet communication over multipath networks. We consider deterministic packet arrivals with finite horizon decoding of individual packets and analyze the error probability for a two stage coding scheme.

We consider the problem of scheduling jobs with given start and finish times over two classes of multi-user channels, namely Multiple Access Channels and Degraded Broadcast Channels, and derive necessary and sufficient conditions for feasible scheduling of the jobs.

We study packet streaming over an erasure channel with delayed feedback. We consider the lag in playback between the sender and the receiver as the performance criterion and propose and analyze schemes to minimize the lag. We show that at lower delays in feedback, purely retransmission based schemes are better than random linear coding schemes and also analyze the tradeoff of the lag with the delay in feedback.

We consider the binary consensus problem where each node in the network initially observes one of two states and the goal for each node is to eventually decide which one of the two states was initially held by the majority of the nodes. Each node contacts other nodes and updates its current state based on the state communicated by the last contacted node. We assume that both signaling (the information exchanged at node contacts) and memory (computation state at each node) are limited and restrict our attention to systems where each node can contact any other node (i.e., complete graphs). It is well known that for systems with binary signaling and memory, the probability of reaching incorrect consensus is equal to the fraction of nodes that initially held the minority state. We show that extending both the signaling and memory by just one state dramatically improves the reliability and speed of reaching the correct consensus. Specifically, we show that the probability of error decays exponentially with the number of nodes N and the convergence time is logarithmic in N for large N. We also examine the case when the state is ternary and signaling is binary. The convergence of this system to consensus is again shown to be logarithmic in N for large N, and is therefore faster than purely binary systems. The type of distributed consensus problems that we study arises in the context of decentralized peer- to-peer networks, e.g. sensor networks and opinion formation in social networks - our results suggest that robust and efficient protocols can be built with rather limited signaling and memory.

We consider source coding over Aref networks. In particular we consider the following two problems: (i) multicasting correlated sources to a set of receivers, (ii) broadcasting sources to their respective receivers. For the first problem we show necessary and sufficient conditions for reliable multicast. For the second problem we show sufficient conditions for reliable broadcast. We further show that these conditions are also necessary when the sources are independent.

We provide bounds to the rate distortion tradeoff of the binary Markov source with the Hamming distance as the distortion measure. The tradeoff has been completely characterized by Gray (1970) for distortions less than a critical value Dc. Our motivation is to examine the tradeoff for values of distortion above Dc. Our inner bound to the tradeoff follows from an achievable scheme that uses conditional codebooks based on decision feedback at the encoder. Our outer bound follows from an extension of the technique of Berger (1977)

This paper provides an inner bound to the rate- distortion region of a source coding setup in which two encoders are allowed some collaboration to describe a pair of discrete memoryless sources. We further require some robustness in case one of the encoders breaks down. This is modeled by having a second decoder, observing the messages from only one of the encoders. We prove the tightness of this inner bound for two special cases. In the first, one of the sources is required to be recovered losslessly if there is no encoder breakdown. In the second, the robustness requirement is dropped and only one of the sources is to be represented. For the second case, we explicitly compute the rate-distortion region for the quadratic Gaussian and binary Hamming problems.