CS 739 - Reviews - Spring 2011

Summary:

This papers describes several simple randomized algorithms for distributed updates for replicated database systems. These algorithms are motivated by Epidemiology which guarantee that every update will be eventually reflected in all replicas with few requirements from the underlying communication system. One of the algorithms, randomized anti-entropy, has been implemented on the Xerox Internet, improving both the consistency and network performance.

Problem:

Xerox's Clearinghouse service is built on Xerox Corporate Internet(CIN), which consists of several hundreds of Ethernets connected by gateways. Its main function is to provide translations from names to machine addresses. The name space is partitioned into domains. However, the network's performance is unacceptable when updates are synchronized across domains for consistency. Thus, new algorithms for this replicated database maintenance are required with both consistency and performance guarantees.

Contributions:

1. Propose three algorithms for replicated database updates problems: direct mail, anti-entropy and rumor mongering with the goal of good performance and consistency. The basic techniques, theory model, analysis and simulation results are presented, which are very helpful to understand new Epidemic algorithms.

2. Using a method of replacing deleted items with death certificates to handle the deletion in replicated database. Death certificates carry timestamps and distributed the same way as the ordinary data. The tradeoff between the time to keep death certificates and the storage space consume is discussed to understand its limitations.

3. To reduce the network communication cost, spatial locality is explored to favor the nearby neighbors. A nonuniform spatial distribution works well for Xerox's CIN topology. Futhermore, both anti-entropy and rumor mongering methods are used with this nonuniform spatial distribution, and detailed analysis and simulations results show that excellent improvement can be achieved particularly the traffic on the critical network links are reduced significantly.

Flaws:

1. The relationship between the spatial distribution and the network topology is not well studied. There are too many ad-hoc parameters used in the paper's model to find the best performance. However, for a different network topology, the cost of search for the optimal spatial distribution and other settings would be high. It would be better if a generic model for the spatial distribution and network topology is proposed.

2. For rumor mongering algorithm, the algorithm will fail if there is some malicious site will give fake response when receiving a rumor or sending fake rumor. For example, if many malicious sites said that they have already received certain rumor. Then, the real rumor may not be distributed to all the sites with big probability. Some analysis for this kind of malicious behavior would make the system more robust.

Applicability:

The randomized rumor spreading algorithm is very interesting and useful in distributed areas. A close related work is using bar gossip protocol to handle BFT. I believe the simplicity and robustness of randomized rumor algorithms are still applicable in online game server, distributed directory service, online shopping service, etc.

Summary:
This paper describes several methods--anti-entropy and rumor mongering--derived from epidemic models for disseminating updates through a distributed database, finding that they operate more efficiently than direct mail methods.

Problem:
The ideas developed in the paper result from scalability problems that Xerox experienced distributing updates in its Clearinghouse service; its use of direct mail and expensive anti-entropy procedures caused significant traffic congestion and delays in the spread of information. The paper analyzes ways of circumventing that, both by improving anti-entropy algorithms and by replacing direct mail with a more sophisticated means of propagating updates.

Contributions:
The paper’s primary contributions are its analysis and improvement of anti-entropy operations and its application of epidemiological models to distributing information with its rumor-mongering algorithm. For anti-entropy, it examines the respective traffic models of push and pull anti-entropy, noting that, in a uniform topology, pull converges noticeably more quickly than push; it also provides simple algorithms that improve the overhead of the database comparisons resulting from anti-entropy. Rumor-mongering acts in a similar fashion to anti-entropy, but only operates on recent updates, spreading them probabilistically to other nodes. If a node sends information to a node that already has it, there is a 1/k (k is a parameter) chance that the node stops spreading the information. Both algorithms could cause deletes that rapidly follow updates to be undone by nodes that have not seen the delete, so the paper introduces death certificates to solve this problem.

The authors provide reasonably extensive analysis of both algorithms, looking at both theoretical models and simulated performance under a variety of parameters. They examine rumor-mongering especially thoroughly, testing and comparing a number of variants. The paper also investigates the functionality of these algorithms when applied to topologies where access is not uniform.

