Abstract Two-Phase Update for Scalable Concurrent Data Structures

A Scalable Approach to Thread-Level SpeculationJ.Gregory Steffan,Christopher B.Colohan,Antonia Zhai,and Todd C.MowryComputer Science DepartmentCarnegie Mellon UniversityPittsburgh,PA15213steffan,colohan,zhaia,tcm@AbstractWhile architects understandhow to build cost-effective parallelmachines across a wide spectrum of machine sizes(ranging fromwithin a single chip to large-scale servers),the real challenge ishow to easily create parallel software to effectively exploit all ofthis raw performancepotential.One promising technique for over-coming this problem is Thread-Level Speculation(TLS),which en-ables the compiler to optimistically create parallel threads despiteuncertainty as to whether those threads are actually independent.In this paper,we propose and evaluate a design for supportingTLS that seamlessly scales to any machine size because it is astraightforward extension of writeback invalidation-based cachecoherence(which itself scales both up and down).Our experi-mental results demonstrate that our scheme performs well on bothsingle-chip multiprocessors and on larger-scale machines wherecommunication latencies are twenty times larger.1.IntroductionMachines which can simultaneously execute multiple parallelthreads are becoming increasingly commonplace on a wide vari-ety of scales.For example,techniques such as simultaneous mul-tithreading[23](e.g.,the Alpha21464)and single-chip multipro-cessing[16](e.g.,the Sun MAJC[21]and the IBM Power4[10])suggest that thread-level parallelism may become increasingly im-portant even within a single chip.Beyond chip boundaries,evenpersonal computers are often sold these days in two or four-processor configurations.Finally,high-end machines(e.g.,theSGI Origin[14])have long exploited parallel processing.Perhaps the greatest stumbling block to exploiting all of thisraw performance potential is our ability to automatically convertsingle-threaded programs into parallel programs.Despite the sig-nificant progress which has been made in automatically paralleliz-ing regular numeric applications,compilers have had little or nosuccess in automatically parallelizing highly irregular numeric orespecially non-numeric applications due to their complex controlflow and memory access patterns.In particular,it is the fact thatcondition)...x =hash[index1];...hash[index2]=y;...(b)Execution using thread-level speculationEpoch 1hash[10] == hash[3]RedoProcessor1Processor2Processor3Processor4Epoch 4hash[25] == hash[10]attempt_commit()..................ing cache coherence to detect a RAW dependence violation.2.1An ExampleTo illustrate the basic idea behind our scheme,we show an example of how it detects a read-after-write(RAW)dependence violation.Recall that a given speculative load violates a RAW de-pendence if its memory location is subsequently modified by an-other epoch such that the store should have preceded the load in the original sequential program.As shown in Figure2,we aug-ment the state of each cache line to indicate whether the cacheline has been speculatively loaded(SL)and/or speculatively mod-ified(SM).For each cache,we also maintain a logical timestamp (called an epoch number)which indicates the sequential ordering of that epoch with respect to all other epochs,and aflag indicating whether a data dependence violation has occurred.In the example,epoch6performs a speculative load,so the cor-responding cache line is marked as speculatively loaded.Epoch5 then stores to that same cache line,generating an invalidation con-taining its epoch number.When the invalidation is received,three things must be true for this to be a RAW dependence violation. First,the target cache line of the invalidation must be present in the cache.Second,it must be marked as having been speculatively loaded.Third,the epoch number associated with the invalidation must be from a logically-earlier epoch.Since all three conditions are true in the example,a RAW dependence has been violated; epoch6is notified by setting the violationflag.As we will show, the full coherence scheme must handle many other cases,but the overall concept is analogous to this example.In the sections that follow,we define the new speculative cache line states and the actual cache coherence scheme,including the actions which must occur when an epoch becomes homefree or is notified that a violation has occurred.We begin by describing the underlying architecture assumed by the coherence scheme.2.2Underlying ArchitectureThe goal of our coherence scheme is to be both general and scalable to any size of machine.We want the coherence mech-anism to be applicable to any combination of single-threaded or multithreaded processors within a shared-memory multiprocessor (i.e.not restricted simply to single-chip multiprocessors,etc.).For simplicity,we assume that the shared-memory architec-ture supports an invalidation-based cache coherence scheme where all hierarchies enforce the inclusion property.Figure3(a)shows Figure3.Base architecture for the TLS coherence scheme.a generalization of the underlying architecture.There may be a number of processors or perhaps only a single multithreaded processor,followed by an arbitrary number of levels of physi-cally private caching.The level of interest is thefirst level where invalidation-based cache coherence begins,which we refer to as the speculation level.We generalize the levels below the spec-ulation level(i.e.further away from the processors)as an inter-connection network providing access to main memory with some arbitrary number of levels of caching.The amount of detail shown in Figure3(a)is not necessary for the purposes of describing our cache coherence scheme.In-stead,Figure3(b)shows a simplified model of the underlying ar-chitecture.The speculation level described above happens to be a physically shared cache and is simply referred to from now on as “the cache”.Above the caches,we have some number of proces-sors,and below the caches we have an implementation of cache-coherent shared memory.Although coherence can be recursive,speculation only occurs at the speculation level.Above the speculation level(i.e.closer to the processors),we maintain speculative state and buffer specula-tive modifications.Below the speculation level(i.e.further from the processors),we simply propagate speculative coherence ac-tions and enforce inclusion.2.3Overview of Our SchemeThe remainder of this section describes the important details of our coherence scheme,which requires the following key ele-ments:(i)a notion of whether a cache line has been speculatively loaded and/or speculatively modified;(ii)a guarantee that a spec-ulative cache line will not be propagated to regular memory,and that speculation will fail if a speculative cache line is replaced;andDescriptionIESDSpESpSDescriptionReadReadExline with exclusive access.Upgrade-request:gain exclusive access to InvWritebackFlushNotifySharedRead-exclusive-speculative:return cache UpgradeSpaccess to a cache line that is already present.Invalidation-speculative:only invalidateDescriptionThe request has returned shared access.The request has returned exclusive access.The request is from a logically-later epoch.The request is from a logically-earlier epoch.(c)Responses to processor events(d)Responses to external coherence events2.6Baseline Coherence SchemeOur coherence scheme for supporting TLS is summarized by the two state transition diagrams shown in Figures4(c)and4(d). The former shows transitions in response to processor-initiated events(i.e.speculative and non-speculative loads and stores),and the latter shows transitions in response to coherence messages from the external memory system.Let usfirst briefly summarize standard invalidation-based cache coherence.If a load suffers a miss,we issue a read to the memory system;if a store misses,we issue a read-exclusive.If a store hits and the cache line is in the shared(S)state,we issue an upgrade-request to obtain exclusive access.Note that read-exclusive and upgrade-request messages are only sent down into the memory hierarchy by the cache;when the underlying coher-ence mechanism receives such a message,it generates an invalida-tion message(which only travels up to the cache from the memory hierarchy)for each cache containing a copy of the line to enforce exclusiveness.Having summarized standard coherence,we now describe a few highlights of how we extend it to support TLS. 2.6.1Some Highlights of Our Coherence SchemeWhen a speculative memory reference is issued,we transi-tion to the speculative-exclusive(SpE)or speculative-shared(SpS) state as appropriate.For a speculative load we set the SLflag,and for a speculative store we set the SMflag.When a speculative load misses,we issue a normal read to the memory system.In contrast,when a speculative store misses, we issue a read-exclusive-speculative containing the current epoch number.When a speculative store hits and the cache line is in the shared(S)state,we issue an upgrade-request-speculative which also contains the current epoch number.When a cache line has been speculatively loaded(i.e.it is in either the SpE or SpS state with the SLflag set),it is susceptible to a read-after-write(RAW)dependence violation.If a normal invalidation arrives for that line,then clearly the speculation fails. In contrast,if an invalidation-speculative arrives,then a violation only occurs if it is from a logically-earlier epoch.When a cache line is dirty,the cache owns the only up-to-date copy of the cache line and must preserve it.When a speculative store accesses a dirty cache line,we generate aflush to ensure that the only up-to-date copy of the cache line is not corrupted with speculative modifications.For simplicity,we also generate aflush when a speculative load accesses a dirty cache line(we describe later in Section2.7how this case can be optimized).A goal of this version of the coherence scheme is to avoid slow-ing down non-speculative threads to the extent possible.Hence a cache line in a non-speculative state is not invalidated when an invalidation-speculative arrives from the external memory system. For example,a line in the shared(S)state remains in that state whenever an invalidation-speculative is received.Alternatively, the cache line could be relinquished to give exclusiveness to the speculative thread,possibly eliminating the need for that specula-tive thread to obtain ownership when it becomes homefree.Since the superior choice is unclear without concrete data,we compare the performance of both approaches later in Section5.4.2.6.2When Speculation SucceedsOur scheme depends on ensuring that epochs commit their speculative modifications to memory in logical order.We imple-ment this ordering by waiting for and passing the homefree token at the end of each epoch.When the homefree token arrives,we know that all logically-earlier epochs have completely performed all speculative memory operations,and that any pending incom-ing coherence messages have been processed—hence memory is consistent.At this point,the epoch is guaranteed not to suffer any further dependence violations with respect to logically-earlier epochs,and therefore can commit its speculative modifications.Upon receiving the homefree token,any line which has only been speculatively loaded immediately makes one of the following state transitions:either from speculative-exclusive(SpE)to exclu-sive(E),or else from speculative-shared(SpS)to shared(S).We will describe in the next section how these operations can be im-plemented efficiently.For each line in the speculative-shared(SpS)state that has been speculatively modified(i.e.the SMflag is set),we must issue an upgrade-request to acquire exclusive ownership.Once it is owned exclusively,the line may transition to the dirty(D) state—effectively committing the speculative modifications to reg-ular memory.Maintaining the notion of exclusiveness is therefore important since a speculatively modified line that is exclusive(i.e. SpE with SM set)can commit its results immediately simply by transitioning directly to the dirty(D)state.It would obviously take far too long to scan the entire cache for all speculatively modified and shared lines—ultimately this would delay passing the homefree token and hurt the performance of our scheme.Instead,we propose that the addresses of such lines be added to an ownership required buffer(ORB)whenever a line be-comes both speculatively modified and shared.Hence whenever the homefree token arrives,we can simply generate an upgrade-request for each entry in the ORB,and pass the homefree token on to the next epoch once they have all completed.2.6.3When Speculation FailsWhen speculation fails for a given epoch,any specula-tively modified lines must be invalidated,and any speculatively loaded lines make one of the following state transitions:either from speculative-exclusive(SpE)to exclusive(E),or else from speculative-shared(SpS)to shared(S).In the next section,we will describe how these operations can also be implemented efficiently.2.7Performance OptimizationsWe now present several methods for improving the perfor-mance of our baseline coherence scheme.Forwarding Data Between Epochs:Often regions that we would like to parallelize contain predictable data dependences be-tween epochs.We can avoid violations due to these dependences by inserting wait–signal synchronization.After producing thefi-nal value of a variable,an epoch signals the logically-next epoch that it is safe to consume that value.Our coherence scheme can be extended to support value forwarding through regular memory by allowing an epoch to make non-speculative memory accesses while it is still speculative.Hence an epoch can perform a non-speculative store whose value will be propagated to the logically-next epoch without causing a dependence violation.Dirty and Speculatively Loaded State:As described for the baseline scheme,when a speculative load or store accesses adirty cache line we generate aflush,ensuring that the only up-to-date copy of a cache line is not corrupted with speculative modifi-cations.Since a speculative load cannot corrupt the cache line,it is safe to delay writing the line back until a speculative store oc-curs.This minor optimization is supported with the addition of the dirty and speculatively loaded state(DSpL),which indicates that a cache line is both dirty and speculatively loaded.Since it is trivial to add support for this state,we include it in the baseline scheme that we evaluate later in Section5.Suspending Violations:Recall that if a speculatively ac-cessed line is replaced,speculation must fail because we can no longer track dependence violations.In our baseline scheme,if an epoch is about to evict a speculative line from the cache,we simply let it proceed and signal a dependence violation.(Since one epoch is always guaranteed to be non-speculative,this scheme will not deadlock.)Alternatively,we could suspend the epoch un-til it becomes homefree,at which point we can safely allow the replacement to occur since the line is no longer speculative. Support for Multiple Writers:If two epochs speculatively modify the same cache line,there are two ways to resolve the sit-uation.One option is to simply squash the logically-later epoch, as is the case for our baseline scheme.Alternatively,we could al-low both epochs to modify their own copies of the cache line and combine them with the real copy of the cache line as they commit, as is done in a multiple-writer coherence protocol[3,4].To support multiple writers in our coherence scheme—thus al-lowing multiple speculatively modified copies of a single cache line to exist—we need the following two new features.First,an invalidation-speculative will only cause a violation if it is from a logically-earlier epoch and the line is speculatively loaded;this al-lows multiple speculatively modified copies of the same cache line to co-exist.Second,we must differentiate between normal invali-dations(triggered by remote stores)and invalidations used only to enforce the inclusion property(triggered by replacements deeper in the cache hierarchy).A normal invalidation will not invali-date a speculative cache line that is only speculatively modified; hence the homefree epoch can commit a speculatively modified cache line to memory without invalidating logically-later epochs that have speculatively modified the same cache line.3.Implementing Our SchemeWe now describe a potential implementation of our coherence scheme.We begin with a hardware implementation of epoch num-bers.We then give an encoding for cache line states,and describe the organization of epoch state information.Finally,we describe how to allow multiple speculative writers and how to support spec-ulation in a shared cache.3.1Epoch NumbersIn previous sections,we have mentioned that epoch numbers are used to determine the relative ordering between epochs.In the coherence scheme,an epoch number is associated with every speculatively-accessed cache line and every speculative coherence action.The implementation of epoch numbers must address sev-eral issues.First,epoch numbers must represent a partial ordering (rather than total ordering)since epochs from independent pro-grams or even from independent chains of speculation within the same program are unordered with respect to each other.We im-plement this by having each epoch number consist of two parts: a thread identifier(TID)and a sequence number.If the TIDs from two epoch numbers do not match exactly,then the epochs are unordered.If the TIDs do match,then the signed difference between the sequence numbers is computed to determine logical ordering.(Signed differences preserve the relative ordering when the sequence numbers wrap around.)The second issue is that we would like this comparison of epoch numbers to be performed quickly.At the same time,we would like to have theflexibility to have large epoch numbers (e.g.,32or even64bits),since this simplifies TLS code gener-ation when there is aggressive control speculation[19].Rather than frequently computing the signed differences between large sequence numbers,we instead precompute the relative ordering between the current epoch and other currently-active epochs,and use the resulting logically-later mask to perform simple bit-level comparisons(as discussed later in Section3.4).The third issue is storage overhead.Rather than storing large epoch numbers in each cache line tag,we instead exploit the logically-later mask to store epoch numbers just once per chip. 3.2Implementation of Speculative StateWe encode the speculative cache line states given in Figure4(a) usingfive bits as shown in Figure5(a).Three bits are used to en-code basic coherence state:exclusive(Ex),dirty(Di),and valid (Va).Two bits—speculatively loaded(SL)and speculatively mod-ified(SM)—differentiate speculative from non-speculative states. Figure5(b)shows the state encoding which is designed to have the following two useful properties.First,when an epoch becomes homefree,we can transition from the appropriate speculative to non-speculative states simply by resetting the SM and SL bits.Sec-ond,when a violation occurs,we want to invalidate the cache line if it has been speculatively modified;this can be accomplished by setting its valid(Va)bit to the AND of its Va bit with the comple-ment of its SM bit(i.e.Va=Va&!SM).Figure5(c)illustrates how the speculative state can be ar-ranged.Notice that only a small number of bits are associated with each cache line,and that only one copy of an epoch number is needed.The SL and SM bit columns are implemented such that they can beflash-reset by a single control signal.The SM bits are also wired appropriately to their corresponding Va bits such that they can be simultaneously invalidated when an epoch is squashed. Also associated with the speculative state are an epoch number,an ownership required buffer(ORB),the addresses of the cancel and violation routines,and a violationflag which indicates whether a violation has occurred.3.3Allowing Multiple WritersAs mentioned earlier in Section2.7,it may be advantageous to allow multiple epochs to speculatively modify the same cache line. Supporting a multiple writer scheme requires the ability to merge partial modifications to a line with a previous copy of the line;this in turn requires the ability to identify any partial modifications. One possibility is to replicate the SM column of bits so that there are as many SM columns as there are words(or even bytes)inDescriptionV aDiExSLSMSL Ex VaI X XE00S00D01DSpL01SpE001111SpS001111Figure5.Encoding of cache line states.Figure6.Support for combining cache lines.a cache line,as shown in Figure5(c).We will call thesefine-grain SM bits.When a write occurs,the appropriate SM bit is set. If a write occurs which is of lower granularity than the SM bits can resolve,we must conservatively set the SL bit for that cache line since we can no longer perform a combine operation on this cache line—setting the SL bit ensures that a violation is raised if a logically-earlier epoch writes the same cache line.Figure6shows an example of how we combine a speculatively modified version of a cache line with a non-speculative one.Two epochs speculatively modify the same cache line simultaneously, setting thefine-grain SM bit for each location modified.A specu-latively modified cache line is committed by updating the current non-speculative version with only the words for which thefine-grain SM bits are set.In the example,both epochs have modified thefirst location.Since epoch i+1is logically-later,its value(G) takes precedence over epoch i’s value(E).Because dependence violations are normally tracked at a cache line granularity,another potential performance problem is false violations—i.e.where disjoint portions of a line were read and written.To help reduce this problem,we observe that a line only needs to be marked as speculatively loaded(SL)when an epoch reads a location that it has not previously overwritten(i.e.the load is exposed[1]).Thefine-grain SM bits allow us to distinguish exposed loads,and therefore can help avoid false violations.3.4Support for Speculation in a Shared CacheWe would like to support multiple speculative contexts within a shared cache for three reasons.First,we want to maintain specula-tive state across OS-level context switches so that we can support TLS in a multiprogramming environment.Second,we can use multiple speculative contexts to allow a single processor to exe-cute another epoch when the current one is suspended(i.e.during a suspending violation).Finally,multiple speculative contexts al-low TLS to work with simultaneous multithreading(SMT)[23].TLS in a shared cache allows epochs from the same program to access the same cache lines with two exceptions:(i)two epochs may not modify the same cache line,and(ii)an epoch may not read the modifications of a logically-later epoch.We can enforce these constraints either by suspending or violating the appropri-ate epochs,or else through cache line replication.With the latter approach,a speculatively modified line is replicated whenever an-other epoch attempts to speculatively modify that same line.This replicated copy is obtained from the external memory system,and both copies are kept in the same associative set of the shared cache. If we run out of associative entries,then replication fails and we must instead suspend or violate the logically-latest epoch owning a cache line in the associative set.Suspending an epoch in this case must be implemented carefully to avoid deadlock.Figure5(c)shows hardware support for shared-cache specula-tion where we implement several speculative contexts.The Ex, Di,and Va bits for each cache line are shared between all specula-tive contexts,but each speculative context has its own SL and SM bits.Iffine-grain SM bits are implemented,then only one group of them is necessary per cache line(shared by all speculative con-texts),since only one epoch may modify a given cache line.The single SM bit per speculative context indicates which speculative context owns the cache line,and is simply computed as the OR ofall of thefine-grain SM bits.To determine whether a speculative access requires replication, we must compare the epoch number and speculative state bits with other speculative contexts.Since epoch number comparisons may be slow,we want to use a bit mask which can compare against all speculative contexts in one quick operation.We maintain a logically-later mask for each speculative context(shown in Fig-ure5(c))that indicates which speculative contexts contain epochs that are logically-later,thus allowing us to quickly make the com-parisons using simple bit operations[19].3.5Preserving CorrectnessIn addition to data dependences,there are a few other issues re-lated to preserving correctness under TLS.First,speculation must fail whenever any speculative state is lost(e.g.,the replacement of a speculatively-accessed cache line,the overflow of the ORB, etc.).Second,as with other forms of speculation,a speculative thread should not immediately invoke an exception if it derefer-ences a bad pointer,divides by zero,etc.;instead,it must wait un-til it becomes homefree to confirm that the exception really should have taken place,and for the exception to be precise.Third,if an epoch relies on polling to detect failed speculation and it con-tains a loop,a poll must be inserted inside the loop to avoid infinite looping.Finally,system calls generally cannot be performed spec-ulatively without special support.We will explore this issue more aggressively in future work;for now,we simply stall a speculative thread if it attempts to perform a system call until it is homefree.4.Experimental FrameworkWe evaluate our coherence protocol through detailed simula-tion.Our simulator models4-way issue,out-of-order,superscalar processors similar to the MIPS R10000[24].Register renaming, the reorder buffer,branch prediction,instruction fetching,branch-ing penalties,and the memory hierarchy(including bandwidth and contention)are all modeled,and are parameterized as shown in Ta-ble1.We simulate all applications to completion.Our baseline architecture has four tightly-coupled,single-threaded processors,each with their own primary data and instruc-tion caches.These are connected by a crossbar to a4-bank,unified secondary cache.Our simulator implements the coherence scheme defined in Section2using the hardware support described in Sec-tion3.To faithfully simulate the coherence traffic of our scheme, we model8bytes of overhead for coherence messages that contain epoch numbers.Because epoch numbers are compared lazily(and in parallel with cache accesses),they have no impact on memory access latency.The simulated execution model makes several assumptions with respect to the management of epochs and speculative threads. Epochs are assigned to processors in a round-robin fashion,and each epoch must spawn the next epoch through the use of a lightweight fork instruction.For our baseline architecture,we as-sume that a fork takes10cycles,and this same delay applies to synchronizing two epochs when forwarding occurs.Violations are detected through polling,so an epoch runs to completion before checking if a violation has occurred.When an epoch suffers a violation,we also squash all logically-later epochs.We are simulating real MIPS binaries which contain TLS in-structions.Unused coprocessor instruction encodings are used forTable1.Simulation parameters.Pipeline ParametersIssue WidthFunctional UnitsReorder Buffer SizeInteger MultiplyInteger DivideAll Other IntegerFP DivideFP Square RootAll Other FPBranch Prediction32B32KB,4-way set-assoc32KB,2-way set-assoc,2banks2MB,4-way set-assoc,4banks8for data,2for insts8B per cycle per bank10cycles Secondary CacheMinimum Miss Latency to1access per20cycles10cycles200cycles TLS primitives,and are added to the applications using gcc ASM statements.To produce this code,we are using a set of tools based on the SUIF compiler system.These tools,which are not yet com-plete,help analyze the dependencepatterns in the code,insert TLS primitives into loops,perform loop unrolling,and insert synchro-nization code.The choice of loops to parallelize and other op-timizations(described below)were made by hand,although we plan to have a fully-automatic compiler soon.We only parallelize regions of code that are not provably parallel(by a compiler).Table2shows the applications used in this study:buk is an implementation of the bucket sort algorithm;compress95per-forms data compression and decompression;equake uses sparse matrix computation to simulate an earthquake;and ijpeg per-forms various algorithms on images.The buk application has been reduced to its kernel,removing the data set generation and verification code—the other applications are run in their entirety. For compress95,certain loop-carried dependences occur fre-quently enough that we either hoist them outside of the loop or else explicitly forward them using wait-signal synchronization. 5.Experimental ResultsWe now present the results of our simulation studies.To quan-tify the effectiveness of our support for TLS,we explore the impact of various aspects of our design on the performance of the four ap-plications.Our initial sets of experiments are for a single-chip multiprocessor,and later(in Section5.5)we evaluate larger-scale machines that cross chip boundaries.5.1Performance of the Baseline SchemeTable3summarizes the performance of each application on our baseline architecture,which is a four-processor single-chip multiprocessor that implements our baseline coherence scheme. Throughout this paper,all speedups(and other statistics relative to a single processor)are with respect to the original executable (i.e.without any TLS instructions or overheads)running on a sin-gle processor.Hence our speedups are absolute speedups and not。

