ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



Эͬ༭άԸĵע
κȪԴޡ
ժҪʵʱЭͬ༭ϵͳ,Ըһάǹ¸,ЭͬϵͳһάҪ.ĵעķͨԹĵǡע,βԹĵɵӰ,ʹòЭִʱĻĻһ,ӶЧάԸһ.ʵӦеľ,صĵעԼӦĿ㷨.
ؼʡCSCW,ʵʱЭͬ༭,Ըά,ĵע.
ͼšTP311
Document Marking Scheme for Preserving Intention of Operationin Cooperative Editing System
HE Hong-junWU Quan-yuanLUO Li
AbstractIntention preservation of operation is a new proposed concept in the field of CSCW (computer-supported cooperative work), and the key feature of consistency control. A new called document marking scheme for intention preservation is proposed in this paper. By properly marking the sharing document, the document marking scheme can hide the effect of all concurrent operations of one operation. Therefore, operation can be performed at any cooperative side under the document environment just like it produced. Associating operations in a real-time cooperative editing system, the idea and the high-level control algorithm of the new method are presented in detail.
Key wordsCSCW(computer-supported cooperative work), real-time cooperative editing, intention preservation of operation, document marking scheme.
ʵʱЭͬ༭ϵͳ֧ϷֲĶЭͬʱ༭ͬһĵ,һҪCSCWcomputer-supported cooperative workӦϵͳ.ʵʱЭͬ༭ϵͳǵ͵ķֲʽӦϵͳ,ҪûкܿӦٶ,ͨص㣺ͬһʱ̽вЭûĿû,ЭûԱ༭ĵҲԼ,ûʱ̱༭ĵⲿ,ͬGROVE,REDUCEϵͳ13ݣн㶼ڱش洢йĵ,֮䴫͵ϢҪǲϢͲԼҪĿϢ,ϵṹڱִ,ڱصӦʱܶ.
άԸ(Intention Preservation of Operation)ǹ¸,ּʹûòʱϣﵽЧòʵִкЧһ,ڲһά.ֲʽϵͳݿϵͳ,Բһά˹㷺о,дʹõĳɹ.,Эͬоķչ,һάĲ紫ӳٵĲȷԶӻ.Ըάֱ.Ŀǰ,άԸѳΪЭͬ,رʵʱЭͬ༭ϵͳоսо15.ĵע,ʵֲԸάЧ;.
۲ԸҪ,򵥽ĿǰϽԸάҪɹ,任Ļ˼.Ȼ,ĵע,Ͼʵ˵,ϸ÷ʵʱЭͬ༭ϵͳάԸĿ㷨.,ܽĵעص,һоƻ.
1Ը
 ,ķչʱ仹,Ըάⳤûеõ㹻,ıʺ͸ȱ˽.C.Sunʿڽȷ˲ԸIntention of Operationĸ,任ӦʵʱЭͬı༭ϵͳвԸά4,5.
1. Ը.
OĲԸָOʱĻ,OҪɵĶ.ڲOʱĵ״̬,ִOõĽȻԸ.
ʵʱЭͬ༭ϵͳ,һԶִ̽вЧ,ԵͿ,ڱִʱЧһ,ûϣﵽЧһ.ٶO1O2ֱڽA,BͬʱĲ,A,Bĵ״̬O1O2ǰͬ.ô,ʵʱЭͬ༭ϵͳص,O1O2ڱؽִ,Ȼ㲥Э㲢ִ.O1Bʱ,ĵ״ִ̬O2˱仯,O1ʱĵ״̬һ,ִO1,ܿܲĽ.ͬ,O2Aʱ,ҲƵ.
ֿһв롢ɾʵʱЭͬı༭ϵͳ.ͼ1ʾ,O1,O2ڽN0N1ϵִ.蹲ĵĳʼ״̬ΪABCDEF,O1=O2=remove1,3,ʾɾλ3ǵ1ַλΪ0ʼ1ַ,ɾַD.Ȼ,нӦõõȷǡABCEF.Ȼ,õĽܿǡABCF.ʵ,Ӹʰ.ͼ1Ϊ,ҹĵĳʼ״̬ΪABCEF,O1insertۡ11,1,O2insert
ۡ22,3,O3remove3,0,Ϊ3ͬͬʱĲ,ֱʾλ13֮ǰַ1122ԼɾABC.ȷĽǡ1122DEF,O1,O2,O36еκһ˳ִ,ܵõȷ.ԸΥ,ִ˳޹,ڲĲ,ֲʹøӸ.Կ,ʵʱЭͬ༭ϵͳһά,൱ս,зֲʽĿ㷨ֱ68.

