Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Distributed System > LU5 Coordination and Agreement > Flashcards

LU5 Coordination and Agreement Flashcards

1
Q

What is the critical section (CS) in distributed systems?

A

A segment of code where a process accesses shared resources, requiring mutual exclusion.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Why is mutual exclusion important in distributed systems?

A

to prevent race condition, and protect data integrity and accuracy.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the main challenge in achieving mutual exclusion in distributed systems?

A

The lack of shared variables or facilities provided by a single local kernel.

solution: message passing.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a semaphore?

A

A mechanism that controls access to the critical section by putting processes in a FIFO queue.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How does a semaphore prevent busy waiting?

A

By queuing processes and allowing them to enter the critical section one at a time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Which Java class provides semaphore functionality?

A

java.util.concurrent.Semaphore.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the three essential requirements for distributed mutual exclusion?

A

ME1: Safety, ME2: Liveness, ME3: Ordering.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does ME1 (Safety) ensure?

A

At most one process may execute in the critical section at a time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What does ME2 (Liveness) ensure?

A

Requests to enter and exit the critical section eventually succeed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does ME3 (Ordering) ensure?

A

Requests are granted in the order they were made if one happened before another.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is starvation in distributed mutual exclusion?

A

when a process is indefinitely blocked from accessing a critical section due to unfair scheduling.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Why can’t request time be used for ordering in distributed systems?

A

Due to the lack of a global clock.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How is ordering typically managed in distributed systems?

A

Using the happen-before relationship.

(causal relationship)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What factors are considered in performance evaluation of mutual exclusion algorithms?

A
  • Network Bandwidth consumption
  • client delay
  • system throughput.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a permission-based algorithm for mutual exclusion?

A

An algorithm where processes request permission to enter the critical section.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a token-based algorithm for mutual exclusion?

A

An algorithm where a unique token circulates among processes, granting access to the critical section.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the Central Server Algorithm?

A

A server will grant permission to the client request to enter the critical section by issuing a token

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How does the Central Server Algorithm handle requests?

A

The server queues requests if the token is held by another process.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the main limitation of the Central Server Algorithm?

A

It does not satisfy the ordering requirement (ME3).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is the Ring-based Algorithm?

A

Processes are arranged in a logical ring and pass a token clockwise to manage mutual exclusion.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

How does the Ring-based Algorithm ensure mutual exclusion?

A

Only the process holding the token can enter the critical section.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the primary drawback of the Ring-based Algorithm?

A

The token passing mechanism will continue consumes bandwidth even when no process request access to the CS.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is a multicast-based mutual exclusion algorithm?

A

Processes multicast requests (the timestamp) and enter the critical section when ALL others have replied. (confirming no earlier requests)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What role do logical clocks play in multicast-based algorithms?

A

