20. Examination 2002-2003: Error-free message replication & Multi-server client representation

Werner Van Belle¹ - werner@yellowcouch.org, werner.van.belle@gmail.com

1- Programming Technology Lab (PROG) Department of Computer Science (DINF) Vrije Universiteit Brussel (VUB); Pleinlaan 2; 1050 Brussel; Belgium

Abstract : I loved this examination. It used a number of scripts to verify the programs, each of which had to change the behavior of the interaction between client and whiteboard. The first exercise focuses on replicating the behavior of a client on 3 servers and aggregating the answers. The second exam focuses on representing a client onto multiple servers and the last one modifies the behavior of a particular client.

Reference: Werner Van Belle; Examination 2002-2003: Error-free message replication & Multi-server client representation;

1 Foutvrije Gedrags Replicatie

In deze opgave willen we het gedrag van een server proces ontdubbelen zodat het geheel foutentolerant wordt. Het serverprocess is een actor gebaseerde adder, dewelke twee getallen optelt en het antwoord terugstuurd. De clients van dergelijk proces vragen voor het optellen van twee getallen en verifieren het resultaat dat terugkomt.

1.1 De Adder Actor

import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import java.rmi.*;
import java.rmi.server.*;
import java.util.*;

public class Adder
    extends Actor
{
    String proxy;
    
    public Adder(String name, String args[]) throws RemoteException
    {
	super(name);
	proxy=args[1];
	sendMessage(proxy,new ConnectionRequest(actor));
	// System.out.println("Connection request "+actor+" sent");
    }
    
    public void handleMessage(Message m)
    {
	AddRequest req = (AddRequest)m;
	// System.out.println("Adder "+actor+" activated");
	sendMessage(req.comesfrom,
		    new AddAnswer(actor, req.a+req.b,req.message_id));
    }
    
    public static void main(String args[])
    {
	try
	    {
		new Adder(args[0],args);
	    }
	catch (Exception e)
	    {
		System.out.println(e);
		e.printStackTrace();
	    }
    }
}

Important: This version of the adder is different from the adder given in a previous exercise. This adder will automatically send a connection Request to the proxy.

1.2 De Messages

Important: Merk op dat de AddRequest en AddAnswer messages beide een field extra gekregen hebben.

ConnectionRequest

public class ConnectionRequest
  implements Message
{
    String name;
    public ConnectionRequest(String comes)
    {
	name = comes;
    }
}

AddAnswer

public class AddAnswer 
  implements Message
{
    int result;
    int message_id;
    String comesfrom;
    public AddAnswer(String from, int r, int id)
    {
	comesfrom = from;
	result = r;
	message_id=id;
    }
}

AddRequest

public class AddRequest
  implements Message
{
    int a,b;
    int message_id;
    String comesfrom;
    public AddRequest(String comes, int A, int B, int id)
    {
	comesfrom = comes;
	message_id=id;
	a=A;
	b=B;
    }
}

1.3 De Client Actor

import java.awt.*;
import java.rmi.*;
import java.rmi.server.*;
import java.util.Random;

public class Client
    extends Actor
{
    // location of adder process
    String adder;
    // the two number that should be added
    int a;
    int b;
    Random random;

    public Client(String name, String args[]) throws RemoteException
    {
	super(name);
	adder=args[1];
	random=new Random();
	System.out.println("Client "+actor+" started");
	sendNumbers();
    }
    
    public void sendNumbers()
    {
	a=random.nextInt();
	b=random.nextInt();
	// 'actor' is the name of this process
	sendMessage(adder,new AddRequest(actor,a,b,0));
    }

    public void handleMessage(Message m)
    {
	AddAnswer answer = (AddAnswer)m;
	System.out.println(actor+" addition of "+a+" and "+b+" is "+answer.result);
	if (answer.result!=a+b)
	    System.out.println("\n>>>>>>>>>>> This is wrong ! <<<<<<<<<<<<<<<<<<\n\n\n");
	else
	    sendNumbers();
    }
    
    public static void main(String args[])
    {
	try
	    {
		new Client(args[0],args);
	    }
	catch (Exception e)
	    {
		System.out.println(e);
		e.printStackTrace();
	    }
    }
}

