Standard Problems
- Atomic commit
- An atomic commit is an operation where a set of distinct changes is applied as a single operation. If the atomic commit succeeds, it means that all the changes have been applied. If there is a failure before the atomic commit can be completed, the "commit" is aborted and no changes will be applied.
- Algorithms for solving the atomic commit protocol include the two-phase commit protocol and the three-phase commit protocol.
- Consensus
- Consensus algorithms try to solve the problem of a number of processes agreeing on a common decision.
- More precisely, a Consensus protocol must satisfy the four formal properties below.
-
- Termination: every correct process decides some value.
- Validity: if all processes propose the same value, then every correct process decides .
- Integrity: every correct process decides at most one value, and if it decides some value, then must have been proposed by some process.
- Agreement: if a correct process decides, then every correct process decides .
- A typical algorithm for solving consensus is the paxos algorithm.
- Distributed search
- Leader election
- Leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task is begun, all network nodes are unaware which node will serve as the "leader," or coordinator, of the task. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader.
- Mutual exclusion
- Reliable Broadcast
- Reliable broadcast is a communication primitive in distributed systems. A reliable broadcast is defined by the following properties:
-
- Validity - if a correct process sends a message, then some correct process will eventually deliver that message
- Agreement - if a correct process delivers a message, then all correct processes eventually deliver that message
- Integrity - every correct process delivers the same message at most once and only if that message has been sent by a process
- A reliable broadcast can have sequential, causal or total ordering.
- Replication
- Resource allocation
- Spanning tree generation
- Symmetry breaking, e.g. vertex coloring
Read more about this topic: Distributed Algorithms
Famous quotes containing the words standard and/or problems:
“There is a certain standard of grace and beauty which consists in a certain relation between our nature, such as it is, weak or strong, and the thing which pleases us. Whatever is formed according to this standard pleases us, be it house, song, discourse, verse, prose, woman, birds, rivers, trees, room, dress, and so on. Whatever is not made according to this standard displeases those who have good taste.”
—Blaise Pascal (1623–1662)
“I’m no good at being noble, but it doesn’t take much to see that the problems of three little people don’t amount to a hill of beans in this crazy world. Someday you’ll understand that.”
—Julius J. Epstein, U.S. screenwriter, Philip Epstein, screenwriter, Howard Koch, screenwriter, and Michael Curtiz. Rick Blaine (Humphrey Bogart)