General Terms

Automated Timing Model GenerationAjay J. Daga, Loa Mize, Subramanyam Sripada, Chris Wolff, Qiuyang WuSynopsys, Inc.2025 NW Cornelius Pass Rd., Hillsboro, OR 97124503-547-6900

{ajdaga, loa, ssubram, wolff, qwu}@synopsys.com

ABSTRACTThe automated generation of timing models from gate-levelnetlists facilitates IP reuse and dramatically improves chip-levelSTA runtime in a hierarchical design flow. In this paper wediscuss two different approaches to model generation, the designflows they lend themselves to and results from the application ofthese model generation solutions to large customer designs.

Categories and Subject DescriptorsJ.6: ComputerApplication.CAD.General TermsDesign, Performance, Algorithm, VerificationKeywordsStatic Timing Analysis, Model Generation. EDA.

1. INTRODUCTIONSystem-on-a-chip (SoC) design is performed in an inherentlyhierarchical manner. Intellectual property (IP) is integrated on-chip with new blocks that are often designed by geographicallydispersed teams. Timing models are important in such a designflow because they are a compact means of exchanging theinterface timing information for blocks. The automatic generationof timing models from the gate-level netlist for a design is key tosustaining a hierarchical SoC design flow for two reasons:

A Biologically Inspired Programming Modelfor Self-Healing SystemsSelvin George Department of Computer Science University of VirginiaCharlottesville, VAselvin@David EvansDepartment of Computer ScienceUniversity of VirginiaCharlottesville, VAevans@Lance DavidsonDepartment of BiologyUniversity of VirginiaCharlottesville, VAlance_davidson@ABSTRACTThere is an increasing need for software systems to be able to adapt to changing conditions of resource variability, component malfunction and malicious intrusion. Such self-healing systems can prove extremely useful in situations where continuous serviceis critical or manual repair is not feasible. Human efforts to engineer self-healing systems have had limited success, but nature has developed extraordinary mechanisms for robustness and self-healing over billions of years. Nature’s programs are encoded in DNA and exhibit remarkable density and expressiveness. We argue that the software engineering community can learn a great deal about building systems from the broader concepts surrounding biological cell programs and the strategies they use to robustly accomplish complex tasks such as development, healing and regeneration. We present a cell-based programming model inspired from biology and speculate on biologically inspired strategies for producing robust, scalable and self-healing software systems.Categories and Subject DescriptorsD.1.0 [Programming Techniques]: General; D.2.4 [Software/Program Verification] – reliability; F.1.1 [Models of Computation].General TermsDesign, Reliability, Experimentation, Security, Languages KeywordsBiological programming; self-healing systems; amorphous computing.1. INTRODUCTIONBiology is replete with examples of systems with remarkable robustness and self-healing properties. These include morphogenesis, wound healing and regeneration: Morphogenesis. A single cell develops into a full organism following a program encoded in its DNA that evolved over billions of years. Cells perform various actions like division, deformation and growth based on gene actions. The actions of the genes are dictated by the presence of chemical substances. Gene actions coupled with physical forces acting on a cell from its neighboring cells and external environment lead to a developed organism. Even in simple organisms, development is robust to many kinds of local failures and adapts to a wide range of environments. For example, when a cell dies, the neighboring cells sense changes in the environment and adapt their own development to correct the problem [6].Wound Healing. Almost all complex organisms have some sort of mechanism for healing simple wounds. In humans, when a minor injury happens, an inflammatory response occurs and the cells below the dermis (the deepest skin layer) begin to increase collagen (connective tissue) production. Later, the epithelial tissue (the outer skin layer) is regenerated. The interesting point here is the apparent level of awareness of the cells. Also, cells around the injury are able to adapt to a different function based on the new circumstances [2].Regeneration. Many organisms can regenerate new heads, limbs, internal organs or other body parts if the originals are lost or damaged. Organisms take two approaches to replacing a lost body part. Some, such as flatworms and the polyp Hydra, retain populations of stem cells throughout their lives, which are mobilized when needed. These stem cells retain the ability to regrow many of the body’s tissues. Other organisms, including newts, segmented worms and zebrafish, convert differentiated adult cells that have stopped dividing and form part of the skin, muscle or another tissue back into stem cells. When a newt’s leg, tail or eye is amputated or damaged, cells near the stump begin an extraordinary change. They revert from specialized skin, muscle and nerve cells into blank progenitor cells. These progenitors multiply quickly to about 80,000 cells and then grow into specialized cells to regenerate the missing part [5].We observe that nature’s approach to programming has the following properties:1. Environmental Awareness. Though the cells may havelimited communication capabilities, they act differently in response to sensed properties of the surrounding environment. This enables cells to react to changes in nearbycells, as well as the surrounding environment.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.WOSS '02, Nov 18-19, 2002, Charleston, SC, USA.Copyright 2002 ACM 1-58113-609-9/02/0011 ...$5.002. Adaptation. Many cells have a great amount of adaptability.In many organisms, at the beginning of morphogenesis, if one of the initial cells obtained by the first division of the germ cell dies then the surviving cell is often able to complete the development of the organism. This indicates that enough information is preserved to be able to “backtrack” to a previous state of development. This is due to the fact that all cells run the same cell-program and can hence respond to aberrant behavior from neighbors3. Redundancy. A non-redundant organism would have everycell assigned a fixed role in the development process. Any failure during the development process would produce a defective organism. Typical organisms have many cells devoted to the same function throughout development, so that failures of individual cells are inconsequential.Biological systems also exhibit redundancy of function, where several distinct mechanisms evolve for the same purpose in a single organism.4. Decentralization. There is no global coordination andlimited communication for most of the development process.Cells sense properties of their environment, and are most affected by nearby cells. Cells can induce neighboring cells to do a particular action, but there is no centralized control and limited long-distance communication.2. CELL-BASED PROGRAMMINGInspired by biological systems, we propose a cell-based programming model that can be used for software systems operation and healing. Our model is similar to the cellular automata that have been studied extensively since von Neumann’s early work [4], but differs in that it is more closely related to biological processes. In particular, we support a notion of cell division, a communication model based on chemical diffusion, and a rudimentary model of the physical forces involved. By developing a programming model more like nature’s, we believe we will produce more robust programs with natural self-healing properties.A related approach is amorphous computing, which considers approaches for programming a medium of randomly distributed computing particles. The Growing Point Language [1] and Origami Shape Language [3] both illustrate mechanisms for global self-organization using simple local communication of the agents. Self-healing properties are also being studied using GPL. As with our work, the challenge is to produce programs that generate predictable behavior with a locally unpredictable and non-traditional programming model. Because the underlying execution environment is inherently redundant and decentralized, robustness is practically inevitable if programs are constructed in the right way.We represent a cell program as an automaton containing discrete states and transitions between these states. Every cell comprising the program is in one of these states. The input to each cell state is the sensed properties of the local environment and the output is a transition to another state, or a division into two (possibly different) states. States are represented by circles and state transitions by directional arrows. Dots represent cell divisions.Our cell programming model incorporates: 1. Cell Division. A cell can divide into two daughter cells thatmay be dissimilar in orientation and chemical composition but have the same program (DNA). A cell has an axis calledthe apical-basal axis. Divisions can be either perpendicular tothis cell axis or along the plane containing the axis. The difference in chemical composition and also the different chemicals on their cell walls causes the two daughter cells tobehave differently from that point onwards. Cell division ismodeled by using a transition from one state to two states.2. Cell Actions. Cells can produce proteins and signalingchemicals depending on what genes are active. Chemicals produced this way affect the environment and neighboring cells through chemical diffusion.3. Gene Actions. Genes can activate or deactivate dependingon the presence or absence of a particular protein or a certaindegree of chemical concentration. Activation or deactivationof a gene results in cell actions like production of chemicals. The varying degrees of concentration produced by earlier cell actions (both by the cell and its neighbors) cause gene actions and gene actions cause cell actions; this results in a powerful programming paradigm. Cell actions such as production of chemicals are modeled using messages. Gene actions are modeled using cell state transitions; these are a result of received messages.A cell program begins with cells in an initial configuration, and all the cells follow transition rules like a finite state machine. Between steps, an environment simulator determines changes in external stimuli. The changes to the environment can be due to operations of the software system, expected input conditions or failure conditions. Since cells can sense their local environment it is possible for them to be able to perform failure recovery (healing) or re-composition of appropriate components (regeneration). Our simulator also provides opportunities to conduct experiments involving random and catastrophic failures. Two simple examples of cell programs are shown in Figure 1. Automaton A produces a line of cells as long as the input condition a exists. The condition a may represent the presence of food for growth. AutomatonB produces cells to combat intruders as long as it detects unfavorable conditions. This approach creates excess cells so that some may survive the malicious action.Figure 1. Example Cell ProgramsA. Creating a line of Cellsa – Condition favorableto continued cellproductionB. Robustness through replicationa – Favorable conditionsb – Unfavorable conditionsNumbered Circle – StateArrow – TransitionDot – Cell division3. SIMULATING CELL PROGRAMSUsing a simulator, we have conducted simulations of different cell programs. The simulator simulates a cell program on a simulation configuration. The simulation configuration is used to introduce new cells, chemical concentrations or failures. Our simulator is available at /cellsim .A sample program for creation of a self-healing blastula is shown below. A blastula is a spherical structure that is the first stage of development of many large organisms. A sufficient number of cells are needed before organism development proceeds to the next stage.state s1 {emits (sig, 0.1)transitions(0 <= sig <= 0.375) -> (s2, s2) axis; -> (s1); }state s2 {emits (sig, 0.1) transitions(0 <= sig <= 0.375) -> (s3, s3) normal-X; -> (s2); }state s3 {emits (sig, 0.1) transitions(0 <= sig <= 0.375) -> (s1, s1) normal-Y; -> (s3); }In the above cell automaton there are three cell-states – s1, s2 and s3. They are similar in that they emit the same signaling chemical sig and divide into two cells each if they sense that the concentration of sig is less than 0.375. The cell remains in its current state if the concentration of sig is above 0.375.(a)(b)(c)Figure 2. Simulated Blastula Program. (a) Blastula in 8-cell stage – starting from one cell; (b) damaged blastula – after killing one cell (c) after the blastula regenerates.This self-healing blastula has the property that if a few cells are killed, it will automatically heal itself by producing the required number of cells. Figure 2 shows a simulation of the blastula program for four steps, after which one of the cells was killed to observe the self-healing behavior. The surviving cells regenerate additional cells to continue the process. The principle behind this type of healing is that the once a cell was killed, it stopped producing the particular chemical that was being sensed by its neighbors. Note that nothing in the cell program explicitly deals with healing and regeneration. The neighbors of a failed cell just follow a different path in the cell-program due to the changed environmental conditions.4. TOWARDS SELF-HEALING SYSTEMSAlthough our initial experiments have focused on mimicking simple biological processes and generating basic geometric structures, our long-term goal is to develop techniques that can be used to produce robust, self-healing systems designed to perform a complex task. Developing complex programs using state diagrams, however, is infeasible. A high-level programming abstraction for cell-based programs is needed in which a programmer can describe desired processes at a high-level and a cell-program compiler will produce the steps of the automaton. An important design issue is which operations or abstractions should be part of the language and which can be composed of the elementary operations and hence can be kept outside the language. We are currently working on programming abstractions based on the biological cell model. If successful, programs described in this way will have intrinsic robustness, scaling and self-healing properties. We hope that our experiments with biological programs will provide insights into how to build more robust computer systems.5. ACKNOWLEDGMENTSThis work was funded in part by grants from the National Science Foundation (CCR-0092945 and EIA-0205327) and NASA Langley Research Center.6. REFERENCES[1] H. Abelson, D. Allen, D. Coore, C. Hanson, G. Homsy, T.Knight, R. Nagpal, E. Rauch, G. Sussman and R. Weiss, Amorphous Computing, Communications of the ACM, Volume 43, Number 5, p. 74-83. May 2000.[2] Mary Y. Mazzotta. Nutrition and wound healing . Journal ofthe American Podiatric Medical Association. Volume 84, Number 9, p. 456–62. September 1994. [3] Radhika Nagpal, Programmable Self-Assembly:Constructing Global Shape using Biologically-inspired Local Interactions and Origami Mathematics, PhD Thesis, MIT Department of Electrical Engineering and Computer Science, June 2001. [4] John von Neumann, Theory of Self-Reproducing Automata.University of Illinois Press, 1966 (Originally published in 1953).[5] Helen Pearson, The regeneration gap , Nature ScienceUpdate. 22 November 2001. [6] Lewis Wolpert, Rosa Beddington, Peter Lawrence, ThomasM. Jessell, Principles of Development , Oxford University Press. 2002.。