Problems:
As the paper itself notes, the spatial distribution section could be expanded, given that many real-world environments (including that of Clearinghouse) do not have uniform access characteristics; specifically, the analysis of how this affects rumor-mongering seems sparse compared to that on anti-entropy. Similarly, comparable numbers on the efficiency of rumor-mongering and of anti-entropy would be useful; the tables make it appear that rumor-mongering delivers no benefits over anti-entropy, which is probably untrue. In general, more comparison of the mutual effects of rumor-mongering and anti-entropy would be useful, since the paper gives only a vague sense of how they would cooperate.

Applicability:
Given some further exploration of the issues of spatial distribution the authors outline in the last section, this paper could be quite useful for those implementing eventual consistency in a distributed system. This may be of particular use in data centers, given their spatial proximity, though their hierarchical topology may undercut that (inter-rack links are oversubscribed, potentially producing bottlenecks similar to Bushey, which may cause problems if updates transfer large amount of data). Both the mathematical models and the simulation results provided seem like they would help determine how to parameterize such a system, which improves its prospects of deployability.

Summary
The authors look at how randomized algorithms perform for distributing updates to a replicated database.

Problem
Given a replicated database that runs on a large heterogeneous network, how can database updates be distributed in a way that is scalable, fast, and does not put too much strain on the network?

Contributions
The authors examine the existing solutions direct mail and anti-entropy. They introduce their own method, rumor mongering, which is based on the models of the spread of an epidemic. In this method, each node repeatedly randomly chooses another to share information with. They also look at how to choose a distribution for the random choice that more closely matches the network topology, and thus puts less stress on important links. Finally, they showed that their implementation works on their network.

Flaws
The random algorithms have some parameters that determine how fast and with what probability the nodes converge on a value. With the rumor mongering algorithm, it is possible that some nodes will not receive the update. It would have been nice I think to have a comparison between the probability of this algorithm preventing a node from getting the update, and other errors that could result in the same thing (such as hardware errors).

Discussion
I think the algorithms here are useful today. Perhaps in networks that are completely owned by a single company, it makes more sense to use a more organized strategy. However, rumor mongering seems like a good choice if the network is loosely organized or it is difficult to obtain a global view. For example this might be good for a network that touches many different parts of the Internet. Another advantage is that is seems that rumor mongering could still perform very well, even if each node was only aware of a few neighbors and didn’t know about the rest of the network. There is the potential for abuse though. Actual computer viruses often spread by randomly picking targets. If they don’t restrict how fast they spread, this can be crippling to networks.

Summary:
The paper is about a few simple algorithms that can be used for distributing updates that drives toward consistency in replicated distributed databases. The paper also presents simulations and analytical results for the different techniques discussed.

Description of Problem:
Maintaining consistency in a replicated distributed database in a large network is a problem. A database update in one replica needs to be propagated to all other replicas so that all the replicated databases will become consistent. The network might be heterogeneous, unreliable, and contains several thousands of replicas.

Summary of contributions:
The authors describes three simple methods for distributing updates: direct mail, anti-entropy, and rumor mongering. They provide simulation and analytical results using the anti-entropy and the rumor-mongering methods. For the rumor-mongering algorithm, the authors analyze the differences between blind versus feedback implementation and the differences between push versus pull. They also present dormant death certificates method (that uses an activation timestamp) which is analogous to an immune system reaction where the death certificate can be awakened like antibodies. The authors explore spatial distribution where network traffic can be reduced by taking advantages of nearest neighbors.

Flaws:
I don't know if this is a flaw or I did not fully understand how the algorithm handles simultaneous updates from different replicas or repeated deletion and insertion of an item. Also the algorithm doesn't tell you when replicated database is consistent so how do you know if you have the latest update if that is an important feature to know. There is no mention of how the algorithm deals with network partitions. Anti-entropy could be very expensive if the database is very large.

Application to real systems:
The algorithms seems useful if you want a simple algorithm that eventually drive replicated databases to consistency. I could see it being useful for like replicated backup databases or databases that do not need to be instantly up-to-date. The algorithm has already been used in the Xerox Corporate Internet but it didn't say what type of application the database was used for.

Summary:
This paper presents three algorithms to distribute updates in a replicated database system: Direct mail, Anti-entropy and Rumor mongering, and also some variants of those algorithms. It also discussed residue, traffic and delay of those algorithms; and proposed a non-uniform distribution in the randomization step to reduce traffic in the bottlenecked link.

