Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
399
questions
0
votes
2
answers
2k
views
Vector clock :why Singhal Kshemkalyani differential technique require FIFO for message passing?
Singhal–Kshemkalyani’s differential technique is based on the
observation that between successive message sends to the same process,
only a few entries of the vector clock at the sender process ...
- 101
2
votes
0
answers
85
views
Why is a primary node needed in pBFT algorithm for consensus?
Why is primary needed in pBFT algo? Since many issues of viewchange etc. come up because primary may be faulty - is it possible to have a version of pBFT which doesn't have nodes assigned as primary? ...
- 121
2
votes
1
answer
155
views
What are the recents topics of research that combine both systems research and theoretical computer science?
I am an undergraduate majoring in Computer Science and Mathematics.
For my undergraduate research, I would like to work on something that lies in the overlap between systems research and theoretical ...
0
votes
0
answers
108
views
How is Eventual Consistency (EC) better than Strong Consistency (SC) when N = 3, R=W=2 when SC gives better consistency gurantee in same config?
In dynamo paper, it says that in production most of the users set N = 3, R = 2 and W = 2.
...
- 157
2
votes
0
answers
189
views
Byzantine generals (n=3, m=1)
Leslie Lamport describes a algorithm to come to consensus for the case for n>3*m, there m is the number of traitors in ...
- 21
1
vote
1
answer
187
views
Strong Uniform Total Order vs Weak Uniform Total Order
The definition for SUTO and WUTO is the following:
Suto
If some process TODelivers some message m before message mʹ, then a process TODelivers mʹonly after it has TODelivered m.
And for WUTO
...
- 111
3
votes
1
answer
791
views
What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion?
After reading Lamport Algorithm for Mutual Exclusion, I can not understand the purposes of reply messages. I think they are not necessary because the assumption of the algorithms is that all messages ...
- 171
3
votes
1
answer
234
views
Impossibility of Distributed Consensus with One Faulty Process
I'm reading Fischer et al.'s Impossibility of Distributed Consensus with One Faulty Process, and I don't quite follow 2 points:
The first is in the proof of Lemma 3, pg. 378:
Otherwise, $e$ was ...
- 141
0
votes
1
answer
38
views
Bloom Filter which does not fit in RAM [closed]
Is it possible to efficiently create a bloom filter with 10^12 buckets on a single machine with 32GB of RAM and a hard drive. We can assume that the keys are already on the disk and are small in size?
- 101
0
votes
0
answers
40
views
BFT algorithm perfo
Understand that BFT algorithms are always prepared for the worst possible circumstances and pays a price for this in terms of speed.
Can one reasonably make the statement / assessment that non BFT ...
- 111
2
votes
0
answers
698
views
How to compare distributed systems and big data
Are there scientific papers that compare distributed systems and big data processing systems?
Big data processing systems can be batch processing systems or streaming big data processing systems.
A ...
- 1,198
1
vote
0
answers
42
views
Tendermint Consensus - Resilient up to 1/3 of Byzantine participants
Tendermint Consensus is resilient for up to 1/3 of Byzantine participants.
Question: What actually happens after when the network hits the threshold of byzantine actors? Forking happens? Does ...
- 111
2
votes
1
answer
360
views
Async Distributed Algorithm Time Complexity
In theory of distributed systems, I understand message complexity and time complexity are common performance measures, with the first being the number of messages sent in the overall execution of the ...
- 21
4
votes
0
answers
796
views
Even distribution algorithm
Right now I am working on a distributed system that sends messages from single source to many nodes. It is necessary that certain messages are sent to the same node to ensure order of processing. ...
- 143
1
vote
0
answers
57
views
Number of replicas needed for fault tolerance in state machine replication
I am trying to get my head around "State Machine Replication". I understand that it is a way to ensure resilience against failures. I have read that in order to provide fault tolerance against normal ...
- 11
2
votes
0
answers
118
views
Are Synchronous Message Order and Total Message Order separate concepts?
I am currently studying this book on distributed systems. In the chapter on message ordering the authors appear to use the term total message ordering and synchronous message ordering interchangeably. ...
- 265
0
votes
0
answers
136
views
a problem with Suzuki-Kasami mutex algorithm
I have some sort of a misunderstanding regarding the Suzuki-Kasami distributed mutex algorithm. I am writing my question here because I failed on gaining access to the original paper.
I will call ...
- 722
0
votes
1
answer
125
views
Chord protocol - How should I go about mapping nodes to placeholders on the ring?
In the real world, how is a node mapped to the position on the ring,
Each nodes's IP address is hashed using SHA-1 hashing algorithm which will produce this hash - 73.128.154.69 hashed into ...
- 103
1
vote
0
answers
161
views
bakery algorithm, switching up the condition
I'm currently studying the Bakery Algorithm. I understand it for what it is but now I want to switch it up a bit.
If we changed the < in the 2nd ...
- 11
2
votes
1
answer
51
views
Soft question: program result verification
Let's say there's a cloud computing service that allows people to run arbitrary programs and get the results. The idea being that your machine is too slow, and you don't want to overwhelm it. If your ...
- 257
1
vote
2
answers
164
views
Are consensus (and atomic broadcast) protocols limited by single node's resources?
The main question is the following:
When designing a system supporting atomic broadcast, can it be proved theoretically that the performance & scalability dimensions (i.e. latency, throughput, ...
- 163
1
vote
0
answers
10
views
Where can I find practice for given atom instructions, implement ME
I'm trying to practice for my upcoming distributed systems test. My teacher said that their will be a problem where he'll give us atomic instructions and we're going to have to implement Mutual ...
- 11
1
vote
1
answer
63
views
Enforcing application layer consensus on top of a distributed consensus protocol
If I understand correctly, the term "consensus" in distributed consensus algorithms means that all the participants ("peers") achieve a common understanding of some data value. Different algorithms ...
- 113
0
votes
1
answer
290
views
What us difference between distributed computing and workgroup computing?
According to the definition, distributed computing means to distributed a problem among different users while workgroup computing means to work on a problem by different users. So what's the ...
- 1
1
vote
0
answers
208
views
Distributing Neural Network Training World-Wide Using Blockchain?
I just finished reading a white-paper from a recent AI startup. The company, Deep Brain Chain, wants to distribute neural network training over computers worldwide, using blockchain technology. Here ...
- 131
7
votes
1
answer
1k
views
How are lamport timestamps useful in practice?
I am reading Lamport's paper titled Time, clocks, and the ordering of events in a distributed system
I understand what's in there more or less, but I am confused whether Lamport timestamps on their ...
- 171
3
votes
1
answer
92
views
FLP Impossiblity Result assumption of $C_1 = e'(C_0)$
FLP86's famous proof regarding impossibility of async distributed processes with a single fault assumes in the proof of the third lemma the existence of an event $e'$ such that the neighbor ...
- 41
6
votes
1
answer
2k
views
Why are forks in the Blockchain eventually resolved?
I'm reading Wattenhofer's The Science of the Blockchain. On page 87, he states the following thoerem:
Theorem 7.22. Forks are eventually resolved and all nodes eventually agree on which is the ...
- 940
1
vote
1
answer
95
views
Question about IO automaton
I'm currently reading Nancy Lynch book about distributed systems, chapter about IO automaton. And I have following questions related to book exercise 8.13(c).
We are given some automaton A with sig(A)...
- 113
3
votes
1
answer
267
views
Is it possible to write a wait free leader election algorithm?
I want to understand if there exists an algorithm which is wait free and operates on non-shared memory, asynchronously.
Finally I want to know how to derive the consensus number of this algorithm.
...
- 265
3
votes
2
answers
138
views
Sequential History in Herlihy and Wing's Linearizability paper
I've been reading Herlihy and Wing's paper Linearizability: A Correctness Condition for Concurrent Objects (ACM Transactions on Programming Languages and Systems, 12(3):463–492, 1990; PDF) and ...
- 133
3
votes
1
answer
86
views
affinity based static load balancing
I am trying to find a good model the following problem:
Given a collection of work packets x, y, z, ..., and a collection of worker nodes ...
- 133
-1
votes
1
answer
179
views
Source code for Network File System [closed]
I am doing a small project which explains how operations (file open, file write etc.) are done in client side and server side in network File system. Can anyone help me out providing its source code ...
4
votes
2
answers
517
views
Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system?
Just what the title says.
Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system (without a single point of failure)?
My current thoughts are that this ...
- 65
1
vote
1
answer
408
views
Does Paxos consensus algorithm scale linearly?
I'm trying to build a P2P web application using Paxos to obtain a consensus value.
How well does Paxos scale? linearly? or what kind of distribution can you expect? E.g. in using 10 to 10,000 users ...
- 131
2
votes
0
answers
64
views
Auction website with Paxos consensus algorithm
As a project, I'm trying to construct a P2P auction web application with paxos in a high latency environment. The idea is that each user visiting the website will keep a small log file with the ...
- 131
1
vote
1
answer
54
views
Verifying execution of code in trustless environment
Let us assume I have a Program P running on remote computer generating output O. Without trusting the remote environment and not having to verify the output O, is there is a way to validate that ...
- 113
0
votes
1
answer
601
views
sequential consistency is not composable
I am studying for my exam in Distributed Systems course. And i have one question that i do not really understand. This is the question:
...
- 1
2
votes
1
answer
366
views
Theory of message complexity analysis of distributed systems
Inspired by this post, I thought it would be a good idea to ask an analogous question in the context of distributed systems -
While most of us are familiar with the notion of Time Complexity as a ...
- 142
2
votes
1
answer
211
views
Consensus anomaly about read-write registers and test&set
I read this answer below and got into another question.
Why is the consensus number for test-and-set, 2?
I also read that read/write registers have consensus number 1.
But I see that in test&...
- 265
-2
votes
1
answer
34
views
Aren't the servers that store MYSQL database in Facebook down for maintenance ever as Facebook is always on? [closed]
I have never seen my account not being able to login!
- 23
0
votes
0
answers
53
views
Name for pattern of addressing items by sequence-of-creation
I'm looking for the name of a particular pattern, and/or resources (articles) on its usage.
The context of the pattern is a journalling system to operate on some collection, as in the example given ...
1
vote
0
answers
611
views
How to use version vectors to decide which value to keep?
I am trying to understand how to build an eventually consistent KV store. It's just a learning experiment. Let's only consider one value which stores a fruits list.
We have 2 servers, 2 clients, N=2, ...
- 141
0
votes
0
answers
27
views
Retroactively ordering actors' concurrent activity on disjoint sections of a data-structure
Hi! I'm new here, a terrible computer-scientist, and have no idea what I'm doing; I'm more expecting / hoping for links to research on algorithms or data-structures that contribute to problems like ...
- 101
0
votes
0
answers
135
views
Understanding leslie lamport's spacetime diagram with tick lines
I am trying to understand tick lines in Fig 2 on Page 2 of "Time, Clocks, and the
Ordering of Events in a Distributed System" paper [1]. Below are 2 things which I did not understand
What is the ...
- 101
3
votes
3
answers
287
views
Paxos made simple -- two details
I'm missing two details from Paxos made easy
P1. An acceptor must accept the first proposal that it receives.
What exactly is the reason for rule P1? What if the rule P2 was different, i.e. Upon ...
- 31
0
votes
0
answers
42
views
What's a good method to decide wheter distributed or parallel computing?
I've already programed a grammatical evolution on GPU with a very satisfactory result (an improvement on time of about 140% with relative small datasets, expecting better results whith big ones). ...
- 221
0
votes
0
answers
196
views
Spanning-Tree-Protocol and BFS? (Distributed Computing)
Given is graph with networks and bridges/switches. We know, the root
Bridge is the bridge with the minimal Bridge-ID. The connections between every bridge and network is 1.
In the lecture slides they ...
- 219
1
vote
1
answer
1k
views
Calculate execution time from linear speedup
Given an execution time $t(c_1)$ and linear speedup $s$, how do you calculate the execution time for $c_2$ processor cores?
(Assuming Gustafson's law, or in other words, $t(\infty)=0$)
My ideas:
I ...
- 168
5
votes
2
answers
6k
views
Why is Two-Phase Commit (2PC) blocking?
Can anyone let me know, why 2PC is blocking when the coordinator fails? Is it because the cohorts don't employ timeout concept in 2PC?
Good reference: Analysis and Verification of Two-Phase Commit &...
- 229