The Experts below are selected from a list of 13836 Experts worldwide ranked by ideXlab platform
Roger Wattenhofer - One of the best experts on this subject based on the ideXlab platform.
-
DISC - Randomness vs. Time in Anonymous Networks
Lecture Notes in Computer Science, 2015Co-Authors: Jochen Seidel, Jara Uitto, Roger WattenhoferAbstract:In an Anonymous Network, symmetry breaking tasks can only be solved if randomization is available. But how many random bits are required to solve any such task? As it turns out, the answer to this question depends on the desired runtime of the algorithm. Since any randomized Anonymous Network algorithm can be decomposed into a randomized 2-hop coloring stage and a deterministic stage, we tackle the question by focusing on the randomized stage. We establish that for any reasonable target function f, there is a randomized 2-hop coloring scheme running in $$\mathcal {O} fn$$ time. Our coloring scheme allows to trade an increase in runtime by a factor of d for a decrease by the $$d^\text {th}$$ root in the random bit complexity. To show that the achieved trade-off is asymptotically optimal for any choice of f, we establish a trade-off lower bound. Our bounds yield that it is sufficient to consider the cases when f is between $$\Omega \log ^*n$$ and $$\mathcal {O} \log \log n$$. We obtain that for the two extreme cases, i.e., where $$f \in \Theta \log ^*n$$ and $$f \in \Theta \log \log n$$, the random bit complexity is $$\Theta \root d \of {n}$$ and $$\Theta \log n$$, respectively, for any constant d. The trade-off achieved by our scheme is asymptotically optimal for any f, i.e., reducing the runtime must lead to an increase in the random bit complexity.
-
Randomness vs. Time in Anonymous Networks
2015Co-Authors: Jochen Seidel, Jara Uitto, Roger WattenhoferAbstract:In an Anonymous Network, symmetry breaking tasks can only be solved if randomization is available. But how many random bits are required to solve any such task? As it turns out, the answer to this question depends on the desired runtime of the algorithm. Since any randomized Anonymous Network algorithm can be decomposed into a randomized 2-hop coloring stage and a deterministic stage, we tackle the question by focusing on the randomized stage. We establish that for any reasonable target function f, there is a randomized 2-hop coloring scheme running in O(f(n)) time. Our coloring scheme allows to trade an increase in runtime by a factor of d for a decrease by the dth root in the random bit complexity. To show that the achieved trade-off is asymptotically optimal for any choice of f, we establish a trade-off lower bound. Our bounds yield that it is sufficient to consider the cases when f is between Ω(log∗ n) and O(log log n). We obtain that for the two extreme cases, i.e., where f ∈ Θ(log∗ n) and f ∈ Θ(log log n), the random bit complexity is Θ( d√ n) and Θ(log n), respectively, for any constant d. The trade-off achieved by our scheme is asymptotically optimal for any f, i.e., reducing the runtime must lead to an increase in the random bit complexity.
-
Computability in Anonymous Networks: Revocable vs. Irrecovable Outputs
Automata Languages and Programming, 2014Co-Authors: Yuval Emek, Jochen Seidel, Roger WattenhoferAbstract:What can be computed in an Anonymous Network, where nodes are not equipped with unique identifiers? It turns out that the answer to this question depends on the commitment of the nodes to their first computed output value: Two classes of problems solvable in Anonymous Networks are defined, where in the first class nodes are allowed to revoke their outputs and in the second class they are not. These two classes are then related to the class of all centrally solvable Network problems, observing that the three classes form a strict linear hierarchy, and for several classic and/or characteristic problems in distributed computing, we determine the exact class to which they belong.Does this hierarchy exhibit complete problems? We answer this question in the affirmative by introducing the concept of a distributed oracle, thus establishing a more fine grained classification for distributed computability which we apply to the classic/characteristic problems. Among our findings is the observation that the three classes are characterized by the three pillars of distributed computing, namely, local symmetry breaking, coordination, and leader election.
-
ICALP (2) - Computability in Anonymous Networks: Revocable vs. Irrecovable Outputs
Automata Languages and Programming, 2014Co-Authors: Yuval Emek, Jochen Seidel, Roger WattenhoferAbstract:What can be computed in an Anonymous Network, where nodes are not equipped with unique identifiers? It turns out that the answer to this question depends on the commitment of the nodes to their first computed output value: Two classes of problems solvable in Anonymous Networks are defined, where in the first class nodes are allowed to revoke their outputs and in the second class they are not. These two classes are then related to the class of all centrally solvable Network problems, observing that the three classes form a strict linear hierarchy, and for several classic and/or characteristic problems in distributed computing, we determine the exact class to which they belong.
Olivier Festor - One of the best experts on this subject based on the ideXlab platform.
-
A Bird's Eye View on the I2P Anonymous File-sharing Environment
2012Co-Authors: Juan Pablo Timpanaro, Isabelle Chrisment, Olivier FestorAbstract:Anonymous communications have been gaining more and more interest from Internet users as privacy and anonymity problems have emerged. Among Anonymous enabled services, Anonymous file-sharing is one of the most active one and is increasingly growing. Large scale monitoring on these systems allows us to grasp how they behave, which type of data is shared among users, the overall behaviour in the system. But does large scale monitoring jeopardize the system anonymity? In this work we present the first large scale monitoring architecture and experiments on the I2P Network, a low-latency message-oriented Anonymous Network. We characterize the file-sharing environment within I2P, and evaluate if this monitoring affects the anonymity provided by the Network. We show that most activities within the Network are file-sharing oriented, along with Anonymous web-hosting. We assess the wide geographical location of nodes and Network popularity. We also demonstrate that group-based profiling is feasible on this particular Network.
-
NSS - A bird's eye view on the I2P Anonymous file-sharing environment
Network and System Security, 2012Co-Authors: Juan Pablo Timpanaro, Isabelle Chrisment, Olivier FestorAbstract:Anonymous communications have been gaining more and more interest from Internet users as privacy and anonymity problems have emerged. Among Anonymous enabled services, Anonymous filesharing is one of the most active one and is increasingly growing. Large scale monitoring on these systems allows us to grasp how they behave, which type of data is shared among users, the overall behaviour in the system. But does large scale monitoring jeopardize the system anonymity? In this work we present the first large scale monitoring architecture and experiments on the I2P Network, a low-latency message-oriented Anonymous Network. We characterize the file-sharing environment within I2P, and evaluate if this monitoring affects the anonymity provided by the Network. We show that most activities within the Network are file-sharing oriented, along with Anonymous web-hosting. We assess the wide geographical location of nodes and Network popularity. We also demonstrate that group-based profiling is feasible on this particular Network.
-
TMA - I2P's usage characterization
Traffic Monitoring and Analysis, 2012Co-Authors: Juan Pablo Timpanaro, Isabelle Chrisment, Olivier FestorAbstract:We present the first monitoring study aiming to characterize the usage of the I2P Network, a low-latency Anonymous Network based on garlic routing. We design a distributed monitoring architecture for the I2P Network and show through three one-week measurement experiments the ability of the system to identify a significant number of all running applications, among web servers and file-sharing clients.
-
i2p s usage characterization
Traffic Monitoring and Analysis, 2012Co-Authors: Juan Pablo Timpanaro, Isabelle Chrisment, Olivier FestorAbstract:We present the first monitoring study aiming to characterize the usage of the I2P Network, a low-latency Anonymous Network based on garlic routing. We design a distributed monitoring architecture for the I2P Network and show through three one-week measurement experiments the ability of the system to identify a significant number of all running applications, among web servers and file-sharing clients.
-
I2P's Usage Characterization
2012Co-Authors: Juan Pablo Timpanaro, Isabelle Chrisment, Olivier FestorAbstract:We present the first monitoring study aiming to characterize the usage of the I2P Network, a low-latency Anonymous Network based on garlic routing. We design a distributed monitoring architecture for the I2P Network and show through three one-week measurement experiments the ability of the system to identify a significant number of all running applications, among web servers and file-sharing clients. Additionally, we identify 37% of published I2P applications, which turn out to be unreachable after their publication on the I2P distributed database.
Seiichiro Tani - One of the best experts on this subject based on the ideXlab platform.
-
Compression of View on Anonymous Networks—Folded View—
IEEE Transactions on Parallel and Distributed Systems, 2012Co-Authors: Seiichiro TaniAbstract:View is a labeled directed graph containing all information about the Network that a party can learn by exchanging messages with its neighbors. View can be used to solve distributed problems on an Anonymous Network (i.e., a Network that does not guarantee that every party has a unique identifier). This paper presents an algorithm that constructs views in a compressed form on an Anonymous n-party Network of any topology in at most 2n rounds with O(n6\log n) bit complexity, where the time complexity (i.e., the number of local computation steps per party) is O(n6\log n). This is the first view-construction algorithm that runs in O(n) rounds with polynomial bits complexity. The paper also gives an algorithm that counts the number of nonisomorphic views in the Network in O(n6\log n) time complexity if a view is given in the compressed form. These algorithms imply that some well-studied problems, including the leader election problem, can deterministically be solved in O(n) rounds with polynomial bit and time complexity on an Anonymous n-party Network of any topology.
Xinyuan Wang - One of the best experts on this subject based on the ideXlab platform.
-
DSN - On the effectiveness of low latency Anonymous Network in the presence of timing attack
2009 IEEE IFIP International Conference on Dependable Systems & Networks, 2009Co-Authors: Jing Jin, Xinyuan WangAbstract:In this paper, we introduce a novel metric that can quantitatively measure the practical effectiveness (i.e. anonymity) of all Anonymous Networks in the presence of timing attack. Our metric is based on a novel measurement of the distortion of the packet timing between the incoming and the outgoing flows to and from the Anonymous Network and it uses wavelet based analysis to measure the variability of the distortion. To the best of our knowledge, our approach is the first practical method that can quantitatively measure the packet timing distortion between flows that may have gone through such transformations as flow mixing/spliting/merging, adding chaff, packet dropping. To validate our anonymity metric, we have conducted real-time timing attacks on various deployed Anonymous Networks such as Tor, anonymizer.com and have used the timing attack results as the ground truth for validating our anonymity metric. We have found strong correlation between our anonymity metric and the timing attack results. Our metric measurements and timing attack results show that the circuit rotation in Tor Network could significantly increase its resistance to timing attack at the cost of more timing disturbances to the normal users. In addition, we have found that adding constant rate chaff (i.e. cover traffic) has diminishing effect in anonymizing packet flows.
Lawrence L. Larmore - One of the best experts on this subject based on the ideXlab platform.
-
Self-stabilizing silent disjunction in an Anonymous Network
Theoretical Computer Science, 2017Co-Authors: Ajoy K. Datta, Stéphane Devismes, Lawrence L. LarmoreAbstract:In this paper, we give a distributed silent self-stabilizing algorithm, DISJ, for the disjunction problem in a connected Network. In this problem, each process x has an input bit x.in, assigned by the application layer, and each process must compute the disjunction of the input bits of all processes. DISJ is uniform, and works in an Anonymous Network under the distributed unfair daemon. The stabilization time of DISJ is O(n) rounds, where n is the size of the Network, and the memory requirement per process is O(logD+) where D and are, respectively, the diameter, and the maximum degree of the Network.
-
ICDCN - Self-stabilizing Silent Disjunction in an Anonymous Network
Distributed Computing and Networking, 2013Co-Authors: Ajoy K. Datta, Stéphane Devismes, Lawrence L. LarmoreAbstract:Given a fixed input bit to each process of a connected Network of processes, the disjunction problem is for each process to compute an output bit, whose value is 0 if all input bits in the Network are 0, and 1 if there is at least one input bit in the Network which is 1. A uniform asynchronous distributed algorithm DISJ is given for the disjunction problem in an Anonymous Network. DISJ is self-stabilizing, meaning that the correct output is computed from an arbitrary initial configuration, and is silent, meaning that every computation of DISJ is finite. The time complexity of DISJ is O(n) rounds, where n is the size of the Network. DISJ works under the unfair daemon.