Problem:
How to effectively distribute updates in a replicated database system in an eventual consistency fashion which achieves: low residue (numbers of un-updated sites when the system stabilize), low traffic and low delay time.

Contributions:
1. The paper proposed three algorithms to distribute updates in a replicated database system and discussed their behaviors in how reliable they are, how much network traffic they incur, and how much time they would take to converge. Several variants to the basic algorithms are also proposed and their effectiveness in improving performance is quantified.
2. Network topology is taken into account when choosing servers to contact: nearby servers are favored to propagate updates to. This spatial distribution effectively reduced traffic overhead, especially in the bottlenecked link, thus improves performance.

Flaws:
The author didn’t well motivate some choices they made. For example, the function used to select anti-entropy exchange partners; or some parameter values. Also, as the author noticed, the spatial distribution they proposed doesn’t work well under some network topologies, and this problem is not well studied.

Applicability:
I think those algorithms the paper proposed would still be quite useful when building an eventual consistent system today. Especially if we consider the topology of, say, Amazon S3, where the link capacity within a data center would be uniformly high, but updates propagation could be congested in links which connect different zones. Thus the ability of reducing overhead on the critical network links is quite desirable.

Summary:

This paper investigates propagating updates in a distributed database using randomized algorithms, derived from epidemic models. The end result is efficient dissemination of updates at the cost of relaxed consistency.

Problem Description:

This paper addresses the problem of efficiently transmitting updates submitted to a server in a distributed database to other servers that make up the database. This problem is important because efficiently distributing updates allows a system to scale to large numbers of nodes while avoiding congestion problems. Previous work provided somewhat workable solutions to this problem but required certain guarantees from the underlying communication substrate that could not always be provided in practice.

Contributions Summary:

The major contribution of this paper is the application of epidemic algorithms for efficient communication. The first epidemic algorithm investigated is anti-entropy, or the reduction of system entropy. The basic idea is to have each node communicate with another random node at some interval, doing a merge of their respective databases using timestamps to guide the merge. While a naive approach is expensive, the authors present a few optimizations that decrease the cost of anti-entropy. The next algorithm, rumor mongering, works by having a small set of nodes either push updates to other nodes or pull updates from other nodes. If the contacted nodes have already seen the update, then with some probability the initiating node will stop disseminating the update through the network. Tweaking various parameters, the authors obtain efficient and relatively reliable updates to the database using a combination of rumor mongering and anti-entropy as a backup.

The paper also introduces the idea of death certificates to effectively signal that a piece of data is deleted. A key complexity of death certificates is how long to store them before retiring them. The authors explore a few variants that allow them to store death certificates for longer periods of time while still keeping overall storage overhead for death certificates low.

Shortcomings:

I think the biggest shortcoming in using these algorithms is the relaxed consistency they provide. It is conceivable that the database be updated on one server by a client. This same client could communicate with another server and discover that the update has not propagated yet. This also means that the system is not transparent. This system was a successor of Grapevine, and the designers of that system stated that transparency was not always a good thing. So for these algorithms, transparency might not be important. Regardless, relaxed consistency increases programming difficulty as well as user confusion.

Application to real systems:

As discussed earlier in the class, today’s large web services don’t focus on providing strict consistency to their users; they value the performance improvement gained from eliding consistency. It appears that these services could benefit from using epidemic algorithms to propagate information updates.

Summary
This paper investigates the possibility of using randomized algorithms for maintaining consistency in replicated database systems. The paper evaluates the cost of different algorithms, specifically the overall network traffic that they generate. They introduce direct-mail, anti-entropy, and rumor mongering. They also evaluate using non-uniform spatial distribution which favors nearby sites.

The results show that we can replace the existing expensive algorithms with randomized algorithms that provide probabilistic guarantees and do not require guarantees from the underlying communications system. In order to achieve deterministic guarantees we need to back up rumor mongering with anti-entropy. It is not very clear how the rumor mongering approach interacts with the proposed usage of spatial distributions.

