Peer-to-peer (P2P) overlay networks such as BitTorrent and Avalanche are increasingly used for disseminating potentially large files from a server to many end users via the Internet. The key idea is to divide the file into many equally-sized parts and then let users download each part (or, for network coding based systems such as Avalanche, linear combinations of the parts) either from the server or from another user who has already downloaded it. However, their performance evaluation has typically been limited to comparing one system relative to another and typically been realized by means of simulation and measurements. In contrast, we provide an analytic performance analysis that is based on a new uplink-sharing version of the well-known broadcasting problem. Assuming equal upload capacities, we show that the minimal time to disseminate the file is the same as for the simultaneous send receive version of the broadcasting problem. For general upload capacities, we provide a mixed integer linear program (MILP) solution and a complementary fluid limit solution. We thus provide a lower bound which can be used as a performance benchmark for any P2P file dissemination system. We also investigate the performance of a decentralized strategy, providing evidence that the performance of necessarily decentralized P2P file dissemination systems should be close to this bound and therefore that it is useful in practice.
The simultaneous send receive model @cite_3 supposes that during each round every user may receive one message and send one message. Unlike the telephone model, it is not required that a user can send a message only to the same user from which it receives a message. The optimal number of rounds turns out to be @math and we will return to this result in Section .
@cite_3
2138489200
We consider the problem of broadcasting multiple messages from one processor to many processors in telephone-like communication systems. In such systems, processors communicate in rounds, where in every round, each processor can communicate with exactly one other processor by exchanging messages with it. Finding an optimal solution for this problem was open for over a decade. In this paper, we present an optimal algorithm for this problem when the number of processors is even. For an odd number of processors, we provide an algorithm which is within an additive term of 3 of the optimum. A by-product of our solution is an optimal algorithm for the problem of broadcasting multiple messages for any number of processors in the simultaneous send receive model. In this latter model, in every round, each processor can send a message to one processor and receive a message from another processor. We study the communication complexity of rumor spreading in the random phone-call model. Suppose nplayers communicate in parallel rounds, where in each round every player calls a randomly selected communication partner. A player u is allowed to exchange messages during a round only with the player that u called, and with all the players that @math received calls from, in that round. In every round, a (possibly empty) set of rumors to be distributed among all players is generated, and each of the rumors is initially placed in a subset of the players. Karp et. al Karp2000 showed that no rumor-spreading algorithm that spreads a rumor to all players with constant probability can be both time-optimal, taking O(lg n) rounds, and message-optimal, using O(n) messages per rumor. For address-oblivious algorithms, in particular, they showed that Ω(n lg lg n) messages per rumor are required, and they described an algorithm that matches this bound and takes O(lg n) rounds. We investigate the number of communication bits required for rumor spreading. On the lower-bound side, we establish that any address-oblivious algorithm taking O(lg n) rounds requires Ω(n (b+ lg lg n)) communication bits to distribute a rumor of size b bits. On the upper-bound side, we propose an address-oblivious algorithm that takes O(lg n) rounds and uses O(n(b+ lg lg n lg b)) bits. These results show that, unlike the case for the message complexity, optimality in terms of both the running time and the bit communication complexity is attainable, except for very small rumor sizes b In a secure message transmission (SMT) scenario, a sender wants to send a message in a private and reliable way to a receiver. Sender and receiver are connected by n wires, t of which can be controlled by an adaptive adversary with unlimited computational resources. In Eurocrypt 2008, Garay and Ostrovsky considered an SMT scenario where sender and receiver have access to a public discussion channel and showed that secure and reliable communication is possible when n ≥ t + 1. In this paper, we will show that a secure protocol requires at least three rounds of communication and two rounds invocation of the public channel and hence give a complete answer to the open question raised by Garay and Ostrovsky. We also describe a round optimal protocol that has constant transmission rate over the public channel. In the problem of secure message transmission in the public discussion model (SMT-PD), a sender wants to send a message MS ∈ 0,1 l to a receiver privately and reliably. Sender and receiver are connected by n channels, also known as simple wires, up to of which may be maliciously controlled by a computationally unbounded adversary, as well as one public channel, which is reliable but not private. The SMT-PD abstraction has been shown instrumental in achieving secure multiparty computation on sparse networks, where a subset of the nodes are able to realize a broadcast functionality, which plays the role of the public channel. In this paper, we present the first SMT-PD protocol with sublinear (i.e., logarithmic in l, the message length) communication on the public channel. In addition, the protocol incurs a simple-wire communication complexity of O(ln n-t), which, as we also show, is optimal. By contrast, the best known bounds in both public and simple channels were linear. Furthermore, our protocol has an optimal round complexity of (3, 2), meaning three rounds, two of which must invoke the public channel. Finally, we ask the question whether some of the lower bounds on resource use for a single execution of SMT-PD can be beaten on average through amortization. In other words, if sender and receiver must send several messages back and forth (where later messages depend on earlier ones), can they do better than the naive solution of repeating an SMT-PD protocol each time? We show that amortization can indeed drastically reduce the use of the public channel; it is possible to limit the total number of uses of the public channel to two, no matter how many messages are ultimately sent between two nodes. (Since two uses of the public channel are required to send any reliable communication whatsoever, this is the best possible.). We propose a protocol (called RBO) for broadcasting long streams of single-packet messages over radio channel for tiny, battery powered, receivers. The messages are labeled by the keys from some linearly ordered set. The sender repeatedly broadcasts a sequence of many (possibly millions) of messages, while each receiver is interested in reception of a message with a specified key within this sequence. The transmission is arranged so that the receiver can wake up in arbitrary moment and find the nearest transmission of its searched message. Even if it does not know the position of the message in the sequence, it needs only to receive a small number of (the headers of) other messages to locate it properly. Thus it can save energy by keeping the radio switched off most of the time. We show that bit-reversal permutation has "recursive bisection properties" and, as a consequence, RBO can be implemented very efficiently with only constant number of @math -bit variables, where @math is the total number of messages in the sequence. The total number of the required receptions is at most @math in the model with perfect synchronization. The basic procedure of RBO (computation of the time slot for the next required reception) requires only @math bit-wise operations. We propose implementation mechanisms for realistic model (with imperfect synchronization), for operating systems (such as e.g. TinyOS). We explore the fundamental limits of distributed balls-into-bins algorithms. We present an adaptive symmetric algorithm that achieves a bin load of two in log* n+O(1) communication rounds using O(n) messages in total. Larger bin loads can be traded in for smaller time complexities. We prove a matching lower bound of (1-o(1))log* n on the time complexity of symmetric algorithms that guarantee small bin loads at an asymptotically optimal message complexity of O(n). For each assumption of the lower bound, we provide an algorithm violating it, in turn achieving a constant maximum bin load in constant time. As an application, we consider the following problem. Given a fully connected graph of n nodes, where each node needs to send and receive up to n messages, and in each round each node may send one message over each link, deliver all messages as quickly as possible to their destinations. We give a simple and robust algorithm of time complexity O(log* n) for this task and provide a generalization to the case where all nodes initially hold arbitrary sets of messages. A less practical algorithm terminates within asymptotically optimal O(1) rounds. All these bounds hold with high probability. We argue that scalability in ad-hoc networks can be achieved by re-defining the functionality for the information transport system itself, where the functionality is driven by a new type of communication paradigm inherent in information dissemination applications. In particular, among the entire population of generated messages, each user desires only that the personally “most interesting” messages are delivered to them — we call this “star-to-one” communication. In the paper we consider a “Zipf product form” model for message preferences, and propose some decentralized algorithms for message forwarding based on this model. We discuss some simulation results for these algorithms, which suggest that it is possible for the users to efficiently obtain the messages that are of most interest to them. Essentially, the amount of “work” required of each user, on the average, is proportional to the desired number of messages to be received by each user, and is independent of the number of users and the number of messages in the network. We study the degrees of freedom (DoF) of the @math -user interference channel with coordinated multipoint (CoMP) transmission and reception. Each message is jointly transmitted by @math successive transmitters, and is jointly received by @math successive receivers. We refer to this channel as the CoMP channel with a transmit cooperation order of @math and receive cooperation order of @math . Since the channel has a total of @math transmit antennas and @math receive antennas, the maximum possible DoF is equal to @math . We show that the CoMP channel has @math DoF if and only if @math . The key idea is that the zero forcing of the interference corresponding to the @math message at the decoder of the @math message, where @math , can be viewed as a shared responsibility between the @math transmitters carrying the @math message, and the @math receivers decoding the @math message. For the general case, we derive an outer bound that states that the DoF is bounded above by @math . For the special case with only CoMP transmission, i.e, @math , we propose a scheme that can achieve @math DoF for all @math K @math M_ t @math M_ t -1$ receivers, thereby allowing each of these receivers to enjoy 1 DoF, and asymptotic interference alignment is used to align the interfering signals at each other receiver to occupy half the signal space. The achievability proofs are based on the notion of algebraic independence from algebraic geometry. In their seminal work on authentication, Wegman and Carter propose that to authenticate multiple messages, it is sufficient to reuse the same hash function as long as each tag is encrypted with a one-time pad. They argue that because the one-time pad is perfectly hiding, the hash function used remains completely unknown to the adversary. Since their proof is not composable, we revisit it using a composable security framework. It turns out that the above argument is insufficient: if the adversary learns whether a corrupted message was accepted or rejected, information about the hash function is leaked, and after a bounded finite amount of rounds it is completely known. We show however that this leak is very small: Wegman and Carter's protocol is still ( ) -secure, if ( ) -almost strongly universal (_2 ) hash functions are used. This implies that the secret key corresponding to the choice of hash function can be reused in the next round of authentication without any additional error than this ( ) . We also show that if the players have a mild form of synchronization, namely that the receiver knows when a message should be received, the key can be recycled for any arbitrary task, not only new rounds of authentication. We explore the fundamental limits of distributed balls-into-bins algorithms, i.e., algorithms where balls act in parallel, as separate agents. This problem was introduced by , who showed that non-adaptive and symmetric algorithms cannot reliably perform better than a maximum bin load of Theta(log log n log log log n) within the same number of rounds. We present an adaptive symmetric algorithm that achieves a bin load of two in log* n+O(1) communication rounds using O(n) messages in total. Moreover, larger bin loads can be traded in for smaller time complexities. We prove a matching lower bound of (1-o(1))log* n on the time complexity of symmetric algorithms that guarantee small bin loads at an asymptotically optimal message complexity of O(n). The essential preconditions of the proof are (i) a limit of O(n) on the total number of messages sent by the algorithm and (ii) anonymity of bins, i.e., the port numberings of balls are not globally consistent. In order to show that our technique yields indeed tight bounds, we provide for each assumption an algorithm violating it, in turn achieving a constant maximum bin load in constant time. As an application, we consider the following problem. Given a fully connected graph of n nodes, where each node needs to send and receive up to n messages, and in each round each node may send one message over each link, deliver all messages as quickly as possible to their destinations. We give a simple and robust algorithm of time complexity O(log* n) for this task and provide a generalization to the case where all nodes initially hold arbitrary sets of messages. Completing the picture, we give a less practical, but asymptotically optimal algorithm terminating within O(1) rounds. All these bounds hold with high probability. Independent sets play a central role in distributed algorithmics. We examine here the minimal requirements for computing non-trivial independent sets. In particular, we focus on algorithms that operate in a single communication round. A classic result of Linial shows that a constant number of rounds does not suffice to compute a maximal independent set. We are therefore interested in the size of the solution that can be computed, especially in comparison to the optimal. Our main result is a randomized one-round algorithm that achieves poly-logarithmic approximation on graphs of polynomially bounded-independence. Specifically, we show that the algorithm achieves the Caro-Wei bound (an extension of the Turan bound for independent sets) in general graphs up to a constant factor, and that the Caro-Wei bound yields a poly-logarithmic approximation on bounded-independence graphs. The algorithm uses only a single bit message and operates in a beeping model, where a node receives only the disjunction of the bits transmitted by its neighbors. We give limitation results that show that these are the minimal requirements for obtaining non-trivial solutions. In particular, a sublinear approximation cannot be obtained in a single round on general graphs, nor when nodes cannot both transmit and receive messages. We also show that our analysis of the Caro-Wei bound on polynomially bounded-independence graphs is tight, and that the poly-logarithmic approximation factor does not extend to @math O(1)-claw free graphs. In this correspondence, the performance of the automatic repeat request-dynamic decode and forward (ARQ-DDF) cooperation protocol is analyzed in two distinct scenarios. The first scenario is the multiple access relay channel where a single relay is dedicated to simultaneously help two multiple access users. For this setup, it is shown that the ARQ-DDF protocol achieves the channel's optimal diversity multiplexing tradeoff (DMT). The second scenario is the cooperative vector multiple access channel where two users cooperate in delivering their messages to a destination equipped with two receiving antennas. For this setup, a new variant of the ARQ-DDF protocol is developed where the two users are purposefully instructed not to cooperate in the first round of transmission. Lower and upper bounds on the achievable DMT are then derived. These bounds are shown to converge to the optimal tradeoff as the number of transmission rounds increases. The multiuser communication channel, in which multiple users exchange information with the help of a relay terminal, termed the multiway relay channel (mRC), is introduced. In this model, multiple interfering clusters of users communicate simultaneously, such that the users within the same cluster wish to exchange messages among themselves, i.e., each user multicasts its message to all the other users in its own cluster. It is assumed that the users cannot receive each other's signals directly. Hence, the relay terminal in this model is the enabler of communication. In particular, restricted encoders are considered, such that the encoding function of each user depends only on its own message and the received signal is used only for decoding the messages of the other users in the cluster. Achievable rate regions and an outer bound are characterized for the Gaussian mRC, and their comparison is presented in terms of the exchange rate, the symmetric rate point in the capacity region in a symmetric Gaussian mRC scenario. It is shown that the compress-and-forward (CF) protocol achieves exchange rates within a constant bit offset of the optimal exchange rate, independent of the power constraints of the terminals in the network. A finite bit gap between the exchange rates achieved by the CF and the amplify-and-forward protocols is also shown. The two special cases of the mRC, the full data exchange model, in which every user wants to receive messages of all other users, and the pairwise data exchange model which consists of multiple two-way relay channels, are investigated in detail. In particular for the pairwise data exchange model, in addition to the proposed random coding-based achievable schemes, a nested lattice coding-based scheme is also presented and is shown to achieve exchange rates within a constant bit gap of the exchange capacity. Mobile instant messaging (e.g., via SMS or WhatsApp) often goes along with an expectation of high attentiveness, i.e., that the receiver will notice and read the message within a few minutes. Hence, existing instant messaging services for mobile phones share indicators of availability, such as the last time the user has been online. However, in this paper we not only provide evidence that these cues create social pressure, but that they are also weak predictors of attentiveness. As remedy, we propose to share a machine-computed prediction of whether the user will view a message within the next few minutes or not. For two weeks, we collected behavioral data from 24 users of mobile instant messaging services. By the means of machine-learning techniques, we identified that simple features extracted from the phone, such as the user's interaction with the notification center, the screen activity, the proximity sensor, and the ringer mode, are strong predictors of how quickly the user will attend to the messages. With seven automatically selected features our model predicts whether a phone user will view a message within a few minutes with 70.6 accuracy and a precision for fast attendance of 81.2 We consider the problem of single-round private information retrieval (PIR) from @math replicated databases. We consider the case when @math databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of @math messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the @math -privacy constraint in this paper, where any @math databases can collude, and exchange the queries submitted by the user. We derive the information-theoretic capacity of this problem, which is the maximum number of that can be retrieved privately (under the @math -privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be @math , if @math . This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing @math databases from the system, with a penalty factor of @math , which signifies that even though the number of databases needed for PIR is effectively @math , the user still needs to access the entire @math databases. The result shows that for the unsynchronized PIR problem, if the user does not have any knowledge about the fraction of the messages that are mis-synchronized, the single-round capacity is the same as the BPIR capacity. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the introduced by the Byzantine databases as opposed to in the RPIR problem. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes. A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors, where a processor receives a message in a given step if and only if it is silent in this step and precisely one of its neighbors transmits. In this paper we prove the existence of a family of radius-2 networks on n vertices for which any broadcast schedule requires at least Omega((log n log log n)2) rounds of transmissions. This almost matches an upper bound of O(log2 n) rounds for networks of radius 2 proved earlier by Bar-Yehuda, Goldreich, and Itai. We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a distributed algorithm which constructs a minimum-weight spanning tree in O(log log n) communication rounds, where in each round any process can send a message to every other process. If message size is @math for some @math , then the number of communication rounds is @math . We develop communication strategies for the rate-constrained interactive decoding of a message broadcast to a group of interested users. This situation diers from the relay channel in that all users are interested in the transmitted message, and from the broadcast channel because no user can decode on its own. We focus on two-user scenarios, and describe a baseline strategy that uses ideas of coding with decoder side information. One user acts initially as a relay for the other. That other user then decodes the message and sends back random parity bits, enabling the first user to decode. We show how to improve on this scheme’s performance through a conversation consisting of multiple rounds of discussion. While there are now more messages, each message is shorter, lowering the overall rate of the conversation. Such multi-round conversations can be more ecient because earlier messages serve as side information known at both encoder and decoder. We illustrate these ideas for binary erasure channels. We show that multi-round conversations can decode using less overall rate than is possible with the single-round scheme. We study an interference network where equally-numbered transmitters and receivers lie on two parallel lines, each transmitter opposite its intended receiver. We consider two short-range interference models: the "asymmetric network," where the signal sent by each transmitter is interfered only by the signal sent by its left neighbor (if present), and a "symmetric network," where it is interfered by both its left and its right neighbors. Each transmitter is cognizant of its own message, the messages of the @math transmitters to its left, and the messages of the @math transmitters to its right. Each receiver decodes its message based on the signals received at its own antenna, at the @math receive antennas to its left, and the @math receive antennas to its right. For such networks we provide upper and lower bounds on the multiplexing gain, i.e., on the high-SNR asymptotic logarithmic growth of the sum-rate capacity. In some cases our bounds meet, e.g., for the asymmetric network. Our results exhibit an equivalence between the transmitter side-information parameters @math and the receiver side-information parameters @math in the sense that increasing decreasing @math or @math by a positive integer @math has the same effect on the multiplexing gain as increasing decreasing @math or @math by @math . Moreover---even in asymmetric networks---there is an equivalence between the left side-information parameters @math and the right side-information parameters @math . We develop and implement an optimal broadcast algorithm for fully connected processor networks under a bidirectional communication model in which each processor can simultaneously send a message to one processor and receive a message from another, possibly different processor. For any number of processors p the algorithm requires [email protected][email protected]? communication rounds to broadcast N blocks of data from a root processor to the remaining processors, meeting the lower bound in the model. For data of size m, assuming that sending and receiving data of size m^' takes time @[email protected]^', the best running time that can be achieved by the division of m into equal-sized blocks is ((@[email protected]?-1)@[email protected])^2. The algorithm uses a regular, circulant graph communication pattern, and degenerates into a binomial tree broadcast when the number of blocks to be broadcast is one. The algorithm is furthermore well suited to fully connected clusters of SMP (Symmetric Multi-Processor) nodes. The algorithm is implemented as part of an MPI (Message Passing Interface) library. We demonstrate significant practical bandwidth improvements of up to a factor 1.5 over several other, commonly used broadcast algorithms on both a small SMP cluster and a 72 node NEC SX vector supercomputer.