Chang and Roberts algorithm

Last updated

The Chang and Roberts algorithm [1] is a ring-based coordinator election algorithm, employed in distributed computing.

Contents

The algorithm

The algorithm assumes that each process has a Unique Identification (UID) and that the processes can arrange themselves in a unidirectional ring with a communication channel going from each process to the clockwise neighbour. The two part algorithm can be described as follows:

  1. Initially each process in the ring is marked as non-participant.
  2. A process that notices a lack of leader starts an election. It creates an election message containing its UID. It then sends this message clockwise to its neighbour.
  3. Every time a process sends or forwards an election message, the process also marks itself as a participant.
  4. When a process receives an election message it compares the UID in the message with its own UID.
    1. If the UID in the election message is larger, the process unconditionally forwards the election message in a clockwise direction.
    2. If the UID in the election message is smaller, and the process is not yet a participant, the process replaces the UID in the message with its own UID, sends the updated election message in a clockwise direction.
    3. If the UID in the election message is smaller, and the process is already a participant (i.e., the process has already sent out an election message with a UID at least as large as its own UID), the process discards the election message.
    4. If the UID in the incoming election message is the same as the UID of the process, that process starts acting as the leader.

When a process starts acting as the leader, it begins the second stage of the algorithm.

  1. The leader process marks itself as non-participant and sends an elected message to its neighbour announcing its election and UID.
  2. When a process receives an elected message, it marks itself as non-participant, records the elected UID, and forwards the elected message unchanged.
  3. When the elected message reaches the newly elected leader, the leader discards that message, and the election is over.

Assuming there are no failures this algorithm will finish. The algorithm works for any number of processes N, and does not require any process to know how many processes are in the ring.

Properties

The algorithm respects safety: a process will receive an elected message with its own UID only if his UID is greater than others', and only when all processes agree on the same UID. The algorithm also respects liveness. "Participant" and "not participant" states are used so that when multiple processes start an election at roughly the same time, only a single winner will be announced.

When there's a single process starting the election, the algorithm requires 3N-1 sequential messages, in the worst case. Worst case is when the process starting the election is the immediate following to the one with greatest UID: it takes N-1 messages for the election message to reach it, then N messages for it to get back its own UID, then other N messages to send everyone in the ring the elected message.

This algorithm is not very fault tolerant. Fault tolerance can be increased If every process knows the whole topology, by introducing ACK messages and skipping faulty nodes on sending messages.

See also

Related Research Articles

<span class="mw-page-title-main">Diffie–Hellman key exchange</span> Method of exchanging cryptographic keys

Diffie–Hellman key exchange is a mathematical method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography. Published in 1976 by Diffie and Hellman, this is the earliest publicly known work that proposed the idea of a private key and a corresponding public key.

A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer science that studies distributed systems.

<span class="mw-page-title-main">Distributed hash table</span> Decentralized distributed system with lookup service

A distributed hash table (DHT) is a distributed system that provides a lookup service similar to a hash table: key–value pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys. Keys are unique identifiers which map to particular values, which in turn can be anything from addresses, to documents, to arbitrary data. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.

The Chandy–Lamport algorithm is a snapshot algorithm that is used in distributed systems for recording a consistent global state of an asynchronous system. It was developed by and named after Leslie Lamport and K. Mani Chandy.

In transaction processing, databases, and computer networking, the two-phase commit protocol (2PC) is a type of atomic commitment protocol (ACP). It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort the transaction. This protocol achieves its goal even in many cases of temporary system failure, and is thus widely used. However, it is not resilient to all possible failure configurations, and in rare cases, manual intervention is needed to remedy an outcome. To accommodate recovery from failure the protocol's participants use logging of the protocol's states. Log records, which are typically slow to generate but survive failures, are used by the protocol's recovery procedures. Many protocol variants exist that primarily differ in logging strategies and recovery mechanisms. Though usually intended to be used infrequently, recovery procedures compose a substantial portion of the protocol, due to many possible failure scenarios to be considered and supported by the protocol.

The Temporally Ordered Routing Algorithm (TORA) is an algorithm for routing data across Wireless Mesh Networks or Mobile ad hoc networks.

In distributed computing, the bully algorithm is a method for dynamically electing a coordinator or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.

In computer science, state machine replication (SMR) or state machine approach is a general method for implementing a fault-tolerant service by replicating servers and coordinating client interactions with server replicas. The approach also provides a framework for understanding and designing replication management protocols.

Paxos is a family of protocols for solving consensus in a network of unreliable or fallible processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communications may experience failures.

The Hirschberg–Sinclair algorithm is a distributed algorithm designed for leader election problem in a synchronous ring network. It is named after its inventors, Dan Hirschberg and J. B. Sinclair.

In distributed computing, leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task has begun, all network nodes are either unaware which node will serve as the "leader" of the task, or unable to communicate with the current coordinator. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader.

In fault-tolerant distributed computing, an atomic broadcast or total order broadcast is a broadcast where all correct processes in a system of multiple processes receive the same set of messages in the same order; that is, the same sequence of messages. The broadcast is termed "atomic" because it either eventually completes correctly at all participants, or all participants abort without side effects. Atomic broadcasts are an important distributed computing primitive.

Raymond's Algorithm is a lock based algorithm for mutual exclusion on a distributed system. It imposes a logical structure on distributed resources. As defined, each node has only a single parent, to which all requests to attain the token are made.

Byzantine fault tolerant protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms. The Byzantine agreement protocol is an essential part of this task. The constant-time quantum version of the Byzantine protocol, is described below.

Distributed algorithmic mechanism design (DAMD) is an extension of algorithmic mechanism design.

The Berkeley algorithm is a method of clock synchronisation in distributed computing which assumes no machine has an accurate time source. It was developed by Gusella and Zatti at the University of California, Berkeley in 1989. Like Cristian's algorithm, it is intended for use within intranets.

<span class="mw-page-title-main">Raft (algorithm)</span> Consensus algorthim

Raft is a consensus algorithm designed as an alternative to the Paxos family of algorithms. It was meant to be more understandable than Paxos by means of separation of logic, but it is also formally proven safe and offers some additional features. Raft offers a generic way to distribute a state machine across a cluster of computing systems, ensuring that each node in the cluster agrees upon the same series of state transitions. It has a number of open-source reference implementations, with full-specification implementations in Go, C++, Java, and Scala. It is named after Reliable, Replicated, Redundant, And Fault-Tolerant.

Rocha–Thatte algorithm is a distributed algorithm in graph theory for detecting cycles on large-scale directed graphs based on the bulk synchronous message passing abstraction. This algorithm for detecting cycles by message passing is suitable to be implemented in distributed graph processing systems, and it is also suitable for implementations in systems for disk-based computations, such as the GraphChi, where the computation is mainly based on secondary memory. Disk-based computations are necessary when we have a single computer for processing large-scale graphs, and the computation exceeds the primary memory capacity.

Yo-Yo is a distributed algorithm aimed at minimum finding and leader election in generic connected undirected graph. Unlike Mega-Merger it has a trivial termination and cost analysis.

References

  1. ↑ Ernest Chang; Rosemary Roberts (1979), "An improved algorithm for decentralized extrema-finding in circular configurations of processes", Communications of the ACM, ACM, 22 (5): 281–283, doi: 10.1145/359104.359108 {{citation}}: CS1 maint: multiple names: authors list (link)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.