Using Redundancy to Improve Robustness of DistributedMechanism ImplementationsJeffrey Shneidman David C.ParkesABSTRACTThis paper introduces computation compatibility and communica-tion compatibility as requirements for a distributed mechanism im-plementation.Just as payments are used to create incentive com-patible mechanisms,some technique must be used to create com-putation/communication compatible mechanisms.This paper ex-plores computation redundancy and communication redundancy astwo such techniques.This paper uses interdomain routing as an ex-ample domain,and considers where redundancy can succeed andfail in addressing cheating with respect to computation and com-munication.Categories and Subject DescriptorsF.2[Theory of Computation]:Analysis of Algorithms and Prob-lem Complexity;J.4[Computer Applications]:Social and Behav-ioral Sciences—Economics.General TermsAlgorithms,Economics.1.INTRODUCTIONMechanism design(MD)studies how best to specify the strate-gic situation,or“rules of the game”,so that the system as a wholeexhibits good behavior in equilibrium when self-interested nodespursue self-interested strategies.Classical MD assumes that theplayers feed their calculated strategies to a special obedient cen-ter that performs the mechanism calculation and declares the out-come.This classic approach is not realistic in many computationalsettings,where networks may consist of strategizing agents and aspecial center may not exist,with computation and communicationspread over several rational nodes.Distributed algorithmic mech-anism design(DAMD)[2]more accurately models network situa-tions,where both agents and resources are distributed.One large problem in implementing distributed mechanisms isthat mechanism design ideas were originally intended to reasononly about agent inputs[4].It is always assumed in traditional MDliterature that messages from agents to the centerflow freely andthat the center performs all necessary computation.In this paper,3.REDUNDANCY AS A TOOLRedundancy can be used as a tool to build distributed systems that are computation-and communication compatible.Intuitively, redundancy is a device that can promote coordination around the computation and communication specification provided by a mech-anism creator.In this work,we assume that redundancy is used to check whether an individual node has deviated,in which case the mechanism is terminated and no outcome is implemented.We as-sume that all nodes prefer that a mechanism computes some out-come rather than no outcome,and rely on this in order to avoid having to explicitly define methods to punish deviating nodes.1 We consider two forms of redundancy.Thefirst is redundant rmally,this means that multiple disjoint paths exist between nodes and are used to relay copies of messages(e.g. node inputs or details of mechanism computation).Sending mes-sages down multiple paths in a biconnected network,where there are at least two independent paths from any node to any other node, can ensure that single node deviations can be detected.2The second form of redundancy is redundant computation.This idea proposes that nodes be required to perform parallel(hopefully identical)computations for comparison purposes by a third party. In the centralized mechanism case,this can mean designating an-other node as a redundant center.In the decentralized mechanism case,where computation is spread throughout the network,some set of alternate nodes might be assigned to receive and the same information and perform identical computations.4.EXAMPLE:INTERDOMAIN ROUTING It helps to explore the problem of computation-and commu-nication compatibility in the context of a previously stated prob-lem.Feigenbaum et al.[1](hereafter FPSS)have previously de-fined a distributed algorithm to implement a BGP-based mecha-nism for lowest cost interdomain routing.FPSS focus on whether a Vickrey-Clarke-Groves(VCG)mechanism can be implemented without a center and without requiring an unreasonable amount of additional communication or computation,but focus less on the is-sue of computation-and communication-compatibility.There are two logical phases in FPSS.In thefirst phase,a node finds the lowest cost paths to all possible routing destinations.In the second phase,a node executes a pricing calculation that deter-mines transit node payments(how much it must pay each transit node for traffic originating at it and traveling to the various desti-nations.)In FPSS,a complete message to a neighbor(and thus the totality of what can be manipulated)consists of three items:a rout-ing table which consists of paths and total path costs,a list of the declared costs of transit nodes,and a sparse pricing table.A rational node will cheat to achieve at least one of two goals. First,a node can try to increase the amount of money it is paid. Second,a node can try to decrease the amount of money is must pay.We consider each phase in turn.Phase I.A node broadcasts paths and forms LCPs.Since FPSS as-。