Problem Statement
The problem at hand is that once you have a database that is replicated at many sites in a large network, it is very hard to provide guaranteed consistency between the replicas. Important factors that need to be considered in any design are time to reach consistency and the network traffic that is generated in order to achieve consistency.

Contributions

Critique
Epidemic processes introduced in this paper were very interesting. However, it seemed to me that in order for them to be effective a lot of tuning is needed. For example, one must be careful that certain thresholds are correctly set once the network topology changes. Otherwise, we will encounter "catastrophic" failure. I believe this is a large burden for system maintenance.

It seems that using epidemic processes causes a lot of corner cases that should be resolved. In order to resolve these corner cases, the authors introduce new sorts of data that need to be maintained in the network. For example, we need to store death certificates and for each death certificate we need to save 2 time stamps. The authors do not evaluate or quantify how much this overhead is at their system and do not compare it with the direct-mail approach. In other words, their main focus in evaluation is in network traffic and storage requirements are not evaluated.

Applications
Today, replication is used frequently in order to maintain service availability as well as faster service. For example, users around the world are served from different databases to ensure lower latency. More over, it is common to replicate critical data in different locations to save them from loss in case of potential disasters. Therefore, maintaining consistency in replicated databases is very important. Considering that this paper is from 1980s, I am curious to know how we tackle this problem today.

Summary
This paper mathematically and experimentally explores the space of epidemic algorithms (algorithms that arrive at consistency lazily by sharing data with peers).

Problem
Often multiple servers are used to store/serve the same data in order to reduce load or improve reliability. While read accesses on such replicated systems are easy to handle, updates are difficult since the updates much reach every replica. Unfortunately, due to network partitions, temporary system failures, and the difficulties of making all the nodes in a distributed system agree, perfect consistency is not practically achievable unless one is willing to block indefinitely. Making no effort to achieve consistency is also undesirable, so many middle-ground solutions have been proposed. These approaches are classified and compared.

Contributions
1. The paper proves that pull algorithms converge must faster to 100% infection than push algorithms. Intuitively, push and pull seem symmetric, so I found this very surprising, but the following scenario helped it make sense. Suppose 50 out of 100 nodes are infected. If push is used, probabilistically fewer than 50 nodes will receive one or more push updates, so there is less than a 50% chance (~40%) a given node that hasn’t received the update will receive it. However, if pull is used, there is exactly a 50% chance for each node.

2. “Complex Epidemics” are also introduced. Basically, these are like anti-entropy pushes that only operate on a subset of the whole database. The policies for choosing what the subset is are broken into four categories (blind vs feedback, and counter vs coin). The first axis (blind vs feedback) determines when nodes lose interest, and the second axis (counter vs coin) determines whether interest should be lost deterministically or randomly. Surprisingly, each of the policies in this space are equivalent in terms of how much traffic is costs to achieve a given infection percent.

3. The idea of dormant death certificates was a clever way of making sure that deleted items don’t come back while saving space.

Flaws
I have no real criticisms of the paper, but I think it would be interesting if non-random push algorithms were also considered. The example I gave in the first point of the contributions section shows that the reason push converges more slowly is that it is almost a certainty that some nodes will receive pushes from multiple sources. If, however, the systems were some how designed so that nodes choose who to push to based on a deterministic sequence, and the nodes were pseudo-synchronized with each other, the pushes would be more evenly spread out (more nodes would receive 1 push and there would be fewer cases of 0 or 2 or more pushes). This should make push convergence closer to pull convergence.

Application
It is common for content to be so popular that multiple servers are needed to serve the same content (many websites could be used as examples). Immediate updates at all locations for such websites probably isn’t much of a concern, so epidemic approaches would be great.

Summary:

The paper describes mechanisms for maintaining consistent data in a highly replicate database present at various sites. It uses three mechanisms: namely, direct mail (mailing the updates of data), anti-entropy (comparing each pair of database to propagate updates) and rumor mongering (spreading the updates in the system via a mechanism of rumors as in an epidemic).The paper look at various mechanisms involving things like push or pull mechanism to resolve difference, death certificates for deletion, dormant death certificates. The paper also looks at the effect of spatial distribution on the propagation mechanism, i .e. effect of variation in network on propagation mechanism.

Problem:

