GESTIONE DELLE RICHIESTE USCENTI IN IRL 83

passo `e stato fatto con l’ipotesi di client sincroni: in questo modo si ha un ack implicito sulla consegna del risultato al client: nel log sra`a presente una entry per ogni client del servizio. Questo implica che la memoria necessaria per il log-ging `e O(n), dove n `e il numero di client che accedono al servizio; questo non d

ovviamente un upper bound assoluto, ma `e anche vero che si presuppone di avere un numero di client molto inferiore al numero di richieste dirette ad un server replicato.

Un altra ipotesi che dal punto di vista pratico non `e accettabile `e l’ipotesi HP2 fatta nella sezione 7.1: in generale si pu`o pensare che un client smetta di reinvo-care un metodo a causa di un evento non deterministico; questo evento pu`o essere lo scadere di un timeout di valida della richiesta o il fatto che l’oggetto su cui il client ha invocato l’operazione non sia pi`u raggiungibile; con la replicazione, il secondo caso pu`o essere reso meno probabile, ma sempre possibile.

stato iniziale di C Result Inv NoRes l'invocazione è stata interrotta

Figura 7.12: Semantica di invocazione estesa.

Dal punto di vista della semantica di invocazione ci`o comporta l’aggiunta di un nuovo stato finale denominato NoRes, nel quale il client si trova quando smette di reinvocare (Figura 7.12).

Quando il client va nello stato NoRes non `e possibile sapere quale sia stata l’evoluzione degli oggetti coinvolti nel processamento di una richiesta. Si consid-eri a tal proposito la Figura 7.13

C O₁ O₂ req₁ req2 result₁ resul^t2 O₃ 1 2 req₃ result₃ 3 C va nello stato NoRes quando cerca di invocare req1 O1si guasta prima di poter portare a termine la computazione

della richiesta req3

Figura 7.13: Richieste uscenti con crash di un oggetto.

richieste uscenti sugli oggetti O₂ e O₃; per qualche motivo (ad esempio il crash dell’oggetto O₁) il client non ha pi`u la possibilit`a di reinvocare la richiesta; in questa situazione il client non potr`a sapere cosa `e realmente successo:

• prima di tutto, perch`e non `e detto che sappia che l’invocazione di req1

convolge anche altri oggetti oltre O₁;

• se anche riuscisse a sapere quali sono tutti gli oggetti coinvolti

nell’invo-cazione, non sarebbe comunque possibile comunicare al client quali ogget-ti hanno fatto evolvere il proprio stato e quali no; pi`u in particolare il client non pu`o comunque intraprendere nessuna operazione di “recovery” che permetta di ristabilire uno stato consistente degli oggetti coinvolti.

Conclusioni

Le repliche server di un servizio stateless possono essere collocate in un sistema distribuito asincrono. Questo non `e vero quando si implementano server state-ful seguendo le classiche tecniche di replicazione a due livelli: c’`e la necessit`a di avere alcune assunzioni temporali sul sistema distribuito che permette quindi di usare le primitive di comunicazione di gruppo. Questo `e il vero limite pratico che impedisce di collocare server stateful replicati su un sistema distribuito.

Sono state definite due propriet`a, Client/Server-Asynchrony e Client-Autonomy, che caratterizzano i client e i server replicati in un sistema asincrono. `E sta-to poi introdotsta-to l’approccio a tre livelli, che soddisfa le due propriet`a definite inglobando la logica di replicazione in in un livello software intermedio. Come conseguenza (i) i client non interagisco direttamente con il servizio replicato, e

(ii) solo le entit`a del mid-tier necessitano di assunzioni temporali aggiuntive. `

E stata presentata poi un’infrastruttura tollerante ai guasti, compliant con la specifica FT-CORBA, sviluppata con l’approccio a tre livelli, e che mette a dis-posizione delle tecniche per la gestione della consistenza gestita dall’infrastrut-tura stessa. Questa architetdall’infrastrut-tura, denominata IRL, `e portabile e interoperabile, caratteristiche queste derivanti dall’approccio sopra l’ORB usato nell’architet-tura. Infine sono state effettuate delle misure di performance basate su un pro-totipo dell’infrastruttura, implementando un semplice protocollo di replicazione basato su forti assunzioni sul sistema in cui vive il mid-tier: i risultati ottenuti mostrano che l’approccio a tre livelli `e realizzabile.

Attualmente si sta lavorando per rilassare le forti assunzioni fatte per realiz-zare il mid-tier: in particolare si sta implementando un protocollo di replicazione a tre livelli basato su un sequencer ([4]), che non necessita di una rilevazione dei guasti sul mid-tier e sui membri degli object group.