1.4 Opgave

De bedoeling van deze opgave is om een Proxy Actor te creeeren dat zich gedraagt alsof het een adder is. De proxy, daarentegen dient zelf geen enkele 'add' functionaliteit te bevatten. Daartoe dient die beroep te doen op een aantal externe Adders. Op deze manier kunnen we zorgen dat verschillende adders zullen aanleiding geven tot 1 consistente resultaat, dat dan terug gestuurd wordt naar de client. Zie bovenstaande figuur. Om het schrijven van de proxy eenvoudiger te maken is de adder reeds aangepast zodat hij een connect request zal sturen naar de proxy, opgegeven op de command-line. De proxy die gemaakt moet worden moet aan een aantal eisen voldoen:

1. Het moet een actor zijn.

2. Het is niet toegestaan de server (adder), de client processes, noch de messages aan te passen. Het enige proces dat geschreven dient te worden is de proxy.

3. De communicatie tussen twee actors verloopt gegarandeert correct. Dit wil zeggen dat de volgorde van de berichten behouden blijft en dat elk bericht exact 1 maal toekomt. Dit wil natuurlijk ook zeggen dat onze proxy deze eigenschap moet respecteren. De berichten verzonden vanuit de client moeten in de correcte volgorde beantwoord worden.

4. De proxy moet elke binnenkomende add-request voorleggen aan minstens 3 verschillende adders.

5. De proxy moet slecht werkende adders detecteren en verwijderen van gebruik.
5a. Een slecht werkende adder kan een adder zijn die niet meer antwoord.
5b. Een slecht werkende adder kan een adder zijn die een fout antwoord geeft in vergelijking met de andere antwoorden. (Hier gaan we er vanuit dat maximum 1 adder in de fout kan gaan)

6. De proxy moet in staat zijn het connecteren of disconnecteren van adders op te vangen.

7. De adders worden manueel gestart. M.a.w. het proxy process kan zelf geen adders spawnen.

8. We werken met een event gebasseerd systeem, niet met Java RMI. De oplossing dient dan ook geschreven te zijn aan de hand van de gegeven library. De library zelf (actor.java) kan niet aangepast worden.

Om te helpen in het detecteren van een uitvallende adder, zullen we moeten terugvallen op timeouts. Deze kunnen geimplementeerd worden als volgt.

1.5 Timeouts

Aangezien we geen mogelijkheid hebben te ontdekken dat ofwel het netwerk down gegaan is ofwel de adder gecrashed is, moeten we werken met timeouts. In ons geval kunnen we een timeout implementeren aan de hand van messages verstuurd naar self. Onderstaande code illustreerd dit.

void handlemessage()
{
   if (message instanceof FlushCommand)
     {
	Date now = new Date();
	long msecs_diff = now.getTime()-last.getTime();
	if (msecs_diff>treshold)
	  {
	     // <too late>
	  }
     }   
   else
     {
	// <not yet too late>
	sendMessage(actor,new FlushCommand)
     }
}

Het is inderdaad zo dat deze timeouts bijzonder processor-consuming kunnen zijn omdat ze constant in een polling loop gaan waarbij ze elke keer checken 'is het reeds te laat ?'. Gelukkig kan dit probleem relatief automatisch opgelost worden, doch aangezien dit niet de focus is van de opgave, mag u gerust dergelijke polling timer gebruiken omdat deze uiteindelijk eenvoudig te construeren zijn.

1.6 Aan de computer

Om te helpen in het designen van een correcte proxy, hebben we een aantal scenarios gegeven die kunnen aanleiding geven tot fouten. Deze staan hieronder beschreven. Een aantal van deze scenarios kunnen automatisch getest worden door gebruikt te maken van de

test<x>_start

Deze scriptjes hangen af van een keypress programmatje dat gecompileert kan worden door

make keypress

in te tikken.

Maak ook zeker dat u, voor u begint te developpen, uw PATH environment variable zodanig uitbreid dat de correcte java virtuele machine erin staat. Wees eveneens zeker dat uw CLASSPATH naar de desbetreffende Java VM point. Dit kan gedaan worden door:

export CLASSPATH=.:$CLASSPATH
export PATH=.:$PATH

Tijdens het testen, wees zeker van voor u start het