The paper looks at a database highly replicated at different sites. In such a highly replicated database, it is hard to ensure that the updates to a data or new data propagates to all the sites and is hence consistent. The paper is inspire from epidemic theory and applies solutions like direct mail, anti-entropy and rumor mongering to such scenario to ensure data consistency in all the databases.

Contributions:

The paper has many interesting contributions. Applying epidemic theory to such a system in Xerox is interesting. The paper uses the various mathematical evaluation to figure out rumor mongering and at what rate should participants loose interest while propagating the data, it also considers variations in the scenario. One of the interesting things is that they make decisions based on connection limit, spatial distribution and performance improvements like checksums to reduce network traffic. I also liked the concept of Death Certificates and even more of Dormant Death Certificates. Although, spatial Distribution was hard to understand especially the work on their simulations to see the traffic numbers and how can they be reduced /influenced at hot point in the network. It seems they found some good results in anti-entropy and rumor mongering.

Application to real System:

It is hard to say where such a system would be useful. The question is if we have locations where the data is highly replicated at various sites and hence consistency in data is required. The paper itself point out towards hierarchical decomposition of database should be preferred over replicated database. However, as the pointed out such systems with a mix of the three mechanisms can be used to propagate information in such a crowd and that might be one of the likely cases in future with the high data demand as well.

Summary
This paper presents an algorithm for achieving consistency in a distributed replicated database, using ideas taken from the study of epidemics. Rather than providing a complex, formal, provably consistent algorithm, the authors give up some correctness in order to gain simplicity and real world applicability.

Problem
Achieving consistency in a distributed system is a complex problem. With large, heterogeneous, unreliable, dynamic networks like the ones the paper is focusing on, it can be very difficult to ensure that all nodes have the same data. Furthermore, in networks like this, details like geography and connectedness can play an important role. Thus, figuring out which nodes to talk to and how to spread out traffic is also an important problem discussed in this paper.

Contributions
The authors begin by discussing two techniques that have previously been used to achieve consistency: direct mail and anti-entropy. However, their main contribution is a new algorithm for doing so, what they call “rumor mongering.” With rumor mongering, an update to the system is viewed as an infection that needs to spread to all nodes. Nodes that have received the update spend some time infecting other individuals who have not yet received it. Eventually they stop spreading it, which creates the property that consistency is not guaranteed – it is possible for all nodes to stop spreading the update while some nodes have not yet seen it. The paper also discusses various optimizations and variations of the main algorithm, and the results seen when using them.

Another contribution of this work is their discussion of spatial distributions and how nodes should decide who to contact for pushing or pulling updates. They view the network as a nonuniform distribution of nodes, with some nodes that receive heavier traffic than others. Their algorithm includes biases when choosing which node to contact for updates, such as contacting closer nodes, which proved to decrease traffic across the network.

Flaws
Given that the focus of this paper is on coming up with a usable system, I thought they glossed over the issue of timestamps and unsynchronized clocks. Their system has very nice simplicity, but in a real world situation, it would likely have to be coupled with some form of synchronized clocks, perhaps the ones they cited, which would increase the complexity of the system.

Application
I think the ideas presented in this system are very applicable to real world systems today. The assumptions the authors made about the network (large, heterogeneous, dynamic, geographically distributed, nonuniform distribution) are all valid assumptions today, perhaps even more so than they used to be. The tradeoff of some correctness for simplicity and usability seems like a valid one to me, and means that a system like this can easily be implemented in real world scenarios where minor consistency flaws or slowness are not a problem.

Summary: This work explores a family of methods for distributing updates to a database system in a way that drives the replicas toward consistency. The algorithms are inspired by and modeled on the spread of epidemics among human populations. They discuss the mathematical underpinnings to the algorithms and how they are affected by network topology. The authors show how this relaxed consistency model allows them to significantly improve the performance of their name service database system.

Problem: The core problem addressed here is the common challenge of maintaining consistent replicas of global data in a distributed system. When data must be updated across a set of nodes several problems can arise: network failures can prevent updates from reaching some of the nodes, nodes may fail before or after the update is received, membership of nodes may change over time so we might not know all node that should receive an update at any given time, etc. Previous approaches to this problem were not satisfactory because they relied on reliability gaurantees in the underlying communications platform and on maintaining large distributed control structures.

Contributions: Three general approaches to the consistent replication problem are discussed: Direct Mail (DM), Anti-Entropy (AE), and Rumor Mongering (RM). DM simply sends a mail message to every node in the system with an instruction to update the value. DM, thus, relies on good knowledge of group membership, a reliable mail/messaging protocol, and is not tolerant of network partitions/failurs. AE periodically reconciles differences between pairs of nodes by comparing the value and timestamp at each node and updating appropriately. AE is tolerant to network failures as DM is not, however it carries alot of overhead (many messages must be exchanged for the system to reach quiescence). RM models the diffusion of an update like an epidemic. Each node is either "infectious", "susceptible", or "removed". In each round, each infectious node chooses a susceptible node (random, or according to closeness) and sends its rumors (updates) to that node. Infectious nodes eventually convert to "removed" nodes after contacting already infected nodes a certain number of times. Delete operations are performed using death certificates in order to avoid having resurrections from stale data.

Limitations: While the eventual consistency model is at once the greatest strength of this system, it is also an important limitation. Applications that demand truly transactional semantics would not be able to use a replication system like this. A banking application, for example, could report different balances for an account depending the order that transactions are submitted to a collection of nodes.

Applications: The simple idea of relaxing consistency requirements has huge relevance to current distributed system design. Very many of the largest web services have exactly that requirement. It doesn't really matter if every user always sees the most current facebook photo taggings just as long as they eventually converge to some agreement. Any situation where scale, fault tolerance and performance are more important than immediate consistency, then an epidemic-style eventually consistent replication protocol is a good option.

Summary

This paper considers the problem of lazily synchronizing updates for database
replicas at different sites to a consistent state, by formally examining three
algorithms, namely, direct mail, anti-entropy, and rumor mongering, under the
metrics of residue, traffic, and delay.

Problem

1. When the same database is deployed at multiple sites, to maintain consistency
among these replicas in the face of updates becomes a problem.

More specifically --

2. Deletion on some of the replicas is hard to deal with, because the obsolete
copies of an item from elsewhere in the database would come back to the site
where the item is deleted.

3. Pathological network topologies present performance problems.

Contribution

- Three algorithms (direct mail, anti-entropy, and rumor mongering) are formally
evaluated in terms of residue, traffic, and delay. This addresses problem 1.

- This paper discusses the trade-off between the retention time for death
certificatcs, the storage spare consumed, and the likelihood of old data
undesirably reappeariug in the database. This addresses problem 2.

- By using a well chosen spatial distribution for selecting anti-entropy
partners, the implemented algorithm reduces average link traffic
significantly. This addresses problem 3.

Flaw

- If multiple replicas of the same item (e.g., the same field in a particular
tuple) are updated at the same time (before being propagated), how to make
multiple replicas agree upon the same value?

Applicability

- A very obvious application for replicated database maintainence is USENET for
newsgroups, where news servers lazily synchronize posts in a batch with each
other.

- The network bandwidth was a precious resource when this paper was
written. Therefore, it was reasonable to have replicated database to improve
locality for data usage, and data can be lazily synchronized in batch among
servers at non-busy time, e.g., at night. However, as broadband network gets
faster, eager synchronization is allowed, which is more user friendly, because
updates can be seen in time.

Summary
This paper explores nondeterministic methods for maintaining consistency of replicated data. The authors explain two algorithms, inspired by epidemiology, which are analytically and experimentally shown to have different performance and efficacy characteristics.

Problem
Many distributed systems require data to be consistent across replicas for proper operation. In some applications, a temporary disagreement over some value is not catastrophic, merely undesirable. High performance may instead be the larger issue.
The goal here is three fold: First, minimize the delay between the beginning and end of an update, to minimize inconsistency. Second, limit the amount of coherence traffic for high performance. Third, eliminate the possibility of lingering inconsistencies after an update, or find some way to eventually rectify incorrect values.