LAUREL ELECTRONICS, ureate™ Digital Panel Meter for Processand Ratiometric SignalsFeatures•Reads process signals from ±200 mV to ±600V or ±2 mA to ±5A full scale•Ratiometric mode for bridges and potentiometers•Scalable to ±99,999 for display in engineering unit•Error less than 0.01% of full scale for most ranges•Up to 60 readings per second•Peak or valley capture & display•Universal AC power: 85-264 Vac•Built-in isolated excitation supply: 5, 10 or 24 Vdc•Ratiometric compensation for variations in excitation voltage•1/8 DIN case sealed to NEMA-4X from front panel•Optional serial I/O: Ethernet, USB, RS232, RS485, Ethernet-to-RS485 converter•Optional relay output: dual or quad relays, contact or solid state•Optional isolated analog output: 4-20 mA, 0-20 mA, 0-10V, -10 to +10V•Optional low voltage power: 10-48 Vdc or 12-32 VacDescriptionLaureate™ digital process meters are a cost-effective solutionfor process signals such as 4-20 mA or 0-10V which require zeroand span adjustment for monitoring and control applications. Full-scale voltage input ranges from ±200 mV to ±600V and currentranges from ±2 mA to ±5 A are jumper selectable. All ranges arepre-calibrated at the factory, so that recalibration is not neededwhen changing ranges or signal conditioners. The 200.00 mVand 2.000 V ranges provide a high input impedance of 1 Gohmto minimize the load on the voltage signal.The meter can be set to a ratio mode (or potentiometer followermode) by making selections at the connector and in software.In this mode, the meter tracks a ratio of the applied excitationvoltage and is unaffected by changes in the excitation voltage.This capability is used for resistive bridge sensors and voltagedividers, such as potentiometers which track wiper position.Scaling is from -99,999 to +99,999 (five full digits) with anydecimal point to display readings in engineering units, such asPSI. Three scaling methods are user selectable: scale and offset,two-point method, and system-level calibration using actualtransducer signals.An isolated 5, 10 or 24 Vdc isolated excitation output is stan-dard to power transducers or two-wire transmitters. Ratiometricoperation, which automatically compensates for changes in theapplied excitation, is jumper selectable for applications, such asbridges, where the signal to be measured is proportional to theexcitation level.High read rates at up to 60 or 50 conversions per second whileintegrating the signal over a full power cycle are provided byConcurrent Slope (US Pat 5,262,780) analog-to-digital conver-sion. High read rates are ideal for peak or valley capture, real-time computer interface, and control. Peak and valley values areautomatically captured. These may be displayed via a front panelpushbutton command or a control signal at the rear connector, orbe transmitted as serial data.Peak and valley values are automatically captured. These maybe displayed via a front panel pushbutton command or controlsignal at the rear connector, or be transmitted as serial data.Digital filtering is selectable for electrically noisy environments,including a batch averaging filter and an adaptive moving aver-age filter which provides a choice of 8 time constants from 80 msto 9.6 s. When a significant change in signal level occurs, thatfilter adapts by briefly switching to the shortest time constant tofollow the change, then reverts back to the selected time con-stant. In a selectable Auto filter mode, the filter time constant isautomatically selected based on detected signal noise.Auto-tare allows the display to be zeroed for any input signal byapplying a switch closure or logic signal at the rear connector.The tare value is stored in non-volatile memory and is retainedwhen power is removed.An Extended Laureate computer board can display rate basedon successive readings. It also allows exceptionally accuratecustom curve linearization, for example to read out liquid volumeor rate of flow in a horizontal cylindrical tank based on levelreported by a 4-20 mA transmitter. For setup, up to 180 datapoints can be input into a computer spreadsheet or text file by theuser. The computer then calculates spline-fit segments, whichare downloaded into the meter.Designed for system use. Optional plug-in boards includeEthernet and other serial communication boards, dual or quadrelay boards, and an isolated analog output board. Laureatesmay be powered from 85-264 Vac or optionally from 12-32 Vacor 10-48 Vdc. The display is available with red or green LEDs.The 1/8 DIN case meets NEMA 4X (IP65) specifications from thefront when panel mounted. Any setup functions and front panelkeys can be locked out for simplified usage and security. A built-in isolated 5, 10, or 24 Vdc excitation supply can power trans-ducers and eliminate the need for an external power supply. Allpower and signal connections are via UL / VDE / CSA ratedscrew clamp plugs.SpecificationsDC VoltageDC Voltage Range Resolution Input Resistance Error at 25°C±200.00 mV ±2.000 V ±20.000 V ±200.00 V ±600.0 V * ±300.0 V10 µV100 µV1 mV10 mV100 mV100 mV1 GΩ1 GΩ10 MΩ10 MΩ10 MΩ10 MΩ0.01% FS ± 2 cts0.01% FS ± 2 cts0.01% FS ± 2 cts0.01% FS ± 2 cts± 0.4 V± 0.4 V* 600.0 V range is ETL certified to 300.0 V.DC CurrentDC Current Range Resolution Input Resistance Error at 25°C±2.0000 mA ±20.000 mA ±200.00 mA ±5.000 A 0.1 µA1.0 µA10 µA1.0 mA100 Ω10 Ω1 Ω0.01 Ω0.01% FS ± 2 cts0.01% FS ± 2 cts0.01% FS ± 2 cts± 10 mADisplayReadout Range Indicators 5 LED digits, 7-segment, 14.2 mm (.56"), red or green. -99999 to 99999 or -99990 to 99990 (count by 10) Minus sign, 2 red LED lampsA-to-D ConversionTechniqueA-to-D rateOutput update rate Display update rate Concurrent Slope™ (Pat 5,262,780) 60/s at 60 Hz, 50/s at 50 Hz56/s at 60 Hz, 47/s at 50 Hz3.5/s at 60 Hz, 3/s at 50 HzAccuracyError at 25°C Span tempco Zero tempco 0.01% FS ± 2 counts (except 5A range) 0.003% of reading/°C0.1 count/°CNoise RejectionCMR, DC to 60 Hz NMR at 50/60 Hz 130 dB90 dB with min filteringMaximum SignalMax applied voltage Current protection 600 Vac for 20, 200 and 300 V ranges, 125 Vac for other ranges 25x for 2 mA, 8x for 20 mA, 2.5x for 200 mA, 1x for 5 APowerVoltage, standard Voltage, optional Power frequency Power consumption (typical, base meter) Power isolation 85-264 Vac or 90-300 Vdc12-32 Vac or 10-48 VdcDC or 47-63 Hz1.2W @ 120 Vac, 1.5W @ 240 Vac, 1.3W @ 10 Vdc, 1.4W @ 20 Vdc, 1.55W @ 30 Vdc, 1.8W @ 40 Vdc,2.15W @ 48 Vdc250V rms working, 2.3 kV rms per 1 min testExcitation Output (standard)Selectable levels Output isolation 5 Vdc ± 5%, 100 mA; 10 Vdc ± 5%, 120 mA; 24 Vdc ± 5%, 50 mA 50 Vdc to meter groundAnalog Output (optional)Output levels Current compliance Voltage compliance Scaling 4-20 mA, 0-20 mA, 0-10V, -10 to +10V (jumper selectable) 2 mA at 10V ( > 5 kΩ load)12V at 20 mA (< 60Ω load)Zero and full scale adjustable from -99999 to +99999Resolution Isolation16 bits (0.0015% of full scale)250V rms working, 2.3 kV rms per 1 min testRelay Outputs (optional) Relay typesCurrent ratingsOutput common Isolation2 Form C contact relays or 4 Form A contact relays (normally open) 2 or 4 Form A, AC/DC solid state relays (normally open) 8A at 250 Vac or 24 Vdc for contact relays120 mA at 140 Vac or 180 Vdc for solid state relaysIsolated commons for dual relays or each pair of quad relays 250V rms working, 2.3 kV rms per 1 min testSerial Data I/O (optional) Board selectionsProtocols Data ratesDigital addresses IsolationEthernet, Ethernet-to-RS485 server, USB, USB-to-RS485 server, RS485 (dual RJ11), RS485 Modbus (dual RJ45), RS232. Modbus RTU, Modbus ASCII, Laurel ASCII protocol 300 to 19200 baud247 (Modbus), 31 (Laurel ASCII),250V rms working, 2.3 kV rms per 1 min testSignal ConnectionsEnvironmental Operating temperature Storage temperature Relative humidity Protection0°C to 55°C -40°C to 85°C95% at 40°C, non-condensingNEMA-4X (IP-65) when panel mountedMechanicalApplication ExamplesRatiometric (or potentiometer follower applicationsIn the application shown, the signal from a sliding contact voltage divider can be converted to engineering units such as position, level or percentage. By operating in a ratiometric mode, the meter will remove any effects caused by variations in the excitation supply. For use with a 1 kohm potentiometer, the recommended applied excitation voltage is 10 V, and a 2 kohm resistor should be placed in series with the excitation output and excitation return leads. This will allow the meter's 2.0000 V scale with a high input impedance of 1 Gohm to be used.Powering two-wire transmitters Testing with peak detectionThe isolated 24 Vdc, 50 mA excitation output, which is standard with all Laureate meters, is ideal for powering two-wire, 4-20 mA transmitters. The same two wires are used to apply voltage and carry the output current. Inside the meter, the 4-20 mA current is dropped across a 10 ohm resistor and sets up a 40-200 mV volt-age, which is then sensed by the meter and scaled to engineering units. Destructive testing is an ideal application for the Laureate strain meter. Peak readings are automatically captured at rates up to 60 per second, while the display updates at a legible 3.5 read-ings per second. The peak reading can be recalled at the push of a button or be transmitted via RS232 or RS485. The meter provides isolated 10 Vdc power for up to four (4) the strain gauges and can be scaled to read out directly in engineering units from -99,999 to +99,999.Custom curve linearization Rate from successive readingsThe Laureate DC meter with the Extended main board option allows exceptionally accurate custom curve linearization. For setup, up to 180 data points can be entered into a spreadsheet. The system then creates multiple non-linear spline-fit segments, which provide much better accuracy than linear segments. Illustrated, is the readout of volume of irregularly shaped tanks based on measured liquid level or pressure. Altimeters and thermistors are further applications.The Extended computer board allows the display of rate based on successive readings, for instance flow rate based on changes in liquid level or static pressure in a tank. In the above illustration, the meter displays the rate in gallons at which a horizontal tank is being emptied. The input to the meter can be nonlinear, since only the linearized readings are compared for the determination of rate.Ordering GuideCreate a model number in this format: L10000P, IPCDPM Type L Laureate Digital Panel MeterMain Board1 Standard Main Board, Green LEDs2 Standard Main Board, Red LEDs3 Extended Main Board, Green LEDs4 Extended Main Board, Red LEDsNote: Extended capability is required for custom curve linearization or for display of time rate of change, such as flow rate from changing tank level or acceleration from changing speed.Power (isolated) 0 85-264 Vac1 12-32 Vac & 10-48 Vdc.Relay Output (isolated) 0 None1 Two 8A Contact Relays2 Two 120 mA Solid State Relays3 Four 8A Contact Relays4 Four 120 mA Solid State RelaysAnalog Output (isolated) 0 None1 Isolated 4-20 mA, 0-20 mA, 0-10 V, -10 to +10VDigital Interface (isolated) 0 None1 RS2322 RS485 (dual RJ11 connectors)4 RS485 Modbus (dual RJ45 connectors)5 USB6 USB-to-RS485 converter7 Ethernet8 Ethernet-to-RS485 converterSignal Input (isolated)Process Signals (e.g., 4-20 mA, 0-5 V)P Field scalable. Default Scaling is 4-20 mA = 0-100.00P1Custom Scaling. In the write-in field of your invoice, specify min input, min reading; max input, max reading.Potentiometer Follower Applications (4-wire ratio)SG Field Scalable. Default Scaling is 0-200 mV = 0-100.00SG1Custom Scaling. In the write-in field of your invoice, specify min input, min reading; max input, max reading.Note: The same DC signal conditioner can be user configured for DC, process, bridge, and potentiometer signals. It is precalibrated in EEPROM for all DC Volt and DC Amp ranges listed for DC meters.Add-on Options CBL01RJ11-to-DB9 cable. RJ11 to DB9. Connects RS232 ports of meter and PC.CBL02USB-to-DB9 adapter cable. Combination of CBL02 and CBL01 connects meterRS232 port to PC USB port.CBL03-16-wire data cable, RJ11 to RJ11, 1 ft. Used to daisy chain meters via RS485.CBL03-76-wire data cable, RJ11 to RJ11, 7 ft. Used to daisy chain meters via RS485.CBL05USB cable, A-B. Connects USB ports of meter and PC.CBL06USB to RS485 adapter cable, half duplex, RJ11 to USB. Connects meter RS485 portto PC USB port.CASE1Benchtop laboratory case for one 1/8 DIN meterCASE2Benchtop laboratory case for two 1/8 DIN metersIPC Splash-proof coverBOX1NEMA-4 EnclosureBOX2NEMA-4 enclosure plus IPCBL Blank Lens without button padsNL Meter lens without button pads or Laurel logo。

2009and2010Papers:Big-4Security ConferencespvoOctober13,2010NDSS20091.Document Structure Integrity:A Robust Basis for Cross-site Scripting Defense.Y.Nadji,P.Saxena,D.Song2.An Efficient Black-box Technique for Defeating Web Application Attacks.R.Sekar3.Noncespaces:Using Randomization to Enforce Information Flow Tracking and Thwart Cross-Site Scripting Attacks.M.Van Gundy,H.Chen4.The Blind Stone Tablet:Outsourcing Durability to Untrusted Parties.P.Williams,R.Sion,D.Shasha5.Two-Party Computation Model for Privacy-Preserving Queries over Distributed Databases.S.S.M.Chow,J.-H.Lee,L.Subramanian6.SybilInfer:Detecting Sybil Nodes using Social Networks.G.Danezis,P.Mittal7.Spectrogram:A Mixture-of-Markov-Chains Model for Anomaly Detection in Web Traffic.Yingbo Song,Angelos D.Keromytis,Salvatore J.Stolfo8.Detecting Forged TCP Reset Packets.Nicholas Weaver,Robin Sommer,Vern Paxson9.Coordinated Scan Detection.Carrie Gates10.RB-Seeker:Auto-detection of Redirection Botnets.Xin Hu,Matthew Knysz,Kang G.Shin11.Scalable,Behavior-Based Malware Clustering.Ulrich Bayer,Paolo Milani Comparetti,Clemens Hlauschek,Christopher Kruegel,Engin Kirda12.K-Tracer:A System for Extracting Kernel Malware Behavior.Andrea Lanzi,Monirul I.Sharif,Wenke Lee13.RAINBOW:A Robust And Invisible Non-Blind Watermark for Network Flows.Amir Houmansadr,Negar Kiyavash,Nikita Borisov14.Traffic Morphing:An Efficient Defense Against Statistical Traffic Analysis.Charles V.Wright,Scott E.Coull,Fabian Monrose15.Recursive DNS Architectures and Vulnerability Implications.David Dagon,Manos Antonakakis,Kevin Day,Xiapu Luo,Christopher P.Lee,Wenke Lee16.Analyzing and Comparing the Protection Quality of Security Enhanced Operating Systems.Hong Chen,Ninghui Li,Ziqing Mao17.IntScope:Automatically Detecting Integer Overflow Vulnerability in X86Binary Using Symbolic Execution.Tielei Wang,Tao Wei,Zhiqiang Lin,Wei Zou18.Safe Passage for Passwords and Other Sensitive Data.Jonathan M.McCune,Adrian Perrig,Michael K.Reiter19.Conditioned-safe Ceremonies and a User Study of an Application to Web Authentication.Chris Karlof,J.Doug Tygar,David Wagner20.CSAR:A Practical and Provable Technique to Make Randomized Systems Accountable.Michael Backes,Peter Druschel,Andreas Haeberlen,Dominique UnruhOakland20091.Wirelessly Pickpocketing a Mifare Classic Card.(Best Practical Paper Award)Flavio D.Garcia,Peter van Rossum,Roel Verdult,Ronny Wichers Schreur2.Plaintext Recovery Attacks Against SSH.Martin R.Albrecht,Kenneth G.Paterson,Gaven J.Watson3.Exploiting Unix File-System Races via Algorithmic Complexity Attacks.Xiang Cai,Yuwei Gui,Rob Johnson4.Practical Mitigations for Timing-Based Side-Channel Attacks on Modern x86Processors.Bart Coppens,Ingrid Verbauwhede,Bjorn De Sutter,Koen De Bosschere5.Non-Interference for a Practical DIFC-Based Operating System.Maxwell Krohn,Eran Tromer6.Native Client:A Sandbox for Portable,Untrusted x86Native Code.(Best Paper Award)B.Yee,D.Sehr,G.Dardyk,B.Chen,R.Muth,T.Ormandy,S.Okasaka,N.Narula,N.Fullagar7.Automatic Reverse Engineering of Malware Emulators.(Best Student Paper Award)Monirul Sharif,Andrea Lanzi,Jonathon Giffin,Wenke Lee8.Prospex:Protocol Specification Extraction.Paolo Milani Comparetti,Gilbert Wondracek,Christopher Kruegel,Engin Kirda9.Quantifying Information Leaks in Outbound Web Traffic.Kevin Borders,Atul Prakash10.Automatic Discovery and Quantification of Information Leaks.Michael Backes,Boris Kopf,Andrey Rybalchenko11.CLAMP:Practical Prevention of Large-Scale Data Leaks.Bryan Parno,Jonathan M.McCune,Dan Wendlandt,David G.Andersen,Adrian Perrig12.De-anonymizing Social Networks.Arvind Narayanan,Vitaly Shmatikov13.Privacy Weaknesses in Biometric Sketches.Koen Simoens,Pim Tuyls,Bart Preneel14.The Mastermind Attack on Genomic Data.Michael T.Goodrich15.A Logic of Secure Systems and its Application to Trusted Computing.Anupam Datta,Jason Franklin,Deepak Garg,Dilsun Kaynar16.Formally Certifying the Security of Digital Signature Schemes.Santiago Zanella-Beguelin,Gilles Barthe,Benjamin Gregoire,Federico Olmedo17.An Epistemic Approach to Coercion-Resistance for Electronic Voting Protocols.Ralf Kuesters,Tomasz Truderung18.Sphinx:A Compact and Provably Secure Mix Format.George Danezis,Ian Goldberg19.DSybil:Optimal Sybil-Resistance for Recommendation Systems.Haifeng Yu,Chenwei Shi,Michael Kaminsky,Phillip B.Gibbons,Feng Xiao20.Fingerprinting Blank Paper Using Commodity Scanners.William Clarkson,Tim Weyrich,Adam Finkelstein,Nadia Heninger,Alex Halderman,Ed Felten 21.Tempest in a Teapot:Compromising Reflections Revisited.Michael Backes,Tongbo Chen,Markus Duermuth,Hendrik P.A.Lensch,Martin Welk22.Blueprint:Robust Prevention of Cross-site Scripting Attacks for Existing Browsers.Mike Ter Louw,V.N.Venkatakrishnan23.Pretty-Bad-Proxy:An Overlooked Adversary in Browsers’HTTPS Deployments.Shuo Chen,Ziqing Mao,Yi-Min Wang,Ming Zhang24.Secure Content Sniffing for Web Browsers,or How to Stop Papers from Reviewing Themselves.Adam Barth,Juan Caballero,Dawn Song25.It’s No Secret:Measuring the Security and Reliability of Authentication via’Secret’Questions.Stuart Schechter,A.J.Bernheim Brush,Serge Egelman26.Password Cracking Using Probabilistic Context-Free Grammars.Matt Weir,Sudhir Aggarwal,Bill Glodek,Breno de MedeirosUSENIX Security2009promising Electromagnetic Emanations of Wired and Wireless Keyboards.(Outstanding Student Paper)Martin Vuagnoux,Sylvain Pasini2.Peeping Tom in the Neighborhood:Keystroke Eavesdropping on Multi-User Systems.Kehuan Zhang,XiaoFeng Wang3.A Practical Congestion Attack on Tor Using Long Paths,Nathan S.Evans,Roger Dingledine,Christian Grothoff4.Baggy Bounds Checking:An Efficient and Backwards-Compatible Defense against Out-of-Bounds Errors.Periklis Akritidis,Manuel Costa,Miguel Castro,Steven Hand5.Dynamic Test Generation to Find Integer Bugs in x86Binary Linux Programs.David Molnar,Xue Cong Li,David A.Wagner6.NOZZLE:A Defense Against Heap-spraying Code Injection Attacks.Paruj Ratanaworabhan,Benjamin Livshits,Benjamin Zorn7.Detecting Spammers with SNARE:Spatio-temporal Network-level Automatic Reputation Engine.Shuang Hao,Nadeem Ahmed Syed,Nick Feamster,Alexander G.Gray,Sven Krasser8.Improving Tor using a TCP-over-DTLS Tunnel.Joel Reardon,Ian Goldberg9.Locating Prefix Hijackers using LOCK.Tongqing Qiu,Lusheng Ji,Dan Pei,Jia Wang,Jun(Jim)Xu,Hitesh Ballani10.GATEKEEPER:Mostly Static Enforcement of Security and Reliability Policies for JavaScript Code.Salvatore Guarnieri,Benjamin Livshits11.Cross-Origin JavaScript Capability Leaks:Detection,Exploitation,and Defense.Adam Barth,Joel Weinberger,Dawn Song12.Memory Safety for Low-Level Software/Hardware Interactions.John Criswell,Nicolas Geoffray,Vikram Adve13.Physical-layer Identification of RFID Devices.Boris Danev,Thomas S.Heydt-Benjamin,Srdjan CapkunCP:Secure Remote Storage for Computational RFIDs.Mastooreh Salajegheh,Shane Clark,Benjamin Ransford,Kevin Fu,Ari Juels15.Jamming-resistant Broadcast Communication without Shared Keys.Christina Popper,Mario Strasser,Srdjan Capkun16.xBook:Redesigning Privacy Control in Social Networking Platforms.Kapil Singh,Sumeer Bhola,Wenke Lee17.Nemesis:Preventing Authentication and Access Control Vulnerabilities in Web Applications.Michael Dalton,Christos Kozyrakis,Nickolai Zeldovich18.Static Enforcement of Web Application Integrity Through Strong Typing.William Robertson,Giovanni Vigna19.Vanish:Increasing Data Privacy with Self-Destructing Data.(Outstanding Student Paper)Roxana Geambasu,Tadayoshi Kohno,Amit A.Levy,Henry M.Levy20.Efficient Data Structures for Tamper-Evident Logging.Scott A.Crosby,Dan S.Wallach21.VPriv:Protecting Privacy in Location-Based Vehicular Services.Raluca Ada Popa,Hari Balakrishnan,Andrew J.Blumberg22.Effective and Efficient Malware Detection at the End Host.Clemens Kolbitsch,Paolo Milani Comparetti,Christopher Kruegel,Engin Kirda,Xiaoyong Zhou,XiaoFeng Wang 23.Protecting Confidential Data on Personal Computers with Storage Capsules.Kevin Borders,Eric Vander Weele,Billy Lau,Atul Prakash24.Return-Oriented Rootkits:Bypassing Kernel Code Integrity Protection Mechanisms.Ralf Hund,Thorsten Holz,Felix C.Freiling25.Crying Wolf:An Empirical Study of SSL Warning Effectiveness.Joshua Sunshine,Serge Egelman,Hazim Almuhimedi,Neha Atri,Lorrie Faith Cranor26.The Multi-Principal OS Construction of the Gazelle Web Browser.Helen J.Wang,Chris Grier,Alex Moshchuk,Samuel T.King,Piali Choudhury,Herman VenterACM CCS20091.Attacking cryptographic schemes based on”perturbation polynomials”.Martin Albrecht,Craig Gentry,Shai Halevi,Jonathan Katz2.Filter-resistant code injection on ARM.Yves Younan,Pieter Philippaerts,Frank Piessens,Wouter Joosen,Sven Lachmund,Thomas Walter3.False data injection attacks against state estimation in electric power grids.Yao Liu,Michael K.Reiter,Peng Ning4.EPC RFID tag security weaknesses and defenses:passport cards,enhanced drivers licenses,and beyond.Karl Koscher,Ari Juels,Vjekoslav Brajkovic,Tadayoshi Kohno5.An efficient forward private RFID protocol.Come Berbain,Olivier Billet,Jonathan Etrog,Henri Gilbert6.RFID privacy:relation between two notions,minimal condition,and efficient construction.Changshe Ma,Yingjiu Li,Robert H.Deng,Tieyan Li7.CoSP:a general framework for computational soundness proofs.Michael Backes,Dennis Hofheinz,Dominique Unruh8.Reactive noninterference.Aaron Bohannon,Benjamin C.Pierce,Vilhelm Sjoberg,Stephanie Weirich,Steve Zdancewicputational soundness for key exchange protocols with symmetric encryption.Ralf Kusters,Max Tuengerthal10.A probabilistic approach to hybrid role mining.Mario Frank,Andreas P.Streich,David A.Basin,Joachim M.Buhmann11.Efficient pseudorandom functions from the decisional linear assumption and weaker variants.Allison B.Lewko,Brent Waters12.Improving privacy and security in multi-authority attribute-based encryption.Melissa Chase,Sherman S.M.Chow13.Oblivious transfer with access control.Jan Camenisch,Maria Dubovitskaya,Gregory Neven14.NISAN:network information service for anonymization networks.Andriy Panchenko,Stefan Richter,Arne Rache15.Certificateless onion routing.Dario Catalano,Dario Fiore,Rosario Gennaro16.ShadowWalker:peer-to-peer anonymous communication using redundant structured topologies.Prateek Mittal,Nikita Borisov17.Ripley:automatically securing web2.0applications through replicated execution.K.Vikram,Abhishek Prateek,V.Benjamin Livshits18.HAIL:a high-availability and integrity layer for cloud storage.Kevin D.Bowers,Ari Juels,Alina Oprea19.Hey,you,get offof my cloud:exploring information leakage in third-party compute clouds.Thomas Ristenpart,Eran Tromer,Hovav Shacham,Stefan Savage20.Dynamic provable data possession.C.Christopher Erway,Alptekin Kupcu,Charalampos Papamanthou,Roberto Tamassia21.On cellular botnets:measuring the impact of malicious devices on a cellular network core.Patrick Traynor,Michael Lin,Machigar Ongtang,Vikhyath Rao,Trent Jaeger,Patrick Drew McDaniel,Thomas Porta 22.On lightweight mobile phone application certification.William Enck,Machigar Ongtang,Patrick Drew McDaniel23.SMILE:encounter-based trust for mobile social services.Justin Manweiler,Ryan Scudellari,Landon P.Cox24.Battle of Botcraft:fighting bots in online games with human observational proofs.Steven Gianvecchio,Zhenyu Wu,Mengjun Xie,Haining Wang25.Fides:remote anomaly-based cheat detection using client emulation.Edward C.Kaiser,Wu-chang Feng,Travis Schluessler26.Behavior based software theft detection.Xinran Wang,Yoon-chan Jhi,Sencun Zhu,Peng Liu27.The fable of the bees:incentivizing robust revocation decision making in ad hoc networks.Steffen Reidt,Mudhakar Srivatsa,Shane Balfe28.Effective implementation of the cell broadband engineTM isolation loader.Masana Murase,Kanna Shimizu,Wilfred Plouffe,Masaharu Sakamoto29.On achieving good operating points on an ROC plane using stochastic anomaly score prediction.Muhammad Qasim Ali,Hassan Khan,Ali Sajjad,Syed Ali Khayam30.On non-cooperative location privacy:a game-theoretic analysis.Julien Freudiger,Mohammad Hossein Manshaei,Jean-Pierre Hubaux,David C.Parkes31.Privacy-preserving genomic computation through program specialization.Rui Wang,XiaoFeng Wang,Zhou Li,Haixu Tang,Michael K.Reiter,Zheng Dong32.Feeling-based location privacy protection for location-based services.Toby Xu,Ying Cai33.Multi-party off-the-record messaging.Ian Goldberg,Berkant Ustaoglu,Matthew Van Gundy,Hao Chen34.The bayesian traffic analysis of mix networks.Carmela Troncoso,George Danezis35.As-awareness in Tor path selection.Matthew Edman,Paul F.Syverson36.Membership-concealing overlay networks.Eugene Y.Vasserman,Rob Jansen,James Tyra,Nicholas Hopper,Yongdae Kim37.On the difficulty of software-based attestation of embedded devices.Claude Castelluccia,Aurelien Francillon,Daniele Perito,Claudio Soriente38.Proximity-based access control for implantable medical devices.Kasper Bonne Rasmussen,Claude Castelluccia,Thomas S.Heydt-Benjamin,Srdjan Capkun39.XCS:cross channel scripting and its impact on web applications.Hristo Bojinov,Elie Bursztein,Dan Boneh40.A security-preserving compiler for distributed programs:from information-flow policies to cryptographic mechanisms.Cedric Fournet,Gurvan Le Guernic,Tamara Rezk41.Finding bugs in exceptional situations of JNI programs.Siliang Li,Gang Tan42.Secure open source collaboration:an empirical study of Linus’law.Andrew Meneely,Laurie A.Williams43.On voting machine design for verification and testability.Cynthia Sturton,Susmit Jha,Sanjit A.Seshia,David Wagner44.Secure in-VM monitoring using hardware virtualization.Monirul I.Sharif,Wenke Lee,Weidong Cui,Andrea Lanzi45.A metadata calculus for secure information sharing.Mudhakar Srivatsa,Dakshi Agrawal,Steffen Reidt46.Multiple password interference in text passwords and click-based graphical passwords.Sonia Chiasson,Alain Forget,Elizabeth Stobert,Paul C.van Oorschot,Robert Biddle47.Can they hear me now?:a security analysis of law enforcement wiretaps.Micah Sherr,Gaurav Shah,Eric Cronin,Sandy Clark,Matt Blaze48.English shellcode.Joshua Mason,Sam Small,Fabian Monrose,Greg MacManus49.Learning your identity and disease from research papers:information leaks in genome wide association study.Rui Wang,Yong Fuga Li,XiaoFeng Wang,Haixu Tang,Xiao-yong Zhou50.Countering kernel rootkits with lightweight hook protection.Zhi Wang,Xuxian Jiang,Weidong Cui,Peng Ning51.Mapping kernel objects to enable systematic integrity checking.Martim Carbone,Weidong Cui,Long Lu,Wenke Lee,Marcus Peinado,Xuxian Jiang52.Robust signatures for kernel data structures.Brendan Dolan-Gavitt,Abhinav Srivastava,Patrick Traynor,Jonathon T.Giffin53.A new cell counter based attack against tor.Zhen Ling,Junzhou Luo,Wei Yu,Xinwen Fu,Dong Xuan,Weijia Jia54.Scalable onion routing with torsk.Jon McLachlan,Andrew Tran,Nicholas Hopper,Yongdae Kim55.Anonymous credentials on a standard java card.Patrik Bichsel,Jan Camenisch,Thomas Gros,Victor Shouprge-scale malware indexing using function-call graphs.Xin Hu,Tzi-cker Chiueh,Kang G.Shin57.Dispatcher:enabling active botnet infiltration using automatic protocol reverse-engineering.Juan Caballero,Pongsin Poosankam,Christian Kreibich,Dawn Xiaodong Song58.Your botnet is my botnet:analysis of a botnet takeover.Brett Stone-Gross,Marco Cova,Lorenzo Cavallaro,Bob Gilbert,MartinSzydlowski,Richard A.Kemmerer,Christopher Kruegel,Giovanni VignaNDSS20101.Server-side Verification of Client Behavior in Online Games.Darrell Bethea,Robert Cochran and Michael Reiter2.Defeating Vanish with Low-Cost Sybil Attacks Against Large DHTs.S.Wolchok,O.S.Hofmann,N.Heninger,E.W.Felten,J.A.Halderman,C.J.Rossbach,B.Waters,E.Witchel3.Stealth DoS Attacks on Secure Channels.Amir Herzberg and Haya Shulman4.Protecting Browsers from Extension Vulnerabilities.Adam Barth,Adrienne Porter Felt,Prateek Saxena,and Aaron Boodman5.Adnostic:Privacy Preserving Targeted Advertising.Vincent Toubiana,Arvind Narayanan,Dan Boneh,Helen Nissenbaum and Solon Barocas6.FLAX:Systematic Discovery of Client-side Validation Vulnerabilities in Rich Web Applications.Prateek Saxena,Steve Hanna,Pongsin Poosankam and Dawn Song7.Effective Anomaly Detection with Scarce Training Data.William Robertson,Federico Maggi,Christopher Kruegel and Giovanni Vignarge-Scale Automatic Classification of Phishing Pages.Colin Whittaker,Brian Ryner and Marria Nazif9.A Systematic Characterization of IM Threats using Honeypots.Iasonas Polakis,Thanasis Petsas,Evangelos P.Markatos and Spiros Antonatos10.On Network-level Clusters for Spam Detection.Zhiyun Qian,Zhuoqing Mao,Yinglian Xie and Fang Yu11.Improving Spam Blacklisting Through Dynamic Thresholding and Speculative Aggregation.Sushant Sinha,Michael Bailey and Farnam Jahanian12.Botnet Judo:Fighting Spam with Itself.A.Pitsillidis,K.Levchenko,C.Kreibich,C.Kanich,G.M.Voelker,V.Paxson,N.Weaver,S.Savage13.Contractual Anonymity.Edward J.Schwartz,David Brumley and Jonathan M.McCune14.A3:An Extensible Platform for Application-Aware Anonymity.Micah Sherr,Andrew Mao,William R.Marczak,Wenchao Zhou,Boon Thau Loo,and Matt Blaze15.When Good Randomness Goes Bad:Virtual Machine Reset Vulnerabilities and Hedging Deployed Cryptography.Thomas Ristenpart and Scott Yilek16.InvisiType:Object-Oriented Security Policies.Jiwon Seo and Monica m17.A Security Evaluation of DNSSEC with NSEC3.Jason Bau and John Mitchell18.On the Safety of Enterprise Policy Deployment.Yudong Gao,Ni Pan,Xu Chen and Z.Morley Mao19.Where Do You Want to Go Today?Escalating Privileges by Pathname Manipulation.Suresh Chari,Shai Halevi and Wietse Venema20.Joe-E:A Security-Oriented Subset of Java.Adrian Mettler,David Wagner and Tyler Close21.Preventing Capability Leaks in Secure JavaScript Subsets.Matthew Finifter,Joel Weinberger and Adam Barth22.Binary Code Extraction and Interface Identification for Security Applications.Juan Caballero,Noah M.Johnson,Stephen McCamant,and Dawn Song23.Automatic Reverse Engineering of Data Structures from Binary Execution.Zhiqiang Lin,Xiangyu Zhang and Dongyan Xu24.Efficient Detection of Split Personalities in Malware.Davide Balzarotti,Marco Cova,Christoph Karlberger,Engin Kirda,Christopher Kruegel and Giovanni VignaOakland20101.Inspector Gadget:Automated Extraction of Proprietary Gadgets from Malware Binaries.Clemens Kolbitsch Thorsten Holz,Christopher Kruegel,Engin Kirda2.Synthesizing Near-Optimal Malware Specifications from Suspicious Behaviors.Matt Fredrikson,Mihai Christodorescu,Somesh Jha,Reiner Sailer,Xifeng Yan3.Identifying Dormant Functionality in Malware Programs.Paolo Milani Comparetti,Guido Salvaneschi,Clemens Kolbitsch,Engin Kirda,Christopher Kruegel,Stefano Zanero4.Reconciling Belief and Vulnerability in Information Flow.Sardaouna Hamadou,Vladimiro Sassone,Palamidessi5.Towards Static Flow-Based Declassification for Legacy and Untrusted Programs.Bruno P.S.Rocha,Sruthi Bandhakavi,Jerry I.den Hartog,William H.Winsborough,Sandro Etalle6.Non-Interference Through Secure Multi-Execution.Dominique Devriese,Frank Piessens7.Object Capabilities and Isolation of Untrusted Web Applications.Sergio Maffeis,John C.Mitchell,Ankur Taly8.TrustVisor:Efficient TCB Reduction and Attestation.Jonathan McCune,Yanlin Li,Ning Qu,Zongwei Zhou,Anupam Datta,Virgil Gligor,Adrian Perrig9.Overcoming an Untrusted Computing Base:Detecting and Removing Malicious Hardware Automatically.Matthew Hicks,Murph Finnicum,Samuel T.King,Milo M.K.Martin,Jonathan M.Smith10.Tamper Evident Microprocessors.Adam Waksman,Simha Sethumadhavan11.Side-Channel Leaks in Web Applications:a Reality Today,a Challenge Tomorrow.Shuo Chen,Rui Wang,XiaoFeng Wang Kehuan Zhang12.Investigation of Triangular Spamming:a Stealthy and Efficient Spamming Technique.Zhiyun Qian,Z.Morley Mao,Yinglian Xie,Fang Yu13.A Practical Attack to De-Anonymize Social Network Users.Gilbert Wondracek,Thorsten Holz,Engin Kirda,Christopher Kruegel14.SCiFI-A System for Secure Face Identification.(Best Paper)Margarita Osadchy,Benny Pinkas,Ayman Jarrous,Boaz Moskovich15.Round-Efficient Broadcast Authentication Protocols for Fixed Topology Classes.Haowen Chan,Adrian Perrig16.Revocation Systems with Very Small Private Keys.Allison Lewko,Amit Sahai,Brent Waters17.Authenticating Primary Users’Signals in Cognitive Radio Networks via Integrated Cryptographic and Wireless Link Signatures.Yao Liu,Peng Ning,Huaiyu Dai18.Outside the Closed World:On Using Machine Learning For Network Intrusion Detection.Robin Sommer,Vern Paxson19.All You Ever Wanted to Know about Dynamic Taint Analysis and Forward Symbolic Execution(but might have been afraid to ask).Thanassis Avgerinos,Edward Schwartz,David Brumley20.State of the Art:Automated Black-Box Web Application Vulnerability Testing.Jason Bau,Elie Bursztein,Divij Gupta,John Mitchell21.A Proof-Carrying File System.Deepak Garg,Frank Pfenning22.Scalable Parametric Verification of Secure Systems:How to Verify Ref.Monitors without Worrying about Data Structure Size.Jason Franklin,Sagar Chaki,Anupam Datta,Arvind Seshadri23.HyperSafe:A Lightweight Approach to Provide Lifetime Hypervisor Control-Flow Integrity.Zhi Wang,Xuxian Jiang24.How Good are Humans at Solving CAPTCHAs?A Large Scale Evaluation.Elie Bursztein,Steven Bethard,John C.Mitchell,Dan Jurafsky,Celine Fabry25.Bootstrapping Trust in Commodity Computers.Bryan Parno,Jonathan M.McCune,Adrian Perrig26.Chip and PIN is Broken.(Best Practical Paper)Steven J.Murdoch,Saar Drimer,Ross Anderson,Mike Bond27.Experimental Security Analysis of a Modern Automobile.K.Koscher,A.Czeskis,F.Roesner,S.Patel,T.Kohno,S.Checkoway,D.McCoy,B.Kantor,D.Anderson,H.Shacham,S.Savage 28.On the Incoherencies in Web Browser Access Control Policies.Kapil Singh,Alexander Moshchuk,Helen J.Wang,Wenke Lee29.ConScript:Specifying and Enforcing Fine-Grained Security Policies for JavaScript in the Browser.Leo Meyerovich,Benjamin Livshits30.TaintScope:A Checksum-Aware Directed Fuzzing Tool for Automatic Software Vulnerability Detection.(Best Student Paper)Tielei Wang,Tao Wei,Guofei Gu,Wei Zou31.A Symbolic Execution Framework for JavaScript.Prateek Saxena,Devdatta Akhawe,Steve Hanna,Stephen McCamant,Dawn Song,Feng MaoUSENIX Security20101.Adapting Software Fault Isolation to Contemporary CPU Architectures.David Sehr,Robert Muth,CliffBiffle,Victor Khimenko,Egor Pasko,Karl Schimpf,Bennet Yee,Brad Chen2.Making Linux Protection Mechanisms Egalitarian with UserFS.Taesoo Kim and Nickolai Zeldovich3.Capsicum:Practical Capabilities for UNIX.(Best Student Paper)Robert N.M.Watson,Jonathan Anderson,Ben Laurie,Kris Kennaway4.Structuring Protocol Implementations to Protect Sensitive Data.Petr Marchenko,Brad Karp5.PrETP:Privacy-Preserving Electronic Toll Pricing.Josep Balasch,Alfredo Rial,Carmela Troncoso,Bart Preneel,Ingrid Verbauwhede,Christophe Geuens6.An Analysis of Private Browsing Modes in Modern Browsers.Gaurav Aggarwal,Elie Bursztein,Collin Jackson,Dan Boneh7.BotGrep:Finding P2P Bots with Structured Graph Analysis.Shishir Nagaraja,Prateek Mittal,Chi-Yao Hong,Matthew Caesar,Nikita Borisov8.Fast Regular Expression Matching Using Small TCAMs for Network Intrusion Detection and Prevention Systems.Chad R.Meiners,Jignesh Patel,Eric Norige,Eric Torng,Alex X.Liu9.Searching the Searchers with SearchAudit.John P.John,Fang Yu,Yinglian Xie,Martin Abadi,Arvind Krishnamurthy10.Toward Automated Detection of Logic Vulnerabilities in Web Applications.Viktoria Felmetsger,Ludovico Cavedon,Christopher Kruegel,Giovanni Vigna11.Baaz:A System for Detecting Access Control Misconfigurations.Tathagata Das,Ranjita Bhagwan,Prasad Naldurg12.Cling:A Memory Allocator to Mitigate Dangling Pointers.Periklis Akritidis13.ZKPDL:A Language-Based System for Efficient Zero-Knowledge Proofs and Electronic Cash.Sarah Meiklejohn,C.Chris Erway,Alptekin Kupcu,Theodora Hinkle,Anna Lysyanskaya14.P4P:Practical Large-Scale Privacy-Preserving Distributed Computation Robust against Malicious Users.Yitao Duan,John Canny,Justin Zhan,15.SEPIA:Privacy-Preserving Aggregation of Multi-Domain Network Events and Statistics.Martin Burkhart,Mario Strasser,Dilip Many,Xenofontas Dimitropoulos16.Dude,Where’s That IP?Circumventing Measurement-based IP Geolocation.Phillipa Gill,Yashar Ganjali,Bernard Wong,David Lie17.Idle Port Scanning and Non-interference Analysis of Network Protocol Stacks Using Model Checking.Roya Ensafi,Jong Chun Park,Deepak Kapur,Jedidiah R.Crandall18.Building a Dynamic Reputation System for DNS.Manos Antonakakis,Roberto Perdisci,David Dagon,Wenke Lee,Nick Feamster19.Scantegrity II Municipal Election at Takoma Park:The First E2E Binding Governmental Election with Ballot Privacy.R.Carback,D.Chaum,J.Clark,J.Conway,A.Essex,P.S.Herrnson,T.Mayberry,S.Popoveniuc,R.L.Rivest,E.Shen,A.T.Sherman,P.L.Vora20.Acoustic Side-Channel Attacks on Printers.Michael Backes,Markus Durmuth,Sebastian Gerling,Manfred Pinkal,Caroline Sporleder21.Security and Privacy Vulnerabilities of In-Car Wireless Networks:A Tire Pressure Monitoring System Case Study.Ishtiaq Rouf,Rob Miller,Hossen Mustafa,Travis Taylor,Sangho Oh,Wenyuan Xu,Marco Gruteser,Wade Trappe,Ivan Seskar 22.VEX:Vetting Browser Extensions for Security Vulnerabilities.(Best Paper)Sruthi Bandhakavi,Samuel T.King,P.Madhusudan,Marianne Winslett23.Securing Script-Based Extensibility in Web Browsers.Vladan Djeric,Ashvin Goel24.AdJail:Practical Enforcement of Confidentiality and Integrity Policies on Web Advertisements.Mike Ter Louw,Karthik Thotta Ganesh,V.N.Venkatakrishnan25.Realization of RF Distance Bounding.Kasper Bonne Rasmussen,Srdjan Capkun26.The Case for Ubiquitous Transport-Level Encryption.Andrea Bittau,Michael Hamburg,Mark Handley,David Mazieres,Dan Boneh27.Automatic Generation of Remediation Procedures for Malware Infections.Roberto Paleari,Lorenzo Martignoni,Emanuele Passerini,Drew Davidson,Matt Fredrikson,Jon Giffin,Somesh Jha28.Re:CAPTCHAs-Understanding CAPTCHA-Solving Services in an Economic Context.Marti Motoyama,Kirill Levchenko,Chris Kanich,Damon McCoy,Geoffrey M.Voelker,Stefan Savage29.Chipping Away at Censorship Firewalls with User-Generated Content.Sam Burnett,Nick Feamster,Santosh Vempala30.Fighting Coercion Attacks in Key Generation using Skin Conductance.Payas Gupta,Debin GaoACM CCS20101.Security Analysis of India’s Electronic Voting Machines.Scott Wolchok,Erik Wustrow,J.Alex Halderman,Hari Prasad,Rop Gonggrijp2.Dissecting One Click Frauds.Nicolas Christin,Sally S.Yanagihara,Keisuke Kamataki3.@spam:The Underground on140Characters or Less.Chris Grier,Kurt Thomas,Vern Paxson,Michael Zhang4.HyperSentry:Enabling Stealthy In-context Measurement of Hypervisor Integrity.Ahmed M.Azab,Peng Ning,Zhi Wang,Xuxian Jiang,Xiaolan Zhang,Nathan C.Skalsky5.Trail of Bytes:Efficient Support for Forensic Analysis.Srinivas Krishnan,Kevin Z.Snow,Fabian Monrose6.Survivable Key Compromise in Software Update Systems.Justin Samuel,Nick Mathewson,Justin Cappos,Roger Dingledine7.A Methodology for Empirical Analysis of the Permission-Based Security Models and its Application to Android.David Barrera,H.Gunes Kayacik,Paul C.van Oorschot,Anil Somayaji8.Mobile Location Tracking in Metropolitan Areas:malnets and others.Nathanial Husted,Steve Myers9.On Pairing Constrained Wireless Devices Based on Secrecy of Auxiliary Channels:The Case of Acoustic Eavesdropping.Tzipora Halevi,Nitesh Saxena10.PinDr0p:Using Single-Ended Audio Features to Determine Call Provenance.Vijay A.Balasubramaniyan,Aamir Poonawalla,Mustaque Ahamad,Michael T.Hunter,Patrick Traynor11.Building Efficient Fully Collusion-Resilient Traitor Tracing and Revocation Schemes.Sanjam Garg,Abishek Kumarasubramanian,Amit Sahai,Brent Waters12.Algebraic Pseudorandom Functions with Improved Efficiency from the Augmented Cascade.Dan Boneh,Hart Montgomery,Ananth Raghunathan13.Practical Leakage-Resilient Pseudorandom Generators.Yu Yu,Francois-Xavier Standaert,Olivier Pereira,Moti Yung14.Practical Leakage-Resilient Identity-Based Encryption from Simple Assumptions.Sherman S.M.Chow,Yevgeniy Dodis,Yannis Rouselakis,Brent Waters15.Testing Metrics for Password Creation Policies by Attacking Large Sets of Revealed Passwords.Matt Weir,Sudhir Aggarwal,Michael Collins,Henry Stern16.The Security of Modern Password Expiration:An Algorithmic Framework and Empirical Analysis.Yinqian Zhang,Fabian Monrose,Michael K.Reiter17.Attacks and Design of Image Recognition CAPTCHAs.Bin Zhu,JeffYan,Chao Yang,Qiujie Li,Jiu Liu,Ning Xu,Meng Yi18.Robusta:Taming the Native Beast of the JVM.Joseph Siefers,Gang Tan,Greg Morrisett19.Retaining Sandbox Containment Despite Bugs in Privileged Memory-Safe Code.Justin Cappos,Armon Dadgar,JeffRasley,Justin Samuel,Ivan Beschastnikh,Cosmin Barsan,Arvind Krishnamurthy,Thomas Anderson20.A Control Point for Reducing Root Abuse of File-System Privileges.Glenn Wurster,Paul C.van Oorschot21.Modeling Attacks on Physical Unclonable Functions.Ulrich Ruehrmair,Frank Sehnke,Jan Soelter,Gideon Dror,Srinivas Devadas,Juergen Schmidhuber22.Dismantling SecureMemory,CryptoMemory and CryptoRF.Flavio D.Garcia,Peter van Rossum,Roel Verdult,Ronny Wichers Schreur23.Attacking and Fixing PKCS#11Security Tokens.Matteo Bortolozzo,Matteo Centenaro,Riccardo Focardi,Graham Steel24.An Empirical Study of Privacy-Violating Information Flows in JavaScript Web Applications.Dongseok Jang,Ranjit Jhala,Sorin Lerner,Hovav Shacham25.DIFC Programs by Automatic Instrumentation.William Harris,Somesh Jha,Thomas Reps26.Predictive Black-box Mitigation of Timing Channels.Aslan Askarov,Danfeng Zhang,Andrew Myers27.In Search of an Anonymous and Secure Lookup:Attacks on Structured Peer-to-peer Anonymous Communication Systems.Qiyan Wang,Prateek Mittal,Nikita Borisov28.Recruiting New Tor Relays with BRAIDS.Rob Jansen,Nicholas Hopper,Yongdae Kim29.An Improved Algorithm for Tor Circuit Scheduling.Can Tang,Ian Goldberg30.Dissent:Accountable Anonymous Group Messaging.Henry Corrigan-Gibbs,Bryan Ford31.Abstraction by Set-Membership—Verifying Security Protocols and Web Services with Databases.Sebastian Moedersheim。

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.18, No.10, October 2007, pp.2516−2527 DOI: 10.1360/jos182516 Tel/Fax: +86-10-62562563© 2007 by Journal of Software. All rights reserved.∗一种实时动态数据库故障恢复策略肖迎元1+, 刘云生2, 廖国琼3, 邓华锋21(天津理工大学计算机科学与工程系,天津 300191)2(华中科技大学计算机科学与技术学院,湖北武汉 430074)3(西门子有限公司西门子中国研究院,北京 100102)A Real-Time Dynamic Database Crash Recovery StrategyXIAO Ying-Yuan1+, LIU Yun-Sheng2, LIAO Guo-Qiong3, DENG Hua-Feng21(Department of Computer Science and Engineering, Tianjin University of Technology, Tianjin 300191, China)2(School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China)3(China Corporate Technology, Siemens Limited, Beijing 100102, China)+ Corresponding author: Phn: +86-22-23679366, E-mail: xiaoyingyuan_hust@Xiao YY, Liu YS, Liao GQ, Deng HF. A real-time dynamic database crash recovery strategy. Journal ofSoftware, 2007,18(10):2516−2527. /1000-9825/18/2516.htmAbstract: Distributed real-time main memory databases are usually applied in some time-critical applications. Forthese applications, rapid and efficient recovery in the event of site crash is very important. Firstly, throughanalyzing the recovery requirements of failure in distributed real-time main memory databases, the recoverycorrectness criteria of distributed real-time main memory database are presented. Then, a real-time dynamic crashrecovery scheme based on log (RTDCRS) is presented, and the correctness of RTDCRS is proved. RTDCRS adoptsthe real-time logging scheme integrating the characteristics of partitioned logging, ephemeral logging and usesnonvolatile high-speed store as logging storage area in order to reduce the logging cost during the normal running.After a site crash, a dynamic recovery strategy based on classification recovery idea is adopted to decrease thedowntime. Performance tests and evaluations results show that RTDCRS has better performances than thetraditional recovery schemes in two aspects: The missing deadlines ratio of transactions and the time of systemdenying services after crashes.Key words: distributed real-time main memory database; failure recovery; orthogonal partition; transaction class;dynamic recovery摘要: 分布式实时内存数据库通常使用在时间关键型应用中,对这些应用而言,故障后能迅速而有效地恢复是至关重要的.首先通过分析分布式实时内存数据库故障恢复需求,给出了其恢复正确性准则.然后提出了一种基于日志的实时动态故障恢复模式RTDCRS(real-time dynamic crash recovery scheme),并证明了其正确性.RTDCRS采用了集成分区日志和短暂日志特性的实时日志模式,同时使用非易失性高速存储设备作为日志存储区,以尽可能地降低∗ Supported by the National Natural Science Foundation of China under Grant No.6073045 (国家自然科学基金); the DefensePre-Research Project of the ‘Tenth Five-Year-Plan’ of China under Grant No.413150403 (国家“十五”国防预研基金)Received 2006-06-15; Accepted 2006-08-22肖迎元等:一种实时动态数据库故障恢复策略2517系统正常运行时日志代价.在站点故障后的恢复策略上,给出了基于分类恢复思想的动态恢复策略,以尽可能地减少故障站点停止服务的时间.性能测试结果显示,RTDCRS在事务错过截止期比率和站点停止服务时间两方面与传统的故障恢复模式相比具有明显的优越性.关键词: 分布式实时内存数据库;故障恢复;正交分划;事务类;动态恢复中图法分类号: TP311文献标识码: A一类应用,如工业过程控制、电网调度、军事作战指挥系统等,需要分布式实时数据库系统的支持.分布式实时数据库系统(distributed real-time database systems,简称DRTDBS)是分布式数据库系统和实时数据库系统相结合的产物,是事务和数据都可以具有定时限制的分布式数据库系统.在DRTDBS中,事务的定时限制典型地表现为事务有截止期限制.一个实时事务若在规定的截止期后(超截止期)完成,结果将变得毫无价值(对固实时事务),甚至还可能带来灾难性的后果(对硬实时事务).DRTDBS通常处理两类数据:实时数据和持久数据.实时数据仅在其有效期内有效,过期的实时数据将变为无效.持久数据在它的整个生命周期内始终有效.为了更好地满足事务和数据的定时限制,DRTDBS通常需要内存数据库技术提供支持.内存数据库(main memory databases,简称MMDB)要求数据库工作版本(main databases,简称MDB)常驻内存,外存版本(secondary databases,简称SDB)作为内存版本的备份.MMDB确保事务执行过程中的所有读、写操作都是针对内存版本,即事务执行过程中无数据I/O[1].我们将集成了MMDB技术的DRTDBS称为分布式实时内存数据库系统(distributed real-time main memory databases,简称DRTMMDBS).DRTMMDBS集成了分布式数据库、实时数据库和内存数据库的能力,但并非三者在概念、技术、机制上的简单组合,而有一系列问题需要研究和解决,如事务调度、并发控制、故障恢复等.分布式环境本身的复杂性加上内存的易失性和脆弱性,使得相对于基于磁盘的集中式数据库而言, DRTMMDBS发生故障的可能性更大.当系统故障发生,在恢复正常服务之前,许多实时事务可能错过它们的截止期,大量实时数据将变得无效.因此故障发生后,能迅速而有效地恢复对DRTMMDBS而言有至关重要的意义.目前,对于DRTMMDBS故障恢复技术的相关研究不多,已有的工作主要是针对单一的分布式数据库、实时数据库、内存数据库的恢复策略和技术的研究.在实时数据库方面,Choi等人给出了一种采用双CPU的并行处理结构,一个CPU(database processor,简称DP)负责正常的事务处理,而另一个CPU(recovery processor,简称RP)专门负责有关恢复处理,如记日志、做检验点以及故障后进行数据库恢复.该方法提高了系统性能,但RP的利用率不高.此外,如何进行负载平衡是该结构应解决的问题[2].针对传统的基于磁盘的顺序、持久日志恢复方法的低效问题,分区日志思想[3]和短暂日志[4,5]技术分别被提了出来.分区日志采用将事务日志基于事务类(或数据类)分区存放,即不同类的事务(或数据)的日志记录在不同的分区.分区日志能够避免单一日志存储区因为严重的访问竞争而导致的系统性能瓶颈问题.然后,如何对事务(或数据)进行分类、如何确定日志分区的准则、如何确保故障后能将数据库恢复到正确、一致的状态是该策略必须加以研究和解决的问题.短暂日志不需要持久地保留日志记录,短暂日志要求事务提交时将其更新强制刷新到稳定的存储设备中,这样,事务一旦提交即可将其日志记录删除.其优点是大大缩短了故障后恢复时日志处理的时间,而缺点是缺乏持久日志记录,不利于审计跟踪.Liu[6]和Panda[7]分别研究了故障后加快恢复处理速度的技术,但这些技术都需要在整个故障恢复期间停止系统服务.针对内存数据库,基于影子的恢复技术被提了出来[8−10],该技术的优点是消除了日志开销,恢复速度快,缺点是在事务生命周期内数据库需维持其更新数据页的两个版本——当前页和影子页,同时需维护大量的页表指针.本文通过分析DRTMMDBS的故障恢复需求,给出了DRTMMDBS恢复正确性准则.在此基础上,提出了适合DRTMMDBS的充分考虑了数据和事务的定时限制的基于日志的动态恢复模式.1 故障恢复需求和恢复正确性准则在分析DRTMMDBS的故障恢复需求之前,我们先给出如下定义:2518 Journal of Software软件学报 V ol.18, No.10, October 2007定义1. 实时数据对象X定义为一个三元组:X::=〈V(X),ST(X),VI(X)〉.其中,V(X)表示X的当前状态或值;ST(X)表示采样时标,即采样X对应的外部世界对象的时间;VI(X)表示X的有效期,即自ST(X)算起V(X)具有有效性的时间长度.根据上述定义,持久数据可看成是VI(X)取无穷大时的实时数据.定义2. 一个数据对象X被称为满足时态一致性,如果有:ST(X)+VI(X)≥T c.这里,T c表示当前时刻.DRTMMDBS中事务和数据的定时限制及分布特性对恢复策略、技术提出了下述需求[11]:(1) 恢复必须考虑数据的定时限制和存取频率,如有效期紧迫的数据及存取频率高的“热点”数据应优先恢复;(2) 恢复也需要考虑事务的定时限制,如高优先级事务所需存取的数据应优先恢复;(3) 恢复除了要考虑数据库的逻辑(内部)一致性以外,数据的时态一致性也必须被确保;(4) 除了数据库状态的恢复以外,由夭折事务导致的外部世界状态的改变也必须被恢复;(5) 恢复必须结合一定的提交协议以确保分布式实时事务故障的原子性;(6) 恢复必须考虑内存数据库的特性和要求;(7) 快速且有效的恢复,以保证故障发生后事务错过截止期的比率并不会显著增加.基于上述故障恢复需求,我们给出了DRTMMDBS的如下恢复正确性准则:准则1(实时数据恢复准则). 在故障恢复时,对于实时数据对象X,若ST(X)+VI(X)≤T c,则对X的所有更新操作,无论对应的事务提交与否,都无须进行REDO或UNDO恢复,而通过重新从外界环境采样进行恢复.准则1要求对于过期的实时数据采用重新从外界环境采样进行恢复,以确保数据的时态一致性.DRTMMDBS通过两种方式直接与外部世界交互作用:一是关于外部世界状态或事件的信息被记录到数据库中;二是事务可以启动各种影响外部世界的活动.为此,在DRTMMDBS中有如下事务分类:(1) 数据采样事务:记录外部世界的状态或发生的事件到数据库中.它是简单的只写事务.(2) 数据处理事务:类似于传统数据库中的事务,用来执行用户或应用程序发起数据库操作请求.(3) 控制事务:能触发外部世界中相关活动的事务.控制事务通过向受控子系统发送控制消息,来触发改变外部世界的活动.在DRTMMDBS中,控制事务的执行将引发外部世界相应的活动.对于已提交的控制事务引发的外部世界状态的改变无须恢复,而对夭折的控制事务所引发的改变外部世界状态的活动,则必须执行相应的补偿或替代事务进行复原.下文中用符号AT表示控制事务T所引发的活动;AT ′表示AT的补偿或替代事务.准则2(外部世界状态恢复准则). 若控制事务T夭折,AT已发生,则执行AT ′以恢复外部世界状态.分布式实时事务的执行被分解为多个分布在不同站点的实时子事务的协同执行,因此要确保分布式实时事务的原子性就必须保证构成分布式实时事务的所有实时子事务要么全提交,要么全不提交,即使故障发生.假定分布式实时事务T={ST1,ST2,…,ST i,…,ST m},这里,ST i(1≤i≤m)表示构成T的在站点i执行的实时子事务.准则3(分布式实时事务REDO恢复准则). 在故障时刻,若分布式实时事务T已提交,则在故障站点i根据需要执行REDO恢复操作以确保ST i的效果.对于准则3,下述两种情况,无须执行REDO恢复:(1) ST i所更新的数据对象的后映像已被物理地写入数据库;(2) ST i所更新的数据对象满足ST(X)+VI(X)≤T c.对于(2),通过执行采样事务进行恢复.准则4(分布式实时事务UNDO恢复准则). 在故障时刻,若分布式实时事务T未提交,则对所有的ST i(1≤i≤m)在相应站点根据需要执行UNDO恢复.对于准则4,下述两种情况,ST i无须执行UNDO恢复:(1) ST i所更新的数据对象的后映像还未被物理地写入数据库;肖迎元 等:一种实时动态数据库故障恢复策略2519(2) ST i 所更新的数据对象满足ST (X )+VI (X )≤T c . 2 实时动态故障恢复模式就故障恢复而言,DRTMMDBS 需要处理各种不同类型的故障,如通信故障、网络分割、站点故障(系统故障)等.本文主要考虑站点故障(crash).站点故障造成故障站点易失性主存数据丢失(MDB 遭到破坏),系统非正常终止,从而导致一些已提交事务(效果已写入MDB,但未写出到SDB)的效果丢失.同时,站点故障可能影响到分布式实时事务的原子性.此外,在恢复服务之前,站点故障还可能导致许多实时事务错过它们的截止期,大量实时数据变得无效.在前面分析的DRTMMDBS 故障恢复需求和恢复正确性准则的基础上,针对站点故障,本文提出了一种实时动态故障恢复模式(real-time dynamic crash recovery scheme,简称RTDCRS).2.1 实时日志模式传统的顺序日志模式将日志记录存储在单一的日志文件中,日志文件会因为严重的访问竞争而成为系统性能的瓶颈,这显然不能满足DRTMMDBS 对实时性能的需求.本文给出了基于非易失RAM(random access memory)的、集成分区日志和短暂日志特性的实时日志模式,后文中将该日志模式简记为NRPERTL.2.1.1 基于分区日志的事务类的划分NRPERTL 采用了日志存储区分区的思想,即根据事务类的划分策略,将日志存储区分成对应的不同分区,属于不同类别的事务的日志记录被分别存储在不同的日志分区,从而可以避免单一日志文件导致的系统性能瓶颈.分区日志根据事务类的划分策略将日志存储区分成对应不同分区,因此,事务分类策略就决定了日志的分区方法.在DRTMMDBS 中,事务具有丰富的语义特征,可以按不同的特征来进行分类,本文从日志分区的角度来考虑事务划分策略.单一的分区日志技术对事务类的划分策略并无太多的要求,然而RTDCRS 在故障后的恢复处理策略上采用了分类恢复的思想,为了确保故障后能将数据库恢复到正确、一致性状态,基于分区日志的事务类划分就必须遵循一定的原则.下面的定义中,用ST 表示所有可能事务的集合;ST i 表示ST 的一个子集;DS (T )表示事务T 存取的数据对象的集合;DS (ST i )表示ST i 中所有事务可能存取的数据对象的集合;LS 表示日志存储区;SA (T )表示事务T 的日志记录的存储区域.定义3. 假定ST 1,ST 2 ⊆ST ,若ST 1∩ST 2=∅,则称ST 1和ST 2互斥.记为ST 1⊥ST 2.定义4. 假定ST 1,ST 2,…,ST n ⊆ST ,若对任意的ST i ,ST j ,1≤i ≤n ,1≤j ≤n ,有ST i ⊥ST j ,则称集合{ST 1,ST 2,…,ST n }为ST 的互斥集.定义5. 假定{ST 1,ST 2,…,ST n }为一互斥集,若有ST 1∪ST 2∪…∪ST n =ST ,则称{ST 1,ST 2,…,ST n }为ST 的一个分划(分类).其中,ST i ,1≤i ≤n ,称为一个事务类.定义6. 假定LS 1,LS 2,…,LS n ⊆LS ,若对任意的LS i ,LS j ,1≤i ≤n ,有LS i ∩LS j =∅,则称集合{LS 1,LS 2,…,LS n }为LS 的互斥集.定义7. 假定π={ST 1,ST 2,…,ST n }为ST 的一个分划,µ={LS 1,LS 2,…,LS n }为LS 的一个互斥集,若存在双射(一一映射)f :π→µ,则称µ为关联分划π的LS 的一个分区,LS i (1≤i ≤n )称为一个子日志区.其中,f 表示∀ST i ∈π有且只有一个LS i ∈µ使得∀T ∈ST i 都有SA (T )⊆LS i ,且反之也成立.定义8. {ST 1,ST 2,…,ST n }被称为ST 的一个正交分划,若{ST 1,ST 2,…,ST n }为ST 的一个分划且∀ST i ,ST j ∈{ST 1, ST 2,…,ST n },有DS (ST i )∩DS (ST j )=∅.原则1. 为了确保故障后能将数据库恢复到正确、一致性状态,RTDCRS 要求日志分区所关联的ST 的分划 π={ST 1,ST 2,…,ST n }满足条件:∃π1={,,…,}⊂π,(DS (π1k ST 2k ST j k ST 1)∩DS (π2))=∅.这里,π2=ST −π1.我们称满足原则1中条件的分划为规范化分划.2520Journal of Software 软件学报 V ol.18, No.10, October 2007定理1. 若{π1,π2}是ST 的一个正交分划,{,,…,}是π1k ST 2k ST j k ST 1的一个分划,{,,…,}是π1m ST 2m ST i m ST 2的一个分划,则{,,…,,,,…,}为一规范化分划.1k ST 2k ST j k ST 1m ST 2m ST i m ST 证明:因为{π1,π2}是一正交分划,所以有DS (π1)∩DS (π2)=∅.因此,要证明{,,…,,,,…, }为一规范化分划,根据规范化分划的定义,只需证明{,,…,,,,…,}为一分划.由{π1k ST 2k ST j k ST 1m ST 2m ST i m ST 1k ST 2k ST j k ST 1m ST 2m ST i m ST 1,π2}是一正交分划可得π1∪π2=ST ,π1∩π2=∅.又因为{,,…,}是π1k ST 2k ST j k ST 1的一个分划,所以∪ ∪…∪=π1k ST 2k ST j k ST 1且∀ST u ,ST v ∈π1,ST u ∩ST v =∅,同理,有∪∪…∪=π1m ST 2m ST i m ST 1且∀ST u ,ST v ∈π2,ST u ∩ST v =∅.由此可得∪∪…∪∪∪∪…∪=ST 且∀ST 1k ST 2k ST j k ST 1m ST 2m ST i m ST u ,ST v ∈{,,…,,,,…, },ST 1k ST 2k ST j k ST 1m ST 2m ST i m ST u ∩ST v =∅,即{,,…,,,,…,}为ST 的一个分划.从而定理得证. □1k ST 2k ST j k ST 1m ST 2m ST i m ST 根据定理1,可以容易地构造出规范化分划.下面具体给出一种构造方法.首先将ST 按事务优先级划分成两个子集:ST >p ={T i |Pr(T i )>p ,T i ∈ST }和ST <=p ={T i |Pr(T i )≤p ,T i ∈ST },这里,Pr(T i )表示事务T i 的优先级.显然,{ST >p ,ST <=p }为ST 的一个分划.通过适当地调整p 的值,可使DS (ST >p )∩DS (ST <=p )=∅(最坏的情况ST >p 和ST <=p 中有一个为∅),即{ST >p ,ST <=p }为ST 的一个正交分划.DS (ST >p )为属于ST >p 中的高优先级事务所存取的数据对象的集合,我们称DS (ST >p )为关键数据类,称ST >p 为关键事务类;DS (ST <=p )为属于ST <=p 中的低优先级事务所存取的数据对象的集合,我们称其为一般数据类,称ST <=p 为一般事务类.进一步地,我们将ST >p 划分成两个(也可为多个)子集:ST >p ,>f = {T i |Fr (T i )>f ,T i ∈ST >p }和ST >p ,<=f ={T i |Fr (T i )≤f ,T i ∈ST >p },这里,Fr (T i )代表T i 的估计执行频率,f 为一设定的频率值.显然,{ST >p ,>f ,ST >p ,<=f }是ST >p 的一个分划.类似地,可将ST <=p 划分成两个(也可为多个)子集:ST <=p ,>f ={T i |Fr (T i )>f , T i ∈ST <=p }和ST <=p ,<=f ={T i |Fr (T i )≤f ,T i ∈ST <=p }.显然,{ST <=p ,>f ,ST <=p ,<=f }是ST <=p 的一个分划.令σ={ST >p ,>f ,ST >p ,<=f , ST <=p ,>f ,ST <=p ,<=f },则根据定理1,σ是一个规范化分划.后文中,NRPERTL 和动态恢复策略的描述都是基于σ.2.1.2 存储介质的组织如图1所示,每个站点的存储介质分为3层:磁盘存储器、非易失RAM 、易失RAM(主存).本地外存数据库(local secondary databases,简称LSDB)被存储在磁盘存储器中.非易失RAM 作为日志存储区,对应于规范化分划σ,整个日志存储区被划分成4个独立的子日志区:关键高频事务类子日志区、关键低频事务类子日志区、一般高频事务类子日志区和一般低频事务类子日志区,分别简记为:LS ch ,LS cl ,LS gh 和LS gl ,它们分别用来对应地存储ST >p ,>f ,ST >p ,<=f ,ST <=p ,>f 和ST <=p ,<=f 事务类的日志记录,即{LS ch ,LS cl ,LS gh ,LS gl }是关联规范化分划σ的日志存储区的一个分区.我们将LS ch 和LS cl 统称为关键日志区;LS gh 和LS gl 统称为一般日志区.本地内存数据库(local main databases,简称LMDB)被存储在易失性主存中,并且被分成两个独立的分区:关键数据分区和一般数据分区,用来分别存储关键数据类和一般数据类.为了充分利用非易失性日志存储空间,我们采用空间动态分配策略,即在系统初始化时为每一子日志区分配一定数量的日志存储区空间,在系统运行过程中,当某一子日志区没有足够的空间存储对应事务类的日志记录时,系统为它分配一个新的日志页,属于同一子分区的日志页被链接在一起. LSDB LSDB LSDB LSDBGeneral data partition Critical data partitionDiskstorages Volatile main memory Nonvolatile RAM LS glLS gh LS cl LS chFig.1 Storage media organization at a site图1 单个站点存储介质的组织肖迎元等:一种实时动态数据库故障恢复策略25212.1.3 实时日志记录类型与结构数据库更新策略(包括延迟更新和立即更新)对日志处理有很大的影响.立即更新可能产生“脏数据”,从而导致串联夭折(cascading abort),严重影响系统性能.因此,DRTMMDBS通常采用延迟更新策略.对于延迟更新策略,由一事务更新了的数据对象的值直到该事务提交才真正反映到LMDB.因此,若采用延迟更新策略,故障后恢复处理时,UNDO操作不再需要.后文中,我们假定延迟更新策略被采用.结合实时提交协议1PRCP(one-phase real-time commit protocol)[12],我们设计5种日志记录类型:Begin,Redo,Compensate,Ready和Commit,如图2所示.其中,P-TID表示分布式事务(全局事务)标识,定义为P-TID::=〈Cor_Addr,N〉,这里,Cor_Addr表示分布式事务的协调者的网络地址;N代表分布式事务的序号,在每个协调者站点,N是单调递增的.对于本地事务,P-TID被置为NULL.TID为本地事务或子事务标识,定义为TID::=〈Addr,SN〉,这里,Addr表示本地事务或子事务所在站点的网络地址;SN表示本地事务或子事务的序号,在每个站点SN是单调递增.B,D,CP,R和C用来分别表示Begin,Redo,Compensate,Ready和Commit这5种日志记录类型.TS表示Redo或Compensate或Commit类型日志记录创建时刻的逻辑时标.在每个站点,逻辑时标的初始值置为0,每当一条Redo或Compensate或Commit日志记录或后文介绍的检验点日志记录被创建,逻辑时标的值增加1.RID代表被更新数据对象的标识.BN表示与LMDB中数据页相对应的LSDB中数据块的逻辑块号.AI表示被更新数据对象的后映像.VTI表示实时数据对象的最大有效时刻,即VTI=ST(X)+VI(X).对持久数据对象而言,其VTI 置为无穷大.CA表示控制事务所对应的补偿活动.Fig.2 Types and structures of real-time log record图2 实时日志记录的类型与结构当一个事务开始执行时,在执行站点,一条Begin日志记录在对应的子日志区被创建;对每一个更新操作,对应的Redo日志记录被创建;当一个控制事务向受控子系统发送控制信息时,相应的Compensate日志记录被创建;在参与者站点,当一个子事务进入了准备提交状态且未超截止期,一条相应的Ready日志记录在该参与者站点被创建;当一个分布式事务的协调者在限定时间内收到来自所有参与者的Vote-Commit消息时,在协调者站点,相应的Commit日志记录被创建;当一个子事务收到来自协调者的Global Commit决定时,在其所在站点,相应的Commit日志记录被创建.2.2 本地检验点模式检验点的目的是在辅助存储设备中维持数据库的最近版本、确定恢复起始点以及限制故障恢复时间.在RTDCRS中,每个站点独立地执行本地检验点(在后文中,检验点指的都是本地检验点).在检验点执行过程中, LMDB的更新被写出到LSDB,同时,一些无用的日志记录被删除以释放相应的日志存储空间.由于检验点的执行涉及到大量的磁盘I/O,故检验点模式(静态或模糊)和执行频率对系统性能有很大的影响.静态检验点要求在将LMDB的更新写出到LSDB的过程中不允许存在活跃的事务,这显然不利于DRTMMDBS中事务和数据的时限满足,因此,RTDCRS采用模糊检验点模式.此外,在检验点触发时机上,RTDCRS不是采用固定时间间隔的周期性触发策略,而是根据日志存储区空间使用率(简记为R LU)是否到达设定的阈值α来决定是否触发检验点.当R LU 大于α时,检验点被触发执行.α的初始值可根据应用的要求预先设定,在系统运行过程中可以通过修改α的值来动态调整检验点执行的频率.当检验点执行时,检验点日志记录被写入系统在非易失性RAM中为检验点日志记录分配的独立存储空2522 Journal of Software软件学报 V ol.18, No.10, October 2007间.检验点日志记录包括5个部分:检验点位域(CKB)、关键事务类恢复起始时标(CTRST)、一般事务类恢复起始时标(GTRST)、检验点时标(CKT)和更新页域(UPF).CKB用来表示本次检验点是否成功完成:CKB取值为1表示成功完成,为0表示检验点执行过程中发生系统故障.CTRST表示故障后需要执行REDO恢复操作的关键事务类的最小TS(逻辑时标值),而GTRST表示故障后需要执行REDO恢复操作的一般事务类的最小TS(逻辑时标值).CKT表示检验点被触发时的逻辑时标.UPF为LMDB中的每一数据页设置一个更新位(updating bit)来记录该页的更新状态,该位为0表示自上次检验点后该页还未被更新;该位为1表示自上次检验点后该页已被更新.检验点执行过程可描述如下:Procedure LocalCheckpoint()1: CKB=0;2: CKT=TCounter++;3: Write data pages updated by committed transaction out to LSDB;4: Set UPF according to updating state of data page;5: Write the data pages whose upadting bits are 1 out to LSDB;6: Delete useless log records, i.e. the log records of aborted transactions or whose logic timestamp in Commit log records is not larger than CKT, and free the corresponding logging store spaces;7: Get the minimal logging timestamp of critical transaction class, set the value of CTRST;8: Get the minimal logging timestamp of ordinary transaction class, set the value of GTRST;9: CKB=1;在上面的描述及后面的恢复处理的算法描述中,TCounter用来表示逻辑时标计数器,其初始值置为0,每当一条Redo或Compensate或Commit或检验点日志记录被创建,其值加1.系统在非易失性RAM中为TCounter 分配相应的存储空间.2.3 动态恢复处理策略在站点故障后的恢复处理过程中,首先,LSDB被装入主存并重建LMDB;然后,恢复子系统负责将LMDB恢复到最近的一致性状态.为了提高系统性能,RTDCRS给出了基于分类恢复思想的动态恢复处理策略,动态恢复处理策略以前面提出的NRPERTL日志模式为基础,其关键特征是:关键数据类被首先恢复,在恢复一般数据类之前恢复站点服务,然后边服务边恢复一般数据类,以最大限度地降低故障站点停止服务的时间.结合实时提交协议1PRCP,动态恢复策略能够确保分布式事务故障的原子性.动态恢复策略具体包括如下几个步骤:(1) 从LSDB中将关键数据类装入主存相应数据分区,重建LMDB;(2) 消除属于关键事务类的夭折的控制事务导致的对外部世界改变,并将关键数据类恢复到最近一致性状态;(3) 恢复故障站点的服务;(4) 从LSDB中将一般数据类装入主存相应数据分区;(5) 消除属于一般事务类的夭折的控制事务导致的对外部世界改变,并将一般数据类恢复到最近一致性状态.在上面的步骤中,步骤(2)和步骤(5)的实现算法可统一描述如下:Procedure CrashRecovery(char dc)Input: dc denotes the data class asking to be recovered, and dc=“C” stands for critical data class, while dc=“G” stands for general data class.1: FT=TCounter;2: if (dc=“C”) then3: RST=CTRST;4: Scan the critical logging partition (including LS ch and LS cl) to look for all Compensate log reords。

1:Groupware systemsGroupware systems use computers and networksto facilitate collaborative working. Withreference to shared data objects they may becontrasted with, for example, distribu teddatabases where the emphasis is on protectingand hiding the actions of concu rrent u sers fromeach other. A popu lar su mmation of possiblegrou pware interaction modes is illu strated inFigu re 1.SamePlace Different PlacesFigure 1.For example, electronic mail belongs to the lowerright qu adrant, video conferencing to the lowerleft, traditional group meetings to the upper leftand bulletin boards to the upper right. Englebartarg u es that what really matters isinteroperability and that any effective groupwaremu st su pport all modes as in practice thesequ adrant bou ndaries are rou tinely crossed [1].Systems belonging to the left hand colu mn maybe described as real time and those belonging tothe lower left quadrant as distributed real time.In the next section we explain why distribu tedreal time systems are of particular interest.2:RequirementsReal time distribu ted grou pware (same time,different places) is likely to place the heaviestdemands on system constru ction. For examplesynchronisation at the u ser interface (UI) levelcannot simply be mapped onto an u nderlyingsynchronou s compu ter network protocol as widearea message delays can lead to u nacceptablyslow response times at the local UI.This interaction mode is of particu lar interesthowever, not because it is difficult to implement,but because it satisfies most of the requirementsof other modes and is therefore the mostgenerally u sefu l form of grou pware. If a participant in a shared editing session leaves for an hou r and then rejoins they are effectively expecting the application to cope with asynchronou s interaction - a possibility that cannot be ignored.We identify the following requ irements:•Responsiveness Users working on a shared document with tools su ch as text editors expect the same response time they get from a single u ser version.Failu re to provide good response time is likely to result in reluctance to use the software. With respect to the integrity of shared replicated objects database protocols su ch as two-phase commit and two-phase locking are likely to be inappropriate becau se of their impact on response time. For example, the Argu s system[3] integrated database techniques into a programming langu age intended for u se in application construction but an attempt to build a shared docu ment editor, CES[4], with Argu s fru strated researchers: "...in ou r initial experiments with the editor, response time was slow enou gh for the editor to be u nu sable in realistic testing...." [4].•Concurrency controlEven in a small grou p, the problems of u nprincipled parallel compu tation can occu r.These inclu de:•deadlock •termination •non-fairness •starvation It is essential for grou pware to adopt a concurrency control policy. In the terms of the readers/writers problem the policy mu st deal with many readers, many writers.•Correctness The application mu st be able to maintain complete consistency between all instances of a shared object. It is qu ite possible for a mu lti-user application to appear correct in typical use but to fail under unusual conditions. A formal model is therefore highly desirable so that thelogic of the algorithm can be separated fromimplementation related problems. Forexample, a popu lar make of workstationbu ndles a mu lti-u ser, mu lti-view calendarmanager with its desktop u tilities and waxeslyrical about its usefulness as groupware. Thedistribu ted calendar management protocolallows u sers to qu ery and u pdate each otherscalendars and provides overlapping views tofacilitate the finding of a free time to su it agroup. Most of the time the application works asone might expect. If, however, two users attemptto book the same free slot at the same time, oneach others calendar, the application exits onboth workstations. When restarted theapplication presents two different versions ofthe ou tcome to the two u sers. Neither arenotified that a clash has occu rred and thesystem is now in an inconsistent state. Is this a fault of the implementation or the design?•Non-serialisable operations supportSerialisability is a well understood structuringconcept u sed to allow the safe interleaving ofconcu rrent operations. Correctness is oftenattrib u ted to systems if they exhibitserialisability. Unfortu nately in grou pwaresystems serialisability does not always providethe correct outcome. We illustrate the problemwith two types of operations: updates on valuesand updates on references.Non-serialisable u pdates on shared valu es:A text string variable has value "abcd" and theoperation "delete character 3" is applied to its twoinstances concu rrently at two sites; noserialised application of the overlappingoperations will result in the expected outcomei.e. "abd". The conflict must be detected andresolved. A solution here could be to reject oneof the operations.Non-serialisable u pdates of shared references:The problem above does not appear to arise ifthe variable is a reference rather than avalu e. For example, when the contents of aspreadsheet cell are deleted twice in anyorder then the ou tcome is correct. Similarproblems do arise, however, if the operationis a move or copy on the contents of areference. Su ppose the contents of a spreadsheet cell, reference C3, are moved to references C4 and D3 at the same time; in this case no serialisation can achieve consistency. As before, one of the operations could be rejectedto solve the problem.•Divergence handling How shou ld conflict leading to divergence be handled? The rou tine enforcement of system wide consistency by rejecting one operation in preference to another is not always appropriate.A policy which simply rejects one of two conflicting operations may throw away valu able information. For example a shared calendar system cou ld handle conflicting schedu les by overlaying them while clearly flagging the u ser that a divergence has occu rred. Participants can then decide to attend one meeting in preference to another or a proposer may choose to reschedule.•Fault tolerance In a distributed system the probability of failure increases with the nu mber of participating nodes. If a shared data object is replicated at each node however it is possible to construct a recovery scheme. In practice there may be little perceptible difference to a grou p of u sers between an inactive participant and one whose workstation has crashed. A more seriou s problem is cau sed by Byzantine failu res i.e.where a fa u lty node behaves in an u npredictable and disru ptive fashion.•Effective realisation The sol tion m st work with existing technology. As cu rrent network interconnect speeds are relatively slow compared with local workstation processing capabilities non-blocking and non-locking strategies are more likely to provide good response time to interactive users. If the system is to be scalable i.e. capable of incremental growth, it is essential that global synchronisation is u sed sparingly, if at all. In other words, the concu rrency control method mu st exhibit a high degree of locality.The requ irements list forms the basis of an evalu ation framework for synchronisation andconcurrency control policies. This paper will nothowever pursue issues relating to fault tolerance or divergence handling. We now go on to look at two approaches to meeting these requ irements: dOPT [5], and EDITS.3:dOPT: the distributed operation transformationdOPT is originally and fu lly described in [5]. The algorithm attempts to meet all the requ irements listed in the previou s section with the exceptions of fault tolerance and divergence handling. Existing dOPT based applications inclu de Grove [6], a shared docu ment ou tliner, and CoEd [7], a shared text editing system. Our practical experience with dOPT is based on the implementation of MUSST, a mu ltiu ser sharedspreadsheet which ru ns on networkedworkstations [8].3.1 The dOPT groupware modelA groupware system is modelled as a set of sites with u niqu e ids and a set of parameterised operations. Operations are application specific: O = <O1, O2,...O n>. For example, a text edit operation may take the form O3 = delete(n) where n is a character or word offset. A shared object is replicated at each site and may be written or read arbitrarily by participants. Each site runs three processes: generate and qu eu e operations, receive and queue operations, execute operations. After an operation has been executed it is logged. Each site maintains its own log. If an incoming request is identified from its state vector as being potentially in conflict with a local operation that has already executed, then it is compared against selected log entries, and if necessary transformed.3.2Communications, Event Ordering and StateVectorsIntersite commu nication assu mes a reliable message handling service. No global clock is assumed and an event ordering scheme based on logical time [9] is u sed. Logical clocks are structured as state vectors [10,11]. In an N site system each site maintains a state vector s of size N by incrementing the ith component after execu tion of an operation from site i. The following relations are defined for the state vectors:s i = s j if all the components have the same value as their counterpartss i < s j if each component of s i is less than or equ al to its cou nterpart in s j, and atleast one component in s i is clearlyless than its counterpart in s j(This relation is u sed to enforceprecedence: if an operation isreceived at site i tagged with s j and s i< s j then it is not excuted until s j ≤s i).s i > s j if at least one of the components of s i is greater than its counterpart in s j.3.3Operation requestsEach operation requ est is a tu ple < i, s i, o, p > containing a copy of the originators site id, its state vector, the specific operation and the priority of the operation. The priority can simply be the site id and is used for tie breaking in the case of two identical operations with equ ivalent state vectors. It could be calculated on a fairer basis if necessary.3.4 The transformation matrix TT contains application specific ru les which handle concu rrent operations in su ch a manner that the effect of applying operation O1then operation O2 at site i is the same as applying operation O2 then operation O1 at site j. A simple example: the ru le dealing with the arrival of an insert operation “B:Ins x2,y2 val2” on a spreadsheet cell "x,y" where insert operation “A:Ins x1,y1val1”is in the log:if (A:sender < B:sender)return “B:Ins x2,y2” no changeelsereturn “no-op” transformed3.5 The core algorithmData structures:Q i the queue of operation requestsL i the log of operations which have beenexecuted<i, s, o, p>the form of a request: i is the site id, s isthe state vector, o is the operationand p is the priority.Initialisation:Q i ←empty the queue of operation requestsL i ←emptythe log of executed operationss i ←<0,0,...0>the state vector of site i Generate Operations:receive operation o from the user interfacecalculate the priority p of oQ i ← Q i + <i, s i , o i , p i >broadcast <i, s i , o i , p i > to all other sitesReceive Operations:receive <j, s j , o j , p j > from the networkQ i ←Q i + <j, s j , o j , p j >Execute Operations:for each <j, s j , o j , p j > ∈ Q i where s j ≤ s i beginQ i ← Q i - <j, s j , o j , p j >if s j < s i <k, s k , o k , p k > ← most recent entry from L iwhere s k ≤ s j ( ∅ if none )do while <k, s k , o k , p k > ≠ ∅ and o j ≠ ∅if the k'th component of s j is ≤ the k'thcomponent of s k let u be the index of o j let v be the index of o k o j ← T uv (o j ,o k ,p j ,p k )fi<k, s k , o k , p k > ← next entry in L i ( or ∅ ifnone)odfi perform operation o j on i's site objectL i ← L i + <j,s i ,o j ,p j >s i ← s i with jth component incremented by 1end 3.6. The partial concurrency problemProgress at each site was recorded in anindependent log (not L i ) and u sed for post-mortem analysis. The spreadsheet initiallyappeared to work well, resolving occasionalclashes correctly. Eventu ally however, thepartial concu rrency problem became manifest.Figu re 2 illu strates a recorded instance of theproblem in a time/event diagram where there areconflicting operations on spreadsheet cell C3.Site 0 inserts the string "textA" into cell C3 and increments its state vector. The broadcast message has state vector <0,0,0>. It then receives the request [1, Insert C3 "textB", <0,0,0>, 1] from site 1. <0,0,0> is less than the local state vector so the request is dOPTed and due to the priority 1 > 0(simple site id priority) the new string is inserted. Finally the delete requ est from site 2arrives with <0,1,0> and is not transformed with respect to the most recent insert because its state vector is greater than that in the log entry ( site 2saw site 1's insertion before deleting it ). It is then transformed against the initial insert to a no-op (insert is preferred to delete) and the insert from site 1 ("textB ") remains.cell C3 is empty cell C3 = "textB"cell C3 is emptyFigure 2.Site 1 inserts the string "textB " into cell C3 and increments its state vector. The broadcast message has <0,0,0>. It then receives the request [0, Insert C3 "textA", <0,0,0>, 0] from site 0. <0,0,0>is less than the local state and must be dOPTed.According to site priority the request from site 0 istransformed into a no-op. Finally a delete requ est arrives from site 2 with state <0,1,0>which is less than the local state. This operation is dOPTed, bu t is not transformed against the most recent log entry becau se it is a no-op. In addition it is not transformed with respect to the oldest log entry because its state vector is greater than that in the log entry (site 2 saw site 1's insertion before deleting it). The delete operation is carried ou t and the final resu lt is an empty cell.Site 2 receives an insert from site 1, increments its state vector, deletes the recent insert and broadcasts the delete operation with state <0,1,0 >. It then receives an insert from site 0 with clock <0,0,0> which is not transformed against the delete (and wins due to insert precedence). It is then transformed against the oldest log entry and due to site priority is transformed to a no-op. The final result is an empty cell.Partial concurrency refers to any set of operations where at least two are sequ ential to each other bu t concu rrent with a third. The problems in Figu re 2 stem from the first two events at Site 2 being sequential with each other, but both being concurrent with the first event at Site 0. Figure 3 shows the simplest example. The operations O1and O2are sequ ential with each other and concu rrent with O3. Depending on which types of operations are involved the ou tcome from dOPT may or may not appear consistent. It may be possible to adapt the transformation ru les to fix the problem for a particular set of operations but such a solution is lacking in generality.3.7Interpreting dOPTAlthough the dOPT paper [5] raises issues which are central to grou pware implementation it also contains some ambiguities, and it is clear that at the time of writing the au thors were not completely satisfied with the correctness of their algorithm. This section describes ou r resolu tion of some dOPT ambigu ities.Use of the empty set symbol "∅" is not explained and is overloaded. When being compared with an requ est tu ple "do while <k, s, o, p> ≠∅"it appears to mean end-of-list. When u sed in comparison with a specific operation "o j≠∅" weO OO132A BFigure 3.assu me it means "no-op".This seems a reasonableinterpretation as at r a n s f o r m a t i o n c a nusefully return a no-op toinvalidate an operationinvolved in a conflict,and when o j =∅the searchfor resolu tion stops. Partof the gu ard on the whileloop however reads "o j≠∅" which implies that the transformation matrix shou ld accommodate the possibility of a transformation of a new requ est against a log entry where o k =∅. Rather than extending T to hold (O+1)2 rules we assume that the gu ard effectively means o k≠∅on the first pass, this being consistent with a no-op constitu ting a termination condition rather than a source of further transformation.The u se of the greater-than symbol ">" in the comparison of state vectors is at best confu sing: "s i > s j if at least one of the components of s i is greater than its cou nterpart in s j". If the two vectors <0,1,0> and <1,0,0> are compared then they are both greater than each other. However, <1,0,0> > <0,0,0> also holds. This is the negation of ≤and is not the definition of concurrency used in other work, that is ¬(s i≤ s j) & ¬(s j≤ s i). Although not explicitly used in the algorithm this does present the implementor with an unpleasant ambigu ity regarding the intended meanings of comparisons between state vectors.Relations defined on state vectors are "<", ">" and "=", but it is quite possible for two state vectors to meet none of these conditions when compared. Consider the two vectors <0,1,0> and <1,0,0>. We resolve this idiosyncrasy by leaving a operation requ est, transformed or not, with its original state vector when it is logged. Thu s instead of "L i ← L i + <j,s i,o j,p j>" we use:"L i← L i + <j,s j,o j,p j>".4:EDITS: An Event Driven Interactive Transaction ServiceEDITS attempts to meet the grou pware requ irements listed in section 2, with the exception of divergence handling, bu t in qu ite adifferent way from that of dOPT. It is a grou pware oriented transaction service based on the Warp backtrack mechanism [12]. The original Warp based transaction service, also described in [12], is optimistic, live, fair, free from deadlock and scalable. It is also fau lt tolerant in some respects, but further discussion is ou twith the scope of this paper. This made WARP a good basis and EDITS represents the adaptation of its transaction service to su pport u ser interface (UI) synchronisation.EDITS synchronises with the UI as follows: when a u ser completes a write the local display is updated and a transaction generated to propagate the change; at commitment all displays are updated. If the user completes one or more writes before an existing transaction is complete they are added to it, forming a sequ ential list of operations. Transactions are identified by u niqu e totally-ordered transaction IDs (TIDs). The ordering of TIDs is u sed to ensu re liveness, by treating the TID of a transaction as its age, with oldest having highest priority. A site S can host many visiting transactions T i..T n, all execu ting simu ltaneou sly, on their own T-clones, T i|S…T n|S. When a site initiates a transaction T it refu ses visitors u ntil T has committed. When a transaction commits, each of its clones replaces the master of the corresponding site object. At any given time precisely one of the visitors owns the site object. If a site has no visitors, the next visitor becomes the owner. Thereafter, ownership may change when a visitor departs, caused either by rollback, triggered elsewhere in the transaction, or by commitment. To avoid deadlock, an owner which is u nable to progress as originally intended mu st release ownership and send a special backoff message to all its acqu aintance clones. Ownership passes to the oldest of the remaining visitors. As the same decision is taken locally at all sites, u nsu ccessfu l visitors commit thereby terminating themselves and effectively performing a no-op. Commitment uses a stable property detection protocol derived from a distribu ted termination detection algorithm [13]. At commitment the persistent states of objects involved in a transaction and corresponding UI displays are updated.4.2 The Warp Backtrack MechanismThe Warp backtrack mechanism u nderlying EDITS is derived from Time Warp [14]. It differs from its predecessor mainly by doing away with explicit virtual time values, including Global Virtu al Time. All protocol decisions and calcu lations are made locally and only cau sal relationships are preserved. The side effects of a process's optimism are limited to state changes, which are resolved throu gh restoration from a checkpoint, and messages sent to other processes, which may be cancelled by sending a n t i-m e s s a g e s. The overall effect is that of backtracking.(a)S(c)original computationSretry afterrollback to S'recoveryretry afterrollback to S(perhaps viaundo to S')Figure 4: BacktrackingFig. 4(a) is the situation before backtrack occurs. Fig. 4(b) shows the rollback caused by the receipt of the anti-message ¬M corresponding to the positive message M. Fig. 4(c) shows how backtrack results in a tree-structured compu tation over time, becau se generally a different retry compu tation ensu es after each rollback. In EDITS retries depend on u sersactions. Notice that in Fig. 4(a) the message M is already in the recipient’s past. Were M still in the input pool, it would simply be cancelled out by ¬M withou t cau sing rollback. For su bsequ ent retry to take place, the client state S at the backtrack point must be restored. It may happen that S itself was not checkpointed, in which case the nearest previou s checkpoint (e.g. S' in Fig. 4(c)) must be restored and the client run forward using the appropriate past inputs to reconstruct S — we say that the process undoes to S', and that S is recovered from S'.4.3 Resolving Non-SerialisabilitySu ppose sites A and B both delete character "c" from the string "a b c d". Site A generates transaction T1 which visits B and is blocked beca se B has already initiated its own transaction, T2. T2 visits A and is reciprocally blocked. Both sides backoff and ownership in both cases passes to the oldest transaction according to TID ordering, in this case T1|A < T2|B at A, and T1|B < T2|B at B; the asymmetry avoids deadlock and only one of the deletes is applied and propagated. Clones T2|A and T2|B know that they have been u nsu ccessfu l in conflict and commit by terminating. At this point all the persistent states of sites and all UI displays are u pdated. Note that non-serialisability has been resolved by effectively aborting one of the operations. The next change is dependent on inputs from the users.4.4 Coping with partial concurrencyWhen EDITS is applied to the events of Fig. 3 O1 and O2 become a single extended transaction and O3 is invalidated. Note that the bias in favour of an extended transaction, du e to its continu ed inheritance of the original TID, could be inverted by making it acqu ire a new TID when each new operation is added.5:SummaryDistribu ted real time grou pware is difficu lt to implement du e to the conflicting demands made by the need for good response time and the need to maintain consistency throu ghou t the distribu ted system. Traditional database concu rrency control schemes are unlikely to provide adequate response times as they u tilise locking and blocking. We have looked in detail at two approaches, dOPT and EDITS which both u se non-locking, non-blocking approaches and provide adequ ate interactive response times. Both avoid the use of potentially expensive global synchronisation as all protocol decisions are made locally. dOPT has some u nresolved problems stemming from the difficu lt natu re of concurrency in distributed systems but nevertheless it has introdu ced some key ideas such as having an application specific part which can accommodate the diverse demands of different groupware areas. EDITS is a provably correct system, bu t requ ires specific su pport services at the OS level provided in this case by the WARP backtracking mechanism.6:Future workNetwork speeds are increasing and some grou pware applications already offer real time a u dio-vis u al comm u nication if s u itable networking infrastru ctu re and workstation technology exists. Direct access to su ch low-latency high-speed wide-area networks may remove much of the tension created at present by the need for provision of good response times by optimistic concu rrency control schemes. If all participants are connected by a su itably fast network then certain integrity schemes cou ld be imported from the database world.Another consideration is the recent work on the provision of grou p-oriented services at the OS level. For example, Amoeba [15] and ISIS [16] now exist in stable produ ction versions su itable for commercial u se having evolved from research projects. There is also a growing body of literatu re contribu ting to the grou p-oriented paradigm, such as [17]. Groups at the OS process level are of cou rse different from groups in the distribu ted workplace, and cu rrent grou pware toolkits do not expect any particu lar assistance from workstation operating systems. However, the u se of OS level grou p services to implement grou pware possibly via a toolkit, shou ld allow developers to focus on their applications without having to spend time implementing ad hoc concu rrency control schemes.7:References[1] E N G E L B A R T, D.C. Knowledge-domaininteroperability and an open hyperdocument system,Proc. of the Conference on Computer-SupportedCooperative Work, ACM, (Oct.90) 143-156. [2]O ZSU M.T. & V ALDURIEZ P., Principles ofDistributed Database Systems, Prentice-Hall, 1991,pp. 276–339.[3]L ISKOV B., Distributed programming in Argus,CACM32, 3 (March 1988) 300–312.[4]G RIEF, I., SELIGER, R., AND WEIHL, W., AtomicData Abstractions in a Distributed CollaborativeEditing System, Proc. of the 13 AnnualSymposium on Principles of ProgrammingLanguages, 160-172, 1986.[5]E LLIS, C.A., and G IBBS, S.J., ConcurrencyControl in Groupware Systems, Proc. of the ACMSIGMOD ‘89 Conference on the Management ofData (June 1989) 399-407.[6]E LLIS, C.A., G IBBS, S.J., AND R EIN, G, Designand Use of Group Editor, Report STP-263-88,MCC Software Technology Program, Austin(1988).[7]Holtz, B. CoEd: a distributed shared text editor.Written as a demonstrator for Sun MicrosystemsToolTalk messaging service. Software placed inpublic domain. (April 1992).[8]L IVESEY, M.J., and A LLISON, C., Coping withconcurrency in groupware systems, Division ofComputer Science Technical Report, University ofSt Andrews (June 1993).[9]L AMPORT L., Time, clocks, and the ordering ofevents in a distributed system, CACM21, 7 (July1978) 558–565.[10]M ATTERN F., Efficient distributed snapshots andglobal virtual time algorithms for non-FIFOsystems (private communication), March 1990. [11]F IDGE C.J., Timestamps in message passingsystems that preserve the partial ordering, Proc. ofthe 11th Australian Computer Science Conference,Brisbane(Feb 1988) 56–66[12]L IVESEY, M.J., and A LLISON, C., Coherence inDistributed Persistent Object Systems, Proc. of theFifth International Workshop on Persistent ObjectSystems, Springer-Verlag (Sept. 1992)186-197.[13]D IJKSTRA E.W. & S CHOLTEN C.S., Terminationdetection for diffusing computations, Info. Proc.Letters11, 1 (August 1980) 1–4.[14]J EFFERSON D.R., Virtual Time, ACM TOPLAS73 (July 1985) 404–425.[15]K AASHOEK, M.F. AND T ANENBAUM, A.S.,Group Communication in the Amoeba DistributedOperating System, Proc. Eleventh InternationalConference on Distributed Computer Systems,IEEE Computer Society, (May 1991) 222-230. [16]BIRMAN K., The Processs group approach toreliable distributed computing, Cornell UniversityDepartment of Computer Science Research Report(July 1991).[17]V ERISSIMO, P., R ODRIGUES, L., AND V OGELS,W. Group orientation: a Paradigm for ModernDistributed Systems, First Year Report - BroadcastO p e n W o r k s h o p, 1, October 1993.。

Elsevier期刊被SCI收录最新一期题录信息本内容包括：主题、各主题有代表性刊名、该刊最新一期目录信息（包括卷期、论文题名、页码及作者等）Automation & Control Systems（自动化及控制系统）SYSTEMS & CONTROL LETTERSVolume 59, Issue 5, Pages 265-322 (May 2010)1.Editorial BoardPage IFC2.Gain-scheduled open-loop system design for LPV systems using polynomially parameter-dependent Lyapunov functionsPages 265-276Masayuki Sato3.Delay-adaptive feedback for linear feedforward systemsPages 277-283Nikolaos Bekiaris-Liberis, Miroslav Krstic4.Implicit Euler numerical scheme and chattering-free implementation of sliding mode systemsPages 284-293Vincent Acary, Bernard Brogliato5.Decentralized dynamic nonlinear controllers to minimize transmit power in cellular networks, Part IPages 294-298Vishwesh V. Kulkarni, Mayuresh V. Kothare, Michael G. Safonov6. ISDS small-gain theorem and construction of ISDS Lyapunov functions for interconnected systemsPages 299-304Sergey Dashkovskiy, Lars Naujok7.An observer for a class of nonlinear systems with time varying observation delay Pages 305-312F. Cacace, A. Germani, C. Manes8.Rendezvous of multiple mobile agents with preserved network connectivity Pages 313-322Housheng Su, Xiaofan Wang, Guanrong ChenBiology（生物学）BIOELECTROCHEMISTRYVolume 79, Issue 1, Pages 1-152 (August 2010)1. Editorial BoardPage IFC2. ContentsPages v-vi3.Electrochemistry of norepinephrine on carbon-coated nickel magnetic nanoparticlesmodified electrode and analytical applicationsPages 1-5Chunli Bian, Qingxiang Zeng, Huayu Xiong, Xiuhua Zhang, Shengfu Wang4.Interaction of surface-attached haemoglobin with hydrophobic anions monitored by on-line acoustic wave detectorPages 6-10Jonathan S. Ellis, Steven Q. Xu, Xiaomeng Wang, Grégoi re Herzog, Damien W.M. Arrigan, Michael Thompson5.Electrochemical impedance spectroscopy of polypyrrole based electrochemical immunosensorPages 11-16A. Ramanavicius, A. Finkelsteinas, H. Cesiulis, A. Ramanaviciene6.Electrochemical and AFM characterization on gold and carbon electrodes of a high redox potential laccase from Fusarium proliferatumPages 17-24K. González Arzola, Y. Gimeno, M.C. Arévalo, M.A. Falcón, A. Hernández Creus7.Improvements in the extraction of cell electric properties from their electrorotation spectrumPages 25-30Damien Voyer, Marie Frénéa-Robin, Franois Buret, Laurent Nicolas8.Electrochemical DNA biosensor for the detection of specific gene related to Trichoderma harzianum speciesPages 31-36Shafiquzzaman Siddiquee, Nor Azah Yusof, Abu Bakar Salleh, Fatimah Abu Bakar, Lee Yook Heng9.Development of electrochemical DNA biosensor based on gold nanoparticle modified electrode by electroless depositionPages 37-42Shufeng Liu, Jing Liu, Li Wang, Feng Zhao10.Herbicides affect fluorescence and electron transfer activity of spinach chloroplasts, thylakoid membranes and isolated Photosystem IIPages 43-49Andrea Ventrella, Lucia Catucci, Angela Agostiano11.Nanostructured polypyrrole-coated anode for sun-powered microbial fuel cells Pages 50-56Yongjin Zou, John Pisciotta, Ilia V. Baskakov12.Anodic oxidation of 3,4-dihydroxyphenylacetic acid on carbon electrodes in acetic acid solutionsPages 57-65Slawomir Michalkiewicz, Agata Skorupa13.A voltammetric Rhodotorula mucilaginosa modified microbial biosensor for Cu(II) determinationPages 66-70Meral Yüce, Hasan Nazır, Gönül Dönmez14.Explore various co-substrates for simultaneous electricity generation and Congo red degradation in air-cathode single-chamber microbial fuel cellPages 71-76Yunqing Cao, Yongyou Hu, Jian Sun, Bin Hou15.Electrochemical oxidation of amphetamine-like drugs and application to electroanalysis of ecstasy in human serumPages 77-83E.M.P.J. Garrido, J.M.P.J. Garrido, N. Milhazes,F. Borges, A.M. Oliveira-Brett16.A l-cysteine sensor based on Pt nanoparticles/poly(o-aminophenol) film on glassy carbon electrodePages 84-89Li-Ping Liu, Zhao-Jing Yin, Zhou-Sheng Yang17.The effects of the electro-photodynamic in vitro treatment on human lung adenocarcinoma cellsPages 90-94Jolanta Saczko, Mariola Nowak, Nina Skolucka, Julita Kulbacka, Malgorzata Kotulska 18.Gadolinium blocks membrane permeabilization induced by nanosecond electric pulses and reduces cell deathPages 95-100Franck M. André, Mikhail A. Rassokhin, Angela M. Bowman, Andrei G. Pakhomov19.Scanning electrochemical microscopy activity mapping of electrodes modified with laccase encapsulated in sol–gel processed matrixPages 101-107Wojciech Nogala, Katarzyna Szot, Malte Burchardt, Martin Jönsson-Niedziolka, Jerzy Rogalski, Gunther Wittstock, Marcin Opallo20.Maltose biosensing based on co-immobilization of α-glucosidase and pyranose oxidasePages 108-113Dilek Odaci, Azmi Telefoncu, Suna Timur21.Plasma membrane permeabilization by trains of ultrashort electric pulses Pages 114-121Bennett L. Ibey, Dustin G. Mixon, Jason A. Payne, Angela Bowman, Karl Sickendick, Gerald J. Wilmink, W. Patrick Roach, Andrei G. Pakhomov22.Effect of nano-topographical features of Ti/TiO2 electrode surface on cell response and electrochemical stability in artificial salivaPages 122-129I. Demetrescu, C. Pirvu, V. Mitran23.Efficiency of the delivery of small charged molecules into cells in vitro Pages 130-135M.S. Venslauskas, S. Šatkauskas, R. Rodaitė-Riševičienė24.Carbon nanotube-enhanced cell electropermeabilisationPages 136-141Vittoria Raffa, Gianni Ciofani, Orazio Vittorio, Virginia Pensabene, Alfred Cuschieri25.Dependence of catalytic activity and long-term stability of enzyme hydrogel films on curing timePages 142-146Joshua Lehr, Bryce E. Williamson, Frédéric Barrière, Alison J. Downard26.Enzymatic flow injection method for rapid determination of choline in urine with electrochemiluminescence detectionPages 147-151Jiye Jin, Masahiro Muroga, Fumiki Takahashi, Toshio NakamuraChemistry Applied（化学应用）CARBOHYDRATE POLYMERSVolume 81, Issue 4, Pages 751-970 (23 July 2010)1.Editorial BoardPage CO22.Adsorption separation of Ni(II) ions by dialdehyde o-phenylenediamine starch from aqueous solutionPages 751-757Ping Zhao, Jian Jiang, Feng-wei Zhang, Wen-feng Zhao, Jun-tao Liu, Rong Li3.Rheological and morphological characterization of the culture broth during exopolysaccharide production by Enterobacter sp.Pages 758-764Vítor D. Alves, Filomena Freitas, Cristiana A.V. Torres, Madalena Cruz, Rodol fo Marques, Christian Grandfils, M.P. Gonçalves, Rui Oliveira, Maria A.M. Reis4.Synthesis and evaluation of N-succinyl-chitosan nanoparticles toward local hydroxycamptothecin deliveryPages 765-768Zhenqing Hou, Jing Han, Chuanming Zhan, Chunxiao Zhou, Quan Hu, Qiqing Zhang5.Synthesis and application of new sizing and finishing additives based on carboxymethyl cellulosePages 769-774Z. El-Sayed Mohamed, A. Amr, Dierk Knittel, Eckhard Schollmeyer6.Synthesis and thermo-physical properties of chitosan/poly(dl-lactide-co-glycolide) composites prepared by thermally induced phase separationPages 775-783Santos Adriana Martel-Estrada, Carlos Alberto Martínez-Pérez, José Guadalupe Chacón-Nava, Perla Elvia García-Casillas, Imelda Olivas-Armendarizparison of the immunological activities of arabinoxylans from wheat bran with alkali and xylanase-aided extractionPages 784-789Sumei Zhou, Xiuzhen Liu, Yan Guo, Qiang Wang, Daiyin Peng, Li Cao8.Nano-in-micro alginate based hybrid particlesPages 790-798Abhijeet Joshi, R. Keerthiprasad, Rahul Dev Jayant, Rohit Srivastava9.The effects of reaction conditions on block copolymerization of chitosan and poly(ethylene glycol)Pages 799-804F. Ganji, M.J. Abdekhodaie10.Thermal behaviour and interactions of cassava starch filled with glycerolplasticized polyvinyl alcohol blendsPages 805-810W.A.W.A. Rahman, Lee Tin Sin, A.R. Rahmat, A.A. Samad11.Banana fibers and microfibrils as lignocellulosic reinforcements in polymer compositesPages 811-819Maha M. Ibrahim, Alain Dufresne, Waleed K. El-Zawawy, Foster A. Agblevor12.Variability of biomass chemical composition and rapid analysis using FT-NIR techniquesPages 820-829Lu Liu, X. Philip Ye, Alvin R. Womac, Shahab Sokhansanj13.TEMPO oxidation of gelatinized potato starch results in acid resistant blocks of glucuronic acid moietiesPages 830-838Ruud ter Haar, Johan W. Timmermans, Ted M. Slaghek, Francisca E.M. Van Dongen, HenkA. Schols, Harry Gruppen14.Development of films based on quinoa (Chenopodium quinoa, Willdenow) starch Pages 839-848Patricia C. Araujo-Farro, G. Podadera, Paulo J.A. Sobral, Florencia C. Menegalli 15.Polysaccharide determination in protein/polysaccharide mixtures for phase-diagram constructionPages 849-854Jacob K. Agbenorhevi, Vassilis Kontogiorgos16.Calorimetric and light scattering study of interactions and macromolecular properties of native and hydrophobically modified hyaluronanPages 855-863Martin Chytil, Sabina Strand, Bjørn E. Christensen, Miloslav Pekař17.Spray drying of nopal mucilage (Opuntia ficus-indica): Effects on powder properties and characterizationPages 864-870F.M. León-Martínez, L.L. Méndez-Lagunas, J. Rodríguez-Ramírez18.Preparation and evaluation of nanoparticles of gum cordia, an anionic polysaccharide for ophthalmic deliveryPages 871-877Monika Yadav, Munish Ahuja19.Functional modification of agarose: A facile synthesis of a fluorescent agarose–guanine derivativePages 878-884Mihir D. Oza, Ramavatar Meena, Kamalesh Prasad, P. Paul, A.K. Siddhanta20.Characterization of maize amylose-extender (ae) mutant starches. Part III: Structures and properties of the Naegeli dextrinsPages 885-891Hongxin Jiang, Sathaporn Srichuwong, Mark Campbell, Jay-lin Jane21.Multistage deacetylation of chitin: Kinetics studyPages 892-896N. Yaghobi, F. Hormozi22.Sulfated modification, characterization and structure–antioxidantrelationships of Artemisia sphaerocephala polysaccharidesPages 897-905Junlong Wang, Hongyun Guo, Ji Zhang, Xiaofang Wang, Baotang Zhao, Jian Yao, Yunpu Wang23.Magnetic chitosan/iron (II, III) oxide nanoparticles prepared by spray-drying Pages 906-910Hsin-Yi Huang, Yeong-Tarng Shieh, Chao-Ming Shih, Yawo-Kuo Twu24.Effect of adding a small amount of high molecular weight polyacrylamide on properties of oxidized cassava starchPages 911-918Yan Liu, Xu-chao Lv, Xiao Hu, Zhi-hua Shan, Pu-xin Zhu25.Preparation of nanofibrillar carbon from chitin nanofibersPages 919-924M. Nogi, F. Kurosaki, H. Yano, M. Takano26.Preparation and characterization of cellulose acetate–Fe2O3 composite nanofibrous materialsPages 925-930Costas Tsioptsias, Kyriaki G. Sakellariou, Ioannis Tsivintzelis, Lambrini Papadopoulou, Costas Panayiotou27.Synthesis, characteristic and antibacterial activity of N,N,N-trimethyl chitosan and its carboxymethyl derivativesPages 931-936Tao Xu, Meihua Xin, Mingchun Li, Huili Huang, Shengquan Zhou28.Fast compositional analysis of ramie using near-infrared spectroscopyPages 937-941Wei Jiang, Guangting Han, Yuanming Zhang, Mengmeng Wang29.Structure characterization of polysaccharide isolated from the fruiting bodies of Tricholoma matsutakePages 942-947Xiang Ding, Su Feng, Mei Cao, Mao-tao Li, Jie Tang, Chun-xiao Guo, Jie Zhang, Qun Sun, Zhi-rong Yang, Jian Zhao30.New insights into viscosity abnormality of sodium alginate aqueous solution Pages 948-952Dan Zhong, Xin Huang, Hu Yang, Rongshi Cheng31.Structural characterization and anti-inflammatory activity of two water-soluble polysaccharides from Bellamya purificataPages 953-960Hong Zhang, Lin Ye, Kuiwu WangComputer Science, Artificial Intelligence（计算机科学，人工智能）ARTIFICIAL INTELLIGENCEVolume 174, Issue 11, Pages 639-766 (July 2010)1.Editorial BoardPage IFC2.Partial observability and learnabilityPages 639-669Loizos Michael3.Monte Carlo tree search in KriegspielPages 670-684Paolo Ciancarini, Gian Piero Favini4.Learning conditional preference networksPages 685-703Frédéric Koriche, Bruno Zanuttini5.Planning to see: A hierarchical approach to planning visual actions on a robot using POMDPsPages 704-725Mohan Sridharan, Jeremy Wyatt, Richard Dearden6.Analysis of a probabilistic model of redundancy in unsupervised information extractionPages 726-748Doug Downey, Oren Etzioni, Stephen Soderland7. Designing competitions between teams of individualsPages 749-766Pingzhong Tang, Yoav Shoham, Fangzhen LinEnergy & Fuels（能源和燃料）APPLIED ENERGYVolume 87, Issue 8, Pages 2427-2768 (August 2010)1.IFCPage IFC2. Energy balance analysis of wind-based pumped hydro storage systems in remote island electrical networksPages 2427-2437J.K. Kaldellis, M. Kapsali, K.A. Kavadias3.Energy auditing and energy conservation potential for glass worksPages 2438-2446Yingjian Li, Jiezhi Li, Qi Qiu, Yafei Xu4.Energy demand and comparison of current defrosting technologies of frozen raw materials in defrosting tunnelsPages 2447-2454Marek Bezovsky, Michal Stricik, Maria Prascakova5.Guidelines for clockspeed acceleration in the US natural gas transmission industry Pages 2455-2466Ruud Weijermars6.Multi-objective self-adaptive algorithm for highly constrained problems: Novel method and applicationsPages 2467-2478Abdelaziz Hammache, Marzouk Benali, François Aubé7.Stochastic interest rates in the analysis of energy investments: Implications on economic performance and sustainabilityPages 2479-2490Athanasios Tolis, Aggelos Doukelis, Ilias Tatsiopoulos8.Effects of the PWM carrier signals synchronization on the DC-link current in back-to-back convertersPages 2491-2499L.G. González, G. Garcerá, E. Figueres, R. González9.Efficiency improvement of the DSSCs by building the carbon black as bridge in photoelectrodePages 2500-2505Chen-Ching Ting, Wei-Shi Chao10.Integer programming with random-boundary intervals for planning municipal power systemsPages 2506-2516M.F. Cao, G.H. Huang, Q.G. Lin11. Modeling the relationship between the oil price and global food prices Pages 2517-2525Sheng-Tung Chen, Hsiao-I Kuo, Chi-Chung Chen12.Marginal production in the Gulf of Mexico – II. Model resultsPages 2526-2534Mark J. Kaiser, Yunke Yu13.Marginal production in the Gulf of Mexico – I. Historical statistics & model frameworkPages 2535-2550Mark J. Kaiser14.Assessment of forest biomass for use as energy. GIS-based analysis of geographical availability and locations of wood-fired power plants in PortugalPages 2551-2560H. Viana, Warren B. Cohen, D. Lopes, J. Aranha15.Alkaline catalyzed biodiesel production from moringa oleifera oil with optimized production parametersPages 2561-2565G. Kafuku, M. Mbarawae of two-component Weibull mixtures in the analysis of wind speed in the Eastern MediterraneanPages 2566-2573S.A. Akdağ, H.S. Bagiorgas, G. Mihalakakou17.Evaluation of wind energy investment interest and electricity generation cost analysis for TurkeyPages 2574-2580Seyit Ahmet Akdağ, Önder Güler18.The role of demand-side management in the grid integration of wind power Pages 2581-2588Pedro S. Moura, Aníbal T. de Almeida19.Synthesis of biodiesel from waste vegetable oil with large amounts of free fatty acids using a carbon-based solid acid catalystPages 2589-2596Qing Shu, Jixian Gao, Zeeshan Nawaz, Yuhui Liao, Dezheng Wang, Jinfu Wang20.A study on the overall efficiency of direct methanol fuel cell by methanol crossover currentPages 2597-2604Sang Hern Seo, Chang Sik Lee21.Study of heat transfer between an over-bed oil burner flame and a fluidized bed during start-up: Determination of the flame to bed convection coefficientPages 2605-2614Vijay Jain, Dominic Groulx, Prabir Basu22.Predictive tools for the estimation of downcomer velocity and vapor capacity factor in fractionatorsPages 2615-2620Alireza Bahadori, Hari B. Vuthaluru23. Monitoring strategies for a combined cycle electric power generatorPages 2621-2627Joshua Finn, John Wagner, Hany Bassily24. Combustion and heat transfer at meso-scale with thermal recuperationPages 2628-2639V. Vijayan, A.K. Gupta25.Part-load characteristics of direct injection spark ignition engine using exhaust gas trapPages 2640-2646Yun-long Bai, Zhi Wang, Jian-xin Wang26.Gas–liquid absorption reaction between (NH4)2SO3 solution and SO2 for ammonia-based wet flue gas desulfurizationPages 2647-2651Xiang Gao, Honglei Ding, Zhen Du, Zuliang Wu, Mengxiang Fang, Zhongyang Luo, Kefa Cen27. Direct contact PCM–water cold storagePages 2652-2659Viktoria Martin, Bo He, Fredrik Setterwall28. Fatty acid eutectic/polymethyl methacrylate composite as form-stable phase change material for thermal energy storagePages 2660-2665Lijiu Wang, Duo Meng29.Thermal characteristics of shape-stabilized phase change material wallboard with periodical outside temperature wavesPages 2666-2672Guobing Zhou, Yongping Yang, Xin Wang, Jinming Cheng30. Study on a compact silica gel–water adsorption chiller without vacuum valves: Design and experimental studyPages 2673-2681C.J. Chen, R.Z. Wang, Z.Z. Xia, J.K. Kiplagat, Z.S. Lu31. Separation characteristics of clathrate hydrates from a cooling plate forefficient cold energy storagePages 2682-2689Tadafumi Daitoku, Yoshio Utaka32. A flexible numerical model to study an active magnetic refrigerator for near room temperature applicationsPages 2690-2698Ciro Aprea, Angelo Maiorino33. Feasibility study of an ice slurry-cooling coil for HVAC and R systems in a tropical buildingPages 2699-2711Y.H. Yau, S.K. Lee34. Optimum sizing of wind-battery systems incorporating resource uncertainty Pages 2712-2727Anindita Roy, Shireesh B. Kedare, Santanu Bandyopadhyay35. Peak current mode control of three-phase boost rectifiers in discontinuous conduction mode for small wind power generatorsPages 2728-2736O. Carranza, G. Garcerá, E. Figueres, L.G. González36. Experimental flow field characteristics of OFA for large-angle counter flow of fuel-rich jet combustion technologyPages 2737-2745Weidong Fan, Zhengchun Lin, Youyi Li, Mingchuan ZhangEngineering, Electrical & Electronic（电机及电子工程）MICROELECTRONIC ENGINEERINGVolume 87, Issue 9, Pages 1655-1808 (November 2010)1. Inside Front Cover - Editorial BoardPage IFC2 PrefacePage 1655Joel Barnett3.In0.53Ga0.47As(1 0 0) native oxide removal by liquid and gas phase HF/H2O chemistriesPages 1656-1660F.L. Lie, W. Rachmady, A.J. Muscat4.A study of the interaction of gallium arsenide with wet chemical formulations using thermodynamic calculations and spectroscopic ellipsometryPages 1661-1664J. Price, J. Barnett, S. Raghavan, M. Keswani, R. Govindarajan5.The removal of nanoparticles from sub-micron trenches using megasonicsPages 1665-1668Pegah Karimi, Taehoon Kim, Juan Aceros, Jingoo Park, Ahmed A. Busnaina6.In-line control of Si loss after post ion implantation stripPages 1669-1673D. Shamiryan, D. Radisic, W. Boullart7.Removal of post-etch 193 nm photoresist in porous low-k dielectric patterning using UV irradiation and ozonated waterPages 1674-1679E. Kesters, Q.T. Le, M. Lux, L. Prager, G. Vereecke8.Repair of plasma-damaged p-SiOCH dielectric films in supercritical CO2Pages 1680-1684Jae Mok Jung, Hong Seok Kwon, Won-Ki Lee, Byung-Chun Choi, Hyun Gyu Kim, Kwon Taek Lim9.Development of compatible wet-clean stripper for integration of CoWP metal cap in Cu/low-k interconnectsPages 1685-1688Aiping Wu, Eugene Baryschpolec, Madhukar Rao, Matthias Schaller, Christin Bartsch, Susanne Leppack, Andreas Ott10.Dissolution and electrochemical impedance spectroscopy studies of thin copper oxide films on copper in semi-aqueous fluoride solutionsPages 1689-1695N. Venkataraman, S. Raghavan11.The sacrificial oxide etching of poly-Si cantilevers having high aspect ratios using supercritical CO2Pages 1696-1700Ha Soo Hwang, Jae Hyun Bae, Jae Mok Jung, Kwon Taek Lim12.Monitoring wafer cleanliness and metal contamination via VPD ICP-MS: Case studies for next generation requirementsPages 1701-1705Meredith Beebe, Scott Anderson13.Fabrication of a two-step Ni stamp for blind via hole application on PWB Pages 1707-1710In-Soo Park, Jin-Soo Kim, Seong-Hun Na, Seung-Kyu Lim, Young-Soo Oh, Su-Jeong Suh 14.Arrays of metallic nanocones fabricated by UV-nanoimprint lithographyPages 1711-1715Juha M. Kontio, Janne Simonen, Juha Tommila, Markus Pessa15.Synthesis, characterization of CeO2@SiO2 nanoparticles and their oxide CMP behaviorPages 1716-1720Xiaobing Zhao, Renwei Long, Yang Chen, Zhigang Chen16.Development of a triangular-plate MEMS tunable capacitor with linear capacitance–voltage responsePages 1721-1727M. Shavezipur, S.M. Hashemi, P. Nieva, A. Khajepour17.The correlation of the electrical properties with electron irradiation and constant voltage stress for MIS devices based on high-k double layer (HfTiSiO:N and HfTiO:N) dielectricsPages 1728-1734V. Mikhelashvili, P. Thangadurai, W.D. Kaplan, G. Eisenstein18. Intra-level voltage ramping-up to dielectric breakdown failure on Cu/porous low-k interconnections in 45 nm ULSI generationPages 1735-1740C.H. Huang, N.F. Wang, Y.Z. Tsai, C.I. Hung, M.P. Houng19. Anodic bonding of glass–ceramics to stainless steel coated with intermediate SiO2 layerPages 1741-1746Dehua Xiong, Jinshu Cheng, Hong Li, Wei Deng, Kai Ye20.Preparation of silica/ceria nano composite abrasive and its CMP behavior on hard disk substratePages 1747-1750Hong Lei, Fengling Chu, Baoqi Xiao, Xifu Tu, Hua Xu, Haineng Qiu21.Investigation on the controllable growth of monodisperse silica colloid abrasives for the chemical mechanical polishing applicationPages 1751-1755XiaoKai Hu, Zhitang Song, Haibo Wang, Weili Liu, Zefang Zhang22.Fabrication and electrical characteristics of ultrathin (HfO2)x(SiO2)1−x films by surface sol–gel method and reaction-anneal treatmentPages 1756-1759You-Pin Gong, Ai-Dong Li, Chao Zhao, Yi-Dong Xia, Di Wu23.Frequency properties of on-die power distribution network in VLSI circuits Pages 1760-1763Pavel Livshits, Yefim Fefer, Anton Rozen, Yoram Shapira24.Analytical modelling for the current–voltage characteristics of undoped or lightly-doped symmetric double-gate MOSFETsPages 1764-1768A. Tsormpatzoglou, D.H. Tassis, C.A. Dimitriadis, G. Ghibaudo, G. Pananakakis, N. Collaert25.Anti-buckling S-shaped vertical microprobes with branch springsPages 1769-1776Jung Yup Kim, Hak Joo Lee, Young-Ho Cho26.Characterization of UV photodetectors with MgxZn1−xO thin filmsPages 1777-1780Tung-Te Chu, Huilin Jiang, Liang-Wen Ji, Te-Hua Fang, Wei-Shun Shi, Tian-Long Chang, Teen-Hang Meen, Jingchang Zhong27.Barrier height temperature coefficient in ideal Ti/n-GaAs Schottky contacts Pages 1781-1784T. Göksu, N. Yıldırım, H. Korkut, A.F. Özdemir, A. Turut, A. Kökçe28.Optical coherence tomography for non-destructive investigation of silicon integrated-circuitsPages 1785-1791K.A. Serrels, M.K. Renner, D.T. Reid29.Materials selection procedure for RF-MEMSPages 1792-1795G. Guisbiers, E. Herth, B. Legrand, N. Rolland, T. Lasri, L. BuchaillotPreview PDF (303 K) | Related Articles30.Automated optical method for ultrasonic bond pull force estimationPages 1796-1804Henri Seppänen, Robert Schäfer, Ivan Kassamakov, Peter Hauptmann, Edward Hæggström31.Oxygen incorporation in TiN for metal gate work function tuning with a replacement gate integration approachPages 1805-1807Zilan Li, Tom Schram, Thomas Witters, Joshua Tseng, Stefan De Gendt, Kristin De MeyerEngineering, Industrial（工业工程）APPLIED ERGONOMICSVolume 41, Issue 5, Pages 643-718 (September 2010)1.Editorial BoardPage IFC2.Editorial for special issue of applied ergonomics on patient safetyPages 643-644Pascale Carayon, Peter Buckle3.Systems mapping workshops and their role in understanding medication errors in healthcarePages 645-656P. Buckle, P.J. Clarkson, R. Coleman, J. Bound, J. Ward, J. Brown4.Human factors in patient safety as an innovationPages 657-665Pascale Carayon5.Space to care and treat safely in acute hospitals: Recommendations from 1866 to 2008Pages 666-673Sue Hignett, Jun Lu6.Macroergonomics and patient safety: The impact of levels on theory, measurement, analysis and intervention in patient safety researchPages 674-681Ben-Tzion Karsh, Roger Brown7.Designing packaging to support the safe use of medicines at homePages 682-694James Ward, Peter Buckle, P. John Clarkson8.Reflective analysis of safety research in the hospital accident & emergency departmentsPages 695-700Robert L. Wears, Maria Woloshynowych, Ruth Brown, Charles A. Vincent9.Improving cardiac surgical care: A work systems approachPages 701-712Douglas A. Wiegmann, Ashley A. Eggman, Andrew W. ElBardissi, Sarah Henrickson Parker, Thoralf M. Sundt III10.Are hospitals becoming high reliability organizations?Pages 713-718Sebastiano Bagnara, Oronzo Parlangeli, Riccardo TartagliaEngineering, Civil(土木工程)ENGINEERING STRUCTURESVolume 32, Issue 7, Pages 1791-1956 (July 2010)1.A study of the collapse of a WWII communications antenna using numerical simulations based on design of experiments by FEMPages 1792-1800J.J. del Coz Díaz, P.J. García Nieto, A. Lozano Martínez-Luengas, J.L. Suárez Sierra 2.Evaluation study on structural fault of a Renaissance Italian palacePages 1801-1813Michele Betti, Gianni Bartoli, Maurizio Orlando3.Case study: Damage of an RC building after a landslide—inspection, analysis and retrofittingPages 1814-1820P. Tiago, E. Júlio4.Deep trench, landslide and effects on the foundations of a residential building:A case studyPages 1821-1829A. Brencich5.Forensic diagnosis of a shield tunnel failurePages 1830-1837Wei F. Lee, Kenji Ishihara6.Failure of concrete T-beam and box-girder highway bridges subjected to cyclic loading from trafficPages 1838-1845Kent K. Sasaki, Terry Paret, Juan C. Araiza, Peder Hals7.Durability problem of RC structures in Tuzla industrial zone — Two case studies Pages 1846-1860Radomir Folić, Damir Zenunović8.Transverse vibrations in existing railway bridges under resonant conditions: Single-track versus double-track configurationsPages 1861-1875M.D. Martínez-Rodrigo, J. Lavado, P. Museros9.Case study: Analytical investigation on the failure of a two-story RC building damaged during the 2007 Pisco-Chincha earthquakePages 1876-1887Oh-Sung Kwon, Eungsoo Kim10.An evaluation of effective design parameters on earthquake performance of RC buildings using neural networksPages 1888-1898M. Hakan Arslan11.Structural performance of the historic and modern buildings of the University of L’Aquila during the seismic events of April 2009Pages 1899-1924A.M. Ceci, A. Contento, L. Fanale, D. Galeota, V. Gattulli, M. Lepidi, F. Potenza14.Collapse modelling analysis of a precast soft storey building in Australia Pages 1925-1936。

Impact of JIT JVM Optimizations on Java Application Performance¢K. Shiv , R. Iyer , C. Newburn , J. Dahlstedt , M. Lagergren and O. Lindholm Intel Corporation BEA Systems¢ ¢ ¢ ¡ ¡ ¡ ¡AbstractWith the promise of machine independence and efficient portability, JAVA has gained widespread popularity in the industry. Along with this promise comes the need for designing an efficient runtime environment that can provide high-end performance for Java-based applications. In other words, the performance of Java applications depends heavily on the design and optimization of the Java Virtual Machine (JVM). In this paper, we start by evaluating the performance of a Java server application (SPECjbb2000 ) on an Intel platform running a rudimentary JVM. We present a measurement-based methodology for identifying areas of potential improvement and subsequently evaluating the effect of JVM optimizations and other platform optimizations. The compiler optimizations presented and discussed in this paper include peephole optimizations and Java specific optimizations. In addition, we also study the effect of optimizing the garbage collection mechanism and the effect of improved locking strategies. The identification and analysis of these optimizations are guided by the detailed knowledge of the micro-architecture and the use of performance measurement and profiling tools (EMON and VTune) on Intel platforms.1 IntroductionThe performance of Java client/server applications has been the topic of significant interest in the recent years. The attraction that Java offers is the promise of portability across all hardware platforms. This is accomplished by using a managed runtime engine called the Java Virtual Machine (JVM) that runs a machine-independent representation of Java applications called bytecodes. The most common mode of application execution is based on a Just-InTime (JIT) compiler that compiles the bytecodes into native machine instructions. These native machine instructions are also cached in order to allow for fast re-use of the frequently executed code sequences. Apart from the JIT compilation, the JVM also performs several functions including thread management and garbage collection. This brings us to the reason for our study i.e. Java application performance depends very heavily on the efficient execution of the Java Virtual Machine (JVM). Our goal in this paper is to characterize, optimize and evaluate a JVM while running a representative Java application. Over the last few years, several projects (from academia as well as in the industry) [1,2,4,7,8,9,10,15,16,21] have studied various aspects of Java applications, compilers and interpreters. We found that R. Radhakrishnan et al. [16] cover a brief description of much of the recent work on this subject. In addition, they also provide insights on architectural implications of Java client workloads based on SPECjvm98 [18]. Overall, the published work can be classified into the following general areas of focus: (1) presenting the design of a compiler, JVM or interpreter, (2) optimizing a certain aspect of Java code execution, and (3) discussing the application performance and architectural characterization. In this paper, we take a somewhat different approach touching upon all the three aspects listed above. We present the software architecture of a commercial JVM, identify several optimizations and characterize the performance of a representative Java server benchmark through several phases of code generation optimizations carried out on a JVM. Our contributions in this paper are as follows. We start by characterizing SPECjbb2000 [17] performance on Intel platforms running an early version of BEA’s JRockit JVM [3]. We then identify various possible optimizations (borrowing ideas from literature wherever possible), present the implementation details of these optimizations in the JVM and analyze the effect of each optimization on the execution characteristics and overall performance. Our performance characterization and evaluation methodology is based on hardware measurements on Intel platforms - using performance counters (EMON) and a sophisticated profiler (VTune [11]) that allows us to characterize various regions of software execution. The code generation enhancements that we implement and evaluate include (1) code quality improvements such as peephole optimizations, (2) dynamic code optimizations, (3) parallel garbage collection and (4) fine-grained locks. The outcome of our work is the detailed analysis and breakdown of benefits based on these individual optimizations added to the JVM. The rest of this paper is organized as follows. Section 2 covers a detailed overview of the BEA JRockit JVM, the measurement-based characterization methodology and the SPECjbb2000 benchmark. Section 3 discusses the opti-¤ ¥£2 Background and MethodologyIn this section, we present a detailed overview of JRockit (the commercial JVM used) [3], SPECjbb2000 (the Java server benchmark) [17] and the optimization and performance evaluation methodology and tools.Figure 1. The SPECjbb2000 Benchmark Process2.1 Architecture of the JRockit JVMThe goal of the JRockit project is to build a fast and efficient JVM for server applications. The virtual machine should be made as platform independent as possible without sacrificing platform specific advantages. Some of the considerations included reliability, scalability, nondisruptiveness and of course, high performance. JRockit starts up differently from most ordinary Java JVMs by first JIT-compiling the methods it encounters during startup. When the Java application is running, JRockit has a bottleneck detector active in the background to collect runtime statistics. If a method is executed frequently and found to be a bottleneck, it is sent to the Optimization Manager subsystem for aggressive optimization. The old method is replaced by the optimized one while the program is running. In this way, JRockit is using adaptive optimization to improve code performance. JRockit relies upon a fast JIT-compiler for unoptimized methods, as opposed to interpretative byte-code execution. Other JVMs such as Jalapeno/Jikes [23] have used similar approaches. It is important to optimize the garbage collection mechanism in any JVM in order to avoid disruption and provide maximum performance to the Java application. JRockit provides several alternatives for garbage collection. The ”parallel collector” utilizes all available processors on the host computer when doing a garbage collection. This means that the garbage collector runs on all processors, but not concurrently with the Java program. JRockit also has a concurrent collector which is designed to run without ”stopping the world”, if non-disruptiveness is the most important factor. To complete the server side design, JRockit also contains an advanced thread model, that makes it possible to run several thousands of Java threads as light weight tasks in a very scalable fashion.The database component requirement common to three-tier workloads is emulated using binary trees of objects. The clients are similarly replaced by driver threads. Thus, the whole benchmark runs on a single computer system, and all the three tiers run within the same JVM. The benchmark process is illustrated in Figure 1. The SPECjbb2000 application is somewhat loosely based on the TPC-C [20] specification for its schema, input generation, and operation profile. However, the SPECjbb2000 benchmark only stresses the server-side Java execution of incoming requests and replaces all database tables with Java classes and all data records with Java objects. Unlike TPC-C where the database execution requires disk I/O to retrieve tables, in SPECjbb2000 disk I/O is completely avoided by holding the objects in memory. Since users do not reside on external client systems, there is no network IO in SPECjbb2000 [17]. SPECjbb2000 measures the throughput of the underlying Java platform, which is the rate at which business operations are performed per second. A full benchmark run consists of a sequence of measurement points with an increasing number of warehouses (and thus an increasing number of threads), and each measurement point is work done during a 2-minute run at a given number of warehouses. The number of warehouses is increased from 1 until at least 8. The throughputs for all the points from N warehouses to 2*N inclusive warehouses are averaged, where N is the number of warehouses with best performance. This average is the SPECjbb2000 metric.2.3 Performance Optimization and Evaluation MethodologyThe approach that we have taken is evolutionary. Beginning with an early version of JRockit, performance was analyzed and potential improvements were identified. Appropriate changes were made to the JVM and the new version of the JVM was then tested to verify that the modifications did deliver the expected improvements. The new version of the JVM was then analyzed in its turn for the next stage of performance optimizations. The types of performance optimizations that we investigated were two-fold. Changes were made to the JIT so that the quality of the generated code was superior, and changes were made to other parts of the JVM, particularly to the Garbage Collector, Object Allo-2.2 Overview of the SPECjbb2000 BenchmarkSPECjbb2000 is Java Business Benchmark from SPEC that evaluates the performance of Server Side Java. It emulates a three-tier system, with business logic and object manipulation, the work of the middle layer predominating.$ ' i7 f  8"" h g`e V (d"cb #! '6 § a X  & !! ' § $ '$1 Y "! (#© W"   %$V T S RE BIHG FE D A U(QP 3(#3 BC 3 9@  &! ¦ &6 4 $ $© #! (87 #(¨5$ #! 321 " # 0 $ ' ' ' "#) ( & $ #!  %© $ #"  !   © §   ¨¦mizations - how they were identified, implemented and their performance evaluation. Section 4 summarizes the breakdown of the performance benefits and where they came from. Section 5 concludes this paper with some direction on future work in this area.Figure 2. Processor Scaling on an early JRockit JVM version2.4.2 VTune Performance Monitoring Tool Intel’s VTune performance tools provide a rich set of features to aid in performance analysis and tuning: (1) Timebased and event-based sampling, (2) Attribution of events to code locations, viewed in source and/or assembly, (3) Call graph analysis and (4) Hot spot analysis with the AHA tool, which indicates how the measured ranges of event count values compare with other applications, and which provides some guidance on what other events to collect and how to address common performance issues. One of the key tools provides the means for providing the percentage contribution of a small instruction address range to the overall program performance, and for highlighting differences in performance among versions of applications and different hardware platforms.2.4 Overview of Performance Tools - EMON and VTuneThis section describes the rich set of event monitoring facilities available in many of Intel’s processors, commonly called EMON, and a powerful performance analysis tool based on those facilities, called VTune [11].2.4.1 EMON Hardware and Events Used The event monitoring hardware provides several facilities including simple event counting, time-based sampling, event sampling and branch tracing. A detailed explanation of these techniques is not within the scope of this paper. Some of th key EMON events leveraged in our performance analysis include (1) Instructions – the number of instructions architecturally retired, (2) Unhalted cycles – the number of processor cycles that the application took to execute, not counting when that processor was halted, (3) Branches – the number of branches architecturally retired which are useful for noting reductions in branches due to optimizations, (4) Branch Mispredictions – the number of branches that experienced a performance penalty on the order of 50 clocks, due to a misprediction, (5)Locks – the number of locked cmpxchg instructions, or instructions with a lock prefix and (6) Cache misses – the number of misses and its breakdown at each level of the cache hierarchy. The reader is referred to the Pentium 4 Processor Optimization Guide [24] for more details on these events.3 JVM Optimizations and Performance ImpactIn this section we describe the various JVM improvements that we studied and document their impact on performance. We also show the analysis of JVM behavior and the identification of performance inhibitors that informed the improvements that were made.3.1 Performance Characteristics of an early JVMThe version of JRockit with which we began our experiments was a complete JVM in the sense that all of the required JVM components were functional. Unlike several other commercial JVMs though, JRockit does not include an interpreter. Instead, all application code is compiled before execution. This could slow down the start of an application slightly, but this approach enables greater performance. JRockit also included a selection of Garbage Collectors and two threading models. Figure 3 shows the performance for increasing numbers of warehouses for a 1-processor and a 4-processor system.d–‘  ‰ ˆ ‡ q y „  y t w q s v v u t sq ’cY¨† u ¥Y ‚ƒ €xYdg"rp d • d (™ “ • Q“ ” – Q“ ” — Q“ ” ™ ˜ ”Q“ ™ ”– ”• ™ hf ge kf ij fm l f hqr omp ncator and synchronization, to enhance the processor scaling of the system. Our experiments were conducted on a 4 processor, 1.6 GHz, Xeon platform with 4GB of memory. The processors had a 1M level-3 cache along with a 256K level-2 cache. The processors accessed memory through a shared 100 MHz, quad-pumped, front side bus. The network and disk I/O components of our system were not relevant to studying the performance of SPECjbb2000, since this benchmark does not require any I/O. Several performance tools assisted us in our experiments. Perfmon, a tool supplied with Microsoft’s operating systems, was useful in identifying problems at a higher level, and allowed us to look at processor utilization patterns, context switch rates, frequency of system calls and so on. EMON gave us insight into the impact of the workload on the underlying micro-architecture and into the types of processor stalls that were occurring, and that we could target for optimizations. VTune permitted us to dig deeper by identifying precisely the regions of the code where various processor micro-architecture events were happening. This tool was also used to study the generated assembly code. The next section describes the performance tools – EMON and VTune – in some more detail.Table 1. System Performance Characteristics for early JVMFigure 3. Performance Scaling with Increasing WarehousesThere is a marked roll-off in performance from the peak at 3 warehouses in the 4-processor case. The JVM can thus be seen to be having some difficulty with increasing numbers of threads. Data obtained using Perfmon is shown in Table 1. While the utilization of the 1 processor is quite good at 94%, the processor utilization in the 4-processor case is only 56%. It is clear that improvements are needed to increase the processor utilization. The context switch and system call rates are two orders of magnitude larger in the 4P than in the 1P. The small processor queue length indicates the absence of work in the system. These aspects along with the sharp performance roll-off with increased threads, all point to a probable issue related to synchronization. It appears likely that one or more locks are being highly contended, resulting in a large number of the threads being in a state of suspension waiting for the lock. While being fully functional, this version of JRockit (we call it early JVM) had not been optimized for performance. It thus served as an excellent test-bed for our studies. The processor scaling seen with the initial, nonoptimized early JVM is shown in Figure 2. It is obvious that we can do much better on scaling. Many other statically compiled workloads exhibit scaling of 3X or better from 1 processor to 4 processors, for instance.œ™ Qœ 8 Ÿ¥ ww¦ ˜—¦ 53wQŸ œ¦Ÿ wQQ3— ¥ › œ œ ™œœ wœ 8w› ¥™ Q 8š œ ™œœ wœ 8w› ‰ˆ s ‚ 3u‡€Š ֘™ º› w› —š QQŸ ›——œ 8QwQŸ œœ› w8w ¥ › œ ¦™Ÿ 5ž ¨w Ÿ™ wž 8¦ ™ž 5Ÿ ¨w †…ƒ ‚ €‹„¨ŠÎ Í Ì Ë Ê ÈÄ Å Ç À Æ Å Ä Ã¿ ¼ Á ¿ ¾ ¼ „u€‹8É ‹½ W‹€½ Y"€‹ÂÀ 8 ¼½ g»â ÛâØ Ýá Ü à ß ÞÝ Ü ÛÚ ÙØ Q"#¨3¨Û ¨ÂQ38¨¤w× Õ Ñœ™ wœ ¨— ›— ¨#› ¥ Qw¦ ž¥ž wQQ˜ ¥ œ œ ™œœ Qœ 8Q#› ˜™¦ w˜ 8› œ ™œœ Qœ 8Q#› ‰ˆ s ‚ wu‡wš™ 5Ÿ 8 ¦ Q— ¥ Q— œ˜ 53¦ ¥ œ ™¦ w¥ 8w— ™ Q¥ 8œ › ™˜ 8š €— †…ƒ ‚ ¨g„w Ô¯ 3¢#¨#„#8xQ83#Q(w ‹‘ Ž ©”¹ ”ª”ª ¸’••”“ ’ “” µ Ž« ’ Ž 5#• #• #w ’ª 8” ( ¨© “” µ•”¯ · Ž¶ Ž© Q• (Q#w“ Ž   ¨± #3” #5° “” µ  ° ³ Ž ² w• (•  5´5” (• €± Ž(Qª5|35” QgQŽ 33wgQ¬ ©  ° £ ’¯ Œ  ®“ ­ – 3 ’ª ¨” (© 8 ‹Œ Ž« ’ Ž ¨ Ž –’”• § Ž 5¨#8 ‹Œ – £”¢   ’ ‘ Ž ¤wQw”  Q¡   #8 ‹Œ –’••”“ ’ ‘ Ž 853#w#w #8 ‹Œ v€ x v ~}{ vt wwt 8t w Y5| xyz wus Ò Ï ÒÑ ÐwÏ Ò Ó ä Ñ QÓ Ð æä åã éä çè äë ê ÐÑ æïðíëî ì3.2 Granularity of Heap LocksThe early version of JRockit performed almost all object allocation globally with all allocating threads increasing a pointer atomically to allocate. In order to avoid this contention, thread local allocation and Thread Local Areas (TLAs) were introduced. In that scheme, each thread has its own TLA to allocate from and the atomic operation for increasing the current pointer could be removed, only the allocation of TLAs required synchronizations. A chain is never stronger than its weakest link, once a contention on a lock or an atomic operation is removed, the problem usually pops up somewhere else. The next problem to solve was the allocation of the TLAs. For each TLA that was allocated, the allocating thread had to take a ”heap lock”, find a large enough block on a free list and release the lock. The phase of object allocation that requires space to be allocated from a free list requires a lock. This lock acquisition and release showed up on all our measurements with VTune as a hot spot, marking it as a highly contended lock. One attempt was made to reduce the contention of this lock by letting the allocating thread allocate a couple of TLAs and putting them in a smaller temporary storage where they could be allocated using only atomic operations by other threads. This attempt was a dead end. Even if the thread that had the heap lock put a large amount of TLAs in the temporary storage, all threads still ended up waiting most of the time, either for the heap lock or that the holder of the heap lock would give away TLAs. The final solution was to create several TLA free lists. Each thread has a randomly allotted ”home” free list from which to allocate the TLAs it needs. If the chosen list was empty, the allocating thread tried to take the heap lock and fill that particular free list with several TLAs. After this, the thread would choose another ”home” free list randomly to allocate from. By having several lists, usually only one thread would try to take the heap lock at the same time and the contention of the heap lock was reduced dramatically. Contention was further reduced by providing a TLA cache; the thread that acquires the heap lock moves 1MB of memory into the cache. A thread that finds its TLA free list empty checks for TLAs in the cache before taking the heap lock. Figure 4 shows the marked improvement in processor scaling in the modified JVM, the JVM with the heap lock contention reduction. Scaling at 2 processors has increased from 1.08X to 1.70X, and the scaling at 4 processors has improved to 2.46X from 1.29X. The perfmon data with these changes is interesting, and is shown in Table 2. The increase in processor utilization and the decrease in system calls and context switches are all very dramatic.3.3 Garbage Collection OptimizationsThe early version of JRockit included both a single and multi generational concurrent garbage collector, designed toFigure 4. Improvement of Processor Scaling with Heap Lock contention scalingˆ ¦ˆ — ‡  S¡— ‡ ƒ ‡ S¡‡ — ƒ ‰ ¡¦©‡ ˆ ‡ ˆ ˆ ˆ ˆ ¡ˆ ¡‡ ˆ ¦‘ ƒ ˆ ‘ ¡ƒ ¡‰ c h ` FHg Y 9 X W i @ f¡pF¦R ™ y‡ F‡ — „ ¦¡† ˆ ¦‘ ˆ ‘ ¡™ ˆ ‡ ˆ ™ ‡ F„ FS‰ ˆ ¡— ˆ ƒ ‡ ¡ FS‰ c b a dSF` Y 9 X W i @ f¡pF¦R ˆ ¡ˆ ƒ † ‰ F¡— ƒ ™  — ¡¦† ˆ — ƒ † ¡¡¦F ‰ ©‡ ˆ ˆ ˆ ˆ ¦ˆ ¡‡ ‰ ¡ƒ ‘ ˆ ˆ ˆ ¦ˆ ¡‡ c h ` FHg Y 9 X W T f¦HV eG ™ y‡ F‡  ‘ ¦¦† ‡   ˆ S¦¡¦† ˆ ˆ ‡ ƒ ¡S¡ƒ ‰ ©‡ ˆ — † „ S¡ƒ † ¡„ — ƒ „ † S¡ƒ c b a dSF` Y 9 X W T 4¡HV UGFigure 5. Impact of Parallel Garbage Collection on Processor Scalinghave really short pause times and fair throughput. Throughput in a concurrent collector is usually not a problem since a full collection is rarely noticed, even less on a multiprocessor system. The problem occurs when objects are allocated in such a fast rate that even if the garbage collector collects all the time on one processor and lets the other processors run the program, the collector still doesn’t manage to keep up the pace. This problem started to hurt performance badly in JRockit when running 8 warehouses on 8-way systems. To solve this, the so-called ”parallel collector” was developed. The base was a normal Mark and Sweep [13] collector with one marking thread per processor. Each thread had its own marking stack, and if a stack is empty the thread could work-steal references from other stacks [5]. Normal pushing and popping required no synchronization or atomic operations, only the work-stealing required one atomic operation. Each thread also had an expandable local stack to handle overflow in the exposed marking stack. Sweeping is also done in parallel by splitting the heap in N sections and letting each thread allocate a section, sweep it, allocate a new section and so forth until all sections were swept. The sweeping algorithm focused on performance more than accuracy, creating room for fragmentation if we were unlucky. A partial compaction scheme was employed to reduce this fragmentation. These GC optimizations resulted in an increase in the re-Figure 6. Impact of Parallel Garbage Collection on SPECjbb2000 Performanceported SPECjbb2000 result in a 4P system, and improved processor scaling from 2.46 to 2.92, as illustrated in Figure 5. The benefits of this were more noticeable at higher numbers of warehouses and therefore lead to a much flatter roll-off from the peak, as shown in Figure 6.3.4 Code Quality ImprovementsSeveral code quality improvements were made during the benchmarking process. A new code generation pipeline was developed and merged into the product. This enabled us to do a lot more versatile and low-level optimizations on code than previously was possible. Based on the SPECjbb2000 characteristics measured and analyzed in the previous section, we were able to identify several patterns at the native code level that were suboptimal. The JRockit team replaced these with better code through peephole optimizations (commonly used for compiler optimizations as in [6, 14]) or more efficient code generation methodologies. While the compiler optimizations listed below are well-known and understood, the requirement here is¾ Àà ¿Ð É Ð Æ Ë Ï Ê Î Í Ì Ë Ê É È Ç Æ ¦¦¡edÉ d8U¦ed¦½S4ž ©¿Ã¾Table 2. System Performance Characteristics after Heap Lock Improvements S‘¼ » º º ¹ ¸ · ² ¶ µ ´ ³ ² ½S‚³ º ‚¸ ‚|QƒSe2² f±‰ † ~ „ { }   € ~ { Qˆ ‡ fdm4ƒ‚eUU} |z  SŽ °ƒ¤ £  ¦¡ ¡  ¯ £ £ ¢ ®y­¡¬Fm¦F  ¨ « ª © ¡ § ¦ ¥ ¢ ¡ 4y| £¤ ¡     Œ ¦ ‹ Œ ¦Š ‹  Œ Ž ‹ Œ © ‹ Š Ž ¿ à Á ¾ Ä À Â × ÕÖ Ò Ù ØÒ ÞÒ ÜÔÝ Ù ÚÛ ÓÔ ÑÒ Ÿ“ •ž š ›œ š ™“ “ –—˜ ”• ’“ 3428¤©5 1) 7 6 3 1) ' 420( ¦& ¨ þ ûúõùòôøø÷õ ò Y üý YuóYöô óñ¨ ¥ k s¡”©S©x©Sv¦S¡¤¡r ev e y w y f y f u w r € € y x w x y r s g w s ¦©€ ©€ ¡f w dy ©e d x y r € y k ¤€ ©¡©¡x ’s dn Fy ©4l t s s s e r x y r u t l p s o ¦€ ¤ u€ 4qy ©€ dn s©e¡fS4mFy ¦Q¡s FF¡Q¦h r l • t w k q ’ j x r i ‚ ¡f w Sy ©e ©t ¡Uq s g w s d u s r ‚ w y € ˜ u s r SSe©t ¡Uq ‚ • y ” ’ w v u s r –¡¡¡ uy ¦ ’“ e©t ¡Uq ‚ w r € € y x w v u s r S¡©¡r e©t ¡Uq A E B A P I G E A @ ¡¡@ S@ ¡R QHFD C B ¡09 ¨ ©£ £ §ÿ¥ ¢¡   ¢ ¤£  ¢ ¦¥  ÿ   $% #    !"Figure 8. An Example of Copy PropagationP £b`I00D qik jbD ih IiUtiqQ(V @ H 8 k 8 m A l G A @ A 8 H 8 X 8 h DFigure 7. A Simple Example of Peep-Hole Optimization• ”5Ii˜—• U5y d ™ € – ” “ ‡ "y †  u € y w v u s %iixItr @ P A @ RQ8 I8 0H G F D B A @ 8 0EC 097that the compile time overhead be kept to a minimum since it is a part of the execution time; and as such, not all known optimizations and techniques could be added. These are by no means a complete list of improvements, but give some perspective on things that were done to enhance code quality. 1. Peephole Optimizations: The new JRockit code generator made it possible to work with native code just before emission, i.e. there would be IR operations for each native code operation. Several small peephole optimizations were implemented on this. We present one example of this kind of pattern matching here: Java contains a lot of load/store patterns, where a field is loaded from memory, modified and then rewritten. Literal translation of a Java getfield/putfield sequence would result in three instructions on IA32 as shown in Figure 7(left). IA32 allows most operations to operate directly on addresses, so the above sequence could be collapsed to a single instruction as shown in Figure 7(right). 2. Better use of IA32 FPU instructions: Java has precise floating-point semantics, and works either in 32bit or 64-bit precision. This is usually a problem if one wants to use fast 80-bit floating points that there is hardware support for on IA32, but in some cases we don’t need fp-strict calculations and can use built in FPU instructions. JRockit was modified to determine when this is possible. 3. Better SSA reverse transform: Most code optimizations take place in SSA form. There were some problems with artifacts in the form of useless copies not being removed from the code when transforming back to normal form. The transform was modified to get rid of these, with good results. Register pressure dropped significantly for optimized code. 4. Faster checks: The implementation of several Java runtime checks was speeded up. Some Java runtime checks are quite complicated, such as the non-trivial case of an array store check. These were treated as special native calls, but without using all available registers. Special interference information for these simplified methods was passed to the register allocator, enabling less saves and restores of volatile registers.Table 3. Impact of Better Code Generation on Application Performance5. Specializations for common operations: Array allocation was re-implemented with specialized allocation policies for individual array element sizes. The Java ”arraycopy” function was also specialized, depending on if it was operating on primitives or references and on elements of specific sizes. Other common operations were also specialized. 6. Better Copy Propagation: The copy propagation algorithm was improved and also changed to work on the new low level IR, with all its addressing modes and operations. An example of better copy propagation is shown in Figure 8. These improvements to the JIT were undertaken to reduce the code required to execute an application. It is possible that the techniques used to lower the path length could increase the CPI of the workload, and end up hurting throughput. One example of this would be the usage of a complex instruction to replace a set of simpler instructions. However, Table 3 shows that while the efforts to reduce the path length were well rewarded with a 27% improvement for SPECjbb2000, these optimizations did not hurt the CPI in any significant way. The path length improvement resulted in a 34% boost to the reported SPECjbb2000 result.3.5 Dynamic OptimizationThe initial compile time that is tolerable limits the extent to which compiler optimizations can be applied. This implies that while JRockit provides better code in general than an interpreter, for the few functions that other JITs do choose to compile, there is a risk of under-performance. JRockit has chosen to handle this issue by providing a secondary compilation phase that can include more sophisticated optimizations, and using this secondary compilation during the application run to compile a few frequently used hot functions.© 3  § 1 ' )  ' !   © $ # !   § ¥ 24 6% ¡0%("&%"¡© ¨5¤      § ¥ © 2© ¨5¤ 8 p H h g V q0IiYfe e ‘ ˆ e ¡’ ‚ e i„ G X V A F dcbI8 @ 5a gUˆ ‚ ˆ ‘ q‰ ƒ ˆ ƒ £„ Q‚G X V A DF `YW8 UT08 SfI0qQ e ‘  U‰ ƒ ˆ ‚     § ¥ © © ¨¦¤ © 3  § 1 ' )  ' !   © $ # !   § ¥ 4 2 ¡&0("&%"¡© ¨¦¤      § ¥ © © ¨¦¤ü ¢   ÿ ú ô ó þ ý û úù ÷ õ ô 0£¡U0F|ü ‚2øöóë ð ï î é ä à å ä 4S©Q‚ƒíß ã Qà ä ì ê è æ å ä fë dé yç ƒƒpß ã ‚áß â à ä òß ã ©fë dé yç ñ‚áß å ì ê è æ â à。

A CASE-STUDY APPLICATION OF RTCA DO-254: DESIGN ASSURANCEGUIDANCE FOR AIRBORNE ELECTRONIC HARDWARE Paul S. Miner, Victor A. Carreño, Mahyar Malekpour, and Wilfredo TorresNASA Langley Research Center, Hampton, VA{p.s.miner, v.a.carreno, m.r.malekpour, w.torres-pomales}@ DISCLAIMER: This paper was authored by a team from NASA Langley Research Center for the 2000 Digital Avionics Systems Conference (October 2000). It is based on aresearch program being funded by the Federal Aviation Administration (FAA). Itdoes not represent FAA regulatory material, policy, or guidance.A CASE-STUDY APPLICATION OF RTCA DO-254:DESIGN ASSURANCE GUIDANCE FOR AIRBORNEELECTRONIC HARDWAREPaul S. Miner, Victor A. Carreño, Mahyar Malekpour, and Wilfredo Torres NASA Langley Research Center, Hampton, VA{p.s.miner, v.a.carreno, m.r.malekpour, w.torres-pomales}@AbstractIn a joint project with the FAA, NASA Langley is developing a hardware design in accordance with RTCA DO-254: Design Assurance Guidance for Airborne Electronic Hardware. The purpose of the case study is to gain understanding of the new guidance document and generate an example suitable for use in training.For the case study, we have selected a core subsystem of the Scalable Processor-Independent Design for Electromagnetic Resilience (SPIDER). SPIDER is a new fault-tolerant architecture under development at NASA Langley Research Center. IntroductionRTCA, Inc. has recently approved DO-254: Design Assurance Guidance for Airborne Electronic Hardware [1]. This document is intended to provide a basis for the certification of complex electronic hardware devices used in aircraft. As with all new guidance documents, there will be a period of uncertainty while developers and the FAA learn how best to apply the document. This uncertainty will likely be compounded by the flexibility DO-254 offers for developing a design assurance strategy.To alleviate some of this uncertainty the FAA initiated this case study to gain some experience with this new guidance document. This case study has limited scope; there are insufficient resources to explore all aspects of DO-254. The focus of the case study is on logical aspects of design, and is targeted to early stages of the design process.There are two goals for the case study. The primary purpose is to help identify problems in applying the new document. A secondary purpose is to provide material suitable for use in training. The second objective places some constraints on the project scope. Specifically, the hardware device should be non-proprietary, non-commercial, and of limited complexity.NASA Langley Research Center also has some objectives for this case study. One goal is to demonstrate the application of formal methods on a representative example. Another priority for NASA is to develop a hardware platform to support in-house research targeted toward demonstrating systematic recovery from multiple correlated transient failures.With these objectives and restrictions in mind, the chosen device for the case study is a core subsystem of a new fault-tolerant architecture under development at NASA Langley Research Center. Several factors motivated the choice of a fault-tolerant system for this exercise. Hardware realizations of fault-tolerant protocols are generally compact designs; this allows for comprehensive treatment within the time constraints of a training exercise. Also, the behavior of fault-tolerant devices is inherently complex; such a device is clearly within the scope of DO-254. Furthermore, there is a considerable amount of research literature addressing the formal analysis of fault-tolerant protocols; a fault-tolerant system is a good candidate for a formal methods demonstration. Finally, any device expected to recover from transient failures will necessarily need to deal with a bounded set of permanent failures, as well.The architecture being explored for this case study is the Scalable Processor-Independent Design for Electromagnetic Resilience (SPIDER). In this architecture, the primary basis for fault-tolerance is a communication subsystem called the Reliable Optical Bus (ROBUS). The concept for the SPIDER architecture builds on previous fault-tolerant computing research at NASA LangleyResearch Center. The main concept was inspired by a fault-tolerant system designed as part of the Fly-by-Light/Power-by-Wire (FBL/PBW) program [2] [3].Project OverviewThe project consists of three sequential phases beginning in August 1999 and ending in December 2001. The first phase, which began in August 1999 and ended in January 2000, consisted of planning the hardware development activities. The initial Plan for Hardware Aspects of Certification was presented to the FAA in January and was subsequently revised. The second phase consists of the development of a detailed design in accordance with the submitted plan. The detailed design will include a limited laboratory prototype intended to illustrate certain characteristics of the architectural concept. The final phase will culminate in a more complete prototype implementation; this prototype will include sufficient features to make a fair assessment of the proposed design.Planning PhaseAny organization applying DO-254 for the first time must decide how to map its existing development processes to those of DO-254. Since our research group did not have any defined hardware development processes, we were free to define all aspects of our hardware development environment. This served as both a blessing and a curse. We were able to select from a variety of options. However, some of the choices we made were necessarily uninformed. It is likely that we shall need to update our processes as the project progresses.During the planning phase of the project, we identified the target design artifacts and determined the various components of our development environment. In addition to identifying the design and verification methods, we needed to define the supporting processes that serve to control the development and maintenance of the developed product. These supporting processes include: • Certification Liaison• Process Assurance• Configuration ManagementThe certification liaison activities consist of regular interaction with a small team from the FAA. The initial Plan for Hardware Aspects of Certification was presented to the FAA in January. They agreed with the proposed plan, in principle, but deferred judgement on some of the proposed verification activities until more detailed descriptions are developed.The process assurance activities are primarily focused on monitoring the development activities to ensure that they are proceeding in accordance with the approved plans. For this project, the emphasis is on ensuring the internal consistency of the set of controlled data we accumulate throughout the development effort.An integral part of developing hardware in accordance with DO-254 is the management of design and verification data throughout the life of the product. Hence, there is a need for an effective recording and configuration management system.The purpose of configuration management is to ensure consistent replication and controlled modification of artifacts produced during the design process. There are several interrelated aspects to configuration management. The primary requirement is a consistent repository of data. This repository contains identification of the design environment, a collection of design artifacts sufficient for consistent replication, and verification data that provides sufficient evidence that the design meets its requirements. Information in this repository needs to be maintained such that controlled changes preserve a consistent set of data.Configuration Management ToolsConfiguration management for this project is supported by two tools, the Concurrent Versions System (CVS) [4] and GNATS [5]. Both tools are freely available on the Internet and are distributed under the GNU public license. Both of these tools provide access for users from both UNIX and Windows systems. This is necessary for the SPIDER project because the development involves data generated on both UNIX and Windows platforms. Additionally, both of these tools have auxiliary programs that provide a web-based interface.CVS is a revision control system. As such, it maintains a history of changes to the controlled project files. , it records:• who makes a change• when it is made• why it is made (if the user providesmeaningful log messages)• what other changes are made at the same timeThe change history is traceable. VS does not implement any change control policies. However, it can be used in a manner where changes are restricted. S is based on a copy-modify-merge philosophy for version control. , each developer maintains a copy of their part of the development tree, implements changes on the local copy, then merges the changes into the central repository. plemented to restrict the authority to commit changes to the central repository.GNATS is a problem reporting system. Problem reports are submitted via e-mail and are automatically logged into a database and forwarded to a responsible party. The problem reports can later be updated to reflect actions taken to resolve the problems. he problem report database is always accessible for review. s the design is modified in response to problem reports, the CVS change logs can readily reflect the problem report number from GNATS.The GNATS system can also be used to log other reports generated during the course of a design. this project, we are using GNATS to record all of our process-control actions.The hardware design life cycle data is being accumulated following the process data-flow model depicted in Figure 1. he emphasis is on managing all data that will serve as a basis for certification. The data flow depicted in Figure 1 corresponds to controlled data. he central idea is that data cannot be controlled unless all the data on which it depends is also controlled.1. System Level Requirements Allocated to Hardware2. Feedback to System Development3. Process Control Actions4. Process Control Requests5. Design Development Data6. Configuration Management Entries7. Process Assurance Evidence8. Design Manufacturing Data9. Hardware Design Manual10. Unmanaged Design Notes and Artifacts Figure 1: Documented Hardware Design LifeCycleDesign Assurance StrategyFor this project, we are developing the ROBUS to support any level A aircraft function. Since the design is being developed to the most stringent requirements, it is not necessary to justify the selected design assurance level. f we desired to develop part of the hardware system to a lower design assurance level, we would need to justify our decision using a Functional Failure Path Analysis (FFPA). A high-level description of performing an FFPA is presented in Appendix B of DO-254 [1].A worked example illustrating an FFPA is presented in [6].Our primary strategy is to focus on ensuring correctness at the conceptual design stage and then preserving the design integrity as we proceed through detailed design and implementation.the certification basis depends upon the conceptual design, the conceptual design data will be maintained under configuration management.This is not the only strategy allowed by DO-254. n fact, DO-254 does not require conceptual design data to be controlled, if it is not used toSpecificallyCCVSpecifically Specific policies can be imTAForTTISince Isupport certification arguments. When a system is being developed to assurance level A or B, DO-254 requires that the design assurance strategy be developed using the guidance of Appendix B [1]. Selection of Design Assurance MethodSubsection 3 of Appendix B in DO-254 suggests a number of methods that may be appropriate for a level A design assurance strategy [1]. The methods enumerated include architectural mitigation, service history, and three advanced analysis techniques:• Safety-Specific Analysis• Elemental Analysis• Formal MethodsArchitectural mitigation strategies are employed to constrain potentially adverse effects of errors in the design. The ROBUS may ultimately be used as part of an architectural mitigation scheme, but there is no architectural solution to mask design errors within the ROBUS. Hence, we cannot base the design assurance of ROBUS on architectural mitigation techniques. Also, since ROBUS is a new design, we cannot appeal to service history as part of our design assurance strategy. Therefore, we need to consider the suggested advanced analysis techniques.Since we have expertise in the application of formal methods, that will be the core of our design assurance strategy. We will focus on formal proof at the conceptual design level to ensure that the SPIDER family of fault-tolerant systems is correct. We will then use conventional design and verification techniques to ensure that our detailed design and implementation are correct realizations of our conceptual design.Fault AssumptionsThere are at least two approaches to reasoning about faults and failures in a digital system. One is to postulate possible component failures and then assess the resulting impact on the system. Alternatively, one may assume that all faults have potentially devastating consequences and then design the system relative to this worst case assumption. Our approach is closer to the latter, but we allow some variation into the potential impact of faults. We will adopt the fault-classification strategy used in the development of the Multiprocessor Architecture for Fault-Tolerance (MAFT) [7]. Faulty nodes are globally classified based on the locally observable characteristics to other nodes within the system. The system is partitioned into Fault Containment Regions (FCRs) that ensure independence of random physical failures. The failure status of an FCR is then one of four mutually exclusive possibilities. An FCR may be• Good• Benign Faulty: All good nodes thatobserve its behavior know that it is bad • Symmetric Faulty: All good nodesobserve consistent error manifestations,but do not know that it is bad• Asymmetric Faulty: No assumption ismade about the behavior. The behaviorof an asymmetrically faulty unit hasdifferent manifestations to at least twodistinct good nodesSeveral formal verifications have been performed using this fault classification. We will be able to adapt some of these proofs to the conceptual design of the SPIDER. When the development reaches the stage of a detailed implementation, we will use this same classification when conducting the Failure Modes and Effects Analysis (FMEA).Reliability AnalysisThe system level reliability analysis uses the Semi-Markov Unreliability Range Evaluator (SURE) tool developed at NASA Langley Research Center [8]. Some of the reliability models have been generated using the Abstract Semi-Markov Specification Interface to the SURE Tool (ASSIST) [9]. The developers of these tools and techniques are available for consultation on this project. In addition, they are available for expert review of the generated models.Additional ConsiderationsSeveral of the verification activities employ formal methods. As part of the conceptual design activities, the algorithms for providing the fault-tolerant services are being formally specified andverified using PVS [10] (/). The models, algorithms, and proofs will be reviewed by Langley personnel that have expertise in both formal methods and fault-tolerance. In addition, some of the detailed design artifacts may be subjected to formal analysis.The focus of the verification activities during the detailed design and implementation stages will be to preserve the integrity of the verification performed at the conceptual design level. We intend to explore elemental analysis and safety-specific analysis as we proceed, but we do not yet have sufficient understanding of these techniques. Tool Assessment and QualificationSection 11.4 of DO-254 details the requirements for tool assessment and qualification. If the output of a tool is independently checked in some manner, it is not necessary to qualify the tool. Given the limited resources of this project, it is not feasible to undertake a tool qualification exercise. Therefore, in this design effort, the output of each tool will be independently checked.Design ConceptThe system concept for this case study is the SPIDER family of fault-tolerant architectures. One of the design goals is that the SPIDER will support various fault-tolerant configurations. This will enable experimentation with different schemes for automatic recovery from multiple correlated transient faults.The SPIDER architecture is intended tosupport a collection of N simplex general purpose processing elements communicating over a Reliable Optical Bus (ROBUS). One logical view of the SPIDER architecture is depicted in Figure 2.Figure 2: SPIDER Logical ViewThe ROBUS behaves as a time-division multiple access (TDMA) broadcast bus. For the ROBUS to provide unhindered access to all good nodes, it must be protected against any one node monopolizing its capacity. Furthermore, the communication model must support several fundamental services. The essential goal is to ensure reliable communication between all pairs of fault-free processing elements in the system. To ensure this flexibility, the ROBUS design shall guarantee that all good processing elements observe an identical sequence of messages. This will enable the development of several fault-tolerance strategies combining the simplex nodes. For example, Figure 3 illustrates a possible SPIDER configuration with three processors in a Triple Modular Redundant (TMR) configuration, four processors in a dual-dual configuration and a single simplex processor.Figure 3: Sample SPIDER ConfigurationKey Design RequirementsThe primary requirement for the ROBUS is that it shall ensure that all fault-free attached processing elements observe identical message sequences, even if there are a bounded number ofphysical component failures within the ROBUS. This implies that the ROBUS will be a realization of a special purpose fault-tolerant device. If the ROBUS can be shown to meet this requirement, then we have assurance that the failure modes of the attached processing elements are limited to symmetric or benign manifestations only. It will be impossible for an attached node to exhibit asymmetric behavior.Schedule AgreementThe first implementation of the SPIDER will be based upon an assumption of a static, predetermined communication schedule. This is similar to the approach taken for ARINC 659 [11] and the Time-Triggered Architecture [12]. The communication protocol for the first implementation of the SPIDER will be based upon the protocol developed by Malekpour for theFBL/PBW testbench [3]. This is a statically scheduled TDMA protocol.All analysis will be based upon the weaker assumption that all fault-free nodes agree on the communication schedule. This will allow future exploration of dynamic scheduling algorithms for later instances of the SPIDER architecture.Interactive ConsistencyIn a redundant computer system, it is necessary to ensure that all single-source data items are consistently replicated among the redundant computational elements. Otherwise, a single faulty source may overwhelm the redundancy in the system. There are several published algorithms for ensuring interactive consistency; the first fully general solution is by Pease, Shoshtak, and Lamport [13]. Interactive consistency requirements are:Agreement---All non-faulty receivers agree on the single-source data value receivedValidity---If the originator of the data is non-faulty, then all non-faulty receivers receive the transmitted valueProtocols achieving interactive consistency are frequently referred to as Byzantine Agreement protocols, following the presentation of the problem in [14]. Byzantine agreement protocols depend on the assumption that redundant elements fail independently. Specifically, it is required that the nodes participating in the protocol are sufficiently physically and electrically isolated to ensure that a fault in one node cannot cause a fault in another node. These isolation regions of the design are termed Fault-Containment Regions (FCRs). An FCR may exhibit erroneous behavior. Additional logic is required to address potential error propagation. This is only possible if a sufficient number of FCRs are fault-free. There are several examples of formally verified interactive consistency algorithms available. The internal topology of the ROBUS is sufficiently similar to the Draper FTP architecture [15] that we were able to adapt its interactive consistency protocol. In addition, we were also able to adapt the PVS verification presented by Lincoln and Rushby [16].Clock SynchronizationBoth interactive consistency and TDMA scheduling require that the redundant nodes be synchronized within a known skew. The general requirements for clock synchronization are:Precision---There is a small constant d such that for any two good clocks at real time t:|C1(t) -C2(t)| < dAccuracy---All good clocks maintain an accurate measure of the passage of timeAs in the case of interactive consistency, clock synchronization protocols assume that the redundant clocks are in separate FCRs and that a sufficient number of FCRs are fault-free. There are several clock synchronization protocols discussed in the research literature. Ramanathan et al provide a survey of different approaches [17]. We have adapted a synchronization scheme proposed by Davies and Wakerly [18] for use in the ROBUS. There are established techniques for formal verification of clock synchronization algorithms [19] [20]. We have modified the approach presented in [20] for the verification of the SPIDER synchronization protocol.DiagnosisThe ROBUS shall support distributed diagnosis in the presence of a bounded number of FCR failures. The goals of a diagnosis algorithm are to ensure the following properties:Correctness---Every FCR diagnosed as faulty by a good FCR is indeed faultyCompleteness---Every faulty FCR is eventually diagnosed as faultyThere exist fault scenarios where it is impossible to identify which FCR is faulty, so in these cases diagnosis is necessarily incomplete. However, it is essential to always ensure the correctness property. The ROBUS will be designed against a modified completeness property that is consistent with the fault assumptions of the clock synchronization and Byzantine agreement protocols. We will adapt the algorithms and verification presented in [21].Concluding RemarksWe are currently involved in the conceptual design phase of a case study exercising the new RTCA document DO-254: Design Assurance Guidance for Airborne Electronic Hardware. For the case study, we have chosen to design a central subsystem of a new fault-tolerant architecture. For this design, we have chosen to emphasize early life-cycle development and verification activities. It is our belief that if we get the conceptual design right, then it will be easier to assure correctness of the detailed design and implementation.The principal focus of our conceptual design verification activities is formal proof that the fault-tolerance protocols are correct. Subsequent design and verification activities will be focused on preserving the implementation integrity of the verified algorithms.AcknowledgementsWe are grateful to Leanna Rierson and Pete Saraceni of the FAA for partially funding this effort under Interagency Agreement DTFA03-96-X-90001.References[1] RTCA, 2000, DO-254: Design Assurance Guidance for Airborne Electronic Hardware, RTCA, Inc., Washington, DC.[2] Palumbo, D.L., 1996, Fault-tolerant processing system, United States Patent 5,533,188.[3] Malekpour, M., To Appear, Fly-by-Light/Power-by-Wire Fault-Tolerant Fiber-Optic Backplane, NASA Contractor Report, NASA Langley Research Center, Hampton, VA. [4] Free Software Foundation, 1998, CVS -Concurrent Versions System,/software/cvs/cvs.html.[5] Osier, J. M., and B. Kehoe, 1996, Keeping Track: Managing Messages with GNATS,/gnats/gnats_toc.html.[6] Beland, S.C., and B. BonJour, 2000, Functional Failure Path Analysis of Airborne Electronic Hardware, in Proceedings of the 19th Digital Avionics Systems Conference, Philadelphia, PA. [7] Kieckhafer, R. M., C. J. Walter, A. M. Finn, and P. M. Thambidurai, 1988, The MAFT Architecture for Distributed Fault Tolerance, IEEE Transactions on Computers, 37 (4), pp. 398-405.[8] Butler, R. W., and A. L. White, 1988, SURE Reliability Analysis: Program and Mathematics, NASA Technical Paper, 2764.[9] Johnson, S.C., and D. P. Boerschlein, 1995, ASSIST User Manual, NASA Technical Memorandum 4592, NASA Langley Research Center, Hampton, VA.[10] Owre, S., J. Rushby, N. Shankar, and F. von Henke, 1995, Formal Verification for Fault-Tolerant Architectures: Prolegomena to the Design of PVS, IEEE Transactions on Software Engineering, 21 (2), pp. 107-125.[11] ARINC, 1993, ARINC Specification 659: Backplane Data Bus, Aeronautical Radio, Inc., Annapolis, MD.[12] Kopetz, H., 1997, Real-Time Systems: Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, Boston.[13] Pease, M., R. Shostak, and L. Lamport, 1980, Reaching Agreement in the Presence of Faults, Journal of the ACM, 27 (2), pp. 228-234.[14] Lamport, L., R. Shostak, and M. Pease, 1982, The Byzantine Generals Problem, ACM Transactions on Programming Languages, 4 (3), pp. 382-401.[15] Smith, T.B., 1984, Fault Tolerant Processor Concepts and Operation, in Fourteenth International Conference on Fault-Tolerant Computing, IEEE Computer Society Press, pp. 158-163.[16] Lincoln, P., and J. Rushby, 1994, Formal Verification of an Interactive Consistency Algorithm for the Draper FTP Architecture Under a Hybrid Fault Model, Proceedings of the Ninth Annual Conference on Computer Assurance, pp. 107-120.[17] Ramanathan, P., K. G. Shin, and R. W. Butler, 1990, Fault-Tolerant Clock Synchronization in Distributed Systems, IEEE Computer, 23 (10), pp. 33-42.[18] Davies, D., and J. F. Wakerly, 1978, Synchronization and Matching in Redundant Systems, IEEE Transactions on Computers, C-27 (6), pp. 531-539.[19] Miner, P.S., 1993, Verification of Fault-Tolerant Clock Synchronization Systems, NASA Technical Paper 3349, Hampton, VA.[20] Schwier, D., and F. von Henke, 1998, Mechanical Verification of Clock Synchronization Algorithms, Proceedings 5th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, pp. 262-271.[21] Walter, C. J., P. Lincoln, and N. Suri, 1997, Formally Verified On-Line Diagnosis, IEEE Transactions on Software Engineering, 23 (11), pp. 684-721.。