ͼ1ʵʱЭͬ༭ϵͳĲϵʾ
2άԸз
 任ĿǰоԸάһЧ.任˼ʵʱЭͬ༭ϵͳ,C.A.EllisԵĹ1,2.,C.Sunʿϼо,ԭڵ,״ȷάԸĸ,任õ˽һķչƣ35.
任Ļ˼ǣִǰԲĸʽе,Բִĵ仯.ҪĲ任,ֱΪ任Inclusion Transformation޳任Exclusion Transformation1,35.任ǰһĵɵӰЧذһ,任ĲѾһĵɵӰ.޳任һһӰ.任ʵӦ,ʵʵĲӦ㷨.ͬӦ,һ,εõȷ任ʽ,ǶԱ任еȵĹ,㷨ͨõģ1,4,5.
ٸ,ͼ1ʾ.蹲ĵĳʼ״̬ΪABCDEF,O1insertۡ11,1,ڡA롰BCDEF֮롰11,O2remove3,2,ɾCDE.O1ڽN0ִк,ĵΪA11BCDEF,O2N0ʱ,ͨ任ΪO2remove3,4,ִеõĵA11BF.
Ӧָ,ӵĲϵʹʵʩ任.,еO1Ϊinsertۡ11,3,O2任Ӧõremove1,2ݺremove2,5.
3ĵע
 Կ,任ڲ,ͼͨ任ĲʽʵֲԸά.ڲ任㷨,ر,紫ӳٵĲȷ,ģԴʱ,֮Ŀܹϵ÷ǳ,ȫܲ,ʵʩ任ʱҪر.5,任㷨ƵѶȺͼҪ󶼺ܸ.
ĵעڹĵ.ĳһִǰ˶ٲ,ͨԹĵӱעֶ,Ѳִĵ仯,ʹòִʱĵ״̬Ȼòǰ˲ĵ״̬һ,ӶʵֲԸά.巽£Oǰ˲ĵ״̬ΪDOC,O͵Զִ̽ʱ,OĲڸԶ̽Ѿִ,ͨĵӱעֶ,ִеĲĵı仯,ʹøԶ̽ĵ״̬ȻDOC,ȻִO,,ȥӵıע,Իָصĵ.
Ŀǰо,ĵעֵ֣(1) ɼ.ʾӲĽǶȿ,ⲿĵǲڵ,ʵⲿĵǴڵ,ڲǲɼ.(2) ɼʵʲ.ʾӲĽǶȿ,ⲿĵǿɼ,ʵѾǰִеĳɾ.
ɾҪصע.ִɾʱ,ĵӦɾ,ô󽫸ɾָֻǺܲ.ԭڣִн͵ʱϵͳ״̬ص,ִв,ϵͳ״̬˸ı䣻Ҫȷִ,ҪõЩϵͳ״̬.һֿеǣִɾʱ,ĵĶӦɾ,Ӧ.ļϵͳݿϵͳΪṩɾļݼ¼ĻָܶƼ.
ͨϽе˵ĵע.ͼ1ʾ,蹲ĵĳʼ״̬ΪABCDEF,O1insertۡ11, 3,O2remove3, 2,O1 O2ڽN0N1ϵִ.ٶ»ߴɼע,ɾߴɼʵʲڡע.
N0 (1) O1ִк,ĵ״̬ΪABC11DEF(2)O2ﱾ,O1O2Ĳ,,ҪO1ĵ仯,11.ԡ11»߱ע,ĵ״̬ΪABC11DEF.ִO2,ɾλ2ʼ3ַ,ڡ11»߱ע,ɾ֮,,ɾַǡCDE,ӶõAB11F.Ȼ,ȥ11ϵıע.
һᵽ,ò仯,O2任Ӧõ.ĵע,O2κα仯,ִʱֻס»߱עַɾ֮.
N1 1) O2ִк,ûĵΪABF.O2ɾ,,ǰ,ʵʰѡCDEĵгȥ,ĵ״̬ΪABCDEF,ҪڡCDEĸַϱO2,ʾO2ɾ,Ҳʾ2) O1ﱾ,O2O1Ĳ,,ҪO2ĵ仯.ԡCDEɾ߱ע,ĵ״̬ΪABCDEF.ִO1,11λ3D֮ǰ,õABC11DEF.,ȥCDEϵɾ߱ע,ûĵΪAB11F.
4㷨
 ĵעʵֿɷΪ.һζĵбע,㷨Ӧ.һǸ߲㷨,Ӧ޹,ݵǰĲѾִ˵ĲĹϵ,ĵע㷨,ʹĵ״̬òʱؽĵ״̬ͬ,Ȼִв,ԸҪ.
