Tla+/Pluscal Modeling Of Synchronized Circular Consensus Algorithm

In my distributed systems cast for Fall 17, I assigned modeling of the synchronized circular consensus algorithm equally the commencement project. I direct maintain been assigning TLA+/PlusCal modeling projects inwards my cast for the final iv years too releasing the projects too their solutions. I believe this is useful for the distributed systems community, because at this betoken the barrier earlier wider adoption of TLA+ tools seems to hold out the lack of to a greater extent than TLA+ modeling examples of algorithms/systems. My destination is to furnish a TLA+/PlusCal illustration for everything I learn inwards the class. This agency the students volition larn a hands-on sense inwards algorithms pattern too dealing alongside the intrinsic complexities of distributed systems: concurrent execution, asymmetry of information, concurrency bugs, too a serial of untimely failures.

Here is about previous discussion/context nearly why I started assigning TLA+/PlusCal modeling projects inwards distributed systems classes.

Timing of the project

I intend I timed this projection well. In the commencement calendar month of the semester, I direct maintain covered reasoning nearly distributed programs inwards price of security too progress properties too gave them sufficient introduction to TLA+/PlusCal equally well. While the students worked on the project, I covered time/state inwards distributed systems (logical/vector clocks, distributed snapshots, asynchrony concerns), too distributed usual exclusion too dining philosophers.

The submission deadline for the projection was but earlier I embrace consensus. Working on the projection prepared the students to appreciate the challenges of consensus, too primed them nearly the issues alongside about hands on practice. So, this is inwards about sense this is my misfortunate man's implementation of a flipped classroom.

The Project 1 makes unrealistic assumptions of synchronized rounds too reliable channels. Last calendar week I told the students nearly why too how these needs to hold out relaxed further, too that made a real dainty introduction to Paxos too the failure detectors give-and-take that comes after.

Synchronized consensus

Every procedure broadcasts (to all other processes, including itself) its initial value v. In a synchronous network, this tin hold out done inwards a unmarried "round" of messages. After this round, each procedure decides on the minimum value it received.

If no faults occur, this algorithm is correct. In the presence of a crash fault, however, a work tin arise. In particular, if a procedure crashes during a round, about processes may direct maintain received its (low) initial value, but others may non have. (Note that the channels are e'er assumed to hold out fault-free; they deliver messages reliably in i trial a message is set to the channel.)

Use the template below equally your starting point, too fill upwards inwards the redacted parts. Write too seek an invariant holding to capture the Agreement holding of the consensus protocol. The understanding holding should hold out satisfied when FAILNUM=0, i.e., when no node is allowed to fail. The holding volition neglect to hold out satisfied when FAILNUM>0. In that case, write inwards the comments section, later on the "================" line, your findings/observations nearly how the Agreement holding is violated.

Extending the algorithm to address crash faults

To address crash faults, consider this simplifying assumption: say that at most 1 procedure tin crash. How tin nosotros modify the algorithm to direct maintain such a failure? (Note in i trial again that the channels are e'er fault-free; they deliver messages reliably in i trial a message is set to the channel.)

Answer: yesteryear using 2 rounds. In the 1st round, processes broadcast their ain initial value. In the 2nd round, processes broadcast the minimum value they heard. Each procedure too then decides on the instant value amid all the sets of values it received inwards the 2nd round.

If the i crash occurs during the commencement round, the 2nd circular ensures that all processes direct maintain the same laid of values from which to decide. Else, if the i crash occurs during the 2nd round, the commencement circular must direct maintain completed without a crash too thence all processes direct maintain the same laid of values from which to decide.

Without knowing/referring-to FAILNUM, modify your commencement PlusCal algorithm to accomplish consensus inwards the presence of crash faults. The fundamental observation is that if no crash occurs during a round, all processes direct maintain the same laid of values from which to create upwards one's hear too they correctly create upwards one's hear on the same minimum value.

Future projects

For the 2nd project, I am assigning 2 stage transaction commit modeling. There are already models of this available from Lamport's webpage, too I inquire students to model what happens when the initiator/transaction managing director (TM) fails, how would a backup (TM) accept over, too what type of problems would arise inwards an asynchronous organisation where failure-detection timeouts may fail.

I don't know what projects I volition assign adjacent year. Viewstamped replication modeling maybe? Another interesting i would hold out modeling blockchains too consensus? Feel gratuitous to advise me ideas inwards the comments or via email.

While the projects may alter every year, i matter is invariant: My cast enables you lot to start out a lifelong career inwards modeling, regardless of your looks.  And equally I proceed my career inwards modeling, I give away that, yes, the black life is pretty exciting: TLA+ has a agency of enticing people to ship away midnight oil.

Share this post