Trust-Based Contracting in Supply ChainsSandip Sen Math&CS Department University of T ulsa sandip@Sabyasachi SahaMath&CS DepartmentUniversity of T ulsasaby@Dipyaman BanerjeeMath&CS DepartmentUniversity of T ulsadipu@Categories and Subject DescriptorsI.2.11[Artificial Intelligence]:Distributed Artificial Intelligence—Multiagent systemsGeneral TermsAlgorithm,Performance,ExperimentationKeywordscontracting,trust,monopoly1.INTRODUCTIONEngineering robust,vibrant supply chains that allowflexibility, modularity,and scalability present open,important,and unsolved research challenges.As a result,supply chain management where rational agents represent interests of individual entities and orga-nizations have been an area of active research[1].Agent-based approaches typically attempt to optimize the profitability of enti-ties with emphasis on pricing and scheduling.Researchers in busi-ness and management science,however,have recognized that a key component of decision-making in real-world supply chains is the consideration of trust between the contracting organizations[2]. We use a contracting framework to allocate tasks:manufacturers announce contracts for tasks with given deadlines;suppliers bid on these tasks;and the contract is allocated to a highly trusted bidder. Trust of an agent is measured as the fraction of assigned tasks for which the agent could meet the deadline.We assume that the trust preferences of the contractor,the task deadline distribution and the performance distribution of the contractees are known.We then develop a precise bidding strategy for trust-building contractees. The motivation is to bid only on those tasks for which they have a high likelihood of meeting deadlines.However,not bidding on tasks also reduces the success rate of completing tasks.We providea probabilistic analysis to handle this tradeoff.2.CONTRACTING MODELThe Request For Quote(RFQ)of each task T i contains an as-sociated deadline d(T i)drawn from a distribution T.P j,de-Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on thefirst page.To copy otherwise,to republish,to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.AAMAS’05,July25-29,2005,Utrecht,Netherlands.Copyright2005ACM1-59593-094-9/05/0007...$5.00.fined over the closed interval[l,h],represents the distribution fromwhich the actual time taken by the suppliers to process tasks is drawn.For continuous distributions,this means h l P(x)dx=1 and h l T(y)dy=1.Each contractor maintains a trust rating,t c for each possible con-tractee,c,which is the proportion of time that contractee could meet an assigned task deadline.A contractor considers a contractee b tobe more trusted than another contractee b ifγ∗t b<tb,where γ>1is a trust constant.The contractor of a task assigns it ran-domly to one of those contractees for whom there are no other more trusted contractees.The goal of a contractee j is to maximize its success in procuring and delivering contracts,i.e.,its success ratebh bl r(j,y)T(y) y l P j(x)dx dy,(1)where r(j,y)is the probability that a task of length y is assigned to agent j,the integration within the parenthesis represents the like-lihood of meeting the deadline y and bl,bh are respectively the minimum and maximum deadlines for tasks on which j will bid.3.TRUST BUILDING MECHANISMWe use two types of bidding strategies for a contractee j in re-sponse to an RFQ for a task t i:(a)Greedy(G)agents bid for any task for which is a non-zero probability of meeting the deadline, i.e., d(T i)l P j(x)dx>0,Trust-building(TB)agents focus on building trust and hence bids only for tasks whose deadlines they are likely to meet.While this means that it will compete for less tasks,in the long run such agents expect to be favorably treated for awarding contracts with‘safer’tasks,i.e.,tasks that they are likely to be able to complete by the deadline.The key consideration here is the choice of the minimum deadline threshold,D,for bidding such that the TB contractee is viewed by the contractor to be more trustworthy than a G contractee.The Figure1presents a typical sit-uation with task and performance probability distributions and the deadline D below which TB agents will not bid.The average expected success likelihood or trustworthiness of an agent who wins all tasks in the region[bl,bh]is given by¯P(bl,bh)=1T bl,bh bh bl T(y)y l P j(x)dx dy,(2)where T x,y= y x T(z)dz,is the cumulative probability of tasks arriving with deadlines in the region[x,y].If an agent wins only a fraction f of tasks in that region,the corresponding average success likelihood is f¯P(bl,bh).To facilitate the presentation of the analysis we consider the steady state case,where one of the TB agents always win the contract0.050.10.150.20.250.30.350.412345678910p r o b a b i l i t ydeadlineperformance distr.task distr.DFigure 1:Example continuous task deadline and performance distributions.when they bid (because they have been recognized to be more trust-worthy than greedy contractees),and at other times one of the G agents win the contract.First we note that there is no reason for the TB agents to not bid on tasks at the higher end of the task deadline distribution.Hence,the upper limit of the range of task deadlines a TB agent will bid,bh T B is equal to h .Therefore,at steady state,the TB agents will win all the tasks for deadlines in the range [D ss ,h ]and G agents will win all contracts in the re-gion [l,D ss ),where D ss is the deadline threshold above which TB agents will bid in steady state.For the TB agent to be viewed to be more trustworthy the following inequality must be satisfied:¯P(D ss ,h )>γ¯P (l,D ss ).(3)This implies that at the steady state,the TB agents have at least γtimes higher trustworthiness at steady state.Equations 2and 3can be used to calculate D ss .The assumption of TB agents winning whenever they bid is not valid at the outset when they are yet to be recognized as more trust-worthy than greedy agents.Hence D ss is not the appropriate choice for the initial minimum task deadline to bid for,D I ,by TB agents.To calculate D I ,we assume that tasks are initially assigned ran-domly between all bidders in the population.So,while all the tasks with deadlines in the range [l,D I )will be assigned to G con-tractees,tasks in the region [D I ,h ]will be assigned to G versus TB bidders in the ratio of N G to N T B .The choice of D I should be such that it allows a TB agent to have at least γtimes higher trustworthiness when tasks are being assigned randomly between bidders:N T B N¯P (D I ,h )>γT l,D I ¯P (l,D I )+T D I ,h N G N¯P (D I ,h )T l,h.(4)The LHS of the inequality represents the proportion of tasks ex-pected to be successfully delivered by TB agents when tasks are randomly assigned between all bidders and the TB agents bid only in the interval [D I ,h ].The term within the parenthesis on the RHS denotes the proportion of tasks successfully delivered by G agents in this period.The terms T l,D I and T D I ,h are used to normalize the trustworthiness in the regions [l,D I ]and [D I ,h ]respectively.The inequality in Equation 4can be satisfied for a range of D I val-ues.The TB agent uses the minimum value in the range which also satisfies the inequality N T B >γN G T D I ,h .0.20.40.60.81020*******800100012001400160018002000S e l e c t i o n R a t i ono_of_iterationSelection Ration, Tp = 40trust-buildinggreedyFigure 2:Selection Ratio (T p =40,γ=1.25).4.EXPERIMENTAL RESULTSWe use triangular performance and task distributions defined inthe range [0,60]with the highest likelihood point at T p =40.From the ratio of selection of one Greedy and one TB agent by a contrac-tor (shown in Figure 2)we observe that the TB contractee clearly outperforms the greedy contractee as it succeeds in winning almost three times as many contracts.Though winning contracts do not necessarily mean successfully fulfilling them,as TB contractees bid for tasks of longer deadline,the actual ratio of their success rates is likely to be even higher.Initially,the customer makes awards ran-domly between the bidders,and the greedy agent is selected more often as it bids over the entire task range compared to the TB agent who bids only if the task deadline is greater than D I .Over time,as the TB contractee is significantly more successful in meeting con-tract deadlines compared to the greedy agent,it gains the trust of the contractor and is thereafter selected whenever it bids.5.OBSERV ATIONSWe investigate a particular trust-based contracting framework where contractees with significantly higher historical success rates in meeting contract deadlines are preferentially selected over less “punctual”agents.We argue that in order to build and maintain the trust of their contractor,contractees will need to avoid bidding on risky tasks,i.e.,tasks for which there is a significant risk of failing to meet deadlines.The goal of such strategic bidding is to more than recover the loss from not bidding on such high-risk tasks by more consistently winning the contracts on tasks with longer dead-lines.As a result,such trust-building agents bid less often for tasks,but win and successfully meet the deadline of tasks they bid for in comparison to “greedy”agents who bid for all tasks.We have calculated the initial and steady state bidding thresh-old to earn trust.An interesting,open question is how to vary the threshold over time to get from D I to D ss while consistently main-taining the trust of the contractor.That process might lead to TB agents monopolizing the market!Acknowledgments:This work has been supported in part by an NSF award IIS-0209208.6.REFERENCES[1]W.E.Walsh and M.P.Wellman.Decentralized supply chainformation:A market protocol and competitive equilibrium analysis.JAIR ,19:513–567,2003.[2]B.Welty and I.Becerra-Fernandez.Managing trust andcommitment in collaborative supply chain munications of the ACM ,44(6):67–73,2001.。

