Problems with Distributed Coordination

A brief working note

David E. Bakken, Ph.D.

February, 2018

This short document lists the many problems that have to be dealt with when employing distributed consensus in the IoT, Remedial Action Schemes (RAS) in power grids, and many other contexts. An overview of this space can be found in [TS92] and a detailed survey in [BM93]. More recent surveys, as well as a large number of new results, exist but are beyond the scope and purpose of this document.

1. Variable network delay – Messages may arrive in different order or get missed completely.

Solutions with distributed computing (or good programming):

a. Timeouts to detect delayed or missing messages should be adjusted dynamically based on current network conditions (it should not be too small or too large).

b. Multiple message transmission retries may be required to receive missing messages.

2. Variable computational delay – The coordinating systems (or programs) may have different computational times because of different underling computational hardware or software used at different locations.For example: Same application software may be running in simple PCs and high performance servers. Obviously, the computational time will vary and hence overall performance of the whole system needs to be well balanced.

Solutions with distributed computing design:

a. Load balancing is required.

3. Different messages arriving in different order at each destination -

Solutions with distributed computing design:

a. Message ordering (or event ordering) is required. Depending the requirements of the application, different type of message ordering need to be supported.

i. FIFO ordering

ii. Causal ordering

iii. Total ordering

4. Different failure types seen at each coordinating process. – Failure detection and handling of different type of failures like crash failures, message omission, message corruption, value type of failures, byzantine failures. It is difficult to identify all these of failures and provide fault tolerance support for each of them.

Solutions with distributed computing design:

a. Crash failures: Crash failures of remote processes need to be detected. To periodically check the availability (or unavailability) of remote processes, a heartbeat mechanism need to implemented. For example, few processes in the neighborhood can decide to monitor each other. If any process within this subgroup is detected unreachable, this information can be broadcasted (through gossip dissemination) to rest of the processes in the group.

(Naïve approach would be for all processes to monitor each other which may lead to different status interpretation of remote processes due to variable network delays etc.).

b. Omission failures: Timeouts need to be implemented to detect omission failures. Timeouts need to be calculated based on current network conditions. Based on the application requirement, message retry mechanism can to be implemented.

c. Message corruption

d. Byzantine failures: There may be cases where in failures observed in the communicating system might be arbitrary in nature, in which a process can arbitrarily omit to send a message, or send conflicting messages to different processes, or send duplicate messages etc. These type of failures can be unintentional (due to software or hardware malfunction) or intentional (malicious) and is difficult to detect and recover from them. Signed messages need to be used to guarantee authenticity of sender.

5. Group Membership issues: Each member of the group should have consistent view of all the members of the group (list of current members, list of faulty members) so that they can make consistent decision based on current membership state. The group membership service logic needs to be decoupled from the application logic, so that the application logic is not concerned with group management activities.

Solutions with distributed computing design:

a. A robust group membership service should deliver the view changes (e.g., new member joined, member removed, member faulty or unreachable etc.) consistently to all the members of the group.

b. Failure detection and handling: A heartbeat mechanism needs to be used to detect crash failures. Some failure recovery mechanism can be handled by the group membership service. For example, check point the data and commands regularly. And when a process crashes, the group membership service can restart the crashed process and rolled back to last safe check point.

6. Leader Election and Consensus: Naïve implementation of leader election and consensus would miss the boundary cases such as missing/delayed messages, corrupt messages and crash and byzantine type of failures.

Solutions with distributed computing design:

a. Leader election and consensus algorithms use failure detectors to detect different type of failures and increase the execution (algorithm) rounds in an attempt to confirm faulty process and receive missing or delayed messages or uncorrupted messages from other processes.

b. Upper bound on the maximum number of rounds in presence of high number of faulty processes (e.g., crashed processes) needs to be fixed. This is required to reduce the execution time (and unnecessary repetitive rounds).

7. Distributed data access synchronization – Concurrent data access of shared resource by multiple processes is problematic as the outcome of any such data may depend on the execution order, and so synchronization is required. The clocks at individual processes may vary and hence happened-before relationship based on clocks (or time) cannot be correctly established.

Solutions with distributed computing design:

a. Mutual exclusion algorithms using logical clocks and vector clocks.

b. If the system is fairly synchronous (time bounded), mutual exclusion algorithms for tightly synchronous clocks can be used, and would provide quicker data synchronization and much quicker failure detection.

8. Scalability: Performance bottleneck becomes an issue.

Solutions with distributed computing design:

a. Caching and replication need to be employed.

Context: this is not the whole set of problems and solutions. They can be understood in the following context (from [BM93]: Consensus problems in fault management):

[BM93] Michael Barborak and Miroslaw Malek, The Consensus Problem in Fault-Tolerant Computing. ACM Computing Surveys (25:2), June 1993, 171-220.

[TS92] John Turek and Dennis Shasha, The Many Faces of Distributed Consensus, IEEE Computer (25:6), June 1992, 8-17.