TupleSpaces

A distributed shared memory system built on the Linda tuple space model. Clients interact with a replicated cluster of servers to put, read, and destructively take string tuples, with consistency guarantees maintained across three replicas through a custom mutual exclusion protocol and per-client request ordering.

Group T13 | Distributed Systems, IST 2025 | Difficulty: I am Death incarnate!

Team Members

Number	Name	User	Email
106213	Dinis Gonçalves Rodrigues	https://github.com/DinisRodrigues10	mailto:dinis.g.rodrigues@tecnico.ulisboa.pt
106378	Luca Grespan Dallalana	https://github.com/Luca-Dallalana	mailto:luca.dallalana@tecnico.ulisboa.pt
107157	Inês Brandão Alves	https://github.com/ines-alves	mailto:ines.b.alves@tecnico.ulisboa.pt

---

Tech Stack

• Languages: Java 17, Python 3
• Communication: gRPC (Protocol Buffers / proto3)
• Build: Maven 3.8+
• Concurrency: Java synchronized / wait / notifyAll primitives

---

Features

• put — insert a tuple into all replicas; returns to the client immediately while replication completes in the background
• read — non-destructively retrieve a tuple matching a regex pattern; returns from whichever replica responds first
• take — atomically remove a tuple from all replicas using a two-phase voting protocol
• getTupleSpacesState — inspect the combined tuple list across all replicas
• Blocking operations — read and take block until a matching tuple exists
• Linearizability — per-client request IDs enforce that each client's operations execute in issue order across all replicas
• Configurable delay injection — artificial per-replica delays can be injected via gRPC metadata headers, useful for testing race conditions
• Dual client support — interactive CLI clients in both Java and Python

---

Architecture / How It Works

The system has four layers:

Client (Java or Python)
        |  gRPC
    Front-End (Java proxy, port 2001)
        |  gRPC  (fan-out to 3 replicas)
 Server 1   Server 2   Server 3
(port 2002) (port 2003) (port 2004)

Contract defines the shared gRPC service in TupleSpaces.proto. All modules depend on it.

SingleServer holds an in-memory list of tuples and a votedTuples map that tracks which tuples are locked for a pending take. It enforces per-client linearizability by blocking any request whose requestId is not exactly one ahead of the last processed request from that client.

Front-End is itself a gRPC server that clients talk to. It fans requests out to all three replicas asynchronously using a ResponseCollector barrier:

• put: fires requests to all three replicas and immediately returns to the client; waits for all three confirmations before allowing the same client's next operation.
• read: fires to all three replicas, returns as soon as the first response arrives.
• take: implements a simplified Maekawa voting algorithm for mutual exclusion:
  1. Enter phase — sends enterTake to the two replicas in the client's voter set (clientId % 3 and (clientId + 1) % 3). Each replica locks all matching, currently unlocked tuples and returns their identities.
  2. Intersection — the front-end computes the intersection of both replies. A tuple appears in the intersection only if both replicas had it available and unlocked simultaneously.
  3. Exit phase — sends exitTake to all three replicas. If an intersection exists, the chosen tuple is removed; otherwise all locks are released. On empty intersection, the front-end applies exponential backoff and retries.
  4. The client receives the matched tuple as soon as the intersection is found, before the exit phase completes.

Clients (Java and Python) connect to the Front-End and expose an interactive REPL that accepts put, read, take, getTupleSpacesState, sleep, and exit commands.

---

Getting Started

Prerequisites

• Java 17
• Maven 3.8+
• Python 3 with grpcio and grpcio-tools for the Python client

Verify:

javac -version
mvn -version
python3 --version

Build

From the project root, compile and install all modules:

mvn clean install

This generates the gRPC stubs for both Java and Python from the proto definition.

Run

Start three replica servers (each in a separate terminal):

cd SingleServer
mvn exec:java -Dexec.args="2002"
mvn exec:java -Dexec.args="2003"
mvn exec:java -Dexec.args="2004"

Start the Front-End proxy:

cd Front-End
mvn exec:java -Dexec.args="2001 localhost:2002 localhost:2003 localhost:2004"

Start a client (connect to the Front-End on port 2001):

# Python client
cd Client-Python
python3 client_main.py localhost:2001 1

# Java client
cd Client-Java
mvn exec:java -Dexec.args="localhost:2001 1"

Add -Ddebug to any Maven command to enable verbose logging:

mvn exec:java -Dexec.args="2002" -Ddebug

---

Usage

Store a tuple:

> put <alice>
OK

Read a tuple non-destructively (regex pattern):

> read <alice>
OK
<alice>

Atomically remove a tuple:

> take <alice>
OK
<alice>

Inspect all tuples in the space:

> getTupleSpacesState
OK
[<alice>, <30>]

Pause execution (useful in scripted test scenarios):

> sleep 2

Tuples must be enclosed in angle brackets: <value>. The read and take commands accept Java regex patterns, so <a.*> matches any tuple starting with a.

---

What I Learned / Challenges

The hardest part was correctly implementing the two-phase take with Maekawa's algorithm across three replicas without deadlocks. The tricky invariant is that a client must release all its locks when no intersection is found, otherwise two clients waiting on each other's locked tuples would deadlock forever. Getting the exitTake logic right (release all locks held by the requesting client even on an empty result) took careful reasoning about the locking state. I also had to handle the interaction between the front-end's per-client request ordering and the take's retry loop, since a retried take needs a new request ID while a blocked put from the same client has to wait for the take to finish before it can proceed.