Infine, `e stato affrontato il problema delle richieste uscenti duplicate, definendo il problema e dando una possibile soluzione.

Bibliografia

[1] R. Baldoni and C. Marchetti. Software replication in three-tiers architectures: is it a real challenge? In Proceedings of the 8th IEEE Workshop on Future Trends

of Distributed Computing Systems (FTDCS’2001), pages 133–139, Bologna, Italy,

November 2001.

[2] R. Baldoni, C. Marchetti, R. Panella, and L. Verde. Handling FT-CORBA Compliant Interoperable Object Group Reference. In in Prooceedings of the 6th

IEEE International Workshop on Object Oriented Real-time Dependable Systems (WORDS’02), page to appear, Santa Barbara (CA), USA, January 2002.

[3] R. Baldoni, C. Marchetti, and A. Termini. IRL a Three-tier Approach for FT-CORBA Infrastructures. Technical Report 01-02, Dipartimento di Informatica e Sistemistica, Universit`a di Roma “ La Sapienza”, january 2002.

[4] R. Baldoni, C. Marchetti, and S. Tucci-Piergiovanni. Asynchronous Active Repli-cation in Three-Tier Distributed Systems. Technical Report 05-02, Dipartimento di Informatica e Sistemistica, Universit`a di Roma “ La Sapienza”, february 2002.

[5] R. Baldoni, C. Marchetti, and S. Tucci-Piergiovanni. Fault Tolerant Sequencer: Specification and an Implementation. In Paul Ezhilchevaln and Alexander Ro-manovsky, editors, Concurrency in Dependable Computing, chapter 8, pages 149–168. Kluwer Academic Publishers, 2002.

[6] K. Birman. The Process Group Approach to Reliable Distributed Computing.

Communications of the ACM, 36(12):37–53, December 1993.

[7] K. Birman and T. Joseph. Exploiting Virtual Synchrony in Distributed Systems. In Proc. of the 11th ACM Symp. on Operating Systems Principles, pages 123–138, December 1987.

[8] K. Birman, A. Schiper, and P. Stephenson. Lightweight Causal and Atomic Group Multicast. ACM Transactions on Computer Systems, 9(3):272–314, August 1991.

[9] K. Birman and R. van Renesse. Reliable Distributed Computing With The ISIS

Toolkit. IEEE Computer Society Press, Los Alamitos, 1993.

[10] N. Budhiraja, F.B. Schneider, S. Toueg, and K. Marzullo. The Primary-Backup Approach. In S. Mullender, editor, Distributed Systems, pages 199–216. ACM Press - Addison Wesley, 1993.

[11] T. Chandra and S. Toueg. Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM, pages 225–267, Mar. 1996.

[12] P. Chung, Y. Huang, S. Yajnik, D. Liang, and J. Shih. DOORS - Provid-ing fault tolerance to CORBA objects. In poster session at IFIP International

Conference on Distributed Systems Platforms and Open Distributed Processing (Middleware’98), The Lake District, England, 1998.

[13] F. Cristian and C. Fetzer. The Timed Asynchronous Distributed System. In Proc.

of the 28nd Annual International Symposium on Fault-Tolerant Computing, pages

140–149, 1998.

[14] M. Cukier, J. Ren, C. Sabnis, D. Henke, J. Pistole, W. H. Sanders, D. E. Bakken, M. E. Berman, D. A. Karr, and R. E. Schantz. AQuA: An Adaptive Architecture that Provides Dependable Distributed Objects. In Proceedings of the 17th IEEE

Symposium on Reliable Distributed Systems, pages 245–253, West Lafayette, IN,

USA, October 1998.

[15] X. D´efago, A. Schiper, and N. Sergent. Semi-passive replication. In Proceedings of

the 17th IEEE Symposium on Reliable Distributed Systems (SRDS), pages 43–50,

West Lafayette, IN, USA, October 1998.

[16] D. Dolev, C. Dwork, and L. Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77–97, January 1987.

[17] C. Dwork and N.A. Lynch L. Stockmeyer. Consensus in the Presence of Partial Synchrony. Journal of the ACM, 35(2):288–323, April 1988.

[18] D. Powell (ed.). Special Section on Group Communication. Communications of

BIBLIOGRAFIA 89

[19] P. Ezhilchelvan, R. Macedo, and S. Shrivastava. Newtop: A Fault-Tolerant Group Communication Protocol. Technical report, Computer Science Depart-ment, University of Newcastle, Newcastle upon Tyne, United Kingdom, August 1994.

[20] P. Felber. The CORBA Object Group Service: A Service Approach to Object

Groups in CORBA. PhD thesis, ´Ecole Polytechnique F´ed´erale de Lausanne, Switzerland, 1998. PhD thesis no. 1867.

[21] P. A. Felber and R. Guerraoui. The Implementation of a CORBA Group Communication Service. Theory and Practice of Object Systems, 4(2):93–105,

1998.

[22] Pascal Felber and Andr´e Schiper. Optimistic active replication. In Proceedings of

21st International Conference on Distributed Computing Systems (ICDCS’2001),

Phoenix, Arizona, USA, April 2001. IEEE Computer Society.

[23] C. Fetzer and F. Cristian. The Timed Asynchronous Distributed System Model.

IEEE Transactions on Parallel and Distributed Systems, 10(6):642–657, 1999.

[24] Christof Fetzer. Enforcing perfect failure detection. In Proceedings of the 21st

International Conference on Distributed Systems, Phoenix, AZ, April 2001.

[25] M. Fischer, N. Lynch, and M. Patterson. Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, 32(2):374–382, April 1985.

[26] M.J. Fisher and L. Lamport. Byzantine Generals and Transaction Commit Protocols. Technical report, 1982.

[27] D. Gifford. Weighted voting for replicated data. In Proceedings of 7th ACM

Symposium on Operating System Principles, pages 150–162, 1979.

[28] R. Guerraoui, B. Garbinato, and K. Mazouni. Lessons from designing and imple-menting GARF. In Object-Oriented Parallel and Distributed Computing, LNCS. Springer-Verlag, 1996.

[29] R. Guerraoui and A. Schiper. Software-Based Replication for Fault Tolerance.

[30] V. Hadzilacos. Issues of Fault Tolerance in Concurrent Computations. PhD thesis, Harvard University, 1984.

[31] M. Henning and S. Vinoski. Advanced CORBA Programming with C++. Addison Wesley Longman, 1999.

[32] M. Herlihy and J. Wing. Linearizability: a Correcteness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems, 12(3):463– 492, 1990.

[33] IONA Web Site. http://www.iona.com.

[34] IRL Project Web Site. http://www.dis.uniroma1.it/∼irl.

[35] JacORB Web Site. http://www.jacorb.org.

[36] S. Landis and S. Maffeis. Building Reliable Distributed Systems with CORBA.

Theory and Practice of Object Systems, 3(1), 1997.

[37] L. Lamport M. Pease and R. Shostak. The byzantine generals problem. ACM

Transaction of Programming Languages and Systems, 1982.

[38] Dahlia Malkhi. Quorum Systems. In Joseph Urban and Partha Dasgupta, editors,

The Encyclopedia of Distributed Computing. Kluwer Academic Publishers, 2000.

[39] C. Marchetti, L. Verde, and R. Baldoni. CORBA Request Portable Interceptors: a Performance Analysis. In Proceedings of the 3rd Intenational Symposium on

Distributed Objects and Applications, pages 208–217, Rome, Italy, September 2001.

[40] L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal, R. K. Budhia, C. A. Lingley-Papadopoulos, and T. P. Archambault. The Totem System. In Proc. of the

25th Annual International Symposium on Fault-Tolerant Computing, pages 61–66,

Pasadena, CA, June 1995.

[41] L.E. Moser, P.M. Melliar-Smith, P. Narasimhan, L.A. Tewksbury, and V. Kaloger-aki. The Eternal System: an Architecture for Enterprise Applications. In

Proceed-ings of the 3rd International Enterprise Distributed Object Computing Conference (EDOC’99), pages 214–222, Mannheim, Germany, July 1999.

[42] Priya Narasimhan. Transparent Fault Tolerance for CORBA. PhD thesis, University of California, Santa Barbara, USA, 1999.

BIBLIOGRAFIA 91

[43] Object Management Group (OMG), Framingham, MA, USA. Fault Tolerant

COR-BA Specification, V1.0, OMG Document ptc/2000-12-06 edition, April 2000. OMG

Final Adopted Specification.

[44] Object Management Group (OMG), Framingham, MA, USA. The Common Object

Request Broker Architecture and Specifications. Revision 2.4.2, OMG Document

formal edition, February 2001. OMG Final Adopted Specification.

[45] OMG Web Site. http://www.omg.org.

[46] Graham D. Parrington, Santosh K. Shrivastava, Stuart M. Wheater, and Mark C. Little. The design and implementation of arjuna. Computing Systems, 8(2):255– 308, 1995.

[47] K.J. Perry and S. Toueg. Distributed Agreement In The Presence Of Processor And Communication Faults. IEEE Transaction of Software Engineering, 1986.

[48] F.B. Schneider. Bizantine Generals In Action: Implementing Fail-Stop Processors.

ACM Transaction on Computer Systems, 2(2):pp. 145–154, 1984.

[49] Fred B. Schneider. Replication Management Using the State Machine Approach. In S. Mullender, editor, Distributed Systems. ACM Press - Addison Wesley, 1993.

[50] A. V. and K. P. Birman. The Maestro Approach to Building Reliable Interoperable Distributed Applications with Multiple Execution Styles. Theory and Practice of