外贸常用词第一期:GeneralTerms1establishingbusinessrelation建立业务关系13.acceptance-接受2.inquiry-询盘14.signingacontract-签订合同3.offer-报盘15.claim-索赔4.counteroffer-还盘16.agency-代理5.quantity-数量mission-佣金6.packing-包装18.exclusivesales-包销独家销售7.timeofshipment-装运期19.jointventure-合资企业8.price-价格pensationtrade-补偿贸易9.discount-折扣21.processingandassemblingtrade-加工装10.termsofpayment-支付条款配贸易11.insurance-保险22.thetermsofinternationaltrade国际贸易modityinspection-商品检验术语第二期:Establishingbusinessrelation建立业务关系1.recommendation推荐、介绍24.garment服装rm通知25.meetwithgreatfavor受欢迎3.enterintobusinessrelations建立业务关系26.creditstanding信用地位4.catalogue目录27.state-operated国营的5.foryourreference供您参考28.currency,Chinesecurrency,British6.specificinquiry具体询价currency货币，中国货币，英国货币7.promptly立即29.investment投资8.representative代表30.along-terminvestment长期投资9.chamberofcommerce商会31.aprofitableinvestment有利可得的投资10.specializein专营32.asafeandsureinvestment安全可靠投资11.onthebasesofequalityandmutual33.aheavyinvestment巨额投资benefit在平等互利的基础上34.investmentintent投资意向12.pamphlet小册子35.investmentpartner投资伙伴13.arangeof一套36.directinvestment直接投资14.makeoffers报价37.investmentenvironment投资环境15.importandexportcorporatio进出口公司38.investor投资者16.silk丝绸39.enterprise企业17.cottonpiecegoods棉布40.jointventureenterprise合资企业18.blouse女衬衫41.cooperativeenterprise合作企业19.beofthelateststyle最新式样42.exclusivelyforeign-ownedenterprise外20.financialposition财务状况商独资企业21.tradereputation贸易声誉43.state-ownedenterprise国营企业22.ondisplay展出44.collectively-ownedenterprise集体企业23.woolenknitwear毛织品45.individuallyownedenterprise个体企业第三期:inquiry询盘1.generalinquiry一般询盘3.dealer商人2.specificinquiry具体询盘4.quotation报价13.salesdepartment销售部26.todeliversthtosb把某物交付给某人14.purchase购买27.shipment装船15.enquiry询价28.tomakeshipment装船16.quote开价29.toreceiveshipment接货17.sample样品30.partialshipment分批装船18.along-termcontract长期合同31.promptshipment即期装运19.discount折扣32.timeofshipment装运期20.grant批准33.offer报盘报价21.tomakeaninquiryforsth对某物询价34.afirmoffer实盘22.tokeeptheinquiryonfil把询价记录在卷35.acounteroffer还盘23.toinquiryforsth对某物询价36.toacceptanoffer接受报盘24.toinquiryaboutsth询问某事37.toextendanoffer延长报盘25.process加工38.torenewanoffer更新报盘26.guarantee,guarantor保证,保证人39.towithdrawanoffer撤消报盘27.delivery交货40.thevalidityofanoffer报盘有效期28.portofdelivery交货港41.tomakeanoffer报价29.timeofdelivery交货期42.toofferfirm报实盘30.promptdelivery即期交货43.tooffersubjecttofinalconfirmation报盘31.toeffectdelivery办理交货以最后确认为准32.tomakedelivery办理交货44.specializein专门经营33.topostponedelivery推迟交货第四期:Counteroffer还盘24.counteroffer还盘25.enjoygreatpopularity享有盛誉26.readyseller;quickseller;quick-sellingproduct畅销品27.concludebusinesswithsb.与某人达成交易28.closebusiness,closeadeal,closeatransaction,closeabargain达成交易29.tradeterms贸易条件30.tradeagreement贸易协定31.tradefair交易会32.trademark商标33.foreigntrade对外贸易11tradeinsth经营某物3.tradewithsb.与某人交易4.favourableprice优惠价格5.favourableterms优惠条件6.quotation行情7.discountquotation贴现行情8.exchangeratequotation外汇行情mission佣金10.acommissionof....%;....%commission.百分之几佣金11.your..%commission你的百分之几佣金12.Theabovepriceincludesyourcommissionof2%.上述价格包括你方2%佣金.34.generalpractice惯例35.acceptanorder接受订单36.cancelanorder撤消订单37.confirmanorder确认订单38.executeanorder履行订单39.abackorder尚未执行的订单40.afreshorder新订单41.arepeatorder续订订单第五期:Quantity数量34.weight重量16.volume体积35.metricton公吨17.cubicmeter立方米36.longton长吨18.capacity容积37.shortton短吨19.litre升38.kilogram,kilo,kg公斤20.gallon加仑39.pound,lb磅21.bushel蒲式耳40.ounce,oz盎司22.metricsystem公制41.number个数23.britishsystem英制42.piece件24.U.S.System美制43.pair双25.grossweight毛重11dozen打weight净重13.ream令27.shippingweight装运重量14.set套ndedweight卸货重量15.length长度29.theoreticalweight理论重量16.area面积第六期:Packing包装1.packaging包装方法16.shrunkpackaging,压缩包装2.blisterpacking起泡包装17.foam-sparypackaging喷泡沫包装3.neutralpacking中性包装18.gift-wrap礼品包装4.skinpacking吸塑包装19.bag,sack袋5.hangingpacking挂式包装20.jutebag麻袋6.catchsb'seye引某人注目21.polythelenebag,plasticbag塑料袋7.mark唛头22.polythelenenet尼龙绳网袋8.unlabelledpacking无牌的包装23.zipperedbag拉链袋9.inbulk散装24.case,chest箱10.inloosepacking散装25.box盒11nudepacking裸装26.woodencase木箱12.bulkpack整批包装27.carton纸箱13.consumerpack零售包装28.container集装箱rgepacking大包装29.rate板条箱15.innerpacking,externalpacking,end30.fibreboardcase纤维板箱packing小包装第七期:Packing(二)包装42.packet小包16.kraftpaper牛皮纸43.bale包17.canvas帆布44.bundle捆18.fibreboard纤维板45.tin,can罐头19.nylonstrap尼龙腰子46.basket篮，篓，筐20.plasticstrap塑料腰子47.bamboobasket竹篓21.adhesivetape胶带48.bottle瓶22.stuffingmaterial填料49.woodenkeg小木桶23.nylonplastic尼龙丝50.hogshead大桶24.fermentedplastic泡沫塑料51.irondrum铁桶25.paperscrap纸屑11cylinder铁桶26.sawdust木屑44.barrel琵琶桶27.tarpaper沥青纸45.drum圆桶28.waxpaper蜡纸46.waterproofpaper防水纸29.slushingcompound润滑油47.cellophone玻璃纸30.tarpaulin油布、防水帆布第八期:Shipment装运17.backlog积压而未交付的订货12.bookup（票、车位、舱位等）订完18.termsofshipment装运条件13.tranship转运19.preparegoods备货14.transhipment转载20.load装货15.ForceMajeure人力不可抗力21.unload卸货16.EuropeanMainPorts--EMPs欧洲主要22.board木板，板，船舷口岸23.onboard在船（或车、飞机）上17.vessel船；飞船；飞机24.steamer轮船18.thefirstavailablevessel第一艘可订到25.spaceofasteamer舱位的船26.shippingdepartment运输部门19.callat停泊11liner班轮，班机20.duly按期地，按时的第九期:Price价格11.Priceterms价格条件9.driveahardbargainoversth.为某事拼命12.bargain讨价还价讨价还价13.currency货币10.abargainsale廉价出售14.onthelowside价格偏低11.rock-bottomprice最低价15.marketprice市场价12.F.O.B船上交货16.currentprice现行价13.C.I.F.成本加保险费，运费价17.floorprice底价14.CFR成本加运费价18.makeabargainwithsb与某人成交外贸常用英语词汇大全(进出口贸易)出口信贷exportcredit出口津贴exportsubsidy贸易逆差unfavorablebalanceoftrade商品倾销dumping外汇倾销exchangedumping进口配额制importquotas优惠关税specialpreferences自由贸易区freetradezone保税仓库bondedwarehouse对外贸易值valueofforeigntrade贸易顺差favorablebalanceoftrade国际贸易值valueofinternationaltrade普遍优惠制generalizedsystemofpreferences-GSP最惠国待遇most-favorednationtreatment-MFNT价格条件价格术语tradeterm(priceterm)回佣returncommission运费freight.装运港portofshipment单价unitprice折扣discount,allowance码头费wharfage卸货港portofdischarge总值totalvalue批发价wholesaleprice卸货费landingcharges目的港portofdestination金额amount零售价retailprice关税customsduty进口许口证importlicence净价netprice现货价格spotprice印花税stampduty出口许口证exportlicence含佣价priceincludingcommission期货价格forwardprice港口税portdues现行价格（时价）currentprice/prevailingprice国际市场价格world(International)Marketprice离岸价（船上交货价）FOB-freeonboard成本加运费价（离岸加运费价）C&F-costandfreight到岸价（成本加运费、保险费价）CIF-cost,insuranceandfreight交货条件班轮regularshippingliner交货delivery驳船lighter轮船steamship(缩写S.S)舱位shippingspace装运、装船shipment油轮tanker租船charter(thecharteredship)报关clearanceofgoods交货时间timeofdelivery陆运收据cargoreceipt定程租船voyagecharter提货totakedeliveryofgoods装运期限timeofshipment空运提单airwaybill定期租船timecharter正本提单originalBL(originalbilloflanding)托运人（一般指出口商）shipper,consignor选择港（任意港）optionalport收货人consignee选港费optionalcharges选港费由买方负担optionalchargestobebornebytheBuyers或optionalchargesforBuyers’account一月份装船shipmentduringJanuary或Januaryshipment一月底装船shipmentnotlaterthanJan.31st.或shipmentonorbeforeJan.31st.一/二月份装船shipmentduringJan./Feb.或Jan./Feb.shipment在......(时间)分两批装船shipmentduring....intwolots在......(时间)平均分两批装船shipmentduring....intwoequallots分三个月装运inthreemonthlyshipments分三个月，每月平均装运inthreeequalmonthlyshipments立即装运immediateshipments即期装运promptshipments收到信用证后30天内装运shipmentswithin30daysafterreceiptofL/C(LetterofCredit) 不允许／允许分批装船partialshipmentnotallowed／partialshipmentnotpermitted／partialshipmentnotunacceptable交易磋商、合同签订订单indent业务洽谈businessdiscussion订货；订购book;booking限**复subjecttoreply**电复cablereply限**复到subjecttoreplyreachinghere**实盘firmoffer有效期限timeofvalidity递盘bid;bidding有效至**:validtill**购货合同purchase递实盘bidfirm还盘counteroffercontract发盘（发价）offer销售合同salescontract发实盘offerfirm购货确认书purchaseconfirmation询盘（询价）inquiry;enquiry销售确认书salesconfirmation指示性价格priceindication一般交易条件generaltermsandconditions速复replyimmediately以未售出为准subjecttopriorsale参考价referenceprice需经卖方确认subjecttoseller’s习惯做法usualpracticeconfirmation交易磋商businessnegotiation需经我方最后确认subjecttoourfinal不受约束withoutengagementconfirmation贸易方式INT(拍卖auction)寄售consignment招标invitationoftender投标submissionoftender一般代理人agent总代理人generalagent代理协议agencyagreement累计佣金accumulativecommission补偿贸易compensationtrade（或抵偿贸易）compensating/compensatorytrade（又叫：往返贸易）countertrade来料加工processingongivingmaterials来料装配assemblingonprovidedparts独家经营/专营权exclusiveright独家经营/包销/代理协议exclusivityagreement独家代理soleagency;soleagent;exclusiveagency;exclusiveagent品质条件品质quality宣传小册pamphlet原样originalsample公差tolerance规格specifications货号articleNo.复样duplicatesample花色（搭配）assortment说明description样品sample对等样品countersample增减5%plusorminus标准standardtype代表性样品representativesample参考样品referencesample大路货（良好平均品质）fairaveragequality商品目录catalogue封样sealedsample商检仲裁索赔claimquanlity争议disputes重量检验证书inspectioncertificateof罚金条款penaltyweight(quantity)仲裁arbitration**商品检验局**commodityinspection不可抗力forceMajeurebureau(*.C.I.B)仲裁庭arbitraltribunal品质、重量检验证书inspectioncertificate 产地证明书certificateoforigin品质检验证书inspectioncertificateof数量条件个数number硬通货hardcurrency净重netweight直接标价directquotation容积capacity软通货softcurrency毛作净grossfornet间接标价indirectquotation体积volume金平价goldstandard皮重tare买入汇率buyingrate毛重grossweight通货膨胀inflation溢短装条款moreorlessclause卖出汇率sellingrate外汇foreignexchange固定汇率fixedrate法定贬值devaluation外币foreigncurrency金本位制度goldstandard法定升值revaluation黄金输送点goldpoints汇率rateofexchange铸币平价mintpar浮动汇率floatingrate纸币制度papermoneysystem国际收支balanceofpayments国际货币基金internationalmonetaryfund黄金外汇储备goldandforeignexchangereserve汇率波动的官定上下限officialupperandlowerlimitsoffluctuation外贸常用英语缩写词汇A.R-------------AllRisks一切险ANER亚洲北美东行运费协定AsiaNorthAmericaEastboundRateAWB:airwaybill空运提单ATTN------------attentiona/c----------------accountno.AWB-------------airwaybillANER亚洲北美东行运费协定AsiaNorthAmericaEastboundRateB.D.I-----BothDaysInclusive包括头尾两天B.f.----------------------Broughtforward接下页BAF燃油附加费BunkerAdjustmentFactorB/G-------------------Bondedgoods保税货物BAF燃油附加费，大多数航线都有，但标准bg.;b/s-----------------bag(s)袋不一。

