Coordinated distributed systems (advanced)

As already mentioned briefly in the introduction, there are two main types of coordinated distributed systems depending on what is being coordinated:

1. Coordination of resources: The service is replicated on a distributed resource platform (or infrastructure) so that users in different places can be provided with a service that is relatively close (physically or at least available from various locations), while maintaining the required consistency. Cloud systems and many distributed client‑server systems belong to this category.
2. Coordination of services: Dispersed actors interact to produce a shared distributed service according to certain consistency requirements. For example, transaction databases and distributed ledgers are of this type and require strong consistency. Web‑indexing robots (web crawlers), searches, or logistics applications may operate under weaker consistency requirements.

These types are distinguished only in the next section. Here we discuss general properties that apply to both: basic concepts as well as replication and coordination.

Basic concepts of distribution (advanced)

Synchronization

The interaction of distributed resources and services is implemented through synchronization, which, broadly speaking, takes the following forms:

1. Synchronous: All components of the distributed system are synchronized—that is, kept up to date with each other’s state—step by step or in rounds. Causality is achieved explicitly. Examples include safety‑critical systems such as aircraft fly‑by‑wire control, where predictability and guaranteed real‑time responsiveness are required.
2. Asynchronous: Separate objects take steps in arbitrary order and operate at different speeds. The order of events is ensured through collective interaction. Typical examples include event systems, databases, web indexing robots, etc.
3. Partially synchronous: Some restrictions are applied to ordering, but there is no step‑wise synchronization. Typical examples include SCADA control systems or high‑value transactions in warehouse systems where timely execution affects service correctness.

Reliable group communication

Group communication is needed to ensure reliable delivery of messages among distributed objects. These may be simple direct point‑to‑point messages with appropriate acknowledgements. Alternatively, reliable and secure multicast may be used, with variations that provide redundant channels, or message ordering can be adjusted in publish‑subscribe practices. Channels and messages may be encrypted or signed, though this incurs overhead. Group communication also includes managing authorization information and cryptographic protocols, including PKI and key distribution.

Consensus

Consensus means sharing the same understanding of values, which may be—for example—data or process identifiers. Consensus requires the following properties to hold:

1. Agreement: All correct processes agree on the same value.
2. Validity: The agreed‑upon value is valid, i.e. (as far as possible) correct.
3. Termination: A decision on the value is eventually reached; negotiation does not continue indefinitely.

The particular type of consensus depends on the semantics of the faults being considered (crash, omission, Byzantine, etc.). Fault types are discussed later.

Consistency

Consistency has several nuances. The underlying assumption is always determinism—i.e. running the same procedure leads to the same state.

Strong consistency: Participants must agree on one coherent ordering of operations. The basic model is strict consistency. Linearizability adds the requirement that the observed order of operations matches their real order. Strong models are used in high‑risk applications where consistency is valued more than availability. Enforcing strong constraints introduces delays due to repeated synchronization. Traditional relational databases such as MySQL or Microsoft’s SQL Server, as well as modern NoSQL databases such as MongoDB or Google’s Chubby lock service, implement these models.

Weak consistency: Participants do not necessarily observe the same order of events. This may lead to different states, requiring conflict‑resolution mechanisms depending on the requirements.

1. Sequential consistency: The order of operations performed by each individual process is preserved, even if events from two different processes do not interleave correctly.
2. Causal consistency: The previous requirement is relaxed to apply only to events that are causally related. This occurs exactly when both use the same data and at least one writes.
3. Eventual consistency: Participants eventually reach a consistent state. If consistency is not observed when needed, conflicts are resolved using dedicated mechanisms.

Systems without strong consistency became common with the rise of the Internet, where large‑scale web‑service implementations had to serve huge user populations. High availability was achieved by giving up strong consistency. Examples include Amazon’s Dynamo and Facebook’s Cassandra.

Replication and coordination as reducers of attack surfaces (advanced)

The fundamental challenge in building reliable distributed systems is to support cooperation between distributed objects required to perform a shared task, even when some of those objects or their communication fail. Service operation order must be ensured, and partitioning of distributed resources must be avoided to maintain a holistic “coordinated” resource set.

A general method for implementing a fault‑tolerant service is to replicate servers and coordinate client interactions with server copies. However, no distributed system (e.g. the WWW) can provide more than two of the three CAP properties:

1. Consistency: A single up‑to‑date version of the data exists; each server returns the correct answer to each request.
2. Availability: Each data request eventually receives a response.
3. Partition tolerance: Resistance to servers splitting into mutually non‑communicating groups.

Naturally, security attacks attempt to influence these properties.

Management of replicas is a central coordination mechanism characterizing the functioning of any distributed system. The choice of mechanism depends on the synchronization model, the type of group communication, and particularly the nature of the failures (faults or attacks) being considered. Mechanisms may be simple voting or leader‑election processes, or more complex consensus approaches for handling crashs or Byzantine failure. Transaction‑commit protocols are important, as are identity‑management and PKI infrastructures providing authenticated access control. A few widely used techniques are briefly mentioned here. Authorization and authentication in distributed systems are discussed in a later module.

Paxos

Paxos is a family of complex and highly complex protocols for achieving asynchronous consensus. Initially, any process may propose a value for the data under consideration. If a majority accepts the value in their replies, the protocol may proceed to the next item. The protocol may enter a situation in which processes continue proposing values indefinitely and become stuck in the initial phase because a majority cannot be formed. In practice this is rare, and Paxos remains one of the most widely used coordination protocols. One example is Google’s Chubby file system. The RAFT protocol has been proposed as a simpler alternative offering the same guarantees.

Byzantine fault tolerance (BFT)

Byzantine failure is possible when a set of separated actors constructs its overall view of system state through communication. An attacker may send modulated information (e.g. combinations of correct and incorrect values) to different actors, preventing them from forming the correct view. A Byzantine attack may exploit access control, communication, or coordination services, or the data itself.

Byzantine fault‑tolerant (BFT) protocols use coordinated replication that guarantees correct behavior as long as no more than one third of the processes act incorrectly.

In BFT, processes exchange the values they have received in rounds. The number of rounds required to reach consensus depends on the number of faulty participants. Round‑based execution means the protocol is synchronous. It has been proven that consensus is impossible in the asynchronous case (i.e. Paxos cannot be perfect). Because of the need for synchronous communication and the high message overhead required for BFT, these protocols are used mainly in certain critical applications.

From a security perspective, BFT is an attractive building block for intrusion‑tolerant systems because it tolerates arbitrary malicious behavior. However, identical replicas are not sufficient because they share the same vulnerabilities. An adversary who can corrupt one replica can easily corrupt the others if they are identical. Thus, in addition to replication, diversity or different protection methods are required.

Commit protocols

Many applications, such as databases, require the atomicity property, meaning that all participants either commit an operation or do nothing. In the latter case, any partial changes are rolled back. Two‑phase commit or the stronger three‑phase commit, which is an extension of a BFT protocol, may be used. Although the three‑phase variant is more robust than BFT, it is not widely used—partly because of communication overhead and partly because it is sensitive to network partitioning (cf. the “P” in CAP). In practice, systems use either BFT for simplicity or Paxos for robustness. A typical database update may apply two‑phase commit.

Posting submission...