./stop

script aan te roepen. Maar al te vaak lopen verschillende actors in elkaars weg omdat ze nog in de background aan het uitvoeren zijn en bepaalde namen gebonden houden in de rmiregistry. In de geleverde code komen een aantal extra adders voor. Deze zijn nodig om de test-scripts te laten werken. Daarom moeten deze allen gecompileerd zijn voor u kan beginnen testen. Daarom:

javac *.java
rmic Actor

De oplossing die u maakt noemt u

Proxy.java

Zorg dat alle classen die u nodig hebt in deze file voorkomen.

1.7 Scenarios

Vereiste 1: Interleaving

Figuur 1a: Bovenstaande tekening is correct gedrag met correcte interleaving van messages.

Figuur 1b: niet correct omdat de message niet correct geinterleaved zijn

De eerste vereiste van de proxy is dat berichten zo snel mogelijk afgehandeld worden. Dit kan gedaan worden door verschillende add-requests (van verschillende) clients te interleaven met elkaar en niet te wachten op het antwoord van de eerste request vooraleer de tweede request door te sturen. Figuur 1a laat zien wat bedoeld wordt. In dit scenario ziet u hoe addrequest B reeds doorgestuurd wordt naar all adders terwijl nog niet alle antwoorden op een eerdere addrequest A ontvangen zijn. Figuur 1b laat zien wat niet mag. In dit voorbeeld zal de proxy alle berichten achterhouden en ze slechts 1 voor 1 afwerken. In dit specifieke scenario zal de proxy slechts request B doorsturen als al de antwoorden van request A binnen gekomen zin en dus de originele request A afgehandelt is. Script test1_start.

Vereiste 2: Kick Offending Adders

Figuur 2a: Goed gedrag. Incorrect answer = verwijder de offending 'adder'

Figuur 2b: Fout gedrag: offending 'Adder' blijft in gebruik

Op het ogenblik de proxy ontdekt dat een van de adders een fout antwoord teruggegeven heeft, mag deze adder in de toekomst niet meer gebruikt worden. Figuur 2a laat zien hoe zulk een scenario er uit ziet. Nadat the proxy ontedekt heeft dat de eerste adder een fout antwoord teruggegeven heeft (zijnde 6), zal deze adder niet meer gebruikt worden in de toekomst. Figuur 2b is een scenario dat illustreert wat niet mag. In dit scenario zal adder 1 verder gebruikt blijven terwijl geweten is dat hij fout kan antwoorden. Script test2_start.

Vereiste 3: Timeouts

Figuur 3a: Standaard gedrag: normal timeout operation

Figuur 3b: Een onverwachte situatie

Gebruik een timer om te ontdekken wanneer een antwoord te laat is. Neem als timeout waarde 10 seconden. Figuur 3a laat zien hoe een adder sterft en hoe de proxy een timeout zal ontdekken. Figuur 3b laat zien hoe de proxy een timeout voor adder1 ontdekt, terwijl deze eigenlijk gewoon heel erg traag is en bijzonder veel 'lag' te verduren gekregen heeft. Wat in dergelijke situatie gedaan wordt is uw vrije keuze (ofwel kicken we de adder voor goed, ofwel accepteren we het antwoord toch nog en doen we verder alsof er niets aan de hand is..). Script test3_start en test4_start.

Vereiste 4: Message Orde & Message Resends

Figuur 4a: Volgorde blijft behouden zelfs indien een resend van een oude message nodig is

Figuur 4b: Message volgorde blijft niet behouden wanneer een message moet herverstuurd worden

Zoals opgegeven in de opgave moet elke request minstens aan 3 processen voorgelegd worden. Als 1 van de processen faalt door geen antwoord terug te geven binnen een gegeven tijdsperiode dan dient, indien nodig, de proxy de request opnieuw door te sturen naar een eventueel nieuwe aanwezige server.

