Hi, everyone. I am a Ph. D. student in computer science department at KAIST, Korea. I am researching the real-time collaboration and have a solution that can be used as building blocks of collaborative applications. As a novel kind of distributed abstract data type (ADT), “Replicated abstract data types (RADTs)” are those solutions that make replicated ADTs maintain consistency. I presented RADT versions for three representative ADTs; array (RFA), hash table (RHTs), and linked list or vector (RGAs). Especially, RGAs, the RADT version of linked list or vector data type, ensure consistency for INSERT and DELETE operations as operational transformation (OT) algorithms.
When I first saw the Google Wave from the Youtube videos, I thought it is the very best application to apply RADTs to. RADTs are introduced in the paper<http://cs.kaist.ac.kr/common/download.cs?tbl=report_tbl&clm=rpt_upload,rpt_filename,rpt_dir&wclm=rpt_sno&uclm=rpt_download&sno=246>, which was submitted to a prominent journal and is currently under the review. The paper linked above is the technical report with the permission of the journal. Anyway, an important point is that RADTs can boost the real-time collaboration of Google wave. In the paper, I compared RGAs with various operational transformation (OT) methods. RADTs are superior to OT in the following aspects: 1) They provide the familiar operation contexts of representative ADTs for application developers. 2) RGAs support not only INSERT and DELETE operations but also UPDATE (REPLACE) operations. 3) Complexity: the complexity of remote operations (in terms of the Google wave, server operations) is O(1). 4) Scalability: due to the performance of remote operations, RADTs are scalable. 5) Reliability: RADTs can cope with the loss of operations flexibly. Though, for academics’ sake, the paper discussed RADTs in the peer-to-peer communication protocol, RADTs can be employed easily in the client/server protocol. If RADTs are deployed with the client/server protocol, they may need no vector clocks, which deteriorate scalability, as the Jupiter OT algorithm. Above all, RADTs require less computational power than any other OT algorithms. According to the Google wave team, the complexity of Jupiter OT algorithm is O(NM) where N is # of client operations and M is # of sever operations. The complexity of RGA operations is O(1) or O(n), where n is # of objects. Especially, the optimal complexity of remote operations would ultimately enhance the scalability of the wave server and the responsiveness of wave clients. In addition, RGAs have been designed with considering the concept of the intention preservation which was not considered when Jupiter system was introduced. Though undo operations haven’t been discussed in the paper, it seem easy to find inverse operations in RADTs. I hope Google Wave team adopt RADTs as a part of protocol. I think RADTs will not threaten the position of OT in the wave. Instead, by providing RADT APIs, Google Wave could support the developments of the wave extension or robot applications. In addition, if there is a plan to support more various objects, such as graphical objects, in the wave document, RADTs can maintain consistency of them. I am eager to contribute my research work to Google Wave. Please read the paper, and don’t hesitate in asking me. Sincerely, Hyun-Gul Roh [email protected] --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Wave Protocol" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en -~----------~----~----~----~------~----~------~--~---
