Unit 6 – Coordination in Distributed Systems

83 question-and-answer style flashcards covering key concepts from Unit 6: Coordination, including clock synchronization, logical clocks, mutual exclusion, election algorithms, location systems, event matching, and gossip-based coordination.

What is the main goal of coordination in a distributed system?

To let processes synchronize and manage their interactions so that shared resources are used safely and events are consistently ordered.

How does coordination relate to synchronization?

Coordination manages interactions and dependencies between activities; synchronization (process or data) is a subset that ensures ordering or consistency. Thus, coordination encapsulates synchronization.

Why is coordination harder in distributed systems than in single-machine systems?

Because processes have no shared memory or global clock, suffer from communication delays/failures, and must agree without instant, reliable interaction.

Why is time unambiguous in a centralized system?

All processes read the same kernel clock, so a later read always returns an equal or higher value than an earlier read.

What is clock skew?

The difference in the time values reported by the clocks of different machines due to their crystal oscillators running at slightly different rates.

Give an example of an application harmed by unsynchronized clocks.

The Unix make utility may recompile wrong files if file‐timestamp order is incorrect across machines.

State the two main problems when multiple physical clocks are used.

(1) Synchronizing each clock with real-world (UTC) time. (2) Synchronizing the clocks with each other.

What does UTC stand for, and why is it important?

Coordinated Universal Time; it is the worldwide standard on which global timekeeping and clock synchronization algorithms are based.

What timing accuracy do short-wave UTC radio stations typically deliver in practice?

About ±10 milliseconds due to atmospheric variations.

How can satellites improve UTC accuracy for ground time servers?

By combining several satellite signals, servers can reach accuracies as good as 50 nanoseconds.

What hardware component forms the basis of most computer clocks?

A precisely machined quartz crystal oscillator.

What happens inside the timer on every crystal oscillation?

A counter register is decremented; when it reaches zero a clock-tick interrupt is generated and the counter is reloaded from a holding register.

Define a clock tick.

One interrupt generated by the timer indicating that a fixed period has elapsed.

Why do PCs have battery-backed CMOS RAM with a clock value?

So the date and time survive reboots and need not be re-entered by the user.

What is the consequence of clock skew for distributed applications?

Timestamps may be inconsistent across machines, leading to failures in programs expecting a consistent global time order.

Describe the purpose of Network Time Protocol (NTP).

To synchronize the clocks of Internet hosts by letting clients estimate network delays and adjust time obtained from accurate servers.

Identify the four timestamps (T1–T4) used in a basic NTP exchange.

T1 – client send time, T2 – server receive time, T3 – server send time, T4 – client receive time.

What is the distinctive feature of the Berkeley algorithm?

An active time daemon polls all machines, computes an average, then tells each machine to speed up or slow down; no UTC receiver is required.

Does the Berkeley algorithm aim at real time or internal consistency?

Internal consistency; having all machines agree on the same time is sufficient even if that time differs from real UTC.

Why is clock synchronization tougher in wireless sensor networks?

Nodes are resource-constrained, multihop routing is costly, and energy must be conserved, making frequent, precise time exchanges expensive.

How does Reference Broadcast Synchronization (RBS) differ from earlier protocols?

A sender only broadcasts a reference message; receivers compare arrival times to synchronize with each other, keeping the sender out of the loop.

What observation led Lamport to introduce logical clocks?

Full clock synchronization is unnecessary if processes do not interact; only causally related events need a consistent order.

State the two basic rules of Lamport’s happens-before (→) relation.

1) If two events occur in the same process, their execution order defines →. 2) Send of a message precedes its receive: send → receive.

When are two events considered concurrent in Lamport’s sense?

When neither a→b nor b→a holds; they occur in different processes without causal relation.

What three-step algorithm updates a Lamport logical clock C_i?

1) Increment Ci before each local event. 2) Timestamp outgoing message with current Ci. 3) On receipt, set Cj = max(Cj, ts(m)), then increment C_j.

Why might a receiver ‘fast-forward’ its clock on message arrival?

To ensure its local time is later than the send time, preventing messages from appearing to arrive in the past.

What limitation of Lamport clocks is solved by vector clocks?

Lamport clocks cannot distinguish causally unrelated (concurrent) events, whereas vector clocks can detect causal precedence.

For N processes, how large is each vector clock?

A list of N integers, one logical clock entry per process.

How is a vector clock updated when a process performs an internal event?

The process increments its own entry in the vector by 1.

Describe the vector clock rule on sending a message.

Before sending, the process increments its own entry and attaches the entire vector as the message timestamp.

Describe the vector clock rule on receiving a message.

Increment own entry, then for every index take the maximum of the local vector and the received vector.

Name the two major categories of distributed mutual-exclusion algorithms.

Token-based algorithms and permission-based (quote‐request) algorithms.

How does a token-based mutual-exclusion algorithm work?

A unique token circulates; the process holding the token can enter the critical section and passes the token on after use.

In a permission-based approach, what must a requesting process obtain?

Explicit permission (usually OK messages) from other processes before entering the critical section.

In the centralized mutual-exclusion algorithm, what entity controls access?

A single coordinator process that grants or denies requests for the resource.

How many messages are used per critical-section entry in the centralized scheme?

Three: request, grant, and release.

List two main disadvantages of the centralized mutual-exclusion algorithm.

A single point of failure and potential performance bottleneck at the coordinator.

What information is contained in a request message in the Ricart–Agrawala distributed algorithm?

Resource name, sender’s process identifier, and current Lamport timestamp.

Upon receiving a request, when does a process immediately send back OK?

When it is neither accessing nor requesting the resource, or when the sender’s timestamp is lower than its own pending request.

When may a process enter its critical section in the Ricart–Agrawala algorithm?

After it has received OK from every other process in the system.

How does the Ricart–Agrawala algorithm break ties when timestamps are equal?

Usually by comparing process identifiers; the lower ID wins.

What failure causes global blocking in the basic Ricart–Agrawala algorithm?

Any process crash: lack of reply is interpreted as denial, preventing others from ever collecting all OKs.

How can Ricart–Agrawala be patched to handle lost or delayed messages?

Always reply (grant or deny), use timeouts and retries, and suspect crashed nodes when no response is ever received.

In the token-ring algorithm, what logical structure is imposed on the processes?

A unidirectional logical ring where each process knows its successor.

What is a token in the token-ring algorithm?

A special control message whose possession grants the right to enter the critical section.

After a process finishes its critical section, what must it do with the token?

Pass it to its successor; it may not immediately re-enter using the same token.

Why is losing the token a major issue, and what makes detection hard?

No process can enter the critical section without the token, but the gap between token appearances is unbounded, so absence is hard to distinguish from long use.

How is a crashed process handled in the token-ring scheme?

Its predecessor eventually detects failure (e.g., via missing ACK), removes it from the ring, and forwards the token to the next live member.

What assumption about identifiers underlies most election algorithms?

Each process has a unique identifier known to all other processes.

What is the ultimate goal of an election algorithm?

To have all processes agree on a single coordinator when the previous one fails or a new one joins.

Outline the three steps a process follows in the bully algorithm.

1) Send ELECTION to all higher-ID processes. 2) If nobody responds, declare itself coordinator. 3) If a higher-ID answers, stop; that higher-ID process takes over.

Why is Garcia-Molina’s algorithm called the bully algorithm?

Because the process with the highest identifier ‘bullies’ its way to become coordinator—whenever it’s alive, it wins.

In the ring election algorithm, what does the initiator place in the ELECTION message?

Its own identifier; each subsequent process appends its identifier before forwarding.

How is the new coordinator chosen in the ring-based election?

The process with the highest identifier in the collected list becomes coordinator when the list returns to the initiator.

What message informs all nodes of the election result in the ring algorithm?

A COORDINATOR message containing the winner’s identifier circulated once around the ring.

Why is proximity important in large-scale overlay networks?

To reduce latency and bandwidth by placing frequently communicating processes physically near each other.

What does GPS stand for, and what problem does it solve?

Global Positioning System; it lets any receiver determine its geographic position worldwide.

Roughly how many satellites make up the operational GPS constellation?

Up to 72 satellites (with about 24–32 typically active).

What two key pieces of data does each GPS satellite broadcast?

Its precise orbital position and a timestamp from its on-board atomic clock.

Why do GPS receivers need distance measurements from four satellites?

To solve for three spatial coordinates (latitude, longitude, altitude) plus the receiver’s own clock offset.

Name two practical obstacles in determining satellite distance for GPS.

Signal propagation delay and the receiver’s clock not being synchronized with the satellite.

Why is GPS generally unusable indoors?

Satellite signals are too weak or obstructed to penetrate buildings.

How can Wi-Fi access points help with indoor positioning?

By estimating distance to multiple known APs and triangulating the receiver’s location using a database of AP coordinates.

In publish–subscribe systems, what is a subscription S?

A specification by which a process declares the events or notifications it is interested in.

What is a notification N in event matching?

A message published to announce that a specific event has occurred, possibly carrying event data.

What does the function match(S, N) return?

True if subscription S matches notification N, false otherwise.

Describe the simplest centralized event-matching architecture.

One server stores all subscriptions, compares every incoming notification against them, and forwards matches to subscribers.

Why does a single matching server not scale for large systems?

CPU and bandwidth can become bottlenecks; all traffic funnels through one node.

What is a broker in distributed event matching?

A server that stores some subscriptions and/or forwards notifications within an overlay network of brokers.

List three dissemination strategies for routing notifications through brokers.

Flooding, selective routing, and gossip-based dissemination.

Describe two flooding variants for event dissemination.

(1) Store every subscription at all brokers and unicast notifications to one broker. (2) Store each subscription at one broker and broadcast notifications to all brokers.

What is the goal of selective routing in publish–subscribe overlays?

To forward notifications only along paths leading toward interested subscribers, reducing unnecessary traffic.

What is a gossip protocol in distributed coordination?

A peer-to-peer communication scheme where nodes periodically exchange information with random peers, mimicking epidemic spread.

What are dissemination (rumor-mongering) gossip protocols used for?

To spread information, such as events or background data, throughout the network with bounded load per node.

Differentiate event dissemination gossip from background data dissemination.

Event dissemination gossips periodically independent of events; background dissemination spreads slowly changing data where latency is less critical.

What is the purpose of aggregate-computing gossip protocols?

To compute global aggregates (e.g., max, min, count) by exchanging and combining local values across many rounds.

What property must an aggregate have to be suitable for gossip computation?

It must be computable by fixed-size, pairwise combination of partial results (associative/commutative operations).

Give two examples of advanced structures formed via gossip aggregates.

Building a globally sorted list of nodes or arranging nodes into a tree to compute sums or counts.

What is ‘clock drift rate’ in the context of distributed clocks?

The rate at which a clock deviates from real time, typically expressed as parts per million (ppm).

What does UTC provide to timekeeping systems?

A globally agreed reference time from which local clocks can be synchronized.