<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/xsl'?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T09:41:29Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/2213" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/2213</identifier><datestamp>2026-05-14T13:49:21Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">Allavena, Andre</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2005-10-04T14:07:29Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2005-10-04T14:07:29Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2005-10-04T14:07:29Z</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/2213</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">6475822</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">The importance of scalability and fault-tolerance in modern distributed systems has led to considerable research in multi-cast protocols using gossip. In a gossip protocol, each node forwards messages to a small set of ``gossip partners'' chosen at random from the entire group membership. By discarding the strong reliability guarantees of traditional protocols in favor of probabilistic guarantees, gossip protocols can deliver greater scalability and fault tolerance. In early gossip algorithms, partners were chosen uniformly at random from the entire membership, limiting scalability because of the resources required to store and maintain complete membership views at each node. Later protocols avoided this issue by storing much smaller random subsets of the membership at each node, and choosing gossip partners only from these local views. Such protocols are subtle: at least some local views must change in response to group membership changes in order to preserve connectivity and performance guarantees. While these protocols have been the subject of much simulation and analysis, formal proofs of key properties - in particular the probability of partitioning - have remained elusive.&#xd;
&#xd;
In this thesis we give a new scalable gossip-based algorithm for local view maintenance, together with a proof that the expected time until a network partition is at least exponential in the view size and the size of the departing set. We develop probabilistic bounds on the in-degree (hence the load) of individual nodes, and argue that protocols lacking our reinforcement component eventually converge to star-like networks, whose connectivity depends on a small set of overloaded nodes. We argue that the undirected connectivity graph is an expander, for which application-level gossip multi-cast protocols will converge rapidly. An analysis of the membership system under heavy churn yields a lower bound on the amount of communications required per round. Finally, we offer some arguments supporting the experimental fact that the elements of the local views - although not a uniformly random sampling of the set of nodes in the system - have a high degree of randomness and suggesting that the state of the system after O(ln n) iterations is independent of the initial state.</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">1061477 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en_US</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">gossip</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">random graph</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">distributed system</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">membership</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">peer-to-peer</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">scalability</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">reliability</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">epidemic</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">probabilistic multi-cast</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">group communication</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">On the Correctness of Gossip-based Membership Protocols</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://cornell-ecommons.eks.prod.4science.cloud/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author">Allavena, Andre</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="93c1d626-ba2e-4bde-93c1-7317654b0326">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en_US&lt;/Language>
   	&lt;Title>On the Correctness of Gossip-based Membership Protocols&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2005-10-04T14:07:29Z&lt;/PublicationDate>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Allavena, Andre&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;Keyword>gossip&lt;/Keyword>
    &lt;Keyword>random graph&lt;/Keyword>
    &lt;Keyword>distributed system&lt;/Keyword>
    &lt;Keyword>membership&lt;/Keyword>
    &lt;Keyword>peer-to-peer&lt;/Keyword>
    &lt;Keyword>scalability&lt;/Keyword>
    &lt;Keyword>reliability&lt;/Keyword>
    &lt;Keyword>epidemic&lt;/Keyword>
    &lt;Keyword>probabilistic multi-cast&lt;/Keyword>
    &lt;Keyword>group communication&lt;/Keyword>
   	&lt;Abstract>The importance of scalability and fault-tolerance in modern distributed systems has led to considerable research in multi-cast protocols using gossip. In a gossip protocol, each node forwards messages to a small set of ``gossip partners&amp;apos;&amp;apos; chosen at random from the entire group membership. By discarding the strong reliability guarantees of traditional protocols in favor of probabilistic guarantees, gossip protocols can deliver greater scalability and fault tolerance. In early gossip algorithms, partners were chosen uniformly at random from the entire membership, limiting scalability because of the resources required to store and maintain complete membership views at each node. Later protocols avoided this issue by storing much smaller random subsets of the membership at each node, and choosing gossip partners only from these local views. Such protocols are subtle: at least some local views must change in response to group membership changes in order to preserve connectivity and performance guarantees. While these protocols have been the subject of much simulation and analysis, formal proofs of key properties - in particular the probability of partitioning - have remained elusive.&#xd;
&#xd;
In this thesis we give a new scalable gossip-based algorithm for local view maintenance, together with a proof that the expected time until a network partition is at least exponential in the view size and the size of the departing set. We develop probabilistic bounds on the in-degree (hence the load) of individual nodes, and argue that protocols lacking our reinforcement component eventually converge to star-like networks, whose connectivity depends on a small set of overloaded nodes. We argue that the undirected connectivity graph is an expander, for which application-level gossip multi-cast protocols will converge rapidly. An analysis of the membership system under heavy churn yields a lower bound on the amount of communications required per round. Finally, we offer some arguments supporting the experimental fact that the elements of the local views - although not a uniformly random sampling of the set of nodes in the system - have a high degree of randomness and suggesting that the state of the system after O(ln n) iterations is independent of the initial state.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>