Talk:Gossip protocol

Untitled

Most of this page is extracted from a longer article I wrote for a special edition of Operating Systems Review (an ACM publication that doesn't impose copyright restrictions). The longer article seemed a bit too detailed for a Wiki page, but it seemed to me that an encyclopedia treatment really should at least explain what a gossip protocol is, and isn't.

The references I included here are all cited in the longer article. Some are papers I co-authored but most are by other folks. I hope this isn't a violation of the POV/COI policies. I'm not trying to sell anything and if people want to edit the article to reduce any perceived bias, go for it!

Are illustrations needed? Ken Birman 12:59, 14 June 2007 (UTC)

Article in need of work--not okay (same note as on Virtual synchrony)

This article has numerous problems. First of all the editor who created the artice, User:Ken Birman has a conflict of interest (WP:COI) in that he is the developer of Virtual synchrony software, as he has stated. The article does not contain in-line citations. Its tone is inappropriate for an encyclopedia, a casual discussion in some areas, abruptly introduced technical language in others, sometimes both in one, so the article seems like a casual discussion among insiders or buyers in places, and unfocused run on descriptions of the process without any concept of the reader of Wikipedia articles ("Developers of distributed computer systems often need a way to replicate data for sharing between programs running on multiple machines, connected by a network. Virtual synchrony is one of three major technologies for solving this problem. The key idea is to create a form of distributed state machine associated with the replicated data item"). The examples are awkwardly introduced (probably due to COI), the prose needs thoroughly edited. The sections need cohesively structured, with internal order, for the reader of the article--WP:MOS. I have tagged these articles with requests for this clean-up in case there are interested Wikipedia editors who can improve these articles, in particular starting with structure and pose before moving on to technical accuracy. Ken Birman has made it clear he does not want me to edit the articles. KP Botany 18:23, 23 June 2007 (UTC)

On the OR: I included this tag because of the COI between the primary editor and the topic and the failure to include in-line citations, coupled with the disorganized structure of the article, that altogether make difficult the direct verification of information and original research. KP Botany 18:33, 23 June 2007 (UTC)

What a surprise to see that KP Botany has a view on this article too... seems to me that someone has a bit of a power issue here. I'm struck by the fact that s/he didn't even bother to come up with comments about the gossip protocol article per-se but instead simply pulls in comments from a completely unrelated article (virtual synchrony) that KP Botany feels needs a rewrite.

Curiously, I don't have a conflict of interest on gossip protocols, since I neither invented the concept (Demers did so, decades ago), nor am even particularly fond of them. I do use them, of course, as does any developer of distributed protocols, but while the research community has gone wild over gossip, my own view is decidely more cautious. I think these are useful tools, when used appropriately. I don't understand the COI claim, at all, in this respect.

Unless, of course, KP Botany is simply on some form of rampage. Ken Birman 00:00, 26 June 2007 (UTC)

As Virtual synchrony is, according to you, "a completely unrelated article,"[1] please remove Virtual synchrony from the "See also" section of this article. Again, the WP:MOS will explain that "a completely unrelated article" should not be in the "See also" sections of Wikipedia articles:

"See also virtual synchrony, distributed state machines, Paxos, database transactions."[2] KP Botany 22:01, 26 June 2007 (UTC)

Quick question for Ken Birman: How do you recouncil your 14 June 2007 statement

Some are papers I co-authored but most are by other folks. I hope this isn't a violation of the POV/COI policies

above with

Curiously, I don't have a conflict of interest on gossip protocols?

The first statement expresses at the least some doubts, while the second denies them completely, or at least denies a tangential concern or subset of the actually stated concern. --Calton | Talk 00:00, 30 June 2007 (UTC)

Calton, I think that you are misunderstanding what I meant by "I hope". You read that as asking a question, but I actually meant it as a statement.

So, when I wrote "I hope this isn't a violation of the POV/COI policies" I meant this in the same sense as if I had written "It would be an absurd distortion of the commonly accepted interpretation of conflict of interest to assume that anyone who has any involvement with a technology has a conflict of interest in it."

For example, suppose that you happen to be an expert on botany, and create an admirable set of Wiki pages about species of plants that you happen to be very knowledgeable about, perhaps from your work -- let's imagine that you are curator of a collection and have decades of experience in the field. Would your article about such and such a plant be a violation of POV/COI? One would "hope" not, because the alternative would mean that Wiki pages could only be written by people lacking the needed expertise to actually do a good job on them. A Wikipedia in which only non-qualified people were permitted to author the original content of articles would be a strange "Big Brother" sort of world, with everything backwards and mediocrity promoted to a sort of religion.

Having said that, I believe that non-experts are fully qualified to edit and revise content once they understand it. Here I'm distinguishing the editing role - an expertise in its own right - from original authorship, particularly on topics with science or technology content. Thus: while a person like myself should write the FIRST draft of an article on virtual synchrony, or gossip, it would be highly appropriate for a skilled editor to rewrite it (perhaps quite aggressively) with the goal of improving exposition, bringing it closer to the Wiki style, etc. (It would not, however, be wise for that non-expert to rewrite in ways that change meaning or factual content, of course)

With respect to the reference to Virtual Synchrony, KP Botany's comment simply confirms that he or she isn't playing very fair. In the particular case, the article on gossip makes the point that the types of guarantees one can obtain with such protocols are probabilistic in nature, unlike the kinds of guarantees one can obtain using protocols in the class that includes virtual synchrony (also transactions and state machine replication). This is a case where we have two major but distinct ways of replicating data in a computer network, but they don't behave identically and are not interchangable. Obviously, such a statement needs a reference to the relevant Wiki page. However, KP Botany probably didn't read this carefully before posting a duplicate of his/her diatribe from the Virtual Synchrony page (where it made more sense, although I do think it was overheated).

As to the specifics: Computer protocols (algorithms for exchanging messages between computers on networks to accomplish some task) are an area in which, perhaps, 10,000 people have worked over the past decade. I'm one of them. Gossip protocols are a major subarea within the overall area, and there are probably 150 or 200 people who publish ideas that use this style of protocol. I'm one of them, but not a major player. I find them useful in some situations and use them, when appropriate. But most of my work is focused on problems for which they are not appropriate, and hence on the whole, my papers don't use this technique very often.

Does this represent a point of view? Well, sure, but not in the sense of the WP:POV policy as I read and understand it. Does it represent a conflict of interest? I think not because as the WP:COI policy is written, conflict of interest is expressed in terms of ulterior motives -- I write a page about Roibos Tea being great for your health, but don't disclose that I happen to be a major importer of Roibos Tea. Viewed in this sense, I have no COI on either of these pages, because I neither benefit by them existing in this form, nor am hurt if they don't exist at all. I do see them as a good addition to Wiki, but not because they somehow advance my interests (beyond the propagation of knowledge, that is).

WP:POV, similarly, is written to suggest that Wiki is not the place to go on diatribes of one form or another. A person who thinks that Single Malt Whiskey is far better than Scotch should not be using Wiki to advance that point of view. This is different from a factual statement. So, while both articles have factual content -- for example that Virtual Synchrony supports data replication at higher data rates than transactional systems -- this is supported by experimental information (including some that can be found in the cited literature), and would not be disputed by any knowledgeable editor. There is actually a simple technical reason for the speed improvement (an extra commit phase is needed in the transactional protocols) and one loses some guarantees (a point made in the article). A point of view is something "debatable" but these are not debatable points. Thus, I think the articles neither attempt to promote a point of view (except in the sense that these are ideas people should be able to learn about via Wiki), nor embody a conflict of interest (except in the sense that I believe the spread of knowledge in this area is good and it "advances" that specific interest if the Wiki pages live on).

But there is a different WP policy that applies here. If one reads the conflict resolution policies suggested on the pages for new users, the kind of behavior KP Botany is engaged in is actually called out at some length. There is discussion of baiting, exagerated claims, insulting other users, misrepresenting facts, passive-aggressive postings, etc. Over the course of the past few weeks, I've experienced some of all of these and by browsing some of the history, I see that KP Botany is often in such dialogs (although, curiously, his/her pages on botany seem tremendous, so I guess this is mostly an issue when KP Botany gets passionate about topics outside of the botany field...). Most recently I see that KP Botany has gone on a bit of a cleanup, deleting a lot of those old arguments and leave his/her talk page rather clean and flattering. But it was more lively three or four days ago (I mean with respect to totally different disputes, not those relating to my two little contributions).

What to do about this? Well, those WP guidelines suggest that a cooling off period often solves conflicts. With that in mind, I won't be responding further to anything KP Botany choses to post here. I'll certainly respond to anyone else, but enough is enough on the KP Botany thing. He or she has made his or her points. Let's allow others who aren't in an angry mood to get involved, hopefully with a focus on the technical content here and the exposition, not on silly issues that probably come from outside Wikipedia or from other fights with other contributors... looks like there have been a lot of them... Ken Birman 20:56, 30 June 2007 (UTC)

This article reads like an advertisement for 'Gossip Protocol'. Many of the claims are unsupported. The "gossip protocol is one that satisfies the following conditions" is even much more specific than in real life. — Preceding unsigned comment added by 50.68.57.160 (talk) 03:03, 26 November 2018 (UTC)

This was useful to me

I thought this article did a good job -- I came here looking for info on epidemic/gossip protocols, and learned most of what I wanted to know. The technical content and exposition is fine, and the prose is serviceable, though it could benefit a little from copy-editing. I'd like to see more details, but then again, that's what the references at the end are for.

But I'm a computer scientist, not a botanist, so what do I know... JensAlfke 23:53, 3 July 2007 (UTC)

While it's nice that so many folks want to show just how moronic botanists are, you don't help the situation and you don't help the article any by showing that it is for computer scientists rather than a general encyclopedia's audience. If you had simply written the first part without the snide personal attack on me, it might have shown some support of Ken's position. It was rather nice support of Ken, though, to imply, as he did, that botanists know nothing about computers. This simply shows that neither of you is reading in the botanical sciences these days, and that the article cannot be solely supported on its own merits without trying to take me down--in other words, ad hominem attacks prove necessary. So, if the article doesn't stand without insulting me, why are people so eager to support article?

My sister's a computer scientist. I asked her if she gets computer information from Wikipedia articles. She's still laughing as I type this. I'm trying to ask her if she uses Wikipedia, and where she goes to get general information about computer science topics, but she won't stop laughing. I don't think that Wikipedia's articles on computer science, including these, are generally all that bad, so I do want to find out what she is laughing about, but I don't think she's going to be much help. Maybe other computer scientists, like you, use Wikipedia as a source of technical information. That's fine. But that is not the intended audience for Wikipedia, it's a general encyclopedia.

By the way, I'm not a complete computer moron, I do know where to plug in the power cord before I call tech support to find out why the screen is black. I did have to call the one time there was no surge protector, but other than that.... KP Botany 17:56, 4 July 2007 (UTC)

KPBotany, this is getting absurd. Your shrill attacks aren't doing anyone any good. Your assumption I have a negative opinion of botany is rampant projection (I have a good friend who got her PhD in plant genetics, if you must know.) If you're this unable to remain calm and objective in a discussion of editing, you have absolutely no business volunteering your services (unasked-for). You also are looking in the wrong place if you insist on complaining about overly-technical content: you should really go look at some of the math articles. For example, see Cardinality -- a fundamental property of sets, but an article that beyond the first paragraph is unreadable by anyone without a graduate-level degree in math. Those articles could use some rewriting, but do read up on the subject a bit first before making your opinions known; some of those mathematicians can be really touchy. JensAlfke (talk) 03:10, 4 February 2008 (UTC)

JensAlfke, I appreciate the comments. In this case it might be possible to add more detail; I'll think about it (gossip protocols are pretty simple and I could give some examples). KP Botany, you and I agreed to abide by the WP:Conflict policy under which we're supposed to be in a cooling off period. You are supposed to direct your energy elsewhere and not look at these pages. I want to respectfully ask you to do as you agreed to do less than one week ago. Ken Birman 19:14, 4 July 2007 (UTC)

No, I did not agree to direct my energies elsewhere and not look at these pages--in fact I clearly told you I would be monitoring these pages as long as there were problems with them. You wrote nasty comments about me here and others think that open season on me is necessary to support the articles--this is incorrect, and simply shows that there are, as I stated, too many problems with the articles to support them directly. If you and others persist in commenting about me, I will respond--simply stop talking about me, and I won't have anythign to respond to. Please bother to actually read what I wrote before telling me what I said.[3] KP Botany 01:10, 5 July 2007 (UTC)

And, take your comments about me to my talk page, not to this article. KP Botany 01:11, 5 July 2007 (UTC)

I also liked this article. I don't see nor have they been named here any false claims. Perhaps some details (exact numbers on size) could be added to the data center example. 141.24.33.171 (talk) 12:51, 11 July 2008 (UTC)

Protocol for removing tags?

For about six months now, this page has been tagged for Point of View, Original Research and Factual Accuracy. After a brief period of discussion and editing activity, nothing has happened for six months.

Here's my question: as a matter of policy, do such tags remain on the page forever, or is there some procedure for agreeing to remove them? It seems safe to assume that KPBotany, who placed them there, would not consider the matter resolved, since nothing substantive changed during this period. However, perhaps that particular reviewer will never find comfort with this material -- such things do sometimes happen. Ken Birman (talk) 18:04, 21 December 2007 (UTC)

Protocol on wikipedia isn't always polite, professor. You'll notice on the history of this page, that some people concur with

User_talk:KP_Botany in saying that this article needs work. I wouldn't know where to go with it. BrewJay (talk) 00:34, 14 July 2008 (UTC)

What's wrong with Internet Relay Chat?

It's a multi-cast protocol. It hosts gossip. It's reliable. It's based upon internet structure that has existed for decades. Some companies are routing sound and files over it in real-time. Why reinvent the wheel? BrewJay (talk) 12:03, 4 July 2008 (UTC)

Why don't add it to see-also? 141.24.33.171 (talk) 12:48, 11 July 2008 (UTC)

Good suggestion. I don't see any reason not to add it. But do keep in mind that when companies like Amazon use gossip, they mean they are using this "class" of solutions -- they have an abstracted behavior in mind. IRC is a very specific protocol, with an associated RFC standard, and this is definitely NOT the implementation of gossip Amazon favors. In fact there are hundreds of gossip protocols, and I would say that the modern perspective is that IRC is an early example of a particular application that uses a gossip mechanism. One would think of it side-by-side with a dozen others (Astrolabe, the Amazon shopping cart, etc), each of which also is an application of some kind running on a gossip protocol of some type. But this said, many people know about IRC and using it as an example would be super. Go for it... Ken Birman (talk) 14:34, 9 August 2008 (UTC)

"Thus, while one could run a 2-phase commit protocol over a gossip substrate, doing so would be at odds with the spirit, if not the wording, of the definition."

This article might be useful in understanding the problems that routing protocols hav already solved by *not* trying to see the whole path that a packet travels. They don't try to make trees out of network topology. People make maps out of it, sometimes. Perhaps you could explain how a gossip protocol would also be reliable *without* a lock and an acknowledgement to that lock (2-phases). For me, it's basic versing, and I don't see any easy ways around locking without comparisons and arbitration that pretty much, in the end, need to occur on one CPU that needs to serialize that arbitration before it saves. The Amazon shopping cart runs on cookies. It could run on URL-code in HTML that it sends you just as easily. When cookies were being derided and misunderstood, hotmail was using URL-code to identify users more certainly than IP#.

The spirit of gossip is a lack of reliability. So, I hope you understand that I'm inclined to ask for references or terse descriptions of implementations when you indicate "logarithmic growth". BrewJay (talk) 14:48, 16 October 2008 (UTC)

Notability

Someone asked for Gossip-based multicast protocol to be created. I redirected it to Internet Relay Chat, because it carries gossip. Later, after deletion of my redirection, I discovered an uninformative article on a proprietary protocol that doesn't seem to do anything that IP doesn't, when implemented. For example, I know that there are several ways to rank a routing table:

• You can measure only the number of hops from yourself to a distant host.
• You can measure the latency (delay) between yourself and a distant host.
• You can measure the reliability of every hop.
• And, finally, you could rank routes based on weights for all of the above statistics.

The more of that work you do, the more expensive your router becomes, but considering the ratio of speed between a CPU (mine is rated at about 27 gigabits per second) and network speed, such work is feasible.

Considering it further, I think reliability statistics would need to be mapped and averaged over a week. There might be reliable times when a network node is saturated with traffic or regular maintenance. BrewJay (talk) 06:37, 9 July 2008 (UTC)

I remove the redirection tage today, because the idea hasn't gained any real traction. I think it would just confuse people -- it would make the routing page more complex, and anyhow gossip isn't really the same sort of routing mechanism. The routing page is mostly about maintaining data to do point-to-point message routing. Gossip is really more of a data replication mechanism -- a way to get information robustly from where it originates to "everywhere". Thus a merge with a page on broadcast protocols would make more sense, if one was so inclined. But gossip is also used in ways that don't do replication, like to compute an average over a large set of nodes (average load, or average queue-length), or to build an overlay graph. In fact there are so many gossip algorithms that I think this justifies a wiki page of its very own... Ken Birman (talk) 14:34, 9 August 2008 (UTC)

I didn't make a deletion proposal based on the reality of the subject, because I KNOW that it's real; I'm using a gossip protocol (as I'm led to understand the definition) called Transmission Control Protocol over IP.

