Topic: updating information with rumor mongering and random updates

topics > computer science > database > Group: distributed database

computational mail
replicated data
updating information in Clearinghouse and Grapevine
updating information in a distributed system


Rumor mongering is repeated updates until almost everyone knows. Clearinghouse compared databases at random in case rumor mongering failed.

Two-phase gossip uses timestamps and read quorums to survive site crashes, network partitions, and communication errors. (cbb 8/06)

Subtopic: eventual update up

Quote: rumor mongering -- mail updates until they're old news at multiple sites [»demeA8_1987]
Quote: Clearinghouse's update algorithm only requires eventual delivery of repeated messages [»demeA8_1987]

Subtopic: deletion up

Quote: use death certificates to delete items -- retain dormant certificates [»demeA8_1987]

Subtopic: random, exact updates up

Quote: use anti-entropy as a backup for rumor mongering [»demeA8_1987]
Quote: anti-entropy compares databases at random -- is much slower than direct mail [»demeA8_1987]
Quote: anti-entropy by recent updates and comparing checksums [»demeA8_1987]

Subtopic: random updates up

Quote: epidemic algorithm for peer-to-peer broadcast; each node randomly forwards messages a limited number of times [»eugsPT5_2004]

Subtopic: locality up

Quote: favor nearby servers for anti-entropy and rumor mongering updates [»demeA8_1987]

Subtopic: two phase gossip up

Quote: two phase gossip--replicated data objects with checkpoint and event history; roll-forward an object when all sites have complete histories [»heddA10_1989]
Quote: two phase gossip best for systems that use distributed and replicated event histories for large data objects [»heddA10_1989]
Quote: in two phase gossip, each site keeps timestamp vectors that indicate the completeness of its histories and every other site's histories [»heddA10_1989]
Quote: two phase gossip uses quorum consensus; a query uses a quorum to gather a complete history for an object; an update writes a quorum [»heddA10_1989]
Quote: two phase gossip survives site crashes, network partitions, an message delays, reorderings and losses

Related Topics up

Topic: computational mail (11 items)
Topic: replicated data (51 items)
Topic: updating information in Clearinghouse and Grapevine (11 items)
Topic: updating information in a distributed system
(50 items)

Updated barberCB 3/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.