Algorithm AL Sample Clauses

Algorithm AL. L ∅ − | | ≥ We show in this section that the algorithm AL of Figure 2 implements the failure detector in HSSr[ , Y, n 1] when Y 2 and two processes of Y have different and known identities. A For each process pi, outputi is initially false (line 3). Process pi uses the boolean value of the stable storage variable restartedi to communicate to the other processes if it has ever crashed (initially is false, line 1). If process pi recovers, it will execute lines 19-20, and restartedi will be true (line 19). By definition of the system HSS used to execute L, process pi knows at least two processes’ identifiers with different values. These two known identifiers of Y with different value are IDENT1 and IDENT2 in Figure 2. Then, each process pi whose identifier is neither IDENT1 nor IDENT2 changes outputi to true (lines 4-6). Every η time, η > ∆, each process pi broadcasts heartbeats with (alive, restartedi) messages that arrive synchronously (at most ∆ units of time later) to the rest of processes of the system (line 8). Note that we select a value η greater than ∆ to allow that messages broadcast in line 8 arrive to processes on time in each iteration of line 9. After ∆ units of time, process pi analyzes the messages received (reci) to see if it has to set outputi to true (lines 11-17). Note that once outputi = true, process pi never changes it to false again while it is running. Only if process pi crashes and recovers, line 3 is executed again and outputi is false again, but restartedi will be true in this case. The variable counti counts the number of heartbeats received by pi from processes that are up, and that have never crashed (lines 12-14). If this number of messages is 0, then pi sets outputi = true (lines 15-17). L −