They help order requests based on timestamps.
(from lower–> higher timestamp)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What is Ricart and Agrawala’s algorithm?
A multicast-based algorithm where processes send **requests and wait** for replies from **ALL other processes** before entering the CS.
26
What is Maekawa’s voting algorithm?
It ensures mutual exclusion by having each process ask for permission from a **subset of peers** (called a voting set). These subsets **overlap**, meaning *at least one* peer in the subset is shared between *any two* groups. The shared peer ensures that only one process can get all the permissions it needs at a time, **preventing** two processes from entering the CS simultaneously.
27
How does Maekawa’s algorithm reduce message complexity?
By requiring permission from only a subset of processes instead of all.
28
What is a key disadvantage of Maekawa’s algorithm?
It is prone to deadlock.
29
How can Maekawa’s algorithm be made deadlock-free?
By queuing requests in happen-before order.
30
What is fault tolerance in mutual exclusion algorithms?
The ability of the algorithm to handle **message loss** or **process crashes**.
31
Which mutual exclusion algorithm cannot tolerate any process crash?
**The Ring-based Algorithm** (relies on the continuous and unbroken circulation of a token among all processes in the ring) ## Footnote * **Maekawa’s** algorithm **can** tolerate **some** process crash failures: if a crashed process is *not in a voting set* that is required. * The **central server** algorithm **can** tolerate the crash failure of a client process that neither holds nor has requested the token.
32
Which algorithm can tolerate some process crashes?
Maekawa’s algorithm. (as long as the crashed process is not in a voting set that is required.)
33
How does Ricart and Agrawala’s algorithm handle process crashes?
By implicitly granting requests from crashed processes using **timeout**
34
What is an election algorithm?
An algorithm used to choose a unique process to play a specific role, such as a coordinator.
35
What are the requirements of an election algorithm?
E1: Safety (unique election), E2: Liveness (eventual election).
36
What is the Ring-based election algorithm?
Processes send messages clockwise around a ring to elect the process with the largest identifier.
37
How does the Ring-based election algorithm handle failures?
It assumes no failures occur, making it less practical.
38
What is the Bully algorithm?
An election algorithm where the process with the highest identifier becomes the coordinator, even if the current one is functioning.
39
How does the Bully algorithm detect failures?
By using timeouts in a synchronous system.
40
What is the best-case scenario for the Bully algorithm?
The process with the second highest ID detects the failure and immediately becomes the coordinator.
41
What is the worst-case scenario for the Bully algorithm?
The process with the lowest ID detects the failure, leading to O(N^2) messages.
42
What is the consensus problem in distributed systems?
Getting processes to agree on a value after proposals are made.
43
What are the requirements of a consensus algorithm?
Termination, Agreement, and Integrity.
44
What is the Byzantine Generals Problem?
A scenario where generals must agree on a common action despite some being treacherous.
45
How does the Byzantine Generals Problem differ from consensus?
A distinguished process (commander) proposes the value instead of each process proposing.
46
What is interactive consistency?
A variant of consensus where processes agree on a decision vector of values for each process.
47
How many rounds are needed to reach consensus with up to f crash failures?
At least f + 1 rounds.
48
What is the termination requirement in consensus?
Each correct process eventually sets its decision variable.
49
What is the agreement requirement in consensus?
All correct processes must have the same decision value.
50
What is the integrity requirement in consensus?
If all correct processes propose the same value, they must decide on that value.
51
How is the Byzantine Generals Problem solved?
Using digital signatures or majority voting in larger groups.
52
What is the minimum number of processes required to solve the Byzantine Generals Problem?
More than 3f processes are needed to tolerate f faults.
53
What is the role of digital signatures in the Byzantine Generals Problem?
They help distinguish between correct and faulty processes.
54
What happens if a process crashes in the Central Server Algorithm?
It can tolerate the crash if the process does not hold or has not requested the token.
55
What is the synchronization delay in distributed mutual exclusion?
The time between one process exiting and the next entering the critical section.
56
How does the Central Server Algorithm measure throughput?
By the round-trip time of release and grant messages.
57
What is the client delay in mutual exclusion algorithms?
The delay experienced by a process at each entry and exit operation.
58
How does the Ring-based Algorithm manage token passing?
Processes pass the token clockwise; if not needed, it's forwarded immediately.
59
What happens if a token is lost in the Ring-based Algorithm?
The system cannot tolerate this, leading to failure.
60
What is the purpose of Lamport clocks in distributed mutual exclusion?
To provide a logical ordering of events.
61
What is the difference between Ricart and Agrawala’s algorithm and Maekawa’s algorithm?
Ricart and Agrawala require replies from all processes, Maekawa from a subset.
62
What is the advantage of using multicast in mutual exclusion?
Ensures ordering and fairness by collecting replies from all processes.
63
How does a process enter the critical section in Ricart and Agrawala’s algorithm?
By receiving replies from all other processes after sending a request.
64
How does Maekawa’s algorithm ensure mutual exclusion?
By requiring overlapping voting sets where only one process can receive enough votes.
65
What is the effect of process failure on consensus algorithms?
It may delay or prevent consensus unless fault-tolerant mechanisms are in place.
66
How does the Bully algorithm handle concurrent elections?
Processes with higher IDs bully others and take over the election process.
67
What is the main challenge in the Byzantine Generals Problem?
Distinguishing between faulty and correct generals.
68
What is the purpose of election algorithms in distributed systems?
To select a unique leader or coordinator among processes.
69
How does the Ring-based election algorithm elect a coordinator?
By circulating identifiers and selecting the highest one.
70
What are the three states in multicast synchronization?
RELEASE (outside CS), WANTED (requesting CS), HELD (inside CS).
71
What happens when two processes request the critical section simultaneously in multicast?
The process with the lower timestamp enters first.
72
How does fault tolerance vary among mutual exclusion algorithms?
Depends on message reliability and process crash handling capabilities.
73
What is the impact of unreliable channels on mutual exclusion algorithms?
They may fail if messages are lost, as none tolerate unreliable channels well.
74
What ensures fairness in distributed mutual exclusion?
Proper ordering of requests and prevention of starvation.
75
What is the main drawback of the Central Server Algorithm in distributed mutual exclusion?
It creates a single point of failure.
76
What is a critical section problem?
A problem where multiple processes need exclusive access to shared resources.
77
How do logical clocks help in distributed systems?
They provide a mechanism for ordering events without a global clock.
78
What is the purpose of the semaphore's acquire() method?
To request entry into the critical section.
79
What is the purpose of the semaphore's release() method?
To signal that the process has exited the critical section.
80
How does the multicast-based algorithm ensure all processes are synchronized?
By requiring replies from all other processes before entering the critical section.
81
What is a voting set in Maekawa’s algorithm?
A subset of processes that grant permission to enter the critical section.
82
How does the Bully algorithm prevent lower-ID processes from becoming coordinators?
Higher-ID processes take over the election when detected.
83
What is the role of timeouts in the Bully algorithm?
To detect coordinator failure and initiate elections.
84
How does the Ring-based election algorithm handle message passing?
Messages are passed clockwise until the highest ID is found.
85
What is the main limitation of consensus algorithms in asynchronous systems?
Difficulty in handling arbitrary process failures.
86
How does the Byzantine Generals Problem illustrate the need for consensus?
It shows how disagreement among processes can lead to failure.
87
What is the role of the commander in the Byzantine Generals Problem?
To propose a value that lieutenants must agree on.
88
What is the effect of process crashes on the Ring-based Algorithm?
It disrupts the token passing, leading to failure.
89
How do distributed systems achieve agreement without a fixed master?
By using consensus and election algorithms to select coordinators dynamically.
90
What is the importance of synchronization delay in mutual exclusion?
It affects the overall throughput of the system.
91
How does the Ricart and Agrawala’s algorithm handle queued requests?
Processes reply to queued requests after exiting the critical section.
92
What ensures integrity in consensus algorithms?
Processes must decide on a proposed value if all propose the same.
93
How does Maekawa’s algorithm optimize bandwidth usage?
By reducing the number of messages needed to grant permission.
94
What is the key challenge in the consensus problem?
Ensuring agreement despite process failures.
95
How does the Byzantine Generals Problem demonstrate fault tolerance?
It highlights the challenges of reaching agreement with faulty participants.
96
What is the impact of process crashes on consensus in synchronous systems?
Consensus can still be achieved if up to f processes crash.
97
How does the Central Server Algorithm manage token release?
Processes send a release message to the server after exiting the critical section.
98
What is the main purpose of mutual exclusion in distributed systems?
To ensure that only one process accesses shared resources at a time.
99
What is the significance of happen-before ordering in distributed mutual exclusion?
It helps establish the correct sequence of events without a global clock.
100
What distinguishes Ricart and Agrawala’s algorithm from other mutual exclusion algorithms?
Its reliance on multicast requests and replies from all processes.
101

Distributed System (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions