๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Communication Complexity of Gossiping by Packets

โœ Scribed by Luisa Gargano; Adele A. Rescigno; Ugo Vaccaro

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
153 KB
Volume
45
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

This paper considers the problem of gossiping with packets of limited size in a network with a cost function. We show that the problem of determining the minimum cost necessary to perform gossiping among a given set of participants with packets of limited size is NP-hard. We also give an approximate (with respect to the cost) gossiping algorithm. The ratio between the cost of an optimal algorithm and the approximate one is less than 1+2(k-1)/n, where n is the number of nodes participating in the gossiping process and k โ‰ค n-1 is the upper bound on the number of individual blocks of information that a packet can carry. We also analyze the communication time and communication complexity, i.e., the product of the communication cost and time, of gossiping algorithms.

๐Ÿ“œ SIMILAR VOLUMES

Fast collective communication by packets
Fast collective communication by packets in the postal model
โœ Gargano, Luisa; Rescigno, Adele A. ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 260 KB

Collective communication operations play an important role in message-passing systems and have been extensively investigated. We study two widely used collective communication operations: gossiping and all-to-all personalized communication. We assume the multiport postal model of communication that

The Communication Complexity of Pointer
The Communication Complexity of Pointer Chasing
โœ Stephen J. Ponzio; Jaikumar Radhakrishnan; S. Venkatesh ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 253 KB

We study the k-round two-party communication complexity of the pointer chasing problem for fixed k. C. Damm, S. Jukna and J. Sgall (1998, Comput. Complexity 7, 109 127) showed an upper bound of O(n log (k&1) n) for this problem. We prove a matching lower bound; this improves the lower bound of 0(n)

The Complexity of Scheduling Trees with
The Complexity of Scheduling Trees with Communication Delays
โœ Jan Karel Lenstra; Marinus Veldhorst; Bart Veltman ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 190 KB

We consider the problem of finding a minimum-length schedule on m machines for a set of n unit-length tasks with a forest of intrees as precedence relation, and with unit interprocessor communication delays. First, we prove that this problem is NP-complete; second, we derive a linear time algorithm

The Communication Complexity of Enumerat
The Communication Complexity of Enumeration, Elimination, and Selection
โœ Andris Ambainis; Harry Buhrman; William Gasarch; Bala Kalyanasundaram; Leen Tore ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 278 KB

Let k, n ยฅ N and f: {0, 1} n ร— {0, 1} n Q {0, 1}. Assume Alice has x 1 , ..., x k ยฅ {0, 1} n , Bob has y 1 , ..., y k ยฅ {0, 1} n , and they want to compute municating as few bits as possible. The direct sum conjecture (henceforth DSC) n (log log(n))(log(n)) ) bits. This establishes a weak randomize

Routing in packet-switched communication
Routing in packet-switched communication networks with different criticality classes of communicating node pairs
โœ Ali Amiri; Hasan Pirkul ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 129 KB ๐Ÿ‘ 1 views

This paper addresses the routing problem with reliability requirements in packetswitched communication networks. In this problem, two classes of communicating node pairs are considered: less critical and highly critical node pairs. We develop a model which identifies a primary route for each less cr