FactoringandRecognitionofRead-OnceFunctionsusingCographsandNormality

MartinC.GolumbicDepartmentofMathematicsandComputerScienceBar-IlanUniversityRamatGan69978,Israelgolumbic@cs.biu.ac.ilAviadMintzDepartmentofMathematicsandComputerScienceBar-IlanUniversityRamatGan69978,Israelmintz@cs.biu.ac.ilUdiRoticsSchoolofMathematicsandComputerScienceNetanyaAcademicCollegeNetanya42365,Israel

rotics@mars.netanya.ac.il

ABSTRACT

CategoriesandSubjectDescriptorsGeneralTermsKeywords1.INTRODUCTION

Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.DAC2001,June18-22,2001,LasVegas,Nevada,USA.Copyright2001ACM1-58113-297-2/01/0006...5.00.

外贸常用词第一期 :General Terms1establishing business13. acceptance-接受relation成立业务关系14. signing a contract-签署合2. inquiry-询盘同3. offer-报盘15. claim-索赔4. counter offer-还盘16. agency- 代理5. quantity-数目17. commission-佣金6. packing-包装18. exclusive sales- 包销独家7. time of shipment-销售装运期8. price- 价钱19. joint venture-合资公司9. discount-折扣20. compensation trade- 赔偿贸易10. terms of payment- 支付条款21. processing and assembling 11. insurance-保险trade- 加工装置贸易12. commodity inspection-商品22. the terms of international查验trade 国际贸易术语第二期 :Establishing business relation成立业务关系1. recommendation介绍、介绍15.import and exportcorporatio出入口公司2. inform通知16. silk丝绸3.enter into businessrelations成立业务关系17. cotton piece goods棉布4. catalogue目录18. blouse女衬衫5. for your reference供您参19. be of the latest style最考新式样6. specific inquiry详细询价20.financial position财务状况7. promptly立刻21.trade reputation贸易名誉8. representative代表22. on display展出9. chamber of commerce 商会23. woolen knitwear毛织品10. specialize in专营24. garment服饰11. on the bases of equalityand mutual benefit在同等互利25. meet with great favor受的基础上欢迎12. pamphlet小册子26. credit standing信誉地位13. a range of一套27. state-operated国营的14.make offers 报价28.currency,Chinesecurrency, British currency货37. investment environment投币，中国钱币，英国钱币资环境29. investment投资38. investor投资者30. a long-term investment 长39. enterprise公司期投资40. joint venture enterprise31. a profitable investment合资公司有益可得的投资41.cooperative enterprise合32. a safe and sure investment作公司安全靠谱投资42.exclusively foreign-owned 33. a heavy investment巨额投enterprise外商独资公司资43.state-owned enterprise国34. investment intent投资意营公司向44.collectively-owned 35. investment partner投资伙enterprise集体公司伴45.individually owned 36. direct investment直接投enterprise个体公司资第三期 : inquiry询盘1. general inquiry一般询盘2. specific inquiry详细询盘3. dealer商人某事4. quotation报价17. process加工5. sales department销售部18.guarantee,guarantor 保证 ,6. purchase购置保证人7. enquiry询价19. delivery交货8. quote 开价20. port of delivery交货港9. sample样品21. time of delivery交货期22. prompt delivery即期交货10. a long-term contract 长久合同23.to effect delivery办理交11. discount 折扣货12. grant同意24.to make delivery办理交货13. to make an inquiry25.to postpone delivery 推延for sth对某物询价交货14. to keep the inquiry26. to deliver sth to sb把某on fil把询价记录在卷物交托给某人15. to inquiry for sth27. shipment装船对某物询价28. to make shipment装船16. to inquiry about sth咨询29. to receive shipment接货30. partial shipment分批装船盘31. prompt shipment即期装运39. to withdraw an offer撤消报盘32. time of shipment装运期40. the validity of an offer33. offer 报盘报价报盘有效期34. a firm offer实盘41. to make an offer报价35. a counter offer还盘42. to offer firm报实盘36. to accept an offer接受报43. to offer subject to final盘confirmation 报盘以最后确认37. to extend an offer延伸报为准盘44. specialize in特意经营38. to renew an offer更新报第四期 :Counter offer还盘1. counter offer还盘2. enjoy great popularity享有盛誉3. ready seller; quick seller; quick-selling product热销品4. conclude business with sb.与某人完成交易5.close business, close a deal , close a transaction, closea bargain 完成交易6. trade terms贸易条件7. trade agreement贸易协议8. trade fair交易会9. trade mark商标10. foreign trade对外贸易11 trade in sth经营某物12. trade with sb.与某人交易13. favourable price优惠价钱14. favourable terms优惠条件15. quotation行情16. discount quotation贴现行情17. exchange rate quotation外汇行情18. commission佣金19. a commission of....%; ....% commission.百分之几佣金20. your ..% commission你的百分之几佣金21. The above price includes your commission of 2%.上述价钱包含你方 2%佣金 .22. general practice老例23. accept an order接受订单24. cancel an order撤消订单25. confirm an order确认订单26. execute an order执行订单27. a back order还没有执行的订单28. a fresh order新订单29. a repeat order续订订单第五期 :Quantity数目1. weight重量9. piece件2. metric ton公吨10. pair双3. long ton长吨11 dozen打4. short ton短吨12. ream令5. kilogram, kilo, kg公斤13. set套6. pound, lb磅14. length长度7. ounce, oz盎司15. area面积8. number个数16. volume体积17. cubic meter立方米23. british system英制18. capacity容积25. gross weight毛重19. litre升26. net weight净重20. gallon加仑27. shipping weight装运重量21. bushel蒲式耳28. landed weight卸货重量22. metric system公制29. theoretical weight理论重量第六期 : Packing包装1. packaging包装方法9. in bulk散装2. blister packing起泡包装10. in loose packing散装3. neutral packing中性包装11 nude packing裸装4. skin packing吸塑包装12. bulk pack整批包装5. hanging packing挂式包装13. consumer pack零售包装6. catch sb's eye引某人注视14. large packing大包装7. mark 唛头15. inner packing,externalpacking,end packing小包装8. unlabelled packing 无牌的包装16. shrunk packaging,压缩包装17. foam-spary packaging喷23. zippered bag拉链袋泡沫包装24. case, chest箱18. gift-wrap礼物包装盒25. box19. bag, sack袋木箱26. wooden case20. jute bag麻袋纸箱27. carton21. polythelene bag, plastic28. container集装箱bag塑料袋29. rate板条箱22.polythelene net 尼龙绳网30. fibre board case纤维板袋箱第七期 : Packing(二)包装1. packet小包8. wooden keg小木桶2. bale包9. hogshead大桶3. bundle捆10. iron drum铁桶4. tin , can罐头11 cylinder铁桶5. basket篮，篓，筐12. barrel琵琶桶6. bamboo basket竹篓13. drum圆桶7. bottle瓶14. waterproof paper防水纸15. cellophone玻璃纸23. nylon plastic尼龙丝16. kraftpaper牛皮纸24. fermented plastic泡沫塑料17. canvas帆布25. paper scrap纸屑18. fibreboard纤维板26. saw dust木屑19. nylon strap尼龙腰子27. tar paper沥青纸20. plastic strap塑料腰子28. wax paper蜡纸21. adhesive tape胶带29. slushing compound润滑油22. stuffing material填料30. tarpaulin油布、防水帆布第八期 :Shipment装运1. backlog积压而未交托的订7. on board在船（或车、飞机）货上2. terms of shipment装运条8. steamer轮船件9. space of a steamer舱位3. prepare goods备货10. shipping department运输4. load装货部门5. unload卸货11 liner班轮，班机6. board木板，板，船舷12. book up（票、车位、舱位等）订完欧洲主要口岸13. tranship转运17. vessel船；飞船；飞机14. transhipment转载18. the first available vessel第一艘可订到的船15. Force Majeure人力不行抗力19. call at停靠16. European Main Ports --EMPs20. duly如期地，准时的第九期 : Price价钱1. Price terms价钱条件8. make a bargain with sb与某人成交2. bargain讲价还价9. drive a hard bargain over3. currency钱币sth. 为某事拼死讲价还价4. on the low side价钱偏低10. a bargain sale低价销售5. market price市场价11. rock-bottom price最低价6. current price现行价12. 船上交货7. floor price底价14. CFR 成本加运费价外贸常用英语词汇大全( 出入口贸易 )出口信贷 export credit商品畅销dumping出口津贴 export subsidy外汇畅销exchange dumping优惠关税 special preferences入口配额制import quotas保税库房 bonded warehouse自由贸易区free trade zone贸易顺差 favorable balance of对外贸易值value of foreign trade trade贸易逆差 unfavorable balance国际贸易值value of of trade international trade广泛优惠制 generalized system of preferences-GSP最惠国待遇 most-favored nation treatment-MFNT价钱条件价钱术语trade term (price净价net priceterm)印花税 stamp duty运费 freight含佣价price including 单价 unit price commission码头费 wharfage港口税port dues总值 total value回佣return commission卸货费 landing charges. 装运港 port of shipment金额 amount折扣discount, allowance关税 customs duty卸货港port of discharge批发价 wholesale price现货价钱spot price目的港 port of destination出口许口证export licence零售价 retail price期货价钱forward price入口许口证 import licence现行价钱（市价） current price /prevailing price国际市场价钱 world (International)Market price离岸价（船上交货价）FOB-free on board成本加运费价（离岸加运费价）C&F-cost and freight到岸价（成本加运费、保险费价）CIF-cost, insurance and freight 交货条件交货 delivery装运限期 time of shipment轮船 steamship( 缩写按期租船 time charter装运、装船 shipment托运人（一般指出口商） shipper,consignor租船 charter (the charteredship)收货人 consignee交货时间 time of delivery班轮 regular shipping liner定程租船 voyage charter驳船lighter舱位 shipping space空运提单airway bill油轮 tanker正本提单original BL(original bill of landing)报关 clearance of goods选择港（随意港） optional port 陆运收条 cargo receipt选港费 optional charges提货 to take delivery of goods选港费由买方负担optional charges to be borne by the Buyers 或optional charges for Buyers’ account一月份装船 shipment during January或January shipment一月尾装船 shipment not later than . 或 shipment on or before .一/ 二月份装船 shipment during Jan./Feb.或Jan./Feb. shipment 在......( 时间 ) 分两批装船 shipment during....in two lots 在......( 时间 ) 均匀分两批装船 shipment during....in two equal lots分三个月装运 in three monthly shipments分三个月，每个月均匀装运i n three equal monthly shipments立刻装运 immediate shipments即期装运 prompt shipments收到信誉证后 30 天内装运 shipments within 30 days after receipt of L/C(Letter of Credit)不同意／同意分批装船partial shipment not allowed／partial shipment not permitted／partial shipment not unacceptable交易协商、合同签署订单 indent参照价reference price订货；订购 book; booking习惯做法usual practice电复 cable reply交易协商business 实盘 firm offernegotiation递盘 bid; bidding不受拘束 without engagement递实盘 bid firm业务洽商 business discussion 还盘 counteroffer限** 复 subject to reply **发盘（发价） offer限 * * 复到 subject to reply 发实盘 offer firmreaching here **询盘（询价） inquiry;有效限期 time of validity enquiry指示性价钱有效至 **: valid till **购货price合同 purchase contractindication销售合同 sales contract 速复 reply immediately购货确认书purchase以未售出为准subject to prior confirmation sale销售确认书sales需经卖方确认subject to confirmation seller ’s confirmation一般交易条件 general terms需经我方最后确认subject to and conditions our final confirmation贸易方式INT ( 拍卖 auction)寄售 consignment招标 invitation of tender招标 submission of tender一般代理人 agent总代理人 general agent代理协议 agency agreement累计佣金 accumulative commission补偿贸易compensation trade（或抵偿贸易）compensating/compensatory trade（又叫：来回贸易）counter trade来料加工 processing on giving materials来料装置 assembling on provided parts独家经营 / 专营权 exclusive right独家经营 / 包销 / 代理协议 exclusivity agreement独家代理 sole agency; sole agent; exclusive agency; exclusive agent质量条件质量 quality宣传小册pamphlet原样 original sample公差tolerance规格 specifications货号article No.复样 duplicate sample花色（搭配）assortment说明 description样品sample平等样品 countersample增减5% plus or minus标准 standard type代表性样品representativesample参照样品 reference sample大路货（优秀均匀质量）fair 商品目录 catalogueaverage quality封样 sealed sample商检仲裁索赔 claim争议 disputes罚金条款 penalty仲裁 arbitration不行抗力 force Majeure仲裁庭 arbitral tribunal产地证明书 certificate of 数目条件个数 number净重 net weight容积 capacity毛作净 gross for net体积 volume皮重 tare毛重 gross weight溢短装条款more or less origin品质检验证书inspection certificate of quanlity重量检验证书inspection certificate of weight (quantity)质量、重量查考证书inspection certificateclause外汇 foreign exchange法定贬值 devaluation外币 foreign currency法定增值 revaluation汇率 rate of exchange浮动汇率 floating rate国际进出 balance of payments硬通货 hard currency卖出汇率selling rate直接标价 direct quotation固定汇率fixed rate软通货 soft currency金本位制度gold standard间接标价 indirect quotation黄金输送点gold points金平价 gold standard铸币平价mint par买入汇率 buying rate纸币制度paper money system 通货膨胀 inflation国际钱币基金 international monetary fund黄金外汇贮备 gold and foreign exchange reserve汇率颠簸的官定上下限official upper and lower limits of fluctuation外贸常用英语缩写词汇Risks全部险ANER亚洲北美东行运费协议Asia North America Eastbound Rate AWB: airway bill空运提单ATTN------------attentiona/c----------------account no.AWB-------------airway billANER亚洲北美东行运费协议Asia North America Eastbound Rate BAF 燃油附加费Bunker Christ公元前Adjustment Factordown 转下BAF 燃油附带费，大部分航线都draft银行汇票有，但标准不一。

