commit 5bb507a02e8f230c8cc432f1d6830014b060169a Author: Ivan Gankevich <igankevich@ya.ru> Date: Sun, 7 Aug 2016 16:08:50 +0300 Initial Diffstat:
| figures/buffer.eps | | | 577 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| figures/discovery.eps | | | 579 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| figures/trans.eps | | | 430 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| llncs.cls | | | 1208 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| main.tex | | | 67 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| references.bib | | | 95 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| sec-1.tex | | | 57 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| sec-2.tex | | | 103 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
8 files changed, 3116 insertions(+), 0 deletions(-)
diff --git a/figures/buffer.eps b/figures/buffer.eps @@ -0,0 +1,577 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Creator: cairo 1.13.1 (http://cairographics.org) +%%CreationDate: Mon Mar 23 00:40:41 2015 +%%Pages: 1 +%%DocumentData: Clean7Bit +%%LanguageLevel: 2 +%%BoundingBox: 3 2 313 194 +%%EndComments +%%BeginProlog +save +50 dict begin +/q { gsave } bind def +/Q { grestore } bind def +/cm { 6 array astore concat } bind def +/w { setlinewidth } bind def +/J { setlinecap } bind def +/j { setlinejoin } bind def +/M { setmiterlimit } bind def +/d { setdash } bind def +/m { moveto } bind def +/l { lineto } bind def +/c { curveto } bind def +/h { closepath } bind def +/re { exch dup neg 3 1 roll 5 3 roll moveto 0 rlineto + 0 exch rlineto 0 rlineto closepath } bind def +/S { stroke } bind def +/f { fill } bind def +/f* { eofill } bind def +/n { newpath } bind def +/W { clip } bind def +/W* { eoclip } bind def +/BT { } bind def +/ET { } bind def +/pdfmark where { pop globaldict /?pdfmark /exec load put } + { globaldict begin /?pdfmark /pop load def /pdfmark + /cleartomark load def end } ifelse +/BDC { mark 3 1 roll /BDC pdfmark } bind def +/EMC { mark /EMC pdfmark } bind def +/cairo_store_point { /cairo_point_y exch def /cairo_point_x exch def } def +/Tj { show currentpoint cairo_store_point } bind def +/TJ { + { + dup + type /stringtype eq + { show } { -0.001 mul 0 cairo_font_matrix dtransform rmoveto } ifelse + } forall + currentpoint cairo_store_point +} bind def +/cairo_selectfont { cairo_font_matrix aload pop pop pop 0 0 6 array astore + cairo_font exch selectfont cairo_point_x cairo_point_y moveto } bind def +/Tf { pop /cairo_font exch def /cairo_font_matrix where + { pop cairo_selectfont } if } bind def +/Td { matrix translate cairo_font_matrix matrix concatmatrix dup + /cairo_font_matrix exch def dup 4 get exch 5 get cairo_store_point + /cairo_font where { pop cairo_selectfont } if } bind def +/Tm { 2 copy 8 2 roll 6 array astore /cairo_font_matrix exch def + cairo_store_point /cairo_font where { pop cairo_selectfont } if } bind def +/g { setgray } bind def +/rg { setrgbcolor } bind def +/d1 { setcachedevice } bind def +%%EndProlog +11 dict begin +/FontType 42 def +/FontName /DejaVuSerif def +/PaintType 0 def +/FontMatrix [ 1 0 0 1 0 0 ] def +/FontBBox [ 0 0 0 0 ] def +/Encoding 256 array def +0 1 255 { Encoding exch /.notdef put } for +Encoding 32 /space put +Encoding 46 /period put +Encoding 48 /zero put +Encoding 49 /one put +Encoding 50 /two put +Encoding 51 /three put +Encoding 52 /four put +Encoding 53 /five put +Encoding 54 /six put +Encoding 55 /seven put +Encoding 56 /eight put +Encoding 68 /D put +Encoding 78 /N put +Encoding 91 /bracketleft put +Encoding 93 /bracketright put +Encoding 97 /a put +Encoding 98 /b put +Encoding 99 /c put +Encoding 101 /e put +Encoding 102 /f put +Encoding 105 /i put +Encoding 106 /j put +Encoding 108 /l put +Encoding 109 /m put +Encoding 110 /n put +Encoding 111 /o put +Encoding 114 /r put +Encoding 115 /s put +Encoding 116 /t put +Encoding 117 /u put +Encoding 121 /y put +/CharStrings 32 dict dup begin +/.notdef 0 def +/zero 1 def +/one 2 def +/two 3 def +/three 4 def +/four 5 def +/five 6 def +/six 7 def +/seven 8 def +/eight 9 def +/N 10 def +/o 11 def +/period 12 def +/space 13 def +/f 14 def +/b 15 def +/j 16 def +/e 17 def +/c 18 def +/t 19 def +/s 20 def +/i 21 def +/n 22 def +/u 23 def +/r 24 def +/D 25 def +/l 26 def +/a 27 def +/y 28 def +/bracketleft 29 def +/m 30 def +/bracketright 31 def +end readonly def +/sfnts [ +<000100000009008000030010637674208f33abf40000170c000001946670676de780f1c40000 +18a00000008b676c79668af85a360000009c00001670686561640747fea80000192c00000036 +686865610eb7088d0000196400000024686d74788f650c3700001988000000806c6f63610001 +659400001a08000000846d617870047e053300001a8c0000002070726570757906f600001aac +0000055e00020066fe96046605a400030007001a400c04c70006c70108055d0204002fc4d4ec +310010d4ecd4ec301311211125211121660400fc73031bfce5fe96070ef8f272062900020087 +ffe3048f05f0000b00170023401300650c066512690c60180306151409060f0b1810f4ecf4ec +310010e4f4ec10ee30253212111002232202111012172200111000333200111000028b999898 +9999989899f3feef0111f3f40110fef0460150015301540150feb0feacfeadfeb0630198016e +016f0198fe68fe91fe92fe680000000100fa000003f405f0000a0078401c0464050605036406 +054d03060401050669080173000907110400020b10d4c4c4fcc431002fec32f4c41139113930 +4b53580704ed071004ed5922014bb00a5458bd000b00400001000b000bffc038113738594009 +200020012f092f0a045d014bb00b5458bd000bffc00001000b000b0040381137385921352111 +0535253311211501230104fed3016c8a01046a04dac383ecfa7a6a0000000001008b0000044e +05f0001c004d40210c14000f0d007402641a6505690d7711140d0c17000a011706080e0a1001 +120b1d10f4c4d4ecd4ec10ee1139393931002feef6eefeee10c411393930400b460a460b460c +4614461505015d0123113e01333204151401060701213533112135013e013534262322060106 +706bd968e9010efece180cfe87026f75fc3d01c596809d8a8f9c0471010a393ce2c2dbfecf17 +0cfe87b8fea46d01c496fb8a97aa8e000001009cffe3047f05f0002a004d402b091d651f1374 +126517651f0f29740065266503690f602b201e091d23290a002306061a060c140a0012022b10 +f4c4ecd4ecd4ec10ee1139393939310010e4f4ecfcec10c6eefeee10ee3930133e0133321615 +1406071e011514042122262711331e013332363534262b01353332363534262322060723c775 +d75edbf6aa9cb8cbfee7fef875df6e700aae9e99b1b6b05f32afaf908787950d7005962c2ebd +a887b5201ad7abd1df323301229094b19ab0b5669192838b807e0002003f000004b005f00002 +0011009f40250264090a0901640a0a094d010a0c00730e071005730a69030208040600110d03 +0f0b08021210f4d43cc4c4fc3cc4113931002fe4fc3cd43cec321139304b5358071004ed0710 +05ed5922b22f0901015db62009200d200e035d014bb00b544bb00c545b4bb00d545b4bb00f54 +5b58bd0012ffc00001001200120040381137385940180b011a01380149010406021602280a36 +02380a4702480a075d005d01110901213533112135013311211521113302cbfe0203b6fd58f0 +fd74028ec6011dfee3f001fa031afce6fe066a01256d03f4fc0a6bfedb00000100aeffe30479 +05d5001f00ad402503061d781a650610740f651465060c017700620c60201d11020a1e001706 +091e110a0f022010f4ecc4d4ecc410ee1139310010e4f4ec10c6eefeee10fee4123930014bb0 +09544bb00b545b4bb00f545b58bd0020ffc000010020002000403811373859014bb012544bb0 +13545b58bd00200040000100200020ffc0381137385940260f030f040f050f060f070f080f19 +0f1a0f1b0f1c0f1d0f1e0c0f000f011f001f012f002f01065d005d011521113e013332001514 +002122262711331e013332363534262322060723110406fd54348b56f20118fee5ff0067d871 +7109a3939eaaa99f5a89355605d5a4fe542424fef4e8edfef7323301228e96d0c3c2cf404302 +ee0000020089ffe3049605f0000b0025006340220c0006650f0065151f6c1e7923651b691560 +26200a1e16030612150c060905180b2610f4ececf4ecf4ec310010e4f4ecfcec10eed6ee1139 +304025090c090d11041005100610071108130c130d100e100f10101111290c290d4e1f4e204e +21125d253236353426232206151416033e013332001514002322001110002132161715232e01 +232202029e8d98988d8f9698b944ac6cdf0103fee9e9fdfef0014201254fae5b710c826ec2be +46cfc2c2cfc8bdc7d602f04b4afef4e8e3feef0179015e018801ae1e1ef6656afeda00000001 +00ac0000048305d500080072401d030300010002030101004d05010377076201030201030004 +0a0006020910f4c4ec11173931002ff4ec1139304b5358071005ed071005ed5922014bb00954 +58bd0009ffc000010009000900403811373859014bb0125458bd00090040000100090009ffc0 +3811373859b417011803025d0901230121152311210483fdb895022dfd4e7503d7056ffa9105 +31b8015c000000030089ffe3048d05f0000b0017002f003e4022241803651509651e0f652a69 +1e603024180c1205270c052d00061b15060627210b3010f4c4ecf4ecd4ec10ee113939310010 +e4f4ec10eed6ee393930013426232206151416333236033426232206151416333236071e0115 +1404232224353436372e0135343633321615140603ba9f90909f9f90909f298a7c7b8b8b7b7c +8a6caabefef6f8f7fef5beab97a1f8d9d9f8a10198a0b1b1a0a1b1b1037688989888899898c9 +17cd9fd2e3e3d29fcd171baf88b4cfcfb488af0000010064ffe306a605d500130070402d1010 +06070607100f100f4d1007010c08036f0a056211016f0e000924071224100b24070f0d040024 +100f02211410f4ece432d4ece410e410e431002fc6ee32f63cee3232113939304b5358071004 +ed071004ed5922b2201501015d400e05070130154f15701580159f15055d005d333533112335 +210111233521152311230111331564c9c9017f037fc8020cc979fc44c96a05006bfb66042f6b +6bfa7904eafb9d6a000000020066ffe3046a0444000b0017002b4013008f0c068f128c0c6018 +031a1544091a0f2a1810f4ecf4ec310010e4fcec10ee30b420196f1902015d25323635342623 +220615141617220035340033320015140002689497979494979893e8fee60119e9e90119fee7 +46eae4e4e9e9e4e4ea630133fefe0132fecefefefecd0000000100c1ffe301cb00ee000b0038 +b40d0600000c10d4fcc44bb0135158b40a020008043c3c103c3c593100b4036109600c10f4ec +4bb0135158b40501030b073c3c103c3c5930373436333216151406232226c14c39374e4e3739 +4c68384e4e38374e4d000001004a000003710614001c00714026071600120a7a08001c048f19 +71100c7a14089c0e090d012d000d0b07270036130f2c1511301d10f43ce432e4fc3cc410ee11 +3931002fee32ee32feeed6c610ee3212393930b28f1e01015d014bb0155458bd001dffc00001 +001d001d00403811373859b760006001023f1e015d005d01232e012322061d01211521113315 +213533112335333534363332161703716101534f67540129fed7ecfdacb0b0b0b9b343864205 +194b4e7191896bfcae6a6a03526b85b2b61819000002003bffe304b806140014002100474025 +2105111503001e940818940e017a0371007a0e60088c121b1a0b3513022c1511042700302210 +f4ec3232e432f4ec31002fece4ecfcec10ee10ee1117393930b27f2301015d3711233521113e +013332121514022322262715213501141633323635342623220615ecb1016936a77bc4f8f8c4 +7ba736fe970169938c8d91918d8c936a05406afd6d645ffecafafafec95f64a66a0175c0c9e2 +dcdde0cabf000002ff3bfe3901b205e3000b001e006940221e10170c030917161b8f13090c7a +0e9c139d1f182d1600030616360f270d2c0c301f10f4e4fce4d4ec10ee310010ecfcecc410ee +d6c610ce1112393930b62f206020702003015d014bb0155458bd001fffc00001001f001f0040 +3811373859b47317731802005d13343633321615140623222613233521111406232226273533 +1e0133323635cd432f2e4341302f432dae0166c3ab48833e5f0755525b5705712e44442e2f42 +42fe7a6bfb71a4bb2121db605a7b810000020066ffe3045604440014001b004e401e0208157a +000899058f0c188f009b128c0c601c0809151a001b011a0f2a1c10f4ec32d4ecd4cc310010e4 +fcecec10fee410ee1239304012201d401d7f1d03cf00cf01cf02cf15cf1b055d015d01211514 +1633323637330e01232200353400333200072e01232206070456fce7a29e799b1f942cedc1e9 +fee50116e2f10102d40691887f9210020008d7db7f7dafb00133fefc0134fed7b1babdbeb900 +000000010066ffe3041d0444001a0035401a0099178f030d970c95118f098c03601b0e2d0c1a +00141a062a1b10f4ecd4ccd4ec310010e4fcecfcec10fee430b26f1c01015d010e0123220035 +10003332161711232e0123220615141633323637041d27deb0e8fee6011ae865c8656b158d83 +95989796778e1a013faab20133fe00ff01312f30fef08c80e7e6e6e87c7d00000001003bffe3 +0327057100170068401d170a00100d8f140408007a06029c146018071011012c09052703002f +1810f43cec32e4d4cc39310010e4fc3cec32c410fec411393930014bb00d5458bd0018004000 +0100180018ffc0381137385940150507050815071508260726082f197f198f199f190a5d1323 +353311331121152111141633323637330e0123222635dda2a2b9015afea634464842028b088e +919f8403bc6b014afeb66bfd5d874c555f91868da90000010073ffe303b20444002900d94041 +23220224213e0c0b1e1f021d203e0b0c0b4d0b0c2021041601a100a0058f2716a115a01a8f12 +8c27602a200b0c211d08172d151d3e0f0827154624022d0f00452a10f4c4ecd4e4ec10ee10ee +111239393939310010e4fcecf4ec10eef6ee111739304b535807100eed111739070eed111739 +5922b2202b01015d4058271f27202721272227235a0a5a0b5a0c5a0d5a1f5a205a215a225823 +861f8620862186228623961f9620962196229623a61fa620a621a622a6231d402b7f2baf14af +15af16af17af18af19bf14bf15bf16bf17bf18bf190e5d005d3735331e013332363534262f01 +2e013534363332161715232e012322061514161f011e01151406232226736a048d8a7c825f99 +85897bd6bd54ba636a04887574775a87929785e7cb67c43bf877765d594656312d2c846692a6 +2c2ae86774525243512a2d2f8d6f97ad2c0000000002004a0000026005e3000b001500494017 +0309127a149c100c7a0e0003060d2c0c27130f2c11301610f4e432fce4d4ec31002fec32fcec +d4cc30b28f1701015d014bb0155458bd0016ffc0000100160016004038113738591334363332 +1615140623222613331521353311233521c7432f2e43422f2f43ebaefdeab0b0016805712e44 +442e2f4242fb286a6a03526b0001004a000004ee0444001d0070402e070d141a04030117850a +037a059c1b120e03017a0a8c1000113d131c2c060f2c13270d3a042c1a0627002c02301e10f4 +e4ec32e4f4ece410e410e431002f3ceeee1732fcee10ee1112173930b62f1f7f1fb01f03015d +014bb0155458bd001effc00001001e001e0040381137385933353311233521153e0133321615 +1133152135331134262322061511331554a6b0016833a36cb0a6a4fe049f60798086a06a0352 +6bbd6c6ecad6fdc66a6a0200c391bbb3fe1a6a00000000010037ffe304db0427001900754022 +1711060c0d14028509180d7a0f009c096004002c170527032c013a0e2c10270c2f1a10f4ece4 +f4e4fc3ce431002fe4fc3cec3210ee32113939393930014bb00b5458bd001a00400001001a00 +1affc03811373859b47f1bb01b025d014bb0155458bd001affc00001001a001a004038113738 +59012111331521350e01232226351123352111141633323635112302d50158aefe9a33a26bb1 +a7a6015f5f7a8086a00427fc436abc6a6fc9d702396bfd95c290bcb301e300000001004a0000 +03d304440018009540220809130501000f7a110005168c0d097a119c0b0a08022d00102c1208 +270c2c0e301910f4e4ec32e4d4ec10c431002feeee32fec6c610ee10c6113911393040381000 +1001100210031004100510151016101710182f1a400040014002400340044005441540164017 +401815000100021001100220012002065d015d014bb0155458bd0019ffc00001001900190040 +38113738590111232e012322061511331521353311233521153e0133321603d36a054e4b8891 +d5fdcda6b0016836aa7a2d630429fef64f4ebcb0fe1a6a6a035469bd6f6b0e00000200710000 +05f405d500080015003d40190c076f0e620a006f090701150f00040e120d092400110b211610 +f4ece432d4ec113939393931002fec32f4ec3230400930174f1780179f1704015d2533200011 +100021230135331123352120001110002101faba01230137fecafedcbafe77bebe0252018201 +affe50fe7f6a014c013601360148fa966a05006bfe76fea1fea0fe740001003b000002520614 +000900404012067a087104007a02012c002707032c05300a10f4e432fce431002fec32fcec30 +b28f0b01015d014bb0155458bd000affc00001000a000a004038113738592533152135331123 +352101a4aefde9b1b101696a6a6a05406a0000020066ffe3048b0444000a0028007e402f1b21 +0b1900100c017a1993088f13218e238d1e8f268c13600c7a0e02190500212d220d2c1a0f0027 +0b051a22162a2910f4c4ecd4ec3232e410ee1112393931002feee4feeef6e610eef6ee113939 +11391239304024102a6f2a7828c02a047a28c001c002c003c404c405c406c415c416c417c018 +c019c01a0d5d015d01352322061514163332361311331521350e012322263534363321353426 +2322060723353e01333216032fed89868874738db8a4fea43da06bb1d0eed9010293856e8210 +5f60b556dde7014ee1767a6f828e01bcfdd26a734a46bca0a5b64979856462d72929db000000 +0001fffafe39047f0427001c01034059019f02010f0e1b1c021a009f0f0f0e0b0a02099f0e0f +0e089f07080f0f0e083e0908010201050602073e0202014d081d020f1a000216151a8f120d09 +0603027a0b049c129d1d02150e0a090807050100080f0c172d150c031d10d4c4d4ec11391739 +1139310010ecfc3cec173210eed6c611391139111239304b5358071005ed1732071008ed0710 +08ed071005ed173207100eed1117390708ed5922b2070e01015d405a17105901690178010407 +0f1510290529062a0a2a0b270e270f26105801530255055005550650065307560a560b680164 +026005600664077600770178027e037e04740574067909780c780d790e750f75107611761a76 +1b761c285d005d053701233521152309012335211523010e012322262735331e0133323601ba +46fe737901e9aa012b012b9f018f77fe19327a6f2f63325e06393c3743c3b103ce6b6bfd2502 +db6b6bfb547c5b100fcb443b3d00000100b0fef2028106140007002440120473060273007108 +0605020103031200020810f4ec10c0c0c0c0310010fcecd4ec301321152111211521b001d1fe +ee0112fe2f06146af9b26a0000000001004a0000075e0444003000a94041201a130d04062b00 +03071d108503277a299c252118140b05077a2e038c2316090019130a3d0c222c20082c0c2706 +3f173d1927152c133f282c2a2027242c26303110f4e4ec32e4f4e4fce4f4ece410e410e41112 +3931002f3c3cee32ee1732feee10ee32111739173930400b3f325f326f329032b03205015d01 +4bb0155458bd0031ffc00001003100310040381137385940132f0a2f0b2f172f18cf0acf0bcf +17cf18c032095d013e0133321615113315213533113426232206151133152135331134262322 +061511331521353311233521153e01333216042535a56ea7a4a6fe02a0606f7b81a0fe08a060 +6f7b81a0fe02a6b00168339e647ca603587577cfd1fdc66a6a0225a38abab2fe1a6a6a022c9f +87bab2fe1a6a6a035469bd6a707b0001009efef2026f06140007001f400f0373010573007108 +0602080012040810d4ec123939310010fcecd4ec300111213521112135026ffe2f0112feee06 +14f8de6a064e6a000000010a0073000200b800cb00cb00d30002004c006a0071008700a00002 +00e5007b00cb00cb00c1040804080408000200d9050200b800d300b80129006a000200020002 +012f0000000200be0073003300b800e500cb0066000200a000620002000200fa03cd03cd03cd +039a03cd027700020350039a03500000000200a000b8033b040403cd040403cd040400660002 +00cb003d00ba00aa0066000205cd00960000005200d700d700420073004a00bc00d9018300a4 +01d5007d008d007304000000001d010a05d5006a006a006205d505d505d505f0005c00020002 +006a006a006a05d5061400a0006a010a00bc00cb00a40002006a006a01290152036003660158 +007b000201aa0348006a0085006a046004600427042704270444006a00020062000200020002 +027b0073006a00020002000200cd025c0229042701aa005c006a006a00cd00a000aa003d05cd +006600d7004800d700020066000203e900a0030c0000001905c1004a074a060c0106077d0054 +0002007b0333019a061d0060007d0354006a004e0002008d004e01d7007300001400b6060504 +030201002c2010b002254964b040515820c859212d2cb002254964b040515820c859212d2c20 +100720b00050b00d7920b8ffff5058041b0559b0051cb0032508b0042523e120b00050b00d79 +20b8ffff5058041b0559b0051cb0032508e12d2c4b505820b0c9454459212d2cb00225456044 +2d2c4b5358b00225b0022545445921212d2c45442d00000100000002570ababdf8805f0f3cf5 +001f080000000000d0672e4300000000d0672e43f9d8fd3a0d6f08e000000008000000010000 +000000010000076dfe1d00000ddff9d8fc700d6f000100000000000000000000000000000020 +04cd006605170087051700fa0517008b0517009c0517003f051700ae05170089051700ac0517 +00890700006404d10066028b00c1028b000002f6004a051f003b027bff3b04bc0066047b0066 +0337003b041b0073028f004a0527004a0527003703d3004a066a0071028f003b04c500660485 +fffa031f00b00796004a031f009e0000000000000044000000c80000017000000220000002e8 +000003d0000004e4000005c40000066400000730000007e400000864000008c8000008c80000 +099000000a4000000b0800000bb800000c4800000cfc00000e5000000ee000000fa800001070 +00001154000011e80000125000001348000014ac000014f80000162800001670000100000020 +0209002b0098000800020010009900070000040b01f300080004b8028040e0c7fe03c61303c5 +c42405c56403c54004c42403c30d03c2c12705c26403c12703c05d03bf7d03bc0b03bb0b03ba +b91405ba3203b91403b83203b7fe03b6fe03b5fe03b3fe03b2fe03b1b04705b1fa03b04703af +fe03ae7d03adfe03ac0e03abaa0c05ab1403aa0c03a93203a86403a71e03a43203a3a26405a3 +fe03a26403a1960e05a12503a0780a05a025039f4b039e10039d2e039c881e059cfe039b9a10 +059b1d039a100399980e0599250398780a05980e0398400497960e05971403978004960e0396 +40049525039484300594fe039392130593250392910d0592130392b8014040090491900a0591 +0d0391b80100404904900a0390c0048f6f7d058fbb038e810b058e11038e40048d810b058d3a +038c8bbb058cfe038b8a5d058bbb038b80048a8925058a5d038a400489881e05892503888711 +05881e0388b8ffc040ff0487110385843005856403843003831603829603810b038064640580 +fe037f6c10057f19037e7d0e057e32037d0e037c7b0f057c13037b0f037a9603791103780a03 +7776200577fa0376751c05762003751c03746c1005741e0373fe0372fe0371700d0571fe0370 +0d037040046f7d036e6d3e056e6b036d3e036c6b0c056c10036c80046b0c036b40046a646405 +6afa036968bb0569fe0368675d0568bb0368800467662505675d036740046625036564640565 +fa0364640363150362fe0361fe03605f2e0560fe035f2e035efe035dfe035c4b035b7d035afe +0359440358fe0357fe0356bb0355fe03536403521403513203504f0f05507d034f0f034e4140 +42034c0b034a6403492208054996034832034703100547130346120345020a05451903444313 +05446b034342100543130342410b0542100341400905410b0340090340b8ffc04053043f9603 +3e042d053e4d033d3c14053d4b033c3b0a053c14033c40043b0a033a3912053a5d0339381105 +391203381103370d0336fe033534140535fe033433130534140333320a053313033231090532 +0a0332b8ffc040ff04310903302f18053044032f2e15052f18032fc0042e1e0a052e15032e80 +042d0964052d96032c2b14052c4b032b2208052b14032b40042a020a052a6403292830052941 +0328042d0528300327042d0527fe03263a03250d1805255d0324231205245303232208052312 +0323400422080321201805215d03201f110520180320c0041f1e0a051f11031f80041e0a031e +40041d23031c0f031b24031a1930051a530319042d0519300318fe0317020a0517fe03161003 +15141405156b031413130514140314400413130312042d0512bb031103100511fe0310031005 +1042030f0964050f96030e042d050efe030d020a050d18030d40040cfe030b020a050b40386b +030a0964050a7d030964030807110508140307110306053205067d0305042d05053203040310 +05042d03031003020a0301530300fe0301b80164858d012b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b002b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b1d000000> +] def +/f-0-0 currentdict end definefont pop +11 dict begin +/FontType 42 def +/FontName /DejaVuSerif def +/PaintType 0 def +/FontMatrix [ 1 0 0 1 0 0 ] def +/FontBBox [ 0 0 0 0 ] def +/Encoding 256 array def +0 1 255 { Encoding exch /.notdef put } for +Encoding 1 /uniFB00 put +/CharStrings 2 dict dup begin +/.notdef 0 def +/uniFB00 1 def +end readonly def +/sfnts [ +<000100000009008000030010637674208f33abf4000001ec000001946670676de780f1c40000 +03800000008b676c79662172e7fc0000009c00000150686561640747fea80000040c00000036 +686865610eb7086f0000044400000024686d74780a7c00b000000468000000086c6f63610000 +0194000004700000000c6d617870046005330000047c0000002070726570757906f60000049c +0000055e00020066fe96046605a400030007001a400c04c70006c70108055d0204002fc4d4ec +310010d4ecd4ec301311211125211121660400fc73031bfce5fe96070ef8f27206290001004a +ffff062a06140035007640202d31252d24312c2f272436342c1c0007142d1303011a27133609 +052c0b07303610f43ce432e4fc3cc410ee10d43ce4e4fc3cc410ee1139310040212b1d1a0c04 +242f01087a1b2413231228178f200f7130350203077a0b1b2c9c33052f3cee3232ee1732fe3c +ee32d63cc63210ee3232121739300125113315213533112335333534363332161715232e0123 +22061d01213534363332161715232e012322061d0121152111331521353303b4fdfeecfdacb0 +b0b0b8b44286426002525066540202b8b44286426002525066540128fed8ecfdacb003bb01fc +ae6a6a03526b85b2b61819ca4b4e71918984b2b61819ca4b4e7191896bfcae6a6a000000010a +0073000200b800cb00cb00d30002004c006a0071008700a0000200e5007b00cb00cb00c10408 +04080408000200d9050200b800d300b80129006a000200020002012f0000000200be00730033 +00b800e500cb0066000200a000620002000200fa03cd03cd03cd039a03cd027700020350039a +03500000000200a000b8033b040403cd040403cd04040066000200cb003d00ba00aa00660002 +05cd00960000005200d700d700420073004a00bc00d9018300a401d5007d008d007304000000 +001d010a05d5006a006a006205d505d505d505f0005c00020002006a006a006a05d5061400a0 +006a010a00bc00cb00a40002006a006a01290152036003660158007b000201aa0348006a0085 +006a046004600427042704270444006a00020062000200020002027b0073006a000200020002 +00cd025c0229042701aa005c006a006a00cd00a000aa003d05cd006600d7004800d700020066 +000203e900a0030c0000001905c1004a074a060c0106077d00540002007b0333019a061d0060 +007d0354006a004e0002008d004e01d7007300001400b6060504030201002c2010b002254964 +b040515820c859212d2cb002254964b040515820c859212d2c20100720b00050b00d7920b8ff +ff5058041b0559b0051cb0032508b0042523e120b00050b00d7920b8ffff5058041b0559b005 +1cb0032508e12d2c4b505820b0c9454459212d2cb002254560442d2c4b5358b00225b0022545 +445921212d2c45442d00000100000002570a97da7da65f0f3cf5001f080000000000d0672e43 +00000000d0672e43f9d8fd3a0d6f08e000000008000000010000000000010000076dfe1d0000 +0ddff9d8fc700d6f00010000000000000000000000000000000204cd006605af004a00000000 +00000044000001500001000000020209002b0098000800020010009900070000040b01f30008 +0004b8028040e0c7fe03c61303c5c42405c56403c54004c42403c30d03c2c12705c26403c127 +03c05d03bf7d03bc0b03bb0b03bab91405ba3203b91403b83203b7fe03b6fe03b5fe03b3fe03 +b2fe03b1b04705b1fa03b04703affe03ae7d03adfe03ac0e03abaa0c05ab1403aa0c03a93203 +a86403a71e03a43203a3a26405a3fe03a26403a1960e05a12503a0780a05a025039f4b039e10 +039d2e039c881e059cfe039b9a10059b1d039a100399980e0599250398780a05980e03984004 +97960e05971403978004960e039640049525039484300594fe039392130593250392910d0592 +130392b8014040090491900a05910d0391b80100404904900a0390c0048f6f7d058fbb038e81 +0b058e11038e40048d810b058d3a038c8bbb058cfe038b8a5d058bbb038b80048a8925058a5d +038a400489881e0589250388871105881e0388b8ffc040ff0487110385843005856403843003 +831603829603810b038064640580fe037f6c10057f19037e7d0e057e32037d0e037c7b0f057c +13037b0f037a9603791103780a037776200577fa0376751c05762003751c03746c1005741e03 +73fe0372fe0371700d0571fe03700d037040046f7d036e6d3e056e6b036d3e036c6b0c056c10 +036c80046b0c036b40046a6464056afa036968bb0569fe0368675d0568bb0368800467662505 +675d036740046625036564640565fa0364640363150362fe0361fe03605f2e0560fe035f2e03 +5efe035dfe035c4b035b7d035afe0359440358fe0357fe0356bb0355fe035364035214035132 +03504f0f05507d034f0f034e414042034c0b034a640349220805499603483203470310054713 +0346120345020a0545190344431305446b034342100543130342410b0542100341400905410b +0340090340b8ffc04053043f96033e042d053e4d033d3c14053d4b033c3b0a053c14033c4004 +3b0a033a3912053a5d0339381105391203381103370d0336fe033534140535fe033433130534 +140333320a0533130332310905320a0332b8ffc040ff04310903302f18053044032f2e15052f +18032fc0042e1e0a052e15032e80042d0964052d96032c2b14052c4b032b2208052b14032b40 +042a020a052a64032928300529410328042d0528300327042d0527fe03263a03250d1805255d +03242312052453032322080523120323400422080321201805215d03201f110520180320c004 +1f1e0a051f11031f80041e0a031e40041d23031c0f031b24031a1930051a530319042d051930 +0318fe0317020a0517fe0316100315141405156b031413130514140314400413130312042d05 +12bb031103100511fe03100310051042030f0964050f96030e042d050efe030d020a050d1803 +0d40040cfe030b020a050b40386b030a0964050a7d0309640308071105081403071103060532 +05067d0305042d0505320304031005042d03031003020a0301530300fe0301b80164858d012b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b002b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b1d000000> +] def +/f-0-1 currentdict end definefont pop +%%Page: 1 1 +%%BeginPageSetup +%%PageBoundingBox: 3 2 313 194 +%%EndPageSetup +q 3 2 310 192 rectclip q +0 g +0.8 w +1 J +1 j +[] 0.0 d +4 M q 1 0 0 -1 0 200 cm +43.762 160.398 m 38.398 160.398 l S Q +BT +9 0 0 9 27.629531 36.88 Tm +/f-0-0 1 Tf +(0)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 138.961 m 38.398 138.961 l S Q +BT +9 0 0 9 21.899063 58.32 Tm +/f-0-0 1 Tf +(10)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 117.441 m 38.398 117.441 l S Q +BT +9 0 0 9 21.899063 79.84 Tm +/f-0-0 1 Tf +(20)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 96 m 38.398 96 l S Q +BT +9 0 0 9 21.899063 101.28 Tm +/f-0-0 1 Tf +(30)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 74.559 m 38.398 74.559 l S Q +BT +9 0 0 9 21.899063 122.72 Tm +/f-0-0 1 Tf +(40)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 53.121 m 38.398 53.121 l S Q +BT +9 0 0 9 21.899063 144.16 Tm +/f-0-0 1 Tf +(50)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 31.602 m 38.398 31.602 l S Q +BT +9 0 0 9 21.899063 165.68 Tm +/f-0-0 1 Tf +(60)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 10.16 m 38.398 10.16 l S Q +BT +9 0 0 9 21.899063 187.12 Tm +/f-0-0 1 Tf +(70)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 160.398 m 43.762 165.762 l S Q +BT +9 0 0 9 40.894766 20.8 Tm +/f-0-0 1 Tf +(0)Tj +ET +q 1 0 0 -1 0 200 cm +96 160.398 m 96 165.762 l S Q +BT +9 0 0 9 90.269531 20.8 Tm +/f-0-0 1 Tf +(20)Tj +ET +q 1 0 0 -1 0 200 cm +148.16 160.398 m 148.16 165.762 l S Q +BT +9 0 0 9 142.429531 20.8 Tm +/f-0-0 1 Tf +(40)Tj +ET +q 1 0 0 -1 0 200 cm +200.398 160.398 m 200.398 165.762 l S Q +BT +9 0 0 9 194.669531 20.8 Tm +/f-0-0 1 Tf +(60)Tj +ET +q 1 0 0 -1 0 200 cm +252.559 160.398 m 252.559 165.762 l S Q +BT +9 0 0 9 246.829531 20.8 Tm +/f-0-0 1 Tf +(80)Tj +ET +q 1 0 0 -1 0 200 cm +304.801 160.398 m 304.801 165.762 l S Q +BT +9 0 0 9 296.204297 20.8 Tm +/f-0-0 1 Tf +(100)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 10.16 m 43.762 160.398 l 304.801 160.398 l S Q +BT +-0.000000000000001653 9 -9 -0.000000000000001653 10.56 62.178984 Tm +/f-0-0 1 Tf +[(No)18(. of objec)-3(ts in )-3(bu)]TJ +/f-0-1 1 Tf +<01>Tj +/f-0-0 1 Tf +[(er)]TJ +9 0 0 9 149.77125 4.72 Tm +[(Delay [ms)-3(])]TJ +ET +2.4 w +q 1 0 0 -1 0 200 cm +43.762 38.078 m 46.398 10.719 l 49.039 114.641 l 51.68 128.078 l 54.32 +134.961 l 56.961 139.121 l 59.602 143.441 l 62.238 145.52 l 64.879 147.602 + l 67.52 147.441 l 70.16 147.68 l 72.801 149.84 l 75.441 149.602 l 78 149.922 + l 80.641 152 l 83.281 151.762 l 85.922 151.84 l 91.199 151.84 l 93.84 151.762 + l 96.48 152.16 l 99.121 154.16 l 101.762 153.922 l 104.398 154 l 107.039 + 153.922 l 109.68 154 l 138.719 154 l 141.359 153.922 l 143.922 154 l 146.559 + 153.762 l 149.199 154.801 l 151.84 156.32 l 154.48 156.078 l 157.121 156.16 + l 159.762 156.078 l 244.16 156.078 l 246.801 156.16 l 249.441 155.922 l + 252.078 157.922 l 254.719 158.32 l 257.359 158.238 l 304.801 158.238 l S Q +0.8 w +q 1 0 0 -1 0 200 cm +43.762 10.16 m 43.762 160.398 l 304.801 160.398 l S Q +Q Q +showpage +%%Trailer +end restore +%%EOF diff --git a/figures/discovery.eps b/figures/discovery.eps @@ -0,0 +1,579 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Creator: cairo 1.13.1 (http://cairographics.org) +%%CreationDate: Sun Mar 22 23:12:52 2015 +%%Pages: 1 +%%DocumentData: Clean7Bit +%%LanguageLevel: 2 +%%BoundingBox: 3 4 310 194 +%%EndComments +%%BeginProlog +save +50 dict begin +/q { gsave } bind def +/Q { grestore } bind def +/cm { 6 array astore concat } bind def +/w { setlinewidth } bind def +/J { setlinecap } bind def +/j { setlinejoin } bind def +/M { setmiterlimit } bind def +/d { setdash } bind def +/m { moveto } bind def +/l { lineto } bind def +/c { curveto } bind def +/h { closepath } bind def +/re { exch dup neg 3 1 roll 5 3 roll moveto 0 rlineto + 0 exch rlineto 0 rlineto closepath } bind def +/S { stroke } bind def +/f { fill } bind def +/f* { eofill } bind def +/n { newpath } bind def +/W { clip } bind def +/W* { eoclip } bind def +/BT { } bind def +/ET { } bind def +/pdfmark where { pop globaldict /?pdfmark /exec load put } + { globaldict begin /?pdfmark /pop load def /pdfmark + /cleartomark load def end } ifelse +/BDC { mark 3 1 roll /BDC pdfmark } bind def +/EMC { mark /EMC pdfmark } bind def +/cairo_store_point { /cairo_point_y exch def /cairo_point_x exch def } def +/Tj { show currentpoint cairo_store_point } bind def +/TJ { + { + dup + type /stringtype eq + { show } { -0.001 mul 0 cairo_font_matrix dtransform rmoveto } ifelse + } forall + currentpoint cairo_store_point +} bind def +/cairo_selectfont { cairo_font_matrix aload pop pop pop 0 0 6 array astore + cairo_font exch selectfont cairo_point_x cairo_point_y moveto } bind def +/Tf { pop /cairo_font exch def /cairo_font_matrix where + { pop cairo_selectfont } if } bind def +/Td { matrix translate cairo_font_matrix matrix concatmatrix dup + /cairo_font_matrix exch def dup 4 get exch 5 get cairo_store_point + /cairo_font where { pop cairo_selectfont } if } bind def +/Tm { 2 copy 8 2 roll 6 array astore /cairo_font_matrix exch def + cairo_store_point /cairo_font where { pop cairo_selectfont } if } bind def +/g { setgray } bind def +/rg { setrgbcolor } bind def +/d1 { setcachedevice } bind def +%%EndProlog +11 dict begin +/FontType 42 def +/FontName /DejaVuSerif def +/PaintType 0 def +/FontMatrix [ 1 0 0 1 0 0 ] def +/FontBBox [ 0 0 0 0 ] def +/Encoding 256 array def +0 1 255 { Encoding exch /.notdef put } for +Encoding 32 /space put +Encoding 46 /period put +Encoding 48 /zero put +Encoding 49 /one put +Encoding 50 /two put +Encoding 51 /three put +Encoding 52 /four put +Encoding 53 /five put +Encoding 54 /six put +Encoding 56 /eight put +Encoding 57 /nine put +Encoding 68 /D put +Encoding 78 /N put +Encoding 84 /T put +Encoding 91 /bracketleft put +Encoding 93 /bracketright put +Encoding 97 /a put +Encoding 99 /c put +Encoding 100 /d put +Encoding 101 /e put +Encoding 102 /f put +Encoding 104 /h put +Encoding 105 /i put +Encoding 109 /m put +Encoding 110 /n put +Encoding 111 /o put +Encoding 114 /r put +Encoding 115 /s put +Encoding 116 /t put +Encoding 117 /u put +Encoding 118 /v put +Encoding 119 /w put +Encoding 121 /y put +/CharStrings 34 dict dup begin +/.notdef 0 def +/zero 1 def +/period 2 def +/three 3 def +/six 4 def +/nine 5 def +/one 6 def +/two 7 def +/five 8 def +/eight 9 def +/four 10 def +/T 11 def +/i 12 def +/m 13 def +/e 14 def +/space 15 def +/bracketleft 16 def +/s 17 def +/bracketright 18 def +/N 19 def +/o 20 def +/f 21 def +/n 22 def +/d 23 def +/D 24 def +/c 25 def +/v 26 def +/r 27 def +/y 28 def +/w 29 def +/t 30 def +/h 31 def +/u 32 def +/a 33 def +end readonly def +/sfnts [ +<000100000009008000030010637674208f33abf400001aa8000001946670676de780f1c40000 +1c3c0000008b676c796668dc6f2b0000009c00001a0c686561640747fea800001cc800000036 +686865610eb7088f00001d0000000024686d7478a0360d3a00001d24000000886c6f63610001 +a06c00001dac0000008c6d6178700480053300001e380000002070726570757906f600001e58 +0000055e00020066fe96046605a400030007001a400c04c70006c70108055d0204002fc4d4ec +310010d4ecd4ec301311211125211121660400fc73031bfce5fe96070ef8f272062900020087 +ffe3048f05f0000b00170023401300650c066512690c60180306151409060f0b1810f4ecf4ec +310010e4f4ec10ee30253212111002232202111012172200111000333200111000028b999898 +9999989899f3feef0111f3f40110fef0460150015301540150feb0feacfeadfeb0630198016e +016f0198fe68fe91fe92fe680000000100c1ffe301cb00ee000b0038b40d0600000c10d4fcc4 +4bb0135158b40a020008043c3c103c3c593100b4036109600c10f4ec4bb0135158b40501030b +073c3c103c3c5930373436333216151406232226c14c39374e4e37394c68384e4e38374e4d00 +0001009cffe3047f05f0002a004d402b091d651f1374126517651f0f29740065266503690f60 +2b201e091d23290a002306061a060c140a0012022b10f4c4ecd4ecd4ec10ee11393939393100 +10e4f4ecfcec10c6eefeee10ee3930133e01333216151406071e011514042122262711331e01 +3332363534262b01353332363534262322060723c775d75edbf6aa9cb8cbfee7fef875df6e70 +0aae9e99b1b6b05f32afaf908787950d7005962c2ebda887b5201ad7abd1df323301229094b1 +9ab0b5669192838b807e00020089ffe3049605f0000b0025006340220c0006650f0065151f6c +1e7923651b69156026200a1e16030612150c060905180b2610f4ececf4ecf4ec310010e4f4ec +fcec10eed6ee1139304025090c090d11041005100610071108130c130d100e100f1010111129 +0c290d4e1f4e204e21125d253236353426232206151416033e01333200151400232200111000 +2132161715232e01232202029e8d98988d8f9698b944ac6cdf0103fee9e9fdfef0014201254f +ae5b710c826ec2be46cfc2c2cfc8bdc7d602f04b4afef4e8e3feef0179015e018801ae1e1ef6 +656afeda000000020081ffe3048d05f000190025005d4024001a206503136c127917650f031a +6509690f6026140a12000623050c151d061216060b2610f4e4ecf4ecec10ee310010e4f4ecc4 +10eefeee10ee113930401b1f011f021f031f041f051f1e1f1f1f201f211f224113411441150d +5d010e012322003534003332001110002122262735331e013332120122061514163332363534 +2603be43ae6ddefeff0117e9fd010ffebefedc4fae5b700d826dc2befebe8e97978e8e979802 +9d4b4a010ce8e30111fe87fea2fe78fe521e1ef8656c01250422cfc2c2d0c9bdc7d600000001 +00fa000003f405f0000a0078401c0464050605036406054d0306040105066908017300090711 +0400020b10d4c4c4fcc431002fec32f4c411391139304b53580704ed071004ed5922014bb00a +5458bd000b00400001000b000bffc038113738594009200020012f092f0a045d014bb00b5458 +bd000bffc00001000b000b00403811373859213521110535253311211501230104fed3016c8a +01046a04dac383ecfa7a6a0000000001008b0000044e05f0001c004d40210c14000f0d007402 +641a6505690d7711140d0c17000a011706080e0a1001120b1d10f4c4d4ecd4ec10ee11393939 +31002feef6eefeee10c411393930400b460a460b460c4614461505015d0123113e0133320415 +1401060701213533112135013e013534262322060106706bd968e9010efece180cfe87026f75 +fc3d01c596809d8a8f9c0471010a393ce2c2dbfecf170cfe87b8fea46d01c496fb8a97aa8e00 +000100aeffe3047905d5001f00ad402503061d781a650610740f651465060c017700620c6020 +1d11020a1e001706091e110a0f022010f4ecc4d4ecc410ee1139310010e4f4ec10c6eefeee10 +fee4123930014bb009544bb00b545b4bb00f545b58bd0020ffc0000100200020004038113738 +59014bb012544bb013545b58bd00200040000100200020ffc0381137385940260f030f040f05 +0f060f070f080f190f1a0f1b0f1c0f1d0f1e0c0f000f011f001f012f002f01065d005d011521 +113e013332001514002122262711331e013332363534262322060723110406fd54348b56f201 +18fee5ff0067d8717109a3939eaaa99f5a89355605d5a4fe542424fef4e8edfef7323301228e +96d0c3c2cf404302ee0000030089ffe3048d05f0000b0017002f003e4022241803651509651e +0f652a691e603024180c1205270c052d00061b15060627210b3010f4c4ecf4ecd4ec10ee1139 +39310010e4f4ec10eed6ee393930013426232206151416333236033426232206151416333236 +071e01151404232224353436372e0135343633321615140603ba9f90909f9f90909f298a7c7b +8b8b7b7c8a6caabefef6f8f7fef5beab97a1f8d9d9f8a10198a0b1b1a0a1b1b1037688989888 +899898c917cd9fd2e3e3d29fcd171baf88b4cfcfb488af000002003f000004b005f000020011 +009f40250264090a0901640a0a094d010a0c00730e071005730a69030208040600110d030f0b +08021210f4d43cc4c4fc3cc4113931002fe4fc3cd43cec321139304b5358071004ed071005ed +5922b22f0901015db62009200d200e035d014bb00b544bb00c545b4bb00d545b4bb00f545b58 +bd0012ffc00001001200120040381137385940180b011a01380149010406021602280a360238 +0a4702480a075d005d01110901213533112135013311211521113302cbfe0203b6fd58f0fd74 +028ec6011dfee3f001fa031afce6fe066a01256d03f4fc0a6bfedb00000100140000054205d5 +000f007b401b09050b036f07620d016f000a0f08040f060e24080c11002406021010d4c4e4fc +c4e410ee10ee31002fee32f4fe3cc43230014bb0095458bd00100040000100100010ffc03811 +373859b21f11015d014bb00b544bb00c545b58bd0010ffc00001001000100040381137385940 +0b2f1160118f11a011bf11055d213533112115231121112335211133150187bffe497b052e7b +fe49bf6a04f4e90160fea0e9fb0c6a0000000002004a0000026005e3000b0015004940170309 +127a149c100c7a0e0003060d2c0c27130f2c11301610f4e432fce4d4ec31002fec32fcecd4cc +30b28f1701015d014bb0155458bd0016ffc00001001600160040381137385913343633321615 +140623222613331521353311233521c7432f2e43422f2f43ebaefdeab0b0016805712e44442e +2f4242fb286a6a03526b0001004a0000075e0444003000a94041201a130d04062b0003071d10 +8503277a299c252118140b05077a2e038c2316090019130a3d0c222c20082c0c27063f173d19 +27152c133f282c2a2027242c26303110f4e4ec32e4f4e4fce4f4ece410e410e411123931002f +3c3cee32ee1732feee10ee32111739173930400b3f325f326f329032b03205015d014bb01554 +58bd0031ffc00001003100310040381137385940132f0a2f0b2f172f18cf0acf0bcf17cf18c0 +32095d013e013332161511331521353311342623220615113315213533113426232206151133 +1521353311233521153e01333216042535a56ea7a4a6fe02a0606f7b81a0fe08a0606f7b81a0 +fe02a6b00168339e647ca603587577cfd1fdc66a6a0225a38abab2fe1a6a6a022c9f87bab2fe +1a6a6a035469bd6a707b00020066ffe3045604440014001b004e401e0208157a000899058f0c +188f009b128c0c601c0809151a001b011a0f2a1c10f4ec32d4ecd4cc310010e4fcecec10fee4 +10ee1239304012201d401d7f1d03cf00cf01cf02cf15cf1b055d015d01211514163332363733 +0e01232200353400333200072e01232206070456fce7a29e799b1f942cedc1e9fee50116e2f1 +0102d40691887f9210020008d7db7f7dafb00133fefc0134fed7b1babdbeb9000000000100b0 +fef20281061400070024401204730602730071080605020103031200020810f4ec10c0c0c0c0 +310010fcecd4ec301321152111211521b001d1feee0112fe2f06146af9b26a00000000010073 +ffe303b20444002900d9404123220224213e0c0b1e1f021d203e0b0c0b4d0b0c2021041601a1 +00a0058f2716a115a01a8f128c27602a200b0c211d08172d151d3e0f0827154624022d0f0045 +2a10f4c4ecd4e4ec10ee10ee111239393939310010e4fcecf4ec10eef6ee111739304b535807 +100eed111739070eed1117395922b2202b01015d4058271f27202721272227235a0a5a0b5a0c +5a0d5a1f5a205a215a225823861f8620862186228623961f9620962196229623a61fa620a621 +a622a6231d402b7f2baf14af15af16af17af18af19bf14bf15bf16bf17bf18bf190e5d005d37 +35331e013332363534262f012e013534363332161715232e012322061514161f011e01151406 +232226736a048d8a7c825f9985897bd6bd54ba636a04887574775a87929785e7cb67c43bf877 +765d594656312d2c846692a62c2ae86774525243512a2d2f8d6f97ad2c0000000001009efef2 +026f06140007001f400f03730105730071080602080012040810d4ec123939310010fcecd4ec +300111213521112135026ffe2f0112feee0614f8de6a064e6a00000000010064ffe306a605d5 +00130070402d101006070607100f100f4d1007010c08036f0a056211016f0e00092407122410 +0b24070f0d040024100f02211410f4ece432d4ece410e410e431002fc6ee32f63cee32321139 +39304b5358071004ed071004ed5922b2201501015d400e05070130154f15701580159f15055d +005d333533112335210111233521152311230111331564c9c9017f037fc8020cc979fc44c96a +05006bfb66042f6b6bfa7904eafb9d6a000000020066ffe3046a0444000b0017002b4013008f +0c068f128c0c6018031a1544091a0f2a1810f4ecf4ec310010e4fcec10ee30b420196f190201 +5d25323635342623220615141617220035340033320015140002689497979494979893e8fee6 +0119e9e90119fee746eae4e4e9e9e4e4ea630133fefe0132fecefefefecd00000001004a0000 +03710614001c00714026071600120a7a08001c048f1971100c7a14089c0e090d012d000d0b07 +270036130f2c1511301d10f43ce432e4fc3cc410ee113931002fee32ee32feeed6c610ee3212 +393930b28f1e01015d014bb0155458bd001dffc00001001d001d00403811373859b760006001 +023f1e015d005d01232e012322061d0121152111331521353311233533353436333216170371 +6101534f67540129fed7ecfdacb0b0b0b9b343864205194b4e7191896bfcae6a6a03526b85b2 +b61819000001004a000004ee0444001d0070402e070d141a04030117850a037a059c1b120e03 +017a0a8c1000113d131c2c060f2c13270d3a042c1a0627002c02301e10f4e4ec32e4f4ece410 +e410e431002f3ceeee1732fcee10ee1112173930b62f1f7f1fb01f03015d014bb0155458bd00 +1effc00001001e001e0040381137385933353311233521153e01333216151133152135331134 +262322061511331554a6b0016833a36cb0a6a4fe049f60798086a06a03526bbd6c6ecad6fdc6 +6a6a0200c391bbb3fe1a6a00000000020066ffe304e3061400140021004f4026160410150300 +19940d1f9407117a1371007a07600d8c02122c15100327012c00351c1a0a2a2210f4ecf4e4fc +3c3ce431002fece4ecfcec10ee10ee11173939304009002310237f23b02304015d2533152135 +0e012322023534123332161711233521033534262322061514163332360433b0fe9836a77bc4 +f9f8c57ba736ae0166b8938c8e91918e8c936a6aa6645f0137fafa01365f6402296afbcb69bf +cae0dddce2c9000000020071000005f405d500080015003d40190c076f0e620a006f09070115 +0f00040e120d092400110b211610f4ece432d4ec113939393931002fec32f4ec323040093017 +4f1780179f1704015d2533200011100021230135331123352120001110002101faba01230137 +fecafedcbafe77bebe0252018201affe50fe7f6a014c013601360148fa966a05006bfe76fea1 +fea0fe7400010066ffe3041d0444001a0035401a0099178f030d970c95118f098c03601b0e2d +0c1a00141a062a1b10f4ecd4ccd4ec310010e4fcecfcec10fee430b26f1c01015d010e012322 +003510003332161711232e0123220615141633323637041d27deb0e8fee6011ae865c8656b15 +8d8395989796778e1a013faab20133fe00ff01312f30fef08c80e7e6e6e87c7d00000001fffa +0000047f0427000e00b840390a0902089f0d0e0d079f06070e0e0d073e080700010004050206 +3e0101004d07000c080503017a0a039c000e0d09080706040100090f0b020f10d4cc11173931 +002ffc3cec17321139304b5358071005ed1732071008ed071008ed071005ed17325922b2080a +01015d4048060716072707200753076307760707080808091b041b051509150a25002a042a05 +2a092a0a2a0e380030104800470d470e5700580e6700680e76047605770678087809780a780d +1c5d005d21012335211523090123352115230101fafe797901e9aa012b012b9f018f77fe7903 +bc6b6bfd2502db6b6bfc44000001004a000003d304440018009540220809130501000f7a1100 +05168c0d097a119c0b0a08022d00102c1208270c2c0e301910f4e4ec32e4d4ec10c431002fee +ee32fec6c610ee10c61139113930403810001001100210031004100510151016101710182f1a +400040014002400340044005441540164017401815000100021001100220012002065d015d01 +4bb0155458bd0019ffc0000100190019004038113738590111232e0123220615113315213533 +11233521153e0133321603d36a054e4b8891d5fdcda6b0016836aa7a2d630429fef64f4ebcb0 +fe1a6a6a035469bd6f6b0e000001fffafe39047f0427001c01034059019f02010f0e1b1c021a +009f0f0f0e0b0a02099f0e0f0e089f07080f0f0e083e0908010201050602073e0202014d081d +020f1a000216151a8f120d090603027a0b049c129d1d02150e0a090807050100080f0c172d15 +0c031d10d4c4d4ec113917391139310010ecfc3cec173210eed6c611391139111239304b5358 +071005ed1732071008ed071008ed071005ed173207100eed1117390708ed5922b2070e01015d +405a171059016901780104070f1510290529062a0a2a0b270e270f2610580153025505500555 +0650065307560a560b680164026005600664077600770178027e037e04740574067909780c78 +0d790e750f75107611761a761b761c285d005d053701233521152309012335211523010e0123 +22262735331e0133323601ba46fe737901e9aa012b012b9f018f77fe19327a6f2f63325e0639 +3c3743c3b103ce6b6bfd2502db6b6bfb547c5b100fcb443b3d0000010021000006be04270014 +01c4405b0b9f1314130a9f090a1414130a3e0b0a000100093e010100040302029f070807019f +0001080807133e14130c0d0c101102123e0d0d0c4d130a010308110d0603027a0f04009c0b08 +141312100d0c0b0a090807030201000f050e1510d4cc173931002f3cfc3c3cec173211173930 +4b5358071005ed1732071008ed071008ed071005ed1732071005ed071008ed071008ed071005 +ed5922b2601601015d40ff03011701160a1a1324012c0a281333013d0a391344014a0a491357 +0a5e136401690a691374017a0a7a138a0a160600070108020d030d0405080709060a070b0a0c +061413001001100213031304100510061007170810081009120a140b180c1613131426002801 +2909260a230b2a102a11251326143a003b013f023f033f043f053f063f073a083b09390a3b0c +380d38123a1339144600450145084509460a460b490c480d4810481148124813461451005001 +50025003500450055006500750085009520a540b581256135314501662006001600264036404 +60056006600760086009620a640b6613621460167500780179027d037d047905790679077a08 +401f7909760a710b750c760d760e760f771077117712741377148a09890ac016785d005d0901 +1323352115230123090123012335211523130103d70110f09a018176fec499fefafef993fec5 +7701e1acee01120427fcc202d36b6bfc44031bfce503bc6b6bfd2d033e000001003bffe30327 +057100170068401d170a00100d8f140408007a06029c146018071011012c09052703002f1810 +f43cec32e4d4cc39310010e4fc3cec32c410fec411393930014bb00d5458bd00180040000100 +180018ffc0381137385940150507050815071508260726082f197f198f199f190a5d13233533 +11331121152111141633323637330e0123222635dda2a2b9015afea634464842028b088e919f +8403bc6b014afeb66bfd5d874c555f91868da9000001004a000004ee0614001d006f402c1a14 +070d0117850a037a05711b120e03017a0a8c1000113d131c2c060f2c13270d3a042c1a062700 +2c02301e10f4e4ec32e4f4ece410e410e431002f3ceeee1732fcee10ee113939393930b62f1f +7f1fb01f03015d014bb0155458bd001effc00001001e001e0040381137385933353311233521 +113e01333216151133152135331134262322061511331554a6b0016833a36cb0a6a4fe049f5f +7a8086a06a05406afd566c6ecad6fdc66a6a0200c38fbab2fe1a6a00000000010037ffe304db +04270019007540221711060c0d14028509180d7a0f009c096004002c170527032c013a0e2c10 +270c2f1a10f4ece4f4e4fc3ce431002fe4fc3cec3210ee32113939393930014bb00b5458bd00 +1a00400001001a001affc03811373859b47f1bb01b025d014bb0155458bd001affc00001001a +001a00403811373859012111331521350e01232226351123352111141633323635112302d501 +58aefe9a33a26bb1a7a6015f5f7a8086a00427fc436abc6a6fc9d702396bfd95c290bcb301e3 +000000020066ffe3048b0444000a0028007e402f1b210b1900100c017a1993088f13218e238d +1e8f268c13600c7a0e02190500212d220d2c1a0f00270b051a22162a2910f4c4ecd4ec3232e4 +10ee1112393931002feee4feeef6e610eef6ee11393911391239304024102a6f2a7828c02a04 +7a28c001c002c003c404c405c406c415c416c417c018c019c01a0d5d015d0135232206151416 +3332361311331521350e0123222635343633213534262322060723353e01333216032fed8986 +8874738db8a4fea43da06bb1d0eed9010293856e82105f60b556dde7014ee1767a6f828e01bc +fdd26a734a46bca0a5b64979856462d72929db000000010a0073000200b800cb00cb00d30002 +004c006a0071008700a0000200e5007b00cb00cb00c1040804080408000200d9050200b800d3 +00b80129006a000200020002012f0000000200be0073003300b800e500cb0066000200a00062 +0002000200fa03cd03cd03cd039a03cd027700020350039a03500000000200a000b8033b0404 +03cd040403cd04040066000200cb003d00ba00aa0066000205cd00960000005200d700d70042 +0073004a00bc00d9018300a401d5007d008d007304000000001d010a05d5006a006a006205d5 +05d505d505f0005c00020002006a006a006a05d5061400a0006a010a00bc00cb00a40002006a +006a01290152036003660158007b000201aa0348006a0085006a046004600427042704270444 +006a00020062000200020002027b0073006a00020002000200cd025c0229042701aa005c006a +006a00cd00a000aa003d05cd006600d7004800d700020066000203e900a0030c0000001905c1 +004a074a060c0106077d00540002007b0333019a061d0060007d0354006a004e0002008d004e +01d7007300001400b6060504030201002c2010b002254964b040515820c859212d2cb0022549 +64b040515820c859212d2c20100720b00050b00d7920b8ffff5058041b0559b0051cb0032508 +b0042523e120b00050b00d7920b8ffff5058041b0559b0051cb0032508e12d2c4b505820b0c9 +454459212d2cb002254560442d2c4b5358b00225b0022545445921212d2c45442d0000010000 +0002570add4f36285f0f3cf5001f080000000000d0672e4300000000d0672e43f9d8fd3a0d6f +08e000000008000000010000000000010000076dfe1d00000ddff9d8fc700d6f000100000000 +00000000000000000000002204cd006605170087028b00c10517009c05170089051700810517 +00fa0517008b051700ae051700890517003f05560014028f004a0796004a04bc0066028b0000 +031f00b0041b0073031f009e0700006404d1006602f6004a0527004a051f0066066a0071047b +00660485fffa03d3004a0485fffa06d900210337003b0527004a0527003704c5006600000000 +00000044000000c80000012c000001f4000002d4000003b000000458000005080000061c0000 +06e8000007d0000008840000091400000a4400000af400000af400000b4000000c9400000cdc +00000d9000000e1000000ed800000fa000001058000010ec0000117c00001270000013540000 +14b8000016d0000017840000184c0000191400001a0c0001000000220209002b009800080002 +0010009900070000040b01f300080004b8028040e0c7fe03c61303c5c42405c56403c54004c4 +2403c30d03c2c12705c26403c12703c05d03bf7d03bc0b03bb0b03bab91405ba3203b91403b8 +3203b7fe03b6fe03b5fe03b3fe03b2fe03b1b04705b1fa03b04703affe03ae7d03adfe03ac0e +03abaa0c05ab1403aa0c03a93203a86403a71e03a43203a3a26405a3fe03a26403a1960e05a1 +2503a0780a05a025039f4b039e10039d2e039c881e059cfe039b9a10059b1d039a100399980e +0599250398780a05980e0398400497960e05971403978004960e039640049525039484300594 +fe039392130593250392910d0592130392b8014040090491900a05910d0391b8010040490490 +0a0390c0048f6f7d058fbb038e810b058e11038e40048d810b058d3a038c8bbb058cfe038b8a +5d058bbb038b80048a8925058a5d038a400489881e0589250388871105881e0388b8ffc040ff +0487110385843005856403843003831603829603810b038064640580fe037f6c10057f19037e +7d0e057e32037d0e037c7b0f057c13037b0f037a9603791103780a037776200577fa0376751c +05762003751c03746c1005741e0373fe0372fe0371700d0571fe03700d037040046f7d036e6d +3e056e6b036d3e036c6b0c056c10036c80046b0c036b40046a6464056afa036968bb0569fe03 +68675d0568bb0368800467662505675d036740046625036564640565fa0364640363150362fe +0361fe03605f2e0560fe035f2e035efe035dfe035c4b035b7d035afe0359440358fe0357fe03 +56bb0355fe03536403521403513203504f0f05507d034f0f034e414042034c0b034a64034922 +08054996034832034703100547130346120345020a0545190344431305446b03434210054313 +0342410b0542100341400905410b0340090340b8ffc04053043f96033e042d053e4d033d3c14 +053d4b033c3b0a053c14033c40043b0a033a3912053a5d0339381105391203381103370d0336 +fe033534140535fe033433130534140333320a0533130332310905320a0332b8ffc040ff0431 +0903302f18053044032f2e15052f18032fc0042e1e0a052e15032e80042d0964052d96032c2b +14052c4b032b2208052b14032b40042a020a052a64032928300529410328042d052830032704 +2d0527fe03263a03250d1805255d032423120524530323220805231203234004220803212018 +05215d03201f110520180320c0041f1e0a051f11031f80041e0a031e40041d23031c0f031b24 +031a1930051a530319042d0519300318fe0317020a0517fe0316100315141405156b03141313 +0514140314400413130312042d0512bb031103100511fe03100310051042030f0964050f9603 +0e042d050efe030d020a050d18030d40040cfe030b020a050b40386b030a0964050a7d030964 +030807110508140307110306053205067d0305042d0505320304031005042d03031003020a03 +01530300fe0301b80164858d012b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b002b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b1d000000> +] def +/f-0-0 currentdict end definefont pop +%%Page: 1 1 +%%BeginPageSetup +%%PageBoundingBox: 3 4 310 194 +%%EndPageSetup +q 3 4 307 190 rectclip q +0 g +0.8 w +1 J +1 j +[] 0.0 d +4 M q 1 0 0 -1 0 200 cm +48.801 160.32 m 43.441 160.32 l S Q +BT +9 0 0 9 32.669531 36.96 Tm +/f-0-0 1 Tf +(0)Tj +ET +q 1 0 0 -1 0 200 cm +48.801 135.281 m 43.441 135.281 l S Q +BT +9 0 0 9 24.073828 62 Tm +/f-0-0 1 Tf +(0.3)Tj +ET +q 1 0 0 -1 0 200 cm +48.801 110.238 m 43.441 110.238 l S Q +BT +9 0 0 9 24.073828 87.04 Tm +/f-0-0 1 Tf +(0.6)Tj +ET +q 1 0 0 -1 0 200 cm +48.801 85.199 m 43.441 85.199 l S Q +BT +9 0 0 9 24.073828 112.08 Tm +/f-0-0 1 Tf +(0.9)Tj +ET +q 1 0 0 -1 0 200 cm +48.801 60.238 m 43.441 60.238 l S Q +BT +9 0 0 9 24.073828 137.04 Tm +/f-0-0 1 Tf +(1.2)Tj +ET +q 1 0 0 -1 0 200 cm +48.801 35.199 m 43.441 35.199 l S Q +BT +9 0 0 9 24.073828 162.08 Tm +/f-0-0 1 Tf +(1.5)Tj +ET +q 1 0 0 -1 0 200 cm +48.801 10.16 m 43.441 10.16 l S Q +BT +9 0 0 9 24.073828 187.12 Tm +/f-0-0 1 Tf +(1.8)Tj +ET +q 1 0 0 -1 0 200 cm +48.801 160.398 m 48.801 165.762 l S Q +BT +9 0 0 9 45.934766 20.8 Tm +/f-0-0 1 Tf +(2)Tj +ET +q 1 0 0 -1 0 200 cm +65.84 160.398 m 65.84 165.762 l S Q +BT +9 0 0 9 62.974766 20.8 Tm +/f-0-0 1 Tf +(4)Tj +ET +q 1 0 0 -1 0 200 cm +100 160.398 m 100 165.762 l S Q +BT +9 0 0 9 97.134766 20.8 Tm +/f-0-0 1 Tf +(8)Tj +ET +q 1 0 0 -1 0 200 cm +134.16 160.398 m 134.16 165.762 l S Q +BT +9 0 0 9 128.429531 20.8 Tm +/f-0-0 1 Tf +(12)Tj +ET +q 1 0 0 -1 0 200 cm +168.238 160.398 m 168.238 165.762 l S Q +BT +9 0 0 9 162.509531 20.8 Tm +/f-0-0 1 Tf +(16)Tj +ET +q 1 0 0 -1 0 200 cm +202.398 160.398 m 202.398 165.762 l S Q +BT +9 0 0 9 196.669531 20.8 Tm +/f-0-0 1 Tf +(20)Tj +ET +q 1 0 0 -1 0 200 cm +236.559 160.398 m 236.559 165.762 l S Q +BT +9 0 0 9 230.829531 20.8 Tm +/f-0-0 1 Tf +(24)Tj +ET +q 1 0 0 -1 0 200 cm +270.641 160.398 m 270.641 165.762 l S Q +BT +9 0 0 9 264.909531 20.8 Tm +/f-0-0 1 Tf +(28)Tj +ET +q 1 0 0 -1 0 200 cm +304.801 160.398 m 304.801 165.762 l S Q +BT +9 0 0 9 299.069531 20.8 Tm +/f-0-0 1 Tf +(32)Tj +ET +q 1 0 0 -1 0 200 cm +48.801 10.16 m 48.801 160.398 l 304.801 160.398 l S Q +BT +-0.000000000000001653 9 -9 -0.000000000000001653 10.56 96.078398 Tm +/f-0-0 1 Tf +[(Time )-3([s])]TJ +9 0 0 9 148.094922 4.72 Tm +[(No)18(. of nodes)]TJ +-6.517214 19.075556 Td +[(Discovery with)-3(out cache)]TJ +ET +3.2 w +q 1 0 0 -1 0 200 cm +58.879 20.879 m 84.398 20.879 l 48.801 159.441 m 51.359 156.961 l 54 154.879 + l 56.559 153.68 l 59.121 153.84 l 61.762 154.719 l 64.32 155.441 l 66.879 + 154.879 l 69.52 152.961 l 72.078 150.801 l 74.641 149.359 l 77.281 149.441 + l 79.84 150.238 l 82.398 151.039 l 85.039 150.961 l 87.602 150.32 l 90.16 + 149.602 l 92.719 149.52 l 95.359 150.078 l 97.922 150.801 l 100.48 151.121 + l 103.121 150.719 l 105.68 149.68 l 108.238 148 l 110.879 145.84 l 113.441 + 143.68 l 116 142.238 l 118.641 142 l 121.199 142.801 l 123.762 143.922 +l 126.398 144.559 l 128.961 144.32 l 131.52 143.602 l 134.16 142.801 l 136.719 + 142.16 l 139.281 141.762 l 141.922 141.281 l 144.48 140.641 l 147.039 139.762 + l 149.68 138.559 l 152.238 137.199 l 154.801 135.68 l 157.441 134.32 l +160 133.52 l 162.559 133.52 l 165.199 133.922 l 167.762 134.398 l 170.32 + 134.559 l 172.961 134.32 l 175.52 133.441 l 178.078 131.922 l 180.641 129.84 + l 183.281 127.68 l 185.84 125.762 l 188.398 124.32 l 191.039 122.801 l +193.602 120.559 l 196.16 117.121 l 198.801 113.199 l 201.359 109.68 l 203.922 + 107.441 l 206.559 106.641 l 209.121 107.039 l 211.68 108.16 l 214.32 109.441 + l 216.879 110.078 l 219.441 109.441 l 222.078 106.801 l 224.641 103.281 + l 227.199 100.078 l 229.84 98.398 l 232.398 98 l 234.961 98 l 237.602 97.359 + l 240.16 95.84 l 242.719 94.078 l 245.359 92.641 l 247.922 91.84 l 250.48 + 90.961 l 253.121 89.121 l 255.68 85.68 l 258.238 81.039 l 260.879 76.398 + l 263.441 72.719 l 266 70.48 l 268.559 69.52 l 271.199 69.441 l 273.762 + 69.84 l 276.32 69.762 l 278.961 68 l 281.52 63.922 l 284.078 58.48 l 286.719 + 53.359 l 289.281 50.32 l 291.84 48.961 l 294.48 47.68 l 297.039 44.961 +l 299.602 40.16 l 302.238 34.961 l 304.801 31.039 l S Q +BT +9 0 0 9 89.44 165.68 Tm +/f-0-0 1 Tf +[(Discovery with)-3( cache)]TJ +ET +[ 4 6.4] 0 d +q 1 0 0 -1 0 200 cm +58.879 31.602 m 84.398 31.602 l 48.801 160.32 m 51.359 160.398 l 54 160.398 + l 56.559 160.32 l 59.121 160.16 l 61.762 159.84 l 64.32 159.602 l 66.879 + 159.441 l 74.641 159.441 l 77.281 159.359 l 82.398 158.719 l 85.039 158.238 + l 87.602 157.84 l 90.16 157.68 l 92.719 158 l 95.359 158.641 l 97.922 159.199 + l 100.48 159.441 l 103.121 159.121 l 105.68 158.398 l 108.238 157.84 l +110.879 157.52 l 113.441 157.602 l 116 157.762 l 118.641 157.84 l 121.199 + 157.922 l 123.762 157.84 l 126.398 157.762 l 128.961 157.602 l 131.52 157.602 + l 134.16 157.762 l 136.719 158.32 l 139.281 158.801 l 141.922 158.801 l + 144.48 157.922 l 147.039 156.641 l 149.68 155.52 l 152.238 155.359 l 154.801 + 156.32 l 157.441 157.68 l 160 158.719 l 162.559 158.879 l 165.199 158.559 + l 167.762 157.922 l 170.32 157.359 l 172.961 157.039 l 175.52 156.879 l + 178.078 157.039 l 180.641 157.441 l 183.281 157.762 l 185.84 157.762 l +188.398 157.359 l 191.039 156.801 l 193.602 156.16 l 196.16 155.68 l 198.801 + 155.441 l 201.359 155.281 l 203.922 155.359 l 206.559 155.52 l 209.121 +155.84 l 211.68 156.238 l 214.32 156.719 l 216.879 157.039 l 219.441 156.961 + l 222.078 156.48 l 224.641 155.762 l 227.199 155.281 l 229.84 155.441 l + 232.398 156 l 234.961 156.641 l 237.602 157.039 l 240.16 157.039 l 242.719 + 156.641 l 245.359 156.078 l 247.922 155.281 l 250.48 154.641 l 253.121 +154.398 l 255.68 154.801 l 258.238 155.52 l 260.879 156.078 l 263.441 156 + l 268.559 154.719 l 271.199 154.48 l 273.762 154.879 l 276.32 155.602 l + 278.961 156.078 l 281.52 155.922 l 284.078 155.199 l 286.719 154.16 l 289.281 + 152.801 l 291.84 151.68 l 294.48 151.039 l 297.039 151.281 l 299.602 152.48 + l 302.238 154 l 304.801 155.281 l S Q +0.8 w +[] 0.0 d +q 1 0 0 -1 0 200 cm +48.801 10.16 m 48.801 160.398 l 304.801 160.398 l S Q +Q Q +showpage +%%Trailer +end restore +%%EOF diff --git a/figures/trans.eps b/figures/trans.eps @@ -0,0 +1,430 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Creator: cairo 1.13.1 (http://cairographics.org) +%%CreationDate: Mon Mar 23 01:01:10 2015 +%%Pages: 1 +%%DocumentData: Clean7Bit +%%LanguageLevel: 2 +%%BoundingBox: 3 2 310 194 +%%EndComments +%%BeginProlog +save +50 dict begin +/q { gsave } bind def +/Q { grestore } bind def +/cm { 6 array astore concat } bind def +/w { setlinewidth } bind def +/J { setlinecap } bind def +/j { setlinejoin } bind def +/M { setmiterlimit } bind def +/d { setdash } bind def +/m { moveto } bind def +/l { lineto } bind def +/c { curveto } bind def +/h { closepath } bind def +/re { exch dup neg 3 1 roll 5 3 roll moveto 0 rlineto + 0 exch rlineto 0 rlineto closepath } bind def +/S { stroke } bind def +/f { fill } bind def +/f* { eofill } bind def +/n { newpath } bind def +/W { clip } bind def +/W* { eoclip } bind def +/BT { } bind def +/ET { } bind def +/pdfmark where { pop globaldict /?pdfmark /exec load put } + { globaldict begin /?pdfmark /pop load def /pdfmark + /cleartomark load def end } ifelse +/BDC { mark 3 1 roll /BDC pdfmark } bind def +/EMC { mark /EMC pdfmark } bind def +/cairo_store_point { /cairo_point_y exch def /cairo_point_x exch def } def +/Tj { show currentpoint cairo_store_point } bind def +/TJ { + { + dup + type /stringtype eq + { show } { -0.001 mul 0 cairo_font_matrix dtransform rmoveto } ifelse + } forall + currentpoint cairo_store_point +} bind def +/cairo_selectfont { cairo_font_matrix aload pop pop pop 0 0 6 array astore + cairo_font exch selectfont cairo_point_x cairo_point_y moveto } bind def +/Tf { pop /cairo_font exch def /cairo_font_matrix where + { pop cairo_selectfont } if } bind def +/Td { matrix translate cairo_font_matrix matrix concatmatrix dup + /cairo_font_matrix exch def dup 4 get exch 5 get cairo_store_point + /cairo_font where { pop cairo_selectfont } if } bind def +/Tm { 2 copy 8 2 roll 6 array astore /cairo_font_matrix exch def + cairo_store_point /cairo_font where { pop cairo_selectfont } if } bind def +/g { setgray } bind def +/rg { setrgbcolor } bind def +/d1 { setcachedevice } bind def +%%EndProlog +11 dict begin +/FontType 42 def +/FontName /DejaVuSerif def +/PaintType 0 def +/FontMatrix [ 1 0 0 1 0 0 ] def +/FontBBox [ 0 0 0 0 ] def +/Encoding 256 array def +0 1 255 { Encoding exch /.notdef put } for +Encoding 32 /space put +Encoding 46 /period put +Encoding 48 /zero put +Encoding 49 /one put +Encoding 50 /two put +Encoding 52 /four put +Encoding 53 /five put +Encoding 54 /six put +Encoding 56 /eight put +Encoding 76 /L put +Encoding 84 /T put +Encoding 91 /bracketleft put +Encoding 93 /bracketright put +Encoding 101 /e put +Encoding 103 /g put +Encoding 105 /i put +Encoding 108 /l put +Encoding 109 /m put +Encoding 110 /n put +Encoding 111 /o put +Encoding 115 /s put +/CharStrings 22 dict dup begin +/.notdef 0 def +/zero 1 def +/two 2 def +/four 3 def +/six 4 def +/eight 5 def +/one 6 def +/five 7 def +/T 8 def +/i 9 def +/m 10 def +/e 11 def +/space 12 def +/bracketleft 13 def +/s 14 def +/bracketright 15 def +/L 16 def +/o 17 def +/g 18 def +/l 19 def +/n 20 def +/period 21 def +end readonly def +/sfnts [ +<000100000009008000030010637674208f33abf400000ed0000001946670676de780f1c40000 +10640000008b676c79668a726c480000009c00000e34686561640747fea8000010f000000036 +686865610eb708830000112800000024686d7478630a09c30000114c000000586c6f63610000 +a974000011a40000005c6d61787004740533000012000000002070726570757906f600001220 +0000055e00020066fe96046605a400030007001a400c04c70006c70108055d0204002fc4d4ec +310010d4ecd4ec301311211125211121660400fc73031bfce5fe96070ef8f272062900020087 +ffe3048f05f0000b00170023401300650c066512690c60180306151409060f0b1810f4ecf4ec +310010e4f4ec10ee30253212111002232202111012172200111000333200111000028b999898 +9999989899f3feef0111f3f40110fef0460150015301540150feb0feacfeadfeb0630198016e +016f0198fe68fe91fe92fe6800000001008b0000044e05f0001c004d40210c14000f0d007402 +641a6505690d7711140d0c17000a011706080e0a1001120b1d10f4c4d4ecd4ec10ee11393939 +31002feef6eefeee10c411393930400b460a460b460c4614461505015d0123113e0133320415 +1401060701213533112135013e013534262322060106706bd968e9010efece180cfe87026f75 +fc3d01c596809d8a8f9c0471010a393ce2c2dbfecf170cfe87b8fea46d01c496fb8a97aa8e00 +0002003f000004b005f000020011009f40250264090a0901640a0a094d010a0c00730e071005 +730a69030208040600110d030f0b08021210f4d43cc4c4fc3cc4113931002fe4fc3cd43cec32 +1139304b5358071004ed071005ed5922b22f0901015db62009200d200e035d014bb00b544bb0 +0c545b4bb00d545b4bb00f545b58bd0012ffc00001001200120040381137385940180b011a01 +380149010406021602280a3602380a4702480a075d005d011109012135331121350133112115 +21113302cbfe0203b6fd58f0fd74028ec6011dfee3f001fa031afce6fe066a01256d03f4fc0a +6bfedb0000020089ffe3049605f0000b0025006340220c0006650f0065151f6c1e7923651b69 +156026200a1e16030612150c060905180b2610f4ececf4ecf4ec310010e4f4ecfcec10eed6ee +1139304025090c090d11041005100610071108130c130d100e100f10101111290c290d4e1f4e +204e21125d253236353426232206151416033e01333200151400232200111000213216171523 +2e01232202029e8d98988d8f9698b944ac6cdf0103fee9e9fdfef0014201254fae5b710c826e +c2be46cfc2c2cfc8bdc7d602f04b4afef4e8e3feef0179015e018801ae1e1ef6656afeda0000 +00030089ffe3048d05f0000b0017002f003e4022241803651509651e0f652a691e603024180c +1205270c052d00061b15060627210b3010f4c4ecf4ecd4ec10ee113939310010e4f4ec10eed6 +ee393930013426232206151416333236033426232206151416333236071e0115140423222435 +3436372e0135343633321615140603ba9f90909f9f90909f298a7c7b8b8b7b7c8a6caabefef6 +f8f7fef5beab97a1f8d9d9f8a10198a0b1b1a0a1b1b1037688989888899898c917cd9fd2e3e3 +d29fcd171baf88b4cfcfb488af00000100fa000003f405f0000a0078401c0464050605036406 +054d03060401050669080173000907110400020b10d4c4c4fcc431002fec32f4c41139113930 +4b53580704ed071004ed5922014bb00a5458bd000b00400001000b000bffc038113738594009 +200020012f092f0a045d014bb00b5458bd000bffc00001000b000b0040381137385921352111 +0535253311211501230104fed3016c8a01046a04dac383ecfa7a6a000000000100aeffe30479 +05d5001f00ad402503061d781a650610740f651465060c017700620c60201d11020a1e001706 +091e110a0f022010f4ecc4d4ecc410ee1139310010e4f4ec10c6eefeee10fee4123930014bb0 +09544bb00b545b4bb00f545b58bd0020ffc000010020002000403811373859014bb012544bb0 +13545b58bd00200040000100200020ffc0381137385940260f030f040f050f060f070f080f19 +0f1a0f1b0f1c0f1d0f1e0c0f000f011f001f012f002f01065d005d011521113e013332001514 +002122262711331e013332363534262322060723110406fd54348b56f20118fee5ff0067d871 +7109a3939eaaa99f5a89355605d5a4fe542424fef4e8edfef7323301228e96d0c3c2cf404302 +ee00000100140000054205d5000f007b401b09050b036f07620d016f000a0f08040f060e2408 +0c11002406021010d4c4e4fcc4e410ee10ee31002fee32f4fe3cc43230014bb0095458bd0010 +0040000100100010ffc03811373859b21f11015d014bb00b544bb00c545b58bd0010ffc00001 +0010001000403811373859400b2f1160118f11a011bf11055d21353311211523112111233521 +1133150187bffe497b052e7bfe49bf6a04f4e90160fea0e9fb0c6a0000000002004a00000260 +05e3000b0015004940170309127a149c100c7a0e0003060d2c0c27130f2c11301610f4e432fc +e4d4ec31002fec32fcecd4cc30b28f1701015d014bb0155458bd0016ffc00001001600160040 +381137385913343633321615140623222613331521353311233521c7432f2e43422f2f43ebae +fdeab0b0016805712e44442e2f4242fb286a6a03526b0001004a0000075e0444003000a94041 +201a130d04062b0003071d108503277a299c252118140b05077a2e038c2316090019130a3d0c +222c20082c0c27063f173d1927152c133f282c2a2027242c26303110f4e4ec32e4f4e4fce4f4 +ece410e410e411123931002f3c3cee32ee1732feee10ee32111739173930400b3f325f326f32 +9032b03205015d014bb0155458bd0031ffc00001003100310040381137385940132f0a2f0b2f +172f18cf0acf0bcf17cf18c032095d013e013332161511331521353311342623220615113315 +2135331134262322061511331521353311233521153e01333216042535a56ea7a4a6fe02a060 +6f7b81a0fe08a0606f7b81a0fe02a6b00168339e647ca603587577cfd1fdc66a6a0225a38aba +b2fe1a6a6a022c9f87bab2fe1a6a6a035469bd6a707b00020066ffe3045604440014001b004e +401e0208157a000899058f0c188f009b128c0c601c0809151a001b011a0f2a1c10f4ec32d4ec +d4cc310010e4fcecec10fee410ee1239304012201d401d7f1d03cf00cf01cf02cf15cf1b055d +015d012115141633323637330e01232200353400333200072e01232206070456fce7a29e799b +1f942cedc1e9fee50116e2f10102d40691887f9210020008d7db7f7dafb00133fefc0134fed7 +b1babdbeb9000000000100b0fef2028106140007002440120473060273007108060502010303 +1200020810f4ec10c0c0c0c0310010fcecd4ec301321152111211521b001d1feee0112fe2f06 +146af9b26a00000000010073ffe303b20444002900d9404123220224213e0c0b1e1f021d203e +0b0c0b4d0b0c2021041601a100a0058f2716a115a01a8f128c27602a200b0c211d08172d151d +3e0f0827154624022d0f00452a10f4c4ecd4e4ec10ee10ee111239393939310010e4fcecf4ec +10eef6ee111739304b535807100eed111739070eed1117395922b2202b01015d4058271f2720 +2721272227235a0a5a0b5a0c5a0d5a1f5a205a215a225823861f8620862186228623961f9620 +962196229623a61fa620a621a622a6231d402b7f2baf14af15af16af17af18af19bf14bf15bf +16bf17bf18bf190e5d005d3735331e013332363534262f012e013534363332161715232e0123 +22061514161f011e01151406232226736a048d8a7c825f9985897bd6bd54ba636a0488757477 +5a87929785e7cb67c43bf877765d594656312d2c846692a62c2ae86774525243512a2d2f8d6f +97ad2c0000000001009efef2026f06140007001f400f03730105730071080602080012040810 +d4ec123939310010fcecd4ec300111213521112135026ffe2f0112feee0614f8de6a064e6a00 +0000000100710000051f05d5000d0030401a0b0907036f05620980016f000624080a0f0c0400 +24081102210e10f4ece432d4ec10e431002feeeef6ee3210c430333533112335211523112135 +331171bebe0247be02aa7b6a05006b6bfb11fafe8b0000020066ffe3046a0444000b0017002b +4013008f0c068f128c0c6018031a1544091a0f2a1810f4ecf4ec310010e4fcec10ee30b42019 +6f1902015d253236353426232206151416172200353400333200151400026894979794949798 +93e8fee60119e9e90119fee746eae4e4e9e9e4e4ea630133fefe0132fecefefefecd00000002 +0066fe3904e30444001f002c006640332c000f0113101c200329007a1d299413089e070c8f04 +2394198c1360049d1d9c2d092d071e2c201c0f270035261a0737162a2d10f4e4ecf4ec3232e4 +10ee310010ecece4fcec10eedee610ee10ee1117391239391239304009002e102e7f2eb02e04 +015d011114062322262735331e013332363d010e012322023534123332161735211501342623 +2206151416333236350433fce969c0586012867da29736a77bc4f9f8c57ba7360168fe98938c +8e91918e8c9303bcfc5be5f92626df6860b7c48f645f0137fafa01365f64a66bfe8cbfcae0dd +dce2c9c000000001003b000002520614000900404012067a087104007a02012c002707032c05 +300a10f4e432fce431002fec32fcec30b28f0b01015d014bb0155458bd000affc00001000a00 +0a004038113738592533152135331123352101a4aefde9b1b101696a6a6a05406a000001004a +000004ee0444001d0070402e070d141a04030117850a037a059c1b120e03017a0a8c1000113d +131c2c060f2c13270d3a042c1a0627002c02301e10f4e4ec32e4f4ece410e410e431002f3cee +ee1732fcee10ee1112173930b62f1f7f1fb01f03015d014bb0155458bd001effc00001001e00 +1e0040381137385933353311233521153e013332161511331521353311342623220615113315 +54a6b0016833a36cb0a6a4fe049f60798086a06a03526bbd6c6ecad6fdc66a6a0200c391bbb3 +fe1a6a000000000100c1ffe301cb00ee000b0038b40d0600000c10d4fcc44bb0135158b40a02 +0008043c3c103c3c593100b4036109600c10f4ec4bb0135158b40501030b073c3c103c3c5930 +373436333216151406232226c14c39374e4e37394c68384e4e38374e4d00010a0073000200b8 +00cb00cb00d30002004c006a0071008700a0000200e5007b00cb00cb00c10408040804080002 +00d9050200b800d300b80129006a000200020002012f0000000200be0073003300b800e500cb +0066000200a000620002000200fa03cd03cd03cd039a03cd027700020350039a035000000002 +00a000b8033b040403cd040403cd04040066000200cb003d00ba00aa0066000205cd00960000 +005200d700d700420073004a00bc00d9018300a401d5007d008d007304000000001d010a05d5 +006a006a006205d505d505d505f0005c00020002006a006a006a05d5061400a0006a010a00bc +00cb00a40002006a006a01290152036003660158007b000201aa0348006a0085006a04600460 +0427042704270444006a00020062000200020002027b0073006a00020002000200cd025c0229 +042701aa005c006a006a00cd00a000aa003d05cd006600d7004800d700020066000203e900a0 +030c0000001905c1004a074a060c0106077d00540002007b0333019a061d0060007d0354006a +004e0002008d004e01d7007300001400b6060504030201002c2010b002254964b040515820c8 +59212d2cb002254964b040515820c859212d2c20100720b00050b00d7920b8ffff5058041b05 +59b0051cb0032508b0042523e120b00050b00d7920b8ffff5058041b0559b0051cb0032508e1 +2d2c4b505820b0c9454459212d2cb002254560442d2c4b5358b00225b0022545445921212d2c +45442d00000100000002570a14959ccc5f0f3cf5001f080000000000d0672e4300000000d067 +2e43f9d8fd3a0d6f08e000000008000000010000000000010000076dfe1d00000ddff9d8fc70 +0d6f00010000000000000000000000000000001604cd0066051700870517008b0517003f0517 +008905170089051700fa051700ae05560014028f004a0796004a04bc0066028b0000031f00b0 +041b0073031f009e0550007104d10066051f0066028f003b0527004a028b00c1000000000000 +0044000000c80000017800000260000003400000040c000004b4000005c80000067c0000070c +0000083c000008ec000008ec0000093800000a8c00000ad400000b3400000bb400000ca00000 +0d0800000dd000000e340001000000160209002b0098000800020010009900070000040b01f3 +00080004b8028040e0c7fe03c61303c5c42405c56403c54004c42403c30d03c2c12705c26403 +c12703c05d03bf7d03bc0b03bb0b03bab91405ba3203b91403b83203b7fe03b6fe03b5fe03b3 +fe03b2fe03b1b04705b1fa03b04703affe03ae7d03adfe03ac0e03abaa0c05ab1403aa0c03a9 +3203a86403a71e03a43203a3a26405a3fe03a26403a1960e05a12503a0780a05a025039f4b03 +9e10039d2e039c881e059cfe039b9a10059b1d039a100399980e0599250398780a05980e0398 +400497960e05971403978004960e039640049525039484300594fe039392130593250392910d +0592130392b8014040090491900a05910d0391b80100404904900a0390c0048f6f7d058fbb03 +8e810b058e11038e40048d810b058d3a038c8bbb058cfe038b8a5d058bbb038b80048a892505 +8a5d038a400489881e0589250388871105881e0388b8ffc040ff048711038584300585640384 +3003831603829603810b038064640580fe037f6c10057f19037e7d0e057e32037d0e037c7b0f +057c13037b0f037a9603791103780a037776200577fa0376751c05762003751c03746c100574 +1e0373fe0372fe0371700d0571fe03700d037040046f7d036e6d3e056e6b036d3e036c6b0c05 +6c10036c80046b0c036b40046a6464056afa036968bb0569fe0368675d0568bb036880046766 +2505675d036740046625036564640565fa0364640363150362fe0361fe03605f2e0560fe035f +2e035efe035dfe035c4b035b7d035afe0359440358fe0357fe0356bb0355fe03536403521403 +513203504f0f05507d034f0f034e414042034c0b034a64034922080549960348320347031005 +47130346120345020a0545190344431305446b034342100543130342410b0542100341400905 +410b0340090340b8ffc04053043f96033e042d053e4d033d3c14053d4b033c3b0a053c14033c +40043b0a033a3912053a5d0339381105391203381103370d0336fe033534140535fe03343313 +0534140333320a0533130332310905320a0332b8ffc040ff04310903302f18053044032f2e15 +052f18032fc0042e1e0a052e15032e80042d0964052d96032c2b14052c4b032b2208052b1403 +2b40042a020a052a64032928300529410328042d0528300327042d0527fe03263a03250d1805 +255d03242312052453032322080523120323400422080321201805215d03201f110520180320 +c0041f1e0a051f11031f80041e0a031e40041d23031c0f031b24031a1930051a530319042d05 +19300318fe0317020a0517fe0316100315141405156b03141313051414031440041313031204 +2d0512bb031103100511fe03100310051042030f0964050f96030e042d050efe030d020a050d +18030d40040cfe030b020a050b40386b030a0964050a7d030964030807110508140307110306 +053205067d0305042d0505320304031005042d03031003020a0301530300fe0301b80164858d +012b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b002b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b +2b2b2b2b2b2b2b2b2b1d000000> +] def +/f-0-0 currentdict end definefont pop +%%Page: 1 1 +%%BeginPageSetup +%%PageBoundingBox: 3 2 310 194 +%%EndPageSetup +q 3 2 307 192 rectclip q +0 g +0.8 w +1 J +1 j +[] 0.0 d +4 M q 1 0 0 -1 0 200 cm +43.762 160.398 m 38.398 160.398 l S Q +BT +9 0 0 9 27.629531 36.88 Tm +/f-0-0 1 Tf +(0)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 138.961 m 38.398 138.961 l S Q +BT +9 0 0 9 27.629531 58.32 Tm +/f-0-0 1 Tf +(2)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 117.441 m 38.398 117.441 l S Q +BT +9 0 0 9 27.629531 79.84 Tm +/f-0-0 1 Tf +(4)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 96 m 38.398 96 l S Q +BT +9 0 0 9 27.629531 101.28 Tm +/f-0-0 1 Tf +(6)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 74.559 m 38.398 74.559 l S Q +BT +9 0 0 9 27.629531 122.72 Tm +/f-0-0 1 Tf +(8)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 53.121 m 38.398 53.121 l S Q +BT +9 0 0 9 21.899063 144.16 Tm +/f-0-0 1 Tf +(10)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 31.602 m 38.398 31.602 l S Q +BT +9 0 0 9 21.899063 165.68 Tm +/f-0-0 1 Tf +(12)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 10.16 m 38.398 10.16 l S Q +BT +9 0 0 9 21.899063 187.12 Tm +/f-0-0 1 Tf +(14)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 160.398 m 43.762 165.762 l S Q +BT +9 0 0 9 40.894766 20.8 Tm +/f-0-0 1 Tf +(0)Tj +ET +q 1 0 0 -1 0 200 cm +96 160.398 m 96 165.762 l S Q +BT +9 0 0 9 93.134766 20.8 Tm +/f-0-0 1 Tf +(5)Tj +ET +q 1 0 0 -1 0 200 cm +148.16 160.398 m 148.16 165.762 l S Q +BT +9 0 0 9 142.429531 20.8 Tm +/f-0-0 1 Tf +(10)Tj +ET +q 1 0 0 -1 0 200 cm +200.398 160.398 m 200.398 165.762 l S Q +BT +9 0 0 9 194.669531 20.8 Tm +/f-0-0 1 Tf +(15)Tj +ET +q 1 0 0 -1 0 200 cm +252.559 160.398 m 252.559 165.762 l S Q +BT +9 0 0 9 246.829531 20.8 Tm +/f-0-0 1 Tf +(20)Tj +ET +q 1 0 0 -1 0 200 cm +304.801 160.398 m 304.801 165.762 l S Q +BT +9 0 0 9 299.069531 20.8 Tm +/f-0-0 1 Tf +(25)Tj +ET +q 1 0 0 -1 0 200 cm +43.762 10.16 m 43.762 160.398 l 304.801 160.398 l S Q +BT +-0.000000000000001653 9 -9 -0.000000000000001653 10.56 96.078398 Tm +/f-0-0 1 Tf +[(Time )-3([s])]TJ +9 0 0 9 147.389414 4.72 Tm +[(Log line n)-3(o)18(.)]TJ +ET +2.4 w +[ 4 6.4] 0 d +q 1 0 0 -1 0 200 cm +54.238 44.398 m 283.922 44.398 l S Q +3.2 w +[] 0.0 d +q 1 0 0 -1 0 200 cm +54.238 84 m 56.559 76.719 l 58.879 70.48 l 61.199 66.48 l 63.52 65.762 +l 65.84 69.441 l 68.16 76.32 l 70.48 83.281 l 72.801 87.121 l 75.121 84.559 + l 77.441 73.602 l 79.762 57.68 l 82.078 41.199 l 84.398 28.879 l 86.719 + 25.121 l 89.039 30.32 l 91.359 41.199 l 93.68 54.078 l 96 65.52 l 98.32 + 72.719 l 100.641 76.238 l 102.961 77.359 l 105.281 77.359 l 107.602 77.68 + l 109.922 78.801 l 112.238 80.238 l 114.559 81.84 l 116.879 83.039 l 119.199 + 83.68 l 121.52 83.84 l 123.84 83.68 l 126.16 83.359 l 128.48 83.121 l 130.801 + 83.121 l 133.121 83.199 l 135.441 83.52 l 137.762 84 l 140.078 84.641 l + 142.398 85.281 l 144.719 85.84 l 147.039 86.238 l 149.359 86.32 l 151.68 + 85.922 l 154 84.961 l 156.32 83.281 l 158.641 80.801 l 160.961 77.441 l + 163.281 73.68 l 165.602 70.078 l 167.922 67.121 l 170.238 65.359 l 172.559 + 64.801 l 174.879 65.199 l 177.199 66.16 l 179.52 67.359 l 181.84 68.398 + l 184.16 68.879 l 186.48 68.559 l 188.801 66.961 l 191.121 63.84 l 193.441 + 59.441 l 195.762 54.559 l 198.078 50 l 200.398 46.641 l 202.719 45.121 +l 205.039 45.281 l 207.359 46.48 l 209.68 48.48 l 212 50.719 l 214.32 52.801 + l 216.641 54.16 l 218.961 54.48 l 221.281 53.281 l 223.602 50.32 l 225.922 + 45.84 l 228.238 40.641 l 230.559 35.281 l 232.879 30.238 l 235.199 25.922 + l 237.52 22.238 l 239.84 19.121 l 242.16 16.641 l 244.48 14.719 l 246.801 + 13.281 l 249.121 12.32 l 251.441 11.922 l 253.762 11.84 l 256.078 12.238 + l 258.398 12.961 l 260.719 14 l 263.039 15.441 l 265.359 17.039 l 267.68 + 18.961 l 270 21.121 l 272.32 23.441 l 274.641 25.922 l 276.961 28.48 l +279.281 31.121 l 281.602 33.922 l 283.922 36.641 l S Q +0.8 w +q 1 0 0 -1 0 200 cm +43.762 10.16 m 43.762 160.398 l 304.801 160.398 l S Q +Q Q +showpage +%%Trailer +end restore +%%EOF diff --git a/llncs.cls b/llncs.cls @@ -0,0 +1,1208 @@ +% LLNCS DOCUMENT CLASS -- version 2.18 (27-Sep-2013) +% Springer Verlag LaTeX2e support for Lecture Notes in Computer Science +% +%% +%% \CharacterTable +%% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z +%% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z +%% Digits \0\1\2\3\4\5\6\7\8\9 +%% Exclamation \! Double quote \" Hash (number) \# +%% Dollar \$ Percent \% Ampersand \& +%% Acute accent \' Left paren \( Right paren \) +%% Asterisk \* Plus \+ Comma \, +%% Minus \- Point \. Solidus \/ +%% Colon \: Semicolon \; Less than \< +%% Equals \= Greater than \> Question mark \? +%% Commercial at \@ Left bracket \[ Backslash \\ +%% Right bracket \] Circumflex \^ Underscore \_ +%% Grave accent \` Left brace \{ Vertical bar \| +%% Right brace \} Tilde \~} +%% +\NeedsTeXFormat{LaTeX2e}[1995/12/01] +\ProvidesClass{llncs}[2013/09/27 v2.18 +^^J LaTeX document class for Lecture Notes in Computer Science] +% Options +\let\if@envcntreset\iffalse +\DeclareOption{envcountreset}{\let\if@envcntreset\iftrue} +\DeclareOption{citeauthoryear}{\let\citeauthoryear=Y} +\DeclareOption{oribibl}{\let\oribibl=Y} +\let\if@custvec\iftrue +\DeclareOption{orivec}{\let\if@custvec\iffalse} +\let\if@envcntsame\iffalse +\DeclareOption{envcountsame}{\let\if@envcntsame\iftrue} +\let\if@envcntsect\iffalse +\DeclareOption{envcountsect}{\let\if@envcntsect\iftrue} +\let\if@runhead\iffalse +\DeclareOption{runningheads}{\let\if@runhead\iftrue} + +\let\if@openright\iftrue +\let\if@openbib\iffalse +\DeclareOption{openbib}{\let\if@openbib\iftrue} + +% languages +\let\switcht@@therlang\relax +\def\ds@deutsch{\def\switcht@@therlang{\switcht@deutsch}} +\def\ds@francais{\def\switcht@@therlang{\switcht@francais}} + +\DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}} + +\ProcessOptions + +\LoadClass[twoside]{article} +\RequirePackage{multicol} % needed for the list of participants, index +\RequirePackage{aliascnt} + +\setlength{\textwidth}{12.2cm} +\setlength{\textheight}{19.3cm} +\renewcommand\@pnumwidth{2em} +\renewcommand\@tocrmarg{3.5em} +% +\def\@dottedtocline#1#2#3#4#5{% + \ifnum #1>\c@tocdepth \else + \vskip \z@ \@plus.2\p@ + {\leftskip #2\relax \rightskip \@tocrmarg \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \parindent #2\relax\@afterindenttrue + \interlinepenalty\@M + \leavevmode + \@tempdima #3\relax + \advance\leftskip \@tempdima \null\nobreak\hskip -\leftskip + {#4}\nobreak + \leaders\hbox{$\m@th + \mkern \@dotsep mu\hbox{.}\mkern \@dotsep + mu$}\hfill + \nobreak + \hb@xt@\@pnumwidth{\hfil\normalfont \normalcolor #5}% + \par}% + \fi} +% +\def\switcht@albion{% +\def\abstractname{Abstract.} +\def\ackname{Acknowledgement.} +\def\andname{and} +\def\lastandname{\unskip, and} +\def\appendixname{Appendix} +\def\chaptername{Chapter} +\def\claimname{Claim} +\def\conjecturename{Conjecture} +\def\contentsname{Table of Contents} +\def\corollaryname{Corollary} +\def\definitionname{Definition} +\def\examplename{Example} +\def\exercisename{Exercise} +\def\figurename{Fig.} +\def\keywordname{{\bf Keywords:}} +\def\indexname{Index} +\def\lemmaname{Lemma} +\def\contriblistname{List of Contributors} +\def\listfigurename{List of Figures} +\def\listtablename{List of Tables} +\def\mailname{{\it Correspondence to\/}:} +\def\noteaddname{Note added in proof} +\def\notename{Note} +\def\partname{Part} +\def\problemname{Problem} +\def\proofname{Proof} +\def\propertyname{Property} +\def\propositionname{Proposition} +\def\questionname{Question} +\def\remarkname{Remark} +\def\seename{see} +\def\solutionname{Solution} +\def\subclassname{{\it Subject Classifications\/}:} +\def\tablename{Table} +\def\theoremname{Theorem}} +\switcht@albion +% Names of theorem like environments are already defined +% but must be translated if another language is chosen +% +% French section +\def\switcht@francais{%\typeout{On parle francais.}% + \def\abstractname{R\'esum\'e.}% + \def\ackname{Remerciements.}% + \def\andname{et}% + \def\lastandname{ et}% + \def\appendixname{Appendice} + \def\chaptername{Chapitre}% + \def\claimname{Pr\'etention}% + \def\conjecturename{Hypoth\`ese}% + \def\contentsname{Table des mati\`eres}% + \def\corollaryname{Corollaire}% + \def\definitionname{D\'efinition}% + \def\examplename{Exemple}% + \def\exercisename{Exercice}% + \def\figurename{Fig.}% + \def\keywordname{{\bf Mots-cl\'e:}} + \def\indexname{Index} + \def\lemmaname{Lemme}% + \def\contriblistname{Liste des contributeurs} + \def\listfigurename{Liste des figures}% + \def\listtablename{Liste des tables}% + \def\mailname{{\it Correspondence to\/}:} + \def\noteaddname{Note ajout\'ee \`a l'\'epreuve}% + \def\notename{Remarque}% + \def\partname{Partie}% + \def\problemname{Probl\`eme}% + \def\proofname{Preuve}% + \def\propertyname{Caract\'eristique}% +%\def\propositionname{Proposition}% + \def\questionname{Question}% + \def\remarkname{Remarque}% + \def\seename{voir} + \def\solutionname{Solution}% + \def\subclassname{{\it Subject Classifications\/}:} + \def\tablename{Tableau}% + \def\theoremname{Th\'eor\`eme}% +} +% +% German section +\def\switcht@deutsch{%\typeout{Man spricht deutsch.}% + \def\abstractname{Zusammenfassung.}% + \def\ackname{Danksagung.}% + \def\andname{und}% + \def\lastandname{ und}% + \def\appendixname{Anhang}% + \def\chaptername{Kapitel}% + \def\claimname{Behauptung}% + \def\conjecturename{Hypothese}% + \def\contentsname{Inhaltsverzeichnis}% + \def\corollaryname{Korollar}% +%\def\definitionname{Definition}% + \def\examplename{Beispiel}% + \def\exercisename{\"Ubung}% + \def\figurename{Abb.}% + \def\keywordname{{\bf Schl\"usselw\"orter:}} + \def\indexname{Index} +%\def\lemmaname{Lemma}% + \def\contriblistname{Mitarbeiter} + \def\listfigurename{Abbildungsverzeichnis}% + \def\listtablename{Tabellenverzeichnis}% + \def\mailname{{\it Correspondence to\/}:} + \def\noteaddname{Nachtrag}% + \def\notename{Anmerkung}% + \def\partname{Teil}% +%\def\problemname{Problem}% + \def\proofname{Beweis}% + \def\propertyname{Eigenschaft}% +%\def\propositionname{Proposition}% + \def\questionname{Frage}% + \def\remarkname{Anmerkung}% + \def\seename{siehe} + \def\solutionname{L\"osung}% + \def\subclassname{{\it Subject Classifications\/}:} + \def\tablename{Tabelle}% +%\def\theoremname{Theorem}% +} + +% Ragged bottom for the actual page +\def\thisbottomragged{\def\@textbottom{\vskip\z@ plus.0001fil +\global\let\@textbottom\relax}} + +\renewcommand\small{% + \@setfontsize\small\@ixpt{11}% + \abovedisplayskip 8.5\p@ \@plus3\p@ \@minus4\p@ + \abovedisplayshortskip \z@ \@plus2\p@ + \belowdisplayshortskip 4\p@ \@plus2\p@ \@minus2\p@ + \def\@listi{\leftmargin\leftmargini + \parsep 0\p@ \@plus1\p@ \@minus\p@ + \topsep 8\p@ \@plus2\p@ \@minus4\p@ + \itemsep0\p@}% + \belowdisplayskip \abovedisplayskip +} + +\frenchspacing +\widowpenalty=10000 +\clubpenalty=10000 + +\setlength\oddsidemargin {63\p@} +\setlength\evensidemargin {63\p@} +\setlength\marginparwidth {90\p@} + +\setlength\headsep {16\p@} + +\setlength\footnotesep{7.7\p@} +\setlength\textfloatsep{8mm\@plus 2\p@ \@minus 4\p@} +\setlength\intextsep {8mm\@plus 2\p@ \@minus 2\p@} + +\setcounter{secnumdepth}{2} + +\newcounter {chapter} +\renewcommand\thechapter {\@arabic\c@chapter} + +\newif\if@mainmatter \@mainmattertrue +\newcommand\frontmatter{\cleardoublepage + \@mainmatterfalse\pagenumbering{Roman}} +\newcommand\mainmatter{\cleardoublepage + \@mainmattertrue\pagenumbering{arabic}} +\newcommand\backmatter{\if@openright\cleardoublepage\else\clearpage\fi + \@mainmatterfalse} + +\renewcommand\part{\cleardoublepage + \thispagestyle{empty}% + \if@twocolumn + \onecolumn + \@tempswatrue + \else + \@tempswafalse + \fi + \null\vfil + \secdef\@part\@spart} + +\def\@part[#1]#2{% + \ifnum \c@secnumdepth >-2\relax + \refstepcounter{part}% + \addcontentsline{toc}{part}{\thepart\hspace{1em}#1}% + \else + \addcontentsline{toc}{part}{#1}% + \fi + \markboth{}{}% + {\centering + \interlinepenalty \@M + \normalfont + \ifnum \c@secnumdepth >-2\relax + \huge\bfseries \partname~\thepart + \par + \vskip 20\p@ + \fi + \Huge \bfseries #2\par}% + \@endpart} +\def\@spart#1{% + {\centering + \interlinepenalty \@M + \normalfont + \Huge \bfseries #1\par}% + \@endpart} +\def\@endpart{\vfil\newpage + \if@twoside + \null + \thispagestyle{empty}% + \newpage + \fi + \if@tempswa + \twocolumn + \fi} + +\newcommand\chapter{\clearpage + \thispagestyle{empty}% + \global\@topnum\z@ + \@afterindentfalse + \secdef\@chapter\@schapter} +\def\@chapter[#1]#2{\ifnum \c@secnumdepth >\m@ne + \if@mainmatter + \refstepcounter{chapter}% + \typeout{\@chapapp\space\thechapter.}% + \addcontentsline{toc}{chapter}% + {\protect\numberline{\thechapter}#1}% + \else + \addcontentsline{toc}{chapter}{#1}% + \fi + \else + \addcontentsline{toc}{chapter}{#1}% + \fi + \chaptermark{#1}% + \addtocontents{lof}{\protect\addvspace{10\p@}}% + \addtocontents{lot}{\protect\addvspace{10\p@}}% + \if@twocolumn + \@topnewpage[\@makechapterhead{#2}]% + \else + \@makechapterhead{#2}% + \@afterheading + \fi} +\def\@makechapterhead#1{% +% \vspace*{50\p@}% + {\centering + \ifnum \c@secnumdepth >\m@ne + \if@mainmatter + \large\bfseries \@chapapp{} \thechapter + \par\nobreak + \vskip 20\p@ + \fi + \fi + \interlinepenalty\@M + \Large \bfseries #1\par\nobreak + \vskip 40\p@ + }} +\def\@schapter#1{\if@twocolumn + \@topnewpage[\@makeschapterhead{#1}]% + \else + \@makeschapterhead{#1}% + \@afterheading + \fi} +\def\@makeschapterhead#1{% +% \vspace*{50\p@}% + {\centering + \normalfont + \interlinepenalty\@M + \Large \bfseries #1\par\nobreak + \vskip 40\p@ + }} + +\renewcommand\section{\@startsection{section}{1}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {12\p@ \@plus 4\p@ \@minus 4\p@}% + {\normalfont\large\bfseries\boldmath + \rightskip=\z@ \@plus 8em\pretolerance=10000 }} +\renewcommand\subsection{\@startsection{subsection}{2}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {8\p@ \@plus 4\p@ \@minus 4\p@}% + {\normalfont\normalsize\bfseries\boldmath + \rightskip=\z@ \@plus 8em\pretolerance=10000 }} +\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {-0.5em \@plus -0.22em \@minus -0.1em}% + {\normalfont\normalsize\bfseries\boldmath}} +\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}% + {-12\p@ \@plus -4\p@ \@minus -4\p@}% + {-0.5em \@plus -0.22em \@minus -0.1em}% + {\normalfont\normalsize\itshape}} +\renewcommand\subparagraph[1]{\typeout{LLNCS warning: You should not use + \string\subparagraph\space with this class}\vskip0.5cm +You should not use \verb|\subparagraph| with this class.\vskip0.5cm} + +\DeclareMathSymbol{\Gamma}{\mathalpha}{letters}{"00} +\DeclareMathSymbol{\Delta}{\mathalpha}{letters}{"01} +\DeclareMathSymbol{\Theta}{\mathalpha}{letters}{"02} +\DeclareMathSymbol{\Lambda}{\mathalpha}{letters}{"03} +\DeclareMathSymbol{\Xi}{\mathalpha}{letters}{"04} +\DeclareMathSymbol{\Pi}{\mathalpha}{letters}{"05} +\DeclareMathSymbol{\Sigma}{\mathalpha}{letters}{"06} +\DeclareMathSymbol{\Upsilon}{\mathalpha}{letters}{"07} +\DeclareMathSymbol{\Phi}{\mathalpha}{letters}{"08} +\DeclareMathSymbol{\Psi}{\mathalpha}{letters}{"09} +\DeclareMathSymbol{\Omega}{\mathalpha}{letters}{"0A} + +\let\footnotesize\small + +\if@custvec +\def\vec#1{\mathchoice{\mbox{\boldmath$\displaystyle#1$}} +{\mbox{\boldmath$\textstyle#1$}} +{\mbox{\boldmath$\scriptstyle#1$}} +{\mbox{\boldmath$\scriptscriptstyle#1$}}} +\fi + +\def\squareforqed{\hbox{\rlap{$\sqcap$}$\sqcup$}} +\def\qed{\ifmmode\squareforqed\else{\unskip\nobreak\hfil +\penalty50\hskip1em\null\nobreak\hfil\squareforqed +\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi} + +\def\getsto{\mathrel{\mathchoice {\vcenter{\offinterlineskip +\halign{\hfil +$\displaystyle##$\hfil\cr\gets\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr\gets +\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr\gets +\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +\gets\cr\to\cr}}}}} +\def\lid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil +$\displaystyle##$\hfil\cr<\cr\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr<\cr +\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr<\cr +\noalign{\vskip1pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +<\cr +\noalign{\vskip0.9pt}=\cr}}}}} +\def\gid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil +$\displaystyle##$\hfil\cr>\cr\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr>\cr +\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr>\cr +\noalign{\vskip1pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +>\cr +\noalign{\vskip0.9pt}=\cr}}}}} +\def\grole{\mathrel{\mathchoice {\vcenter{\offinterlineskip +\halign{\hfil +$\displaystyle##$\hfil\cr>\cr\noalign{\vskip-1pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr +>\cr\noalign{\vskip-1pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr +>\cr\noalign{\vskip-0.8pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +>\cr\noalign{\vskip-0.3pt}<\cr}}}}} +\def\bbbr{{\rm I\!R}} %reelle Zahlen +\def\bbbm{{\rm I\!M}} +\def\bbbn{{\rm I\!N}} %natuerliche Zahlen +\def\bbbf{{\rm I\!F}} +\def\bbbh{{\rm I\!H}} +\def\bbbk{{\rm I\!K}} +\def\bbbp{{\rm I\!P}} +\def\bbbone{{\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} +{\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}} +\def\bbbc{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}}} +\def\bbbq{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm +Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}} +\def\bbbt{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm +T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}}} +\def\bbbs{{\mathchoice +{\setbox0=\hbox{$\displaystyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox +to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox +to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox +to0pt{\kern0.5\wd0\vrule height0.45\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.4\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox +to0pt{\kern0.55\wd0\vrule height0.45\ht0\hss}\box0}}}} +\def\bbbz{{\mathchoice {\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}} +{\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}} +{\hbox{$\mathsf\scriptstyle Z\kern-0.3em Z$}} +{\hbox{$\mathsf\scriptscriptstyle Z\kern-0.2em Z$}}}} + +\let\ts\, + +\setlength\leftmargini {17\p@} +\setlength\leftmargin {\leftmargini} +\setlength\leftmarginii {\leftmargini} +\setlength\leftmarginiii {\leftmargini} +\setlength\leftmarginiv {\leftmargini} +\setlength \labelsep {.5em} +\setlength \labelwidth{\leftmargini} +\addtolength\labelwidth{-\labelsep} + +\def\@listI{\leftmargin\leftmargini + \parsep 0\p@ \@plus1\p@ \@minus\p@ + \topsep 8\p@ \@plus2\p@ \@minus4\p@ + \itemsep0\p@} +\let\@listi\@listI +\@listi +\def\@listii {\leftmargin\leftmarginii + \labelwidth\leftmarginii + \advance\labelwidth-\labelsep + \topsep 0\p@ \@plus2\p@ \@minus\p@} +\def\@listiii{\leftmargin\leftmarginiii + \labelwidth\leftmarginiii + \advance\labelwidth-\labelsep + \topsep 0\p@ \@plus\p@\@minus\p@ + \parsep \z@ + \partopsep \p@ \@plus\z@ \@minus\p@} + +\renewcommand\labelitemi{\normalfont\bfseries --} +\renewcommand\labelitemii{$\m@th\bullet$} + +\setlength\arraycolsep{1.4\p@} +\setlength\tabcolsep{1.4\p@} + +\def\tableofcontents{\chapter*{\contentsname\@mkboth{{\contentsname}}% + {{\contentsname}}} + \def\authcount##1{\setcounter{auco}{##1}\setcounter{@auth}{1}} + \def\lastand{\ifnum\value{auco}=2\relax + \unskip{} \andname\ + \else + \unskip \lastandname\ + \fi}% + \def\and{\stepcounter{@auth}\relax + \ifnum\value{@auth}=\value{auco}% + \lastand + \else + \unskip, + \fi}% + \@starttoc{toc}\if@restonecol\twocolumn\fi} + +\def\l@part#1#2{\addpenalty{\@secpenalty}% + \addvspace{2em plus\p@}% % space above part line + \begingroup + \parindent \z@ + \rightskip \z@ plus 5em + \hrule\vskip5pt + \large % same size as for a contribution heading + \bfseries\boldmath % set line in boldface + \leavevmode % TeX command to enter horizontal mode. + #1\par + \vskip5pt + \hrule + \vskip1pt + \nobreak % Never break after part entry + \endgroup} + +\def\@dotsep{2} + +\let\phantomsection=\relax + +\def\hyperhrefextend{\ifx\hyper@anchor\@undefined\else +{}\fi} + +\def\addnumcontentsmark#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{\protect\numberline + {\thechapter}#3}{\thepage}\hyperhrefextend}}% +\def\addcontentsmark#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{#3}{\thepage}\hyperhrefextend}}% +\def\addcontentsmarkwop#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{#3}{0}\hyperhrefextend}}% + +\def\@adcmk[#1]{\ifcase #1 \or +\def\@gtempa{\addnumcontentsmark}% + \or \def\@gtempa{\addcontentsmark}% + \or \def\@gtempa{\addcontentsmarkwop}% + \fi\@gtempa{toc}{chapter}% +} +\def\addtocmark{% +\phantomsection +\@ifnextchar[{\@adcmk}{\@adcmk[3]}% +} + +\def\l@chapter#1#2{\addpenalty{-\@highpenalty} + \vskip 1.0em plus 1pt \@tempdima 1.5em \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima \hskip -\leftskip + {\large\bfseries\boldmath#1}\ifx0#2\hfil\null + \else + \nobreak + \leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern + \@dotsep mu$}\hfill + \nobreak\hbox to\@pnumwidth{\hss #2}% + \fi\par + \penalty\@highpenalty \endgroup} + +\def\l@title#1#2{\addpenalty{-\@highpenalty} + \addvspace{8pt plus 1pt} + \@tempdima \z@ + \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima \hskip -\leftskip + #1\nobreak + \leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern + \@dotsep mu$}\hfill + \nobreak\hbox to\@pnumwidth{\hss #2}\par + \penalty\@highpenalty \endgroup} + +\def\l@author#1#2{\addpenalty{\@highpenalty} + \@tempdima=15\p@ %\z@ + \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima %\hskip -\leftskip + \textit{#1}\par + \penalty\@highpenalty \endgroup} + +\setcounter{tocdepth}{0} +\newdimen\tocchpnum +\newdimen\tocsecnum +\newdimen\tocsectotal +\newdimen\tocsubsecnum +\newdimen\tocsubsectotal +\newdimen\tocsubsubsecnum +\newdimen\tocsubsubsectotal +\newdimen\tocparanum +\newdimen\tocparatotal +\newdimen\tocsubparanum +\tocchpnum=\z@ % no chapter numbers +\tocsecnum=15\p@ % section 88. plus 2.222pt +\tocsubsecnum=23\p@ % subsection 88.8 plus 2.222pt +\tocsubsubsecnum=27\p@ % subsubsection 88.8.8 plus 1.444pt +\tocparanum=35\p@ % paragraph 88.8.8.8 plus 1.666pt +\tocsubparanum=43\p@ % subparagraph 88.8.8.8.8 plus 1.888pt +\def\calctocindent{% +\tocsectotal=\tocchpnum +\advance\tocsectotal by\tocsecnum +\tocsubsectotal=\tocsectotal +\advance\tocsubsectotal by\tocsubsecnum +\tocsubsubsectotal=\tocsubsectotal +\advance\tocsubsubsectotal by\tocsubsubsecnum +\tocparatotal=\tocsubsubsectotal +\advance\tocparatotal by\tocparanum} +\calctocindent + +\def\l@section{\@dottedtocline{1}{\tocchpnum}{\tocsecnum}} +\def\l@subsection{\@dottedtocline{2}{\tocsectotal}{\tocsubsecnum}} +\def\l@subsubsection{\@dottedtocline{3}{\tocsubsectotal}{\tocsubsubsecnum}} +\def\l@paragraph{\@dottedtocline{4}{\tocsubsubsectotal}{\tocparanum}} +\def\l@subparagraph{\@dottedtocline{5}{\tocparatotal}{\tocsubparanum}} + +\def\listoffigures{\@restonecolfalse\if@twocolumn\@restonecoltrue\onecolumn + \fi\section*{\listfigurename\@mkboth{{\listfigurename}}{{\listfigurename}}} + \@starttoc{lof}\if@restonecol\twocolumn\fi} +\def\l@figure{\@dottedtocline{1}{0em}{1.5em}} + +\def\listoftables{\@restonecolfalse\if@twocolumn\@restonecoltrue\onecolumn + \fi\section*{\listtablename\@mkboth{{\listtablename}}{{\listtablename}}} + \@starttoc{lot}\if@restonecol\twocolumn\fi} +\let\l@table\l@figure + +\renewcommand\listoffigures{% + \section*{\listfigurename + \@mkboth{\listfigurename}{\listfigurename}}% + \@starttoc{lof}% + } + +\renewcommand\listoftables{% + \section*{\listtablename + \@mkboth{\listtablename}{\listtablename}}% + \@starttoc{lot}% + } + +\ifx\oribibl\undefined +\ifx\citeauthoryear\undefined +\renewenvironment{thebibliography}[1] + {\section*{\refname} + \def\@biblabel##1{##1.} + \small + \list{\@biblabel{\@arabic\c@enumiv}}% + {\settowidth\labelwidth{\@biblabel{#1}}% + \leftmargin\labelwidth + \advance\leftmargin\labelsep + \if@openbib + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \fi + \usecounter{enumiv}% + \let\p@enumiv\@empty + \renewcommand\theenumiv{\@arabic\c@enumiv}}% + \if@openbib + \renewcommand\newblock{\par}% + \else + \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}% + \fi + \sloppy\clubpenalty4000\widowpenalty4000% + \sfcode`\.=\@m} + {\def\@noitemerr + {\@latex@warning{Empty `thebibliography' environment}}% + \endlist} +\def\@lbibitem[#1]#2{\item[{[#1]}\hfill]\if@filesw + {\let\protect\noexpand\immediate + \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces} +\newcount\@tempcntc +\def\@citex[#1]#2{\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi + \@tempcnta\z@\@tempcntb\m@ne\def\@citea{}\@cite{\@for\@citeb:=#2\do + {\@ifundefined + {b@\@citeb}{\@citeo\@tempcntb\m@ne\@citea\def\@citea{,}{\bfseries + ?}\@warning + {Citation `\@citeb' on page \thepage \space undefined}}% + {\setbox\z@\hbox{\global\@tempcntc0\csname b@\@citeb\endcsname\relax}% + \ifnum\@tempcntc=\z@ \@citeo\@tempcntb\m@ne + \@citea\def\@citea{,}\hbox{\csname b@\@citeb\endcsname}% + \else + \advance\@tempcntb\@ne + \ifnum\@tempcntb=\@tempcntc + \else\advance\@tempcntb\m@ne\@citeo + \@tempcnta\@tempcntc\@tempcntb\@tempcntc\fi\fi}}\@citeo}{#1}} +\def\@citeo{\ifnum\@tempcnta>\@tempcntb\else + \@citea\def\@citea{,\,\hskip\z@skip}% + \ifnum\@tempcnta=\@tempcntb\the\@tempcnta\else + {\advance\@tempcnta\@ne\ifnum\@tempcnta=\@tempcntb \else + \def\@citea{--}\fi + \advance\@tempcnta\m@ne\the\@tempcnta\@citea\the\@tempcntb}\fi\fi} +\else +\renewenvironment{thebibliography}[1] + {\section*{\refname} + \small + \list{}% + {\settowidth\labelwidth{}% + \leftmargin\parindent + \itemindent=-\parindent + \labelsep=\z@ + \if@openbib + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \fi + \usecounter{enumiv}% + \let\p@enumiv\@empty + \renewcommand\theenumiv{}}% + \if@openbib + \renewcommand\newblock{\par}% + \else + \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}% + \fi + \sloppy\clubpenalty4000\widowpenalty4000% + \sfcode`\.=\@m} + {\def\@noitemerr + {\@latex@warning{Empty `thebibliography' environment}}% + \endlist} + \def\@cite#1{#1}% + \def\@lbibitem[#1]#2{\item[]\if@filesw + {\def\protect##1{\string ##1\space}\immediate + \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces} + \fi +\else +\@cons\@openbib@code{\noexpand\small} +\fi + +\def\idxquad{\hskip 10\p@}% space that divides entry from number + +\def\@idxitem{\par\hangindent 10\p@} + +\def\subitem{\par\setbox0=\hbox{--\enspace}% second order + \noindent\hangindent\wd0\box0}% index entry + +\def\subsubitem{\par\setbox0=\hbox{--\,--\enspace}% third + \noindent\hangindent\wd0\box0}% order index entry + +\def\indexspace{\par \vskip 10\p@ plus5\p@ minus3\p@\relax} + +\renewenvironment{theindex} + {\@mkboth{\indexname}{\indexname}% + \thispagestyle{empty}\parindent\z@ + \parskip\z@ \@plus .3\p@\relax + \let\item\par + \def\,{\relax\ifmmode\mskip\thinmuskip + \else\hskip0.2em\ignorespaces\fi}% + \normalfont\small + \begin{multicols}{2}[\@makeschapterhead{\indexname}]% + } + {\end{multicols}} + +\renewcommand\footnoterule{% + \kern-3\p@ + \hrule\@width 2truecm + \kern2.6\p@} + \newdimen\fnindent + \fnindent1em +\long\def\@makefntext#1{% + \parindent \fnindent% + \leftskip \fnindent% + \noindent + \llap{\hb@xt@1em{\hss\@makefnmark\ }}\ignorespaces#1} + +\long\def\@makecaption#1#2{% + \small + \vskip\abovecaptionskip + \sbox\@tempboxa{{\bfseries #1.} #2}% + \ifdim \wd\@tempboxa >\hsize + {\bfseries #1.} #2\par + \else + \global \@minipagefalse + \hb@xt@\hsize{\hfil\box\@tempboxa\hfil}% + \fi + \vskip\belowcaptionskip} + +\def\fps@figure{htbp} +\def\fnum@figure{\figurename\thinspace\thefigure} +\def \@floatboxreset {% + \reset@font + \small + \@setnobreak + \@setminipage +} +\def\fps@table{htbp} +\def\fnum@table{\tablename~\thetable} +\renewenvironment{table} + {\setlength\abovecaptionskip{0\p@}% + \setlength\belowcaptionskip{10\p@}% + \@float{table}} + {\end@float} +\renewenvironment{table*} + {\setlength\abovecaptionskip{0\p@}% + \setlength\belowcaptionskip{10\p@}% + \@dblfloat{table}} + {\end@dblfloat} + +\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname + ext@#1\endcsname}{#1}{\protect\numberline{\csname + the#1\endcsname}{\ignorespaces #2}}\begingroup + \@parboxrestore + \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par + \endgroup} + +% LaTeX does not provide a command to enter the authors institute +% addresses. The \institute command is defined here. + +\newcounter{@inst} +\newcounter{@auth} +\newcounter{auco} +\newdimen\instindent +\newbox\authrun +\newtoks\authorrunning +\newtoks\tocauthor +\newbox\titrun +\newtoks\titlerunning +\newtoks\toctitle + +\def\clearheadinfo{\gdef\@author{No Author Given}% + \gdef\@title{No Title Given}% + \gdef\@subtitle{}% + \gdef\@institute{No Institute Given}% + \gdef\@thanks{}% + \global\titlerunning={}\global\authorrunning={}% + \global\toctitle={}\global\tocauthor={}} + +\def\institute#1{\gdef\@institute{#1}} + +\def\institutename{\par + \begingroup + \parskip=\z@ + \parindent=\z@ + \setcounter{@inst}{1}% + \def\and{\par\stepcounter{@inst}% + \noindent$^{\the@inst}$\enspace\ignorespaces}% + \setbox0=\vbox{\def\thanks##1{}\@institute}% + \ifnum\c@@inst=1\relax + \gdef\fnnstart{0}% + \else + \xdef\fnnstart{\c@@inst}% + \setcounter{@inst}{1}% + \noindent$^{\the@inst}$\enspace + \fi + \ignorespaces + \@institute\par + \endgroup} + +\def\@fnsymbol#1{\ensuremath{\ifcase#1\or\star\or{\star\star}\or + {\star\star\star}\or \dagger\or \ddagger\or + \mathchar "278\or \mathchar "27B\or \|\or **\or \dagger\dagger + \or \ddagger\ddagger \else\@ctrerr\fi}} + +\def\inst#1{\unskip$^{#1}$} +\def\fnmsep{\unskip$^,$} +\def\email#1{{\tt#1}} +\AtBeginDocument{\@ifundefined{url}{\def\url#1{#1}}{}% +\@ifpackageloaded{babel}{% +\@ifundefined{extrasenglish}{}{\addto\extrasenglish{\switcht@albion}}% +\@ifundefined{extrasfrenchb}{}{\addto\extrasfrenchb{\switcht@francais}}% +\@ifundefined{extrasgerman}{}{\addto\extrasgerman{\switcht@deutsch}}% +\@ifundefined{extrasngerman}{}{\addto\extrasngerman{\switcht@deutsch}}% +}{\switcht@@therlang}% +\providecommand{\keywords}[1]{\par\addvspace\baselineskip +\noindent\keywordname\enspace\ignorespaces#1}% +} +\def\homedir{\~{ }} + +\def\subtitle#1{\gdef\@subtitle{#1}} +\clearheadinfo +% +%%% to avoid hyperref warnings +\providecommand*{\toclevel@author}{999} +%%% to make title-entry parent of section-entries +\providecommand*{\toclevel@title}{0} +% +\renewcommand\maketitle{\newpage +\phantomsection + \refstepcounter{chapter}% + \stepcounter{section}% + \setcounter{section}{0}% + \setcounter{subsection}{0}% + \setcounter{figure}{0} + \setcounter{table}{0} + \setcounter{equation}{0} + \setcounter{footnote}{0}% + \begingroup + \parindent=\z@ + \renewcommand\thefootnote{\@fnsymbol\c@footnote}% + \if@twocolumn + \ifnum \col@number=\@ne + \@maketitle + \else + \twocolumn[\@maketitle]% + \fi + \else + \newpage + \global\@topnum\z@ % Prevents figures from going at top of page. + \@maketitle + \fi + \thispagestyle{empty}\@thanks +% + \def\\{\unskip\ \ignorespaces}\def\inst##1{\unskip{}}% + \def\thanks##1{\unskip{}}\def\fnmsep{\unskip}% + \instindent=\hsize + \advance\instindent by-\headlineindent + \if!\the\toctitle!\addcontentsline{toc}{title}{\@title}\else + \addcontentsline{toc}{title}{\the\toctitle}\fi + \if@runhead + \if!\the\titlerunning!\else + \edef\@title{\the\titlerunning}% + \fi + \global\setbox\titrun=\hbox{\small\rm\unboldmath\ignorespaces\@title}% + \ifdim\wd\titrun>\instindent + \typeout{Title too long for running head. Please supply}% + \typeout{a shorter form with \string\titlerunning\space prior to + \string\maketitle}% + \global\setbox\titrun=\hbox{\small\rm + Title Suppressed Due to Excessive Length}% + \fi + \xdef\@title{\copy\titrun}% + \fi +% + \if!\the\tocauthor!\relax + {\def\and{\noexpand\protect\noexpand\and}% + \protected@xdef\toc@uthor{\@author}}% + \else + \def\\{\noexpand\protect\noexpand\newline}% + \protected@xdef\scratch{\the\tocauthor}% + \protected@xdef\toc@uthor{\scratch}% + \fi + \addtocontents{toc}{\noexpand\protect\noexpand\authcount{\the\c@auco}}% + \addcontentsline{toc}{author}{\toc@uthor}% + \if@runhead + \if!\the\authorrunning! + \value{@inst}=\value{@auth}% + \setcounter{@auth}{1}% + \else + \edef\@author{\the\authorrunning}% + \fi + \global\setbox\authrun=\hbox{\small\unboldmath\@author\unskip}% + \ifdim\wd\authrun>\instindent + \typeout{Names of authors too long for running head. Please supply}% + \typeout{a shorter form with \string\authorrunning\space prior to + \string\maketitle}% + \global\setbox\authrun=\hbox{\small\rm + Authors Suppressed Due to Excessive Length}% + \fi + \xdef\@author{\copy\authrun}% + \markboth{\@author}{\@title}% + \fi + \endgroup + \setcounter{footnote}{\fnnstart}% + \clearheadinfo} +% +\def\@maketitle{\newpage + \markboth{}{}% + \def\lastand{\ifnum\value{@inst}=2\relax + \unskip{} \andname\ + \else + \unskip \lastandname\ + \fi}% + \def\and{\stepcounter{@auth}\relax + \ifnum\value{@auth}=\value{@inst}% + \lastand + \else + \unskip, + \fi}% + \begin{center}% + \let\newline\\ + {\Large \bfseries\boldmath + \pretolerance=10000 + \@title \par}\vskip .8cm +\if!\@subtitle!\else {\large \bfseries\boldmath + \vskip -.65cm + \pretolerance=10000 + \@subtitle \par}\vskip .8cm\fi + \setbox0=\vbox{\setcounter{@auth}{1}\def\and{\stepcounter{@auth}}% + \def\thanks##1{}\@author}% + \global\value{@inst}=\value{@auth}% + \global\value{auco}=\value{@auth}% + \setcounter{@auth}{1}% +{\lineskip .5em +\noindent\ignorespaces +\@author\vskip.35cm} + {\small\institutename} + \end{center}% + } + +% definition of the "\spnewtheorem" command. +% +% Usage: +% +% \spnewtheorem{env_nam}{caption}[within]{cap_font}{body_font} +% or \spnewtheorem{env_nam}[numbered_like]{caption}{cap_font}{body_font} +% or \spnewtheorem*{env_nam}{caption}{cap_font}{body_font} +% +% New is "cap_font" and "body_font". It stands for +% fontdefinition of the caption and the text itself. +% +% "\spnewtheorem*" gives a theorem without number. +% +% A defined spnewthoerem environment is used as described +% by Lamport. +% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\def\@thmcountersep{} +\def\@thmcounterend{.} + +\def\spnewtheorem{\@ifstar{\@sthm}{\@Sthm}} + +% definition of \spnewtheorem with number + +\def\@spnthm#1#2{% + \@ifnextchar[{\@spxnthm{#1}{#2}}{\@spynthm{#1}{#2}}} +\def\@Sthm#1{\@ifnextchar[{\@spothm{#1}}{\@spnthm{#1}}} + +\def\@spxnthm#1#2[#3]#4#5{\expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}\@addtoreset{#1}{#3}% + \expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand + \csname the#3\endcsname \noexpand\@thmcountersep \@thmcounter{#1}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@spynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}% + \expandafter\xdef\csname the#1\endcsname{\@thmcounter{#1}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#3}{#4}}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@spothm#1[#2]#3#4#5{% + \@ifundefined{c@#2}{\@latexerr{No theorem environment `#2' defined}\@eha}% + {\expandafter\@ifdefinable\csname #1\endcsname + {\newaliascnt{#1}{#2}% + \expandafter\xdef\csname #1name\endcsname{#3}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}% + \global\@namedef{end#1}{\@endtheorem}}}} + +\def\@spthm#1#2#3#4{\topsep 7\p@ \@plus2\p@ \@minus4\p@ +\refstepcounter{#1}% +\@ifnextchar[{\@spythm{#1}{#2}{#3}{#4}}{\@spxthm{#1}{#2}{#3}{#4}}} + +\def\@spxthm#1#2#3#4{\@spbegintheorem{#2}{\csname the#1\endcsname}{#3}{#4}% + \ignorespaces} + +\def\@spythm#1#2#3#4[#5]{\@spopargbegintheorem{#2}{\csname + the#1\endcsname}{#5}{#3}{#4}\ignorespaces} + +\def\@spbegintheorem#1#2#3#4{\trivlist + \item[\hskip\labelsep{#3#1\ #2\@thmcounterend}]#4} + +\def\@spopargbegintheorem#1#2#3#4#5{\trivlist + \item[\hskip\labelsep{#4#1\ #2}]{#4(#3)\@thmcounterend\ }#5} + +% definition of \spnewtheorem* without number + +\def\@sthm#1#2{\@Ynthm{#1}{#2}} + +\def\@Ynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname + {\global\@namedef{#1}{\@Thm{\csname #1name\endcsname}{#3}{#4}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@Thm#1#2#3{\topsep 7\p@ \@plus2\p@ \@minus4\p@ +\@ifnextchar[{\@Ythm{#1}{#2}{#3}}{\@Xthm{#1}{#2}{#3}}} + +\def\@Xthm#1#2#3{\@Begintheorem{#1}{#2}{#3}\ignorespaces} + +\def\@Ythm#1#2#3[#4]{\@Opargbegintheorem{#1} + {#4}{#2}{#3}\ignorespaces} + +\def\@Begintheorem#1#2#3{#3\trivlist + \item[\hskip\labelsep{#2#1\@thmcounterend}]} + +\def\@Opargbegintheorem#1#2#3#4{#4\trivlist + \item[\hskip\labelsep{#3#1}]{#3(#2)\@thmcounterend\ }} + +\if@envcntsect + \def\@thmcountersep{.} + \spnewtheorem{theorem}{Theorem}[section]{\bfseries}{\itshape} +\else + \spnewtheorem{theorem}{Theorem}{\bfseries}{\itshape} + \if@envcntreset + \@addtoreset{theorem}{section} + \else + \@addtoreset{theorem}{chapter} + \fi +\fi + +%definition of divers theorem environments +\spnewtheorem*{claim}{Claim}{\itshape}{\rmfamily} +\spnewtheorem*{proof}{Proof}{\itshape}{\rmfamily} +\if@envcntsame % alle Umgebungen wie Theorem. + \def\spn@wtheorem#1#2#3#4{\@spothm{#1}[theorem]{#2}{#3}{#4}} +\else % alle Umgebungen mit eigenem Zaehler + \if@envcntsect % mit section numeriert + \def\spn@wtheorem#1#2#3#4{\@spxnthm{#1}{#2}[section]{#3}{#4}} + \else % nicht mit section numeriert + \if@envcntreset + \def\spn@wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4} + \@addtoreset{#1}{section}} + \else + \def\spn@wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4} + \@addtoreset{#1}{chapter}}% + \fi + \fi +\fi +\spn@wtheorem{case}{Case}{\itshape}{\rmfamily} +\spn@wtheorem{conjecture}{Conjecture}{\itshape}{\rmfamily} +\spn@wtheorem{corollary}{Corollary}{\bfseries}{\itshape} +\spn@wtheorem{definition}{Definition}{\bfseries}{\itshape} +\spn@wtheorem{example}{Example}{\itshape}{\rmfamily} +\spn@wtheorem{exercise}{Exercise}{\itshape}{\rmfamily} +\spn@wtheorem{lemma}{Lemma}{\bfseries}{\itshape} +\spn@wtheorem{note}{Note}{\itshape}{\rmfamily} +\spn@wtheorem{problem}{Problem}{\itshape}{\rmfamily} +\spn@wtheorem{property}{Property}{\itshape}{\rmfamily} +\spn@wtheorem{proposition}{Proposition}{\bfseries}{\itshape} +\spn@wtheorem{question}{Question}{\itshape}{\rmfamily} +\spn@wtheorem{solution}{Solution}{\itshape}{\rmfamily} +\spn@wtheorem{remark}{Remark}{\itshape}{\rmfamily} + +\def\@takefromreset#1#2{% + \def\@tempa{#1}% + \let\@tempd\@elt + \def\@elt##1{% + \def\@tempb{##1}% + \ifx\@tempa\@tempb\else + \@addtoreset{##1}{#2}% + \fi}% + \expandafter\expandafter\let\expandafter\@tempc\csname cl@#2\endcsname + \expandafter\def\csname cl@#2\endcsname{}% + \@tempc + \let\@elt\@tempd} + +\def\theopargself{\def\@spopargbegintheorem##1##2##3##4##5{\trivlist + \item[\hskip\labelsep{##4##1\ ##2}]{##4##3\@thmcounterend\ }##5} + \def\@Opargbegintheorem##1##2##3##4{##4\trivlist + \item[\hskip\labelsep{##3##1}]{##3##2\@thmcounterend\ }} + } + +\renewenvironment{abstract}{% + \list{}{\advance\topsep by0.35cm\relax\small + \leftmargin=1cm + \labelwidth=\z@ + \listparindent=\z@ + \itemindent\listparindent + \rightmargin\leftmargin}\item[\hskip\labelsep + \bfseries\abstractname]} + {\endlist} + +\newdimen\headlineindent % dimension for space between +\headlineindent=1.166cm % number and text of headings. + +\def\ps@headings{\let\@mkboth\@gobbletwo + \let\@oddfoot\@empty\let\@evenfoot\@empty + \def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}% + \leftmark\hfil} + \def\@oddhead{\normalfont\small\hfil\rightmark\hspace{\headlineindent}% + \llap{\thepage}} + \def\chaptermark##1{}% + \def\sectionmark##1{}% + \def\subsectionmark##1{}} + +\def\ps@titlepage{\let\@mkboth\@gobbletwo + \let\@oddfoot\@empty\let\@evenfoot\@empty + \def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}% + \hfil} + \def\@oddhead{\normalfont\small\hfil\hspace{\headlineindent}% + \llap{\thepage}} + \def\chaptermark##1{}% + \def\sectionmark##1{}% + \def\subsectionmark##1{}} + +\if@runhead\ps@headings\else +\ps@empty\fi + +\setlength\arraycolsep{1.4\p@} +\setlength\tabcolsep{1.4\p@} + +\endinput +%end of file llncs.cls diff --git a/main.tex b/main.tex @@ -0,0 +1,66 @@ +\documentclass[runningheads]{llncs} + +\usepackage{amssymb} +\usepackage{amsmath} +\setcounter{tocdepth}{3} +\usepackage{graphicx} + +\newcommand{\keywords}[1]{\par\addvspace\baselineskip +\noindent\keywordname\enspace\ignorespaces#1} + +\begin{document} + +\mainmatter + +\title{Novel approaches for distributing workload on~commodity computer systems} +\titlerunning{Novel approaches for distributing workload} + +\author{Ivan Gankevich \and Yuri Tipikin \and Alexander Degtyarev \and Vladimir Korkhov} +\authorrunning{I.~Gankevich \and Yu.~Tipikin \and A.~Degtyarev \and V.~Korkhov} + +\institute{Saint Petersburg State University,\\ +Universitetskii 35, Petergof, 198504, Saint Petersburg, Russia\\ +igankevich@yandex.com, yuriitipikin@gmail.com +} + +\toctitle{Novel approaches for distributing workload on commodity computer systems} +\tocauthor{Ivan Gankevich, Yuri Tipikin, Alexander Degtyarev, Vladimir Korkhov} +\maketitle + +\graphicspath{ {figures/} } + +\begin{abstract} +Efficient management of a distributed system is a common problem for university's and commercial computer centres, and handling node failures is a major aspect of it. Failures which are rare in a small commodity cluster, at large scale become common, and there should be a way to overcome them without restarting all parallel processes of an application. The efficiency of existing methods can be improved by forming a hierarchy of distributed processes. That way only lower levels of the hierarchy need to be restarted in case of a leaf node failure, and only root node needs special treatment. Process hierarchy changes in real time and the workload is dynamically rebalanced across online nodes. This approach makes it possible to implement efficient partial restart of a parallel application, and transactional behaviour for computer centre service tasks. + +\keywords{long-lived transactions, distributed pipeline, node discovery, software engineering, distributed computing, cluster computing} +\end{abstract} + +\section*{Introduction} + +There are two main tasks for a computer centre: to run users' parallel applications, and to service users. Often these tasks are delegated to some distributed systems, so that users can service themselves, and often these systems are heterogeneous and there are many of them in a computer centre. Yet another system is introduced to make them consistent, but this system is usually not distributed. Moreover, the system usually does not allow rolling back a distributed transaction spanning its subordinate systems. So, the use of reliable distributed systems under control of an unreliable one makes the whole system poorly orchestrated, and absence of automatic error-recovery mechanism increases amount of manual work to bring the system up after a failure. + +To orchestrate computations and perform service tasks in distributed environment the system should be decomposed into two levels. The top level of this system is occupied by transaction manager which executes long-lived transactions (a transaction consisting of nested subordinate ones which spans a long period of time and provides relaxed consistency guarantees). Transactions are distributed across cluster nodes and are retried or rolled back in case of a system failure. On the second level a distributed pipeline is formed from cluster nodes to process compute-intensive workloads with automatic restart of failed processes. The goal of this decomposition is to separate service tasks which need transactional behaviour from parallel applications which need only restart of failed processes (without a roll back). On both levels of the system a hierarchy is used to achieve these goals. + +The first level of the system is capable of reliably executing ancillary and configuration tasks which are typical to university's computer centres. Long-lived transactions allow for a task to run days, months and years, until the transaction is complete. For example, a typical task of registering a user in a computer centre for a fixed period of time (the time span of his/her research grant) starts after the user submits registration form and ends when the research is complete. Additional tasks (e.g.~allocation of computational resources, changing quotas and custom configuration) are executed as subordinate of the main one. Upon completion of the work tasks are executed in reverse, reconfiguring the system to its initial state and erasing or archiving old data. + +The rest of the paper describes the structure of two levels of the system and investigates their performance in a number of tests. Long-lived transactions are discussed in Section~\ref{sec:trans} and distributed pipeline (lower level) in Section~\ref{sec:pipe}. + +\input{sec-1} +\input{sec-2} + +\section*{Related work} + +In~\cite{lifflander2014scalable} the authors discuss the use of message logging to implement efficient recovery from a failure. They observed that some messages written to log are commutative (can be reordered without changing the output of a program) and used this assumption to optimise recovery process. In our system objects in sent buffer are used instead of messages in a log, they are commutative within bounds of the buffer but do not represent history of all messages sent to another node. They are deleted upon receiving a reply, and deleted object can be safely ignored when recovering from a hard fault. So, when an object depends on parallel execution of its subordinates, results can be collected in any order, and it is often desirable to log only execution of principal to reduce recovery time. + +In~\cite{tel2000introduction} the author introduces general distributed wave algorithms for leader election. In contrast to distributed pipeline, these algorithms assume that there can be only one leader and as a result do not take into account link speed between nodes. The goal of discovery algorithm is to create a framework of leaders to distribute workload on a cluster, and each leader is found by recursively repeating election process for the new level of a hierarchy. Using hierarchy of leaders simplifies election algorithm, and taking into account links between nodes allows efficient mapping of resulting hierarchy to physical topology of a network. + +\section*{Conclusions and future work} + +Distributed pipeline is a general method for distributing workload on a commodity cluster which relies on dynamically reconfigurable virtual topology and reliable data transfer. It primarily focuses on service tasks but can be used for high-performance computing as well. The future work is to find a simple way to make distributed pipeline resilient to the root node failures, and test applicability of this approach to high-performance computing applications. + +\subsubsection*{\ackname} The research was carried out using computational resources of Resource Centre ``Computational Centre of Saint Petersburg State University'' (T-EDGE96 HPC-0011828-001) within frameworks of grants of Russian Foundation for Basic Research (project no. 13-07-00747) and Saint Petersburg State University (projects no. 9.38.674.2013 and 0.37.155.2014). + +\bibliography{references}{} +\bibliographystyle{ieeetr} + +\end{document}+ \ No newline at end of file diff --git a/references.bib b/references.bib @@ -0,0 +1,94 @@ +@book{wilde2011rest, + title={{REST}: from research to practice}, + author={Wilde, Erik and Pautasso, Cesare}, + year={2011}, + publisher={Springer Science \& Business Media} +} + +@incollection{kochman2012batched, + title={Batched transactions for {RESTful} web services}, + author={Kochman, Sebastian and Wojciechowski, Pawe{\l} T and Kmieciak, Mi{\l}osz}, + booktitle={Current Trends in Web Engineering}, + pages={86--98}, + year={2012}, + publisher={Springer} +} + +@phdthesis{armstrong2003making, + title={Making reliable distributed systems in the presence of software errors}, + author={Armstrong, Joe}, + year={2003}, + school={The Royal Institute of Technology Stockholm, Sweden} +} + + +% second part + +@book{andrianov2007, + title={Parallel and distributed computations (in Russian)}, + author={Andrianov, S. and Degtyarev, A.}, + isbn={9785983400733}, + url={http://books.google.ru/books?id=CGF0DwEACAAJ}, + year={2007}, + publisher={Saint Petersburg State University} +} + +@article{soshmina2007, + title = {Using {GRID} technologies for computations (in Russian)}, + author = {Soshmina, I. and Bogdanov, A.}, + year = {2007}, + series = {4}, + volume = {3}, + pages = {130--137}, + journal={Saint Petersburg State University Bulletin (Physics and Chemistry)} +} + +@incollection{deg2003, + title = {High Performance Computer Technologies in Shipbuilding}, + booktitle={OPTIMISTIC --- optimization in marine design, Mensch \& Buch Verlag, Berlin}, + author={Degtyarev, A.}, + editor={Birk, L. and Harries, S.}, + year={2003}, + institution={ISBN 3-89820-514-2} +} + +@inproceedings{lifflander2014scalable, + title={Scalable replay with partial-order dependencies for message-logging fault tolerance}, + author={Lifflander, Jonathan and Meneses, Esteban and Menon, Harshitha and Miller, Phil and Krishnamoorthy, Sriram and Kal{\'e}, Laxmikant V}, + booktitle={IEEE International Conference on Cluster Computing (CLUSTER)}, + pages={19--28}, + year={2014}, + organization={IEEE} +} + +@book{tel2000introduction, + title={Introduction to distributed algorithms}, + author={Tel, Gerard}, + year={2000}, + publisher={Cambridge university press} +} + +@inproceedings{lantz2010network, + title={A network in a laptop: rapid prototyping for software-defined networks}, + author={Lantz, Bob and Heller, Brandon and McKeown, Nick}, + booktitle={Proceedings of the 9\textsuperscript{th} ACM SIGCOMM Workshop on Hot Topics in Networks}, + pages={19}, + year={2010}, + organization={ACM} +} + +@inproceedings{handigol2012reproducible, + title={Reproducible network experiments using container-based emulation}, + author={Handigol, Nikhil and Heller, Brandon and Jeyakumar, Vimalkumar and Lantz, Bob and McKeown, Nick}, + booktitle={Proceedings of the 8\textsuperscript{th} international conference on Emerging networking experiments and technologies}, + pages={253--264}, + year={2012}, + organization={ACM} +} + +@phdthesis{heller2013reproducible, + title={Reproducible Network Research with High-fidelity Emulation}, + author={Heller, Brandon}, + year={2013}, + school={Stanford University} +}+ \ No newline at end of file diff --git a/sec-1.tex b/sec-1.tex @@ -0,0 +1,57 @@ +\section{Long-lived transactions} +\label{sec:trans} + +While performing computing in HPC environment various errors may occur. Hardware errors have the greatest impact among others. To fix this type of errors several approaches exist today which often consist of restarting the job completely. In distributed systems computational nodes have even more risk to be lost because of additional factors such as unreliable network. Thus, a complete job restart every time one or more nodes fail is ineffective. + +While searching solution of this problem let us refer to the traditional transaction mechanism. Designed for operations on data it uses logging and locking to prevent data corruption and loss. ACID properties --- Atomicity, Consistency, Isolation, Durability --- of the transaction apply to relational databases, but for distributed system they are implemented with several restrictions. Now let us take a look at high-performance distributed environment. Here operations are performed on the tasks and the objective is to get valid computation results. At first glance, to apply transactions for computing one needs to segment initial task code and take a subtask as an atomic operation, but this is not sufficient. + +Unlike database operations, computations can take much more time to execute, and long-lived transactions, which theoretically can take as much time as needed, is the solution. The main aspect of this technology is a correct logging and further journal processing. There is no unified definition of ``long-lived transaction'', so we define this term here. + +\textsl{Long-lived transaction} is a transaction operations of which are executed for long time periods and there are long gaps between completion of operations. So, it is not safe to assume fast execution time of such transactions. For them only atomicity and reliability properties are guaranteed. + +At the modeling stage web service can be a perfect container for computational subtask. Using REST~\cite{armstrong2003making} --- representational state transfer --- as a specific implementation of web services, we design and implement job scheduling on nodes as a call of a web service with target URL. Main accent here is on restore process of failed operation. The aim of this paper is to offer time-efficient algorithm of such restoration. Next, we will compare properties of REST realisation to ``reliable'' set of properties ACID and will draw a conclusion about meaningful changes in our model, which guarantee satisfiability of the initial task. + +During testing REST web services inside transaction container, the fact of inapplicability of ACID ``as is'' was revealed. These properties conflict with both REST basics and a definition of a web service. Lets consider these properties step by step. + +\subsection{ACID in REST} + +\subsubsection{Atomicity.} Atomicity guarantees that transactions will not be partially saved and in terms of data this works best. However, web services are operations which create, modify and delete data while running, so transaction involving one or more web services must be moved to a higher level of abstraction. In fact, REST web service transactional system has two levels of atomicity: database level and level where web services are called directly. First of them is provided by a particular database implementation by default, second one is on the logical level, which programmer must implement in terms of a particular algorithm. It is important to understand what web service implementation must guarantee logical atomicity of its internal operations by providing only two available states of termination: absolutely correct result of entire web service and error state result. Thus, a collection of web services on logical level can be considered as a single web service recursively applying such requirements. + +So, there is a need for a rollback operation for a web service, and in \cite{kochman2012batched,wilde2011rest} the authors also came to this conclusion. However, REST architecture has no mandatory requirements to system functionality implementation, and this generally leads to impossibility of automatic operation rollback in those systems. Even if rollback operations were implemented by web service developer, there would be no guarantee of valid result after calling these methods, because logical side of an algorithm can be non-trivial. + +\subsubsection{Durability.} Durability is an interesting property. It prevents losing state information (even from hardware failure) by logging all actions in special journal. There are some challenges to implement an efficient distributed journal, but for now there are a few related articles where logging REST web services was partially described~\cite{kochman2012batched,wilde2011rest}. In our approach to achieve efficient failed-task restoration distributed logging system plays an important role, and implementation of this property meets REST requirements. + +\subsubsection{Isolation.} In REST this property is difficult to achieve without making an additional proxy server objects. Those objects serve as queues filtering ``transactional'' web services and executing them sequentially. This method is described in more detail in~\cite{kochman2012batched}. But if web service is designed to use parallel operations, a proxy server can be a performance bottleneck. In this case, isolation must be implemented on web service level, not on abstract level of a collection of web services. Transaction isolation through web service isolation imposes additional requirements to web service developer, but efficiency of transactional system may suffer without it. Isolation of a collection of transactions is applied by transactional job scheduler by default, because it executes transactions sequentially from a queue. + +\subsubsection{Consistency.} Much like isolation, consistency is difficult to guarantee on web service level. It is a property of database rather than a web service. + +%Web services are distributed systems and there is well-known CAP theorem, so, no consistency property for web services, because in our case they must be highly available and be tolerant to failures (and use rollback). + +\subsection{Implementation} + +Main feature of our transactional manager is a special initial task code structure for long-lived transactions. Implementation consist of a server which executes transactions sequentially by placing them to a queue, logging and collecting responses, and a rewritten client code, which uses special functions (we called it {\it act} and {\it react}) to divide a task into a set of subtasks. On server's input we have structured code of a subtask, transferred in JSON format, for example. Each subtask is an autonomous part of code. Initial task after rewriting by this algorithm is represented by a tree, which itself is a transaction and leaves are operations. Thus, sequence of operations are saved: sequential operations have parent-child relation, and parallel have child-child relation. + +This approach is largely different from those described in~\cite{kochman2012batched,wilde2011rest}, it is not focused only on web service calls. In real world applications, reliable summary result is what user wants, without middleware web services calls information. But those middleware operations must be processed in any case. Only simplistic algorithms use exclusively web service calls, often a call is a result of subtask processing from another web service. Dividing task to a group of subtasks and after that formatting a transaction allows processing not only invokes of web services. In fact, any part of initial task can be secure. + +In REST web services there is no universal way to achieve general atomicity. Rollback is implemented by moving the tree backward from a leave with failed state. Rollback performs for each subtask separately, not affecting other subtask on that particular computational node. In case of a node hardware failure, first rollback will wait the node to come online for some time, to not to move a task to another node's queue. In case of impossibility of that scenario, rollback function goes one level up and tries the same approach. Code segmentation can improve restoration time significantly, but also prevent legacy application to run in such environment. + +The ineffectiveness of running rollback straight away on higher levels (entire subtree) shown in~\cite{armstrong2003making}. As previously mentioned, rollback function is empty by default and must be written by a programmer of a web service himself. This step is a necessary and logical, because correct rollback for each function must be written by a person who exactly knows in which state abstract transaction will be after failed operation and what that operation was doing before stop. Transactional system described in this paper is a tool, not an universal solution for all types of operations because each computational algorithm is unique. Use of this tool requires rethinking of original algorithm in terms of partitioning to autonomous segments. + +\subsection{Building the transaction and early results} +There is a step-by-step algorithm of transaction manager. +\begin{enumerate} + \item Programmer select self-sufficient parts of original algorithm -- marking it as transaction operations. + \item Programmer writes a rollback function for all of such parts. + \item Structured code is sent to transaction server. + \item Server executes transaction by placing a root node (which includes a whole algorithm) to queue and then starts moving down across the code tree. + \item If processing is done without failures, iteration reaches leaves and starts going back by transferring successful results from children to their parents. + \item If processing is done with failures, transaction will run a rollback function on failed nodes and try to prevent massive rollback by slowly moving up the tree by one level at time. +\end{enumerate} + +The system was tested on 3 level algorithm tree which produces 25 lines in journal until it is completed. Measured time indicates how long transaction manager works to complete the task if a rollback function was called at specific log line (Fig.~\ref{fig:trans}). Computation time without any rollback calls shown as dotted line. Time peaks in Fig.~\ref{fig:trans} belong to lines in journal that designate ``execution'' step of one or more subtasks. Total overhead oscillate from 5\% to 15\% because of fast prototype implementation on Node.js technology. The task itself consists of simple integration. Web services as task was tested as well, to investigate properties of long-lived transactions that are described above. +\begin{figure} + \centering + \includegraphics[width=0.77\textwidth]{trans} + \caption{Rollback time of a subtask at different log lines.} + \label{fig:trans} +\end{figure} diff --git a/sec-2.tex b/sec-2.tex @@ -0,0 +1,103 @@ +\section{Distributed pipeline} +\label{sec:pipe} + +The main idea of distributed pipeline is to create virtual topology of processes running on different computer cluster nodes and update it in real-time as infrastructure changes. The changes include nodes going offline and online, joining or leaving the cluster, replacement of any hardware component or an entire network node (including switches and routers), and other changes affecting system performance. Each change results in virtual topology being updated for a new infrastructure configuration. + +The main purpose of distributed pipeline is to optimise performance of distributed low-level service tasks running on a computer cluster. Typically these tasks involve querying each cluster node for some information or updating files on each node, and often single master node sends and collects messages from all slave nodes. To reduce network congestion intermediate nodes should be used to communicate master and slave nodes, that is to collect information and send it to master or the other way round. In case of large cluster a distributed pipeline with virtual topology of a tree is formed. + +The other purpose of distributed pipeline is to improve efficiency of high-performance applications. These applications typically launch many parallel processes on a subset of cluster nodes, which communicate messages with each other. To make these communications efficient virtual topology should resemble a real one as much as possible and take into account nodes' performance (relative to each other) and communication link speed (see Section~\ref{sec:node-rating}). That is, if two nodes are adjacent to each other in virtual topology, then the node which is closest to the tree root should have higher performance than the other one, and the link between them should be of the highest throughput. + +Another aspect of high-performance applications is their fault tolerance and recovery time from node failure. Often these applications consist of long-running processes which are checkpointed with specified time period. If a node fails, then a new one is reserved and the application is recovered from the last checkpoint on each node. To reduce recovery time checkpointing can be made incremental and selective, that is to recover only those parts of a program that have failed and checkpoint the data that have actually changed. In distributed pipeline it is accomplished by logging messages sent to other nodes and resending them in case of a node failure (see Section~\ref{sec:impl}). + +To summarise, distributed pipeline creates virtual topology of a computer cluster in a form of a tree with high-performance nodes being closest to the root, and every virtual link having the highest-possible throughput. The purpose of this pipeline is to optimise performance of various cluster management tasks, but it can be beneficial for high-performance applications as well. + +\subsection{Implementation} +\label{sec:impl} + +From technical point of view distributed pipeline is a collection of reliable network connections between principal and subordinate nodes, which are made unique and shared by multiple applications (or service tasks) in a controlled way. The absence of duplicate connections between any two nodes conserves operating system resources and makes it possible to build distributed pipeline crossing multiple NAT environments: If the node hidden behind NAT can reach a node with public Internet address, they can communicate in both directions. Additionally, it allows creating persistent connections which are closed only when a change in topology occurs or in an event of system failure. + +Connection between nodes can be shared by multiple applications in a controlled way. Each message is tagged with an application identifier (a number), and each application sends/receives messages from either standard input/output or a separate file descriptor (a pipe) which can be polled and operated asynchronously. The data is automatically converted to either portable binary (with network byte order) or text format. So, if high performance of asynchronous communication and small size of binary messages are not required, any programming language which can read and write data to standard streams can be used to develop an application for distributed pipeline. + +To simplify writing high-performance applications for distributed pipeline the notion of a message is removed from the framework, instead the communication is done by sending one object to another and passing it as an argument to a defined method call. Each object can create subordinates to process data in parallel, perform parallel computations, or run tasks concurrently, and then report results to their principals. The absence of messages simplifies the API: an object always processes either principal's local data or results collected from subordinate objects. + +Various aspects of reliable asynchronous communication have to be considered to make distributed pipeline fault-tolerant. If the communication between objects is not needed, the object is sent to a free node to perform some computation, and sent back to its principal when it is done. Objects which are sent to remote computer nodes are saved in a buffer and are removed from it when they return to their principals. That way even if the remote node fails after receiving the objects, they are sent back to their principals from the buffer with an error. After that it is principal that decides to rollback and resend objects to another node, or to fail and report to its own principal. In case the failure occurs before sending an object (e.g. node goes offline), then the object is sent to some other node bypassing its principal. To summarise, subordinate objects \textit{always} return to their principals either with a success or a failure which further simplifies writing high-performance applications. + +Principal/subordinate objects easily map to tree topology. If not specified explicitly, a principal sends a subordinate object to a local execution queue. In case of high load, it is extracted from the queue and sent to a remote node. If the remote node is also under high load, the object is sent further. So, the hierarchy of principals and subordinates is compactly mapped to tree topology: lower-level nodes are used on-demand when a higher-level node can not handle the flow of objects. In other words, when a higher-level node ``overflows'', the excessive objects are ``spilled'' to lower-level nodes. + +So, the main goal of the implementation is to simplify application programming by minimising dependencies for small service programmes, making asynchronous messaging reliable, and by using automatic on-demand load balancing. + +\subsection{Peer discovery} + +The core of distributed pipeline is an algorithm which builds and updates virtual topology, and there are several states in which a node can be. In \textit{disconnected} state a node is not a part of distributed pipeline, and to become the part it discovers its peers and connects to one of them. Prior to connecting the link speed and relative performance of a node are measured. After connecting the node enters \textit{connected} state. In this state it receives updates from subordinate nodes (if any) and sends them to its principal. So, updates propagate from leaves to the root of a tree. + +In initial state a node uses discovery algorithm to find its peers. The node queries operating system for a list of networks it is part of and filters out global and Internet host loopback addresses (/32 and 127.0.0.0/8 blocks in IPv4 standard). Then it sends a subordinate object to each address in the list and measures response time. In case of success the response time is saved in the table and in case of failure it is deleted. After receiving all subordinate objects principal repeats the process until minimal number of performance samples is collected for all peers. Then the rating (see~Section~\ref{sec:node-rating}) of each peer is calculated and the table is sorted by it. The principal declares the first peer in the table a leader and sends a subordinate object to it which increases peer's level by one. Then the whole algorithm repeats for the next level of a tree. + +%The algorithm is best described with a listing in Figure~\ref{alg:discovery}. + +Sometimes two nodes in disconnected state can be chosen to be principals of each other, which creates a cycle in tree topology of distributed pipeline. This can happen if two nodes have the same rating. The cycle is eliminated by rejecting offer from the node with higher IP address, so that a node with lower IP address becomes the principal. To make rating conflicts rare IP address is used as the second field when sorting the table of peers. + +On initial installation the total number of subordinate objects sent by each node amounts to $m n^2$ where $n$ is the total number of nodes and $m$ is the minimal number of samples, however, for subsequent restarts of the whole cluster this number can be significantly reduced with help of peer caches (Section~\ref{sec:peer-caches}). Upon entering connected state or receiving updates from peers each node stores current peer table in a file. When the node restarts it runs discovery algorithm only for peers in the file. If no peers are found to be online, then the algorithm repeats with an empty cache. + +\subsection{Node's rating} + +Determining performance of a computer is a complex task on its own right. The same computers may show varying performance for different applications, and the same application may show varying performance for different computers. For distributed pipeline performance of a node equals the number of computed objects per unit of time which depends on a type of a workload. So, performance of a computer is rather a function of a workload, not a variable that can be measured for a node. + +In contrast to performance, concurrency (the ability to handle many workloads of the same type or a large workload) is a variable of a node often amounting to the number of processor cores. Using concurrency instead of processor speed for measuring performance is equivalent to assuming that all processors in a cluster have the same clock rate so that a number of cores determines performance. This assumption gives rough estimate of real performance, however, it allows determining performance just by counting the total number of cores in a computer node and relieves one from running resource-consuming performance tests on each node. + +\label{sec:node-rating} +In~\cite{deg2003,soshmina2007,andrianov2007} the authors suggest generalisation of Amdahl's law formula for computer clusters from which node's rating can be devised. The formula +\begin{equation*} + S_N = \frac{N}{1 - \alpha + \alpha N + \beta\gamma N^3} +\end{equation*} +shows speedup of a parallel programme on a cluster taking into account communication overhead. Here $N$ is the number of nodes, $\alpha$ is the sequential portion of a program, $\beta$ is the diameter of a system (the maximal number of intermediate nodes a message passes through when any two nodes communicate), and $\gamma$ is the ratio of node performance to network link performance. Speedup reaches its maximal value at $N = \sqrt[3]{(1-\alpha)/(2\beta\gamma)}$, so the higher the link performance is the higher speedup is achieved. In distributed pipeline performance is measured as the number of objects processed by a node or transmitted by network link during a fixed time period. The ratio of these two numbers is used as a rating. + +So, when nodes are in disconnected state the rating is estimated as the ratio of a node concurrency to the response time. The rating of a remote node is re-estimated to be the ratio of number of transmitted objects to the number of processed objects per unit of time when nodes enter connected state and start processing objects. + +\subsection{Rating and level updates} + +A node in connected state may update its level if a new subordinate node with the same or higher level chooses it as a leader. The level of each node equals to the maximal level of subordinates plus one. So, if some high-level node connects to a principal, then its level is recalculated and this change propagates towards root of a tree. That way the root node level equals the maximal level of all nodes in the cluster plus one. + +The rating of principal can become smaller than the rating of one of its subordinates when the workload type is changed from compute-intensive to data-intensive or the other way round. This also may occur due to a delayed level update, a change in node's configuration, or as a result of higher level node being offline. When it happens, the principal and the subordinate swap their positions in virtual topology, that is the higher level subordinate node becomes principal. Thus high-performance node can make its way to the root of a tree, if there are no network bottlenecks in the path. + +%Large number of subordinates. Prime factors of number of subordinates. Or node performance. + +So, rating and level updates propagate from leaves to the root of a tree in virtual topology automatically adapting distributed pipeline for a new type of workload or new cluster configuration. + +\subsection{Node failures and network partitions} + +There are three types of node failures in distributed pipeline: a failure of a leaf node, a principal node, and the root node. When a leaf node fails, objects in the corresponding sent buffer of its principal node are returned to their principals, and objects in unsent buffer are sent to some other subordinate node. If error processing is not done by principal object, then returning subordinate objects are also re-sent to other subordinate nodes. In case of principal or root node failure the recovery mechanism is the same, but subordinate nodes that lost their principal enter disconnected state, and a new principal is chosen from these subordinate nodes. + +In case of root node failure all objects which were sent to subordinate nodes are lost and retransmitted one more time. Sometimes this results in restart of the whole application which discards previously computed objects. The obvious solution to this problem is to buffer subordinate objects returning to their principals so that in an event of a failure retransmit them to a new principal node. However, in case of a root node failure there is no way to recover objects residing in this particular node other than replicating them to some other node prior to failure. This makes the solution unnecessary complicated, so for now no simple solution to this problem has been found. + +In case of network partition the recovery mechanism is also the same, and it also possess disadvantages of a root node failure: The results computed by subordinate objects are discarded and potentially large part of the application has to be restarted. + +So, the main approach for dealing with failures consists of resending lost objects to healthy nodes which is equivalent of recomputing a part of the problem being solved. In case of root node failure or network partition a potentially large number of objects are recomputed, but no simple solution to this problem has been found. + +\subsection{Evaluation} + +Test platform consisted of a multi-processor node, and Linux network namespaces were used to consolidate virtual cluster of varying number of nodes on a physical node~\cite{lantz2010network,handigol2012reproducible,heller2013reproducible}. Distributed pipeline needs one daemon process on each node to operate correctly, so one virtual node was used for each daemon. Tests were repeated multiple times to reduce influences of processes running in background. Each subsequent test run was separated from previous one with a delay to give operating system time to release resources, cleanup and flush buffers. + +Discovery test was designed to measure effect of cache on the time an initial node discovery takes. For the first run all cache files were removed from file system so that a node went from disconnected to connected state. For the second run all caches for each node were generated and stored in file system so that each node started from connected state. + +Buffer test shows how many objects sent buffer holds under various load. Objects were sent between two nodes in a ``ping-pong'' manner. Every update of buffer size was captured and maximum value for each run was calculated. A delay between sending objects simulated the load on the system: the higher the load is the higher the delay between subsequent transfers is. + +\subsection{Test results} + +\label{sec:peer-caches} +Discovery test showed that caching node peers can speed up transition from disconnected to connected state by up to 25 times for 32 nodes (Fig.~\ref{fig:discovery}), and this number increases with the number of nodes. This is expected behaviour since the whole discovery step is omitted and cached values are used to reconstruct peers' level and performance data. The absolute time of this test is expected to increase when executed on real network, and cache effect might become more dramatic. + +Buffer test showed that sent buffer contains many objects only under low load, i.e. when the ratio of computations to data transfers is low. Under high load computations and data transfer overlap, and the number of objects in sent buffer lowers (Fig.~\ref{fig:buffer}). + +\begin{figure} + \centering + \includegraphics[width=0.77\textwidth]{discovery} + \caption{Time taken for various number of nodes to discover each other with and without help of cache.} + \label{fig:discovery} +\end{figure} + +\begin{figure} + \centering + \includegraphics[width=0.77\textwidth]{buffer} + \caption{Number of objects in sent buffer for various delays between objects transfers.} + \label{fig:buffer} +\end{figure}