Objectives

Each group should implement a fault-tolerant version of a simplified tuple space, called RSTS (Resilient Simplified Tuple Space). 

The tuple space shall be replicated over a set of processes, and deployed over an APPIA channel ensuring virtual synchrony.

Clients shall be able to submit operations via any of the processes that replicated the tuple space.

RSTS - Programming model

RSTS adopts a programming model inspired to the Tuple Space approach [1,2]

 The main simplification that we are introducing with respect to the original tuple space model is to allow for storing a statically defined type of tuples, whose fields are a triplet of strings: 

                <String s1, String s2, String s3>

As in the original tuple space model, we say that a tuple is a template if at least one of its fields is left "unspecified", meaning that it matches any value for that field. In RSTS, we assume, for simplicity, that the special value "*" is used to mark a field of a tuple as unspecified. A template has from 1 to 3 unspecified fields.

The tuple space should support the following operations:

·       void write (Tuple out): creates and adds the Tuple out to the tuple space without affecting any other tuple.

·       Tuple read (Tuple rd): retrieves content of one tuple matching the template rd, without affecting any other tuple. The operation shall block in case no tuple exists that matches the template.

·       Tuple take (Tuple in): retrieves one tuple that matches the template in and removes it from the tuple space. Each tuple is consumed by only one take operation. As for read operations, the primitive should have blocking semantics (see read).

RSTS - Fault-tolerance

The RSTS shall maintain data fully in-memory and achieve durability by maintaining a full copy of the tuple space at each replica.  STRS shall be designed to tolerate a minority of crash (i.e., non-byzantine) faults. 

STRS is built on the assumption that there are at most N (e.g. N=5) replicas and that replicas process operations only if they are in a view that contains has a majority of replicas.

Students shall take advantage of the set of protocols included in the Appia Library (e.g., View synchrony, Total Order Broadcast, Uniform Reliable Broadcast) to build replication mechanisms that ensures the following properties:

SAFETY

·       state changing (i.e., write or take) operations are executed atomically, i.e. if a replica executes a state-changing operation, then all correct processes shall execute them.

·       There exists a serial order for all operations that agrees with i) the causal order among operations and ii) the sequential specification of a tuple space.

LIVENESS

·       Let p be a correct process that issues an operation while in the majority view, and that never leaves it (although possibly delivering different views, all containing a majority of replicas). All operations issued by p eventually complete.

The QoS provided by the Appia channels used by RSTS shall be selected in order to maximize efficiency, while preserving correctness.

 Students should also deal with scenarios in which nodes join the RSTS platform for the first time, or re-join the majority view after a network partition.  In these situations the current state of the tuple space shall be migrated to the joining nodes, properly synchronising the execution of concurrent operations that applications submit in the meanwhile. Usage of Virtual Synchrony is strongly recommended to simplify the development of these mechanisms.

Dates

 A zip file containing the code should be sent to romano@inesc-id.pt. Limit date is May, 22th.

Discussions will occur during the laboratory of May, 28th.

Written Report

Along with the code, students are required to deliver a pdf document with the following sections:

·       Appia Stack used to implement RSTS

·       Description of how each operation is implemented

·       A set of instructions explaining how to run the code and a set of test cases demonstrating that RSTS is correctly implemented.