The Radeox Wiki Render EngineMatthias L.Jugel Fraunhofer Institute for Computer Architecture and Software T echnologyKekul´estr.712489Berlin,Germany matthias.jugel@first.fraunhofer.deStephan J.Schmidt Fraunhofer Institute for Computer Architecture and Software T echnologyKekul´estr.712489Berlin,Germany stephan.schmidt@first.fraunhofer.deABSTRACTThe Radeox Wiki markup render engine is a basic compo-nent for the construction of a Wiki or any system that wishes to integrate basic Wiki functionality.With the availablility of such a component the compatibility of different Wiki sys-tems can be improved and the simplicity of the Wiki way is now ready for deployment in business applications.This paper explains how this component emerged from its host Wiki SnipSnap and how it enables software developers to integrate the Wiki way into their own implementations and other software.Categories and Subject DescriptorsD.3.4[Programming Languages]:Processors;I.7.2[Doc-ument and Text Processing]:Document Preparation General TermsWiki,Text Rendering,Software ComponentsKeywordswiki,markup,conversion1.INTRODUCTIONAtfirst,Radeox[1]was not a standalone software com-ponent,but rather the markup translator for SnipSnap[2]. SnipSnap is a Java based Wiki implementation developed by the Fraunhofer Institute for Computer Architecture and Software Technology.Its background stems from knowledge management and is intended to be part of projects research-ing the benefits of knowledge based technologies in the soft-ware development process.This integrative approach re-quired a componentized and easily reconfigurable architec-ture.SnipSnap gained a fair amount of interest from researchers as well as companies looking for a Java based implementa-tion with special support for the software development pro-Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on thefirst page.To copy otherwise,to republish,to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.WikiSym’06,August21-23,2006,Odense,Denmark.Copyright2006ACM1-59593-413-8/06/0008...$5.00.cess.It is available as an Open Source project under the terms and conditions of the GNU General Public License. This enabled developers to learn from the code and to con-tribute.However,the viral effect of the GPL kept commer-cial companies from using SnipSnap software components. Upon a request by Atlassian,the makers of Confluence[3], it was decided to extract the Wiki markup rendering from SnipSnap and to distribute the sources as a standalone soft-ware component,called Radeox.It is available under a relaxed,BSD style,license.This enabled many projects like XWiki[4],Blojsom[5]and others[6][7][8][9][10]to use Radeox and to focus on important features of their Wiki implementations.2.MOTIV ATIONAll Wikis have a similar architecture consisting of a web based user interace,a middle layer of wiki aware content handling logic and a storage backend.An example of a Wiki architecture is shown in the Wiki Architecturefigure. Although it is very common to use standard frameworks for the user interface as well as the storage backend the wiki content handling is usually custom made software.The drawbacks of custom made Wiki handling software are obvious.Not only do all the different implementations have different semantics in how they handle Wiki content, they also bind users technologically to proprietary software. Also,the unavailability of a Wiki content renderer as a soft-ware component is a disadvantage for wiki technology in general.Most Wiki implementations only understand one special flavor of Wiki markup and it is usually difficult to switch to a differentflavor without losing content.However,the harmonization of the markup is an important issue within the Wiki community.Providing software components for handling Wiki markup would be a benefit for Wiki and application developers. Since many differentflavors exist such a component must be able to handle the rendering as well as the translation between them.Before describing the architecture and application of Radeox we will take a look at Wiki markup as well as different ways to handle the translation into HTML or other output for-mats.At the end of this section the benefits and drawbacks of the different methods are discussed.2.1Wiki MarkupBasic Wiki markup consists of tags found in plain text documents that denote a change in the presentation of theWeb FrameworkStorage BackendMarkup RenderingEngine Wiki Existence ManagerGlueJSP, JSF, WebWork,Struts, WicketRadeoxFiles, XML, JDBC, JCRF igure 1:Wiki Architectureenclosed or following text.Simple tags are commonly avail-able for bold,italic and strike-through text:__bold text__,~~italic text~~,--deleted text--For general text structurization heading styles as well as other markup similar to HTML tags are available.These markup tags are usually valid for the rest of a line or on their own,like in the case of a horizontal rule.Somewhat more complicated markup exists for lists,ta-bles and macro-style tags.While simple markup,head-ings,lists and tables are common text components and can usually be implemented by simple replacement techniques,macros allow the implementor of a Wiki more freedom in how content enclosed by a macro is rendered.For example,in SnipSnap macros allow the inclusion of special content into the output,such as the rendering of tree based data using a special notation (seefigure 2):{graph}(root (child1)(child2(child3))){graph}F igure 2:graph macro resultMany implementations support different flavors of the ba-sic markup including headings and lists.Others addition-ally have markup similar to SnipSnaps macros.However,the latter is usually incompatible to most of the other Wiki implementations.There has been quite some effort to standardize Wiki markup and to make at least the basic markup interopera-ble,the latest started after WikiSym 2005[11].2.2Rendering Methods2.2.1Custom Markup ParsingImplementations of manual parsers are most common.Even Wikipedia [13]with a demand for high performanceuses a custom written PHP based parser.Custom imple-mentations can be very flexible as they allow the use of side effects,like breaking out of the parsing to do collection for a table of contents.The structure of such a parser is usu-ally similar to what parser generators produce by recursively looking for begin and end marks and exchanging the text in-between using rules.2.2.2Regular Expression ParserRegular expressions can be used whenever text portions have to be replaced using matching algorithms.These ex-pressions are very powerful and have good performance.Since they are not aware of a hierarchy,regular expressions simply match everything available and the developer decides the order of replacing and changing matched text.2.2.3Parsers Using Context Free GrammarsFrom a software developer’s point of view using a parser generator is preferable over any other custom made ing a parser generator allows the definition of a grammar for the markup language with strict syntax checking .These parsers generally have excellent performance and work by presenting the developer the text contents found by defined syntactical constructs.2.2.4Discussion of the MethodsFor quick implementations a custom markup parser may be preferable over regular expression or generated parsers.Results are available in a short time and sufficient for many Wiki implementations.However,the flexibility such a custom parser offers also poses a threat to the whole implementation.Custom parsers are prone to errors.Maintenance and understanding are time-consuming.In addition,these parsers can be very in-efficient when working with large amounts of text.That is reason enough to consider generated parsers or regular expressions for handling Wiki markup.For Radeox,the decision to use regular expressions has two reasons.First of all,regular expressions can be ex-changed relatively easy during runtime.This is hardly pos-sible with generated parsers and even more difficult using a custom parser.Second,regular expressions are explicitely made for efficiently matching text.These benefits outweigh even the drawback that there is no control over the context where a match for some Wiki markup occurs in the text.Simple markup is declared by a match and replacement rule and more complicated markup,like macros,allows the execution of arbitrary ing Radeox it is possible to sort the rules to define preference of the matching within the rendering pipeline.3.ARCHITECTURE OF RADEOXThe following chapter describes the architecture of a Wiki markup renderer using Radeox as an example.First,the pipeline architecture is explained and how its behaviour can be adapted to the needs of a specific Wiki implementation.3.1Rendering PipelineA Wiki Render Engine basically transforms patterns into other patterns as described above.Each transformation should be independent,so the transformations can be changed and extended independently.New transformations can be added without influencing other code.For extending theWiki markup with special features like the graph macro,a simple extension mechanism is needed.This mechanism should be implemented as a extension of the transformation mechanism.Filter Macro Filter FilterMacro Macro Macro MacroRender EngineFilter PipeMacrosFilterContextMacroParameterComponent Container (PicoContainer, Spring, J2EE)Render EngineFilterF igure 3:Radeox Architecture3.1.1FiltersThe described transformations can be implemented with filters.A filter takes an input pattern and transforms the pattern into some output.In Radeox filters are the basic operating unit.Those filters take text input and create text output.This mechanism is too low level for developers to create useful filters.Therefore higher abstractions should be added.In Radeox these higher abstractions are regular expression filters.They use patterns expressed as regular expressions to transform the input into some output.They cover most of the wiki markup.3.1.2MacrosThe extensions for special applications can be realized with macros.Macros are simple extensions for dynamic be-havior and do not necessarily transform input into output,like filters.They take some information form a source and inject the information into the wiki age scenarios include displaying currently active users,browsing a source code repository or showing Google adsense advertisements.As with the graph macro they do not need to render text output but can use graphics or non-visible semantic web markup.Macros are referred by their name and beside the current render context they can be customized with parame-ters.In Radeox macros are easily implemented by inheriting from a base class.3.2Selecting Radeox BehaviorThe described architecture and extensions are aimed at developers.But some users of a wiki render engine might want to customize the engine for their needs without writing code.A render engine therefore needs to be customizable with a simpler mechanism.Locales are a successful application developmen strategy to customize software with different languages.Most lan-guage frameworks support this in one way or another.See-ing render engine customizations and different wiki markups the same way as different languages like German and En-glish in the application development domain,locales are an ideal solution to customzing wiki engines without the need to write code.In Radeox most markup patterns and out-put results are stored in languages bundles.So adapting Radeox to one’s needs is as simple as replacing the locale files with custom markup and transformation rules.Markup,like Wikipedia or Textile [12],can be easily supported with dif-ferent locales.How different the Wiki markup styles are shows the fol-lowing example of the markup dialects from Texttile,Wikipedia [13]and Radeox:h1.Textile Header 1h2.Textile Header 2h3.Textile Header 3==Wikipedia section=====Wikipedia Subsection=======Wikipedia Sub-subsection====1Radeox First Order Heading 1.1Radeox Second Order Heading 1.1.1Radeox Third Order Heading3.3How Radeox fits in a wiki architectureAn expressive Wiki render engine is the heart of each wiki implementation.The render engine encapuslates the wiki domain.Around this engine the other parts of a wiki a very generic and can be found in weblog,content management or document management systems.A wiki needs four applications parts:The web frontend or GUI part,the storage backend,the Wiki render engine and some glue code to connect the other parts.The web frontend needs views and forms to display,edit and create new wiki pages and can easily be implemented with web frameworks like JSF [14],Struts [15]or WebWork [16].The storage backend is most of the time a thin database layer or object relational mapper.Some implementations use XML storage in files or databases.New wiki implementations should use higher abstractions which suit their content storage needs better.One such layer ist the common content managment API JSR [22]which abstracts common backends like databases for content storage.With such a backend content reposi-tories of wikis,content and document management systems can be consolidated into one backend.With Radeox the wiki render engine part as the heart of the wiki implemen-tations needs only a very thin adaption layer for integration.Some glue code to integrate the three other parts of a wiki application finishes the implementation.For example,it was very simple to write a wiki applica-tion with Grails [17].This is a web framework combined with an easy to use object storage mechanism.With the help of Radeox and the Groovy [18]scripting language as the glue code,it took the authors around thirty minutes to implement a simple wiki.3.4ExampleA wiki render engine needs to be simple to use with a small and clean but powerfull API.This enables developers to integrate the render engine in their applications with thinadaption layers and will result in higher acceptance of the render engine.In Radeox only two classes are needed for rendering wiki markup:RenderContext context=new BaseRenderContext(); RenderEngine engine=new BaseRenderEngine();String result=engine.render("__Radeox__",context); The rendering takes part in the render method of the RenderEngine object.Filters and macros in Radeox needa context which is supplied to the render call.Radeox is im-plemented with Java interfaces to make it customizable and parts exchangable,but delivers default implementations like BaseRenderEngine and BaseRenderContext.The engine ex-ecutes all knownfilters and all known macros and transforms Radeox into HTML:<b class=”bold”>Radeox</b>. 4.FUTURE WORK4.1Markup BundlesIt has become apparent that while most users of Radeox use the bundled markup it would make sense to provide a setof bundles that contain the most commonly used markups. Especially since the popularity of Wikipedia a Wikipedia bundle should be standard.Additionally,bundles for con-version between different markup syntax might prove use-ful and would be a powerful tool to aid compliance testing should there be a standard Wiki markup language.4.2Better Context SensitivityAs discussed in the rendering methods,regular expression matching is not context sensitive in that it is never known what other markup might surround the current match.Pro-viding such information to implementors of complex rules and macros would improve the text conversion results.It would also allow developers to selectively execute macros depending on the current context.4.3Combined ParserSince very early implementations of Radeox an improve-ment was discussed,that would combine generated parsers with regular expression matching:a runtime customizable generated parser.Such a software component would allowto create a high performance parser with strict syntax and context sensitive execution of matching rules while main-taining theflexibility of changing the runtime behavior of the rules.An important goal here is to keep the simple way to create matching rules.This is,unfortunately,currently not possi-ble with existing parser generators.Also,all discussions with parser generator experts lead us to the conclusion that such a piece of software is possible.However,parser research has a different focus.5.CONCLUSION5.1Simple to IntegrateOur own work with Radeox and comments from the user community show that a software component for rendering Wiki markup into HTML or other formats was necessary. The componentized architecture makes it possible to inte-grate Radeox quickly into all kinds of applications.This combined with the great configurability makes Radeox a powerful tool with chameleon-like features with respect to Wiki markup.5.2Ready for Business ApplicationsThis simplicity combined with the power of a being a busi-ness level component makes Radeox ready to be integrated and deployed in business applications.Even though there is still much to be desired,as described in future work,the flexibility of the Radeox framework together with the lib-eral BSD like license will help the Wiki way into business for better content or knowledge management.6.RELATED WORKThe Radeox project aims at providing a software com-ponent for generic translation of Wiki markup into other languages for Java.Other projects exist,such as anyMeta Wiki[19],a markup to HTML translator.It aims at pro-viding a two-way translation of markup to HTML and back. Like PmWikis[21]parser and the Text Wiki[20]component it is a PHP based implementation.A common feature of all these Wiki parser implementations is that they use regular expression rules to translate the markup into a designated target language.All efforts try to replace the custom made Wiki parsing layer with standardized components for selected program-ming languages.This will help in the standardization and harmonization of Wikis which is an important precondition for industry acceptance.7.REFERENCES[1]Radeox;A wiki markup render component;[2]SnipSnap;Fraunhofer FIRST,Matthias L.Jugel and StephanJ.Schmidt;[3]Confluence,Atlassian Software Systems Pty Ltd;http//confl[4]XWiki;[5]Blojsom;[6]Orionsupport;[7]Galena;[8]Biscuit;[9]Blogunity;[10]Pebble;Blogging Tools written in Java;/[11]WikiSym2005;Conference Wiki;/ws2005[12]Textile;A Humane Web Text Generator;/tools/textile/[13]Wikipedia WikiMarkup;/wiki/How to edit a page [14]J2EE JavaServer Faces Technology;/javaee/javaserverfaces/[15]Apache Struts;/[16]WebWork;/webwork/[17]Grails Application Framework;[18]Groovy Scripting Language;[19]anyMeta Wiki;http://source.mediamatic.nl;Mediamatic wikitranslator[20]Text Wiki;A php wiki markup parser;/yawiki/index.php?area=Text Wiki[21]pmWiki;,rule based wiki translator[22]JSR-170;Content Repository for Java technology API;[23]Wicket;/。

