Distributed Systems

Gossip Algorithms for database replication



Exact vs Relaxed consistency during database replication

  • Consider a database replicated at many sites in a large, heterogeneous, slightly unreliable and slowly changing network of several hundred or thousand sites,
  • Each database update is injected at a single site and must be propagated to all the other sites or supplanted by a later update.
  • The sites can become fully consistent only when all updating activity has stopped and the system has become quiescent.
  • On the other hand, assuming a reasonable update rate, most information at any given site is current. This relaxed form of consistency has been shown to be quite useful in practice

Factors to think for graceful scaling with database replication

  • the time required for an update to propagate to all sites
  • the network traffic generated in propagating a single update. Ideally network traffic is proportional to the size of the update times the number of servers,

Three ways to spread updates

  • Direct mail – each new update is immediately mailed from its entry site to all other sites. This is timely and reasonably efficient but not entirely reliable since individual sites do not always know about all other sites and since mail is sometimes lost.
  • Anti-entropy: every site regularly chooses another site at random and by exchanging database contents with it resolves any differences between the two. Anti-entropy is extremely reliable but requires examining the contents of the database and so cannot be used too frequently. Analysis and simulation show that· anti-entropy, while reliable, propagates updates much more slowly than direct mail.
  • Rumor mongering: sites are initially “ignorant”; when a site receives a new update it becomes a “hot rumor”; while a site holds a hot rumor, it periodically chooses another site at random and ensures that the other site has seen the update; when a site has tried to share a hot rumor with too many sites that have already seen it, the site stops treating the rumor as hot and retains the update without propagating it further. Rumor cycles can be more frequent than anti-entropy cycles because they require fewer resources at each site, but there is some chance that an update will not reach all sites.

Things to know about database replication strategies

  • The randomized anti-entropy algorithm provides impressive performance improvements both in achieving consistency and reducing network overhead traffic.
  • Rumor mongering algorithm shows promise as an efficient replacement for the initial mailing step for distributing updates.
  • A backup anti-entropy scheme easily spreads the updates to the few sites that do not receive them as a rumor.
  • it is possible to combine a peel back version of anti-entropy with rumor mongering, so that rumor mongering never fails to spread an update completely.





How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

0 0 votes
Article Rating
Notify of
Inline Feedbacks
View all comments