Contributions
The main contribution of this work is the introduction of two easy to implement algorithms, which have very different performance characteristics. The first algorithm, anti-entropy, periodically compares its state with other nodes and rectifies inconsistencies. This approach is somewhat slow, because many items of data may need to be checked, but is fairly good at leaving little residue. The second algorithm, rumor mongering, seeks to randomly spread updates to other nodes. Some control is put in place to control when the update stops being infectious. This approach is significantly faster, because only the data item in question needs to be communicated, but there is a potential for residual inconsistency. The duality of these algorithms makes a combined methodology attractive.

Another contribution is the way that deletes are performed and maintained. Because the remnants of a deleted item are possible, it is insufficient to simply get rid of the value. An undeleted value, say from a disconnected node, could reintroduce itself easily after the delete message is no longer viral. Their solution is to keep death certificates for each deleted item, then only delete the death certificate after some period of time. Who says a level of indirection can’t solve every problem?

Limitations
The biggest limitation of the work is the fact that their solutions are probabilistic, and rely on some properties of the underlying network topology. The authors did an excellent job of showing how pathological topologies can cause complete asynchrony. Unless it’s possible to guarantee that these failure configurations won’t occur, this could be a significant barrier to adoption. Perhaps a possible solution would be to incorporate knowledge of previous actions in order to favor pushes to likely susceptible nodes, or favor pulls from likely infected nodes.

Applicability
The most attractive feature of the algorithms described is that they would be simple to implement efficiently, and for that reason I think they may be applicable to many classes of distributed systems. It’s important to keep in mind that relaxed consistency is required for these algorithms to be appropriate.

Summary
The paper presents and analyses several randomized algorithms used to propagate database updates within a distributed database system in order to achieve consistency. Because the behavior of the algorithms is typical of an epidemic, the authors make use of epidemic models to study the algorithms’ behavior and the likelihood of convergence within the system.

Problem
The authors aim to reduce the high volume of network traffic (especially over critical links) resulting from update propagations in large network comprising of thousands of nodes. The work is originally motivated by the poor performance of the Xerox Corporate Internetwork (CIN), which was unable to complete its task in the allotted time due to the load on the network.

Contributions
The paper makes several contributions to the field of distributed system:
1. Several simple randomized algorithms to propagate database updates are presented: direct mail, anti-entropy and rumor-mongering. As the algorithms behave similar to an epidemic, epidemic models are used to study and analyze the algorithms.
2. Analysis of the algorithms as well simulations to determine performance of the algorithms utilizing various mechanisms by which data is propagated between sites viz. push, pull, and push&pull as well as various conditions/parameters such as network topology, partner selection and connection limits.
3. Correct propagation of deletions in order to avoid erroneously inserting old instances of a record or preventing later updates to a deleted record via death certificates.
4. Metrics to evaluate performance of epidemic based algorithms.
5. Mechanisms to reduce the frequency and the amount of data exchanged between partnered sites by exchanging infection lists and consistency checksums.

Flaws
The paper is fairly exhaustive in discussing the strengths and drawbacks of the epidemic algorithms. One possible criticism of the paper however, is the use of a globally unique timestamp, which was treated very briefly in the paper. The timestamp is critical to determining ordering of updates to a record. However, the paper fails to explain how to achieve a globally unique timestamp in a distributed environment, a nontrivial problem in the presence of local clock skew.

Applicability
The eventual consistency model is a very popular topic in research as well as implemented in a number of commercial distributed systems such as Amazon’s Dynamo. Therefore, the paper presents a number of useful topics as well as experiences that may be used to evaluate as well as aid in the design and development of a replicated system.

SUMMARY
This paper explains a simple method for establishing(eventual) consistency in replicated distributed data systems. Taking cue from epidemiological models, It presents randomized algorithms (anti entropy and rumour mongering) that demand only a few guarantees from the underlying communication network.

PROBLEM ADDRESSED
The main motivation for the work arose while encountering the kind of scale for updates in the clearinghouse servers which were using direct mail and anti-entropy schemes. There was more disagreement between the sites and hence more traffic was seen. Anti-entropy could not be completed in the stipulated time. The works during that period made strong assumptions about the network and deterministic with lot of additional overhead. This paper is more elegant in the sense that it does not depend on the guarantees from the underlying network, does not maintain complex control structures and presents simple randomized algorithms for maintaining consistency in a replicated data store.

