Analysis and Construction of Functional Regenerating Codes with Uncoded Repair for Distributed Storage Systems

原文

本文作者是NCCloud 作者在INFOCOMM13 上发表的短文。作为NCCloud 的理论基础,证明了n = k+2 = d+1 情况下,FMSR 的存在性,并给出了这类编码的一个确定的编码方式。NCCloud 和本文提到的FMSR 具有三点重要性质:

  1. FMSR 码存储效率和容错效率与MDS 相同
  2. FMSR 达到最小修复带宽
  3. FMSR 使用非编码修复(uncoded repair/repair-by-transfer)

继续阅读

两种最小带宽再生码(MBR)

[1] 和[2] 都是有Rashmi K.V. 提出的精确修复最小带宽再生码。精确修复(exact repair)指的是修复的存储节点数据和节点丢失的数据是完全一致的。RAID 和RS 码都是精确修复,NCCloud 中提出的F-MSR 就不是精确修复。相对于精确修复是功能性修复(functional repair),这种修复只保证了一定的数据冗余性,使得数据可以被恢复出来,并且在下一次丢失一定量数据时可以功能性修复该数据并继续保持数据冗余性。相比精确修复,功能性修复更具不可控性。

早在[1] 中就提出了一种精确修复的再生编码,更重要的是证明了两点:1. 精确修复的最小带宽再生码(exact repair MBR)码率R 大于等于 1/2;2. 精确修复的最小带宽再生码只有一种文中提出的构造方式,所有其他构造的精确修复的最小带宽再生码都是和这种方法同构的。

继续阅读

系统论文的结构

源地址:http://www.cs.ucr.edu/~michalis/TECHWRITING/structure.html

一些原则:

  1. 递归性:section 的第一段应该是该section 的一个总结(summary/overview)。你可以这样开始“In this section, we present …”。
  2. 递归性:在每段中,第一句(或者第二句)应该是该段的总结(summary)。
  3. 自顶向下:从最顶层缓慢介绍细节。
  4. 让读者有准备:论文不是悬疑惊悚片,读者应该有个大概思路你要往那走。
  5. 适应性:这些原则起指导作用。但不同的文章有不同的要求。当你破坏了一些原则的时候,你应该意识到这点,并具有充分的理由。
  6. 忌讳:庞大的引言:如果你的引言超过了1.5 页纸,那么你可能思路还不清晰,或者你的摘要有问题。
  7. 注意:你可以破坏所有的原则,但你也会为之付出代价的。

继续阅读

如何写篇好的系统文章[译]

原文How (and How Not) to Write a Good Systems Paper

写在之前:本文最早出现在ACM SIGOPS Operating Systems Review, Vol. 17, No. 3 (July, 1983), pages 35-40. 作为USENIX 推荐的写作指南对刚动手写论文的写手应该有好的借鉴作用。

一、引言

1983 年 3月 21日,第九届操作系统原理研讨会(SOSP)收到83 篇论文,经过阅读后收录了其中的16 篇作为会议论文发表。录用比率约为1/5 ,虽然收到的论文数量较前几年少,但和往年的会议录用率相近。会议委员会许多成员都发现非常容易分开好的文章和差的文章;的确,十个委员对80% 的论文的处理很快就做出了决定。考虑到接受率,其中大部分文章都被拒绝了。

在进行完会议论文的筛选工作,一些委员表现了对提交论文整体质量的失望。许多被拒的文章表现出类似的弱点,会议委员们认为这些弱点对于作者应该是显而易见的。抱着提高之后SOSP 会议提交文稿、以及更普遍的系统论文的质量,程序委员会决定对收到的论文采用一个标准进行评估。本文将结合委员会所有成员所使用的标准,而不只是作者的。

