elective-stereophonic
elective-stereophonic
Local and global states
Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Nxt Client: Nxt 1.11.15

Author Topic: Local and global states  (Read 1987 times)

benjyz

  • Hero Member
  • *****
  • Karma: +71/-4
  • Offline Offline
  • Posts: 508
    • View Profile
Local and global states
« on: November 26, 2014, 11:41:51 am »

I'll make some comments on the global and local view problem in this new thread.

Quote
Blocktree is a data which each node can locally store and exchange with others like with the blockchain.

I believe the fundamental property is that nodes have never the same view of the entire structure. Formally: there are N nodes and each node has a list of states S_N_i. The total state of the system is T = {N_1_S_i, ..., N_k_j}. T is never known by anyone. This can be confirmed by looking at the memory pool of each node in a real network. So before we have convergence of any sort, we have local states LS. The global state GS is not the the same as T. GS is what nodes agree on. The problem is that as soon as each node starts to sync data, the data is already old. Some of this can be seen more easily by considering the case of different latencies for subgraphs. Imagine a graph where some nodes connected by a very connection, and others by a very slow connection. Slow nodes will always be out-of-sync and would be unreliable. Fast nodes would prefer to sync with other fast nodes.

Some of this could shown easier with some empirical data. I'll try and work this out more with data and formal methods.
Logged

benjyz

  • Hero Member
  • *****
  • Karma: +71/-4
  • Offline Offline
  • Posts: 508
    • View Profile
Re: Local and global states
« Reply #1 on: November 26, 2014, 11:48:14 am »

In other words: Global state is the past blockchain. The last block is always in the past. For T, I would need to know everything each node knows. An instant update is not possible because information takes time to travel. The knowledge of these imbalance is very present in Highfrequency trading. HFT is now using even micro-waves between market avenues. See this fascinating account of the practise of HFT micro-wave channels:

https://sniperinmahwah.wordpress.com/2014/09/22/hft-in-my-backyard-part-i/
https://sniperinmahwah.wordpress.com/2014/10/02/hft-in-my-backyard-iii/
Logged

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: Local and global states
« Reply #2 on: November 27, 2014, 12:47:54 pm »

I believe the fundamental property is that nodes have never the same view of the entire structure. Formally: there are N nodes and each node has a list of states S_N_i. The total state of the system is T = {N_1_S_i, ..., N_k_j}. T is never known by anyone. This can be confirmed by looking at the memory pool of each node in a real network. So before we have convergence of any sort, we have local states LS. The global state GS is not the the same as T. GS is what nodes agree on. The problem is that as soon as each node starts to sync data, the data is already old. Some of this can be seen more easily by considering the case of different latencies for subgraphs. Imagine a graph where some nodes connected by a very connection, and others by a very slow connection. Slow nodes will always be out-of-sync and would be unreliable. Fast nodes would prefer to sync with other fast nodes.

1. There's awesome CAP theorem http://en.wikipedia.org/wiki/CAP_theorem - the root of all the problems in distributed networks.
2. Global decentralized cryptocurrency should be C, A and P the same time, and it's against CAP theorem
3. Satoshi proposed elegant hack around that with blockchain persistent data structure.
4. This exciting hack generates other problems :) scalability etc
5. There's no global state in a cryptocurency (and it's not possible to have  global state with strong consistency in AP network, while weak consistency is painful for a currency). So yes, we have only local views, while consensus algorithms  try to build some common view for majority of nodes at the moment (while minority seats in forks).
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

benjyz

  • Hero Member
  • *****
  • Karma: +71/-4
  • Offline Offline
  • Posts: 508
    • View Profile
Re: Local and global states
« Reply #3 on: November 27, 2014, 12:58:33 pm »

Yes, I'm going to have to read more about CAP. reminds me of this: http://www.aaronsw.com/weblog/squarezooko

I think these issues become important when trying to do state-transition functions (loops / SC's). I believe they are not possible, and so far from discussions with ethereum people I'm more confident that this is actually the case. Consensus has to be based on something like Chomsky type 3: http://en.wikipedia.org/wiki/Chomsky_hierarchy  . Latency and order of transactions has been so far not well understood. In stock markets both are very important (arbitrage principle).
« Last Edit: November 27, 2014, 01:03:58 pm by benjyz »
Logged

benjyz

  • Hero Member
  • *****
  • Karma: +71/-4
  • Offline Offline
  • Posts: 508
    • View Profile
Re: Local and global states
« Reply #4 on: November 27, 2014, 10:34:40 pm »

A link on CAP theorem, I found by coincidence

http://nathanmarz.com/blog/how-to-beat-the-cap-theorem.html

And Clojure author Rich Hickey commenting:

Quote
As long as we continue to use lax language like mutable/updateable data we will be without the tools to describe, think about, and build better systems that independently manipulate identity, value and place, and correctly handle time.

https://news.ycombinator.com/item?id=3108827

I bought into Hickey's idea of data as memory being a flawed idea. Facts are always atomic in time. If we state in almost any programming language x = 5 and later x = 22, what can this mean? X was 5 at one time, and later became 22. So, according to this understanding, the same statement is x_1 = 5, x_2 = 22. With local views we have a new way of considering this. Any view is always partial - aggregated we get consensus. An example of a system where the output is one variable is a market price. The price of one item reflects many views (a different kind of consensus, modelled by economists since Walras and Bachelier). So sum of the functions (/views) gives the total output, but the summing function is very complex (compare Topos theory, http://en.wikipedia.org/wiki/Topos)
« Last Edit: November 27, 2014, 10:37:09 pm by benjyz »
Logged

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: Local and global states
« Reply #5 on: November 28, 2014, 04:55:57 pm »

Yes, I'm going to have to read more about CAP. reminds me of this: http://www.aaronsw.com/weblog/squarezooko

I think these issues become important when trying to do state-transition functions (loops / SC's). I believe they are not possible, and so far from discussions with ethereum people I'm more confident that this is actually the case. Consensus has to be based on something like Chomsky type 3: http://en.wikipedia.org/wiki/Chomsky_hierarchy  . Latency and order of transactions has been so far not well understood. In stock markets both are very important (arbitrage principle).

If features on top of blockchain(including scripting, assets exchange) are pure functions from current blockchain, there are no additional consensus problems here, I guess.
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

benjyz

  • Hero Member
  • *****
  • Karma: +71/-4
  • Offline Offline
  • Posts: 508
    • View Profile
Re: Local and global states
« Reply #6 on: November 28, 2014, 09:43:22 pm »

The ordering problem which I mentioned briefly highlights some more general problems of blockchains. Ordering problem means: some transaction types are global - basically exchange transactions. Matching is essentially a multi-way transaction, like traffic of cars meeting at one single place. When arbitrage principle applies, order of execution matters. And actually it occurs to me know order of execution of transaction is closely related to order of execution of computation. I don't think this has been clearly described yet, but I had not enough knowledge to explain clearly enough. Solving at this at scale will be impossible, based on traditional knowledge of block-chains. Something quite different is needed for that.

Blockchains solve consensus. But the P2P network requires some fairness. Actually mining is not fair anymore, but in the beginning Bitcoin mining was fair. however today, mining is still location invariant - the position of the node in physical space should not matter. Which is why long blocktimes are essential (and <10 second block-times would lead to failures).
Logged
 

elective-stereophonic
elective-stereophonic
assembly
assembly