CONTRIBUTIONS OF THE PAPER
The paper clearly explains the 3 algorithms: direct mail, anti-entropy and rumor mongering. In the direct mail scheme an update is propagated as soon as it is made. This has reasonably less burden on the network but unreliable(message may be lost due to congestion or when destinations are unreachable). Anti entropy is aimed at resolving differences in the copies by incurring a huge overhead of sending the entire database over a network. It is shown that anti-entropy is a simple epidemic algorithm that eventually infects the entire population of sites. Rumor spreading is done by planting a rumor with one person who becomes infective and spreads it to some random people. Every person getting that rumor again become active and share the rumor. However when an active person makes an unnecessary call, the active member loses interest with a probability. Variations of this rumor spreading like considering residue and traffic and taking feedback from recipient vs blind approach are discussed.

It also proposes a cautionary scheme for complex epidemic that may fail occasionally. In this scenario infrequent anti-entropy back up is prescribed. This ensures with probability 1 that there will be eventual consistency.

The paper establishes that with anti-entropy or rumor merging scheme one cant delete an item from database just the opposite would happen where the old copies are re-propagated. To avoid this the deleted items are replaced with death certificates(time stamp carried like normal data). During update when old copies meet death certificates they are removed. It also explains the usefulness of dormant death certificate which could save space and that when only an obsolete update encounters it they are awakened and propagated to all other sites.

The paper also recognizes that the cost of sending an update to a nearer node is much cheaper than to a distant site. It describes mechanisms that combine this spacial distribution with anti entropy and rumor mongering,

CONCERNS
The paper has a straightforward goal of ensuring eventual consistency to the replicas. Does this work well in the real time where we have replicas for performance reasons catering to large number of clients in a timely and accurate manner? Also the paper makes a honest confession about performance problems in pathological network topologies that needs to be addressed.

RELEVANCE TO MODERN DAY SYSTEMS
The methods explained in the paper are quite relevant to the modern distributed systems. The idea to combine the epidemic algorithms and spatial distribution is practical. I feel Facebook (for example) has this kind of lazy consistency model of eventually updating/propagating the data to its replicas to address its scalability issues.

Summary:

This paper explores strategies for achieving eventual consistency of updates for a database that is replicated across several locations.

Problem:

Maintaining consistency across databases replicas in a distributed system is an important challenge. This paper aims at providing a solution which is more efficient that a deterministic solution. It aims in doing this by assuming that the system can tolerate an eventual delivery of updates VS immediate delivery of updates.

Contribution:

One of the primary contributions in this paper is that it plans of using randomized algorithms to propagate message updates over deterministic mechanisms. Such an approach is easier to implement with less complicated data structures.

The paper also discusses different varieties of solutions and ranks them based on efficiency and reliability. The direct mailing solution is considered reasonably efficient and the least reliable. The Anti-Entropy solution is considered the most reliable and the least efficient as it requires regular comparison of databases. The Rumor mongering approach is the most efficient as it involves lesser message exchanges but it has a certain probability of failure. Keeping all pros and cons of each method the paper suggests in using a hybrid approach of combining Rumor Mongering with Anti Entropy, which is a very nice idea. Another point which interested me is that Anti-Entropy and Rumor Mongering are compared to epidemic processes which is very good analogy.

Another significant contribution provided by this paper is a bunch of parameters to judge an epidemic technique. One important criteria discussed is the tradeoff between a push VS pull strategy to pass on message updates. A pull strategy could be used when there are numerous independent updates in the system. A push strategy could be used when the database is quiescent.

The other important contribution is that the paper explores the effects of spatial distribution of hosts with regards to update propagation. Anti-Entropy epidemic techniques could do well in a non-uniform spatial distribution compared to the other two techniques.

Applications:

1.> The idea of eventual consistency is very important, many modern databases have such a relaxed criteria for consistency. Google Filesystem has a similar update mechanism where chunk replicas reach all the chunk server in due course of time and not all at once.

2.> Rumor Mongering could be used with a distributed database that tolerates eventual consistency and cares more about efficiency.

Flaws:

1.> Complex Epidemic algorithms have certain amount of failure probability, which means some of the sites may not receive the updated data.

2.> These techniques may not work for certain network topologies.