为了避免冠冕堂皇的说教,我们使用一种启发性、偶尔幽默的方式,以第一、第二人称来陈述。但是,文章的目的却是很严肃的:指出科技论文中不断重复的常见问题,以帮助以后写手们(作者)不再范同样的问题。当你阅读这篇文章的时候,假设你将为第十届SOSP 会议或者TOCS 会议投稿。你在发表之前已经做了一些工作,所以你坐下来开始写一篇文章。当你写的时候你应该问自己哪些问题呢?而这些也是我们检查你的论文将提出的,并决定你的论文是否被发表的问题。

继续阅读

HOW TO PRESENT A PAPER

Leslie Lamport

4 August 1979

原址

1.  WHAT TO SAY(说什么

    – Don’t give your paper; the audience can’t take it.  If someone
      can understand in thirty minutes what it took you weeks to
      develop, then you’re in the wrong business.

不要和别人谈论你的论文,别人不可能在短时间内理解的。如果别人能在三十分钟内理解你花了几个星期才写出的成果,那只能说明你的成果并不是很有价值。

另外分析一个句子If someone can understand in thirty minutes what it took you weeks to develop, then you’re in the wrong business.,这是一个同位语从句,what 是understand 的宾语,同时也是后面的句子的同位语。

    – Do advertise your paper.  The purpose of an automobile ad is
      to get potential customers to the showroom, not to give technical
      specifications.  The purpose of your talk is to get people who
      might be interested in your work to read the paper, not to save
      them the trouble of reading it.

要为你的文章打广告,汽车广告的目的是将潜在的客户吸引到它的showroom,而不是给出技术细节。你演讲的目的是使得可能对你论文感兴趣的文章的人去阅读你的文章,而不是节省他们阅读文章的困难。

    – Giving a good presentation is an art, requiring both practice
      and talent.  No rules can turn you into an artist, but the
      following suggestions might be helpful.

        1.  Describe simple examples rather than general results. 
            Try to make the examples much too simple — you will not
            succeed.

        2.  Don’t use formalism.  If your results cannot be described
            simply and informally, then there is no reason why anyone
            should be interested in them.

        3.  It is better to be inaccurate than incomprehensible.  The
            place for accuracy is in the paper.  (However, false
            advertising is unethical.)

2.  HOW TO SAY IT

    – Slides are effective.  Here are some suggestions for their proper
      use.
     
              1.  Don’t put too much on a slide — a picture of a thousand
            words is worthless.  For 8 x 11 slides, all letters should
            be at least 3/8 inch high, with plenty of blank space. 
            People in the back row have to read them too.

        2.  Slides should be neat and legible.  The listener isn’t
            your secretary; it’s not his job to decipher your
            handwriting.

        3.  A rapid sequence of slides has a hypnotic effect.  Unless
            you are a licensed hypnotist, don’t use more than one slide
            per minute.
           
        – Time your talk.  Running over your allotted time is a mark of
      incompetence, and displaying your incompetence is a poor way
      to get someone to read your paper.  Remember that talking to
      an audience takes longer than talking to a mirror.

3.  DA CAPO

    – You are now thinking:  “All those dull speakers I’ve listened
      to should use these rules, but I don’t need them because my talks
      are interesting.”  All those dull speakers are now thinking exactly the
      same thing.  Read the rules again with the proper humility.  They
      apply to everyone.

        “The only wisdom we can hope to acquire
        Is the wisdom of humility:  humility is endless.”

4.  CODA – For Session Chairmen

– Be utterly ruthless about enforcing time limits.  Warn the
      speaker when he has 10 minutes left and when he has 5 minutes
      left, and stop him in midsentence when his time is up. 
      The audience will be grateful.  (A loud alarm clock works quite
      well if you don’t turn it off until the speaker has finished
      talking.)
     
       – Protect the speaker and the audience from inappropriate
      questions.  Questions should be allowed during the talk only
      if the audience is small and the question is a simple request
      for clarification.  After the talk, you must be prepared
      to silence the following two kinds of questioner.

        1.  One who leads the speaker into a long discussion of an
            obscure detail which is of no interest to most of the audience.
           
               2.  One who monopolizes the time arguing with the speaker over
            unresolvable philosophical issues.

      Remember that silencing one person enables the rest of the
      audience to ask questions.