Figuur 4a laat zien wanneer dit problemen kan geven. In de figuur zien we hoe 3 servers reeds geconnecteerd zijn aan de proxy en hoe de proxy de incoming request A doorstuurt naar deze. In fase 2 van dit scenario zal een 4e server de proxy contacteren en zal een 2 addrequest binnenkomen van de client. Deze addrequest zal doorgestuurd worden naar de 4 servers. Op het moment dat nu een timeout plaatsgrijpt moet de addrequest A opnieuw verstuurd worden naar de bijkomende server (omdat anders de addrequest niet beantwoord is door minstens 3 servers). Niettegenstaande is het zo dat addrequest B reeds aan 3 servers voorgelegd is en dus reeds een antwoord geformuleerd kan worden op addrequest B. Dit kunnen we nogthans niet doen omdat eerst addrequest a afgehandelt dient te worden. Script test6_start.

Vereiste 5: Miniumum aantal adders

Figuur 5: Queueing requests totdat er voldoende adders gejoined zijn.

Een van de vereisten is dat elk bericht door minimum een aantal adders behandeld wordt. In ons geval betekent dit eveneens dat als er niet voldoende adders geconnecteerd zijn aan de proxy al de berichten in wait gezet worden totdat ze beantwoord zijn door voldoende adders. Figuur 5 laat zien wat hiermee bedoeld wordt. Script test5_start.

Vereiste 6: Meerdere clients

Uw proxy moet in staat zijn meerdere clients te bedienen. Script test7_start.

2. Realizing one state on multiple servers

In deze opgave willen we het gedrag van een client ontdubbelen en realizeren op een aantal verschillende servers. Elk van deze servers wordt tegelijkertijd benadert door andere actoren, nochthans moet onze adapter ervoor zorgen dat de client-state op alle servers exact hetzelfde is.

2.1 De Playfield Server

De playfield server is een programma dat 3 actors zal starten: playfield1, playfield2 en playfield3. Elke van deze actors werkt volledig onafhankelijk. Elk playfield biedt een locking strategie aan en functionaliteit om posities te kleuren.

Hoofd functionaliteit

• incoming JoinMessage(<from>): wordt gebruikt door een client om als actor erkend te worden op het playfield. Als response wordt altijd een ColorMessage teruggestuurd. Het from-veld bevat de naam van de client actor naar waar het antwoord gestuurd moet worden.

outgoing ColorMessage(<color>, <from>): wordt teruggestuurd door de server op het ogenblik een JoinMessage binnengekomen is. Het color-veld bevat het kleurnummer dat door de client gebruikt moet worden wanneer posities gezet worden. Het from-veld bevat de naam van de server.

• incoming IsFreeMessage(<from>, <x>, <y>): wanneer dit bericht binnenkomt op het playfield, zal een bericht teruggestuurd worden naar <from> met de informatie of de opgegeven positie wel dan niet vrij is. Vooralleer deze message geaccepteerd wordt moet de positie gelocked zijn.

outgoing FreeOrNonFreeMessage(<from>, <free>): Het free-veld bevat true als de opgegeven positie vrij was anders false. Het from-veld bevat de naam van het playfield.

• incoming SetPosition(<from>, <x>, <y>, <c>): Wordt enkel geaccepteerd door het playfield als de gegeven positie gelocked is door <from>. Het from-veld is de naam van de afzender. Het x- en y-veld bevatten de positie waar kleur <c> gezet moet worden. Deze kleur dient overeen te komen met de eerder ontvangen kleur bij het joinen. Als een kleurwaarde 0 doorgegeven wordt, wordt de positie ontkleurd. Deze message heeft geen uitgaand bericht.

Synchronisatie operaties

• incoming LockMessage(<from>, <x>, <y>): dit bericht laat toe een gegeven positie (x,y) te locken voor client <from>. Merk op dat elke lock slechts 1 maal aangevraagd mag worden. Een tweede maal eenzelfde lock aanvragen leidt tot een crash.

outgoing LockReturnMessage(<from>, <lockobtained>): wordt teruggestuurd als antwoord op een binnenkomende lockrequest. <from> zal de naam van de server bevatten en <lockobtained> bevat true als de lock toegekend is aan de client, false in het andere geval.

• incoming UnlockMessage(<from>, <x>, <y>): dit bericht laat toe een gegeven positie weer vrij te geven voor andere clients. Het from-veld bevat de naam van de client. Het x- en y-veld bevatten de positie die vrijgegeven dient te worden. Een positie die niet bezet was door de opgegeven client toch vrijgeven leidt tot een crash. Tweemaal vrijgeven van dezelfde positie leid eveneens tot een crash.

