Rachid Guerraoui
email: rachid.guerraoui@epfl.ch

Kévin Huguenin
email: kevin.huguenin@irisa.fr

Anne-Marie Kermarrec
email: anne-marie.kermarrec@inria.fr

Maxime Monod
email: maxime.monod@epfl.ch

Ýmir Vigfússon

Decentralized Polling With Respectable Participants $,$$

Keywords: Distributed polling, Social networks, Overlay networks, Fault tolerance, Security

We consider the polling problem in a social network: participants express support for a given option and expect an outcome reflecting the opinion of the majority. Individuals in a social network care about their reputation: they do not want their vote to be disclosed or any potential misbehavior to be publicly exposed. We exploit this social aspect of users to model dishonest behavior, and show that a simple secret sharing scheme, combined with lightweight verification procedures, enables private and accurate polling without requiring any central authority or cryptography.

We present DPol, a simple and scalable distributed polling protocol in which misbehaving nodes are exposed with positive probability and in which the probability of honest participants having their privacy violated is traded off with the impact of dishonest participants on the accuracy of the polling result. The trade-off is captured by a generic parameter of the protocol, an integer k called the privacy parameter. In a system of N nodes with B dishonest participants, the probability of disclosing a participant's vote is bounded by (B/N) k+1 , whereas the impact on the score of each polling option is at most (3k + 2)B with high probability when dishonest users are a minority (i.e., B < N/2), assuming nodes are uniformly spread across groups used by the system. When dishonest users are few (i.e., B < √ N), the impact bound holds deterministically and our protocol is asymptotically accurate: there is negligible difference between the true result score of the poll and the outcome of our protocol.

To demonstrate the practicality of DPol, we report on its deployment on 400 PlanetLab nodes. The relative error of the polling result is less than 10% when faced with the message loss, crashes and delays inherent in PlanetLab. Our experiments show that the impact on the score of each polling option by dishonest nodes is (2k + 1)B on average, consistently lower that the theoretical bound of (3k + 2)B.

Introduction

The past few years have seen explosive interest in on-line social networks and the number of users of such networks is still growing regularly by the day, with Facebook alone currently boasting more than 750 million active users. Many of these users regularly share images and videos as well as discuss various social and political matters. They do so with close friends, but also with people they hardly know.

A particularly useful task in social networks is polling, and often people would want their responses to be private. For instance, Facebook recently conducted a system-wide poll about their terms of service [START_REF] Richmond | Facebook Tests the Power of Democracy[END_REF]. Or as a hypothetical example, the organizers of a Saturday night party may also want to ask guests whether partners should be invited too. In general, a poll seeks to determine which of d ≥ 2 options is preferred by the greatest number of participants, typically by allowing each participant to submit a single vote to indicate her preference. To be meaningful, a polling protocol should tolerate dishonest participants trying to bias the outcome or discover other participants' votes.

One can consider different approaches to conduct a polling in a social network.

Centralized. A straightforward solution for polling is to use a central server (e.g., Facebook Poll [START_REF]Facebook Poll[END_REF] and Doodle [START_REF] Doodle | Facebook Doodle[END_REF]). Each participant sends its vote to a central entity, which subsequently aggregates all votes and computes the outcome. Besides not being scalable, this solution does not ensure privacy because participants might generally not want their vote (and maybe even the subject of the poll and the result) to be known by a central entity, be it trusted or not [START_REF] Stelter | Facebook's Users Ask Who Owns Information[END_REF].

Distributed Aggregation. Performing the polling through a distributed aggregation is a simple, yet naïve, alternative to avoid a central server. Participants aggregate votes in such a way that it is impossible to know the vote of a specific participant. Such an aggregation scheme, however, is vulnerable to attacks. First, participants may significantly bias the result by corrupting intermediate results. Second, even with aggregation, the initial votes needed for bootstrapping are revealed. To prevent the initial bootstrapping votes to be known, each vote could be split according to a homomorphic secret sharing scheme. However, a dishonest participant can still create an invalid initial set of shares, for instance by voting for an arbitrary large value, and thus bias the result.

Secure Multi-Party Computation. Assuming a minority of dishonest users, the distributed polling problem may be solved with complete privacy and no bias on the outcome by using heavy machinery from cryptography using protocols for secure multi-party computation (MPC) between N mutually distrustful users [START_REF] Rabin | Verifiable Secret Sharing and Multi-Party Protocols with Honest Majority[END_REF]. Following two decades of theoretical advances, MPC protocols to address efficiency and scalability concerns have only recently been proposed [START_REF] Damgård | Scalable and Unconditionally Secure Multiparty Computation[END_REF][START_REF] Damgård | Scalable Multiparty Computation with Nearly Optimal Work and Resilience[END_REF]. The line of work is promising, but even the time and communication complexity of the state-of-the-art protocol (a polynomial in N) [START_REF] Damgård | Scalable Multiparty Computation with Nearly Optimal Work and Resilience[END_REF] are too large to be practical.

Our solution to the polling problem does not rely on cryptography for ensuring privacy or accuracy. This is for three reasons. First, we are concerned that the practicality and scalability of the protocol will be impacted by the complexity of cryptographic techniques. Accordingly, we wish to explore the space of protocols where we give up some bounded degree of privacy and accuracy without compromising scalability and performance. Second, there is a small risk that the unproven assumptions underlying modern cryptography techniques (e.g., impracticality of factoring large numbers or inverting higher mathematical functions) may be broken. To avoid a full dependence on such techniques, it is prudent to study alternatives. Third, as advocated in [START_REF] Malkhi | E-Voting without 'Cryptography[END_REF] and [START_REF] Rivest | Chaffing and Winnowing: Confidentiality without Encryption[END_REF], there is scientific value in determining if traditional problems in distributed computing (e.g., computation in general and polling in particular) can be solved without cryptography and if so, how efficiently. These investigations help us understand the crux of the individual problems.

Instead of using cryptography, we exploit the social nature of the participants involved in the polling protocol, specifically the one-to-one correspondence between social network identities and real ones. The key insight is that participants in social networks care about their reputation: information related to a user ultimately reflects on the associated real person. Therefore, their misbehavior is rather restricted and not fully Byzantine. We leverage this concern and propose an approach which dissuades dishonest behaviors instead of masking their impact (e.g., as in BFT [START_REF] Castro | Practical Byzantine Fault Tolerance and Proactive Recovery[END_REF]) or preventing them (e.g., by using cryptography [START_REF] Baudron | Practical Multi-candidate Election System[END_REF]). In addition to running a polling algorithm based on a simple secret sharing scheme, we execute a distributed verification protocol which tags the profiles of the participants based on collected testimonies. A reputation system like EigenTrust [START_REF] Kamvar | The EigenTrust Algorithm for Reputation Management in P2P Networks[END_REF] can be used to manage the blames in a robust manner. Social relationships between users further help preventing colluding users from submitting wrongful reports.

To illustrate the idea behind tagging, consider a situation where the testimonies of Alice and Bob demonstrate that Mallory misbehaved. In this situation, Alice's and Bob's profiles are then tagged with "Alice and Bob jointly accused Mallory" and the profile of Mallory is tagged with "Mallory has been accused by Alice and Bob". In a social network, no participant would like to be tagged as dishonest by a protocol that does not wrongly accuse participants, as we will describe below. Our protocol does not wrongfully blame participants, but dishonest participants may [START_REF] Urdaneta | A Survey of DHT Security Techniques[END_REF].

Assuming a system with a large majority of honest participants, the risk for a participant to be caught when wrongly accusing others is high. For instance, if a participant is accused only by users that are related in the social network (i.e., friends forming a coalition), the allegation would be suspicious and thus not taken into account and the claim would eventually backfire on the accuser. It is important to note that Sybil identities can be detected by analyzing the specific characteristics of social graph (e.g., SybilGuard [START_REF] Yu | SybilGuard: Defending Against Sybil Attacks via Social Networks[END_REF], SybilLimit [START_REF] Yu | SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks[END_REF]). Without Sybil identities, the problem of dishonesty boils down to the case where a coalition of real users try to affect an honest user's profile by wrongfully blaming her, attempt to spam the system with a large number of blames, or blame one another as a smokescreen. By leveraging the acquaintanceship between users (e.g., the social graph -be it explicit or inferred), several practical systems have been proposed and successfully applied to on-line massively multi-player games [START_REF] Goodman | A Peer Auditing Scheme for Cheat Elimination in MMOGs[END_REF][START_REF] Kabus | Addressing Cheating in Distributed MMOGs[END_REF], spam mitigation [START_REF] Mislove | Ostra: Leverging Trust to Thwart Unwanted Communication[END_REF][START_REF] Sirivianos | SocialFilter: Introducing Social Trust to Collaborative Spam Mitigation[END_REF] and recommendation systems [START_REF] Tran | Sybil-resilient Online Content Voting[END_REF]8]. Most of these techniques require a consensus of an unaffiliated jury to expel a user and renounce blames originating from friends that are considered suspicious.

In devising our protocol, we have considered a system with both honest and dishonest participants. The honest ones follow the protocol assigned to them whereas the dishonest ones might not, in order to promote their opinion beyond what is allowed. Should dishonest nodes deviate from the protocol, we assume that they never do anything that will jeopardize their reputation with certainty (i.e., with probability 1). We believe that our model for dishonest users is more reflective of real human behavior than e.g. Byzantine users as it accounts for social aspects of the participants, and is interesting in its own right. It is an intriguing direction to consider how to solve problems under this model.

Contributions

We present DPol, a scalable polling protocol that leverages special properties of social networks. In a nutshell, DPol works as follows. Participants, clustered in fully connected groups known as offices, make use of a simple secret sharing scheme to encode their vote. Then they send the shares of their vote to proxies that belong to another group (an office). In the context of polling, the shares of a vote are referred to as ballots.

The key idea is that participants can retain privacy by submitting ballots for their chosen candidate as well as ballots for the candidates they didn't vote for, making sure to send one more ballot for the true choice than the other ones. Each office computes a partial tally that is further broadcast to all other groups. Each participant eventually outputs the same tally. DPol is fully decentralized and does not assign specific roles to any participant. Our scheme results in a simple and scalable protocol that is easy to deploy.

Complexity. The time complexity of

DPol is O( √ Nk), the spatial complexity is O( √ Nk) and the number of messages sent is O( √ Nk),
where k is the privacy parameter and N the number of participants. We point out that other decentralized protocols have explored the O( √ N) trade-off between time and message complexity (e.g., Kelips [START_REF] Gupta | Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead[END_REF] and [START_REF] Galil | Partitioned Encryption and Achieving Simultaneity by Partitioning[END_REF]).