2. ״̬NS.
״̬ڸýѾִ˵Ĳбʾ.,iѾ˳ִ˲O1,O2O3,ô,i״̬NSiԱʾΪһO1 ,O2 ,O3.βԪִеĲ.
3. CT.
ĶΪʱؽѾִ˵Ĳ.,Oڽiϲ˲,iѾ˳ִ˲O1,O2O3,ô,OCTOԱʾΪһO1,O2,O3.
ڿ㷨ҪõϢ,,Ϣͬһ,Ȼ͵Э.
ͬӦúͲ,ĵӱע㷨ľʵֲͬ,˼һµ.Ϊ۷,.
(1) DocumentmarkDoc(Documentdoc,Operationop);
ǰĵ״̬Ϊdoc,ִ˵ĲΪop.
opĵɵӰбע,opִкĵı仯.
ĵ仯һµ״̬doc.opִǰĵ״̬Ϊdoc,markDoc()ִк,ӲĽǶȿ,ĵ״̬Ȼdoc,docdoc.
(2) DocumentdemarkDoc(Documentdoc,Operationop);
ǰĵ״̬Ϊdoc,ִ˵ĲΪop,ҲopĵdocɵӰѾͨmarkDoc().
ĵopӵıעȥ.
ĵ仯һµĵ״̬doc,docвopĵɵӰ챻ʾ.
¹ϵ
demarkDoc(markDoc(DOC,op),op)=DOC.
һ,ڱؽ,ִУԶ̽,ִ㷨.
㷨 OԶ̽,赱ǰ״̬ΪNS,ĵ״̬ΪDOC,OΪCTO,²ִУ
(1) NSCTO,ִO.㷨
(2) opCTOԪ,ҲNSԪأ,ӳִO.㷨
(3) (a) ListTmpΪձ.
(b) ɨNS,opNSԪ, ҲCTOԪأ,
{DOCmarkDoc(DOC,op);
 opListTmpıβ
}
(4) ִO;
(5) ɨListTmp,ListTmpԪop,ִ
DOCdemarkDoc(DOC,op);
(6) 㷨.
һʱ,Ҫĵע,˲Ϣ,Ӧ֪״̬Ϣ,ʹעȷʵʩ.ڽϱвϢ,Ϣ,ĹڴԴ,ЧʽԽԽ.ô,ȷ豣ĲϢأĶ.
1. 輯SĲЭ϶ִ,Բٱ漯SĲϢ.
,Թ첻ͬʽ㷨,ʵֲϢı.
Ͻеһ˵.ȷO1O2Ѿнϱִ,ô,ݶ1,ڽN1N2,CDEʽĵгȥ.
5
 άԸһӵġľսԵĿ,ϵоҲո,ĿǰȡõĳɹֻɹһС.ĵעάԸһ·,⡢ͨõص,㷨ҲȽֱ,.ڽо,ǽһչĵע,ǰӦõֲʽ.
лC.Sunʿڻѧݶܴ,رǶԱĵд˺ܶ౦ľ.,ʿй.ڴ,Ǳʾǳֿл.
оõ863߿ƼĿ.
߽ܣκ,1968,ʿ,ʦ,ҪоΪֲ㼼,ý弼.
ȪԴ,1942,,ʿʦ,ҪоΪרϵͳ,ֲ㼼.
,Ů,1971,ʿ,ʦ,ҪоΪ˹,ֲ㼼.
ͨѶϵˣκ,ɳ 410073,ɳѧԺϵ601
ߵλκȪԴޡ򡡳ɳѧԺϵɳ410073
ο
1Ellis C A, Gibbs S J. Concurrency control in groupware systems. In: Baltimore ed. Proceedings of ACM SIGMOD Conference on Management of Data. New York: ACM Press, 1989. 399407
2Ellis C A, Gibbs S J, Rein G L. Groupware: some issues and experiences. Communications of ACM, 1991,34(1):3958
3Sun C et al. REDUCE: a prototypical cooperative editing system. In: Smith M J et al eds. Proceedings of the 7th International Conference on Human-Computer Interaction. San Fransisco: Elsevier Press, August, 1997. 8992
4Ressel M, Nitsche-Ruhland D, Gunzenbauser R. An integrating transformation-oriented approach to concurrency control and undo in group editors. In: Turner J ed. Proceedings of ACM Conference on Computer Supported Cooperative Work. 1996. 288297
5Sun C et al. A generic operation transformation scheme for consistency maintenance in real-time cooperative editing system. In: Payne S C, Prinz W eds. Proceedings of the International Conference on Supporting Group Work (GROUP'97). Phoenix, Arizona USA, Nov. 1997. 425434
6Tanenbaum A S. Distributed Operating System. Beijing: Tsinghua University Press, 1996. 119158
7Gerard Tel. Introduction to Distributed Algorithms. London: Cambridge University Press, 1994
8Stefano Ceri et al. Distributed Databases: Principles and Systems. New York: McGraw-Hill Book Company, 1984. 209244
1997-10-22յԭ,1998-02-17յ޸ĸ