2.2 The Synchronous Flood Actor

Gegeven deze interface zal de synchrone floodactor trachten een zo groot mogelijk deel van het speelveld in te palmen terwijl toch zijn grens gesloten te houden. Een typische interactie bestaat uit twee fasen. De eerste fase bestaat uit het bezetten van een nieuwe positie. De tweede fase bestaat uit het vrijgeven van interne posities. Beide fasen gebeuren afwisselend. Onderstaande figuur heeft een interactie gevisualiseerd:

2.3 The Asynchronous Flood Actor

Een tweede soort floodactor is een tikje anders ontworpen. In plaats van steeds te wachten op antwoord voor elke request zal deze actor een aantal lockrequests tegelijk uitsturen en dan antwoord per antwoord afhandelen. Een typische interactie bestaat uit twee fasen. De eerste fase bestaat uit het bezetten van nieuwe posities. De tweede fase bestaat uit het vrijgeven van interne posities. Beide fasen gebeuren afwisseled. In onderstaande figuur staat een interactie gevisualiseerd:

2.4 Opgave

Figuur 6: Een adaptor die zorgt dat de floodactor op de drie speelvelden tegelijk aanwezig is.

De layout van de standaardopstelling is eenvoudig. Het eerste speelveld is geconnecteerd met een bewegende dot-actor. Het tweede speelveld is geconnecteerd met de flood-actor en het derde speelveld is geconnecteerd met een derde bewegende dot. Met andere woorden, deze drie speelvelden en actors zijn volledig onafhankelijk. Dit willen we veranderen.

De bedoeling van deze opgave is om een adaptor te ontwikkelen die ervoor zorgt dat de floodactor op de drie speelvelden tegelijk aanwezig is, terwijl de twee bewegende dots slechts op het eerste en respectievelijk het derde speelveld aanwezig zijn. Dit is gevisualiseerd in figuur 6. Deze adaptor, die we de tx-adaptor zullen noemen moet voldoen aan een aantal eisen:

1. Het is niet toegestaan de flood actors, de moving dot actors, noch de server actors aan te passen. Het enige proces dat geschreven dient te worden is de tx-adaptor. We werken met een event gebasseerd systeem, niet met Java RMI. De oplossing dient dan ook geschreven te zijn aan de hand van de gegeven library. De library zelf (actor.java) kan eveneens niet aangepast worden.

2. De communicatie tussen twee actors verloopt gegarandeerd correct. Dit wil zeggen dat de volgorde van de berichten behouden blijft en dat elk bericht exact 1 maal toekomt. Dit wil natuurlijk ook zeggen dat onze tx-adaptor deze eigenschap moet respecteren. De berichten verzonden vanuit de client moeten dus in de correcte volgorde beantwoord worden.

3. De tx-adaptor moet ervoor zorgen dat de floodactor op alle 3 de speelvelden vertegenwoordigd is met exact dezelfde vorm. Figuur 'example.jpg' (of example.png) laat zien wat bedoeld wordt.

4. De tx-adaptor moet de kleur die ontvangen wordt vanuit de speelvelden respecteren voor elk speelveld afzonderlijk. M.a.w: als speelveld1 kleur 5 teruggeeft, en speelveld 2 kleur 8 dan moet elke setPosition naar speelveld 1 vertaald worden naar kleur 6 en elke setPosition naar speelveld 2 moet dan kleur 8 bevatten. (dit geld natuurlijk niet voor de 'lege' kleur 0).

5. Het vertalen van lock-requests in de tx-adaptor dient logischerwijze op zulk een manier te gebeuren zodat geen enkele server een verschil opmerkt in de ''client''. Dit wil zeggen dat een lock, van zodra hij niet volledig genomen kan worden hij ook weer vrijgegeven wordt bij diegene die de lock wel hebben toegekend.

6. De tx-adaptor moet in staat zijn te werken met zowel een synchrone flood-actor als asynchrone floodactor.

2.5. Aan de computer

Om te helpen in het designen van een correcte tx-adaptor, hebben we een beperkt aantal test programmas gegeven. Deze noemen:

