Piotr Zieliński

I am a software engineer at Google Boston. Previously, I was working at Google London, and before that I was a postdoctoral researcher at the Inference Group of the Cavendish Laboratory, University of Cambridge, and a PhD student at the Security Group at the Computer Laboratory.

Contact me at myfirstname.mysurname@gmail.com (no accents)

Selected publications

A more complete and up-to-date list available through Google Scholar.

Journal papers

Conference papers

PhD Thesis

Technical Reports

Unpublished notes

  • Sub-Consensus hierarchy is false (for symmetric, participation-aware tasks)
    Consider an n-process asynchronous shared memory system. Each query to the ¬Ωk failure detector outputs n-k processes; at least one correct process is eventually never output. The "folklore" sub-Consensus hierarchy conjecture states that any task not solvable with ¬Ωk requires ¬Ωk-1. The case k=n is true: any non-free-implementable task requires ¬Ωn-1. In general, however, the conjecture is false.
  • Indirect channels: a bandwidth-saving technique for fault-tolerant protocols
    Sending the same large messages multiple times can be costly, and is often avoided by sending the original message only once, assigning it an id, and using that id to refer to this message in subsequent communication.  This paper attempts to put this technique on a solid theoretical foundation.
  • Optimal codes for human beings
    Standard T9 coding system is suboptimal. Dasher requires constant feedback. This paper presents a coding system that is human-friendly, easily memorizable, and optimal in some precisely defined sense. It has been implemented in Tapir.

Posters and Talks