gossip protocol isn't notable. See category:internet architecture. BrewJay (talk) 21:55, 8 July 2008 (UTC)

I don't comprehend your argument. You think this article should be deleted because you think "gossip protocol" refers to IRC? "Gossip protocol" is a technical concept in computer science, and is very clearly notable given the references in the article and the numerous papers on the subject. I guess in some sense IRC is a "gossip protocol", but that's not the meaning that this article is referring to. Jfire (talk) 22:29, 8 July 2008 (UTC)

What I am referring to is the design decisions that went into the protocol underlying IRC (including some multi-cast implementations with IP version six). The article doesn't say much about anything that routed and its offspring don't IMPLEMENT in open-source code. BrewJay (talk) 06:39, 9 July 2008 (UTC)

I think you are absolutely right, but the problem is that IRC is a standard. There is exactly one legal way for it to function. As noted above, gossip is a general class of solutions with hundreds or thousands of such protocols -- IRC would be one example of a gossip protocol. So if you try to say "gossip is IRC" that's just not true. Many gossip protocols are nothing like IRC and couldn't be used on IRC (for example, how would you implement a distributed hash table (Kelips, Chord, Pastry...) using the IRC protocol? No way. In contrast, saying "IRC is a great early example of a gossip protocol that gained very wide use and was ultimately standardized." is totally true and a good suggestion for an example that might help readers get the idea. Ken Birman (talk) 14:34, 9 August 2008 (UTC)

Wikify Noise Compensation

"*Anti-entropy protocols for repairing replicated data, which operate by comparing replicas and reconciling differences."

That can be done, but it needs wikification, and they never compare replicas, because that isn't efficient (consider that the reverse channel will hav noise on it, too). V.42bis doesn't really work much like that. error correction and cyclic redundancy code.

This statement isn't accurate. Many gossip protocols definitely DO compare replicas. Efficiency isn't always the only consideration. Anyhow, your comment about noise is tangential. The settings where gossip is used aren't really struggling with noise -- they use MAC signatures to discard packets that are corrupted. The issue is missing data -- messages that never get there, for any of a bunch of reasons. Gossip has so many ways to get data from source to all its destinations that it can overcome almost any imaginable outage. This why people like it so much. Super robust. Ken Birman (talk) 14:34, 9 August 2008 (UTC)

If you get to the level of wikipedia, yes, a corrupt submission can be identified by comparing replicas. Or, in a case where you want two computers to work on the same problem, then they should get the same result. When you toss in potential for lost assignments, then we're not talking about entropy management, anymore. For instance, if you're talking about two computers assigned to the same task, and one set of results gets lost, then you need to assign a third computer to that task and either wait twice as long or accept a solution from fewer machines.

I'm talking about what's done on any one transmission channel. Data isn't sent twice over the same serial line to make it more reliable; that's wasteful and it's STILL not reliable. Error-correction bits are sent. Cyclic redundancy codes are sent. If error correction bits can't make CRC correct, then data is sent again. There's probably a sophisticated protocol for using the bad data in the first packet to make the second packet more reliable. IOW, for sending parity bits BACK, after a bad packet is received, to identify bad bytes in a packet, then resending only those bytes. BrewJay (talk) 15:15, 16 October 2008 (UTC)

The current link for "Anti-entropy protocols" goes to "Error correction", which is wrong. These are two distinct concepts; the names are not synonyms. Either the link text needs to be "Error correction" instead of "Anti-entropy protocols", or the link itself needs to point to "Anti-entry protocols" instead of "Error correction". As the text describing the link indicates the topic being Anti-Entropy protocols, I'd recommend to change the link towards "Anti-Entropy protocols". if the link is meant to point to error correction, then I'd recommend to adapt the text describing the link is adapted accordingly. --Christian Kerth (christian.kerth@gmx.net), 08:55, 19 July 2018 (UTC) — Preceding unsigned comment added by 153.96.12.26 (talk)

What's this about radio and direct communication?

In the analogical lead of the article's beginning, that's what I get...that computers on the internet communicate directly along some wavelength. On some networks, like analog telephone (I'm not sure if that exists anymore), or packet radio, maybe they do, but there's no great element of randomness in it. A user picks a BBS, dials the number, BINGO, you hav a peer... Or, in packet radio, some ham scans the radio waves, recognizes digital, then tries to decode it using internet documents and utilities. Relaying QWK-based mail might happen a gossipy manner, but it was (is?) explicitly scheduled -- nothing like the random walk presented in this article. BrewJay (talk) 07:20, 9 July 2008 (UTC)

More description of routed.

b) Background data dissemination protocols continuously gossip about information associated with the participating nodes. Typically, propagation latency isn’t a concern, perhaps because the information in question changes slowly or there is no significant penalty for acting upon slightly stale data.

If I'm going to justify snipping every byte out of this document that's better illustrated elsewhere, this is about where I'd start. Router tables are updated. Routers go down, come up, get hot-connected to other hosts over firewire and USB. The information circulates over TCP, neighbour to neighbour, which is not peer to peer.

Just because a specific example of a gossip protocol is discussed elsewhere is not a reason for removing this article or content from it. "Gossip protocol" refers to a general protocol strategy, not any one specific protocol. Jfire (talk) 15:08, 9 July 2008 (UTC)

No jeneral protocol is for anything. That's what I find particularly confusing about this article. The analogies could be useful, but they amount to brainstorming about how things could become rather than how they are. You can use routing to configure software. This article doesn't offer any potential for decisions about design. BrewJay (talk) 03:47, 10 July 2008 (UTC)

Folks, Gossip isn't really a routing protocol. Sounds like some confusion here but I'm not sure it was caused by the article itself. Actually, gossip is more of a data replication technique than a routing protocol. A routing protocol, as you clearly know, is for getting messages from a sender to a destination. For example, 123.45.76.1024 wants to send a packet to 72.31.16.1570. How can we best get it there with the fastest throughput and lowest latency? So that's routing.

A gossip protocol is a way to share knowledge in a big group of nodes. For example, you might use gossip in a system like Skype to replicate information about the current list of supernodes that do Skype call setup. That list changes a lot, pretty much all the time, so you need a really robust way to ensure that everybody has all the data, and that it tracks changes. Gossip is incredibly simple and is a great way to solve this and similar problems. But it actually depends on, and doesn't replace, routing. To do gossip, I need a way to get messages from node to node. So we're at the next level "up" the protocol stack. Does this help?

Unfortunately, no, because I want to explain how a multi-cast protocol for mirroring data, like IRC or NNTP could get more performance over analog channels, in theory. Throughout your article, there are references to growth functions that aren't possible on what little I know of internet architecture, because there aren't any direct links, say between me and wikipedia. IOW, there are ten hops between me an wikipedia, and no simple way to reduce that without an analog channel between me and wikipedia, which isn't likely to happen. IOW, I'm voting to move it "down" the protocol stack, to where I would need to select modulation and error correction protocols. BrewJay (talk) 10:43, 23 October 2008 (UTC)

Sorry about my delay in responding. Didn't log in for a few weeks... Ken Birman (talk) 13:57, 22 July 2008 (UTC)

"Some kind of" and "might"

These are weasel words.

I would be so very happy if a better writer wanted to come along and do a really professional job of cleaning up my initial text.... Ken Birman (talk) 14:34, 9 August 2008 (UTC)

Gossip protocol causes Amazon outage

Here's an interesting story for you folks:

… from an Amazon announcement Monday: (http://status.aws.amazon.com/s3us-20080720.html):

7:19 PM PDT We wanted to share a brief note about what we observed during yesterday's event and where we are at this stage. As a distributed system, the different components of Amazon S3 need to be aware of the state of each other. For example, this awareness makes it possible for the system to decide to which redundant physical storage server to route a request. In order to share this state information across the system, we use a gossip protocol. Yesterday, we experienced a problem related to gossiping our internal state information, leaving the system components unable to interact properly and causing customers' requests to Amazon S3 to fail. After exploring several alternatives, we determined that we had to temporarily take the service offline so that we could clear all gossipped state and restart gossip to rebuild the state.

These are sophisticated systems and it generally takes a while to get to root cause in such a situation. We're working very hard to do this and will be providing more information here when we've fully investigated the incident. We also wanted to let you know that for this particular event, we'll be waiving our standard SLA process and applying the appropriate service credit to all affected customers for the July billing period. Customers will not need to send us an e-mail to request their credits, as these will be automatically applied. This transaction will be reflected in our customers' August billing statements.

A subsequent news announcement explained that the problem wasn't the gossip protocol, per-se, but rather was caused by corrupted data that entered the system (somehow) and then spread through the gossip layer, contaminating everyone who saw it. Here's the follow-on story (well, the relevant part of it)

We've now determined that message corruption was the cause of the server-to-server communication problems. More specifically, we found that there were a handful of messages on Sunday morning that had a single bit corrupted such that the message was still intelligible, but the system state information was incorrect. We use MD5 checksums throughout the system, for example, to prevent, detect, and recover from corruption that can occur during receipt, storage, and retrieval of customers' objects. However, we didn't have the same protection in place to detect whether this particular internal state information had been corrupted. As a result, when the corruption occurred we didn't detect it and it spread throughout the system causing the symptoms described above. We hadn't encountered server-to-server communication issues of this scale before and, as a result, it took some time during the event to diagnose and recover from it. [4] Ken Birman (talk) 12:29, 27 July 2008 (UTC)

... so clearly, gossip protocols are a big deal in modern computing data centers, and play critical roles. Places like Amazon are using them, and when they go wrong, the data center can become unusable! So the moral of the story is: if you work on distributed computer systems in 2008, you had better know what gossip protcools do, how to build them, and how to get them right! Which isn't to diminish the importance of ALSO knowing how routing works. BTW, Amazon makes a lot of use of gossip. I know of some applications that work well for them -- they reported on one, in the shopping cart subsystem, at the SOSP conference in 2007. Another is the Astrolabe system, which they acquired some years ago and then rebuilt internally. But I don't know this specific gossip subsystem (the one in S3) and hence can't guess at what went wrong, beyond what Amazon is saying in their little announcement. Sounds like some form of corrupted data snuck into the gossip subsystem and got stuck there. This is easy to imagine -- without taking adequate care, gossip protocols can be very much at risk of that sort of accidental contamination... Ken Birman (talk) 11:06, 23 July 2008 (UTC)

Necessity of "pairwise" interaction?

The article currently says that pairwise interactions are a defining characteristic of a gossip protocol. To extend the office rumor analogy, what about the case where three or four people stand around the water cooler and listen to the same rumor when it is only spoken once? In other words, would something still be considered a "gossip protocol" if the underlying transmission can involve subscribing to some sort of broadcast of the message? If so, I think the "pairwise" language could be removed. The reason I am confused is because it also states that one of the uses of gossip is to implement multicast, but gossip also seems useful at a layer where multicast is already provided by some deeper layer... Maghnus (talk) 00:37, 11 August 2008 (UTC)

Cool question. This is very much a hot topic in the gossip community. People do agree that to be gossip, the bandwidth has to be bounded by a small constant. But you are quite right -- when you've got a form of broadcast available (as in wireless, or perhaps UDP multicast setups) you can potentially do gossip with a "fanout" of more than 1-to-1 on each round. Totally reasonable.

My reason for not saying this in the article was that the worry that as we get more and more accurate, the article could grow from a normal encyclopedia treatment into a kind of monograph. So for me this sort of detail is secondary to the key concept. But others may see it differently and I'm really ready to see others take the article over and improve it.

If you do introduce this sort of thing, you'll use the term "fanout" to refer to the number of receivers of each gossip message. One complication jumps out: what if the fanous can't be predicted? E.g. in a wireless setup, maybe you don't know, a-priori, how many people can hear you. This, I would say, starts to depart from the gossip model. To be gossip, we need a predictable constant data transfer on each round -- one to one works, or one to four. But one to "some number" is iffy, especially if "some number" could vary wildly. So if the fanout is fixed... then yes, still gossip. Ken Birman (talk) 21:41, 11 August 2008 (UTC)

According to the simulator in my brain, pairwise has more potential speed than analog broadcast, because error correction problems crop up in a one-to-many topology. I suppose that error correction can be delayed until a transmitter is listening to complaints from whichever node is scheduled to transmit. I don't want to go there. It seems intractable. It probably isn't, and I haven't read that far. A protocol is basically a working description of machine, professor, so if you didn't want a monograph, I'm afraid that monograph is the best I can give you. Trying to describe these protocols in jeneral is a mistake, when you're also demanding nearly optimal performance. IOW, even though I go into how simple it seems to deliver NNTP via scheduled packet radio broadcast, when I work it down to error correction, I don't like the tractability. I want to take the lackadaisical stuff out. Machines don't work like that. BrewJay (talk) 11:20, 23 October 2008 (UTC)

This example reminds me of a scheme I wrote for telephony multi-cast...

"Search strings known to A will now also be known to B, and vice versa. In the next "round" of gossip A and B will pick additional random peers, maybe C and D."

Okay, so here we hav A communicates with B, and they exchange messages, carefully identifying their source with a message-ID, so that I don't need to count the number of unique messages. C and D do the same thing, at the same time as A and B. Later, A and C communicate, while B and D communicate the same way. In this way, you hav four nodes with the same information, and only two communication periods.

Period Nodes
1        2
2        4
3        8

...in thirty-two communication periods, you can hav over four billion nodes with information intended for broadcast. I wrote that method for QWK-packets, which were an early BBS standard for newsgroups. That standard didn't hav message-IDs, so my method had no potential (unless the advantage were worth seeking unique messages, for which I didn't hav an efficient method; now I would use a perfect hash. It still doesn't hav much potential, because hook-ups on the internet are largely manual and static. Notice that my method DEPENDS upon static addresses AND scheduled, regular communication periods. In practice, I don't see any hope for it, except perhaps within one box, where it has been blown away in practical applications, probably long before I even wrote it.

The problem is like one-bit adders strung together with shifters to make a multiplier. I think it illustrates what you're driving at professor, and I don't get logarithmic growth out of it, because the potential amount of information doubles at each period, so each scheduled period could be longer than the last. If, however, you limit the amount of information in an exchange period arbitrarily, and buffer it of course, then you can hav logarithmic growth, where the number of nodes with broadcast information exponentiates in relation to an arbitrarily low and fixed period.

I don't doubt that there are a lot of references for this in papers that have analyzed practicing it for use within a box, where it's easy to hard-wire timing, and when you stick randomness and unreliability into it, then you need some very special error correction protocol, indeed. I read that Intel spends a lot of money on noise control (crosstalk) within a CPU.BrewJay (talk) 16:42, 16 October 2008 (UTC)

Exponential propagation rates and logarithmic growth.

"The term convergently consistent is sometimes used to describe protocols that achieve exponentially rapid spread of information. For this purpose, a protocol must propagate any new information to all nodes that will be affected by the information within time logarithmic in the size of the system (the "mixing time" must be logarithmic in system size)."

I see that growth functions are in here, and I'm having trouble parsing them. For example, "within time logarithmic in the size of the system". Should I rewrite that as "in time proportional to the logarithm of that system size"? I think I should do that and trim off the part in brackets, because I hav no idea what is being mixed in this context, and the mentioned function is the same.

An interesting practical fault in this scheme you might like to note professor, is that exponential propagation rates are not possible on digital infrastructure. If, as you introduce in the leadup, there are (analog) frequencies to select and schedules to follow (as I demonstrate earlier, without rigor, schedules increase performance), then linear growth, proportional to the number of hosts, in the distribution time needed to for many-to-many news, for example, is feasible. I don't see how a logarithmic proportion can happen. Scheduled one-to-all is the simple way to do it in packet radio. There could be a protocol, for example, to get yourself a time-slot and frequency for digital broadcasts that would be heard. Same function: linear; as the community grows, so does the time needed for mirroring all hosts.

In the leadup, there is a mention of "sometimes". I will move to strike it out, because the word is hard to use in Physics. It is a troublesome thing to hav bits sometimes lost or to form an association for collaboration that is irregular. I understand that you want to demonstrate flexibility, reliability and performance. When a router goes down, then the metric for that router in neighbouring routers quickly registers unreachable. That propagates like gossip. BrewJay (talk) 01:57, 21 October 2008 (UTC)

Sure. I actually meant this in a different sense, as in "some people use the term, but others don't". But you can strike it. BTW, everyone calls me "Ken" even in my classes. I know that in much of the world it seems odd to call a professor by anything but the title, but I'm fine being just Ken, so feel free to be a bit less formal! Ken Birman (talk) 12:22, 22 October 2008 (UTC)

Excellent everything to everyone.

My theory goes that if you try to design something that is everything to everyone, then you will end up with a system that is nothing to anyone. Professor Birman wants to express that gossip protocols are reliable, perform superbly, and are ultimately flexible. I am still not getting the impression of any design choices made, rather I am led to believe that it's some general description of all protocols that may call themselves gossip; thousands. It is anything but clear, and yet I cannot pinpoint any particular words that are making this document foggy.

If I continue to work on this document, then I think I will try to impose limits and link it to other topics in network architecture; rather than say that reliability is not assumed, I will ask for how compensations are made. If the professor still wants to describe what works on paper, then I will want the scope narrowed to what can be adequately described, here, in examples. BrewJay (talk) 02:42, 21 October 2008 (UTC)

Well, although I sympathize with your view, the fact remains that there is a community of hundreds of researchers who have written hundreds of papers and even books, taking gossip protocols to mean what the article defines them to be. Yes, this is a broad definition, but there are many things that aren't gossip protocols (for example, 2-phase commit isn't a gossip protocol, atomic multicast isn't gossip, Byzantine Agreement isn't gossip...) To say it means "everything to anyone" is exagerated.

Now, I accept your core point: this is a broad and perhaps excessively broad class of protocols. But nonetheless, the community does have a consensus view on what characterizes gossip and the article reflects that, as accurately as I was able to do so.

So have at it, but do be fair to that community. Read a bunch of their papers and make sure that you as an editor understand this body of work as well as you can, and that you have gained as deep an insight into the core properties that make something a gossip protocol before you try and edit the article. But once you gain this level of insight, it is entirely possible you could dramatically improve the article. I'll look forward to what you come up with.

Drop me a note if you need pointers to more of the literature. ken@cs.cornell.edu will reach me directly. Ken Birman (talk) 16:55, 21 October 2008 (UTC)

Restating a method for proportional growth without many-to-one.

(Growth in time consumed for a broadcast mirroring transaction that is proportional to system size.)

Initial Condition:
Machine A contains messages 1,1,1,1
''      B "        "        2,2,2,2
C = 3,3,3,3
D = 4,4,4,4

Machine A Exchanges with B
Machine C Exchanges with D

State after first period:
A = 1,2,1,2
B = 2,1,2,1
C = 3,4,3,4
D = 4,3,4,3

A Exchanges with C
B Exchanges with D

State after second period:
A = 1,2,3,4
B = 2,1,4,3
C = 3,4,1,2
D = 4,3,2,1

After two periods, four machines contain information intended for broadcast.

Period Nodes
1      2
2      4
3      8

The number of channels required for this process increases at half the number of machines, which means that it is proportional (counting in half duplex (one direction at a time), it's identical). The amount of information that an exchange period can require can double at every step, so it is necessary to either double the length of each consecutive period, or arbitrarily limit the amount of information that can be transmitted in a cycle of periods. This means that there will be more latency in the system during peak hours, unless each consecutive period doubles in length. Taking the choice to double consecutive period length adds up so that the time required for a broadcast is proportional to the number of nodes, not logarithmic.

Period Length Nodes
1	1	2
2	2	4
3	4	8
        7

For some reason, I'm not quite getting eight for a total in column two, so I think I'm making a one-off error. The result I'm expecting is identical to that for one-to-many by rotation (Is that approximately what tokenring means?): proportional. As I said in earlier comments, I like how simple the pairwise choice makes error correction; I could choose V.42bis, for example. I would choose to *always* double the length of consecutive periods, and periodically arbitrate the baseline of real time that represents one in my table above, based upon the most congested server. Proportional is an optimal result in sorting, too. Since the level of congestion on each server would be a few quantities of fixed length, I would broadcast that between periods. If this were to go as far as shared files, then it might be advisable to rotate periods that lock files, accept file locks, distribute files, and gauge conjestion.

I've told people that once you've stated your assumptions and shown how your math works, that it isn't always necessary to follow WP:NOR. (That's less true in Physics, less true yet in Chemistry, and it's downright bonkers in Biochemistry). I think it needs peer review, though, which is why I'm honoured to be conversing with a professor, however much trouble he might be having with encyclopedic standards that really do encourage you to link your stuff to pre-requisites. I'm thinking I should touch up this article with the graphics, and give Ken some time to adjust the words, assuming he cannot find a way to beat proportional. BrewJay (talk) 14:00, 23 October 2008 (UTC)

In fact this is pretty much how gossip protocols work. I'm not totally sure what your notation denotes (why does each node have a vector of 4 numbers? What does it mean if A has "9, 17, 16, 7"?) But this said, the behavior you outlined is definitely that of a gossip-style protocol. You'll generally see an exponential rise in the number of infected machines until time log(N) when most have become infected, after which you get a tail -- an S-shaped curve, if X is the time and Y is the number or the percent of infected machines. Your table has that behavior, albeit for a small N (you generally need 100 or 200 nodes to really see the S shape clearly).

With push-only gossip, also called rumor mongering, the early part of the curve rises fast but the tail can be long. With pull-only, also called anti-entropy, the tail is short but the start can be slow. And with push-pull, also called merge, you get a symmetric S curve, with 100% reached (with high probability) after roughly log(N) rounds.

On the topic of editing the article though, I'm feeling that given that Wiki is a community and many people work with and on gossip technology, it might be better to try and find other people with an interest in improving the article. I certainly don't mind clarifying a specific thing but I worry that our goal here should be an article with less and less of a WP:POV flavor, and to do that we need a more diverse set of editors (knowledgeable ones, obviously, but varied). I guess I could email to a few folks and beg them to have a look... or we can just wait for someone to wander past... Ken Birman (talk) 16:02, 23 October 2008 (UTC)

Something wrong with the search function

I came here searching for "worst protocol ever" (half-expected a redir to SOAP). The search function seems to have understood "worst article ever". Maybe I mistyped. — Preceding unsigned comment added by 194.228.11.192 (talk) 06:03, 2 September 2016 (UTC)

Metaphor sandwich

The lead right now is a metaphor sandwich, with no technical depth. Where's the beef? — MaxEnt 18:41, 7 January 2018 (UTC)

Unsupported Claims

As a networking professional, I can say categorically that the claim in the first paragraph is quite dubious.

To say, "A gossip protocol is a procedure or process of computer–computer communication that is based on the way social networks disseminate information" is false. Social networks spread information based on selective and discriminative sharing. By this, I mean that parties that are interested in certain communications are not always privy to them and those that are not interested are often included in the information that they have already seen or just don't care about. Social media sharing and peer-to-peer networks may have similarities but not much else. The claim that "Modern distributed systems often use gossip protocols to solve problems that might be difficult to solve in other ways, either because the underlying network has an inconvenient structure, is extremely large, or because gossip solutions are the most efficient ones available" is also false. In 99% of the cases, a gossip protocol is the most wasteful and problematic way of achieving necessary communications. In a nutshell, the claims made in this article are rather biased in favor of 'gossip' protocols and fail to reflect the real life problems encountered with them.

Also worth mentioning, this is really a variant of peer-to-peer networking. Rarely will anyone in software development talk about their "gossip deployment". Rather, the mode by which data dissemination is obtained is discussed as peer-to-peer or client-server networking design. Most notable peer-to-peer networks (BitTorrent, Skype, Bitcoin, eDonkey) use trackers (or variants) and peer coordinators to ensure that data is properly available and so that users are directed to the most reliable and perform ant sources for obtaining data. When Quality-Of-Service is important, peer-to-peer networks are rarely ever chosen.

It would be great if someone could incorporate these issues/concerns/criticisms of this into the actual article.

Of the Many Types of Gossip Protocols

Almost an unlimited number of "Gossip" variants could be mentioned. They are not WP material unless supported by current use and/or citations.

In that vein, I have also removed "Spacial Gossip". Although explained, there were no examples given of current use and also no valid references. See 'Unsupported Claims' section for a similar issue. — Preceding unsigned comment added by 50.68.57.160 (talk) 16:50, 26 November 2018 (UTC)

Although I haven't changed it, the heading Gossip Protocol Types also states things unsupported by the citations provided. For example, the opening sentence citation actually supports "information spreading" and "information aggregation" as types. Yet, strangely, the section includes "Anti-entropy protocols" with a link to computer error correction seemingly unrelated. — Preceding unsigned comment added by 50.68.57.160 (talk) 16:57, 26 November 2018 (UTC)

... Which I have also now trimmed and probably needs further refinement. — Preceding unsigned comment added by 50.68.57.160 (talk) 17:00, 26 November 2018 (UTC)