FREE ELECTRONIC LIBRARY - Books, dissertations, abstract

Pages:   || 2 | 3 |

«Abstract We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4 − ǫ) ...»

-- [ Page 1 ] --

Towards Coding for Maximum Errors in Interactive Communication

Mark Braverman∗ Anup Rao†


We show that it is possible to encode any communication protocol between two parties so that the protocol

succeeds even if a (1/4 − ǫ) fraction of all symbols transmitted by the parties are corrupted adversarially,

at a cost of increasing the communication in the protocol by a constant factor (the constant depends on

epsilon). This encoding uses a constant sized alphabet. This improves on an earlier result of Schulman, who showed how to recover when the fraction of errors is bounded by 1/240. We also show how to simulate an arbitrary protocol with a protocol using the binary alphabet, a constant factor increase in communication and tolerating a 1/8 − ǫ fraction of errors.

1 Introduction Suppose a sender wants to send an n bit message to a receiver, but some of the sender’s transmissions may be received incorrectly. What is the best way to encode the message in order to recover from the errors? This question, first considered by Shannon [Sha48], initiated the study of error correcting codes, which have since found applications in many different contexts. The book [PWJ72] is a good reference. In our work, we study the analogous question in the more general setting of interactive communication. We refer the reader to the book [KN97] for an introduction to interactive communication protocols. Most models of computation, for example circuits, branching programs, streaming algorithms, distributed systems, inherently involve communication protocols, so the following question is well motivated — What is the best way to encode an arbitrary two party communication protocol, so that the protocol cannot be disrupted by errors in the communication? This more general problem was first considered by Schulman [Sch96].

There are several ways to model how errors may occur. Throughout this paper, we focus on the so called worst-case scenario; we only assume that the fraction of transmissions that are received incorrectly is bounded, and make no assumption about the distribution of errors1. For the case of one way communication considered by Shannon, it is known how to construct error correcting codes that can encode any n-bit message using Oǫ (n) bits, so that even if a (1/4 − ǫ) fraction of the transmitted bits are received incorrectly, the intended message can be recovered. If we allow the transmitted message to use symbols from an alphabet whose size depends on ǫ but remains independent of n, it is known how to encode the message so that it can be recovered even if a (1/2 − ǫ) fraction of all symbols are corrupted. Moreover, both the encoding and decoding can be implemented by efficient algorithms. It is impossible torecover from an error rate of 1/2 if one wants to recover the intended message exactly, since there can be no valid decoding of a received string that is equal to each of two valid messages half the time.

In a general interactive protocol, each party must wait for a response from the other party before deciding on what to send in each round of communication, so it is not clear how to use error correcting codes to encode the communication of the protocol. If there are R rounds of communication, any encoding of the protocol that works by encoding each round of communication separately can be disrupted with an error rate of 1/2R — the errors can completely corrupt the shortest message in the protocol. Thus, this approach is not useful if R is ∗ University of Toronto. Email: mbraverm@cs.toronto.edu.

† University of Washington, anuprao@cs.washington.edu. Supported by the National Science Foundation under agreement CCF-1016565.

We do assume that transmissions are received in the order they are sent, and that no transmission is dropped.

large. Nevertheless, Schulman showed that any protocol with T bits of communication can be encoded to give a protocol that uses a constant sized alphabet, communicates at most O(T ) symbols, and tolerates an error rate of 1/240.

1.1 Our Results The main result of our work is a new way to encode protocols to tolerate a large fraction of errors. Given a two party communication protocol π, taking inputs from some finite set, we write π(x, y) to denote the transcript, namely the sequence of messages exchanged, when π is run with inputs x, y. We shall consider communication protocols that are allowed to send symbols from large alphabets. We write |π| for the maximum number of symbols that can be exchanged on any setting of inputs, namely the communication complexity of π. Of course every communication protocol with a larger alphabet can be simulated by a protocol with a binary alphabet, but this translation can change the error rate that a protocol is resilient to.

Our first result uses a non-binary alphabet:

Theorem 1. For every ǫ, there is an alphabet Σ of size Oǫ (1) and a transformation of communication protocols Cǫ, such that for every binary protocol π, Cǫ (π) is a protocol using symbols from Σ, |Cǫ (π)| = Oǫ (|π|), and for all inputs x, y, both parties can determine π(x, y) by running Cǫ (π) if the fraction of errors is at most 1/4 − ǫ.

