Automatically assigned DDC number: 00435

Manually assigned DDC number: 00465

Number of references: 4

Title: Optimal Odd Gossiping

Author:

Author:

Author:

Subject: Universit'e Bordeaux I,Guillaume Fertin,Joseph G. Peters Optimal Odd Gossiping

Description: In the gossiping problem, each node in a network starts with a unique piece of information and must acquire the information of all other nodes using two-way communications between pairs of nodes. In this paper we investigate gossiping in n-node networks with n odd. We use a linear cost model in which the cost of communication is proportional to the amount of information transmitted. In synchronous gossiping, the pairwise communications are organized into rounds, and all communications in a round start at the same time. We present optimal synchronous algorithms for all odd values of n. In asynchronous gossiping, a pair of nodes can start communicating while communications between other pairs are in progress. We provide a short intuitive proof that an asynchronous lower bound due to Peters, Raabe, and Xu is not tight. Keywords: gossiping, communication, networks AMS (MOS) subject classifications: 94A05, 68M10 Part of this research was done while both authors were visiting Universit'e ...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1999-01-06

Pubyear: 1998

Format: ps

Identifier: http://citeseer.ist.psu.edu/140831.html

Source: ftp://fas.sfu.ca/pub/cs/TR/1998/CMPT1998-24.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/61910.html"   Type="inproceedings"   CiteSeer_Book="ACM   Symposium   on   Parallel   Algorithms   and   Architectures"   CiteSeer_Volume=""   Title="On   the   Number   of   Rounds   Necessary   to   Disseminate   Information,">

            <identifier   Org="ISBN:0792337778"   Paper_ID="/61910.html"   Extracted="0792337778"   DDC="511/.5"   Normalized_DDC="5115"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0818623101"   Paper_ID="/61910.html"   Extracted="0818623101"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0818642211"   Paper_ID="/61910.html"   Extracted="0818642211"   />

            <identifier   Org="ISBN:0818656026"   Paper_ID="/61910.html"   Extracted="0818656026"   />

            <identifier   Org="ISBN:0818677929"   Paper_ID="/61910.html"   Extracted="0818677929"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0898714907"   Paper_ID="/61910.html"   Extracted="0898714907"   />

            <identifier   Org="ISBN:1584886234"   Paper_ID="/61910.html"   Extracted="1584886234"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540008462"   Paper_ID="/61910.html"   Extracted="3540008462"   DDC="004.6'5"   Normalized_DDC="00465"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540412557"   Paper_ID="/61910.html"   Extracted="3540412557"   DDC="001.64"   Normalized_DDC="00164"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540555994"   Paper_ID="/61910.html"   Extracted="3540555994"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540572732"   Paper_ID="/61910.html"   Extracted="3540572732"   DDC="511.8"   Normalized_DDC="5118"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540578994"   Paper_ID="/61910.html"   Extracted="3540578994"   DDC="004/.01/5115"   Normalized_DDC="004015115"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540582185"   Paper_ID="/61910.html"   Extracted="3540582185"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540583386"   Paper_ID="/61910.html"   Extracted="3540583386"   DDC="005/.01/51"   Normalized_DDC="0050151"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540616268"   Paper_ID="/61910.html"   Extracted="3540616268"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540626166"   Paper_ID="/61910.html"   Extracted="3540626166"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540667318"   Paper_ID="/61910.html"   Extracted="3540667318"   DDC="004.0151"   Normalized_DDC="0040151"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540852379"   Paper_ID="/61910.html"   Extracted="3540852379"   />

      </rec>

      <rec   ID="/225229.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Minimum   Linear   Gossip   Graphs   and   Maximal   Linear   $(\Delta,k)$-Gossip   Graphs,"   />

      <rec   ID="/54604.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Dissemination   of   Information   in   Interconnection   Networks   (Broadcasting   &   Gossiping,">

            <identifier   Org="ISBN:0792337778"   Paper_ID="/54604.html"   Extracted="0792337778"   DDC="511/.5"   Normalized_DDC="5115"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:088629312X"   Paper_ID="/54604.html"   Extracted="088629312X"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:1848009976"   Paper_ID="/54604.html"   Extracted="1848009976"   DDC="511/.54"   Normalized_DDC="51154"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540260528"   Paper_ID="/54604.html"   Extracted="3540260528"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540580786"   Paper_ID="/54604.html"   Extracted="3540580786"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540602496"   Paper_ID="/54604.html"   Extracted="3540602496"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540606483"   Paper_ID="/54604.html"   Extracted="3540606483"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540626166"   Paper_ID="/54604.html"   Extracted="3540626166"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.125"   />

      </rec>

      <rec   ID="/204605.html"   Type="article"   CiteSeer_Book="SIAM   J   Comput"   CiteSeer_Volume="21"   Title="Gossiping   in   Minimal   Time,">

            <identifier   Org="ISBN:0818623101"   Paper_ID="/204605.html"   Extracted="0818623101"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818642211"   Paper_ID="/204605.html"   Extracted="0818642211"   />

            <identifier   Org="ISBN:0818665823"   Paper_ID="/204605.html"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0818677929"   Paper_ID="/204605.html"   Extracted="0818677929"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0898714907"   Paper_ID="/204605.html"   Extracted="0898714907"   />

            <identifier   Org="ISBN:3540221166"   Paper_ID="/204605.html"   Extracted="3540221166"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540295720"   Paper_ID="/204605.html"   Extracted="3540295720"   DDC="004.2"   Normalized_DDC="0042"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540401946"   Paper_ID="/204605.html"   Extracted="3540401946"   />

            <identifier   Org="ISBN:3540569391"   Paper_ID="/204605.html"   Extracted="3540569391"   />

            <identifier   Org="ISBN:3540575685"   Paper_ID="/204605.html"   Extracted="3540575685"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540578994"   Paper_ID="/204605.html"   Extracted="3540578994"   />

            <identifier   Org="ISBN:3540580786"   Paper_ID="/204605.html"   Extracted="3540580786"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540600841"   Paper_ID="/204605.html"   Extracted="3540600841"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540602496"   Paper_ID="/204605.html"   Extracted="3540602496"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540616268"   Paper_ID="/204605.html"   Extracted="3540616268"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540626166"   Paper_ID="/204605.html"   Extracted="3540626166"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540874747"   Paper_ID="/204605.html"   Extracted="3540874747"   />

            <identifier   Org="ISBN:9810244819"   Paper_ID="/204605.html"   Extracted="9810244819"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Optimal   Odd   Gossiping"   />

</references_metadata>