test<x>_start

1. test1_start: test de gewone floodactor tesamen met uw tx-adaptor. Logfiles worden bijgehouden in tx.log, floodactor.log, ballactor1.log en ballactor3.log.
2. test2_start: test de asynchrone floodactor en uw adaptor. Logfiles worden bijgehouden in tx.log, asyncfloodactor.log, ballactor1.log en ballactor3.log.
3. test3_start: speciaal testje: linkt een floodactor direct aan veld1, linkt een andere floodactor direct aan veld3 en een synchrone floodactor aan de tx-adaptor. Logfiles worden bijgehouden in tx.log, asyncfloodactor1.log, floodactor2.log en floodactor3.log
4. test4_start: deadlock testing met 3 tx-adaptors. Logfiles worden bijgehouden in tx1.log, tx2.log, tx3.log, asyncfloodactor1.log, asyncfloodactor2.log en asyncfloodactor3.log. De volgende links worden onderling opgezet
(4a) AFlood1 - Tx1, Tx1 - Field1, Tx2 - Field2
(4b) AFlood2 - Tx2, Tx2 - Field2, Tx2 - Field3
(4c) AFlood3 - Tx3, Tx3 - Field3, Tx3 - Field1

Deze scriptjes hangen af van een keypress programmatje dat gecompileert kan worden door

make keypress

in te tikken.

Maak ook zeker dat u, voor u begint te developpen, uw PATH environment variable zodanig uitbreidt dat de correcte java virtuele machine erin staat. Wees eveneens zeker dat uw CLASSPATH naar de desbetreffende Java VM point. Dit kan gedaan worden door:

export CLASSPATH=.:$CLASSPATH
export PATH=.:$PATH

Tijdens het testen, wees zeker van voor u start het

./stop

javac *.java
rmic Actor

De oplossing die u maakt noemt u

DistriTxAdaptor.java

3. Kaleidoscoop

Deze opgave is sterk gebasseerd op deze gegeven in sectie 2. Sectie 2.1, 2.2, 2.3 blijven dezelfde.

3.4 Opgave

Gegeven een layout waarbij 1 floodactor werkt op 1 server, schrijf een adaptor die elke operatie die coordinaten nodig heeft ontdubbelt in 4 operaties op de posities , , , . Bijvoorbeeld een setPosition(2,5,c) zal vertaald worden naar

• setPosition(2,5,c)
• setPosition(30,5,c)
• setPosition(2,27,c)
• setPosition(30,27,c)

Deze adaptor zullen we de tx-adaptor noemen:

1. Het is niet toegestaan de flood actors, de moving dot actors, noch de server actors aan te passen. Het enige proces dat geschreven dient te worden is de tx-adaptor. We werken met een event gebasseerd systeem, niet met Java RMI. De oplossing dient dan ook geschreven te zijn aan de hand van de gegeven library. De library zelf (actor.java) kan eveneens niet aangepast worden.

2. De communicatie tussen twee actors verloopt gegarandeerd correct. Dit wil zeggen dat de volgorde van de berichten behouden blijft en dat elk bericht exact 1 maal toekomt. Dit wil natuurlijk ook zeggen dat onze tx-adaptor deze eigenschap moet respecteren. De berichten verzonden vanuit de client moeten dus in de correcte volgorde beantwoord worden.

3. Het vertalen van lock-requests in de tx-adaptor dient logischerwijze op zulk een manier te gebeuren zodat geen enkele server een verschil opmerkt in de ''client''. Dit wil zeggen dat een lock, van zodra hij niet volledig genomen kan worden hij ook weer vrijgegeven wordt bij diegene die de lock wel hebben toegekend.

4. De tx-adaptor moet in staat zijn te werken met zowel een synchrone flood-actor als asynchrone floodactor.

3.5 Aan de computer

Deze scriptjes hangen af van een keypress programmatje dat gecompileert kan worden door

make keypress

export CLASSPATH=.:$CLASSPATH
export PATH=.:$PATH

Tijdens het testen, wees zeker van voor u start het

./stop

javac *.java
rmic Actor

De oplossing die u maakt noemt u

DistriTxAdaptor.java

http://werner.yellowcouch.org/
werner@yellowcouch.org