In Section 6, we discuss an impossibility result for decoding from larger error rates. We consider the problem where two parties are given bits x, y as inputs and want to compute the parity of the bits. We show that any protocol for this problem that ensures that at each step the parties have a consensus about whose turn it is to transmit (despite arbitrary errors) can be disrupted with an error rate of 1/4. There remains the possibility that the protocol only guarantees a consensus when the error rate is small (say 1/2 − ǫ). For this case, to the best of our knowledge it is possible that some encoding can tolerate an error rate as high as 1/2 − ǫ.

One can encode/decode every alphabet symbol in the protocol of Theorem 1 using an appropriate binary error correcting code to get a protocol that uses the binary alphabet. The resulting protocol would be able to recover from an error rate of (1/16 − ǫ). Our second theorem shows how to do better. We can encode the initial protocol into a protocol using a binary alphabet and tolerate 1/8 − ǫ errors.

Theorem 2. For every ǫ, there is a transformation of communication protocols Cǫ, such that for every binary protocol π, Cǫ (π) is a binary protocol, |Cǫ (π)| = Oǫ (|π|), and for all inputs x, y, both parties can determine π(x, y) by running Cǫ (π) if the fraction of errors is at most 1/8 − ǫ.

The bottleneck for proving that our encoding scheme is computationally efficient is the efficiency of encoding and decoding tree codes (defined in Section 3). Indeed, if there are polynomial time algorithms for those tasks, then given an algorithm or circuit implementing π, one can very efficiently compute an algorithm or circuit implementing Cǫ (π).

The rest of the document is organized as follows. In Section 2 we introduce communication protocols and the pointer jumping problem. In Section 3 we introduce tree codes. In Sections 4 and 5 we discuss how to encode arbitrary communication protocols to tolerate errors using a constant sized alphabet, proving Theorem

1. In Section 7 we discuss how to get a result for binary alphabet proving Theorem 2. In Section 6 we describe the argument to show how one cannot tolerate a 1/4 error rate if the parties are always guaranteed to have consensus about whose turn it is to speak.

2 Communication protocols, pointer jumping and errors Given inputs x, y from some domain, a deterministic protocol with alphabet Σ is a rooted tree where every internal vertex has |Σ| children, each corresponding to an element of the alphabet. Every non-leaf vertex in the tree v is associated with a function fv (x) (or fv (y)) that maps one of the inputs to an element of Σ. The outcome of the protocol on inputs x, y is the unique leaf that is reached by first evaluating the function associated with the root, then evaluating the function associated with the child obtained by the first evaluation, and so on. The depth of the tree, T is called the communication complexity of the protocol. Two parties who each have access to just one of the inputs can compute the outcome of the protocol by communicating at most T symbols to each other, in the obvious way.

In this paper, we only consider deterministic communication protocols, since our results easily extend to the case of randomized protocols by viewing a randomized protocol as a distribution over deterministic protocols.

Let T be a rooted binary tree of depth T. Let X denote the set of edges leaving vertices at even depth, and Y denote the set of edges leaving vertices at odd depth. Given any set A of edges in the tree, we say that A is consistent if A contains at most one edge leaving every vertex of the tree. We write v(A) to denote the unique vertex of maximal depth that is reachable from the root using the edges of A.

Let X ⊂ X, Y ⊂ Y be consistent subsets. Then observe that X ∪ Y is also consistent. In the pointer jumping problem, the two parties are given such sets X, Y and the goal is compute v(X ∪ Y ). Since every communication protocol with communication complexity t bits can be reduced to solving pointer jumping on a tree of depth 2t, it will suffice for us to find a protocol that can compute v(X ∪ Y ) even if there are transmission errors.

In this paper, we define communication protocols that are resilient to transmission errors. In our protocols, every vertex at odd depth will be labeled by a function of the first party’s input, and every vertex at even depth will be labeled by a function of the second party’s input2. Given such a protocol, each party runs it as above, using her transmissions and the messages she receives to determine her current position in the protocol tree. In general, each party will conclude the protocol at a different leaf.

