17. Examination Questions 1999-2000

Werner Van Belle¹ - werner@yellowcouch.org, werner.van.belle@gmail.com
Johan Fabry¹ - jfabry@dcc.uchile.cl

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

Abstract : A variety of examination questions used in 1999-2000

Reference: Werner Van Belle, Johan Fabry; Examination Questions 1999-2000;

Gnutella

Napster is een programma dat gebruikt wordt om muziek te sharen en online te brengen. Iedreen die napster draait als client connecteert aan een centrale napster server die opgeeft waar andere napster clients draaien. Op het ogenblik er gezocht wordt naar een bepaalde file wordt een file-request naar de centrale server gestuurd die teruggeeft welke napster clients deze files bevatten. De gebruiker selecteert dan van welke client de file afgehaald moet worden. Eens dit gedaan is wordt een connectie gelegd met de client in kwestie om de file af te halen.

Gnutella is een gelijkaardig programma dat dezelfde functionaliteit aanbied. Doch op een ietwat intelligentere manier. Het grootste verschil is dat men niet meer steunt op een centrale server.

Bespreek hoe dit in zijn werk gaat (of kan gaan). Bespreek

het design, hoe mensen connecteren en hoe gezocht wordt
het protocol dat gebruikt wordt tussen verschillende gnutella programmas
bespreek threading op het ogenblik we TCP/IP gebruiken

Gedistribueerde Excel

Stel dat we verschillende mensen tegelijker tijd op 1 spreadsheet willen laten werken. Iedereen kan overal aanpassingen maken en men ziet elkaars cursor in real time. Het systeem houd geen rekening met locking van velden.

Implementeer dergelijk systeem in CORBA.

Schets een design (wat draait waar, hoe de verschillende spreadsheets met elkaar interageren, hoe leren de verschillende computers elkaar kennen)
Definieer nu de nodige interfaces (formele beschrijving van de interactie) en geef een informele bespreking van de mogelijke implementatie.
Geef een schets van implementatie in uw favoriete taal (Java, C, Smalltalk, C++, Python).

Gedistribueerde Transactiemanager met Geneste Transacties

Geneste transacties zijn een uitbreiding op gewone transacties: Bij gebruik van geneste transacties kan men binnen 1 transactie (een parent-transactie) een aantal subtransacties opstarten (en dit recursief, in theorie at infinitum). De subtransacties gedragen zich volledig als normale transacties, die ge-commit en ge-rollbacked kunnen worden. De catch is de volgende: Alhoewel een subtransactie ge-commit kan zijn, kan zijn parent transactie ge-rollbacked worden. Dit houdt dan in dat de (reeds gecommit-te!) subtransactie ook ge-rollbacked wordt.

Bespreek hoe we onze laatste transactiemanager kunnen uitbreiden om geneste transacties te ondersteunen.

Hoe breid je het transactieprotocol uit?
Waar verander je de implementatie en geef en schets van hoe.

Een tweede uitbreiding op transacties zijn gedistribueerde transacties: Er is nu niet 1 transactiemanager, maar 1 master transactiemanager en verscheidene slave transactiemanagers (elke slave met zijn eigen databank). De transactie client spreekt met de master transactiemanager, en die verdeelt dan het werk naar de slaves, naargelang op welke databank gewerkt wordt.

Bespreek hoe we onze laatste transactiemanager kunnen uitbreiden om enerzijds geneste transacties, en anderzijds gedistribueerde transacties, te ondersteunen.

Doe nu de gedistibueerde transacties op basis van deel 1 van deze vraag.
Begin met deze server als slave te beschouwen
Hoe werken de master en de slaves ?
Denk goed na over commits en rollbacks. Bijvoorbeeld: hoe weet de master dat een transactie ge-commit kan worden?

Leg interne werking stubs/skeletons uit (RMI)

Stel dat u de persoon bent die Java RMI libraries moet implementeren. Hoe zou u de stubs en skeletons implementeren ? U kan gebruik maken van TCP/IP. Het uiteindelijke resultaat moet zich exact hetzelfde gedragen als de huidige RMI specs.

Bespreek threading binnen uw stubs en skeletons
Stel een intern protocol samen dat gebruikt kan worden om te communiceren tussen de client en de server.
Bespreek hoe objecten getransfereerd worden. Hoe wordt code getransfereerd ?
Bespreek in details hoe een stub eruit ziet. Hoe wordt een stub geserialiseerd ?
Bespreek in details hoe een skeleton eruit ziet. Hoe wordt een skeleton geserialiseerd ?

Mobile IP: Doorgeven van Channels

IP v4 is het protocol dat gebruikt wordt om internet momenteel draaiende te houden. Om bijvoorbeeld een telnet connectie te leggen naar wendy.vub.ac.be wordt een connectie gelegd naar 134.184.49.3:21. Hierbij is 134.184.49.3 het IP adres en 21 het poortnummer waar de gegeven service (telnet daemon) draait.