Privacy and accuracy. The trade-off between privacy and accuracy arises naturally in our settings: improving accuracy means verifying the participant's actions, which in turn compromises privacy. We bound the impact on the polling result by dishonest participants and balance this with the level of privacy ensured. More specifically, in a system of N participants with B colluding dishonest participants (assuming a social network with a limited number of Sybil identities), we can choose any integer k such that the probability for a given participant to have its vote recovered by dishonest participants is bounded by (B/N) k+1 and their impact on the outcome of each of the d options is bounded by (3k + 2)B with high probability when B < N/2 for large N, assuming that dishonest nodes have no control over the assignment of nodes to groups (more specifically that nodes are assigned to groups uniformly at random). For B < √ N, the accuracy guarantee of (3k + 2)B always holds for any value of N and for any assignment of nodes to groups, and the relative error on the poll outcome is negligible when N is large. This is due to the ability of our underlying simple secret sharing scheme to expose, with certainty, dishonest participants that affect the outcome by more than 3k +2 with only public verifications, i.e., without requiring the participants' votes to be revealed. We also show that private verifications expose, with positive probability, dishonest participants who try to affect the outcome below the limit (i.e., even if their impact on each option is less than 3k + 2), but require inspection of the contents of a subset of ballots. Our results also imply that a coalition of a minority of the nodes cannot influence the outcome of a poll if the most popular option has a lead of more than (6k + 4)B votes over the runner up.

For illustration, consider a poll with two options, Yes and No (a binary poll), in a system of 10, 000 participants. Further, assume there are 99 colluding dishonest participants ( √ N -1), and assume that a fraction α of the participants vote Yes. By setting k = 1, for instance, we ensure privacy with probability 99.99% and when α > 0.54, every participant computes the right decision (i.e., Yes). While e-voting requires stronger guarantees, this amply fits polling applications requirements.

Practicality. DPol is easy to deploy and we report on its deployment on 400 PlanetLab nodes. The result of a binary poll suffers an average relative error of less than 10% in the face of message losses, crashes and asynchrony inherent in PlanetLab. In the presence of dishonest participants, our experiments show that the impact on the polling result is (4k + 1)B on average, consistently lower that the theoretical bound of (6k + 4)B. Further, we back up various theoretical results with experimental evaluation throughout the paper.

Roadmap

The rest of the paper is organized as follows. Section 2 presents the model and introduces the terms and notation used throughout the paper. We present DPol in Section 3 and we report on the deployment of its binary version on PlanetLab. We analyze the correctness and complexity of the protocol. We derive upper and lower bounds on the impact of dishonest nodes in Section 4 by considering worst case scenarios. Section 5 revisits these bounds in practical scenarios. Probabilistic results are illustrated with simulations and experiments on PlanetLab. Section 6 reviews related work and we conclude in Section 7.

System Model

We consider a system of N uniquely identified nodes that represent participants of a social network. Each node p votes for a value v p ∈ V and the expected output of the polling algorithm is a vector containing the proportions of nodes voting for each value in V . The set of possible votes V is {1,..., d} where d is the number of options. Each participant in the social network has an assigned profile which may be tagged by DPol. We assume that nodes are able to communicate by messagepassing, specifically that they can receive messages from any other node in the system. To make this assumption work in the real world, the communication takes place using UDP and efficient NAT traversal techniques ("hole punching") such as STUN [START_REF] Rosenberg | Session Traversal Utilities for NATs (STUN)[END_REF]. Other complementary techniques, for instance the Internet Gateway Device Protocol (through Universal Plug'n'Play), are supported by modern routers and can be used to let devices behind the NAT to dynamically add translation rules thus allowing them to receive incoming messages. We used UDP communication in our implementation and deployment on PlanetLab.

In our model, nodes are either honest or dishonest. Honest nodes strictly follow the protocol and contribute to the verifications as long as their privacy is not compromised. More specifically, honest nodes always collaborate with verification procedures that do not require them to reveal their ballots (i.e., public verifications). However, they may refuse to reveal their ballots for a verification procedure (i.e., private verification). Dishonest nodes may misbehave either to promote their opinion or reveal the opinion of honest nodes. They are, however, rational in the sense that they never behave in such a way that their reputation is tarnished with certainty, i.e., they do not perform attacks that are guaranteed to be detected by public verification procedures. As such they are less powerful than Byzantine users. As motivated in the introduction, dishonest nodes do not wrongfully blame honest nodes since it is rather easy for a human reader or an automatic tool aware of social relationship between users, to distinguish between legitimate and wrongful accusations. Consider, for example, a single participant who blames a large number of nodes and the case where a group of related participants all blame an identical set of nodes. Several existing systems manage to filter wrongful blames or at least limit their impact. For instance Digg [8] does not allow related users to rate each other's articles. SumUp [START_REF] Tran | Sybil-resilient Online Content Voting[END_REF] allows nodes to vote only over the edges of the social network thus limiting the impact of coalitions of connected users. Ostra [START_REF] Mislove | Ostra: Leverging Trust to Thwart Unwanted Communication[END_REF] bounds the emission rate of a node by the number of trust relationships it has. SocialFilter [START_REF] Sirivianos | SocialFilter: Introducing Social Trust to Collaborative Spam Mitigation[END_REF] complements trustworthiness by the notion of credibility which weights the reports nodes send. Finally, EigenTrust [START_REF] Kamvar | The EigenTrust Algorithm for Reputation Management in P2P Networks[END_REF] uses an iterative algorithm inspired by PageRank to determine node reputation in a robust way.

We consider participants who collude to form a single coalition B (|B| = B). When dishonest nodes collaborate to bias the outcome of the poll, they are assumed to share the same opinion. While honest nodes vote for one option, dishonest nodes may want to promote a set of options. Still, they act selfishly in the sense that they prefer to protect their own reputation to covering up their suspected accomplices. A single coalition represents the worst case scenario for both discovering a node's vote and for biasing the result of the polling.

DPol relies on a structured overlay, independent of the social graph, which provides scalable dissemination and facilitates verifications. This overlay could be provided by the social network infrastructure or be built in a decentralized fashion. The N nodes are clustered into r ordered groups, from g 0 to g r-1 . A node p in group g i maintains two sets of nodes: a set P o of officemates containing all nodes belonging to the same group (P o = g i \{p}) and a fixed-size set P p of proxies, containing nodes in the next group (P p ⊆ g i+1 mod r ). Therefore, all groups virtually form a ring with g 0 being the successor of g r-1 . Each group g i is a clique. We define the client of a node p to be a node for which p acts as a proxy. Every node maintains a list of its clients in the previous group (P c ⊆ g i-1 ). Each node discards messages that originates in nodes which are not in the set P c ∪ P o . Figure 1 depicts the overlay used by DPol. Several prominent overlay construction protocols make use of group-based overlays using gossip, the most commonly known of which is Kelips [START_REF] Gupta | Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead[END_REF]. These protocols can further be made robust to dishonest nodes and provide mechanisms that we will extend for polling. Fireflies [START_REF] Johansen | Fireflies: Scalable Support for Intrusion-Tolerant Network Overlays[END_REF], for instance, builds a randomized intrusion-tolerant overlay on which Byzantine nodes have only a limited control, and is resilient to the eclipse attack (i.e., no node has only Byzantine neighbors [START_REF] Urdaneta | A Survey of DHT Security Techniques[END_REF]). Brahms [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] provides unbiased uniform random peer-sampling in the presence of Byzantine nodes. Finally, AVMON [START_REF] Morales | AVMON: Optimal and Scalable Discovery of Consistent Availability Monitoring Overlays for Distributed Systems[END_REF] builds a pseudorandom overlay based on the hashes of the nodes' IP addresses (on which malicious nodes have very little, if any, control) thus reducing the chances of colluding nodes being connected. We further discuss the overlay construction and how to make it resilient to dishonest nodes in our probabilistic analysis which assumes a uniform random distribution of nodes among groups (Section 5).

The Polling Protocol

In this section, we present DPol and prove that the protocol is correct; we then analyze its spatial and message complexity and present experimental results of a binary poll on PlanetLab. We complement these experiments with an analysis of DPol in the presence of crashes and message losses.

Polling in a nutshell

DPol is composed of three phases: (i) voting, (ii) counting and (iii) broadcasting. A node's vote goes to one option Figure 1: The structure of DPol. Node p in g i acts as a proxy for its clients in the preceding group g i-1 , and has proxies of its own in the successive group g i+1 . It also communicates with its officemates -the nodes in g i .

v p ∈ {1,..., d}. During the voting phase, a node generates a set of ballots in the form of binary vectors of size d, b ∈ {0, 1} d reflecting its vote (when aggregated) and sends each ballot to one of its proxies. A ballot with only the first two bits set equally promotes the first two options over the d -2 other options. In the counting phase, each node in a group computes the sum of the votes of the nodes in the previous group (local tally). This is achieved by having each proxy summing up the ballots it has received and broadcasting the result to its officemates. Finally, the local tallies are forwarded along the ring so that all nodes eventually compute the final outcome. Tallies are natural numbers vectors of size d, t ∈ N d and the component with the maximum value in the final tally vector determines the winner of the poll.

Description

We now give the algorithm details of each phase of the DPol protocol.

Voting. The ballot generation method is inspired by the simple secret sharing scheme introduced in [START_REF] Delporte-Gallet | Secretive Birds: Privacy in Population Protocols[END_REF] and shares similarities with the Vote/Anti-Vote/Vote system [START_REF] Rivest | Three Voting Protocols: ThreeBallot, VAV, and Twin[END_REF]. To vote for a given value v ∈ {1,..., d}, a node generates 2k

+ 1 ballots b 1 ,..., b 2k+1 ∈ {0, 1} d representing its vote,
where k is an integer called the privacy parameter. To be valid, a ballot must contain at least one 1 and at least one 0.

In the binary case, a valid ballot is (1, 0) or (0, 1). In this case, the intuition is to create k +1 ballots towards a given target (first or second option) and k ballots for the other option, such that when the ballots are summed they result in a vote for the chosen option v p . In general, we assign the i-th option with a vector c i = (0,..., 0, 1, 0 ...,0) with 1 in the i-th position and its complementary vector c i = (1,..., 1, 0, 1,..., 1) with a 0 at the i-th position. In the case where a node is allowed to vote for a single option, a valid vote therefore equals