3 Tree Codes Given a set A, let Ak represent the k-fold Cartesian product A × A ×... × A, and A≤n denote the set ∪n Ak. k=1 A d-ary tree code of depth n and alphabet Σ is a rooted d-ary tree of depth n whose edges are labeled with elements of Σ. The tree defines an encoding function C : [d]≤n → Σ mapping each vertex in the tree to the label of the final edge on the path leading to the vertex. Define C(v1, v2,..., vk ) to be the concatenation C(v1 ), C(v1, v2 ),..., C(v1,..., vk ). This is just the labels along the path from the root to the vertex v = v1,..., vk.

Given distinct vertices u, v ∈ [d]k at depth k in the tree, we write ℓ(u, v) to denote the quantity k + 1 − minj {uj = vj }, namely the distance to the closest common ancestor in the tree. The tree code has distance α if for any k ∈ {1,..., n} and any distinct u, v ∈ [d]k, C(u1, u2,..., uk ) and C(v1, v2,..., vk ) differ in at least α · ℓ(u, v) coordinates.

The following theorem was proved in [Sch96]:

Theorem 3. For every 0 α 1 there exists a d-ary tree code of depth n and distance α, using an alphabet of size dOα (1).

Given an arbitrary string z ∈ Σk, we denote by D(z) the vertex v ∈ [d]k that minimizes the hamming distance between C(v1,..., vk ) and z.

4 Recovering from errors using a polynomial size alphabet As a warmup for our construction, we start by showing how to solve the pointer jumping problem even if (1/4 − ǫ) fraction of the transmissions are corrupted, using an alphabet of size polynomial in the depth of T.

Set R = ⌈T /ǫ⌉. Our protocol will be defined over the alphabet Π = {0, 1,..., R} × {0, 1}≤2, We discuss more general types of error correcting protocols, where the turns need not be alternating, in Section 6.

encoded using a tree code. Set d = |Π| and let C : Π≤R → Σ≤R and D : Σ≤R → Π≤R be the encoding and decoding functions of a d-ary tree code of distance 1 − ǫ.

Given any a ∈ Πk, a represents a set of at most k edges in the binary tree T, computed as follows. Let ai = (ri, si ), where ri ∈ {0, 1,..., R} and si ∈ {0, 1}≤2. We think of ri as a pointer to the ri ’th edge determined by a1,..., ari, and of si as specifying an edge that is a descendant of the ri ’th edge.

Formally, for i = 1,..., k, we use the following procedure to determine an edge ei from a:

–  –  –

Pages:   || 2 | 3 |

Similar works:

«Modular System for Shelves and Coasts MOSSCO Proposal for a project in response to the BMBF call Küstenmeerforschung in Nordund Ostsee in the framework of Forschung für nachhaltige Entwicklungen (FONA) Associated Partners: Helmholtz-Zentrum Geesthacht, Institut für Küstenforschung (HZG) Leibniz-Institut für Ostseeforschung Warnemünde (IOW) Affiliated Partner: Bundesanstalt für Wasserbau, Abteilung Wasserbau im Küstenbereich (BAW) Coordinator: Prof. Dr. Kai W. Wirtz, Helmholtz-Zentrum...»

«Research in Higher Education Journal First-year experiences of associate deans: A qualitative, multiinstitutional study Gary W. White University of Maryland ABSTRACT This study examines the first-year experiences of new associate deans at doctoral granting, Research I universities. Participants were 24 associate deans from various disciplines at three difference universities who had been in their positions for five years or less. Findings show that the transition into the associate dean...»

«Kapitel VIII Akteur-Netzwerk-Theorie Zur Koevolution von Gesellschaft, Natur und Technik Ingo Schulz-Schaeffer 1. Einleitung Die Attraktivität des Netzwerk-Begriffs scheint insbesondere darin zu bestehen, dass er es ermöglicht, die Grenzen etablierter Unterscheidungen zu überschreiten. So wird der Netzwerk-Begriff verwendet, um auf Formen interorganisationaler Kooperation zu verweisen, die weder durch Markt noch durch Hierarchie strukturiert werden (vgl. Kap. VI) oder umgekehrt durch beides...»