IP v4 is een protocol dat uitermate goed werkt zolang we werken met vaste adressen voor vaste machines. Op het ogenblik men services wil kunnen laten migreren van IP adres naar IP adres en hierbij alle openstaande connecties wil meenemen op een locatietransparante manier zit men met een probleem.

IP v6, mobile IP, heeft de IP standaard aangepast om dit mogelijk te maken. Dit wordt gedaan door een IP nummer samen te stellen uit 2 delen. Het eerste deel is het IP nummer van de originele machine (het vaste IP-nummer) en het tweede deel is het IP-nummer van de host waar de service momenteel op draait. Deze eenvoudige naming strategie is eenvoudig te implementeren. Het moeilijkere gedeelte is de migratie van de openstaande connecties.

Bespreek hoe dit in zijn werk gaat:

bespreek hoe het IP protocol aangepast moet worden.
bespreek hoe de IP stack aangepast moet worden.

Sync

In gedistribueerde systemen is het vaak nodig te kunnen synchronizeren tussen verschillende processen. Dit synchronizeren houd in dat processen op elkaar wachten tot ze op een bepaald punt in hun programma gemkomen zijn. Op dit synchronisatiepunt kan men data uitwisselen tussen alle processen. We willen dergelijke sync functie implementeren in Cborg.

De syntax is als volgt:

Sync(<agenttable>, value) -> <resulttable>
Sync retourneerd slechts een value op het ogenblik alle agents een sync bereiken. Als resultaat wordt een tabel weergegeven waar de values instaan die gegeven zijn door elk proces/agent.

Bijvoorbeeld:

Tecra/ses1: Sync([remotedict("tecra/ses2"),remotedict("tecra/ses3")], 10)
Tecra/ses2: Sync([remotedict("tecra/ses1"),remotedict("tecra/ses3")], 34)
Tecra/ses3: Sync([remotedict("tecra/ses1"),remotedict("tecra/ses2")], 67)

Zal op de drie processen eens ze alle drie het sync statement bereikt hebben de volgende values teruggeven:

Tecra/ses1: -> [34,67]
Tecra/ses2: -> [10,67]
Tecra/ses3: -> [10,34]

Implementeer deze sync operatie in Cborg. Bespreek wat je code doet en hoe problemen opgevangen worden.

Concurrentie vs Distributie & Proton

2 korte vragen:

Wat is het verschil tussen concurrente systemen en gedistribueerde systemen ?
Hebt u enig idee waarom proton is ingevoerd (gelieve te letten op de titel van het vak) ?

Collision Detection in Vliegtuigen

Vroeger werden vliegtuigen 100% vanaf de grond gestuurd. Air traffic control noemt dit. Het grote probleem is dat deze centra zwaar overbelast zijn. Waardoor er af en toe een vliegtuig uit het oog verloren wordt en de kans nogal bestaat dat ze tegen elkaar vliegen. Een eerste verbetering aan dit systeem is dat de vliegtuigen nu uitgerust zijn met een collision detection radar. Op het ogenblik een ander vliegtuig te dichtbij komt is er een alarm in het vliegtuig en moet de piloot uitwijken volgens een vast protocol.

Stel dat we dit systeem uitbreiden tot in het extreme waarbij er geen air traffic control meer is vanaf de grond gestuurd. Vliegtuigen kunnen nu onderling communiceren en afspraken maken. Voor een piloot opstijgt vemeld deze waar hij naartoe wilt en het vliegtuig vliegt er naartoe zonder tegen andere vliegtuigen te vliegen. Neem aan dat er vaste snelwegen zijn die vliegtuigen nemen (met andere woorden, u moet zich niets aantrekken van hoe het vliegtuig zijn koers plant).

Vliegtuigen kunnen elkaar ontwijken door links, rechts, hoger of lager te gaan vliegen. Neem aan dat u voorzien bent van een collision detection radar die een event stuurt (met onmiddelijk een communication channel naar dat vliegtuig) op het ogenblik een ander vliegtuig te dichtbij is. Een tweede event wordt gestuurd op het ogenblik dat dat vliegtuig ver genoeg is.

Bespreek het systeem:

Bespreek de algemene layout van het systeem.
Ontwerp een protocol waarlangs ze met elkaar spreken.
Hoe rekening met errors en uitzonderingen. (U moet niet denken aan opstijgen en landen)
Schets van de implementatie in uw favoriete taal. (Geen Fortran, Cobrol of Pascal aub)

CORBA

Geef schets verloop call corba + leg de interne werking van de ORB uit. (zonder stubs en skeletons) [40' /7p]

Schets het verloop van een call van client naar server in CORBA. Neem aan dat er reeds een referentie bestaat naar het serverobject.
Gebruik makende van dit verloop: leg op socketniveau uit hoe de ORB deze calls afhandelt. (u moet enkel de ORB uitleggen, dus geen stubs en skeletons of zo)

TupleSpaces

Schets de werking van een tuple space, niet gecentraliseerd.

Get wait till tuple available

Put puts tuple in space

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