c i + k • (1,..., 1)
where k is the privacy parameter. The ballots emitted by a node must sum to a valid vote. For instance, in the case d = 3 and k = 1 the set of ballots {(1, 0, 0), (0, 1, 1), (1, 0, 0)} is valid and promotes the first option. Polling Algorithm

1: vote(v, P p ) 2: local_count(t , P p ) 3: t = t + t 4: local_tally_broadcast(i, t , P p ) 5: t = ∑ i T [i]
Voting phase procedure vote(v,P p ) is 6:

{b 1 ,...,b 2k+1 } = share(v) 7:
for each proxy ∈ P p do

8: send [Ballot, b i ] (proxy) 9:
end for

upon event receive | [Ballot, b] do 10: t = t + b function share(v) returns a set of ballot B is 11: B = {c v } 12:
for each i ∈ {1,...,k} do 13: w = random number in {1,...,d} 14:

B = B ∪ {c w } ∪ {c w } 15:
end for

S [i group ] = S [i group ] ∪ {t} 25: if ( S [i group ] = |P c |) then 26: T [i group ] = choose(S [i group ]) 27: if (i group (i + 1) mod r) then 28: local_tally_broadcast(i group ,T [i group ])

return the most represented local tally in A

In DPol, a node generates k ballots associated to k random candidates and their complementary ballots and a single ballot for the candidate v it wants to promote (lines 11-16 in Algorithm 1). Such a set of ballots is valid and sums to c v + k • (1,..., 1). Once a node has generated its 2k + 1 ballots, it sends each of them to a different proxy. The number of proxies is to be chosen accordingly, P p = 2k + 1. Lines 6-9 in Algorithm 1 detail the voting phase. Figure 2(a) depicts a node sending its 2k + 1 ballots (e.g., {(0, 1), (1, 0), (1, 0)}) to its assigned proxies. Once every node in the system has received one ballot from each of its clients, the voting round is over.