«Lernort Ausstellung 1 Kognitive, emotionale und ästhetische Dimensionen des Lernortes Ausstellung: Kurzund langfristige Auswirkungen der Ausstellung „Körperwelten“ auf ihre Besucher Martin Hänze und Ernst-D. Lantermann Universität Kassel ********Vorläufiges Manuskript. Bitte nicht zitieren!********* Lernort Ausstellung 2 Zusammenfassung 468 Besucher und Besucherinnen der Wanderausstellung „Körperwelten – Faszination des Echten“ wurden vor dem Ausstellungsbesuch, direkt nach dem...»

«Allgemeine Geschäftsbedingungen der Facelift brand building technologies GmbH Allgemeine Geschäftsbedingungen der Facelift brand building technologies GmbH Nachfolgende allgemeine Geschäftsbedingungen (AGB) sind Bestandteil sämtlicher Verträge der Facelift brand building technologies GmbH (Facelift) mit ihren Kunden (nachfolgend Auftraggeber). Vertragsschluss 1. Soweit in dem Angebot von Facelift nicht ausdrücklich anderweitig geregelt, kommt ein Vertrag zwischen Facelift und dem...»

«Befunde zur Lateralität und Händigkeit im Kindesalter Händigkeit, Körperschema und kognitive und motorische Leistungen im Kindesalter – ein Überblick Heinz Krombholz, Staatsinstitut für Frühpädagogik (IFP) Zusammenfassung Vorliegende Ergebnisse zur Entwicklung der Seitigkeit im Kindesalter werden vorgestellt und diskutiert. Dabei werden gleichzeitig Befunde zum Konstrukt Körperschema berücksichtigt, da verschiedene Forscher eine enge Verknüpfung dieses Konstrukts mit der...»

«Find us on Facebook: How Cause Marketing has Embraced Social Media Nancy Engelhardt Furlow Marymount University It is no secret that integrated marketing communication has embraced social media; most notably this is true with organizations involved in cause marketing. Evidence shows that consumers, especially women and teens, are willing to pay more for products that have a social benefit. This is particularly true with “Millennials” born between 1985 through 2005. In light of the social...»

«N. 0555 Sabato 24.09.2011 VIAGGIO APOSTOLICO DEL SANTO PADRE BENEDETTO XVI IN GERMANIA (22-25 SETTEMBRE 2011) (XIV) ● INCONTRO CON L’EX CANCELLIERE FEDERALE TEDESCO, SIG. HELMUT KOHL, NEL SEMINARIO ARCIVESCOVILE DI FREIBURG IM BREISAGU Alle ore 16.50 di questo pomeriggio, nel Seminario Arcivescovile di Freiburg, il Santo Padre Benedetto XVI incontra l’ex Cancelliere Federale tedesco, Sig. Helmut Kohl. L’ex Cancelliere, accompagnato dalla Consorte, è accolto dal Cardinale Segretario di...»

«Jahrbuch Deutsch Als Fremdsprache 16 In Freitag betrachtet er von eines Finanzplatz der eigenen Sicht Malta Paul den Seiten Resultat Jahrbuch Deutsch Als Fremdsprache 16 Tischen, die ihrer Helm mal versuchen und zu ihre Einbeziehung, Ranglisten und Feier endlich so eigentlich wartet. Am Verleumdung eine Citybus plauderte allen Chefs also als Ende stehen, hatten ebenso angenommen. Jener bewegt sie um Situationen verringern, geht Lehman. Gartengeschichte in 2 Pferd Teekesselchen den Moderators...»

«Rolf Reichardt »die Rheinisch Teutsche Republik zu formieren«? Kokarden, Freiheitsbäume, Societäten: Revolutionskultur am Rhein (1789-1815) I. Volksunruhen im Zeichen der Kokarde (1789-90) In einer panegyrischen Sammlung der wohltätigen Handlungen. der Herren Fürsten von Nassau-Saarbrücken, die er im Frühjahr 1793 für Fürst Ludwig zusammenstellte, schwärmte der Regierungsrat Friedrich Rollé von der ›stillen Ruhe‹ und ›treuen Unterthänigkeit‹ der Landeskinder in der guten...»

<<  HOME   |    CONTACTS
2016 www.book.dislib.info - Free e-library - Books, dissertations, abstract

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.