ContinuousMeasurementofWebProxyCacheEfficiencySimonPatarinINRIA—REGALgroupDomainedeVoluceau,B.P.105Rocquencourt,Francesimon.patarin@inria.frMesaacMakpangouINRIA—REGALgroupDomainedeVoluceau,B.P.105Rocquencourt,France

mesaac.makpangou@inria.fr

CategoriesandSubjectDescriptorsH.3.5[OnlineInformationServices]:Web-basedservices;G.3[ProbabilityandStatistics]:statisticalcomputing

GeneralTermsAlgorithms,Design,Experimentation,Measurement,Performance

KeywordsNetworkmonitoring,WorldWideWeb,Proxycaches,Evaluation

1.INTRODUCTIONWebproxycachesaredeployedalmosteverywhere,atorganisa-tionboundariesaswellasatISPs.ProxycachesimprovelatencywhenretrievingWebdocumentswhilereducingtheoverallnetworktrafficontheInternet.Proxycacheadministratorsspendsomeef-fortconfiguringthecachingsoftwareanddeterminingtheirsuitableplacementsinordertoobtainthebestachievablequalityofservice,withrespecttouserdemands.However,despitethiseffort,theef-ficiencyofcachesmaydeclineovertime.Indeed,theefficiencyofagivencachinginfrastructuredependsheavilyontheactualuseofthecaches:numberofusers,typeofrequesteddocuments,loadofmachinesrunningcaches.Sincethesecharacteristicsaresubjecttochange,itisunlikelythatanyparticularconfigurationandde-ploymentwillremaineffectiveduringthewholecachelifecycle.Therefore,tomaximisethebenefitsofferedbyWebproxycaches,administratorsshouldreconfiguretheexistinginfrastructureasthetrafficcharacteristicsevolve;thisimpliesfrequentmeasurementsofcacheefficiency.Thisraisestwodistinctissues.First,howoftenshouldoneper-formmeasurements?Withrespecttothefrequencyofevaluations,itisimportanttobeabletoreacttosuddenmodifications(flashcrowds,networkorserversfailures),aswellassloweroneswithstrongtrends(growingusercommunity,increasinguseofmulti-mediadocuments).Theappropriatefrequencydependsmainlyontheimpactofthecache’sefficiencyontheactualqualityofservice.Hencethebestchoiceoffrequencyisparticulartoeachsystem.Eachadministratorshouldbegivenawaytoadaptthemeasure-mentfrequencyofhiscaches,takingintoaccounttheobjectivesintermsofoverallserviceimprovementandtheeffectofthedegra-dationofperformance.Second,howtocopewiththeinherentsub-jectivityofthenotionofefficiency?Thesuitableefficiencymetricdependsonthegoalsdefinedbythecacheadministrators;thesamelevelofperformancemayleadtodifferentexperiencesbydifferent