Intermediate Counting. A group acts as a voting office for the preceding group on the ring. The officemates collect ballots from their clients (Figure 2 Local Tally Forwarding. Once the intermediate counting phase is over, i.e., all the officemates have computed a local tally, each node sends the local tally of its group to its proxies (lines 21-23 in Algorithm 1). Upon reception of a message containing a local tally, a proxy adds it to the set S [i] of possible values for g i (line 18 in Algorithm 1). When a proxy has received the expected number |P c | of local tallies for a given group g i , it decides on a local tally by choosing the most represented value in S [i] and stores it in T [i]. When a local tally T [i] is assigned, it is further forwarded (Figure 2(d)) to the next group using the proxies (lines 25-30 in Algorithm 1). Local tallies are then forwarded in the system along the ring. When a node receives the local tally corresponding to its own group, the tally is no longer forwarded (lines [START_REF] Rivest | Three Voting Protocols: ThreeBallot, VAV, and Twin[END_REF][START_REF] Rodriguez-Perez | Analysis of Peer-to-Peer Distributed Reputation Schemes[END_REF][START_REF] Rosenberg | Session Traversal Utilities for NATs (STUN)[END_REF]. The global tally is computed at each node by simply summing the local tallies of all groups: t = ∑ r-1 i=0 T [i] (line 5 of Algorithm 1). The nodes in group g i assume a special role for the members of the preceding group g i-1 : they collect and count ballots from g i-1 and initiate the dissemination of the resulting local tally over the ring. Each group has a special role for the preceding one, and all nodes execute the exact same protocol.

Analysis

In this section, we analyze the correctness and complexity of DPol assuming an ideal setting (i.e., reliable channels and nonfaulty nodes) and only honest nodes. We later revisit these assumptions by measuring the impact of message loss and crashes both analytically and experimentally in Section 3.4. We will consider the impact of dishonest nodes on privacy and accuracy in the worst case in Section 4 and on average in Section 5. Proof. (Accuracy) We first prove that the local tally computed in every group g i reflects the vote of all nodes in g i-1 . The local tally computed in a group is the sum of the ballots received by its members. Each node p in g i-1 sends each of its ballots b 1,p ,..., b 2k+1,p to distinct proxies in g i . Similarly, each proxy p in g i receives a set of ballots B p from its clients. Since all nodes are honest by assumption, the set of ballots sent by the nodes in g i-1 equals the set of ballots received in g i . Therefore, each member of g i computes the local tally to be:

Theorem 1 (Correctness). Consider a system of size N where each node p votes for the v p -th option. The polling algorithm terminates and each node eventually outputs N

• k(1,..., 1) + ∑ p c v p . (0,1) (1,0) (1,0) g i-1 g i (a) Voting (1,0) (1,0) (1,0) (3,0) g i-1 g i (b) Intermediate counting (3,0) (1,2) (2,1) (9,3) (3,0) g i (c) Individual tally sharing
t = ∑ p ∈g i ∑ b∈B p b = ∑ p∈g i-1 2k+1 ∑ j=1 b j,p = ∑ p∈g i-1 k • (1,..., 1) + c v p = |g i-1 | • k • (1,..., 1) + ∑ p∈g i-1 c v p
Note that this follows from the homomorphic property of the simple secret sharing scheme. Since nodes do honestly forward the local tallies along the ring and the messages are eventually received, each node ends up with the correct values for the local tallies of every group, and thus the correct global tally.

(Termination) A node knows the number of messages it is supposed to receive in each phase. Since every node sends the required number of messages and every message eventually arrives, each phase completes. Because the algorithm has a finite number of phases, it is guaranteed to eventually terminate.

Proposition 1 (Spatial complexity). The size S of the state maintained at each node in group g

i is O(r • k + |g i |).
Proof. A node maintains the set of proxies (2k + 1), the set of its officemates (|g i |) and the list of its clients (at most |g i-1 |). Additionally, a node stores a set of 2k + 1 possible values (a node has 2k + 1 clients on average) for each of the r local tallies to perform global counting, that is

S = O(k) + O(|g i |) + O(|g i-1 |) + O(r • k) = O(r • k + |g i |).

Proposition 2 (Message complexity). The average number of messages M sent by a node in group g

i is O(r • k + |g i |).
Proof. A node sends messages during the voting phase (2k + 1 ballots), the intermediate counting phase (|g i | -1 individual tallies), and the global counting phase which involves the dissemination of r local tallies along the ring using its 2k

+ 1 proxies, that is M = O(k) + O(|g i |) + O(r • k) = O(r • k + |g i |).
Note that the parameters are not independent: the sizes of the groups are related and bound to the number of groups by the relation Proof. The voting phase operates in 2k + 1 rounds. The counting phase requires each node to send its individual tally to its |g i | -1 officemates. All the nodes in the system send their individual tally in parallel, therefore the time complexity of this phase is O(|g i |). The local tally broadcast phase operates in O(kr) rounds as it requires 2k + 1 rounds for a local tally to be forwarded from one group to the next one and the ring is composed of r groups.

Using the values of the parameters r and {g i } r i=1 specified above, the time complexity of DPol is O( √ Nk).

Evaluation

We report on the deployment of DPol, in the case of binary polling, on a PlanetLab testbed of 400 nodes and analyze the practical performance of DPol. The message loss rates, crashes and asynchrony inherent to PlanetLab allow us to experiment with the algorithm in tough real-world settings. We evaluate our algorithm with two different privacy parameter values k = 1 and k = 2.

Overlay. The cluster-ring-based overlay is built using a centralized bootstrapping entity which keeps track of the whole set of nodes, assigning each node to a random group. Nodes have exactly 2k + 1 proxies in the next group and the number of clients of a node is

(2k + 1) |g i-1 | / |g i | on average.
Communication and Asynchrony. Nodes communicate by UDP which may suffer message loss on the communication channels. For instance, we observed loss rates on PlanetLab ranging from 5% to 15%. In addition, PlanetLab nodes are unreliable, causing expected messages to be lost due to sender crashes. Therefore, phase terminations cannot be detected by simply counting the number of received messages. In the local tally forwarding phase, when the number of possible values for a local tally grows beyond a given threshold γ • |P c |, the node gets Δt seconds to make the decision for this particular local tally. The two other phases are simply bounded in time. In our implementation, γ is set to 0.5 and Δt to 5 seconds.

Experimental results. Figure 3 shows the accuracy of DPol among 400 PlanetLab nodes with k = 2. Figure 3(a) considers the value of the outcome while Figure 3(b) considers the sign of the outcome. By outcome we mean the difference between the number of votes for the first option (i.e., corresponding to the first component of the tally) and the number of votes for the second option. More specifically, the outcome equals (1, -1) T • t . Without loss of generality, we vary the proportion α of node voting for the first option between 0.5 and 1. In Figure 3(a), we plot the standard deviation on the computed outcome for α in that range. For each run, we compute the average of the error when computing the outcome (this is the difference between the outcome on each node and the real one) over all nodes. Each point represents the average of this value over 20 independent runs. Note that the accuracy increases when α is close to 0.5. This is because the closer the tally is to 0.5, the lower the impact of message losses on the outcome. Effectively, the two components of the individual and local tallies are close and therefore their impact on the outcome is close to zero.

Figure 3(b) displays the fraction of nodes deciding on the winning option (among the nodes that were able to decide on a global tally) as a function of α. Effectively, even if the standard deviation is relatively small, some nodes may decide incorrectly on the winning option. Consider the organizers of a Saturday night party asking their friends in a social network whether partners should be excluded or not. As depicted in Figure 3(b), for α = 52.5%, some nodes would compute a different answer than the majority. This means that a minority of participants who compute negative outcome would come with their partners. Figure 3(b) (solid line) also shows the proportion of nodes that are unable to decide on a global tally (because their set of possible values never reach the threshold γ). We observe that this fraction remains very low (less than 4%) and is independent of α.

Analysis. Crashes and message loss do arise and affect the correctness and termination of the protocol. Crashes can impact the system in two different ways. First, nodes may crash independently before sending unique information. The information refers to data they received that did not yet get replicated, typically initial shares of votes (i.e., ballots). Losing such data affects the global tally. Second, several nodes may be crashed at given time. This may result in other nodes being unable to decide on a local tally and thus on the global tally from a lack of corroborating pieces of information. In the following, we analyze the impact of the first type of crashes on the outcome. Finally, by relaxing the decision condition from

S [i group ] = |P c | to S [i group ] ≥ γ • |P c | (
as described above), we compute the probability of a node failing to decide on the global tally.

Proposition 4 (Impact of crashes on accuracy). An individual crash can affect the score of an option up to 3k + 2.

Proof. Consider a node that crashes before broadcasting its individual tally to its officemates. This individual tally is lost, and represents the sum of the |P c | = 2k + 1 ballots sent by its clients. The impact of such a crash on each option score is bounded by 2k + 1 since ballots are binary vectors. Moreover, if a node crashes while sending its ballots, it affects each option score by up to k + 1. The maximum impact of an individual crash is thus 2k

+ 1 + k + 1 = 3k + 2.
We assume that nodes crash with probability c and never recover from a crash. There is a probability d i for a node p ∈ g i not to decide on the local tally of group r. This can happen if more than (1 -γ) |P c | = (1 -γ)(2k + 1) clients fail to forward the local tally because they either crashed or have themselves not decided on the local tally. We define e i as the probability for a node in g i to fail to forward a local tally. We have e i = c + (1c)d i where

d i = γ(2k+1)-1 ∑ j=0 2k + 1 j (1 -e i-1
) j e 2k+1-j i-1

and d 0 = 0 A node does not decide on the global tally if it has not has decided on at least one local tally, that is d r .

Discussion. DPol is a decentralized peer-to-peer protocol deployed on the Internet, where nodes may leave and join the system dynamically. This behavior, referred to as churn, is both common and widespread, and may further disrupt the function of the protocol beyond message loss and node crashes. Fortunately, because our protocol is lightweight and executes quickly, the impact of churn is at the same manageable level as we observed in our PlanetLab experiments (i.e., only a few nodes among the 400 nodes participating in the poll crashed or left during the course of the protocol) as we detail below.

As we explained at the beginning of this Section, the phases of DPol are bounded in time for fault-tolerance. During our experiments with 400 nodes, we set the time-out δ to 5 seconds, thus giving an execution time of less than 20 seconds. Using Proposition 3, which states that the time complexity of DPol grows as √ N, we can make a projection for a poll involving 100,000 participants (recall that DPol targets polls within groups rather than in the entire social network): the algorithm is expected to complete in approximately five minutes.

To put this duration in perspective, several trace-driven analysis of churn in various peer-to-peer systems and applications, including file-sharing (BitTorrent, eDonkey [START_REF] Stutzbach | Understanding Churn in Peer-to-Peer Networks[END_REF]), Voice over IP (Skype [START_REF] Xie | A Measurement-Based Study of the Skype Peer-to-Peer VoIP Performance[END_REF]) and on-line social networks (Facebook, Hi-Five [START_REF] Schneider | Understanding Online Social Network Usage from a Network Perspective[END_REF]), report an average session time of at least a few minutes. They further show that this duration is significantly increased when considering peers who already spent some time in the system, and initial duration of 5 minutes are typical for social networks. For instance, it is shown in [START_REF] Stutzbach | Understanding Churn in Peer-to-Peer Networks[END_REF] that more than 95% of the peers who already spent an hour in the system stay at least one more hour in the system. Therefore, by assuming (or even requiring) that peers have spent a reasonable time online to participate to the poll, the impact of churn is brought down to a level in which we ensure stability for a correct execution of the protocol. This corresponds to the outcome of our experiments, in which only a handful of nodes were unable to determine the outcome of the poll due to crashes.

Impact of dishonest nodes

In this section, we analyze the maximum impact of dishonest nodes on DPol. For the sake of the analysis, we assume an overlay with √ N groups of size √ N ( √ N ∈ N), such as Kelips [START_REF] Gupta | Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead[END_REF], and that each node has exactly the same number (2k + 1) of clients and proxies. We consider a polling scheme based on secret sharing to preserve privacy and we assume auxiliary verification schemes to detect attacks and identify dishonest nodes. We distinguish between two types of verifications: (i) public verifications that leverage only information which does not compromise the nodes' privacy (i.e., the content of the ballots), such as the individual tallies received from their officemates, and (ii) private verifications that may leverage all information including the content of the ballots.

To dissuade nodes from misbehaving, verifications affect the user profiles of the involved nodes. When an attack is detected and reported, the neighbors of the accused nodes, i.e., the nodes it communicates with (typically clients and proxies), are asked for the messages they exchanged. If the testimonies of p 1 and p 2 demonstrate that p 0 misbehaved, their profiles are tagged with "p 1 and p 2 jointly accused p 0 " and the profile of p 0 is tagged with "p 0 has been accused by p 1 and p 2 ". These tags can then be used to determine abnormal behaviors.

Preserving privacy in the presence of dishonest nodes

We derive a theoretical upper bound on the impact of a coalition of dishonest nodes on the nodes' privacy, that is the maximum number of votes the dishonest coalition can disclose.

Theorem 2. A coalition of B malicious nodes can disclose the votes of at most B • 2k+1

k+1 ≤ 2B honest users.

Proof. This theorem follows from the secret sharing scheme used in DPol, which is to divide a node's vote into 2k + 1 ballots. Among them, k + 1 ballots have the bit corresponding to the node's vote set and only k ballots have the bit corresponding to each competing candidate set. We first prove that a node's vote is disclosed by dishonest nodes if and only if its k + 1 proxies that received the ballots corresponding to its vote (i.e., the ballots in which the v p -th bit is set) belong to the coalition. It is clear that if k + 1 ballots received by the dishonest have a bit set at the v p -position, the vote is recovered with certainty. We now prove the contrapositive statement by contradiction. Let b be the sum of the ballots sent by p to dishonest proxies. We suppose that all the components of b are strictly lower than k + 1 and assume that the dishonest coalition recovers the client's vote. Not all of the 2k +1 proxies can be dishonest, otherwise, b would simply have been the vote of p, that is c v p + k • (1,..., 1) (whose v p -th component is equal to k + 1). The best case (from the standpoint of the coalition) is when 2k proxies are dishonest. In that case, the components of b are either equal to k -1 or k. The vote of p is recovered with certainty if and only if a single component of b is equal to k. This implies that the missing ballot contains only ones, which is in contradiction with the definition of a valid ballot. Since all nodes, including dishonest ones, have exactly 2k +1 clients, the dishonest coalition collects a total of B • (2k + 1) ballots which in turn may recover at most B • 2k+1 k+1 votes.

Confining the impact of dishonest nodes

First, we assume that honest nodes do not want to disclose any of the ballots they sent or received (i.e., public verifications). In this context, we study the impact of colluding dishonest nodes.

Next, we assume that honest nodes are willing to sacrifice privacy for accuracy by revealing some of their ballots (i.e., private verification) and we explore how this information can be used to catch dishonest nodes that cheat without being detected by public verifications. Proof (structure). The proof relies on the facts that (i) honest nodes always tell the truth and strictly follow the protocol (including verifications), and (ii) dishonest nodes do not behave in such a way that their reputation is tarnished with certainty. Effectively, showing that the attacks with an impact greater than 3k + 2 are detected by the honest nodes with certainty proves the theorem. A dishonest node may bias the protocol at all three phases. Lemmas 4-7 encompass all possible attacks, propose a detection scheme relying on honest nodes, and bound the impact of those that cannot be detected with certainty. In addition, if an attack is detected, we prove that the dishonest node is exposed by the public verification. Summing the impacts of all these attacks (Lemmas 4 and 5) for each dishonest node gives a maximum impact of k + 1 + (2k + 1) = 3k + 2 on each component of the global tally.

Impact of a dishonest coalition under public verifications

Note that the proof relies on the assumption B < √ N , where N is the size of the system and the size of a group is √ N, to ensure that the dishonest coalition can neither "control" (there is at least one honest node to report a misbehavior inside each group) nor "fool" an entire group without being detected (there are not enough dishonest nodes to both perform and cover dishonest actions). This security property holds deterministically under the assumption B < √ N irrespective of how dishonest nodes are distributed among the groups. Indeed, in the worst case scenario where all dishonest nodes are concentrated in one or two consecutive groups, the fact that the number of dishonest nodes is strictly smaller than the size of a group guarantees that there is at least one honest node in each group and that there is a majority of honest node in every pair of successive groups.

The weakest assumption needed is that two consecutive groups contain less than √ N dishonest nodes, formally that

|g i ∩ B| + |g i+1 ∩ B| < √ N for all i.
In Section 5, we provide probabilistic analysis of this bound in a setting where dishonest nodes are distributed randomly among the groups and prove that the system is not compromised (dishonest nodes do not form a majority in any pair of consecutive groups) with high probability when N tends to infinity for B < N/2. Corollary 1. When the margin of the leading candidate over the next candidate is more than (6k + 4)B, a coalition of B < √ N dishonest nodes cannot influence the outcome of the poll.

Proof. By Theorem 3, colluding dishonest users may decrease the score of the leading candidate by at most (3k + 2)B and boost the score of some other candidates by at most (3k + 2)B. This decreases the lead of the top candidate over the runner up by at most (6k + 4)B, which is not sufficient to change the outcome of the poll.

Note that one can infer a relation between the margin by which the leading candidate wins and the maximum number of dishonest nodes the system can tolerate (i.e., to output the correct winner). Consider the binary case for instance where a proportion α > 0.5 of nodes promote the first candidate. Then the margin is N(2α -1) and the maximum number of dishonest nodes the system can tolerate is N(2α -1)/(6k + 4).

Corollary 2. If the proportions of nodes voting for each candidates are nonzero, DPol is asymptotically accurate for B = o(N) dishonest nodes.

Proof. Let (α 1 ,..., α d ) be the proportions of nodes voting for the respective candidates. It can be inferred from Theorem 3 that the relative error on the score of the i-th candidate is bounded by (3k + 2)B/(α i N). Using the fact that B is a sublinear function of N proves that the relative error on the vector of scores computed by DPol tends to 0 when N tends to infinity, which concludes the proof.

Lemma 4 (Voting). When voting, a dishonest node can affect each candidate score by at most k + 1.

Proof. Due to the overlay structure, a node can only send ballots to the proxies it is assigned (otherwise the ballots are discarded), which is a maximum of 2k + 1 ballots. Therefore a dishonest node may affect each component of the global tally by either (i) sending less ballots than it is supposed to or (ii) by sending less than k or more than k + 1 positive ballots for a given candidate (i.e., the bit corresponding to that candidate is set in the considered ballot). In the worst case, the dishonest node sends either 2k + 1 or 0 positive ballots for a candidate. Since the node should send either k or k + 1 positive ballots for that candidate, the maximum impact is

|(2k + 1) -k| = |0 -(k + 1)| = k + 1.
Note that if the node sends 2k + 1 positive ballots for the candidate it is voting for, or 0 positive ballots for a candidate that it is not voting for, the impact is k.

Lemma 5 (Computing individual tallies). Assuming B <

√ N, there exists a public verification scheme such that if a dishonest node modifies the individual tally for a candidate by more than 2k + 1, then the attack is detected with certainty and the node is exposed.

Proof. The overlay structure we consider ensures that any node has exactly 2k + 1 clients and thus receives 2k + 1 ballots during the voting phase. A dishonest node can modify the candidate score by pretending that it received some other number of positive ballots for that candidate, thus affecting the candidate score in its individual tally. If the dishonest node tries to forge too many ballots, specifically by reporting a candidate score outside the range [0, 2k + 1], then the attack is identified by its honest officemates (the assumption B < √ N ensures that at least one such node exists in each voting office). Therefore, in order to not to be publicly detected with certainty, a node that corrupts or forges ballots must output an individual tally in that range. Consequently, the worst case occurs when a dishonest node receives 2k + 1 positive ballots for a candidate and discards them all while summing them, leading to a maximum impact of 2k + 1 on that candidate's score.

We stress that the verification schemes described in the proof succeed to detect misbehavior even in case of collusion. Consider the following situation: a client sends an erroneous ballot (e.g., with value 2 for the first candidate) to a colluding proxy who will aggregate it with its individual tally without reporting the misbehavior. If the dishonest proxy has received only positive ballots for the first candidate (or already turned all the negative ballots into positive ones), the first component in its individual tally will become 2k + 2 which is larger than 2k + 1. This range violation will be detected with certainty. If the dishonest proxy received at least one ballot negative for the first candidate, then covering up for its co-conspirator comes down to turning this negative ballot into a positive one, and the impact will therefore be bounded by 2k + 1. Finally, the assumption that at most √ N -1 nodes are dishonest ensures that there is at least one honest node in each group to report individual tallies outside the range [0, 2k + 1].

Lemma 6 (Broadcasting individual tallies).

There exists a public verification scheme so that a dishonest node that broadcasts inconsistent copies of its individual tally to honest nodes, i.e., sending different values to its honest officemates, is detected with certainty and the node is exposed.

Proof. Before deciding on a local tally, every node broadcasts the set of individual tallies it received to its officemates. This way, an honest officemate will trivially detect the inconsistency. Dishonest nodes are exposed when their neighbors are asked for the individual tallies they received from these nodes.

Note that broadcasting different individual tallies can help a dishonest node to impose an arbitrary value for the local tally. For instance, suppose that k = 2 and that some proxy has 2k + 1 = 5 clients of which only two are dishonest. In this case, there is a majority of honest nodes. Consequently, if the honest nodes send the same local tally, it will be the one chosen by the proxy. However, if the dishonest nodes send different values as their individual tallies then honest nodes will compute different local tallies. The proxy will then decide on the arbitrary local tally sent by the dishonest nodes because it is the most represented.

Lemma 7 (Forwarding local tallies). There exists a public verification scheme to detect with certainty if a group forwards inconsistent copies of a local tally, i.e., nodes sending different values to their proxies, and to expose the dishonest nodes.

Proof. Inconsistency in local tally forwarding is detected assuming the following: before deciding on a local tally, a node broadcasts the set of received local tallies to its officemates. An inconsistency is detected if at least one of the following conditions is satisfied: (C1) an honest node received different local tallies from its clients, (C2) an honest node received different local tallies than its officemates. Consider j dishonest nodes concentrated in a group g i forwarding an incorrect local tally to their proxies. Because of (C1), the clients of an honest node in g i+1 must all be dishonest. Since the number of clients of all nodes equals their number of proxies (2k + 1), j colluding dishonest nodes can corrupt a maximum of j proxies. Therefore, the √ Nj remaining proxies in g i+1 must collude with the coalition in g i to circumvent (C2). This is illustrated in Figure 4. To conclude, in order not to be detected, such an attack requires j dishonest nodes in g i and √ Nj dishonest nodes in g i+1 , that is a minimum number of √ N dishonest nodes in g i ∪ g i+1 . Assuming B < √ N, either a dishonest node in g i is exposed by a public verification scheme (since it broadcast a local tally that does not correspond to the sum of individual tallies it received) or a dishonest node in g i+1 is exposed by a public verification scheme (since it has broadcast a different local tally from the one it received). The proof holds for every hop of the forwarding, including the initial hop which is conducted by the nodes who actually computed the local tally being forwarded.

g i g i+1

Figure 4: Corrupted local tally that remains undetected.

Leveraging private verifications

So far we have only considered public verifications in which the contents of the ballots are never disclosed. Now assume that the nodes accept, with nonzero probability, to relax privacy for the sake of verifications and reveal a subset of the ballots they sent or received or both. This partial information can then be leveraged to detect the dishonest behaviors described in Lemmas 4 and 5.

Consider as a first step, for the sake of simplicity, the case of binary polling. During the voting phase, a dishonest node that sent k + 1 + j ballots (1, 0) and only kj ballots (0, 1) (1 ≤ j ≤ k) is unable to provide the identifier of kj +1 proxies to which it sent a (0, 1) ballot. Therefore, a simple verification is to ask the suspected node to provide a list of proxies who can testify that the node sent at least j ballots of each kind, for a random value j ranging from 1 to k. Note that an inspected node can disclose up to j = k ballots without revealing its vote. For d > 2, the components of an inspected node's vote may be verified independently. Effectively, to check that the vote of a node for the i-th candidate is in [ j , 2k + 1j ] ( j ranging from 1 to k), the verifier asks the inspected node to provide the address of j proxies to which it sent a ballot with a 0 at the i-th position and k proxies to which it sent a ballot with a bit set in the i-th position.

During a ballot corruption attack (Lemma 5), partial information about the ballots received by the inspected node can be leveraged to refine the bound on its individual tally: suppose the inspected node received n b ballots (i.e., under the perfect client-proxy matching assumption n b = 2k + 1), if we further know that it received at least n + b ballots (1, 0) and n - b ballots (0, 1), then the bound on the score of the first candidate can be refined from [0,

n b ] to [n + b , n b -n - b ].
Similarly, the score of the second candidate in the individual tally must be in the range

[n - b , n b -n + b ]
. This verification scheme extends naturally to the cases where d > 2.

p1 p2 (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (3, 0) (a) p1 p2 (1, 0) (1, 0) (0, 1) (1, 0) (1, 0) (3, 0) (b)
Figure 5: Dishonest nodes (p 1 and p 2 ) do not benefit from covering up for each other (illustrated in the binary case).

In both of the aforementioned verification schemes, dishonest nodes have no interest in covering up for one another. Consider the examples depicted in Figure 5 where a dishonest node p 1 is the client of a dishonest node p 2 . In Figure 5(a), if p 1 's vote is verified and p 2 covers p 1 up, i.e., it testifies that p 1 sent a ballot (0, 1), then it exposes itself to a private verification on its individual tally. Note that a node's statement has to be consistent across different verifications, thus if the vote of p 2 is further verified, p 2 must stick to its first version about the ballots it received. The same situation occurs in Figure 5(b): if p 2 's individual tally is verified and p 2 covers up for p 1 , i.e., it testifies it sent a ballot (0, 1) to p 2 , it puts itself at risk should it be subject to a private verification on its vote. Since we assume that dishonest nodes are selfish, they never cover each other up when privately verified. In conclusion, relaxing privacy ensures that every dishonest node has nonzero probability to be exposed. A lower bound on this probability is given in Section 5.5.

Polling in practice

So far we evaluated the impact of a coalition of dishonest nodes in a worst case scenario. In this section, we revisit the results and assumptions of the previous section for the average case. More specifically, we assume a random uniform distribution of nodes across the r groups and that nodes in the next groups are distributed uniformly at random as proxies in the preceding groups. We justify this assumption by sketching an overlay construction protocol, inspired by various techniques found in the literature, which guarantees a uniform pseudorandom distribution of nodes in groups on which nodes will have no or very little control ( §5.1). We then study the average impact of dishonest nodes on privacy ( §5.2) and accuracy ( §5.3). Then we refine the security condition that prevents dishonest nodes from biasing local tallies in an unbounded way during forwarding (i.e., controlling two consecutive groups as explained in Lemma 7) ( §5.4). Finally, we give a lower bound on the probability of detecting a dishonest node who cheats within the bounds (i.e., 3k + 2) by means of private verifications as function of the willingness of honest nodes to compromise their privacy (i.e., disclose their vote) ( §5.5). The results presented in this section are consistent with simulations and experiments on a 400-node PlanetLab testbed.

Overlay construction

The overlay driving DPol organizes the nodes in √ N groups arranged on a ring. Each node is connected to all the nodes in its group (i.e., its officemates), as well as exactly 2k + 1 proxy nodes in the next group on the ring, and to 2k + 1 client nodes in the previous group on the ring. A node is assigned to the group hash(IP) mod √ N. Note that this assignment may be verified locally by any node. Nodes can discover the nodes in their own group (and thus connect to their officemates) and in the next one using a (robust) peer sampling service. By making each node sort the list of the nodes in its own group and in the next one by increasing hashes and making the j-th node in group i choose node number j + 1,..., j + k in group i + 1 as proxies, we obtain the overlay required by DPol, with the desired uniformity property, in a scalable and decentralized fashion. The overlay construction protocol, while being deterministic in its initial design, can be randomized by concatenating a random value shared by all nodes to the nodes' IP addresses when computing the hashes.

Privacy

We now assess the privacy guarantees provided by DPol when the dishonest nodes are placed (i.e., the groups they belong to and their set of clients and proxies) uniformly at random.

Theorem 8 (Privacy). The probability for a given node to have its vote recovered by a coalition of B dishonest nodes is bounded by (B/N) k+1 .

Proof. We proved in Theorem 2 that the vote of a node is recovered with certainty by the dishonest nodes if and only if the k + 1 proxies who received the k + 1 ballots containing a vote for the chosen candidate collude. This event occurs with probability B k+1 / N k+1 when nodes are randomly distributed in the overlay. For all k, B and N, this probability is bounded by (B/N) k+1 .

In order to link the average level of privacy guaranteed by the protocol to the parameter k, the system administrator needs to estimate the proportion of dishonest nodes. However, it is important to note that DPol is oblivious of this proportion: be the proportion of dishonest nodes higher than the estimation, the level of privacy offered would be lower than expected but DPol would still function properly.

Accuracy

We now report on the evaluation of DPol in the binary case over the PlanetLab testbed. The goal of the evaluation is to compare DPol against the presented theoretical bounds. Our experiments focus on binary polling. These experiments show that, in a practical setting, DPol suffers an average impact of dishonest nodes of around (4k + 2)B on the outcome of the poll (i.e., the score of the first candidate minus the score of the second candidate). With a proportion α of nodes voting for the first candidate, the outcome is αN -(1 -α)N = N(2α -1).

We consider the worst case: dishonest nodes perform every possible attack that does not compromise their reputation with probability 1 to promote the second candidate, i.e., each dishonest node (i) sends 2k + 1 ballots (0, 1), and (ii) inverts every ballot (1, 0) it receives into a ballot (0, 1). Figure 6 We observe that the dishonest coalition affects the outcome of the poll within the theoretical bound derived in the analysis (dotted lines in Figure 6). Since a dishonest node can impact the score of each candidate by up to 3k + 2, its maximum impact on the outcome is 6k + 4. However, the average impact of the coalition is less than 6k + 4 (considering the worst case where the dishonest proxy receives only ballots (1, 0) and inverts them all). The theoretical bound is never reached as the average impact of a dishonest node depends on the actual number of ballots it can invert; this, in turn, depends on the proportion α of nodes voting for the first candidate.

Effectively, a voting node sends k + 1 ballots (1, 0) out of 2k + 1 if it votes for the first candidate and k otherwise. Therefore, the number of ballots (1, 0) received by a proxy is (2k + 1) α k+1 2k+1 + (1 -α) k 2k+1 = k + α on average. The impact of a dishonest user who turns ballots (1, 0) into ballots (0, 1) is 2(k + α) on average. In addition, dishonest nodes impact the outcome by another 2k by sending 2k + 1 ballots (0, 1) during the voting phase. Their total impact is therefore around 4k + 1.

Considering a system with B such dishonest users, the biased outcome can be expressed as N(2α -1) -B(4k

+ 2α) = 2(N - B)(α -1
2 ) -B(4k + 1). For k = 2, fitting our 55-data point cloud with a least-squares regression line (plain line in Figure 6) a(α - 1 2 ) + b gives a = 791 and b = -163. This is close to the expected parameter values a = 2(N -B) = 760 and b = -B(4k + 1) = -180. We use this analysis to make a projection on larger scale systems. For k = 1 (Figure 6(a)), every node of the poll outputs a valid binary results when α > 0.62, which is to be compared to α > 0.55 observed in Figure 3(b) (without dishonest nodes). On average, we can derive analytically that with N = 10, 000 and B = 99, the proportion α for which all nodes decide correctly is α > 0.52.

Security

Assuming that dishonest nodes are able to choose their proxies and clients, we have shown in Lemma 7 that they can both perform and cover dishonest actions as soon as the number of dishonest nodes in two consecutive groups is greater than √ N. In other words, the protocol is secure against this attack when the condition ∀i, |g i ∩ B|+|g i+1 ∩ B| < √ N holds. If B < √ N, this condition holds with certainty, regardless of the distribution of dishonest nodes among groups. Otherwise, there is a nonzero probability that the condition is violated.

Theorem 9 (Tolerance to dishonest nodes). The probability that B dishonest nodes compromise the system (i.e., control two consecutive groups as defined in Lemma 7) We first show that if B ≥ N 2 then dishonest nodes will compromise the system regardless of their allocation to groups. We prove the contrapositive statement, so suppose no groups are compromised. Then |g i ∩ B| < √ N for all groups i. Summing the inequalities up for all the √ N groups, we get

∑ i |g i ∩ B| + |g i+1 ∩ B| < N, that is, 2 ∑ i |g i ∩ B| < N, which implies that 2B < N and finally B < N/2. Thus if B ≥ N
2 , then some pair of consecutive groups is compromised.

We now consider the case where B < N 2 . Let β = B N < 1 2 be the proportion of dishonest nodes in the system. By the standard Hoeffding bounds for sampling from a finite population without replacement, the probability that groups i and i + 1 are compromised is:

p i = P |G i ∩ B| ≥ √ N = P |G i ∩ B| -2 √ Nβ ≥ 2 √ N 1 2 -β ≤ exp -4 √ N 1 2 -β 2 .
The right-hand function converges to zero exponentially fast in √ N since β < 1 2 . Using the union bound, the probability that some pair of consecutive groups have been compromised is:

p = P i {|G i ∩ B| ≥ √ N} ≤ √ N ∑ i=1 P |G i ∩ B| ≥ √ N ≤ √ N exp - √ N (1 -2β ) 2 ,
which also converges to zero as N grows to infinity if β < 1 2 . We can conclude that the probability of a compromise incurs a phase transition when half of the nodes in the system are dishonest. The asymptotic number of dishonest nodes that DPol can tolerate is therefore N/2.

We now evaluate the probability of the system being compromised by simulation. We first assume that dishonest nodes are randomly distributed among the groups. For example, groups could be built consecutively, i.e., the first group is built by picking √ N nodes uniformly at random, the second is built by picking uniformly at random √ N nodes from the remaining nodes, and so forth. Under this assumption, the probability of violating the condition of consecutive groups being compromised can easily be computed. In Figure 7(a), we plot this probability as a function of B in a 10, 000-node network. It can be seen that for B < 2, 900 the probability is less than 1%. Therefore, if the deterministic bound is relaxed by using a probabilistic bound instead, the number of dishonest nodes that the system can tolerate is consistently higher. In Figure 7(b), we plot the maximum number of dishonest nodes that the system can tolerate, that is the maximum number of dishonest nodes tolerated to keep the probability of violating the above condition below 1%).

Detecting dishonest nodes with private verifications

We now evaluate the probability of detecting a dishonest node cheating within the bounds derived in Section 4.2 when honest nodes agree to disclose private information with a nonzero probability.

Theorem 10. There is nonzero probability of detecting a dishonest node which misbehaves, even if its impact on each candidate score is less than 3k + 2.

Proof. Consider as a first step the binary case (as shown in Section 4.2.2, the results obtained in the binary case can be easily extended to for d > 2). Assume that each node is willing to disclose each of the ballots it sent or received with probability p d > 0. Now suppose a dishonest node sends k > k + 1 ballots of the same kind, say k ballots (0, 1). This node is detected by a private verification if at least k + 2 of its proxies who received a ballot (0, 1) disclose it. Therefore, the probability for the dishonest node to be detected is:

k ∑ j=k+2 k j p j d (1 -p d ) k -j .
Similarly, consider a dishonest node that receives n + b ballots (1, 0) and turns n of them into ballots (0, 1). The dishonest node is detected by a private verification if at least n + bn + 1 of its clients disclose the ballots they sent to it. Therefore, the probability for the dishonest node to be detected is:

n + b ∑ j=n + b -n+1 n + b j p j d (1 -p d ) n + b -j .

Related Work

We now discuss related distributed voting protocols with particular attention on those that do not depend on intractability of mathematical computations. Like most non-cryptographic voting protocols, DPol ensures privacy via secret sharing techniques. DPol distinguishes itself from related work in the sense that no participant has a special role, following the peer-to-peer paradigm, which results in increased scalability and robustness.

A large amount of work on secret sharing schemes (introduced by Rivest et al. in [START_REF] Shamir | How to Share a Secret[END_REF]) has been published in the late 80's. Benaloh [START_REF] Benaloh | Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret[END_REF] proposed a scheme for privately sharing secrets based on polynomials. Since this scheme is homomorphic with respect to addition, it may be used for polling. However, a dishonest participant can easily corrupt the initial shares in the protocol, thus potentially impacting the final outcome to a significant degree.

Assuming a majority of honest participants, Rabin and Ben-Or extended Benaloh's secret sharing and proposed verifiable secret sharing scheme (VSS) [START_REF] Rabin | Verifiable Secret Sharing and Multi-Party Protocols with Honest Majority[END_REF]. Based on VSS, they proposed a secure multi-party computation (MPC) protocol to privately compute the sum of the participants' inputs with an exponentially small error on the output. Beyond the fact that these techniques assume a fully connected network, synchronous links and broadcast channels, they involve higher mathematics. Moreover, since there is no control over the input itself (in contrast to DPol where the ballots are in {0, 1} for each candidate and therefore the vote is at most ±(2k + 1)), a dishonest participant may still share an arbitrarily high value and thus affect the outcome in a potentially unbounded way. Series of followup work on MPC have improved various aspects of the scheme, but only recently begun thinking about making it scalable and usable in practice [START_REF] Damgård | Scalable and Unconditionally Secure Multiparty Computation[END_REF][START_REF] Damgård | Scalable Multiparty Computation with Nearly Optimal Work and Resilience[END_REF]. The appeal of this class of protocols lies in strong privacy guarantees to participants, including the dishonest ones, but also makes such schemes less suitable for polling applications. Note that the same issues also apply to complex secret sharing scheme and private multiparty computation such as AMPC [START_REF] Malkhi | Anonymity without 'Cryptography[END_REF].

In [START_REF] Malkhi | E-Voting without 'Cryptography[END_REF], Malkhi et al. proposed an e-voting protocol based on AMPC and enhanced check vectors. While powerful, participants of this protocol have distinct and predefined roles (dealers, talliers, and receivers). This may result in decreased scalability as the load of distributing initial ballots to voters falls on a small set of nodes that are not part of the system (i.e., dealers) and robustness if specific nodes fail. Nonetheless, these design choices are fully justified by the requirements inherent in e-voting applications, such as democracy, verifiability, and unconditional accuracy. Instead, polling applications can relax such constraints for the sake of simplicity. Another related distributed voting protocol is the one proposed by Baudron et al. [START_REF] Baudron | Practical Multi-candidate Election System[END_REF] but it uses asymmetric cryptography.

At a high level, DPol also relates to distributed ranking schemes. The principle of ranking is similar to polling, in that a participant evaluates the quality of one of her peers by (i) locally grading its behavior (input value), and (ii) collecting the local grades assigned by the rest of the system. However, to the best of our knowledge, most published work [START_REF] Gupta | A Reputation System for Peer-to-Peer Networks[END_REF][START_REF] Rodriguez-Perez | Analysis of Peer-to-Peer Distributed Reputation Schemes[END_REF] has focused on designing accurate grading mechanism rather than providing efficient polling schemes. Dutta et al. [START_REF] Dutta | The Design of a Distributed Rating Scheme for Peer-to-Peer Systems[END_REF] consider grading free riders and take into account potential collusion. Nevertheless, none of the proposed ranking schemes provide a global polling mechanism, as grading generally relies on polling only a subset of nodes (peers usually collaborate with a small part of the network). In addition, privacy is generally not addressed in these schemes.

Conclusion

We considered the distributed polling problem in a social network where participants are concerned about their reputation. To address it, we presented DPol, a simple fully decentralized polling protocol and proved that it can ensure privacy and accuracy, despite the presence of dishonest participants, by means of verification procedures. Our contribution is therefore twofold. First, we define a new model of faulty nodes in distributed systems which incorporates the human and social nature of participants through privacy and reputation concerns. Second, we provide a combination of secret sharing and verification techniques to ensure privacy and accuracy under this model. We find our model of adversaries to be compelling for various non-critical (i.e., not sensitive to small deviations on their outcome) private and secure distributed computation problems in social settings and that DPol thus paves the way for a new area of research in distributed computing. In this spirit, a natural extension of our protocol is to support arbitrary aggregation functions and revisit traditional problems of distributed computing. For instance, can distributed consensus be reached under this model?

Turning our model and DPol into a solution that can be adopted in practice will require some effort. First, our model of adversaries in social networks asserts that honest participants will always report misbehaviors, and that dishonest participants do not blame honest participants because this may eventually be detected, thus tarnishing the reputation of the dishonest participants. To make these assumptions more realistic in practice, the challenge is to design an automated tool to help users of a social network evaluate and quantify the reputation of a participant by cross-checking information such as tags and social connectivity. Given the selectivity and specificity of such a tool, it would be interesting, within the framework of game theory, to study equilibria and optimal strategies for non-cooperating participants who attach different values to their privacy, their reputation, the outcome of the poll and the accuracy of the tally. Second, DPol relies on a number of assumptions to provide privacy and accuracy guarantees, including the uniform assignment of nodes to groups, synchronization between different phases of the protocol, a limited rate of churn, and that the number of nodes is a perfect square. We intend to address each of these assumptions to make DPol a practical peer-to-peer protocol.

  p's clients (P c ) p's proxies (P p ) p's officemates (P o )

Algorithm 1

 1 DPol at node p in group g i , i ∈ {0,..., r -1} Input: a vote v ∈ {1,...,d} Variables: an individual tally t = 0 a local tally t = 0 an array of local tally sets S [{0,...,r -1} → ∅] a local tally array T [{0,...,r -1} → ⊥] Output: the global tally t

  (b)) and share intermediate results (Figure 2(c)). To this end, a proxy sums the ballots it received into an individual tally t (line 10 in Algorithm 1). Once a node has received the expected number of ballots from its clients, it broadcasts the computed individual tally to its officemates, as depicted in Figure 2(b) (lines 17-19 in Algorithm 1). The officemates aggregate the received data, i.e., they sum each others' individual tallies (line 14 in Algorithm 1) and store the result summed with their individual tally into a local tally t as shown in Figure 2(c) (line 3 in Algorithm 1).

Figure 2 :

 2 Figure2: Key phases of DPol with d = 2. (a) A node in g i-1 generates 3 (k = 1) ballots {(1, 0), (1, 0), (0, 1)} and sends them to its proxies in g i . (b) A node in g i collects its received ballots {(1, 0), (1, 0), (1, 0)} and sums them to (3, 0) (individual tally) and shares the tally with its officemates in g i as depicted in (c). (c) A node receives all expected individual tallies {(3, 0), (2, 1), (1, 2)}, then computes and sends the local tally ((9, 3)) to its proxies in the next group g i+1 as depicted in (d). (d) The proxies in g i+1 forward the local tally to their proxies in g i+2 .

  ∑ r-1 i=0 |g i | = N. The two quantities M and S are minimized when r = N/k and |g i | = √ Nk, and thus M = S = O( √ Nk). Proposition 3 (Time complexity). Under the assumption of a synchronous system where time evolves in rounds, DPol operates in O(max |g i | + rk) rounds.

  Fraction of node deciding correctly on the winner.

Figure 3 :

 3 Figure 3: Accuracy of the algorithm in presence of asynchrony, message loss and failures (N = 400 and k = 2). [400 nodes PlanetLab tested]

  displays for k = 1 and k = 2 the resulting tally (sign on the upper part of the figure and value on the lower part), compared to the real one (dashed line), for B = 19 dishonest nodes (B = √ N -1) in a system of N = 400 nodes.

= 2 Figure 6 :

 26 Figure 6: Accuracy of the poll in the presence of dishonest nodes: with N = 400 and B = 19, dishonest nodes manage to confuse the majority of the nodes for (a) α < 0.62 when k = 1, and (b) α < 0.73 when k = 2. [400 nodes PlanetLab tested]

  controlling two successive groups Proportion of dishonest nodes (B/N) Probability of ring being compromised as the fraction of dishonest nodes grows. of dishonest nodes tolerated Number of nodes (N) probabilistic bound (< 1%) deterministic upper bound (N/2) deterministic lower bound ( √ N ) (b) Number of dishonest nodes tolerated to keep probability of compromise below 1%.

Figure 7 :

 7 Figure 7: Average tolerance to dishonest nodes.

  To anthropomorphize the discussion, suppose that votes are being cast for d distinct candidates representing the different options of the poll. Recall that the global tally is the d-ary vector ∑ p c v p + N • k • (1,..., 1), whose components correspond to the tallies for each candidate in the poll.

	Theorem 3. For B <	√ N, every member of a dishonest coali-
	tion may affect each candidate score up to 3k + 2 without being
	detected by public verifications.

  Since g i and g i+1 are disjoint, this event is equivalent to |G i ∩ B| ≥ √ N where G i = g i ∪ g i+1 for all i.

	and converges to 0 exponentially fast in	√	is 1 when B ≥ N 2 , N when B < N 2 .

Proof. As defined in Lemma 7, groups i and i + 1 have been

compromised if |g i ∩ B| + |g i+1 ∩ B| ≥ √ N.

This work has been partially supported by the ERC Starting Grant GOSS-PLE number 204742. is (Ýmir Vigfússon1 Maxime Monod has been partially funded by the Swiss National Science Foundation with grant 20021-113825.


B Bernecker

T Callegari

J P Boeuf

Evidence of a New Form of Self-Organization in DBD Plasmas: The Quincunx Structure

Self-organized, stable or dynamic, filamentary structures are known to form in dielectric barrier discharges (DBDs) operating in a glow regime. The common "classical" understanding of stable filamentary structures in DBDs is that a glow discharge filament forms at each half-cycle of the sinusoidal applied voltage at the same spatial location along the dielectric surface. The "memory" charges deposited by the previous filament on the dielectric surfaces are responsible for the ignition of a new discharge at the same location. On the other hand, the formation of a filamentary discharge at a given location inhibits discharge development in its vicinity because of charge spreading along the dielectric surface leading to a decrease of the gap voltage in this region. In this paper we show, using experiments and models that another self-organized filamentary regime is possible and coexists with the "classical" regime. In this regime, never reported before, discharge filaments at successive half cycles do not occur at the same location but are shifted by half a spatial period. We call this regime the "quincunx" regime. We also show that the mechanisms of this regime may be responsible for some dynamical aspects of self-organization in DBDs.

Introduction

Dielectric Barrier Discharges (DBDs) are electric discharges between electrodes covered with a dielectric layer and excited by sinusoidal or pulsed voltages. The dielectric layers play the role of capacitance and limit the discharge current. DBDs are the easiest way to generate and control non equilibrium plasmas at elevated pressures and this explains the numerous applications of these discharges 1 , from ozonizers to polymer or textile surface treatment applications, and to UV excimer sources or plasma display panels [START_REF] Boeuf | Plasma display panels-physics, recent developments and key issues[END_REF] .

DBDs are also a very interesting and fascinating tool to study self-organized patterns in spatially extended nonlinear dissipative systems 3 . When operating in a simple parallel plate and glow discharge regime the plasma of DBDs is generally not uniform and consists of many filaments perpendicular to the electrodes, sometimes arranged in organized structures, and that can be observed through transparent electrodes. These filaments, termed as "dissipative solitons" (DS) in Ref. [3], exhibit particle-like behaviour. They can form hexagonal patterns representing a crystal-like state as well as liquid-and gas-like patterns, but isolated stationary or travelling DSs interacting through scattering, generation and annihilation phenomena are also observed 3 . Some of the properties of the self-organized filaments are characteristic of reaction-diffusion or Turing systems and attempts have been made to develop semiphenomenological models based on reaction-diffusion equations able to mimic their behaviour 4,5 (this has however been done mainly for discharges with ohmic and not capacitive layers). In these approaches the variables that are solutions of the reaction-diffusion system may be the local current density and voltage across the gas gap 4 and the axial behaviour of the discharges is represented only by a typical Confidential: not for distribution. Submitted to IOP Publishing for peer review 11 May 2011 non-linear, s-shaped, current-voltage characteristics. This approach is very interesting and useful to find the necessary "ingredients" in a reaction-diffusion system that allow to mimic the behaviour of the many-body system formed by the filaments and to study the properties of the resulting non-linear system. More work is however needed to improve the justification of these ingredients in term of basic discharge physics. Another approach, based on the basic physics of a glow discharge represented by a simple fluid model (drift-diffusion Poisson) has been able to reproduce and explain the formation of glow-discharge filamentary structures in DBDs [6][7][8] .

In this paper we report experimental and modelling results that show evidence of the existence of a filamentary regime of DBDs that is not consistent with the common understanding that DBD filaments in a stationary pattern take place at the same location at each half cycle. This new regime, called the "quincunx" regime because filaments of a given half cycle take place in between filaments of the previous cycle, is observed in quasi 1D DBD arrangements and its existence is predicted and can be explained by fluid models. The existence of this stationary regime is very interesting because it appears that the mechanisms responsible for its existence may also be responsible for some dynamical aspects of filamentary discharges that are not clearly understood.

Experimental arrangement, fluid model, and conditions of a DBD glow regime

Patterns in DBDs can be observed in quasi two-dimensional (2D) or one-dimensional (1D) structures. In the first case, the discharges take place for example between two parallel disk shaped electrodes covered with a dielectric layer 8,9 . If one of the electrode is transparent (Indium Tin Oxide or fine metallic mesh) a 2D pattern can be observed through the electrode (the discharge axis is perpendicular to the observation plane). Quasi 1D structures can be formed for example between two facing line electrodes deposited on thin dielectric layers. The width of the electrodes must be on the order of the filament diameter so that only one filament can form at a given location along the electrode. A linear structure of filaments can therefore develop along the line electrodes. Such an arrangement has be used in the experiments of Walhout et al. 10 . The structures than can be observed in this geometry are much less complex than in the 2D arrangement, but the advantage of the 1D structure is that it allows to observe the discharges both along the electrodes (where the structures form) and across the electrodes (so the details of discharge formation can be viewed with a fast camera). We call x the direction across the electrodes (discharge axis) and y the direction along the electrode. Another advantage of the 1D arrangement is that the experimental results can be directly compared with results from 2D discharge models where simulations are performed in the (x,y) plane.

In this paper we use a 1D experimental arrangement and the experimental results are compared with results from a 2D fluid model similar to the one used in Refs. [11, 12] to describe plasma display panel DBDs, and in Refs. [6, 7] in the context of pattern formations in DBDs. The experimental set-up is shown in Fig. 1. The electrode arrangement of Fig. 1 is placed in a vacuum chamber that can be pumped and filled with a gas mixture. In this paper we show results obtained in neon at pressure around 50 torr, ambient temperature. It is very difficult to reproduce, with the model, the same features as in the experiments at the same discharge conditions. This is because the DBD in a filamentary regime is a very non-linear system that can be sensitive to many details (gas impurities, dielectric surface properties) beyond the global discharge parameters (nature of the gas, pressure, voltage and frequency). Small variations in these "details" or in the global discharge parameters may trigger bifurcations from a self-organized stationary regime to another one or to a dynamical regime.

Discharge axis

In the modeling part of this work we therefore did not try to reproduce the discharge in the exact conditions of the experiments, but the aim was rather to show that different discharges regimes observed in the experiments can be reproduced and explained by the model under similar (not necessarily identical) conditions. We also wanted to show that the simplest possible discharge model, containing the basic, first order features (drift-diffusion electron and ion transport with direct electron impact ionization depending on the local electric field, secondary electron emission by ion impact on the surfaces, and Poisson's equation) is sufficient to reproduce many features of the selforganization phenomena in DBDs.

The conditions considered in the model results presented in this paper are: DBD in neon, with dielectric thickness and gas gap of 2 mm, electrode length of 2 cm, gas pressure of 50 torr, voltage frequency of 20 kHz, secondary electron emission coefficient of neon ions on the surface equal to 0.3. The relative permittivity of the dielectric is 5, and symmetry boundary conditions are used at the end of the electrodes in the y direction.

Under the conditions considered in the experiments and in the models the DBDs operate in a transient glow discharge regime, i.e. the electron multiplication in the gap is sufficiently low that discharge breakdown and maintenance is the result of electron multiplication in the volume associated with secondary electron emission at the surface (i.e. the regime is far from a streamer regime).

Observation of "classical" and "quincunx" filamentary structures through experiments and models

Figure 2 shows a typical picture of a periodic filamentary structure in the quasi 1D experimental arrangement of Fig.

1 Our observations show that the "classical" filamentary regime of Fig. 2 can bifurcate toward a different, unexpected regime, never reported before, where the filaments of successive half cycles do not take place at the same locations along the electrodes, but are shifted from the pattern of the previous half cycle by half a spatial period (see Fig. 3). This filamentary periodic structure, that we will call "quincunx" structure has therefore a spatial period equal to half that of the "classical" structure. The filaments at a given half cycle of the voltage do not form at the same locations as the filament of the previous half cycle, but in between these filaments.

The existence of the quincunx structure is quite unexpected since our understanding of pattern formation in DBDs relies on the fact that filaments form preferentially where memory charges have been deposited during the previous half cycle and inhibit the formation of filaments in their vicinity because the spreading of the charges on the dielectric surface is larger than the size of each filament [6][7][8] . In term of reaction-diffusion systems, volume ionisation (due to the gap voltage) and surface charge (the voltage due to memory charges deposited by the previous filament adds to the gap voltage) play the role of an activator, while surface charging in a second phase plays the role of an inhibitor since the decrease of the gap voltage in the vicinity of a forming filament due to charge spreading along the dielectric surface limits discharge formation around this filament.

Although this image is correct, it is also possible, under some conditions, that the voltage drop associated with the spreading of the charges along the dielectric layers during filament formation at a given half cycle does not completely quench discharge formation between these filaments but allows the formation of a lower current discharge (e.g. much less luminous "Townsend" discharge). This has been illustrated in the experimental and modelling results of Bernecker et al. 13 .

Although the current density of the Townsend discharges between filaments is much less than the current density of the glow discharge filaments, the duration of these low discharge currents can be much longer and lead to a total charge transferred between filaments on the same order as the charge transferred by the filaments. Moreover the model also shows that, because of the longer duration of the Townsend discharges, the density of remaining ions in the gap at the location of these discharges can be much larger than at the locations of the filamentary discharges. This higher remaining volume charge density between filaments, combined with the fact that the charge transferred by the filaments and by the discharges between filaments are equivalent lead, at the next half cycle, to the triggering of discharges in between the filaments of the previous halfcycle. This qualitative explanation is supported by the 2D fluid model, which is able to predict the bifurcation from the classical to the quincunx regimes when some discharge parameters are changed. Figure 4a and4b show the time integrated electron densities and ionisation rate in the quincunx regime as provided by the model. Figure 5a shows the time integrated picture of an experimental linear DBD in neon, 300 torr, 880 V and 50 kHz voltage amplitude and frequency, 3 mm gap. On this figure, the discharge seems to correspond to a static quincunx filamentary regime similar to the one described above (Fig. 11). Figures 5b,c,d, e actually show that the discharge is more complex and present some dynamical features that are periodic with a period equal to three times the period of the applied voltage. The picture of Fig. 5b has been taken with a gate of 10 µs (i.e. one half-cycle) and show that only 1/3 of the filaments expected in a half-cycle quincunx pattern are actually present. Integrating in time over two successive half-cycles gives the picture of Fig. 5c. The filaments of the second half-cycle are shifted by half a spatial period of the quincunx structure of Fig. 5a (the cathode sheath is on the opposite side with respect to the previous filaments). Figures 5d and5e show that at each half cycle, the new filaments are shifted by a half a spatial period. The structure of Fig. 5 is therefore not static and presents an apparent organized motion of several filaments from right to left. The spatial period of this motion is equal to 3 periods of the applied voltage (integrating over 6 halfcycles would give a picture close to that of Fig. 5a).

The experimental results of Fig. 5 are very interesting since they show that the motion of filaments can be due to mechanisms similar to those responsible for the existence of the quincunx regime (i.e. remaining charges in the discharge volume close to a filament trigger the next discharge on the side of this filament). The fact that the motion appears to be from right to left in Fig. 5 is not clear (broken symmetry) and may be associated with the discharge history and memory charge effects.

In the 1D electrode configuration of Fig. 5, we were able to capture many other dynamical features (not reported here) of the filaments, such as filament merging and division. Some of these features could be reproduced with the models.As mentioned above, under specific conditions, the filaments of DBDs are not static but appear to be moving along the dielectric surface and interact with each other (merging or division of filaments). The filaments motion can be chaotic in appearance but is sometimes organized. An example of apparent motion of filaments is shown in Fig. 5.

Conclusion

Evidence of a new form of self-organized filamentary pattern in a quasi 1D DBD in a glow regime, the "quincunx" structure has been shown experimentally and with fluid models of the discharge. In this regime filaments of a given half cycle of the sinusoidal voltage form between filaments of the previous half cycle, in contrast with the "classical" structure of stationary filamentary DBD patterns.

In the quincunx regime, long lasting low current (dark) discharges between filaments transfer a similar amount of surface charge than the filamentary discharges but because of a larger remaining volume charge between filaments, the filamentary discharges at the next half cycle are triggered between the previous ones. The existence of this regime results from a competition between volume and surface charges in triggering the new filaments, and may explain some dynamical aspects of DBD filaments.

Figure 1 :

 1 Figure 1: Quasi 1D DBD configuration used in the experiments. The 1 mm width, 7 cm length electrodes are deposited on 1 mm thick epoxy dielectric layers. The gas gap is 3 mm and 50 torr neon is used in the experiments.

Figure 2 :

 2 Figure2shows a typical picture of a periodic filamentary structure in the quasi 1D experimental arrangement of Fig.1. The maxima of the light emission close to the dielectric surfaces correspond to the negative glow regions of the discharges. Since the picture is integrated in time these maxima are observed on both sides of the gas gap. Each electrode plays in turn the role of a cathode and of an anode, and the maxima in the light emission actually take place alternatively in front of each electrode at successive half cycles of the sinusoidal voltage. The periodic pattern of Fig.2therefore corresponds to the "classical" filamentary regime where the discharges form at the same spatial locations along the electrode at each half cycle (in opposite directions, i.e. each electrode is alternatively a cathode and an anode).

Figure 3 :

 3 Figure 3: Picture of a filamentary "quincunx" structure in the linear electrode arrangement of Fig. 1, in neon, 50 torr with voltage amplitude and frequency 524 V and 30 kHz respectively ; the picture of (a) is integrated over one cycle of the applied voltage (and accumulated over many cycles), while the pictures of (b) and (c) are taken over two different half cycles and accumulated over many cycles.

Figure 4 :

 4 Figure 4 : Space distribution of the electron density (a), (b), (c), and ionisation rate (d), (e), (f) from the 2D model in a quincunx filamentary regime neon, 50 torr, 700 V and 20 kHz voltage amplitude and frequency ; (a), (d) the density and ionisation rate are averaged over one cycle, (b), (e) over a half-cycle, (c), (g) over the following half-cycle.The densities are plotted on a 3 decades log scale, with a maximum of 2 10 9 cm -3 for (a) and 4 10 9 cm -3 for (b), (c). The ionisation rates are on a linear scale with maximum 0.5 10 16 cm -3 s -1 for (d), and 10 16 cm -3 s -1 for (e) and (f).

Figure 5 :

 5 Figure 5 : Multiperiodic filamentary discharge in a quasi 1D DBD experiment in neon, 300 torr, 880 V, 50 kHz, 3 mm gap, 2 mm dielectric layers: (a) time integrated picture of the discharge (standard camera); (b), (c), (d), (e), pictures of the discharge taken with an ICCD camera and integrated over gates of 10, 20, 30, and 40 µs, i.e. 1, 2, 3, 4 half-cycles respectively.